線形計画法の基本定理

線形計画法の基本定理（せんけいけいかくほうのきほんていり、英: fundamental theorem of linear programming）とは、数理最適化の線形計画法における定理で、凸多面体上での線型関数の極値をとり得るものはその多面体上の頂点に存在することをいう。また、極値をとるような頂点が二つ存在する場合は、その頂点を端点としてもつ線分上もまた極値をとる解であることをいう。

以下の最適化問題が与えられているとする:

${\displaystyle \min }$		${\displaystyle c^{T}x}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle x\in P}$

ただし、${\displaystyle P=\{x\in \mathbb {R} ^{n}:Ax\leq b\}}$ とする。もし、${\displaystyle P}$ が有界な多面体であり、${\displaystyle x^{\ast }}$ を最適化問題の最適解としたとき、最適解 ${\displaystyle x^{\ast }}$ は多面体 ${\displaystyle P}$ の端点（頂点）あるいは、多面体の面 ${\displaystyle F\subset P}$ に存在する。

今、${\displaystyle x^{\ast }\in \mathrm {int} (P)}$（すなわち、${\displaystyle x^{\ast }}$ が ${\displaystyle P}$ の内部にある）であるとする。このとき、ある ${\displaystyle \epsilon >0}$ が存在して、半径 ${\displaystyle \epsilon }$ の開球 ${\displaystyle B_{\epsilon }(x^{\ast })}$ が ${\displaystyle P}$ に含まれる。すなわち、${\displaystyle B_{\epsilon }(x^{\ast })\subset P}$ である。

それゆえ、

${\displaystyle x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\in P}$

かつ、

${\displaystyle c^{T}\left(x^{\ast }-{\frac {\epsilon }{2}}{\frac {c}{||c||}}\right)=c^{T}x^{\ast }-{\frac {\epsilon }{2}}{\frac {c^{T}c}{||c||}}=c^{T}x^{\ast }-{\frac {\epsilon }{2}}||c||<c^{T}x^{\ast }.}$

がいえるため、${\displaystyle x^{\ast }}$ は最適解ではなく、矛盾が生じる。このことから、${\displaystyle x^{\ast }}$ は ${\displaystyle P}$ の境界上に存在しなければならない。

もし、${\displaystyle x^{\ast }}$ が頂点でないならば、${\displaystyle x^{\ast }}$ は ${\displaystyle P}$ の頂点 ${\displaystyle x_{1},...,x_{t}}$ の凸結合で表すことができる。すなわち、${\displaystyle x^{\ast }=\sum _{i=1}^{t}\lambda _{i}x_{i}}$ および ${\displaystyle \lambda _{i}\geq 0}$、${\displaystyle \sum _{i=1}^{t}\lambda _{i}=1}$ によって表される。

このとき、

${\displaystyle 0=c^{T}\left(\left(\sum _{i=1}^{t}\lambda _{i}x_{i}\right)-x^{\ast }\right)=c^{T}\left(\sum _{i=1}^{t}\lambda _{i}(x_{i}-x^{\ast })\right)=\sum _{i=1}^{t}\lambda _{i}(c^{T}x_{i}-c^{T}x^{\ast }).}$

がいえる。

${\displaystyle x^{\ast }}$ は最適解であることから、総和内の各項 ${\displaystyle c^{T}x_{i}-c^{T}x^{\ast }}$ はすべて非負でなければならない。そして、それらの和が 0 となるためには、各項が 0 でなければならない。すなわち、すべての ${\displaystyle x_{i}}$ に対して ${\displaystyle c^{T}x^{\ast }=c^{T}x_{i}}$ が成り立つ。よって、すべての ${\displaystyle x_{i}}$ もまた最適解であり、頂点 ${\displaystyle x_{1},...,x_{t}}$ をもつ面上のすべての点が最適解となる。

• Bertsekas, Dimitri P. (1995). Nonlinear Programming (1st ed.). Belmont, Massachusetts: Athena Scientific. p. Proposition B.21(c). ISBN 1-886529-14-0 
• “The Fundamental Theorem of Linear Programming”. WOLFRAM Demonstrations Project. 2024年9月25日閲覧。

• 線形計画法