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

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

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

;

, .

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

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

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

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

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

Рисунок 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

З рисунка визначаємо: А – точка мінімуму .

, , , , , .

.

Відповідь: ; .