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

Поточна версія на 10:48, 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].