运筹学基础-对偶线性规划(2)[全文].doc

《运筹学基础-对偶线性规划(2)[全文].doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、§23>.3对偶单纯形方法原冋题是：原问题的标准型是：minZ=15yl+24y2+5y36y2+y3225yl+2y2+y3yi,y2,y3Momaxw'=・15yl・24y2・5y3+0y4+Oy56y2+y3-y4=25yl+2y2+y3-y5=1yl,y2,y3,y4,y520利用单纯形法：maxw'=-15yl-24y2-5y3+0y4+0y5-My6-My76y2+y3-y4+y6=25yl+2y2+y3-y5+y7=1yl,y2,y3,y4,y5,y6,y720一、用对偶单纯

2、形方法解线性规划对偶单纯形方法是使用对偶原理求解原问题解的一种方法，而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应，原已有的单纯形方法称原始单纯形方法。用对偶单纯形方法解下述线性规划问题原问题是：原问题的标准型是：minZ=15yl+24y2+5y36y2+y3三25yl+2y2+y3Mlyi/y2,y32omaxw'=-15yl-24y2-5y3+0y4+Oy56y2+y3-y4=25yl+2y2+y3-y5=1yl,y2,y3,y4zy5三0maxwz=-15yl-24y2-5y3+

3、0y4+Oy5-6y2-y3+y4=-2-5yl-2y2-y3+y5=-1yl,y2,y3,y4,y5M0对偶单纯形方法检验数??jbXBCB比值Cjy5y4V3y2yioo-5-24-15-1-60-210-1-2-5-1Y5V40000-5-24-150检验数??j0-1/610W1-2/3-5y5Y20-240-4-10-158maxw'=-15yl-24y2-5y3+0y4+0y5-6y2-y3+y4=-2-5yl-2y2-y3+y5=-1yl,y2,y3,y4,y520检验数??j-14

4、01341/4■羽1/210V3Y2-5-24■羽00-15/2Y7/2最优解:YJ(0,lAV2O0)T,maxw*=-1^254121.53MinZ=1^2应用对偶单纯形方法之矩阵法maxw'二-15yl-24y2-5y3+0y4+0y5-6y2・y3+y4=-2-5yl-2y2-y3+y5=-1yl,y2,y3,y4,y52000-5-24-15・W，-11-1-2-50-20-1-60000180-10-15-W,1■羽0-50血0"6100-4•X/6Y7/2■羽00-15/2・W，1/

5、2•羽1015/201A01-S/40•m最优解:Y*二(O,1AV2,0,0)T,max*=-17/2MinZ=17/2两种方法的主要区别在于：而对偶单纯形方法在整个迭代过程屮，则是始终保持对偶问题的可行性即亦即，，也就是全部检验数W0,最后达到全部右边项所有负分量逐步变为全部右边项$0,即满足原问题的可行性时为止。所以，对偶单纯形方法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。原始单纯形方法在整个迭代过程屮，始终是保持原问题的可行性，最后达到检验数即即maxZ取得最优值时为止

6、。-2560-24-1400・Z16・1/1001012・彷3/101相半于：直到对偶问题的解可行为止相当于：即直到原问题的解可行为止用对偶单纯形方法解下述线性规划问题原问题是：原问题的标准型是：minZ=2xl+3x2+4x3xl+2x2+x3三32x1-x2+3x3M4xl,x2,x320maxZ'=-2xl-3x2-4x3+0x4+0x5xl+2x2+x3・x4=32x1-x2+3x3-x5=4xl,x2?x3,x4,x5$0maxw'二-2xl-3x2-4x3+0x4+0x5-xl-2x2

7、-x3+x4=-3-2x1+x2-3x3+x5=-4xl,x2?x3,x4,x5三0应用对偶单纯形方法之矩阵法00-4-3-2・W，-410-30-1-2-100014-1-1-402-1/210-1■眾1/2-^2028/5-VS•笳00・W，11/5•羽010羽100-^5必最优解:Y—(1V5,羽,OQO)T,Maxw'=-28/5maxw'二-2xl-3x2-4x3+0x4+0x5-xl-2x2-x3+x4=-3・2xl+x2-3x3+x5=・4xl,x2,x3,x4,x5$0MinZ*二

8、2&5小结：对偶单纯形方法的解题过程一般分为四步（1）写出与已有的初始基B对应的初始单纯形表。根据模型的标准型,若右边项的数字都为非负，且检验数都为非正，则已得到最优解，计算结束；否则，若右边项屮至少有一个负分量，且检验数也仍然非正，则进行如下计算。（2）确定出基变量。若有：则以对应的变量xr为出基变量。（3）确定入基变量。在单纯形表小观察xr所在行的各系数arj,若所有的arj^O,则无可行解，停止计算；否则若存在：,则以xk为入基变量。（4）以ark为主元按原始单纯形方法的迭代