[講義メモ]Computational Intractability(5/12)

実際に線形計画問題をどうやって解くのかの話.

1. LP問題の標準形が与えられる
 maximize\:\: c^T x, Ax \leq b, x\geq 0

れいだい.
max 5×1 + 6×2 + 9×3 = z
constraints x1 + 2×2 + 3×3 ≦ 5, x1 + x2 + 2×3 ≦ 3, x1, x2, x3 ≧ 0

2. スラック変数を加えて式を変形する.
x4 = 5 – x1 – 2×2 – 3×3
x5 = 3 – x1 – x2 – 2×3

3-a. 変数を選び,zを最大化するように値を可能な範囲で変化させる

3-b. 変数を入れ替えして問題を整理し直す

4. zの式に負の係数だけになったら終わり

線形計画問題 – Wikipedia

シンプレックス法 – Wikipedia

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です