ТЕМА 3. АЛГЕБРАЇЧНИЙ МЕТОД РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
3.1. Симплекс-метод як універсальний метод розв’язання ЗЛП.
Якщо лінійна оптимізаційна задача містить три змінні, то графічний метод розв’язання стає неефективним, а при більшому числі змінних – взагалі неможливим. У цьому випадку необхідно застосувати алгебраїчний апарат. Універсальним алгебраїчним методом розв’язання задач лінійного програмування є так званий симплексний метод, запропонований у 1943 році американським вченим Дж. Данцигом.
Процес розв’язання задачі лінійного програмування симплекс-методом носить ітераційний характер: однотипні обчислювальні процедури в певній послідовності повторюються доти, поки не буде одержаний оптимальний розв’язок. Проце¬дури, що реалізуються в рамках симплекс-методу, потребують застосування обчислювальних машин.
3.2. Стандартна форма лінійних оптимізаційних моделей
У загальному випадку права та ліва частини обмежень лінійної моделі можуть бути пов’язані знаками £, ³ або =. Крім того, змінні задачі можуть бути невід’ємними або не мати обмеження на знак. Для побудови загального методу розв’язання задач ЛП відповідні моделі мають бути представлені в деякій формі, яку назвемо стандартною формою лінійних оптимізаційних моделей. Стандартна форма лінійної моделі відповідає наступним вимогам:
1) всі обмеження записані у вигляді рівнянь з невід’ємною правою частиною;
2) значення всіх змінних моделі є невід’ємними;
3) цільова функція підлягає максимізації або мінімізації.
Покажемо, яким чином лінійну модель довільного виду можна при¬вести до стандартної форми.
Обмеження:
1. Вихідне обмеження - нерівність із знаком £ (або ³) можна подати у вигляді рівняння, додаючи до лівої частини обмеження невід’ємну залишкову змінну (або віднімаючи надлишкову змінну). Наприклад, до лівої частини вихідного обмеження
x1+2x2£ 6
додається залишкова змінна x3 ³ 0, в результаті чого вихідна нерівність обертається на рівняння
x1+2x2+ x3=6.
Якщо вихідне обмеження визначає витрати деякого ресурсу, то змінну x3 слід інтерпретувати як залишок або невикористану частину даного ресурсу. Розглянемо обмеження іншого типу:
3х1+2х2 ³ 5.
Оскільки ліва частина цього обмеження не може бути меншою від правої, для обернення вихідної нерівності на рівняння віднімемо від його лівої частини надлишкову змінну х3³0. В результаті отримаємо: 3х1+2х2-х3=5.
2. Праву частину обмеження завжди можна зробити невід’ємною, помноживши обидві його частини на -1.
Наприклад, рівняння 2х1-х2= -5 є еквівалентним рівнянню 2х1+x2=5.
Знак нерівності замінюється на протилежний при м¬ноженні обох його частин на -1. Наприклад, можна замість x >-4 записати -x<4.
3. Будь яку змінну y, що не має обмеження на знак, можна подати у вигляді різниці двох невід’ємних змінних:
y=y¢-y¢¢ , де y'³0, y¢¢ ³ 0.
Таку підстановку слід зробити в усіх обмеженнях, які містять вихідну змінну y, а також у рівнянні цільової функції. Після цього знаходять розв’язок задачі ЛП, в якому фігурують змінні y¢ та у", а потім за допомогою зворотної підстановки визначають величину y. Наприклад, якщо змінні y1, y2, y3 деякої задачі ЛП не мають обмежень на знак, а в оптимальному розв’язку y¢1 =0, у"1=6; y¢2=10, у"2=0; y'3=y"3=0, то відповідні значення вихідних змінних складатимуть: y1=-6, y2=10, y3=0.
Важливою особливістю змінних y¢, y¢¢ є те, що завжди, при будь-якому допустимому розв’язку, одна з цих змінних приймає додатне значення, а друга - нульове. Тобто, якщо y¢>0, то , y¢¢ =0 і навпаки, якщо y¢¢>0, то y¢=0 . Це дозволяє розглядати y¢ як залишкову змінну, а у"- як надлишкову. Вказана закономірність широко застосовується в цільовому програмуванні.
Цільова функція Цільова функція лінійної оптимізаційної моделі в стандартній формі може підлягати як максимізації, так і мінімізації. В деяких випадках виявляється доцільним замінити вихідну цільову функцію. Максимізація деякої функції є еквівалентною мінімізації тієї ж функції, взятої з протилежним знаком. Наприклад, мінімізація функції:
z=5x1+2x2+3x3
є еквівалентною мінімізації функції (-z) = - 5x1 - 2x2 - 3x3 .
Еквівалентність означає, що при одній і тій самій сукупності обмежень оптимальні значення змінних x1 , x2 , x3 в обох випадках будуть однакові. Відмінність полягає в тому, що при однакових числових значеннях цільових функцій їх знаки будуть протилежними.
Приклад 3.1. Потрібно подати у стандартній формі наступну лінійну модель:
мінімізувати z=2x1+3x2 при обмеженнях
Необхідно виконати наступні перетворення.
1. Помножити друге обмеження на -1 и відняти від його лівої частини надлишкову змінну x3³0.
2. Додати залишкову змінну x4³0 до лівої частини третього обмеження.
3. В цільовій функції та в усіх обмеженнях виконати підстановку:
x1= x1'- x1¢¢ , де x1¢ ³0, x1¢¢ ³ 0.
Названі операції дозволяють звести вихідну модель до стандартної форми:
мінімізувати z= 2x1¢- 2x1¢¢+З x2
при обмеженнях
25 26 27 28 29 30 Наверх ↑