《第2章对偶理论和灵敏度分析-第56节运筹学-东北大学钟磊钢课件》由会员分享,可在线阅读,更多相关《第2章对偶理论和灵敏度分析-第56节运筹学-东北大学钟磊钢课件(25页珍藏版)》请在金锄头文库上搜索。
1、,运筹学,(第三版) 运筹学教材编写组 编 清华大学出版社,第2章 对偶理论和灵敏度分析 第5节 对偶问题的经济解释影子价格 第6节 对偶单纯形法 钱颂迪制作,第2章 对偶理论和灵敏度分析,第5节 对偶问题的经济解释 影子价格,在单纯形法的每步迭代中,目标函数取值z=CBB-1b,和检验数CN-CBB-1N中都有乘子Y=CBB-1,那么Y的经济意义是什么?,设B是max z=CXAXb,X0的最优基,由-Yb= -CB B-1b (2-12)式可知 z*=CBB-1b=Y*b 。 对z求偏导数,得,由上式可知,变量yi*的经济意义是在其他条件不变的情况下,单位资源变化所引起的目标函的最优值的变
2、化。,y1*=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),目标函数z=4.25+31.875=14.125。比原来的增加0.125。原材料B增加1kg时,该约束方
3、程的直线由移至,这时的最优解不变。,图2-1,yi*的值代表对第i种资源的估价-影子价格。,这种估价是针对具体工厂的具体产品而存在的一种特殊价格,称它为“影子价格”。在该厂现有资源和现有生产方案的条件下,设备的每小时租费为1.5元,1kg原材料A的出让费为除成本外再附加0.125元,1kg原材料B可按原成本出让,这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异,在完全市场经济的条件下,当某种资源的市场价低于影子价格时,企业应买进该资源用于扩大生产;而当某种资源的市场价高于企业影子价格时,则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。,第6节偶单纯形法,前节讲到原问
4、题与对偶问题的解之间的对应关系时指出:在单纯形表中进行迭代时,在b列中得到的是原问题的基可行解,而在检验数行得到的是对偶问题的基解。 通过逐步迭代,当在检验数行得到对偶问题的解也是基可行解时,根据性质(2)、(3)可知,已得到最优解。即原问题与对偶问题都是最优解。,根据对偶问题的对称性,可以这样考虑:若保持对偶问题的解是基可行解,即cj-CBB-1Pj0,而原问题在非可行解的基础上,通过逐步迭代达到基可行解,这样也得到了最优解。 其优点是原问题的初始解不一定是基可行解,可从非基可行解开始迭代。 方法如下:,设原问题max z=CXAX=bX0,又设B是一个基。 不失一般性,令B=(P1,P2,
5、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+4x3 x1+2x2+x33 2x1-x2+3x34 x1,x2,x30 解 先将此问题化成下列形式,以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3 -x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 xj0,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, 则对偶问题的最
9、优解为 Y*=(y1*,y2*)=(8/5,1/5),从以上求解过程可以看到对偶单纯形法有以下优点:,(1) 初始解可以是非可行解,当检验数都为负数时就可以进行基的变换,这时不需要加入人工变量,因此可以简化计算。 (2) 当变量多于约束条件,对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量,因此对变量较少,而约束条件很多的线性规划问题,可先将它变换成对偶问题,然后用对偶单纯形法求解。 (3) 在灵敏度分析及求解整数规划的割平面法中,有时需要用对偶单纯形法,这样可使问题的处理简化。对偶单纯形法的局限性主要是,对大多数线性规划问题,很难找到一个初始可行基,因而这种方法在求解线性规划问题时很少单独应用。,