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

Приклад. Знайти найбільше та найменше значення функції

якщо х₁ та х₂ задовольняють нерівностям (лежать в області D₁):

(6.1)

Розв’язування: – нормалі до прямих, які утворені заміною знаків «≤;» та «≥;» на знак «=». – нормаль до прямої

Будуємо область D₁ (рис. 1).

Рис. 1

Алгоритм побудови області D₁, може бути таким:

1. Будуємо прямокутник Р: ().

2. У побудованому прямокутнику шукаємо точки, які задовольняють першу нерівність Для цього будуємо пряму за двома точками перетину з осями координат (0, 6) та (6, 0). Пряма ділить прямокутник Р на дві частини. Та частина прямокутника, яка лежить у напрямку від прямої, має значення лівої частини рівності більші за 6 (у напрямку нормалі лінійна функція зростає), але щоб задовольнити першу нерівність треба розглядати всі значення х₁ та х₂ для яких ліва частина нерівності менша за 6. Цю умову буде виконано якщо в прямокутнику Р узяти частину, яка лежить на самій прямій та в напрямку антинормалі . Тобто, щоб задовольнити першу нерівність, треба брати точки прямокутника Р, які лежать на прямій і нижче від неї.

3. В одержаному чотирикутнику (трапеції), слід залишити лише ті точки, які задовольняють другу з нерівностей (6.1): . Аналогічно, як і в попередньому пункті, будуємо пряму . Точки, що нас цікавлять (де ) лежать в напрямку нормалі до прямої l₂, та на самій прямій.

4. В одержаному трикутнику слід вилучити точки, які не задовольняють умову (третій нерівності в (6.1)). Будуємо пряму і вибираємо точки на прямій та поза прямою в бік антинормалі . Одержимо знову чотирикутник (див. рис. 1).

5. Завершуємо побудову області D₁, вилученням з одержаного чотирикутника точок, що не задовольняють нерівності . Це точки, які лежать поза прямою в напрямку антинормалі . Одержуємо п’ятикутник АВСDE. Переходимо до виконання пункту 2.

Шукаємо оптимальні розв’язки.

1. знаходиться в крайній точці області D₁, в напрямку нормалі до L, .

2. знаходиться в крайній точці області D₁ в напрямку антинормалі . Крайньою точкою області D₁ будемо називати точку у якій перетинаються пряма з областю так, що будь-яке зміщення цієї прямої в окіл точки (в напрямку ) спричиняє відсутність на прямій точок області D₁; d – величина (відстань) на яку зміщується пряма в напрямку нормалі або антинормалі.

знаходиться шляхом обчислення функції L у точці перетину прямих l₂ та l₃ (напрям ). Точку перетину знаходять як результат розв’язку системи рівнянь – значення функції L у точці перетину осі х₂ з прямою l₁ (напрям ). Точку перетину знаходять через розв’язання системи рівнянь

Відповідь: .

Завдання для самостійних і контрольних робіт

Розв’язати графічно ЗЛП.

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.
29.		30.
31.		32.