線形計画法の基本定理

ウィキペディア

線形計画法の基本定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/08 06:25 UTC 版)

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

命題

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

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

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

証明

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

それゆえ、

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

かつ、

$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 }.$

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

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

このとき、

$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 }).$

がいえる。

$x^{\ast }$ は最適解であることから、総和内の各項 $c^{T}x_{i}-c^{T}x^{\ast }$ はすべて非負でなければならない。そして、それらの和が 0 となるためには、各項が 0 でなければならない。すなわち、すべての $x_{i}$ に対して ​ $c^{T}x^{\ast }=c^{T}x_{i}$ が成り立つ。よって、すべての $x_{i}$​ もまた最適解であり、頂点 $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日閲覧。

関連項目

• 線形計画法