線形計画法（2D）

線形計画法は、線形の等式および不等式制約の下で線形目的関数を最適化します。静的に、実行可能領域は凸多面体を形成します。線形計画法の基本定理は、最適な解決策がこの多面体の頂点のいずれかで発生しなければならないことを示しており、これはシンプレックス法や内点法によって効率的に解かれます。

平たく言えば、限られた資源を複数の制約のもとで同時にやりくりしており、各不等式が平面の一部を切り取ります。すべての制約が重なる部分が実行可能領域で、その内側の点はどれも有効な計画です。線形の目的関数は一方向へ増え続けるため、最良の計画は制約が交わる頂点に落ち着きます。要点は、最適化ではすべての点を調べる必要はなく、わずかな頂点だけを確認すればよいということです。

1945年、経済学者ジョージ・スティグラーは、必要な栄養をすべて満たす最も安い食事を調べました。これは77品目からなる線形計画問題です。アルゴリズムがない中で巧みに推定し、年間およそ $39.93(1939年価格)を得ました。1947年にダンツィクのシンプレックス法が正確に解くと、真の最小値は $39.69 — スティグラーの手計算は年間わずか約24セントしか外していませんでした。地味な経済学が、線形計画法の草創期を代表する事例になったのです。