単体法 (simplex method) †実行可能領域の境界の頂点をたどりながら最適解を見つける方法. 次の線形計画問題の場合
制約数を \(M\),\(\mathbf{x}\) の大きさを \(N\) とする. \(\mathbf{x}\) のうち,\(N-M\)個の要素が 0 であり,実行可能領域にあるものを実行可能基底解(basic feasible solution)と呼ぶ. この実行可能基底解は実行可能領域の頂点に該当する. この実行可能基底解の,目的関数の値をより小さくするように,0 である要素と,0でない要素とを入れ替える.これは,隣接する実行可能領域の頂点に移動させることに相当している.
関連項目 †リンク集 †関連文献 †
|