运筹学第4讲 线性规划3

运筹学

（OperationsResearch）上海海事大学20131009任课教师：邓伟邮箱：dengwei1663@单纯形表总结

注：在单纯形表中，检验数的形式为

其中，对于基变量来说，检验数而(此因：基变量的系数矩阵为一个单位阵，当前仅当

)因此线性规划所有变量的检验数可统一为单纯形表总结在初始的单纯形表中，在常数项b的下方添加上当前解（初始基本可行解）对应的目标函数值的相反数，这样，经过一系列的迭代，在最优单纯形表中，这个相反数经过迭代后为最优解对应的目标函数值的相反数。单纯形表总结cj02-210θCBXBbx1x2x3x4x50x15111000x4601-4100x52402601cj-zj-Z1=-601200初始目标函数值的相反数人工变量法在应用单纯形法确定初始基本可行解X1时，如果约束矩阵中不含有单位阵，可以采用人工变量进行处理。人工变量的引入在约束矩阵中不含单位阵时，一般要在模型中人为地添加一些非负变量，称为人工变量，构造一个新的线性规划问题，使新问题的约束矩阵中含有单位阵，从而可以方便地确定新问题的一个基本可行解然后再根据新问题与原问题的解的关系，给出原问题的解的结果。

人工变量法例5.1对于下面的模型

在加入人工变量之后，就得到新问题的约束条件。

此约束矩阵中含有单位矩阵，可以取变量为基变量，确定新问题的初始基本可行解。人工变量法下面介绍两种人工变量方法。大M法引入人工变量的目的是为了使约束系数矩阵中含有单位矩阵，由于此模型已有x4的系数列向量为单位向量，只需要再有两个单位向量就可以得到单位矩阵，所以只在第1个和第2个约束方程中添加两个人工变量即可。添人工变量的原则是，只要在约束矩阵中出现一个单位矩阵即可。构造上面模型对应的“大M规划”人工变量法其中x5,x6为人工变量，目标函数中人工变量的负系数M是非常大的正数，大M法即因此得名。下面分析构造大M规划的原理根据上述大M规划的形式，可以得到大M规划的一个初始基本可行解

(x1,x2,……，x6)T=(0,0,0,26,15,20)T由于x5,x6>0，所以(x1,x2,x3,x4)T=(0,0,0,26)T不是原规划问题的可行解。显然，为了使大M规划的基本可行解，对于原规划从不可行变为可行，需要借助于目标函数使人工变量的值减小到零。人工变量法

由于在大M规划的目标函数中，M为很大的数，所以在原规划存在可行解的情况下，只要人工变量不为零，目标函数就不可能实现极大化。可以说，大M对人工变量具有一种惩罚作用，一旦人工变量为零，这种惩罚作用就消失了，是大M使得人工变量趋于零的。由于非基变量是取零值的，所以M的作用反映在单纯形法的计算中，就是将人工变量从基本可行解的基变量中替换出去，使它们成为非基变量。人工变量法

关于大M法的几个结论：(1)大M规划有最优解，并且在最优解中人工变量皆取零值，则在这个最优解中去掉人工变量的部分后，就是原规划的最优解。(2)大M规划有最优解，但在最优解中人工变量不全为零，则原规划没有最优解。(3)大M规划没有最优解，则原规划也没有最优解。人工变量法

用大M法求解线性规划模型解加入人工变量x5,x6后，得到大M规划模型。取x4,x5,x6为基变量，将目标函数化为典式形式。建立大M规划的单纯形表，进行计算，计算过程如下面的单纯形表。人工变量法人工变量法由于M为很大的数，所以最后表中所有检验数均已小于等于零，因此得到新规划的最优解为(x1,x2,……，x6)T=(25/3,10/3,0,11,0,0)T。由于人工变量已取零值，根据大M法的结论，得到原规划问题的最优解为(x1,x2,x3,x4)T=(25/3,10/3,0,11)T

，最优目标函数值为112/3。

人工变量法例5.2

用大M法解下面模型先引入松弛变量x3,x4化为标准形式人工变量法

再引入人工变量x5,构造大M规划模型。取x3,x5为基变量，由约束条件解出代入目标函数中，得到典式形式人工变量法建立单纯形表进行求解：在上面的最优单纯形表中，检验数全部小于等于零，已得到大M规划的最优解。但是在最优解中人工变量x5=3不为零，所以原规划没有可行解。人工变量法解引入人工变量x5,x6构造大M规划

例5.3用大M法求解下面线性规划问题：由约束条件解出人工变量法代入目标函数，得到目标的典式形式构造单纯形表进行计算，得到人工变量法表中检验数，而皆小于等于零，故大M规划没有最优解。由大M法的结论可知，原规划也没有最优解。人工变量法在机器计算时，大M法有时出现变量字长限制的问题。两阶段法是另一种人工变量法，它是分两阶段进行求解的。两阶段法以下针对大M法中的模型进行讨论。1.引入人工变量构造第一阶段规划，也称辅助规划，求原规划的一个基本可行解。辅助规划的目标函数是求所有人工变量的和的最小值。由于人工变量非负，因此，使人工变量之和趋于零，就是使每个人工变量趋于零。人工变量法关于第一阶段规划(辅助规划)有以下结论：在第一阶段规划的最优解中，如果人工变量不为零，则原规划没有可行解，计算停止；如果人工变量全为零，并且人工变量均为非基变量，则在第一阶段规划的最优解中，去掉人工变量部分之后，就得到原规划的一个基本可行解，继续第二阶段的计算。人工变量法经过第一阶段的求解，得到原规划的一个基本可行解之后，要进行第二阶段的求解，即求解原规划。求解原规划不必另用新表，只需要在第一阶段规划的最优单纯形表中，将检验数行数字去掉，并将原目标函数用非基变量表示，得到检验数后填入表中。另外，由于人工变量已不起作用，所以将人工变量对应的两列元素去掉，经过这些调整之后，继续按照单纯形法步骤求解，直至得到最优解。人工变量法例5.4用两阶段方法求解下面的线性规划问题。解求解第一阶段规划：上面模型的第一阶段规划为，人工变量法由约束条件解出建立单纯形表进行计算，得到最优单纯形表，从表中可以看出，检验数已全部小于等于零，得到第一阶段规划的最优解(0,15/7,25/7,52/7,0,0)T。由于最优解中人工变量皆取零值，故得到原规划的一个基本可行解(0,15/7,25/7,52/7)T。代入目标函数w中，得到化为求极大人工变量法求解第二阶段规划：在最优单纯形表中，去掉人工变量部分的所有元素，并将检验数行换成原规划相应于基本可行解

(0,15/7,25/7,52/7)T的检验数。由于此时x2,x3,x4为基变量，由最优单纯形表可以得到：人工变量法人工变量法代入原规划的目标函数Z，得到将此检验数代入表中进行计算，去掉x5,x6两列元素，得到检验数全部非正，得到原规划的最优解(25/3,10/3,0,11)T,最优值112/3。人工变量法人工变量法例5.5用单纯形法求解下面线性规划问题解引入松弛变量x3,x4化为标准形，引入人工变量x5,x6求解第一阶段规划人工变量法将目标函数化为求极大，并用非基变量表示建立单纯形表进行计算由这个最优单纯形表可以看出第一阶段的最优解为(0,1/2,0,0,0,3/2)T，其中人工变量x6=3/2不为零，所以原规划没有可行解。多个最优解的讨论关于多个最优解的讨论：在图解法中已经看到，一个线性规划问题可能存在多个最优解，这里讨论如何在单纯形方法中识别一个模型是否有多个最优解，在存在的情况下，如何将这些最优解求出。在单纯形表中，存在第二个最优解的判别方法：如果在最优单纯形表中，除去基变量对应的检验数为零外，还存在非基变量xk对应的检验数也为零，并且xk所在列的各个系数aik不全小于等于零，则此模型存在第二个最优解。事实上，这是因为如果将这个检验数为零的非基变量作为进基变量进行迭代计算，则原最优解将发生变化，得到一新解。但是，由于这个进基变量的检验数已经为零，所以检验数行并不需要再做初等变换，因此得到的新解与原最优解取相同的函数值，所以新解也是最优解。多个最优解的讨论在得到第二个最优解后，可以通过下面方法得到无穷多个最优解。设X1,X2为两个最优解，则仍为最优解。当取[0,1]区间上不同值时，对应着不同的X0，因此可以得到无穷多个最优解。注：记Z*为最优值，X1,X2为最优解，则Z*=CX1=CX2，而又可证明X0为可行解，所以X0为最优解。多个最优解的讨论例5.6求出下面线性规划问题的多个最优解：在最优单纯形表中，得到第一个最优解X1=(0,2,16,4,0,0)T，最优值为128.从最优单纯形表可以看出，非基变量x6的检验数为零，并且，因此将x6引入基变量，求解第二个最优解。解

加入松弛变量x4,x5,x6化为标准形，求第一个最优解：多个最优解的讨论多个最优解的讨论第二个最优解为X2=(0,4,16,0,0,2)T，因此原规划的全部解可以表示为多个最优解的讨论第二个最优解为X2=(0,4,16,0,0,2)T，因此原规划的全部解可以表示为退化尽管计算过程的循环现象极少出现，但还是有可能的。先后有人提出了“摄动法”、“字典序法”。1974年Bland提出一种简便的规则（Bland规则）：如何解决这个问题？（1）选择中下标最小的非基变量xk为换入变量，即（2）当按最小比值规则计算存在两个以上的最小比值时，选取下标最小的基变量为换入变量。当按Bland规则计