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

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

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

 

 


Мал. 4

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

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

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

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

.

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

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

 

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

 

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

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


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

 
 

 

 


Мал. 5.

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

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

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

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

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

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

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

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