相補性定理

【そうほせいていり (complementarity slackness theorem)】

線形計画問題

${\begin{array}{llllllll}{\mbox{max.}}&\displaystyle \sum _{j=1}^{n}c_{j}x_{j}&\\{\mbox{s.t.}}&\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}&(i=1,2,\ldots ,m),\\&x_{j}\geq 0&(j=1,2,\ldots ,n)\end{array}}\,$

の実行可能解 $(x_{1},\ldots ,x_{n})\,$ と双対問題の実行可能解 $(y_{1},\ldots ,y_{m})\,$がそれぞれの問題の最適解であるための必要十分条件は,(1) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle (c_j-\sum_{i=1}^{m}a_{ij}y_i)x_j=0 \ (j=1,2,\ldots,n) \,} , かつ(2)$\textstyle (\sum _{j=1}^{n}a_{ij}x_{j}-b_{i})y_{i}=0\ (i=1,2,\ldots ,m)\,$ が成り立つことである. この主張を相補性定理と呼ぶ.