Графічний метод розв’язування задачі лінійного програмування
В основі графічного методу лежить геометричний зміст задачі лінійного програмування. Застосовується цей метод у випадку 
, інакше важко будувати многокутник розв’язків.
Нехай задана задача лінійного програмування
; 
, 
. 
Припустимо, що система , сумісна і многокутник розв’язків задачі обмежений. Кожна з нерівностей ,
визначає півплощину з межею 
, 
, 
, 
.
Перетин цих півплощин визначає многокутник 
.
Цільова функція при фіксованих значеннях 
є рівнянням прямої 
.
Побудуємо і графік цільової функції при 
. Тоді задача - означає: знайти вершину многокутника розв’язків, у якій пряма є опорною і 
при цьому набуває найбільшого (найменшого) розв’язку.
 |
Рисунок 4.3
Відомо, що значення цільової функції зростає у напрямку вектора 
. Тому пряму 
пересуваємо паралельно до себе у напрямку 
, поки вона не стане опорною для .На рис.4.3 пряма 
стає опорною до в двох точках 
і 
. Враховуючи напрям вектора нормалі , одержимо, що максимум досягається в точці , а мінімум – у точці . Тут можливий випадок, коли мінімум (максимум) досягається у вершині або на стороні .
Якщо - необмежений, то можливі випадки:
1) пряма постійно перетинає многокутник і ніколи не стає опорною до нього, тоді цільова функція необмежена знизу і зверху (рис.4.4):
 |
Рисунок 4.4
2) пряма стає опорною до :
– обмежена зверху і необмежена знизу, – точка максимуму, мінімуму не існує (рис.4.5):
 |
Рисунок 4.5
3) f- обмежена знизу і необмежена зверху, В- точка мінімуму, максимуму не існує (рис.4.6):
Рисунок 4.6
4) – обмежена знизу і зверху: на АС досягається максимум, на BD – мінімум (рис.4.7):
 |
Рисунок 4.7
Якщо система - несумісна, то множина допустимих розв’язків порожня, тому задача оптимального розв’язку не має.
Приклад 4.1 Задача про використання сировини
;
, ;
Побудуємо . Для цього зобразимо прямі
(1) Вектор 
(2)
(3)
(4)
(5)
Рисунок 4.8
Точка А – точка максимуму. Знайдемо її координати. Оскільки А – точка перетину (2) і (3), то її координати задовольняють систему
; 
;
; 
;
; 
;
Отже, 
.
Відповідь: 
.
Приклад 4.2. Задача про дієту
;
, ;
Межі : 
; (1)
; (2)
; (3)
; .
Вектор 
Побудуємо многокутник розв’язків:
 |
Рисунок 4.9
А – точка мінімуму функції , і є точкою перетину прямих (1) і (2):
;
;
,
, 
.
Отже, 
.
Відповідь: 
.
Зауваження. За допомогою графічного методу можна розв’язувати задачі лінійного програмування з 
змінними і 
обмеженнями-рівностями, якщо 
.
Нехай рівняння системи обмежень лінійно незалежні. Тоді методом Жордана-Гаусса можна знайти m базисних змінних, які виражаються через n-m вільні змінні. Оскільки 
, то вільних змінних буде дві: 
і 
. Таким чином, всі базисні змінні виражаються через вільні. Тоді, підставивши замість базисних змінних у цільову функцію їх вирази через змінні і , і перейшовши до нерівностей із двома змінними, одержимо задачу з двома невідомими. Розв’язавши одержану задачу графічно, одержимо 
і 
. Таким чином, знайдемо розв’язок 
.
Приклад 4.3. Розв’язати задачу лінійного програмування
;
, …, 
.
Тут 
, 
, 
.
Розв’яжемо систему обмежень. Нехай 
, 
, 
– базисні
| 
| 
| 
| 
|
|
| -1 | -1 | ||||
| -1 | |||||
| -1 | -2 |
Підставимо у :
Система обмежень матиме вигляд
Маємо задачу з двома змінними 
і 
.
Будуємо многокутник розв`язків, лінію рівня, вектор нормалі
- (рис. 4.10)
Рисунок 4.10
З рисунка визначаємо: А – точка мінімуму .
, 
, 
, 
, 
, 
.
.
Відповідь: 
; 
.