Графічний метод розв’язування задачі лінійного програмування

В основі графічного методу лежить геометричний зміст задачі лінійного програмування. Застосовується цей метод у випадку , інакше важко будувати многокутник розв’язків.

Нехай задана задача лінійного програмування

;

, .

Припустимо, що система , сумісна і многокутник розв’язків задачі обмежений. Кожна з нерівностей ,

визначає півплощину з межею , , , .

Перетин цих півплощин визначає многокутник .

Цільова функція при фіксованих значеннях є рівнянням прямої .

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

Рисунок 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 вільні змінні. Оскільки , то вільних змінних буде дві: і . Таким чином, всі базисні змінні виражаються через вільні. Тоді, підставивши замість базисних змінних у цільову функцію їх вирази через змінні і , і перейшовши до нерівностей із двома змінними, одержимо задачу з двома невідомими. Розв’язавши одержану задачу графічно, одержимо і . Таким чином, знайдемо розв’язок .