第2章 对偶理论和灵敏度分析-第5,6节(运筹学-东北大学,钟磊钢).ppt

《第2章 对偶理论和灵敏度分析-第5,6节(运筹学-东北大学,钟磊钢).ppt》由会员分享，可在线阅读，更多相关《第2章 对偶理论和灵敏度分析-第5,6节(运筹学-东北大学,钟磊钢).ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运筹学运筹学（第三版）运筹学教材编写组编清华大学出版社第2章对偶理论和灵敏度分析第5节对偶问题的经济解释影子价格第6节对偶单纯形法钱颂迪制作第2章对偶理论和灵敏度分析第5节对偶问题的经济解释影子价格在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?设B是maxz=CXAXb，X0的最优基，由-Yb=-CBB-1b(2-12)式可知z*=CBB-1b=Y*b。对z求偏导数，得由上式可知，变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。cj23000CBXBbx1x2x3x4x

2、52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由移至，相应的最优解由(4，2)变为(4，2.5)，目标函数z=24+32.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由移至，相应的最优解从(4，2)变为(4.25，1.875)，目标

3、函数z=4.25+31.875=14.125。比 原 来 的 增 加 0.125。原材料B增加1kg时，该约束方程的直线由移至，这时的最优解不变。图2-1yi*的值代表对第i种资源的估价-影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业

4、影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。第6节偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性可以这样考虑：若保持对偶问题的解是基可行解，即cj-CBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。方法如下

5、：设原问题maxz=CXAX=bX0又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为XB=(x1，x2，,xm)当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是(1)对应基变量x1，x2，,xm的检验数是i=ci-zi=ci-CBB-1Pj=0，i=1,2,m(2)对应非基变量xm+1，xn的检验数是j=cj-zj=cj-CBB-1Pj0，j=m+1,n每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从

6、原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤如下：(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量(3)确定换入变量在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止计算。若存在lj0(j=1,2,，n),计算按规则所对应的列的非基变量xk为换入变量，这

7、样才能保持得到的对偶问题解仍为可行解。(4)以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。例6用对偶单纯形法求解min=2x1+3x2+4x3x1+2x2+x332x1-x2+3x34x1，x2，x30解解先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3-x1-2x2-x3+x4 =-3-2x1+x2-3x3 +x5=-4xj0，j=1,2,5例6的初始单纯形表，见表2-6。从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。换出变量的确定：按上述对偶单纯形法计算步骤(2)，即按

8、min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算min(-3,-4)=-4故x5为换出变量。换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止计算。计算故x1为换入变量。换入、换出变量的所在列、行的交叉处“-2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。表2-7表2-8表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。