|
Simplex
Twophase
Dijkstra
Prim
Kruskal
Ford-Fulkerson
Simplex
JavaScript demos:
FAQ
|
線形計画問題
| minimize | z | = | -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)は次の標準形の問題
| minimize | z | = | -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に対応する解)
から出発して、制約条件を満たしつつ、目的関数が減少する方向へ
基底変数を入れ換えていけば、最適解に到達すると予想される。
シンプレックス法は、以上の手順をシンプレックス・タブローに対する
ピボット操作によって実現したものとみなすことができる。
|