Mathematical
Programming
JavaScript Demos of Simplex Algorithm

Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson


Simplex
JavaScript demos:

FAQ
線形計画問題
minimizez= -3x1-2x2-4x3
subject to x1+x2+2x3<=4
2x1+2x3<=5
2x1+x2+3x3<=7
x1>=0x2>=0x3>=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)。
Kenji Ikeda's
Home Page
Last Modified: Tuesday, 01-Sep-2015 11:30:57 JST