13. Алгоритм графічного методу розв'язування задач лінійного програмування.

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

Розглянемо задачу.

Знайти

(2.17)

за умов:

(2.18)

.(2.19)

Розв’язати задачу лінійного програмування графічно означає знайти таку вершину багатокутника розв’язків, у результаті підстановки координат якої в (2.17) лінійна цільова функція набуває найбільшого (найменшого) значення.

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

1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв’язків задачі лінійного програмування.

4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5. Будуємо пряму с1х1 + с2х2 = const, перпендикулярну до вектора .

6. Рухаючи пряму с1х1 + с2х2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального значення.

7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.