Лекція 7. Задачі лінійного програмування

Правило. Нехай — вершини опуклого многокутника (рис.6). Щоб знайти найбільше і найменше значення функції на даному многокутнику, досить знайти значення цієї функції кожній вершині цього многокутника . Найбільше серед знайдених значень і буде найбільшим значенням функції на многокутнику , а найменше — найменшим. При цьому може трапитися, що найбільше (найменше) значення досягається в усіх точках якоїсь сторони многокутника.

Рис.6

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

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

Множиною точок, які задовольняють систему нерівностей, є опуклий многокутник — многокутник розв’язків (див. рисунок 7).

 Рис.7

Вершини знайдемо, розв’язавши системи рівнянь:

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

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

Відповідь: .

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

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗАННЯ

Завдання 1. Знайти найбільше і найменше значення лінійної функції за умови, що змінні задовольняють співвідношенню 

 Завдання 2. Знайти найбільше значення лінійної функції за умови, що змінні задовольняють співвідношенню 

 Завдання 3. Знайти найбільше і найменше значення лінійної функції:

 а) ; 

 б)

 за умови, що змінні задовольняють співвідношенню 

 Завдання 4. Побудувати опуклий многокутник, заданий системою нерівностей 

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

Завдання 5. Побудувати опуклий многокутник, заданий системою нерівностей 

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

 

 

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

Розглянемо геометричну інтерпретацію задачі лінійного програмування на прикладі.

Задача. Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Техніко-економічні показники вирощування цих культур маємо у табл.:

Таблиця

Показник 

(із розрахунку на 1 га)Озима пшеницяЦукрові бурякиНаявний ресурс

Затрати праці, людино-днів525270

Затрати праці механізаторів, людино-днів2880

Урожайність, тонн3,540—

Прибуток, тис. грн.0,71—

Критерієм оптимальності є максимізація прибутку.

Запишемо економіко-математичну модель структури виробництва озимої пшениці та цукрових буряків, ввівши такі позначення:

— шукана площа посіву озимої пшениці, га;

— шукана площа посіву цукрових буряків, га.

Задача лінійного програмування має такий вигляд: за умов: 

Геометричну інтерпретацію задачі зображено на рис.8

 Рис.8

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад , задає півплощину з граничною прямою . Будуємо її і визначаємо півплощину, яка описується нерівністю . З цією метою в нерівність підставляємо координати характерної точки, скажімо, і . Переконуємося, що ця точка належить півплощині . Цей факт на рис.8 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають й іншим нерівностям. У результаті перетину цих півплощин утворюється область допустимих розв'язків задачі (на рис.8 — чотирикутник АВСD). Цільова функція являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z = 0, то маємо . Ця пряма проходить через початок системи координат. Коли Z = 3,5, то маємо пряму .

Зауваження. Для розв’язання задачі лінійного програмування необхідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.

Алгоритм графічного методу розв'язування задачі лінійного програмування складається з таких кроків:

1.Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі знаків нерівностей на знаки рівностей.

2.Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3.Знаходимо багатокутник розв'язків задачі лінійного програмування.

4.Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5.Будуємо пряму , перпендикулярну до вектора .

6.Рухаючи пряму в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набирає екстремального значення.

7.Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.

Отже, у випадку, коли у програмі (плані) містяться тільки дві змінні, задачу лінійного програмування зручно розв’язувати графічним способом.

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

 Зауваження. Із змінними працюємо аналогічно як із «звичними» .

Розв’язання.

Побудувавши