北邮运筹学ch16人工变量法.ppt

§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 1 of 8 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法例例1.15】用大M法解 下列线性规划8/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 2 of 8【解解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量，x6、，x7，目标函数中加入―MR6―MR7一项，得到人工变量单纯形法数学模型再用前面介绍的单纯形法求解，见下表 8/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 3 of 8 Cj32－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λj000－5－25/38/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 4 of 8（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如(参看第二章第一节)；（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。

8/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 5 of 8【例例1.16】求解线性规划 【解解】加入松驰变量x3、x4化为标准型在第二个方程中加入人工变量x5，目标函数中加上M x5一项，得到 8/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 6 of 8用单纯形法计算如下表所示 Cj5－800MbCBXBx1x2x3x4x50Mx3x53※11－2100－1016→4λj5－－M↑－8+2M0M05Mx1x5101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM08/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 7 of 8表中λj≥0，j=1，2，…，5，从而得到最优解X=（2，0，0，0，2）， Z=10+2M。

但最优解中含有人工变量x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解解的判断唯一最优解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解 多重最优解的判断多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解. 无无界界解解的的判判断断: 某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可行解无无可可行行解解的的判判断断：：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解8/30/2024§1.6人工变量法人工变量法The Artificial Variable Method Ch1 Linear Programming Page 8 of 8计算公式第二章 对偶线性规划人工变量法演示人工变量法练习Exit8/30/2024。