Графічний метод розв’язування задачі лінійного програмування
В основі графічного методу лежить геометричний зміст задачі лінійного програмування. Застосовується цей метод у випадку , інакше важко будувати многокутник розв’язків.
Нехай задана задача лінійного програмування
;
,
.
Припустимо, що система ,
сумісна і многокутник розв’язків задачі обмежений. Кожна з нерівностей
,
визначає півплощину з межею ,
,
,
.
Перетин цих півплощин визначає многокутник .
Цільова функція при фіксованих значеннях є рівнянням прямої
.
Побудуємо і графік цільової функції при
. Тоді задача
-
означає: знайти вершину многокутника розв’язків, у якій пряма
є опорною і
при цьому набуває найбільшого (найменшого) розв’язку.
![]() |
Рисунок 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
З рисунка визначаємо: А – точка мінімуму .
,
,
,
,
,
.
.
Відповідь: ;
.