📂最適化理論

線形計画法における弱双対性定理の証明

定理

$$ \begin{align*} \text{Maximize} & \sum_{j=1}^{n} c_{j} x_{j} & \text{(Primal)} \\ \text{subject to} & \sum_{j=1}^{n} a_{ij} x_{j} \le b_{i} & i = 1 ,\cdots , m \\ & x_{j} \ge 0 & j = 1, \cdots , n \end{align*} $$ $$ \begin{align*} \text{Minimize} & \sum_{i=1}^{m} b_{i} y_{i} & \text{(Dual)} \\ \text{subject to} & \sum_{i=1}^{m} y_{i} a_{ij} \ge c_{j} & j = 1 ,\cdots , n \\ & y_{i} \ge 0 & i = 1, \cdots , m \end{align*} $$

与えられた線形計画問題のプライマル問題とデュアル問題が上のように表されるとしよう。もし$\left( x_{1} , \cdots , x_{n} \right)$がプライマル問題の実行可能解で、$\left( y_{1} , \cdots , y_{m} \right)$がデュアル問題の実行可能解ならば、以下の不等式が成立する。 $$ \sum_{j=1}^{n} c_{j} x_{j} \le \sum_{i=1}^{m} b_{i} y_{i} $$

説明

弱い双対性定理は、簡単に言えば、上の図のようにプライマル問題とデュアル問題の目的関数値が逆転しないことを保証するものである。

証明 ¹

$$ \begin{align*} \sum_{j} c_{j} x_{j} \le& \sum_{j} \left( \sum_{i} y_{i} a_{ij} \right) x_{j} & \because \text{Dual Constraint} \\ =& \sum_{i,j} y_{i} a_{ij} x_{j} \\ =& \sum_{i,j} x_{j} a_{ij} y_{i} \\ =& \sum_{i} \left( \sum_{j} a_{ij} x_{j} \right) y_{i} \\ \le& \sum_{i} b_{i} y_{i} & \because \text{Primal Constraint} \end{align*} $$

■

参照

線形計画法での双対性

最適化を専門にするのではなく、一科目として学ぶなら、シンプレックス法と双対性のこの二つを学べば、線形計画法の全てを学んだことになる。もちろん、その二つだけと言っても、そのコースが簡単だというわけではない。

シンプレックス法が具体的なその方法について論じるのに対して、双対性はプライマル問題に対してデュアル問題が存在し、その最適解が互いに等しいという、かなり理論的な―純粋数学的な議論である。これは、次の双対性定理で保証される。

弱い双対性定理

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} \le \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$

強い双対性定理

$$ \sum_{j=1}^{n} c_{j} x_{j}^{\ast} = \sum_{i=1}^{m} b_{i} y_{i}^{\ast} $$