Розв’язання ЗЛП

Зображення множини розв’язків СЛН будуємо за схемою:

· замінюємо в першій нерівності знак нерівності на знак = і отримуємо лінійне рівняння, яке визначає пряму лінію на координатній площині;

· креслимо цю пряму лінію (вона є границею півплощини, яка є множиною розв’язків першої нерівності);

· вибираємо одну, яку завгодно, точку з однієї (якої-небудь) з півплощин, на які розбила площину накреслена пряма; підставляємо координати вибраної точки у першу нерівність; якщо нерівність справджується, то множиною розв’язків нерівності буде та півплощина, де лежить вибрана точка, якщо ні, - інша (“протилежна”) півплощина (часто буває зручно за “пробну” точку брати точку - початок координат);

· описані дії виконуємо з кожною із нерівностей;

· шукана допустима множина ЗЛП є перетином всіх (у нашому випадку чотирьох) півплощин; геометрично - це є многокутник.

Бачимо, що геометричне місце точок, які задовольняють кожну з нерівностей, утворюють чотирикутник . В ньому нам відомі координати всіх вершин, крім точки .

Координати точки знаходимо за такою схемою:

· визначаємо з малюнка, на перетині граничних прямих яких нерівностей знаходиться ця вершина;

· утворюємо систему двох рівнянь з двома невідомими, беручи рівняння двох прямих, визначених на попередньому кроці;

· розв’язуємо утворену систему лінійних рівнянь; знайдений розв’язок - це і є шукані координати розглядуваної вершини.

Обчислюємо за наведеною схемою координати вершини .

* 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б) Допустима множина необмежена у напрямку зростання цільової функції.

2) Множина оптимальних розв’язків містить один-єдиний елемент (точку). В такому випадку оптимальний розв’язок ЗЛП неодмінно є вершиною допустимої області. Прикладом такої ситуації може служити розглянута задача.

3) Множина оптимальних розв’язків нескінчена; це буває в тому випадку, коли лінія рівня паралельна якійсь стороні допустимої множини. Тоді множина оптимальних розв’язків складається із всіх точок цієї сторони, причому ця сторона може бути як відрізком, так і променем:

3а)

3б)

Лінія рівня паралельна стороні допустимої множини.