Теоремы двойственности

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

1) обе задачи имеют планы;

2) только одна из задач имеет планы;

3) множество планов обеих задач пусто.

Теорема 1. Для любых допустимых планов X = (x₁, x₂,… x_n) и Y = (y₁, y₂,…, y_m) исходной и двойственной задач соответственно значение целевой функции в задаче минимизации.

Теорема 2. Если исходная и двойственная задачи имеют допустимые планы, то существуют и оптимальные планы у этих задач.

Теорема 3 (первая основная теорема двойственности). Если одна из задач двойственной пары имеет оптимальный план, то другая также имеет оптимальный план. При этом для любых оптимальных планов

 

X^* = (x₁^*, x₂^*,…, x_n^*) и Y^* = (y₁^*, y₂^*,…, y_m^*)

имеет место равенство

∑ c_jx_j^* = ∑ b_iy_i^*

 

Если целевая функция одной из задач не ограничена, то ограничения другой задачи несовместны. Однако обратное утверждение неверно. В случае отсутствия допустимых планов одной из задач другая также может не иметь допустимых планов.

 

Теорема 4 (вторая основная теорема двойственности).

Для того, чтобы допустимые планы x^* и y^* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

x_j^* (∑a_ijy_i^* - c_j) = 0, j = 1, n;

y_i^* (∑a_ijx_j^* - b_i) = 0, i = 1, m.

 

Это означает, что если какое-либо ограничение одной задачи при подстановке в него оптимального плана обращается в строгое неравенство, то соответствующая этому ограничению переменная в оптимальном плане двойственной задачи равна нулю. И наоборот, если какая-либо переменная в оптимальном плане одной задачи положительна, то соответствующее ей ограничение двойственной задачи обращается в равенство.

Формально указанная связь между исходной и двойственной задачей можно записать следующим образом:

 

если ∑a_ijx_j^* > b_i, то y_i^* = 0;

если y_i^* > 0, то ∑a_ijx_j^* = b_i;

или

если x_j > 0, то ∑a_ijy_i^* = c_j;

если ∑a_ijy_i^* > c_j, то x_j = 0.