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

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

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

П р и к л а д 1 Мінімізувати за таких обмежень:

                                                 

                                                 

                                                 

                                                 

У стандартній  формі задачу формулюють так: знайти такі , що

                                        

                                        

                                         

і мінімізувати .

Якщо помножити  ці обмеження на мінус 1 (для отримання  конкретного вигляду базису), матимемо:

                                        

                                        

                                        

                                           

                                          

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

Початкова симплекс-таблиця, що відповідає оптимальному, але неприпустимому розв’язку, має такий вигляд, як табл. 1

Т а б л и ц я 1

Базисна змінна						Розв’язок
-Z	2	1	0	0	0	0
	-3	-1	1	0	0	-3
	-4	-3	0	1	0	-6
	1	2	0	0	1	3

 

Умова припустимості. За змінну, що виключається, вибирають найбільшу за абсолютною виличиною від’ємну базисну змінну (за наявності альтернатив вибір довільний). Якщо всі базисні змінні навід’ємні, обчислення закінчується, оскильки отриманий розв’язок припустимий і оптимальний.

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

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

У таблиці  змінною, що виключається, є , оскільки вона має найбільше за абсолютною величиною від’ємне значення. Відношення, що обчислюються для визначення нової базисної змінної, наведено в табл. 2

Т а б л и ц я 2

Змінна
z-рівняння -рівняння	2 -4	1 -3	0 0	0 1	0 0
Відношення	1/2	1/3	-	-	-

 

За змінну, що виключається, вибирають , оскільки цій змінній відповідає найменше за моделуем відношення, яке доврівню 1/3.

Наступні  перетворення рядків зводять до новох симплекс-таблиці (табл. 3).

Т а б л и ц я 3

Базисна змінна						Розв’язок
-z	2/3	0	0	1/3	0	-2
	-5/3	0	1	-1/3	0	-1
	4/3	1	0	-1/3	0	2
	-5/3	0	0	2/3	1	-1

 

Новий розв’язок також оптимальний, але все ще неприпустимий (). Потрібно продовжити перетворення симплекс-таблиці до отриання оптимального і припустимого розв’язку.

Застосування  двоїстого симплекс-методу особливо ефективне для аналізу моделей  на чутливість, зокрема тоді, коли після  отримання оптимального розв’язку в умову задачі вводять нове обмеження. Наприклад, для економічних задач цікаво те, як впливає на оптимальний розв’язок збыльшення чи зменшення попиту і (або) зміна запасів вхідних продуктів. Можна також визначити вплив зміни ринкових цін на оптимальний розв’язок.

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