运筹学 北京邮电大学.ch1-6.ppt

《运筹学 北京邮电大学.ch1-6.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。【例1.15】用大M法解下列线性规划7/21/2021【解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量，x6、，x7，目标函数中加入―MR6―MR7一项，得到人工变量单纯形法

2、数学模型再用前面介绍的单纯形法求解，见下表。7/21/2021Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M0－Mx6x5x7－4123－1－2121－1000101000014101→λj3－2M2+M－1+2M↑－M000－M0－1x6x5x3－6－3253－2001－1000100013→81λj5－6M5M↑0－M0020－1x2x5x3－6/53/5－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319

3、/3λj000－5－25/37/21/2021（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如(参看第二章第一节)；（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看

4、出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。7/21/2021【例1.16】求解线性规划【解】加入松驰变量x3、x4化为标准型在第二个方程中加入人工变量x5，目标函数中加上Mx5一项，得到7/21/2021用单纯形法计算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x53※11－2100－1016→4λj5－M↑－8+2M0M05Mx1x5101/3－7/31/3－1/30－10122λj0－29/

5、3+7/3M－5/3+1/3MM07/21/2021表中λj≥0，j=1，2，…，5，从而得到最优解X=（2，0，0，0，2），Z=10+2M。但最优解中含有人工变量x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解。解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解.无界解的判断:某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。无可行解的判断：当用大

6、M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。7/21/2021计算公式第二章对偶线性规划人工变量法演示人工变量法练习Exit7/21/2021