Двоїстий симплекс-метод

11.4. Подвійний симплекс-МЕТОД

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

Перехід до двоїстої задачі не обов'язковий, так як якщо розглянути першу симплексну таблицю з одиничним додатковим базисом, то легко помітити, що в стовпцях записана вихідна завдання, а в рядках -двойственная.

Як було показано, при вирішенні прямої задачі на будь-який ітерації різниця. тобто величина коефіцієнт при змінної. дорівнює різниці між правою і лівою частинами відповідного обмеження двоїстої задачі. Якщо при вирішенні прямої задачі з максімізіруемой цільовою функцією ітерація не приводить до оптимального рішення, то принаймні для однієї змінної і тільки в оптимумі для всіх різниця.

Розглядаючи цю умову з урахуванням подвійності, можна записати

Таким чином, якщо. то. Це означає, що, коли рішення прямої задачі неоптимальний, рішення двоїстої завдання неприпустиме. З іншого боку при. Звідси випливає, що оптимального рішення прямої задачі відповідає допустиме рішення двоїстої завдання.

Це дозволило розробити новий метод розв'язання задач лінійного програмування, при використанні якого спочатку виходить неприпустиме, але «краще, ніж оптимальне» рішення (в звичайному симплекс-методі спочатку знаходиться допустиме. Але неоптимальний рішення). Новий метод, що отримав назву двоїстого симплекс-методу. забезпечує виконання умови оптимальності рішення і систематичне «наближення» його до області допустимих рішень. Коли отримане рішення виявляється допустимим, ітераційний процес обчислень закінчується, так як це рішення є і оптимальним.

Двоїстий симплекс-метод дозволяє вирішувати задачі лінійного програмування, системи обмежень яких при позитивному базисі містять вільні члени будь-якого знака. Цей метод дозволяє зменшити кількість перетворень системи обмежень, а також розміру симплексной таблиці. Розглянемо застосування двоїстого симплекс-методу на прикладі.

Приклад. Знайти мінімум функції

Перейдемо до канонічної формі:

Початкове базисне рішення оптимальне, але не допустиме.

Як і звичайний симплексний метод, розглянутий метод вирішення заснований на використанні умов допустимості й оптимальності.

Умова допустимості. Як исключаемой змінної вибирається найбільша за абсолютною величиною негативна базисна змінна (при наявності альтернатив вибір робиться довільно). Якщо все базисні змінні невід'ємні, процес обчислень закінчується, так як отримане рішення допустиме і оптимальне.

Условіеоптімальності. Включається в базис змінна вибирається з числа небазисних змінних наступним чином. Обчислюються відносини коефіцієнтів лівої частини -уравненія до відповідних коефіцієнтів рівняння, асоційованого з исключаемой змінної. Відносини з позитивним або нульовим значенням знаменника не враховуються. У задачі мінімізації введеної перемінної має відповідати найменше із зазначених відносин, а в задачі максимізації - відношення, найменше за абсолютною величиною (при наявності альтернатив вибір робиться довільно). Якщо знаменники всіх відносин дорівнюють нулю або позитивні, завдання не має допустимих рішень.

Після вибору включається в базис і исключаемой змінних для отримання наступного рішення здійснюється звичайна операція перетворення рядків симплекс-таблиці.

У розглянутому прикладі исключаемой змінної є. Відносини, обчислені для визначення нової базисної змінної, наведені в наступній таблиці:

Як включається змінної вибирається x2. Подальше перетворення рядків призводить до нової симплекс-таблиці:

Нове рішення також оптимальне, але все ще неприпустиме. В якості нової исключаемой змінної виберемо (довільно) x3. Визначимо включається змінну.

Введеної в базис змінної є x1 і в результаті отримаємо наступну симплекс-таблицю:

Отримане рішення x1 =. x2 = є оптимальним і допустимим.

Двоїстий симплекс-метод зручний тим, що його можна застосовувати в тому випадку, коли вирішується не одна, а кілька завдань лінійного програмування з зростаючою кількістю додаткових обмежень.