Алгоритм рішення ЗЛП графічним методом

Розв’язок ЗЛП графічним методом складається з наступних етапів:

1) У площині х ₁ ох ₂ будуємо область припустимих планів даної ЗЛП – область W;

Мал. 4

2) Знаходимо вектор-градієнт ;

3) Будуємо лінію нульового рівня ;

4) Лінію нульового рівня переміщаємо уздовж градієнтного напрямку (див. мал. 4) і визначаємо ту вершину опуклого багатогранника, що вперше стикається з лінією рівня. Ця вершина й буде відповідати оптимуму цільової функції типу мінімум

Потім лінію рівня переміщаємо вглиб ОДЗ (див. мал. 4) і відшукуємо ту вершину багатогранника після якої лінія рівня буде залишати зазначену область. Ця вершина й буде відповідати оптимуму цільової функції типу максимум

.

5) Для одержання чисельного розв’язку задачі знаходимо координати відповідних вершин багатогранника й обчислюємо значення цільової функції в цих точках.

Приклад. Деяке підприємство освоїло виробництво продукції двох видів А і В, використовуючи при цьому сировину чотирьох типів S₁, S₂, S₃, S₄. Запаси сировини й норма її витрат на виробництво одиниці продукції зазначені в таблиці. Відомо, що прибуток підприємства від реалізації одиниці продукції виду А становить 7 у.о., а від реалізації одиниці товару типу В - 5 у.о. Визначити такий план випуску продукції, який би дозволив підприємству отримати максимальний прибуток.

Вид продук- Вид ції сировини	А	В	Запаси сировини
S1
S2
S3
S4
Прибуток

Сформулюємо задачу математично. Через х ₁ позначимо кількість виробів виду А, а через х ₂ – кількість виробів виду В, які необхідно виготовити за планом. Умова функції – прибуток підприємства від реалізації виробленої продукції.

(1) (2) (3) (4)

Дотримуючись послідовності дій при використанні графічного методу розв’язку, будуємо область припустимих планів W (використовуючи систему обмежень ЗЛП і умови невід’ємності, вектор-градієнт цільової функції , лінію нульового рівня 7 х ₁ + 5 х ₂ = 0).

Мал. 5.

Переміщаючи лінію нульового рівня уздовж градієнтного напрямку, знаходимо, що

Визначимо координати вершини Р ₄.

Визначник системи

Тому що , те система сумісна по теоремі Крамера і має єдиний розв’язок

Обчислимо допоміжні визначники

Тоді, по формулах Крамера знаходимо

Таким чином, Р ₄(5; 3). Знаючи координати точки Р ₄, визначимо максимальне значення цільової функції

Виходить, що для одержання максимального прибутку в розмірі 50 у.о. підприємству при заданих обмеженнях на запаси сировини варто робити п'ять виробів типу А и три вироби типу В.