4.2. Розв’язання злп.
4.2.1. Побудова допустимої області ЗЛП.
Пригадаємо ( див. попередній параграф), що множиною розв’язків лінійної нерівності є півплощина . Якщо ми розглядаємо систему з кількох нерівностей, то множиною розв’язків цієї системи є перетин відповідних півплощин, тобто це є така множина точок, які потрапляють в кожну з півплощин.
Почнемо розгляд ЗЛП з побудови зображення на координатній площині допустимої області (множини) ЗЛП — множини розв’язків системи лінійних нерівностей, у якій об’єднано непрямі і прямі умови ЗЛП.
Зображення множини розв’язків СЛН будуємо за схемою:
замінюємо в першій нерівності знак нерівності на знак = і отримуємо лінійне рівняння, яке визначає пряму лінію на координатній площині;
креслимо цю пряму лінію (вона є границею півплощини, яка є множиною розв’язків першої нерівності);
вибираємо одну, яку завгодно, точку з однієї (якої-небудь) з півплощин, на які розбила площину накреслена пряма; підставляємо координати вибраної точки у першу нерівність; якщо нерівність справджується, то множиною розв’язків нерівності буде та півплощина, де лежить вибрана точка, якщо ні, - інша (“протилежна”) півплощина (часто буває зручно за “пробну” точку брати точку
-
початок координат);описані дії виконуємо з кожною із нерівностей;
шукана допустима множина ЗЛП є перетином всіх (у нашому випадку чотирьох) півплощин; геометрично - це є многокутник.
|
|
|
|
|
|
Бачимо, що
геометричне місце точок, які задовольняють
кожну з нерівностей, утворюють чотирикутник
.
В ньому нам відомі координати всіх
вершин, крім точки
.
Координати точки знаходимо за такою схемою:
визначаємо з малюнка, на перетині граничних прямих яких нерівностей знаходиться ця вершина;
утворюємо систему двох рівнянь з двома невідомими, беручи рівняння двох прямих, визначених на попередньому кроці;
розв’язуємо утворену систему лінійних рівнянь; знайдений розв’язок - це і є шукані координати розглядуваної вершини.
Обчислюємо за наведеною схемою координати вершини .
10
10
: 3
(-2)
Допустима множина побудована і координати всіх вершин відповідного многокутника обчислені.
4.2.2. Пошук оптимального допустимого розв’язку.
Почнемо пошук оптимального розв’язку ЗЛП. Для цього залучимо до розгляду цільову функцію:
.
Розглядувана ЗЛП полягає у знаходженні точки з допустимої множини, у якій цільова функція набуває найбільше значення серед усіх значень в усіх допустимих розв’язках, тобто, серед значень в усіх точках допустимої множини.
Нехай r - це деяке дійсне число, яке ми будемо розглядати як значення (у якійсь точці) цільової функції. З огляду на таку інтерпретацію ми будемо називати число r рівнем цільової функції (отже, нам треба знайти точку допустимої множини з найбільшим рівнем цільової функції).
Нехай r
- це деякий
рівень. Множина точок
координатної площини з даним рівнем r
цільової функції, тобто, для яких
,
зветься лінією рівня цільової функції. У нашому конкретному випадку це буде пряма лінія з рівнянням
.
Зобразимо на
спільному малюнку допустиму множину і
декілька ліній рівня цільової функції,
а саме
,
,
:
Всі лінії рівня паралельні, вони мають спільну нормаль, тобто спільний нормальний вектор. Для “конкретизації” цього вектора можна скористатися коефіцієнтами біля невідомих у якому-небудь з рівнянь:
Один з напрямків перпендикуляра, і як раз той, що визначається вибраним нами вектором, перпендикулярним (чому ?), до ліній рівня є напрямком зростання, інший - напрямком спадання цільової функції.
Якщо якась лінія рівня перетинає допустиму множину ЗЛП, це означає, що у допустимій множині є точки, у яких цільова функція набуває відповідного значення.
Отже, для того, щоб знайти оптимальний розв’язок ЗЛП, треба лінію рівня цільової функції пересувати паралельно у напрямку зростання доти, поки вона ще перетинає допустиму множину.
Остання точка перетину лінії рівня з допустимою областю ЗЛП („точка прощання”) є оптимальним розв’язком ЗЛП:
Отже оптимальний план виробництва пилососів і вентиляторів: 20 пилососів і 120 вентиляторів.
4.3. Загальні властивості оптимального розв’язку ЗЛП.
4.3.1. Основна властивість оптимального розв’язку ЗЛП.
Геометричні міркування дають змогу сформулювати загальне положення, що визначає місцезнаходження оптимальної точки ЗЛП у допустимій множині.
Допустима множина ЗЛП, як перетин півплощин, є опуклим многокутником. Отже, якщо взяти яку-небудь внутрішню (тобто яка не лежить на границі) точку допустимої множини і якщо провести через цю точку лінію рівня, то цю лінію рівня можна, хоч трохи, зрушити як у напрямку зростання, так і в напрямку спадання. І вона все ще буде перетинати допустиму множину. Таким чином, внутрішня точка допустимої множини ЗЛП не може бути оптимальним розв’язком ЗЛП.
Звідси висновок: оптимальний розв’язок ЗЛП, якщо він існує, є вершиною допустимої множини ЗЛП.
4.3.2. Знаходження оптимального розв’язку ЗЛП методом перебирання вершин допустимої області.
Інколи, через неточності малюнка, важко визначити, яка саме вершина допустимої області є точкою екстремуму цільової функції ЗЛП. В таких випадках треба обчислити значення цільової функції в декількох “підозрілих” точках:
Точка максимуму — .
4.3.3. Класифікація можливостей щодо “вмісту” множини оптимальних розв’язків ЗЛП.
У загальному випадку можна виділити три якісно різних випадки щодо “вмісту” множини оптимальних розв’язків ЗЛП. Ці випадки однакові як для задачі мінімізації, так і для задачі максимізації. Обмежимось розглядом задачі максимізації.
1) Множина оптимальних розв’язків порожня (ЗЛП не має оптимального розв’язку).
1а) Допустима множина ЗЛП порожня (система обмежень є несумісною).
1б) Допустима множина необмежена у напрямку зростання цільової функції.
Множина оптимальних розв’язків містить один-єдиний елемент (точку). В такому випадку оптимальний розв’язок ЗЛП неодмінно є вершиною допустимої області. Прикладом такої ситуації може служити розглянута задача.
Множина оптимальних розв’язків нескінчена; це буває в тому випадку, коли лінія рівня паралельна якійсь стороні допустимої множини. Тоді множина оптимальних розв’язків складається із всіх точок цієї сторони, причому ця сторона може бути як відрізком, так і променем:
3а)
3б)
Лінія рівня паралельна стороні допустимої множини.