Mathematical
Programming
 		JavaScript Demos of Two Phase Method

Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson

Twophase
JavaScript demos:
FAQ
線形計画問題(Linear Programming Problem)
minimizez= x1 +x2 +3x3 +3x4
subject to 3x1 +x2 +4x3 +5x4= 34
x1 +2x2 +4x3 +3x4= 22
x1>=0, x2>=0, x3>=0, x4>=0
はすでに標準形(standard form)になっているが、 最初の実行可能基底解(basic feasible solution)が分からない。 そこで、2段階法(two-phase method)を用いる。 まず、非負の人為変数(artificial variables) x5 と x6 を導入して 2段階法のシンプレックス・タブロー(simplex tableau)を書き、 第一段階の最小化(phase I)として x5+x6に相当する w の最小化を行う。

サイクル0で、 -wの行のxの係数(相対費用係数)のうち負で最小のものは x3 と x4 の係数 -8 なので、ここでは、 x3 を新しい基底変数とする。 x3 を0から+へ大きくして行ったとき、 x3 = 34/4 のとき x5=0 となり、 x3 = 22/4 のとき x6=0 となるので、 x6 を基底変数から取り除く。 すなわち、 第2行第3列をピボットとして ピボット操作(pivoting)を行う。 同様に、サイクル1では 第1行第1列をピボットとして ピボット操作(pivoting)を行う。
サイクル2で、w=0となるので、 もとの問題は実行可能(feasible) であることがわかる。 そこで、 そのときの実行可能基底解(basic feasible solution)を出発点として 第二段階の最小化(phase II)(zの最小化)を行う。
x2 の係数が負なので、 ピボット操作(pivoting)により基底変数の入れ替え (x2→基底, x3→非基底) を行うと、 zの相対費用係数がすべて非負となり、 最適解(optimal solution)が求まる。すなわち、
x1=46/5, x2=32/5, x3=0, x4=0のとき、 zは最小値 78/5 をとる。
Kenji Ikeda's
Home Page		 Last Modified: Monday, 31-Aug-2015 18:04:57 JST