線形計画法のシンプレックス法（単体法）について分からないところがある．．．．．

質問

シンプレックス法の１段階単体法が分かるけど
いつどうやって2段階単体法を使う事はまったく理解できません
誰か説明していただきませんか？
人工変数も分からない
教えてください

回答No.2

kony0

２段階法の目的は、まさに#1さんのおっしゃるとおりです。あまり補足のしようがありません。

○いつ２段階法を使うか？

制約条件の等式を満たす「初期点」がすぐに選べない場合に適用します。

もし制約条件がすべて不等式制約で、スラック変数を導入して等式制約におきかえた標準問題を解くのであれば、当該スラック変数に値を与えることで初期点が与えられますから２段階法は不要でしょう。

逆に、もとの問題で等式制約があるならば、基本的には２段階法を使うことになると思います。

ここで、#1の補足の問題は、たとえば(X1,X2,X3,X4)=(7.5, 2.5, 0, 0)が制約条件を満たす点の１つであることがすぐわかります。こんな場合は、もはや２段階法は必要ありません。

ただし、文字や制約条件が1000とかある場合に、すぐに自明な解が得られますか？というと無理でしょう。こんな場合こそ２段階法の登場です。

○どうやって２段階法を使うのか？

もとの問題の制約条件Ax=b≧0, x≧0（A: m行n列の係数行列、x: n次の縦ベクトル、b: m次の縦ベクトル、なお制約条件を満たす解があるための条件としてm≦nを仮定します）に対して、次の問題を考えます。

min 1^T y
s.t. (A E)(x^T y^T)^T = b≧0, x≧0, y≧0
ここで、
1^T: すべての要素が1であるm次の横ベクトル
y: m次の変数からなる縦ベクトルで、いわゆる「人工変数」
(A E): Aの右にm次の単位行列を並べたm行(n+m)列の行列
(x^T y^T)^T: ベクトルxの下にベクトルyを並べた(n+m)次の縦ベクトル
です。

ここで、この補助問題においてx=0, y=bは明らかに制約条件を満たします。

また、この等式制約のもとでy=0となった場合、Ax=bを満たすことになり、もとの問題の制約条件を満たすことに他なりません。

さらに、y=0となる場合は、この補助問題の最適解の場合に他なりません。

・・・というプロセスを踏みます。

ということで、

min: X5+X6
subject to:
X１－X２＋X３＋X４＋X５　 　＝５
X１＋X２＋X３－X４　 　＋X６＝１０
なる問題を、初期点(X1,X2,X3,X4,X5,X6)=(0,0,0,0,5,10)からシンプレックス法で解いてみてください。
そして、そこで得られる最適解のうち(X1,X2,X3,X4)がもとの問題の初期点として妥当なことを確認してください。

（補足）
補助問題の目的関数は、もとの問題の目的関数によりません。ま、補助問題の目的が「もとの問題の制約条件を満たす初期点を求める」ことですから当然といえば当然です。
そして、補助問題は、「無意味な変数を付け足したが、結局その変数を０にするのが目的」なので、ぶっちゃけていえば、目的関数は、「もとの変数に対する係数が０、スラック変数に対する係数が正」であり、かつ「当該目的関数を最小化」する（当然、係数が負＆目的関数を最大化でもOK）ならなんでもよいわけです。

なお、今までの表記はすべて、“標準化した”線形計画法に適用できます。（制約はすべて等式、変数はすべて非負・・・）

線形計画の基本的なところであれば、下記の本はお勧めです。
福島雅夫：数理計画入門（システム制御情報ライブラリー１５）、朝倉書店、1996