Спряжені (двоїсті) задачі лінійного програмування. Основні властивості

Розглянемо основну ЗЛП, записану (без зменшення загальності міркувань) у вигляді:

(8.1)

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

(8.2)

Розглянемо, також, задачу:

(8.3)

(8.4)

Задачу (8.3), (8.4) одержана із задачі (8.1), (8.2) згідно з такими правилами:

1) вільні члени обмежень (8.2) є коефіцієнтами нового критерію , а коефіцієнти в критерії – вільними членами в обмеженнях (8.4);

2) матрицею коефіцієнтів нових обмежень є матриця , що одержана транспонуванням матриці ;

3) у нових обмеженнях (8.4) знаки нерівностей протилежні знакам нерівностей (8.2);

4) максимізація критерію змінюється на мінімізацію критерія

Задача (8.3), (8.4) називається спряженою (двоїстою) до задачі
(8.1), (8.2).

Не важко помітити, що задачу (8.1), (8.2) можна розглядати як спряжену відносно своєї спряженої задачі (8.3), (8.4) або

Властивість 1. Якщо одна зі спряжених задач (8.1), (8.2) чи (8.3), (8.4) має розв’язок, то й інша має розв’язок, причому виконується рівність:

Якщо ж в одній із цих задач лінійна форма необмежена, то спряжена задача має порожню область обмежень.

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

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

Інакше кажучи, оптимальні розв’язки пари спряжених задач задовольняють умови: