Двойственность в линейном программировании

Рассмотрим стандартную и двойственную к ней задачи линейного программирования.

Стандартная задача:

Найти значения переменных х₁, х₂,..., х_n, удовлетворяющих условиям

; (4.1)

; (4.2)

. (4.3)

Двойственная задача:

Найти значения переменных у₁, у₂,..., у_m, удовлетворяющих условиям

; (4.4)

; (4.5)

. (4.6)

Условия (4.1) и (4.5), а также (4.2) и (4.4) называются взаимносопряжёнными.

Приведём формулировки основных теорем двойственности, необходимые для дальнейшего рассмотрения.

Теорема 1 (основная). Если задача (4.1) – (4.3) имеет оптимальное решение х*, то и двойственная к ней задача (4.4) – (4.6) также имеет оптимальное решение у*, причём

. (4.7)

Теорема 2 (о равновесии). Для каждой пары сопряжённых условий в оптимальном решении прямой и двойственных задач выполняются следующие соотношения: если одно из них выполняется как строгое равенство, то другое – как строгое неравенство и наоборот, т.е.

если то ; (4.8)

если то ; (4.9)

если то ; (4.10)

если то (4.11)

Примечание: в случае вырожденного решения одной из задач оба взаимносопряжённых условия выполняются как строгие равенства.

4.2 Экономическая интерпретация и свойства двойственныхоценок

Для формулировки свойств двойственных оценок придадим задачам (4.1) – (4.3) и (4.4) – (4.6) конкретный экономический смысл.