📂最適化理論

線形計画法の基本定理の証明

定理

方程式形式の線形計画問題に関して、次の三つのうち一つは真である。

• (1): もし最適解が存在しない場合、問題自体が不可解^infeasibleまたは無限大^unboundedである。
• (2): もし可解が存在する場合、可解基底解も存在する。
• (3): もし最適解が存在する場合、最適基底解も存在する。

証明

戦略: 基本定理という名前がついているだけあって、線形計画法そのものの可能性を論じている。省略証明は別として、他の補助定理を集めたものである。省略証明とは言っても、直感に頼り過ぎで数学的な論法ではないが、アルゴリズム的にアプローチした場合誤っていない。 (1)~(3)はVanderbeiとMatousekが適切に混在している。証明を理解するには少なくとも、シンプレックス法が何故必ず成功するのか、すなわちBlandのルールを理解している必要がある。

簡略版 ¹

フェーズ1で問題が不可解かどうか知ることができるし、基底可解を作り出すことができ、フェーズ2ではBlandのルールを使用したシンプレックス法を通じて問題が無限大かどうか知ることができるし、最適基底解を見つけることができる。

(1) ²

方程式形式での最適解の存在性: $$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$ 行列 $A \in \mathbb{R}^{m \times n}$、$\mathbf{b} \in \mathbb{R}^{m \times 1}$、及び$\mathbf{c} \in \mathbb{R}^{n}$に関して、線形計画問題が方程式形式で表される場合、少なくとも一つの可解が存在し、可解の集合が$\mathbf{c}^{T} \mathbf{x}$で上限有界^{bounded Above}であれば、最適解が存在する。

上記の補助定理の対偶によれば、より最適解が存在しない場合、可解の集合が空集合か目的関数が無限大である。

(2) ^{3 4}

基底可解の一意性: 線形計画問題が方程式形式で表される場合、その基底可解は基底$B$によって一意に定まる。

この補助定理は正確には基底可解の一意性を示すものであるが、証明過程でその存在性も示している。

Blandのルール: 線形計画法のシンプレックス法では$\mathcal{N}$から最も小さいものを入力変数のインデックスとして選び、$\mathcal{B}$から最も小さいものを出力変数のインデックスとして選ぶことをBlandのルール^{Brand’s rule}という。Blandのルールによれば、シンプレックス法はサイクルに陥らない。

サイクリング: もしシンプレックス法が終わらない場合、辞書がサイクルに陥っていることになる。

Blandのルールによれば、一つの可解が存在する場合、他の基底可解を見つけることができ、サイクリングを引き起こさずにシンプレックス法を使用することができる。

(3) ⁵

最適基底可解の存在性: 線形計画問題が方程式形式で表される場合、もし最適解が存在するならば、最適基底可解も存在する。

この補助定理の意味を詳細に考えると、最適解が存在する場合、その中の一つは基底可解でなければならないということである。

■