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

Версія за 17:44, 4 травня 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. Якщо в l-му рядку, що відповідає змінній Неможливо розібрати вираз (невідома помилка): x_{l} , не міститься жодного Неможливо розібрати вираз (невідома помилка): a_{lj} <0 , то цільова функція двоїстої задачі необмежена на багатограннику розв’язків, а початкова задача розв’язку не має. Інакше існують деякі Неможливо розібрати вираз (невідома помилка): a_{lj} <0

і тоді для відповідних стовпчиків визначають аналогічно прямому симплекс-методу оцінки Неможливо розібрати вираз (невідома помилка): \theta 

Неможливо розібрати вираз (невідома помилка): \theta_{j} ={\min }\limits_{j} \left| {\frac{\Delta_{j} }{a_{lj} }}