書記が数学やるだけ#62 線形計画問題における双対原理

最適化問題において重要な，双対原理について解説する。

問題

説明

元の線形計画問題の定義。

元の問題に対して，双体問題は次のように示される。

・変数：x→y

・制約不等式：m個→n個，不等式の向きが反対，係数が転置

・目的関数：最大化問題→最小化問題

・目的関数の係数と制約不等式の右辺の定数が入れ替わっている

変数yを，主問題のスラック変数λの双対変数と呼ぶ。また，スラック変数μを，主問題の変数xの双体変数と呼ぶ。

双体問題を考えるにあたり，双体定理が重要である。

「主問題と双対問題のいずれか一方が最適解を持つなら，もう一方も最適解を持ち，主問題の最大値と双対問題の最小値は一致する」

また，相補性定理も重要である。

スラック変数を導入したときの表現：

「変数が正ならその双体変数は0であり，双体変数が正ならその変数は0である」

解法

まず主問題について。

これに対して，双体問題は次のようになる。

これを解くと，次の最適解を得る。

双体問題をグラフで表すと以下のようになる。

双体問題の最適解が分かっているのであれば，主問題の最適解が求められる，逆もまた然り。

実のところ，今回の問題では双体問題を考えるメリットはあまりなかった。というのも，主問題の方が楽に解けるからである（双体問題では人工変数が必要）。

これの裏を返すと，主問題を解くのが難しい場合，その双体問題を解くことでより簡単に解ける場合があるということが言える。

これは今回扱った線形計画問題のほかに，非線形計画問題でも言えることである。それについては後日別に扱うものとする。

本記事のもくじはこちら：