第一章 线性规划与单纯形法第5节.pptVIP

第一章线性规划与单纯形法第5节第1页，共28页，星期日，2025年，2月5日5.1人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量xn+1,…,xn+m，得到第2页，共28页，星期日，2025年，2月5日

以xn+1,…，xn+m为基变量，并可得到一个m×m单位矩阵。令非基变量x1,…,xn为零，便可得到一个初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T

因为人工变量是后加入原约束条件的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有cj-zj≤0，而在其中还有某个非零人工变量，这表示原问题无可行解。以下讨论如何解含有人工变量的线性规划问题。第3页，共28页，星期日，2025年，2月5日

1大M法

在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响；为此假定人工变量在目标函数中的系数为(-M)(M为任意大的正数)，这样目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。第4页，共28页，星期日，2025年，2月5日例8现有线性规划问题，试用大M法求解。第5页，共28页，星期日，2025年，2月5日解在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到这里M是一个任意大的正数。第6页，共28页，星期日，2025年，2月5日因本例的目标函数是要求min，所以用所有cj-zj≥0来判别目标函数是否实现了最小化。

用单纯形法进行计算时，见表1-6。第7页，共28页，星期日，2025年，2月5日

在表1-6的最终计算结果表中，表明已得到最优解是：

x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=-2

第8页，共28页，星期日，2025年，2月5日

2.两阶段法

用电子计算机求解含人工变量的线性规划问题时，只能用很大的数来代替M，这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第9页，共28页，星期日，2025年，2月5日第一阶段：

不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如第10页，共28页，星期日，2025年，2月5日第一阶段求解用单纯形法求解上述模型：若得到ω=0，这说明原问题存在基可行解，可以进行第二段计算。否则原问题无可行解，应停止计算。第11页，共28页，星期日，2025年，2月5日第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第3节单纯形法相同。下面举例说明第12页，共28页，星期日，2025年，2月5日例9试用两阶段法求解线性规划问题第13页，共28页，星期日，2025年，2月5日解先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：第14页，共28页，星期日，2025年，2月5日第一阶段用单纯形法求解，见表1-7。

求得的结果是ω=0，得到最优解是

x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因人工变量x6=x7=0，所以(0，1，1，12，0)T是这线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数。进行第二阶段计算，见表1-8。第15页，共28页，星期日，2025年，2月5日表1-7第16页，共28页，星期日，2025年，2月5日第二阶段计算，见表1-8第17页，共28页，星期日，2025年，2月5日从表1-8中得到最优解为x1=4,x2=1,x3=9,目标函数值z=-2.第18页，共28页，星期日，2025年，2月5日5.2退化单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，…又返回到B1，即出现计算过程的循环，便永远达不到最优解。第19页，共28页，星期日，2025年，2月5日尽管计算过程的循环现象极少出现，但还是有可能的。如何解决这问题?先后有人提出了“