Mathematical
Programming
JavaScript Demos of Simplex Algorithm

Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson


Simplex
JavaScript demos:

FAQ
線形計画問題
minimizez=-2x1-x2
subject to x1+2x2<=14
x1+x2<=8
3x1+x2<=18
x1>=0,x2>=0
の実行可能領域をx1-x2平面に図示すると、 凸五角形OABCDとその内部となる。 また、 目的関数の式は、 zを定数とすると、 x2切片が-zで傾きが-2の直線となる。 よって、 制約条件を満たし目的関数zを最小にする解は、 下図から、 (x1, x2)=(5,3), z = -13 であることが容易にわかる。

しかしながら、 このような図的解法は多次元の問題には適用できないので、 代数的解法を考える必要があろう。 上の図的解法では、 最小値を求めるためには、たとえばO→A→Bなどと端点のところだけ 調べて行けばよいことがわかる(cf. 線形計画法の基本定理)。 一方、 各直線の交点(O,A,B,C,D,E,F,G,H,I)は次の標準形の問題
minimizez=-2x1-x2
subject to x1+2x2+x3=14
x1+x2+x4=8
3x1+x2+x5=18
x1>=0,x2>=0, x3>=0,x4>=0,x5>=0
の基底解に対応し、実行可能領域の端点は実行可能基底解に対応する。たとえば、 原点Oはx3, x4, x5 を基底変数、 x1, x2を非基底変数(=0)とした場合に対応し、 点Aはx3, x4, x1を基底変数、 x2, x5を非基底変数(=0)とした場合に対応する。 (B〜Iはどの基底解に対応するか?) 以上を考慮すると、ある実行可能な基底解(たとえば原点Oに対応する解) から出発して、制約条件を満たしつつ、目的関数が減少する方向へ 基底変数を入れ換えていけば、最適解に到達すると予想される。 シンプレックス法は、以上の手順をシンプレックス・タブローに対する ピボット操作によって実現したものとみなすことができる。

Kenji Ikeda's
Home Page
Last Modified: Tuesday, 01-Sep-2015 11:30:57 JST