Відмінності між версіями «Двоїстий симплексний метод»

Версія за 10:36, 5 травня 2012

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

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

Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок Неможливо розібрати вираз (невідома помилка): \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].