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

Таким чином, для розв’язування даної задачі (1) – (2) досить побудувати многокутник, обумовлений системою (2) і одну з прямих виду  при будь-якому значенні z (зручно взяти пряму ), а потім за допомогою паралельного руху цієї прямої в напрямку вектора  визначити “крайні” точки многокутника: точку “входу” для задачі мінімізації функції або точку “виходу” для задачі максимізації. У випадку обмеженого многокутника  задача завжди має розв’язок.

Приклад 1. Знайти найбільше значення функції , при таких обмеженнях:

Розв’язання. Побудуємо многокутник , обумовлений системою обмежень, і пряму , задану рівнянням :

Паралельним перенесенням прямої  в напрямку вектора , визначимо точку многокутника , яка відповідає найбільшому значенню z (точку “виходу”). Це буде точка . Координати цієї точки визначаємо з умови перетину прямих ( ) і ( ):

 .

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

Відповідь: .

Приклад 2. Знайти найменше значення функції  при обмеженнях:

Розв’язання. Побудуємо многокутник , який задається даною системою обмежень, і пряму , задану рівнянням :

Паралельним переносом прямої  в напрямку вектора , визначаємо точку  многокутника , яка відповідає найменшому значенню z (точка “входу”). Координати цієї точки знайдемо з умови перетину прямих ( ) і ( ):

 .

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

Помічаємо, що задача максимізації даної функції при тих же вихідних обмеженнях розв’язку не має.

Відповідь: .

Приклад 3. Заводу необхідно скласти оптимальний по реалізації план виробництва двох видів виробів при обмежених можливостях чотирьох видів машин. Обидва види виробів послідовно обробляються на цих машинах. План випуску повинен бути таким, щоб від реалізації всієї виробленої продукції завод одержав найбільший можливий прибуток. План повинен також враховувати, що перший вид машин може працювати в день до 18 годин, другий – до 12, третій – до 12 і четвертий – до 9 годин. Час, необхідний для обробки кожного виду виробів на відповідних верстатах вказано у таблиці. Від реалізації одного виробу першого типу завод одержує 4 тисячі гривень, а від реалізації одного виробу другого типу – 6 тисячі гривень.

Розв’язання. Побудуємо відповідну математичну модель задачі. Нехай планом передбачається виготовити , виробів першого типу і  виробів другого типу. Враховуючи обмеженні запаси ресурсів, одержуємо таку систему нерівностей:

.

Прибуток при цьому буде визначатися такою цільовою функцією: .

Тепер побудуємо відповідний многокутник допустимих планів. Для цього спочатку нерівності попередньої системи замінюємо на рівності і будуємо відповідні прямі, а потім одержимо шуканий опуклий многокутник в результаті перетину відповідних півплощин.

Тепер будуємо довільну пряму із сімейства паралельних прямих даного виду: . Легко бачити, що для збільшення значення z необхідно рухати побудовану пряму паралельно самій в напрямку вектора . Остання, опорна пряма при цьому буде дотикатися до многокутника допустимих планів в точці , отже це шукана точка максимуму.

Відповідь: для максимального прибутку заводу необхідно виготовити 12 виробів першого типу і 6 виробів другого типу, прибуток при цьому буде складати  тисячі гривень.