Page 13 - 6416

6 ПРИКЛАДИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ

6.1 Приклад розв’язання задачі лінійного програмування графічним методом
Задача 1
Розв’яжемо графічним методом таку задач лінійного програмування:

min : R   x  x  3x ,
1
2
x  6x  50 ,
1 2
2x  x  23,
1 2
4x  x  16 ,
1 2
 x  6x  21,
1 2
0
x , x  .
1 2
На координатній площині x 0x будуємо область допустимих розв’язків задачі, границі
1 2
якої утворюють рівняння прямих, що отримані шляхом заміни нерівностей відповідними
рівностями. Наприклад, нерівність x  6x  50 заміняємо на рівність x  6x  50 . Щоб
1 2 1 2
побудувати цю границю допустимої області необхідно задатись двома точками, через які
7
провести пряму лінію. Можна взяти x  . Тоді x  . Якщо тепер візьмемо x  , то
2
8
1 2 2
x  8. Через ці дві точки (2; 8) і (8; 7) проводимо пряму лінію. Аналогічно будуємо границі
1
допустимої області, що описуються рівняннями 2x  x  23, 4x  x  16 і x  6x  21.
1 2 1 2 1 2
Тепер розглянемо як графічно інтерпретуються нерівності. Кожна пряма ділить площину
x 0x на дві напівплощини; одна із них вміщує множину точок, які задовольняють
1 2
відповідну нерівність. Для визначення такої напівплощини необхідно взяти деяку «тестову»
точку, наприклад (0; 0). Якщо вона задовольняє нерівність, то таку напівплощину відмічаємо
стрілкою так як це показано на рис. 6.1. У тому випадку, коли нерівність не дійсна,
допустимі точки будуть належати напівплощині, що не вміщує «тестової» точки. Наприклад,
на рис 6.1 це пряма 4x  x  16.
1 2

Рисунок 6.1 – Графічне розв’язування задачі лінійного програмування
10