単体法 (simplex method) †

実行可能領域の境界の頂点をたどりながら最適解を見つける方法．

次の線形計画問題の場合

  • 目的関数：\(\min\; \mathbf{c}^\top\mathbf{x}\)
  • 制約条件：\(A\mathbf{x}=\mathbf{b}\)，\(\mathbf{x}\ge 0\)

制約数を \(M\)，\(\mathbf{x}\) の大きさを \(N\) とする． \(\mathbf{x}\) のうち，\(N-M\)個の要素が 0 であり，実行可能領域にあるものを実行可能基底解(basic feasible solution)と呼ぶ．

この実行可能基底解は実行可能領域の頂点に該当する． この実行可能基底解の，目的関数の値をより小さくするように，0 である要素と，0でない要素とを入れ替える．これは，隣接する実行可能領域の頂点に移動させることに相当している．

-- しましま

↑

関連項目 †

↑

リンク集 †

↑

関連文献 †
トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:42 (3442d)