第1章+线性规划与单纯形法-第5节.pdf

《第1章+线性规划与单纯形法-第5节.pdf》由会员分享，可在线阅读，更多相关《第1章+线性规划与单纯形法-第5节.pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 线性规划与单纯型法 第第5节 单纯形法的进一步讨论节 单纯形法的进一步讨论 5.1 人工变量法人工变量法 5.2 退化退化 5.3 检验数的几种表示形式检验数的几种表示形式=+=+=+=+=+=+0,;0,112211222222121111212111mnmnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxa?设线性规划问题的约束条件 其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量xn+1,xn+m，得到5.1 人工变量法人工变量法=njjjbxP1 以xn+1,，xn+m为基变量，便可得到一个mm单位矩阵。令非基变量x1,xn为

2、零，便可得到一个初始基可行解X(0)=(0,0,0,b1,b2,bm)T 因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有cj-zj0，而在其中还有某个非零人工变量，这表示原问题无可行解1.大M法 在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响；为此假定人工变量在目标函数中的系数为(-M)(M为任意大的正数)，这样目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。例8 试用大M法求解线性规划问题=+=0,1232411

3、23min32131321321321xxxxxxxxxxxxxxz解解在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到=+=+=+=0,12324112003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxzM是一个任意大的正数因本例的目标函数是要求min，所以用所有cj-zj0来判别目标函数是否实现了最小化.表1-6单纯形法表cj -3 1 1 0 0 M MCB XB b x1 x2 x3 x4x5x6x7 i 0 M M x4 x6 x7 11 3 1 1-4-2-2 1 0 1 2 1 1

4、 0 0 0-10 0 1 0 0 0 1 11 3/2 1 cj-zj -3+6M 1-M 1-3M 0 M0 0 在最终计算结果表中，最优解是：(4,1,9,0,0)zmin=-2cj -31 10 0 M M CBXB b x1x2 x3x4 x5 x6 x7 0 M1 x4 x6 x3 10 1 1 3 0-2-2 1 0 0011 0 0 0-1 0 0 1 0-1-2 1 1 cj-zj -11-M00 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 30-20 1 0 0011 0 0-2-1 0 2 1 0-5-2 1 4 cj-zj -10 00 1 M-1 M

5、+1 -31 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 001 1/30 2/3-2/3-1-4/32/3 1 4/3-5/3-2-7/3 cj-zj 2 0 0 01/31/3M-1/3 M-2/3 2.两阶段法 用电子计算机求解含人工变量的线性规划问题时，只能用很大的数来代替M，这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第一阶段：1121111221112112222221122121min000,0+=+=+=+=?nn mnnnnnnnmmm

6、nnn mmnnn mxxxxxa xa xa xxba xa xa xxba xaxaxxbx xxxx目标函数约束条件 不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第一阶段求解 然后用单纯形法求解上述模型?若得到=0，这说明原问题存在基可行解，可以进行第二段计算?否则原问题无可行解，应停止计算第二阶段：将第一阶段计算得到的最终表，除去人工变量 将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始表 各阶段的计算方法及步骤与第3节单纯形法相同例9 试用两阶段法求解线性规划问题=+=0,123241123min321

7、31321321321xxxxxxxxxxxxxxz约束条件目标函数解 先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：=+=+=+=+=+=+=0,12324112min765432173165321432176xxxxxxxxxxxxxxxxxxxxx约束条件目标函数 第一阶段用单纯形法求解 见表1-7。求得的结果是=0，得到最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0 因人工变量x6=x7=0，所以(0，1，1，12，0)T是这线性规划问题的基可行解 于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消；填入原问题的目标函数的系数

8、。进行第二阶段计算，见表1-8。cj 00 0 0 011CB XB b x1x2x3x4 x5x6x7 i 0 1 1 x4 x6 x7 113 1 1-4-2-21 0 1 2 11 0 0 0-10010001113/21 cj-zj 0-1-10 100 0 M 1 x4 x6 x3 101 1 30-2-210 0 0 1 1 0 0 0-10010-1-21-1-cj-zj 0-10 0 103 0 1 1 x4 x2 x3 121 1 30-20 1 0 0 0 1 1 0 0-2-10210-5-21 cj-zj 00 0 0 011 表 1-7第二阶段计算，表1-8cj-31

9、1 0 0 CB XBb x1x2x3 x4 x5 i0 1 1 x4x2x3121 1 30-20100 0 1 1 0 0-2-1 0 4-cj-zj -100 0 1 -3 1 1 x1x2x34 1 9 1 0 0 0100 0 1 1/30 2/3-2/3-1-4/3 cj-zj 2 0 00 1/3 1/3 从表1-8中得到最优解为x1=4,x2=1,x3=9,目标函数值 z=-2.5.2 退化 单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示

10、为同一顶点 有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解 尽管计算过程的循环现象极少出现，但还是有可能的勃兰特规则 有人提出了“摄动法”，“字典序法”1974年由勃兰特(Bland)提出一种简便的规则，一定能避免出现循环：(1)选取cj-zj0中下标最小的非基变量xk为换入变量，即k=min(jcj-zj0)(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量5.3 检验数的几种表示形式 本书以max z=CX;AX=b,X0为标准型；以cj-zj0，（j=1,2,n）为最优解的判别准则。还有

11、其他的形式。为了避免混淆，现将几种情况归纳如下。设x1,x2,xm为约束方程的基变量，于是可得+=nmjjijiimixabx1,2,1,?将它们代入目标函数后，可有两种表达形式)371()()()1(10111+=+=+=+=+=+=+=+=nmjjjjminmjmijijijiixzczxaccbcz)381()()()2(10111=+=+=+=+=nmjjjjminmjmijjijiiixczzxcacbcz判别准则的选择 要求目标函数实现最大化时，若用(1-37)式来分析，就得到cj-zj0,（j=1,2，,n）的判别准则。若用(1-38)式来分析，就得到zj-cj0,（j=1,2,

12、n）的判别准则。同样，在要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时分别用cj-zj0或zj-cj0，（j=1,2,n）来判别目标函数已达到最小几种判别准则的汇总标准型 检验数 max z=CXAX=b,X0 min z=CX AX=b,X0cj-zj zj-cj 0 0 0 0 5.4 单纯形法小结5.4 单纯形法小结(1)根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-10。分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。表 1-10 变 量 xj 0 xj 0 xj无约束 不需要处理 令 xj=-xj,xj0 令 xj=xj-xj,xj,xj 0 约 束 条 件 b0 b0 =不需要处理 约束条件两端同乘-1 加松弛变量 加人工变量 减去剩余（松弛）变量，加人工变量目 标 函 数 max z min z 加入变量的系数松弛变量 人工变量 不需要处理 令z=-z,求 max z 0-M(2)对目标函数求max的线性规划问题，用单纯形法计算步骤的框图第5节 结束