Розділ 3. Постановка і вирішення задачі

В зоомагазині продають 3 породи собак : вівчарка, пікінес, чау-чау. Для забезпечення нормальних умов їх утримання використовуються 3 види кормів. Кількість корму кожного виду, яку повинні отримувати собаки в середньому наведено в таблиці:

У таблиці вказана загальна кількість корму кожного виду, яке може бути використане зоомагазином, і прибуток від реалізації однієї собаки.

Визначити, скільки собак кожного виду слід тримати в магазині, щоб прибуток від їх реалізації був максимальним.

Алгоритм розвязання задач симплекс - методом

Поставлена описова завдання переводиться в математичну форму (цільова функція та обмеження).

Отримане математичний опис призводять до канонічної форми.

Канонічну форму призводять до матричному увазі.

Шукають перший допустиме рішення. Для цього матриця повинна бути правильною. Матриця в ЗЛП називається правильною, якщо вона містить мінімум m правильних (базисних) стовпців, де m - число рядків в матриці. Стовпець у канонічній ЗЛП називається правильним (базисним), якщо всі його елементи дорівнюють нулю, крім єдиного рівного одиниці.

Якщо матриця не є правильною, то її потрібно зробити такої з допомогою штучного базису. Для цього в матрицю потрібно дописати стільки базисних стовпців, щоб їх загальна кількість разом з уже наявними базисними стовпцями становило m. Після цього переходять до пункту 6. Якщо штучний стовпець виходить з базису, то його видаляють з матриці. Якщо вилучені всі штучні стовпці, то отримано перше допустиме рішення. Якщо штучні елементи не вдається вивести з базису, то система не має рішень.

Будують послідовність матриць. Потрібно визначити провідний стовпець, провідну рядок і ведучий елемент. Елемент, відповідний провідною рядку, видаляється з базису, а на його місце ставлять елемент, відповідний ведучому стовпцю. Складають рівняння перерахунку матриці, виконують перерахунок, а потім перевіряють його результати на оптимальність. Якщо рішення не оптимально, то заново обмежують провідний елемент, провідну рядок і ведучий стовпець.

Ознакою оптимальності рішення є наявність у векторі рішень тільки негативних або нульових коефіцієнтів при всіх обмеженнях.

Відповідь записується таким чином:

- Кожному негативного коефіцієнту у векторі рішення ставиться у відповідність нульовий коефіцієнт для відповідної змінної у відповіді.

- Для кожного нульового коефіцієнта у векторі рішення ставиться у відповідність значення вільного члена з рядка, що містить одиницю в стовпці даної змінної.

- Фіктивні змінні у відповіді не враховуються.

Провідним може бути призначений будь-який стовпець, що задовольняє одній з умов:

1) Перший стовпець, що містить позитивний елемент у векторі рішень.

2) Стовпець, що містить найбільший позитивний елемент у рядку рішення.

3) Якщо стовпець задовольняє умові max (C j min b j / a ij) при вирішенні на max, і m in (C j min b j / a ij) при вирішенні завдань на min.

C j - коефіцієнт цільової функції в стовпці j, a ij - коефіцієнт у стовпці j і рядку i.

Рішення завдання

Визначимо максимальне значення цільової функції

F (X) = 5000 Х1 +4300 Х 2 +6500 Х 3 при наступних умовах обмежень.

2x 1 + 1 x 2 + 3x 3 <= 100

3 x 1 + 0,5 x 2 + 2x 3 <= 250

5 x 1 + 1,5 x 2 + 1 x 3 <= 500

Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних.

2 x 1 + 1 x 2 + 3 x 3 + 1 x 4 + 0 x 5 + 0 x 6 = 100

3 x 1 + 0,5 x 2 + 2 x 3 + 0 x 4 + 1 x 5 + 0 x 6 = 250

5 x 1 + 1,5 x 2 + 1 x 3 + 0 x 4 + 0 x 5 + 1 x 6 = 500

З даних задачі створюємо вихідну симплекс таблицю:

Так як в стовбці вільних членів немає відємних елементів, то знайдено допустиме значення. В рядку F є відємні елементи, це означає що отримане рішення не оптимальне. Визначимо ведучий стовпчик. Для цього знайдемо в рядку F максимальний за модулем відємний елемент - це -6500. Ведучим рядком буде той для якого відношення вільного члена до відповідного елемента ведучого стовбця мінімальне. Ведучим рядком являється X4, а ведучий елемент 3.

В рядку F існують відємні елементи, це означає що отримане рішення не оптимальне. Визначимо ведучий стовпчик. Для цього знайдемо в рядку Fмаксимальний за модулем відємний елемент - це -2133.333. Ведучим рядком буде той для якого відношення вільного члена до відповідного елемента ведучого рядка мінімальне. Ведучим рядком являється Х5, а ведучим елементом 3,333.

Таблица 5

F=334000

при значеннях змінних: X3=15, X2=55, Х1=60.

Отже як висновок можна сказати. Що максимальний прибуток зоомагазину буде 334000 грн. якщо магазин буде продавати 60 вівчарок, 55 пекінесів та 15 чау-чау.

багатокритеріальність задача лінійна