4.2最优性检验 设线性规划(L)的可行基B=(P1,P2,,Pm) iA=(B,N),C=(CB,CN)X=(XB,XN) 用B左乘约束方程组的两端，得 = |-EX:+B-iNXx-B-b 即 EX+B-INXN=B-ib 将X=B-b-B-NX代入目标函数 得 Z=CB-b-CB-NX+CX=CpB-+C-C B-N 记=（Cw-CB=(o+2on其中0=CCBp;j=m+1m+2n 即有Z=CB-b+oXy=CBb+.∑0，X (2) j=m+1
4.2 最优性检验 设线性规划（L）的可行基B=（P1,P2,…,Pm） 记A=（B，N），C=（CB，CN），X=（XB，XN) T 用B-1左乘约束方程组的两端，得 即 将 得 记 即有 （2） EX B NX B b X X B AX B B,N 1 N 1 B N −1 = −1 B = + − = − EX +B − NX =B − b 1 1 N 1 B XB =B −1b-B −1NXN代入目标函数 N 1 N B 1 N N N B 1 B 1 B Z C B b-C B NX C X C B b C -C B N X − = − − + = − + , ,, , j = m +1,m + 2,,n − + + − = = = ，j 1 m 1 m 2 n j j B 1 N N B σ C -C B N σ σ σ 其中σ C -C B P = + = + , = + − − n j m 1 j j 1 N N B 1 B Z C B b σX C B b σx
非基变量x:前面的系数σ，可以用来判断当前对应与基B的基可 行解是否为最优解。故称为变量x对应的检验数。 定理4.1（最优性判定定理)对某基可行解X=B-b,其余x0, 若所有检验数o,=C,CB-P≤0.jm+1m+2m则该解为最优解。 证明对一切可行解X,当所有检验数σ0时 Z=CX=CBb+Σ0XCBb, j=m+1 而基可行解X=Bb,其余x=0对应的目标函数值恰为CB-b, ∴.基可行解XBb,其余xO是最优解，B为最优基
非基变量xj前面的系数σj，可以用来判断当前对应与基B的基可 行解是否为最优解。故称为变量xj对应的检验数。 定理4.1（最优性判定定理） 对某基可行解 XB =B -1b，其余xj=0， 若所有检验数 则该解为最优解。 证明 对一切可行解X，当所有检验数σj≤0时 而基可行解XB =B -1b，其余xj=0对应的目标函数值恰为CBB -1b， ∴基可行解 XB=B-1b，其余xj=0是最优解，B为最优基。 = + + = − 0，j m 1,m 2,,n j 1 j j B σ C -C B P Z CX C B b σx C B b, 1 j j B 1 B n j m 1 − − = = + = +