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

6.1. Основні теоретичні положення

Нехай задана задача лінійного програмування в канонічній формі [0, 0]

c^T x  max; (6.1)

A x = b; (6.2)

x0. (6.3)

Задача, двоїста задачі (6.1) — (6.3), має вигляд

Задачу (6.1) — (6.3) будемо надалі називати прямою задачею.

Критерій оптимальності задачі (6.1) — (6.3) має вигляд

,

де d_N — вектор відносних оцінок небазисних змінних; — вектор оцінок обмежень.

За аналогією з вектором d_N введемо вектор d_B: Визначаємо вектор відносних оцінок змінних таким чином:

;

.

Критерій оптимальності задачі (6.1) — (6.3) можна записати так:

;

;

. (6.4)

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

Двоїстий симплекс-метод – це симплекс-метод, який пристосований до двоїстої задачі, але працює з перетворюваною прямою задачею.

Нехай пряму перетворену задачу записано в такому вигляді:

(6.5)

при обмеженнях

. (6.6)

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

6.2. Схема двоїстого симплекс-методу для задачі максимізації цільової функції

Розглянемо теоретичне обґрунтування методу [0].

Крок 1. Вибір змінної, що виводиться з множини базисних (умови допустимості)

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

.

Якщо всі базисні змінні  0 (тобто такого q не існує), то СТОП, одержали допустимий і оптимальний розв’язок. У протилежному випадку стовпчик, що відповідає змінній , повинен бути виведений з базису.

Крок 2. Вибір змінної, що вводиться в множину базисних (умова оптимальності)

Якщо j-й небазисний стовпчик замінює q-й базисний, тоді після застосування перетворень Гаусса відносна оцінка q-го стовпчика в новому ДБР буде дорівнювати . Для того, щоб компоненти вектора d_N, як і раніше, були невід’ємні (виконувалась умова оптимальності), знаменник повинен бути від’ємним.

Визначимо коефіцієнт  за формулою

(6.7)

і нехай мінімум досягається при j = p.

Якщо у q-му рядку немає жодного дляj, які відповідають небазисним змінним (ознака відсутності допустимих розв’язків), то СТОП, пряма задача не має допустимих розв’язків.

Отже, у множину базисних будемо вводити змінну :

;

.

Якщо взяти більше значення параметра  , ніж те, яке дає (6.7), наприклад значення, яке відповідає j = r , і якщо змінну ввести в базис, то в новому розв’язку одержимо

, тому що

і умови оптимальності ДБР прямої задачі не будуть виконуватися.

Крок 3. Перехід до нового ДБР

За допомогою елементарних перетворень Гауcса виконується операція заміщення на. Перехід докроку 1.

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

Коефіцієнт  визначають за формулою

(6.7а)

(як і раніше розглядаються тільки відношення з від’ємним знаменником).

Ознака відсутності допустимих розв’язків така сама: у рядку, що відповідає вивідній змінній, немає жодного дляj, які відповідають небазисним змінним.

З урахуванням (6.7) і (6.7а) можна записати єдине (для задач максимізації та мінімізації) правило вибору ведучого стовпчика:

.

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

У табл. 6.1 наведено порівняльну характеристику прямого і двоїстого симплекс-методів.

Таблиця 6.1

	Прямий симплекс-метод	Двоїстий симплекс-метод
1	2	3
Проміжний розв’язок	Задача на мінімізацію  хj  0 і  j dj > 0. Проміжні розв’язки є допустимими, але неоптимальними за критерієм оптимальності	Задача на максимізацію  dj  0, але jxj < 0. Проміжні розв’язки є оптимальними за критерієм оптимальності, але не є допустимими
Проміжний розв’язок	Задача на максимізацію  хj  0 і jdj < 0. Проміжні розв’язки є допустимими, але не є оптимальними.	Задача на мінімізацію  dj  0, але jxj < 0. Розв’язки є оптимальними за критерієм оптимальності, але не є допустимими.
Опти-мальний розв’язок	Задача на мінімізацію
	 xj  0  dj  0	 xj  0  dj  0

Продовження таблиці 6.1

1	2	3
	Задача на максимізацію
	 xj  0  dj  0		 xj  0  dj  0
Етапи методу	1. Умова оптимальності. Вибір змінної, що вводиться у базис: вводимо ту змінну xjу якійdj > 0 (min); dj < 0 (max). 2. Умова допустимості. Вибір змінної, що виводиться з базису: вибираємо змінну таким чином, щоб зберегти допустимість розв’язку, що отримується		1. Умова допустимості. Вибір змінної, що виводиться з базису: виводимо ту змінну xj, для якої виконується: xj < 0. 2. Умова оптимальності. Вибір змінної, що вводиться в базис: вибираємо змінну таким чином, щоб зберегти оптимальність розв’язку