Simplex
Twophase
Dijkstra
Prim
Kruskal
Ford-Fulkerson
Simplex JavaScript demos:
FAQ
|
線形計画問題
minimize | z | = |
-3x1 | -2x2 | -4x3 |
subject to | | |
x1 | +x2 | +2x3 | <= | 4 |
| | |
2x1 | | +2x3 | <= | 5 |
| | |
2x1 | +x2 | +3x3 | <= | 7 |
| | |
x1>=0 | x2>=0 | x3>=0 | |
以下の手順でシンプレックス・タブローの更新を行う。
- 手順1: 新しく基底に入れる変数 Xs を求める(表をclick)。
- Cj(相対費用係数)のうち負で最小のものを求め、
その添字をsとする。
- もし、相対費用係数がすべて非負ならば、最適解を得て終了。
- 手順2: 基底から出す変数 Xr を求める(表をclick)。
- すべての Ais が非正ならば、非有界という答えを得て終了。
- 手順3: Bi/Aisのうち最小のものを求め
θとする。また、その添字を r とする。
- 手順4: ピボット操作(基底の入れ換え Xr←→Xs)
を行い手順1に戻る。
- 第r行をArsで割る(表をclick)。
- 第i行(i≠r)から、第r行 × Ais(Cs)
を引く(表をclick)。
|