線形計画法

目的関数も制約もすべて線形な最適化問題。Linear Programming、LP。

$$\underset{x}{\min }{c}^{\top }x\text{s.t.}Ax\le b,x\ge 0$$

解が頂点にある#

実行可能領域は線形不等式で囲まれた凸多面体になる。 線形関数は多面体の内部で極値を持たないので、 最適解は必ず頂点（のいずれか）に存在する。 これが LP を解きやすくしている根本的な理由で、 無限の候補を有限個の頂点の探索に還元できる。

2 つの解法#

単体法 (simplex method) — Dantzig が 1947 年に考案。 頂点から隣の頂点へ、目的関数が改善する方向に移動する。 最悪計算量は指数時間だが、実用上は極めて速く、いまも標準的に使われる。

内点法 (interior point method) — Karmarkar が 1984 年に提案。 多面体の内部を通って最適解へ近づく。多項式時間であることが証明されており、 大規模問題では単体法より速いことが多い。

双対性#

すべての LP には対になる双対問題があり、両者の最適値は一致する（強双対定理）。 双対解は制約を 1 単位緩めたときの改善量（シャドープライス）を意味し、 実務ではこの解釈が主目的になることもある。

参考文献#

• George B. Dantzig. Linear Programming and Extensions. Princeton University Press, 1963. https://doi.org/10.7249/R366
• Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica 4, 1984. https://doi.org/10.1007/BF02579150
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/