線形計画

線形計画

• 最も基本的な数理計画問題
• 理論的側面である双対性⇒感度分析やアルゴリズム構成に重要
• 解法：シンプレックス法，楕円体法，等

標準形（と呼ぶとする）

定式化は様々可能だが、すべてこの形に変形可（不等式を等式に変換するために非負変数（スラック変数）を導入等する）

目的関数：$\boldsymbol{c}^t \boldsymbol{x} \rightarrow min$
制約条件：$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \ge 0$

例
目的関数：$-2x_1+5x_2 ,\rightarrow \ max$
制約条件：$4x_1-6x_2 = 30$
$2x_1+8x_2 \le 50$
$7x_1+5x_2 \le 10$
$x_1 \le 0$, $x_2$は符号制約なし

双対性

与えられた任意の線形計画問題（主問題）に対して、等価なもう一つの線形計画問題（双対問題）を導ける（双対性）。また、任意の実行可能解における目的関数の値に対する大小関係（弱双対定理）とこれからさらに一方の問題の最適解が他方の最適解になる（双対定理）も示せる。

主問題と双対問題には複数のペアが存在するが、ひとつのペアからほかのペアを導けるので、ひとつ理解しておけばよい。
主問題として標準形の問題とする。

主問題（P）：
目的関数：$\boldsymbol{c}^t \boldsymbol{x} \rightarrow min$
制約条件：$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}, \ \boldsymbol{x} \ge \boldsymbol{0}$

これに対する双対問題は

双対問題（D）
目的関数：$\boldsymbol{b}^t \boldsymbol{w} \rightarrow max$
制約条件：$\boldsymbol{A}^t\boldsymbol{w} \le \boldsymbol{c}$

主問題・双対問題というのはあくまで相対的であり、上の双対問題を主問題と考えて、上で示した主問題と双対問題における変数の対応関係で変形すると、上の主問題が双対問題として導ける。

弱双対定理
（P）と（D）それぞれの任意の実行可能解$\boldsymbol{x},\boldsymbol{w}$に対して、常に$\boldsymbol{c}^t \boldsymbol{x} \ge \boldsymbol{b}^t \boldsymbol{w}$が成立

証明

弱双対定理は

• （P）の任意の実行可能解$\boldsymbol{x}$に対して、$\boldsymbol{c}^t\boldsymbol{x} \ge (D)の最大値$
• （D）の任意の実行可能解$\boldsymbol{w}$に対して、$\boldsymbol{b}^t\boldsymbol{w} \ge (P)の最小値$

を主張している。
これから、

• （P）と（D）のそれぞれの実行可能解$\boldsymbol{x},\boldsymbol{w}$が$\boldsymbol{c}^t\boldsymbol{x}=\boldsymbol{b}^t\boldsymbol{w}$を満たせば、$\boldsymbol{x},\boldsymbol{w}$はそれぞれ（P）と（D）の最適解になる
• （P）が有界でないならば、（D）は実行可能解を持たないし、逆に（D）が有界でないならば、（P）は実行可能解を持たない
• 双対問題の実行可能解$\boldsymbol{w}$をひとつ見つけて、目的関数の値$\boldsymbol{b}^t\boldsymbol{w}$を計算すると、これは主問題の最小値の下界値（少なくともこれよりは大きいという値）をひとつ知ることができる。とくに、双対問題の最適解が見つかれば、そのときの目的関数の値$\boldsymbol{b}^t\boldsymbol{w}$を計算すると、主問題の最小値になっている。

これを主張するのが双対定理である。

双対定理
（P）または（D）の一方で最適解を持てば、他方も最適解をもち、（P）の最小値と（D）の最大値は等しい。