Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

3.6. Двоїстий симплексний метод

Як відомо з попередніх параграфів даного розділу, кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна перейти до двоїстої і, використовуючи її оптимальний план, визначити оптимальний план початкової.

Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок (), а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою.

Нехай необхідно розв’язати задачу лінійного програмування, подану в канонічному виді:

, (3.60)

, (3.61)

. (3.62)

Тоді двоїстою до неї буде така задача:

(3.63)

. (3.64)

За алгоритмом двоїстого симплексного методу як перший опорний план вибирається деякий допустимий розв’язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків.

Допустимо, що початковий базис складається з m векторів , причому хоча б одна з компонент вектора від’ємна. Нехай , однак справджується критерій оптимальності плану, тобто всі оцінки векторів (). На підставі першої теореми двоїстості план двоїстої задачі відшукуємо у вигляді: . Цей план не є оптимальним для прямої задачі, оскільки він не задовольняє умову невід’ємності змінних (3.62) і не є оптимальним для двоїстої задачі, бо всі оцінки векторів оптимального плану двоїстої задачі мають бути невід’ємними.

Отже, вектор, що відповідає компоненті , потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від’ємній оцінці, включити до базису двоїстої.

У прямому симплекс-методі спочатку виявляють змінну, яку слід ввести у базис, а в двоїстому симплекс-методі навпаки — спочатку визначають змінну, яку виключають з базису, а потім змінну, яку вводять у базис.

У літературі [19, 22, 28, 31] зустрічаються різні варіанти двоїстого симплексного методу, які не мають принципових відмінностей. Розглянемо такий алгоритм двоїстого симплексного методу:

1. Необхідно звести всі обмеження задачі до виду « », ввести додаткові невід’ємні змінні, визначити початковий базис та перший опорний план .

2. Якщо всі оцінки векторів і компоненти вектора-стовпчика «План» для всіх , то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту і відповідну змінну виключити з базису.

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

(),

що дає змогу вибрати вектор, який буде включено в базис.

4. Виконавши крок методу повних виключень Жордана—Гаусса, переходять до наступної симплексної таблиці (Переходять до пункту 2).

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

Детальне доведення всіх кроків алгоритму двоїстого симплексного методу розглянуто в [10].

Знайти мінімальне значення функції

за умов:

.

Розв’язання: Помножимо другу нерівність на (– 1) і введемо додаткові змінні.

.

Початковий базис — вектори А4 та А5. Псевдоплан .

Складемо початкову симплексну таблицю.

Оскільки , то з базису необхідно вивести вектор А5 і відповідну змінну .

Для визначення вектора, що вводиться в базис, розрахуємо значення . В другому рядку містяться два від’ємних коефіцієнти , які відповідають векторам А1 та А3. Визначимо, який з цих векторів необхідно вводити в базис.

.

Отже, , значить, у базис слід ввести вектор А1. Розв’язувальним елементом буде а21 (–1).

У результаті реалізації методу повних виключень Жордана—Гаусса за два кроки отримаємо оптимальний план.

Згідно з останньою симплексною таблицею маємо такий оптимальний план початкової задачі:

,

та оптимальний план двоїстої задачі:

, .

Для розрахунку оптимального плану двоїстої задачі необхідно було значення оцінок домножити на (– 1), оскільки ці спряжені задачі є симетричними.

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

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