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

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

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) розглядаємо як вираз допустимості вектора двоїстих змінних p. Таким чином у симплекс-методі, підтримуючи допустимість прямого розв’язку, можна прагнути до допустимості двоїстого розв’язку. Такий алгоритм називається прямим. Так само можна розпочати з допустимого двоїстого розв’язку і прагнути допустимості прямого. Такий алгоритм називають двоїстим симплекс - методом.

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

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

(6.5)

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

. (6.6)

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