シンプレックス法

• 線形計画の問題を解くアルゴリズムである
• 最適解があるなら最適実行可能基底解が存在するという前提がある

方法

1. 全ての変数をプラスしか取らないような表現に変換
2. 目的関数を最小化として解釈(陰関数)
3. 制約条件の式にslack変数というダミー変数を入れる
4. slack変数が対角行列になるので、slack変数でない変数の基底を求める作業を行う
   • 掃き出し法がメジャーである
5. 掃き出し法の結果、z=~になった結果が最大値(最小値)である

参考

• シンプレックス法（単体法）
• シンプレックス法を雑に理解した