シンプレックス法: 線形計画入門 6 - コンピュータフリーク

この章では、良い基底解を辿っていくことで線形計画を効率よく解くシンプレックス法を紹介します。

議論の簡単化のための仮定

前章に引き続き標準形の線形計画を考え、制約条件の係数行列 (A) の行は全て一次独立であると仮定します。また、これに加えて、

実行可能解が存在すること
基底解 $x$ のうち 1 つが予め分かっていること
任意の基底解は非ゼロ要素をちょうど $m$ 個もつこと

を仮定します。

非ゼロ要素をちょうど $m$ 個もつ基底解を非縮退基底解、それ以外を縮退基底解といいます。縮退基底解は対応する添字集合 $B$ が一意に定まりません。

全ての基底解が非縮退である場合、その線形計画は非縮退であるといい、一つでも縮退基底解がある場合、その線形計画は縮退であるといいます。3 つ目の仮定は非縮退であることを仮定しています。

これらの仮定が満たされない場合にどうすればいいかについては後ほど議論します。

シンプレックス法の導入

仮定より、基底解 $x^{(0)}$ が 1 つ分かっているとします。$x$ より目的関数の小さい解を見つけるにはどうしたら良いでしょうか。

定義の確認

$x^{(0)}$ の非ゼロ要素を $B \subset \{1, \cdots, n\}$ とし、それ以外の要素を $N = \{1, \cdots, n\} \backslash B$ とします。仮定より $|B| = m$ です。

$A$ のうち $B$ に対応する列を並べた行列を $A_B \in \mathbb{R}^{m \times m}$、残りの列を $A_N \in \mathbb{R}^{m \times (n – m)}$ と置きます。基底解の定義より $A_B$ は正則です。

ベクトル $v$ について添字 $B$ に対応する部分を抜き出した部分ベクトルを $v_B$ と表すことにします。

よりよい実行可能解を見つける方法

前章での議論より、$B$ に対応する値は $$x_B = A_B^{-1} ( b – A_N x_N ) \tag{1}$$ と自動的に定まるので、$x_B$ を決定変数から削除し、$x_N$ のみを決定変数と考えることができます。

$x^{(0)}$ はこの式において $x_N = 0$ を代入した解です。このとき、式 (1) より $x_B = A_B^{-1} b$ で、目的関数は $c_B^\top x_B = c_B^\top A_B^{-1} b$ です。

$x_N$ を自由に動かすことにします。目的関数を $x_N$ のみの式で表すと、$$\begin{align*}c^\top x &= c_B^\top x_B + c_N^\top x_N \\ &= c_B^\top (A_B^{-1} b – A_B^{-1} A_N x_N) + c_N^\top x_N \\ &= (c_N^\top – c_B^\top A_B^{-1} A_N) x_N + c_B^\top A_B^{-1} b \end{align*}$$ となります。

ここで、もし $c_N^\top – c_B^\top A_B^{-1} A_N \ge 0$ が成立すると、$x_N \ge 0$ の範囲でどのように $x_N$ を設定しても $x_N = 0$ のときよりも目的関数を小さくできないので、$x_N = 0$ が最適解となります。

一方、$c_N^\top – c_B^\top A_B^{-1} A_N$ の中に負の要素が存在したとしましょう。その添字を $j \in N$ とします。つまり、$c_j – c_B^\top A_B^{-1} a_j < 0$ ということです。このとき、$x_N = (0, \cdots, 0, \overbrace{\varepsilon}^{j\text{番目}}, 0, \cdots, 0)$ と $j$ 番目の変数を微少量増加させたときの目的関数は $\varepsilon (c_j – c_B^\top A_B^{-1} a_j) + c_B^\top A_B^{-1} b < c_B^\top A_B^{-1} b$ となり、$x_N = 0$ の時よりも目的関数が小さくなります。また、$x_N = 0$ のとき定まる $x_B$ は正なので、$\varepsilon$ が十分小さければ $x \ge 0$ が成り立ち、等式制約も $x_B$ の定義より自動的に満たされ、実行可能解になります。これによりより良い実行可能解が見つかりました。

よりよい基底解を見つける方法

$\varepsilon$ を大きく取るほど目的関数は小さくなるので、実行可能性が成り立つギリギリまで大きい値に設定しましょう。$x_N = (0, \cdots, 0, \overbrace{\varepsilon}^{j\text{番目}}, 0, \cdots, 0)$ のとき式 (1) より $x_B = A_B^{-1} b – \varepsilon A_B^{-1} a_j$ です。$\bar{b} = A_B^{-1} b, y = A_B^{-1} a_j$ と置くと、これは $x_B = \bar{b} – \varepsilon y$ と簡単に表されます。$y_i \le 0$ であれば $\varepsilon$ をいくら大きくとっても $x_i$ は正のままです。$y_i > 0$ であれば、$\varepsilon > \bar{b}_i / y_i$ のとき $x_i$ が負になります。よって、全ての $y_i$ が非正であれば任意に目的関数を小さくできるので最適解が存在しません。一つでも正の要素があれば、$\varepsilon^* = \min \{\bar{b}_i / y_i \mid y_i > 0\}$ まで $\varepsilon$ を増やすことができます。最小を取る添字を $k \in B$ とすると、$x_N = (0, \cdots, 0, \overbrace{\varepsilon^*}^{j\text{番目}}, 0, \cdots, 0)$ のとき $x_B \ge 0, x_k = 0$ となります。このときの解を $x’, B’ = B \cup \{j\} \backslash \{k\}, N’ = \{1, \cdots, n\} \backslash B’$ とおくと、$x’$ は実行可能、$|B’| = m$, $x’_{N’} = 0$ です。また、以下のように $A_{B’}$ も正則であることが示せるので、$x’$ は基底解になります。

補題

$A_{B’}$ は正則である

証明

一般性を失うことなく $B = \{1, \cdots m\}$ であると仮定する。$A_B$ は正則なので、$a_1, \cdots, a_m \in \mathbb{R}^m$ は基底をなす。

$y = A_B^{-1} a_j$ より、 $y_1 a_1 + \cdots + y_m a_m= a_j$ と表せる。$y_k > 0$ より、$a_k = \frac{1}{y_j}(y_1 a_1 + \cdots + y_{k-1} a_{k-1} + y_{k+1} a_{k+1} + \cdots y_m a_m – a_j)$ と $a_k$ を $a_1, \cdots, a_{k-1}, a_{k+1}, \cdots, a_m, a_j$ の線形結合で表せるので、$a_1, \cdots, a_{k-1}, a_{k+1}, \cdots, a_m, a_j$ は基底をなす。よって $A_{B’}$ は正則。

以上をまとめると

$c_N^\top – c_B^\top A_B^{-1} A_N \ge 0$ が成立するとき → $x_0$ は最適解
$c_j – c_B^\top A_B^{-1} a_j < 0$ が成立するとき
1. $A_B^{-1} a_j$ が全て非正のとき → 最適解は存在しない
2. $A_B^{-1} a_j$ に正の要素が存在する時 → $x’$ は $x$ よりも目的関数の小さい基底解

これにより、適当な基底解 $x_0$ から出発し、もしこれが最適解であればその検証を、そうでない場合は最適解が存在しないことを発見するか、よりよい基底解 $x’$ を発見することができます。今度は $x’$ を開始点として同じステップを繰り返すと、どんどんと目的関数が小さい基底解を発見していくことができます。これがシンプレックス法です。

シンプレックス法

シンプレックス法を手続きとしてまとめます。

アルゴリズム: シンプレックス法（非縮退・実行可能の場合）

入力: 標準形線形計画のパラメータ $A, b, c$、基底解 $x^{(0)}$
出力: 最適解 $x^*$ または、最適解が存在しないことを宣言する

$B^{(0)} \subset \{1, \cdots, n\}$ を $x^{(0)}$ の非ゼロ要素、それ以外の要素を $N^{(0)} = \{1, \cdots, n\} \backslash B^{(0)}$ とし、$i = 0$ と設定する
$c_{N^{(i)}}^\top – c_{B^{(i)}}^\top A_{B^{(i)}}^{-1} A_{N^{(i)}} \ge 0$ が成立するなら $x^{(i)}$ を出力して終了
それ以外の場合、$c_j – c_{B^{(i)}}^\top A_{B^{(i)}}^{-1} a_j < 0$ が成立する $j \in N$ を任意にとる
$A_{B^{(i)}}^{-1} a_j$ が全て非正のとき、最適解が存在しないことを宣言して終了
$\bar{b} = A_{B^{(i)}}^{-1} b, y = A_{B^{(i)}}^{-1} a_j$ とおき、$\varepsilon^* = \min \{\bar{b}_i / y_i \mid y_i > 0\}$ および、最小値を達成する添字 $k \in B$ を計算する
$x^{(i+1)}_{N^{(i)}} = (0, \cdots, 0, \overbrace{\varepsilon^*}^{j\text{番目}}, 0, \cdots, 0)$, $x^{(i+1)}_{B^{(i)}} = A_{B^{(i)}}^{-1} b – \varepsilon^* A_{B^{(i)}}^{-1} a_j$, $B^{(i+1)} = B^{(i)} \cup \{j\} \backslash \{k\}$, $N^{(i+1)} = \{1, \cdots, n\} \backslash B^{(i+1)}$, $i \leftarrow i + 1$ とおき 2 へ戻る。

このアルゴリズムは有限回のステップで停止し、正しく解を出力します。

定理: シンプレックス法の正当性

シンプレックス法は有限回のステップで停止し、最適解が存在するときには最適解を、存在しないときには存在しないことを出力する

証明

シンプレックス法の各ステップで目的関数の値は真に小さくなるので、同じ解を二度訪れることはない。基底解は高々 $_nC_m$ 個なので、シンプレックス法は $_nC_m$ 回のループ以内に停止する。

アルゴリズムが停止するのは $c_{N^{(i)}}^\top – c_{B^{(i)}}^\top A_{B^{(i)}}^{-1} A_{N^{(i)}} \ge 0$ が成立するか $A_{B^{(i)}}^{-1} a_j$ が全て非正のときであるが、上の議論より、前者のとき $x^{(i)}$ が最適解であり、後者の場合最適解が存在しない。

理論的なバウンドは $_nC_m$ ステップですが、典型的な入力例では非常に高速に動作することが実験的・理論的に確かめられています