21. Прямая и двойственная задачи линейного программирования

1. Понятие двойственности

Каждой задаче линейного программирования можно поставить в соответствие другую задачу, называемую двойственной. Исходная задача называется прямой.

Двойственная задача к двойственной совпадает с исходной прямой задачей, поэтому обе задачи образуют двойственную пару.

Пусть

• $A=(a_{ij})$ — матрица размера $m\times n$;
• $x=(x_1,\ldots,x_n)^T$ — вектор переменных прямой задачи;
• $y=(y_1,\ldots,y_m)^T$ — вектор переменных двойственной задачи;
• $c=(c_1,\ldots,c_n)^T$;
• $b=(b_1,\ldots,b_m)^T$.

2. Прямая и двойственная задачи

Рассмотрим прямую задачу максимизации:

$$\max c^Tx$$

при условиях

$$Ax\leqslant b,\qquad x\geqslant 0.$$

Соответствующая ей двойственная задача имеет вид

$$\min b^Ty$$

при условиях

$$A^Ty\geqslant c,\qquad y\geqslant 0.$$

В координатной форме прямая задача записывается как

$$\max\sum_{j=1}^{n}c_jx_j$$

при условиях

$$\sum_{j=1}^{n}a_{ij}x_j\leqslant b_i, \qquad i=1,\ldots,m,$$ $$x_j\geqslant 0, \qquad j=1,\ldots,n.$$

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

$$\min\sum_{i=1}^{m}b_iy_i$$

при условиях

$$\sum_{i=1}^{m}a_{ij}y_i\geqslant c_j, \qquad j=1,\ldots,n,$$ $$y_i\geqslant 0, \qquad i=1,\ldots,m.$$

Таким образом, при переходе к двойственной задаче:

1. задача максимизации заменяется задачей минимизации;
2. матрица $A$ заменяется транспонированной матрицей $A^T$;
3. коэффициенты $b_i$ правых частей ограничений становятся коэффициентами целевой функции;
4. коэффициенты $c_j$ целевой функции становятся правыми частями ограничений;
5. каждому ограничению прямой задачи соответствует переменная двойственной задачи;
6. каждой переменной прямой задачи соответствует ограничение двойственной задачи.

3. Допустимые решения

Вектор $x$, удовлетворяющий условиям

$$Ax\leqslant b,\qquad x\geqslant 0,$$

называется допустимым решением прямой задачи.

Вектор $y$, удовлетворяющий условиям

$$A^Ty\geqslant c,\qquad y\geqslant 0,$$

называется допустимым решением двойственной задачи.

4. Теорема слабой двойственности

Для любых допустимых решений $x$ прямой задачи и $y$ двойственной задачи выполняется неравенство

$$c^Tx\leqslant b^Ty.$$

Доказательство

Из условия $A^Ty\geqslant c$ и неотрицательности $x$ следует

$$x^TA^Ty\geqslant x^Tc=c^Tx.$$

Из условия $Ax\leqslant b$ и неотрицательности $y$ следует

$$y^TAx\leqslant y^Tb=b^Ty.$$

Но

$$x^TA^Ty=y^TAx.$$

Следовательно,

$$c^Tx\leqslant x^TA^Ty=y^TAx\leqslant b^Ty,$$

откуда

$$c^Tx\leqslant b^Ty.$$

Таким образом, значение целевой функции прямой задачи не превосходит значения целевой функции двойственной задачи.

5. Следствия слабой двойственности

Если для допустимых решений $x^*$ и $y^*$ выполняется

$$c^Tx^*=b^Ty^*,$$

то $x^*$ является оптимальным решением прямой задачи, а $y^*$ — оптимальным решением двойственной задачи.

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

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

Обратные утверждения в общем случае неверны: из несовместности одной задачи не обязательно следует неограниченность другой.

6. Теорема сильной двойственности

Если прямая задача имеет конечное оптимальное решение, то двойственная задача также имеет оптимальное решение, причём оптимальные значения их целевых функций совпадают:

$$\max_{x}c^Tx=\min_{y}b^Ty.$$

То есть для оптимальных решений $x^*$ и $y^*$ выполняется

$$c^Tx^*=b^Ty^*.$$

Разность

$$b^Ty-c^Tx$$

называется разрывом двойственности. Для любых допустимых решений она неотрицательна, а для оптимальных решений равна нулю.

7. Условия дополняющей нежёсткости

Допустимые решения $x^*$ и $y^*$ являются оптимальными тогда и только тогда, когда выполняются условия

$$y_i^*\bigl(b_i-(Ax^*)_i\bigr)=0, \qquad i=1,\ldots,m,$$ $$x_j^*\bigl((A^Ty^*)_j-c_j\bigr)=0, \qquad j=1,\ldots,n.$$

Следовательно:

• если $y_i^*>0$, то соответствующее ограничение прямой задачи выполняется как равенство;
• если $x_j^*>0$, то соответствующее ограничение двойственной задачи выполняется как равенство.

8. Правила построения двойственной задачи

Для прямой задачи максимизации действуют следующие правила:

• ограничению вида $\leqslant$ соответствует двойственная переменная $y_i\geqslant 0$;
• ограничению вида $\geqslant$ соответствует переменная $y_i\leqslant 0$;
• ограничению-равенству соответствует переменная без ограничения на знак;
• переменной $x_j\geqslant 0$ соответствует двойственное ограничение вида $\geqslant$;
• переменной $x_j\leqslant 0$ соответствует ограничение вида $\leqslant$;
• переменной без ограничения на знак соответствует двойственное ограничение-равенство.