相補性定理のソースを表示

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

線形計画問題

<center>
<math>
\begin{array}{llllllll}
\mbox{max.} & \displaystyle \sum_{j=1}^{n}c_jx_j & \\
\mbox{s.t.} &  \displaystyle \sum_{j=1}^na_{ij}x_j\leq b_i & (i=1,2,\ldots,m),  \\
            & x_j \geq 0  &  (j=1,2,\ldots,n)
\end{array}
\,</math>
</center>


の実行可能解 <math>(x_1,\ldots,x_n) \,</math> と双対問題の実行可能解  <math>(y_1,\ldots,y_m) \,</math>がそれぞれの問題の最適解であるための必要十分条件は,(1) <math>\textstyle (c_j-\sum_{i=1}^{m}a_{ij}y_i)x_j=0 \ (j=1,2,\ldots,n) \,</math>,  かつ(2)<math>\textstyle (\sum_{j=1}^{n}a_{ij}x_j-b_i)y_i =0 \ (i=1,2,\ldots,m) \,</math> が成り立つことである. この主張を相補性定理と呼ぶ.