Двоїстість у лінійному програмуванні

Згадаємо формулювання прямої і двоїстої програм у стандартній формі.

\begin{align} \text{максимізувати}\ &\vec{c}^T\vec{x}\\ \text{за умов}\ &A\vec{x}\le \vec{b}\\ &\vec{x}\ge 0 \end{align}

\begin{align} \text{мінімізувати}\ &\vec{b}^T\vec{y}\\ \text{за умов}\ &A^T\vec{y} \ge \vec{c} \label{eq:dual_constr}\\ &\vec{y}\ge 0 \end{align}

Фізичне тлумачення

• Застосувати поле $\vec{c}$ до кульки в середині обмеженого багатогранника $A\vec{x} \le \vec{b}$.
• Зрештою, кулька зупиниться біля краю багатогранника (в точці $\vec{x}'$).
• Грань $\vec{a}_i\vec{x}'\le b_i$ накладає певну силу $-y_i\vec{a}_i$ на кульку.
• Кулька стабільна, тому $\vec{c}^T = \sum_i y'_i\vec{a}_i = \vec{y}'^TA$.
• Двоїстість можна уявити як намагання мінімізувати "роботу" $\sum_i y_ib_i$, щоб перенести м'ячик у початок координат рухаючи багатогранник.
• В оптимальній позиції тиснуть лише стіни суміжні з кулькою. (На рисунку лише $y_1, y_2$ не нульові.)

Звернемо увагу на те, що на кульку тиснуть лише грані до яких вона притуляється. Тобто для кожного $i$, або вона перебуває на лінії $\vec{a}_i^T \vec{x} = b_i$ або тиск дорівнює нулю: \begin{align} \vec{a}_i\vec{x} = b_i, y_i > 0&\ \text{торкається грані, тиск є} \label{eq:compslack1}\\ \vec{a}_i\vec{x} < b_i, y_i = 0&\ \text{не торкається грані, тиску немає}\label{eq:compslack2} \end{align} Тепер покажемо, що наш $\vec{x}'$ і є оптимальним розв'язком. Згідно з принципом слабкої двоїстості $\vec{c}^T\vec{x} \le \vec{b}^T\vec{y}$. Отже, якщо ми покажемо, що $\vec{c}^T\vec{x}' = \vec{b}^T\vec{y}'$, то це і є оптимальний розв'язок. Cтабільність кульки разом із третім законом Ньютона даюсть нам, що $A^T \vec{y}' = \vec{c}$. Завдяки рівнянням (\ref{eq:compslack1}, \ref{eq:compslack2}) ми можемо записати, що $\vec{a}_i\vec{x}'y'_i = b_iy'_i$, а отже $$\vec{c}^T\vec{x}' = \vec{x}'^T\vec{c} = \vec{x}'^TA^T\vec{y}' = (A\vec{x}')^T\vec{y}' = \sum_i\vec{a}_i\vec{x}'y'_i = \sum_i b_iy'_i = \vec{b}^T\vec{y}'$$ Отже, $\vec{x}'$ - оптимальний розв'язок, а $\vec{y}'$ - двоїстий до нього.

Економічне тлумачення

Розглянемо задачу оптимального виробництва:

• $n$ продуктів, $m$ сирих матеріалів.
• Продукт $j$ потребує $a_{ij}$ одиниць сирого матеріалу $i$.
• Всього доступно $b_i$ одиниць матеріалу $i$.
• Продукт $j$ дає $c_j$ прибутку на одиницю.
• Майстерня хоче максимізувати прибуток за наявних матеріалів

\begin{matrix} \text{максимізувати}&\vec{c}^T\vec{x}&\\ \text{за умов}&\vec{a}_i^T\vec{x}\le b_i,&\ i = 1, \dots, m.\\ &x_j\ge 0,& j = 1,\dots,n. \end{matrix} Якщо задача розв'язна і розв'язок скінченний, то допустима область - це опуклий багатогранник. Завжди існує щонайменше одна вершина в якій цільова функція набуває оптимального значення. Для задачі оптимального виробництва це означає, що для $n$ продуктів і $m$ сирих матеріалів, існує оптимальний план з щонайбільше $m$ продуктами.

Тлумачення двоїстих змінних

Для кожної одиниці продукту $j, j \in \{1,n\}$, нам потріно $a_{ij}, i \in \{1, m\}$. Для того, щоб було вигідно випускати продукт, його ціна має бути не меншою ніж сумарна ціна всіх складових. Позначимо ціну продукту через $c_p(j)$ і ціну матеріалу через $c_m(i)$, тоді $$c_p(j) \ge \sum_i a_{ij} c_m(i)$$ Але ж з точністю до знаку це те саме, що і обмеження двоїстої програми (\ref{eq:dual_constr}). Поглянемо на це з іншого боку. За умови що $\vec{x}$ і $\vec{y}$ оптимальні розв'язки відповідно прямої і двоїстої задач згідно з принципом сильної двоїстості маємо: $$\vec{c}^T\vec{x}=\vec{b}^T\vec{y}$$

• Ліворуч маємо максимальний виторг.
• Праворуч - $\sum_i (\text{наявність матеріалу}\ i) \times (\text{виторг на одиницю матеріалу}\ i)$

Інакше кажучі: Значення $y_i$ в оптимумі - це двоїста ціна ресурсу $i$.

Якщо ж значення не оптимальні, тобто

$$\vec{c}^T\vec{x}<\vec{b}^T\vec{y}$$ Розв'язок не оптимальний, бо ресурси не використані повністю.