相補性定理

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

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