📂最適化理論

シンプレックス法の初期化と補助問題

ビルドアップ

$$\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}$に関して線形計画問題が上のように方程式フォームで表されるとしよう。そして、全ての$j = 1 , \cdots , n+m$に対して、$x_{k} \ge 0$が成り立ち、$i = 1 , \cdots , m$に対して $$\begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*}$$

線形計画問題の最初の辞書が上のように与えられたとする。シンプレックス法は基本的に、与えられた連立方程式の解を変えながら最適化する方法なわけだが、最初から変える解がなければどうしたらいいんだろう？ ¹ 一見すると、どうせ最適化は何とかなるから、とりあえず何か値を入れて適当に始めればいいように思えるけど、たとえば$x_{1} , \cdots , x_{n} = 0$とすると、$x_{n+i} = b_{i}$になるから $$\left( x_{1}, \cdots , x_{n} , x_{n+1} , \cdots , x_{n+m} \right) = \left( 0, \cdots , 0 , b_{1} , \cdots , b_{m} \right)$$ 制約条件を必ず満たしているように見えるけど、すぐに$b_{i} < 0$になったら、$\mathbf{x} \ge \mathbf{0}$に反する。一方でシンプレックス法は、シンプレックスの全ての頂点を探索すれば、必ず最適化に成功することができるが、この戦略の下では、何かしらの実行可能解を見つけることは、実際の最適解を見つけることと同じぐらい難しい。 ² もちろん、これは何の対策も無い場合だが、当然、数学者はその対策を用意してある。

用語

補助問題

シンプレックス法の初期化において、上記のような困難を非実行可能性^{infeasibility}と呼び、新しい変数を導入するトリックによって非実行可能性を解消した辞書を簡単に補助問題^{auxiliary Problem}と呼ぶ。

フェーズ

補助問題を作って、その最初の実行可能解を見つける過程をフェーズ1^{phase 1}と呼び、実際にシンプレックス法を適用して最適化する過程をフェーズ2^{phase 2}と呼ぶ。

例

補助問題がどんなものか、簡単な問題で実際に確認してみよう。$x_{1} , x_{2} , x_{3} \ge 0$に関して、以下のような線形計画問題が与えられているとしよう。 $$\begin{matrix} \text{Maximize} & & x_{1} & + & 2x_{2} \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & = & 4 \\ & & & & 2x_{2} & + & x_{3} & = & 2 \end{matrix}$$

この問題は、シンプレックスのどんな頂点を選んでも、初期化が上手くいかないことを示している。例えば、最も基本的な点$\left( x_{1} , x_{2} , x_{3} \right) = (0,0,0)$を考えてみると、制約条件を満たさない。もちろん、人によっては、すぐに$(1,1,0)$を見つけるかもしれないけど、この問題はあくまで例示するために作られた非常に簡単な問題だということを考えなければならない。実際の問題で$A \in \mathbb{R}^{100 \times 30}$のようなものが与えられたら、暗算や直感は全く役に立たない。

これを解決するアイデアは簡単だ。不等式形式の線形計画問題の方程式フォームを作るときにスラック変数を導入したように、補助変数^{auxiliary variable}を入れて、緩衝剤のような役割をさせることだ。新しい$x_{4} , x_{5} \ge 0$を $$\begin{matrix} \text{Maximize} & & & & & & & - & x_{4} & - & x_{5} & \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & + & x_{4} & & & = & 4 \\ & & x_{1} & & 2x_{2} & + & x_{3} & & & + & x_{5} & = & 2 \end{matrix}$$ のように入れてみると、非常に簡単に$(0,0,0,4,2)$という初期値を見つけることができる。ここからシンプレックス法を始めて、このところをフェーズ1と呼ぶことにした。