ТЕМА 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

при обмеженнях