シンプレックス法

シンプレックス・タブローの作成

　　目的関数
　　　　Ｚ＝３ｘ₁ ＋２ｘ₂ 　→　最大
　　制約条件
　　　　　　４ｘ₁ ＋１ｘ₂ ≦７２
　　　　　　２ｘ₁ ＋２ｘ₂ ≦４８
　　　　　　１ｘ₁ ＋３ｘ₂ ≦４８

（注）この元の問題は「線形計画法の定式化と図式解法」にあります。そこではｘ，ｙ，ａ，ｂ，ｃという変数名を用いていましたが，ここからは，数学的な表現をするために，このような変数名を用います。

上の不等式は，次のように等式に表現することができます。
　　　　４ｘ_１＋１ｘ_２＋１λ_１＝７２
　　　　２ｘ_１＋２ｘ_２＋１λ_２＝４８
　　　　１ｘ_１＋３ｘ_２＋１λ_３＝４８
　また，一般に線形計画法では最小化問題を基準としていますので，目的関数のｘ_１とｘ_２の係数をマイナスにして最小化問題にします。すると，
　　　　Ｚ＝－３ｘ₁ －２ｘ₂＋１λ_１＋１λ_２＋１λ_３ 　→　最小
になります。

このようなλ_１，λ_２，λ_３のことをスラック変数といいます。λ_１とは，制約条件 ４ｘ₁ ＋１ｘ₂ ≦７２ の余裕であり，原料Ａの在庫が使われずに残った数量であると解釈されます。

これを「表０」のよう表にしたものを単体表（シンプレックス・タブロー）といいます。シンプレックスとは「単体」という意味で，シンプレックス法とはこの単体表を操作することにより，線形計画法を解く方法です。

表０
列　→

行 ↓

２次元表を一般に行列といいます。そして縦を行，横を列といい，個々のセルを要素といいます。例えば「目的関数の行のｘ_１の列の要素の値は－３である」というような表現をします。

なお，表０に「基底」という列があります。これは，変数に値を入れた（生産をした）変数の名称です。ここにλ_１，λ_２，λ_３があるのは，これらの変数を定数項だけ作る（すなわちｘ_１もｘ_２も生産しない）ことを意味しています。このときの目的関数の値（定数項）は０になりますので定数項を０にしておきます。

シンプレックス法の手順

手順１

目的関数の行の各要素のうち，最小の要素を持つ列をＬ列とします。
その要素が０か正であれば，最適解に達したことになり終了します。

手順２

Ｌ列の制約条件の要素が正のものについて，定数項をその要素で割った値が最小になる行をＫ行とします。

手順３

Ｋ行Ｌ列の要素をピボットとして掃出計算（後述）をします。
手順１に戻ります。

掃出計算

上の表で，ｉ行ｊ列の要素をＡ(ｉ,ｊ) ということにします。ピボットの要素はＡ(Ｋ,Ｌ) になりますが，その値をＰとします。

手順３ａ

Ｋ行以外の行（目的関数も含む）の全要素について，
　　　　Ａ(ｉ,ｊ) ＝ Ａ(ｉ,ｊ) － Ａ(Ｋ,ｊ)×Ａ(ｉ,Ｌ)／Ｐ
の操作をします。

手順３ｂ

Ｋ行の全要素（定数項も含む）をピボットＰで割ります。

数値例

実際に表０に対してこの手順を行ってみましょう。

第１回

手順１

目的関数の行では，ｘ₁ での－３が最小ですからＬ＝１列になります。－３＜０ですからまだ最適解にはなっていないので，手順２へ進みます。

目的関数の各要素の値は，それぞれの変数を１作るときの利益（マイナス表示になってはいますが）を示します。そのうちの最小のもの（ここではｘ１）をピボット列に選ぶということは，目的関数の値を増加させるのに最も効率のよいものを選ぶということです。

手順２

７２／４＝１８，４８／２＝２４，４８／１＝４８ですからλ₁ の行がＫになります。ピボットの値Ｐは４になります。

ｘ１をできるだけ生産しようとするのですが，図式解法のグラフからわかるように，１８が限度であるとわかります。これが「定数項／係数が最小の列を選ぶ」ことなのです。

手順３ａ

目的関数の行については，次のようになります。
　　ｘ₁ の要素：Ａ(ｉ,ｊ)＝－３，Ａ(Ｋ,ｊ)＝４，Ａ(ｉ,Ｌ)＝－３，Ｐ＝４ですから，（－３）－　４×（－３）／４＝０
　　ｘ₂ の要素：（－２） － １×（－３）／４＝－１.２５
　　λ₁ の要素：０ － １×（－３）／４＝０.７５
　　λ₂ の要素：０ － ０×（－３）／４＝０
　　λ₃ の要素：０ － ０×（－３）／４＝０
となり，表にすれば次のようになります。
　　　　　　　　　 ｘ₁ 　　 ｘ₂ 　　 λ₁ 　　λ₂ 　　λ₃ 　定数項
　　目的関数　　０　－１.２５　０.７５　　０　　　０　　５４
λ₂ の行，λ₃ の行についても同様な操作により，次の結果になります。
　　　　　　　　ｘ₁ 　　ｘ2 　　　λ₁ 　　　λ₂ 　λ₃ 　定数項
　　　λ₂ 　　　０　　１.５　　－０.５　　　１　　０　　　１２
　　　λ₃ 　　　０　　２.７５　－０.２５　　０　　１　　　１２

連立方程式の解法での表現をすればわかりよいでしょう。
λ_２行を例にすると，
　　　元のλ_２の列：　２ｘ_１＋２ｘ_２＋１λ_２＝４８　　　①
　　　元のλ_１の列：　４ｘ_１＋１ｘ_２＋１λ_１＝７２　　　②
において，ｘ_１の係数に着眼して　①－（２／４）×②　をすることにより，
　　　新λ_２の列：　０ｘ_１＋１.５ｘ_２－０.５＋１λ_２＝１２　　③
を求めたことになります。あるいは，手順３ｂでの④を①に代入して，ｘ_１を消去して③を得たともいえます。

手順３ｂ

λ₁ の行の全要素を４で割ります。その結果は次のようになります。
　　　　　　　ｘ₁ 　　ｘ₂ 　　　　λ₁ 　　　λ₂ 　　λ₃ 　定数項
　　　λ₁ 　　　１　　０.２５　　０.２５　　　０　　０　　　１８
このとき，ｘ₁ の列λ₁ の行で掃出計算をしたということで，基底のλ₁ をｘ₁ に変えておきます。

このピボット列（λ_１の列）を数式で表現すると，
　　　４ｘ_１＋１ｘ_２＋１λ_１＝７２
ですから，それをピボットで割るということは，
　　　１ｘ_１＋０.２５ｘ_２＋０.２５λ_１＝１８　　　　　④
としたことなのです。

ここまでの計算でわかるように，掃出計算とは連立方程式からある変数を消去する操作なのです。この操作により，表０は次の表１に書き換えられました。ピボットになったＬ列について，Ｋ行は１，それ以外は０になっているはずです。

表１

表１は，ｘ_１＝１８，λ_２＝１２，λ_３＝３０としたとき，目的関数の値が５４になることを示しています。表０→表１の操作を図式解法で図示すると，下図のＡを行ったことになります。

表１の目的関数の行には，未だマイナスの要素がありますので最適解ではありません。それで第２回の操作をするのですが，その操作は上図でのＢを行うことです。

第２回

手順１と手順２

目的関数の行での最小値はｘ₂ の列の－１.２５です。Ｌ＝２。
　ｘ₁ ：１８／０.２５＝７２，λ₂ ：１２／１.５＝８，λ₃ ：３０／２.７５＝１１ですから，その最小のものはλ₂ の行であり，ピボットはλ₂ 行ｘ₂ 列のＰ＝１.５になります。
　言い換えれば次のようになります。表１ではｘ_１を最大限作りｘ_２は作らないことを意味していました。ところが目的関数の列を見るとｘ_２を１作れば目的関数の値が１.２５増加することを示しています。そこで，点（１８,０）からどこまでｘ_２を増加できるかを調べると，定数項／係数が最小になるのは，λ_２の１２／１.５＝８ですから，（λ_２,ｘ_１）がピボットにするのです。

手順３

ここでの掃出計算は，ｘ_２の消去計算になります。目的関数，ｘ₁ ，λ₃ の行について手順３ａ
　　　　Ａ(ｉ,ｊ) ＝ Ａ(ｉ,ｊ) － Ａ(Ｋ,ｊ)×Ａ(ｉ,Ｌ)／Ｐ
を行い，λ₂ の行については，
　　　　Ａ(Ｋ,ｊ) ＝ Ａ(Ｋ,ｊ)／Ｐ
を行います。その結果は表２になります。

表２

この結果，目的関数の行がすべて０以上になるので，どれを作成しても目的関数は増加しないので，これが最適解であることがわかります。

「基底」と「定数項」を見てください。これより，「ｘ₁ ＝１６，ｘ₂ ＝８，λ₃ ＝８のとき，目的関数は最大値６４になる」と読み取ります。ここでλ₃ ＝８とは，制約式 １ｘ₁ ＋３ｘ₂ ≦４８ において８の余裕があるという意味です。

以下に表０～表２の全体を示します。