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

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

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

(6.1)

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

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

Рис. 1

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

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

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₁ (напрям ). Точку перетину знаходять через розв’язання системи рівнянь