《运筹学 最优性检验证明.doc》由会员分享，可在线阅读，更多相关《运筹学 最优性检验证明.doc（6页珍藏版）》请在金锄头文库上搜索。
参考运筹学，高教出版社，朱道立编一、初始基本可行解的确定考虑如下形式的线性规划：设，并设的秩为m，则总可经过列调整使其前m个列向量线性无关，不妨设，其中，是线性规划的一个基。设是与对应的基变量，是非基变量，则。令，由得，这就是初始基本可行解。在处的目标函数值是其中是目标函数系数向量 中与基变量对应的分量组成的m维行向量，是中与非基变量对应的分量组成的n-m 维行向量。二、最优性检验得到初始基本可行解后，就要检验其是否为最优解，为此需要给出一个判别解是否为最优解的准则。考虑下面标准形式的线性规划问题下面从初始基本可行解出发（与其对应的目标函数值记为 ），求一个改进的基本可行解，设是任一可行解，不妨设，其中是基，设 是与对应的基变量， 是非基变量。则由方程组 得 ，在点的目标函数值是其中 ，。令 则由上式可知，如果能够适当选取非基变量的数值使从而得到使目标函数值增加的新基本可行解。如果对所有的 ，都有 ，则目标函数值已无法改善，因为 ，此时已达到最优解。
