对问题maxz= CX max Z=CBb+(C-CBN)XN s t AX=b A=B-b-B-INX X≥0 Xn≥0,Xx≥0 取可行基 检验数 关于可行基B的典则形式 B=(Pp 令xN=0得YB=Bb≥0得基本可行解X1=(Bb,0 1、若所有的检验数C-BN≤0,则x为最优解 2、检验数CN-CBN中存在一个分量>0,且该分量对应的列 向量中所有的分量<O,则目标函数值在可行解域内无上界 3、若检验数CM-CBN中至少有一个分量>0,且该分量对应 的列向量中至少有一个分量>0,则存在更好的基本可行解 做换基迭代:在迭代过程中,始终保持对应的基本解可行 即XB=Bb≥0 并使检验数C-C。B-N中>0的分量 个数越来越少,最终CN-CBN≤00 . max  = = X s t AX b 对问题 z CX ( ) B = P1 P2  Pm 取可行基 Z CB B b CN CB B N X N max ( ) − 1 − 1 = + − X B B b B NX N − 1 − 1 = − XB  0 , X N  0 关于可行基 B的典则形式 检验数 令X N = 0 0 1 =  − 得X B B b ( ) = − ,0 1 得基本可行解X1 B b 1 0 1 −  − 、若所有的检验数 C N B N , 则X 1为最优解 的列向量中至少有一个分量 则存在更好的基本可行解 、若检验数 中至少有一个分量 且该分量对应 0, 3 0, 1  −  − CN CB B N 向量中所有的分量 则目标函数值在可行解域内无上界 、检验数 中存在一个分量 且该分量对应的列 0, 2 0, 1  −  − CN CB B N 做换基迭代:在迭代过程中，始终保持对应的基本解可行 0 1 =  − 即XB B b 0 0 1 1 −  −  − −C C B N C C B NN B N B 个数越来越少，最终 并使检验数 中 的分量