線形計画法について勉強した

競技プログラミング

目的関数と制約条件がすべて線型の最適化問題を、線形計画問題と呼ぶ。例えば、
f:id:mihael1213:20140928010136j:plain
のとき、
f:id:mihael1213:20140928011202j:plain
のもとで、
f:id:mihael1213:20140928011139j:plain
を最小化する。（特に、この上記の形を標準形と呼ぶ。）

xの次数が2の場合を考える。xの値が取りうる範囲は、グラフを描くと、多角形になる。このとき、最適なxの値は、多角形の頂点のどれかになる。（一般には、多面体の頂点。）
このxの値が取りうる範囲の頂点を辺を伝って調べていくのがシンプレックス法である。

シンプレックス法については、そのうち書くかもしれません。
練習問題を探しています

参考