задач лінійного програмування
Нехай дана задача:
=С1х1 + С2Х2 ® max
а11Х1 + а12Х2? а1
а21Х1 + а22Х2? а2 (7.5)
...
аm1Х1 + аm2Х2? аm.
Введемо на площині декартову прямокутну систему координат і зіставимо кожній парі чисел (Х1, Х2) точку площини з координатами Х1 і Х2. З'ясуємо, насамперед, що являтиме собою безліч точок, відповідних допустимим рішенням даної задачі.
Розглянемо спочатку одне лінійне нерівність з двома змінними:
а11Х1 + а12Х2? а2.
Воно, як відомо, визначає на площині одну з двох частин (напівплощин), на які пряма а11Х1 + а12Х2=а1, розбиває площину. При цьому відповідна напівплощина включає і граничну пряму а11Х1 + а12Х2=а1 (замкнута напівплощина). Щоб визначити, яку саме з двох замкнутих напівплощин визначає таку нерівність, досить підставити в нього координати однієї якийсьнебудь точки, що не лежить на граничній прямій. Якщо нерівність задовольняється, то шукана напівплощина та, в якій лежить взята крапка, а якщо не удовлетворяется- то протилежна їй.
Нехай допустима область задачі лінійного програмування (7.1) виявилася непорожній (багатокутник MNP0 на рис. 7.1).
Як геометрично знайти оптимальні точки? Оптимальними є ті точки допустимої області, координати яких доставляють цільової функції найбільше значення.
Визначаємо градієнт функції ® grad f:
® grad f={C1, C2}.
x2
M
С1х1 + С2Х2=c
Af
x1 P
Рис. 7.1
Лінія f (x, y)=c при будь-якому значенні постійної c являє собою пряму, перпендикулярну вектору grad f. Вважаючи c параметром, отримуємо сімейство паралельних прямих (званих лініями постійного значення, або лініями рівня функції). Нас цікавлять, відповідно до нашої завданням, ті точки допустимої облас, які належати лінії рівня з найбільшим значенням c в порівнянні з його значеннями для всіх інших линів рівня, що перетинаються з допустимою областю. Збільшення c відповідає переміщенню лінії рівня уздовж ® grad f. Отже, щоб знайти оптимальні точки допустимої безлічі завдання на максимум, потрібно переміщати лінії рівня в напрямку вектора ® grad f, починаючи з якого - небудь фіксованого положення, при якому вона перетинається з допустимою областю (точка А на рис. 7.1) до тих пір, поки вона не перестане перетинатися з нею. У точці області допустимих значень, в якій функція f досягає максимуму, лінія рівня покидає D. Тому, якщо ми знайдемо проекцію D на напрям ® grad f, то точка максимуму буде проектуватися на кінець отриманого відрізка. Перетин допустимої області з лінією рівня в тому її становищі, коли подальше переміщення дає пусте перетин, і буде безліччю оптимальних точок задачі лінійного програмування (на рис. 7.1 це єдина точка N).
Аналогічно, при зменшенні c відповідна лінія рівня покине D в точці мінімуму f, і ця точка проектується на початок відрізка-проекції D на напрям grad f.
В якості прикладу розглянемо задачу про розподіл ресурсів.
Приклад. Мається 300 кг металу, 100 м2 скла і 160 - людино-годин робочого часу; з них виготовляють вироби двох найменувань А і Б; вартість одного виробу А дорівнює 10 $, для його виготовлення потрібно 4 кг металу, 2 м2 скла і 2 людино-години робочого часу; вартість одного виробу Б дорівнює 12 $, для його виготовлення потрібно 5 кг металу, 1 м2 скла і 3 людино-години робочого часу; потрібно спланувати виробництво так, щоб призвести вироби з максимальною вартістю.
Рішення. Припустимо, що підприємство випускає x1 одиниць продукції виду A і x2 одиниць продукції виду B. Для цього буде потрібно 4 * x1 + 5 * x2 одиниць металу. Так як в наявності є всього 300 одиниць металу, то повинна виконуватись нерівність
* x1 + 5 * x2? 300
Аналогічні міркування, проведені для решти видів сировини і робочого часу, дозволяють записати наступні нерівності
* x1 + x2? 100
* x1 + 3 * x2? 160
За цих умов дохід Z, одержуваний підприємством, складе
=f (x1, x2)=10 * x1 + 12 * x2 ® max (7.6)
Таким чином, математично завдання можна сформулювати так:
Знайти max Z=10 * x1 + 12 * x2
при обмеженнях
* x1 + 5 * x2? 300
* x1 + x2? 100 (7.7)...
