Двоїстий симплексний метод
Двоїстий симплексний метод
Як відомо кожній задачі лінійного програмування можна пос-тавити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна пе-рейти до двоїстої і, використовуючи її оптимальний план, визна-чити оптимальний план початкової.
Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j}
Неможливо розібрати вираз (невідома помилка): (j=\overline {1,n})
а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою.
Нехай необхідно розв’язати лінійного програмування, подану в канонічному виді:
Неможливо розібрати вираз (невідома помилка): min \,\,F=CX
(1)
Неможливо розібрати вираз (невідома помилка): AX=B
(2)
Неможливо розібрати вираз (невідома помилка): X\ge 0
(3)
Тоді двоїстою до неї буде така задача:
Неможливо розібрати вираз (невідома помилка): max \,\,Z=BY
(4)
Неможливо розібрати вираз (невідома помилка): YA\le C
(5)
За алгоритмом двоїстого симплексного методу як перший опор¬ний план вибирається деякий допустимий розв’язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків.
Допустимо, що початковий базис складається з m векторів Неможливо розібрати вираз (невідома помилка): D=(A_{1} ,A_{2} ,...A_{l} ,...,A_{m} )
, причому хоча б одна з компонент вектора Неможливо розібрати вираз (невідома помилка): X=D^{-1}B=(x_{1} ,x_{2} ,...,x_{l} ,...,x_{n} )
від’ємна. Нехай Неможливо розібрати вираз (невідома помилка): x_{l} <0
, однак справджується критерій оптимальності плану, тобто всі оцінки векторів Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j} \ge 0
Неможливо розібрати вираз (невідома помилка): (j=\overline {1,n})
Отже, вектор, що відповідає компоненті Неможливо розібрати вираз (невідома помилка): x_{l} <0 , потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від’ємній оцінці, включити до базису двоїстої.
У прямому симплекс-методі спочатку виявляють змінну, яку слід ввести у базис, а в двоїстому симплекс-методі навпаки — спочатку визначають змінну, яку виключають з базису, а потім змінну, яку вводять у базис.
У літературі [19, 22, 28, 31] зустрічаються різні варіанти двоїстого симплексного методу, які не мають принципових відмінностей. Розглянемо такий алгоритм двоїстого симплексного методу:
1. Необхідно звести всі обмеження задачі до виду «Неможливо розібрати вираз (невідома помилка): .\le », ввести додаткові невід’ємні змінні, визначити початковий базис та пер-ший опорний план Неможливо розібрати вираз (невідома помилка): X=(b_{1} ,b_{2} ,...,b_{m} )
2. Якщо всі оцінки векторів Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j} \le 0
і компоненти вектора-стовпчика «План» Неможливо розібрати вираз (невідома помилка): (b_{1} ,b_{2} ,...,b_{m} )\ge 0
для всіх Неможливо розібрати вираз (невідома помилка): i=\overline{1,m}
то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту Неможливо розібрати вираз (невідома помилка): b_{l} <0
і відповідну змінну Неможливо розібрати вираз (невідома помилка): x_{l}
виключити з базису.
3. Виконавши крок методу повних виключень Жордана—Гаусса, переходять до наступної симплексної таблиці (Переходять до пункту 2). Зазначимо, що для задачі знаходження максимального зна-чення цільової функції за наведеним алгоритмом необхідно пе-рейти до цільової функції Неможливо розібрати вираз (невідома помилка): {F}'=-F , або дещо змінити сам алгоритм. Детальне доведення всіх кроків алгоритму двоїстого симплек-с¬ного методу розглянуто в [10].
