単体法で解く

第1章 No.9 ／ 線形計画法を「手で回せるアルゴリズム」にする

No.1 では 2 変数の線形計画問題を グラフで解き、No.4 以降は Mathematica や Octave といった計算機に数値解を任せた。 では、その計算機は内部でいったい何をしているのだろうか。 その中心にあるのが、1947 年に G. ダンツィク（Dantzig）が考案した 単体法（シンプレックス法, simplex method）である。 ここでは単体法の考え方を説明し、実際に一つの問題を最後まで解いてみる。

1. なぜ単体法が必要か

グラフ（図示）で解けるのは変数が 2 個までである。変数が 3 個なら立体、 4 個以上になると人間には描けない。しかし線形計画問題には、 次の大切な性質がある。

だから「すべての頂点を調べれば最適解が見つかる」。ところが頂点の数は 変数と制約が増えると爆発的に多くなり、全部は調べきれない。 そこで単体法は、ある頂点から出発し、目的関数がより良くなる隣の頂点へ 次々と移っていく。良くなる隣がなくなったら、そこが最適解である。 「かどからかどへ辺を伝って登っていく」イメージだ。

2. 標準形に直す — スラック変数

単体法は不等式のままでは扱えない。そこで各制約の「余り」を表す スラック変数 s を足して、不等式を等式にする。たとえば

s = 18 − 3x₁ − 2x₂ は「まだ使っていない資源の量」である。 目的関数 z も z − 3x₁ − 5x₂ = 0 の形にそろえて、変数とスラックをすべて等式で並べたものを 標準形と呼ぶ。

3. 単体表（タブロー）と手順

標準形の係数を表にしたものが単体表（タブロー）である。 単体法は、この表に対して次の 3 ステップを繰り返すだけの機械的な手続きだ。

4. 実際に解いてみる

スラック変数 s₁, s₂, s₃ を入れて標準形にする。

まず x₁ = x₂ = 0（何もつくらない原点）から出発する。 このとき基底は s₁=4, s₂=12, s₃=18、利益 z = 0。

z の行で最も負なのは x₂ の −5 → x₂ が入る変数。 比の検定は 12/2 = 6 と 18/2 = 9 で、最小の 6 の行、すなわち s₂ が出る変数。ピボット要素は 2（オレンジのマス）。

x₂ の列を掃き出す（s₂ 行を 2 で割り、他の行から消す）。 x₂ = 6 が基底に入り、z は 0 → 30 に増えた。

まだ z の行に −3 が残っている → x₁ が入る変数。 比の検定は 4/1 = 4 と 6/3 = 2 で、最小の 2 の行、 s₃ が出る変数。ピボット要素は 3。

x₁ の列を掃き出す。x₁ = 2 が基底に入り、z = 36。

z の行に負の係数がもうない。ここで単体法は終了する。

5. 頂点をたどる旅として見る

いま起きたことを No.1 のグラフで振り返ると、単体法は次のように 実行可能領域のかどを順にたどっていた。

原点から出発し、利益が伸びる隣のかどへ 2 回移って頂上に着いた。 変数が 2 個なので今回は図でも確かめられるが、 単体法は変数がいくつあっても同じ手順で動く。だからこそ Mathematica や Octave は、何十・何百変数の問題でもこの掃き出しを 高速に繰り返して最適解を出せるのである。