运筹学第二章对偶问题.ppt

《运筹学第二章对偶问题.ppt》由会员分享，可在线阅读，更多相关《运筹学第二章对偶问题.ppt（51页珍藏版）》请在三一办公上搜索。

1、第二章 对偶问题与灵敏度分析,2.1 对偶问题的提出,例1-1,线性规划模型:,Max z=2x1+3x2 St.x1+2x2 8 4x1 16 4x2 12 x1，x2 0,y1+4y2 2,2y1+4y3 3,=8y1+16y2+12y3,y1，y2，y3 0,对偶问题,y1元/小时,y2元/kg,y3元/kg,资源出租出让价格,Min,例2-1 求解此对偶问题，模型为,y1+4y2 y4+y5=2,2y1+4y3 y6+y7=3,Min=8y1+16y2+12y3+0y4+My5+0y6+My7,y1,y2,y3,y4,y5,y6,y7 0,4,0,2,b,y7,4,1,0,1,3,2,

2、0,1,83M,M,0,M,0,0,1,XB,CB,M,y5,y1 y2 y3 y4 y5 y6 y7,8 16 12 0 M 0 M,M,1,0,0,164M,124M,i,3/4,1,0,2,b,y3,4,1,0,1,3/4,1/2,0,1/4,2-M,M,0,3,M3,0,1/4,XB,CB,M,y5,y1 y2 y3 y4 y5 y6 y7,8 16 12 0 M 0 M,12,1,0,0,16-4M,0,i,1/2,4,4,0,2,b,y7,4,1,0,1,3,2,0,1,83M,M,0,M,0,0,1,XB,CB,M,y5,y1 y2 y3 y4 y5 y6 y7,8 16 12

3、0 M 0 M,M,1,0,0,164M,124M,i,3/4,1,0,1/2,b,y3,1,1/4,0,1/4,3/4,1/2,0,1/4,2,4,M4,3,M3,0,1/4,XB,CB,16,y2,y1 y2 y3 y4 y5 y6 y7,8 16 12 0 M 0 M,12,1/4,0,0,0,0,i,2,3/2,1,0,2,b,y3,4,1,0,1,3/4,1/2,0,1/4,2-M,M,0,3,M3,0,1/4,XB,CB,M,y5,y1 y2 y3 y4 y5 y6 y7,8 16 12 0 M 0 M,12,1,0,0,16-4M,0,i,1/2,4,2,1/2,1/8,b,y1

4、,1,1/4,1/8,0,3/2,1,0,1/2,0,4,M4,2,M2,0,1/2,XB,CB,16,y2,y1 y2 y3 y4 y5 y6 y7,8 16 12 0 M 0 M,8,1/4,1/8,0,0,4,最优解为：,Y=（y1,y2,y3,y4,y6)=（3/2，1/8，0，0，0）,y,14,比较原问题和对偶问题的最优单纯形表，得,2.2 对偶问题的一般形式,Max z=c1 x1+c2 x2+cn xn St.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1,x2,xn 0,对偶

5、问题,Min=b1 y1+b2 y2+bm ym,St.a11 y1+a21 y2+am1 ym c1,a12 y1+a22 y2+am2 ym c2,a1n y1+a2n y2+amn ym cn,y1,y2,ym 0,对于其他形式的对偶问题，可以先转化为上述形式，再求对偶问题,例2-2：求下面线性规划问题的对偶问题,Max z=3x1+4x2+6x3 St.2x1+3x2+6x3 440 6x1 4x2 x3 100 5x1 3x2+x3=200 x1，x2，x3 0,两边乘以“1”,5x1 3x2+x3 2005x1 3x2+x3 200,Max z=3x1+4x2+6x3,St.2x1

6、+3x2+6x3 440,6x1+4x2+x3 100,5x1 3x2+x3 200,5x1+3x2 x3 200,x1，x2，x3 0,对偶,Min w=440y1 100y2+200y4 200y5,2y1 6y2+5y4 5y5 3,3y1+4y2 3y4+3y5 4,6y1+y2+y4 y5 6,y1,y2,y4,y5 0,Min w=440y1 100y2+200（y4 y5）,2y1 6y2+5(y4 y5)3,3y1+4y2+3(y4 y5)4,6y1+y2+(y4 y5)6,y1,y2,y4,y5 0,令 y3=y4 y5,Min w=440y1 100y2+200y3,2y1

7、 6y2+5y3 3,3y1+4y2+3y3 4,6y1+y2+y3 6,y1,y2 0,y3：unr,当原问题的第 i 个约束条件为“=”时，其对偶问题的第 i 个变量没有符号约束,Max z=3x1+4x2+6x3 St.2x1+3x2+6x3 440 6x1 4x2 x3 100 5x1 3x2+x3=200 x1，x2，x3 0,例2-3：求下面线性规划问题的对偶问题,Min w=3x1+9x2+4x3 St.x1+2x2+3x3=180 2x1 3x2+x3 60 5x1+3x2 240 x1，x2 0，x3:unr,两边乘以“1”,Min w=3x1+9x2+4x3,St.x1+2

8、x2+3x3=180,2x1+3x2 x3 60,5x1+3x2 240,x1，x2 0，x3:unr,对偶,Max z=180y1 60y2+240y3,y1 2y2+5y3 3,2y1+3y2+3y3 9,3y1 y2=4,y1：unr,y2,y3 0,2.3 对偶问题的经济解释影子价格,z*=y*=y1*b1+y2*b2+ym*bm,yi*的经济意义：,在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。,例1-1的最终单纯形表中：,y1*=1.5，y2*=0.125，y3*=0,以下用图来说明：,对于对称形式的（P）问题，如果有最优解，则在其最优单纯形表中，松弛变量 的

9、检验数 的负值即为（D）问题的一个最优解.,例1-1的模型为：,Max z=2x1+3x2 St.x1+2x2 8 4x1 16 4x2 12 x1，x2 0,8,4,x1,x2,0,4,3,9,8,（4，2）,（4，2.5）,z=24+32=14,z=24+32.5=15.5,17,4.25,（4.25，1.875）,z=24.25+31.875=14.125,16,13,3.25,z=24+32=14,y1*=1.5，y2*=0.125，y3*=0,几何解释,2.4 灵敏度分析,1、价值系数的变化范围的确定1）非基变量的系数2）基变量的系数2、右手项（资源总量）的变化范围的确定3、技术系数

10、的变化对最优解的影响1）基变量系数变化了2）非基变量系数的变化范围,2.4 灵敏度分析,2.4.1 目标函数系数的变化,（1）当目标函数的斜率在直线B的斜率和直线A的斜率之间变化时，顶点Q2 仍是最优解；,（2）当目标函数的直线反时针旋转，其斜率等于直线A的斜率时，直线Q2 Q3 上的任一点都是最优解。,（3）当目标函数的直线继续反时针旋转，介于直线A和直线C的斜率时，则顶点 Q3 是最优解。,（4）当目标函数的直线继续反时针旋转，其斜率等于直线C的斜率时，直线Q3 Q4 上的任一点都是最优解。,（5）当目标函数的直线继续反时针旋转，则顶点 Q4 是最优解。,（6）当目标函数的直线顺时针旋转，

11、其斜率等于直线B的斜率时，直线Q1 Q2 上的任一点都是最优解。,（7）当目标函数的直线继续顺时针旋转，则顶点 Q1 是最优解。,1.用图解法,直线A的方程：,x1+2x2=8,直线B的方程：,x1=4,即,x2=0.5x1+4,0 x2=x1+4,直线A的斜率：0.5,直线B的斜率：,目标函数,Z=c1 x1+c2 x2,即,目标函数斜率为：,当,0.5,顶点Q2 仍为最优解,（1）计算c1 在什么范围变化，Q2 仍为最优解,假设c2=3不变,由,0.5,可得,1.5 c1,（2）计算c2 在什么范围变化，Q2 仍为最优解,假设c1=2不变,由,0.5,可得,0c2 4,（3）当c1、c2

12、都变化时，只要c1、c2 满足,0.5,Q2 仍为最优解,C的变化只影响检验数（对偶问题的解），不影响原问题的基本解,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)14.00000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 1.500000 3)0.000000 0.125000 4)4.000000 0.000000 NO.ITERATIONS=2

13、 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 INFINITY 0.500000 X2 3.000000 1.000000 3.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 8.000000 2.000000 4.000000 3 16.000000

14、16.000000 8.000000 4 12.000000 INFINITY 4.000000,b1 的变化范围 b2 的变化范围b3 的变化范围,c1 的变化范围 c2 的变化范围,剩余变量和松弛变量的取值,LP问题的解,目标函数的值,用软件分析,单纯形法在两次迭代（旋转）后得到最优解,迭代（旋转）次数,影子价格（对偶问题的解）,灵敏度分析,减少的代价,目标不变下要素的变化范围,目标系数的变化范围,约束总量的变化范围,2.用软件分析,2.4.2 约束条件右边常数项的变化,这是分析当约束条件右边常数项bi 在什么范围变化，对偶问题的最优解（对偶价格）保持不变,2.5 影子价格和 灵敏度分析的

15、应用,例2-4 长城化工公司有两个工厂F1 和F2。F1 厂生产两种产品：D1 和D2，F2 厂也生产两种产品：D3 和D4。这4种产品的生产都需要使用原料A和B。根据合同，公司每日可获得原料A和B分别为42公斤和30公斤。公司经理提出了如下的原料分配计划：,公司的OR分析人员根据经理提出的资源分配方案及各工厂提供的技术系数、利润系数，为两厂分别建立了数学模型，并求出了模型的最优解：,F1 厂的数学模型为：,最优解如下表所示：,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)31.42857 VARIABLE VALUE REDUCE

16、D COST X1 1.428571 0.000000 X2 2.142857 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.428571 3)0.000000 1.857143 NO.ITERATIONS=0 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 10.000000 6.000000 5.200000 X2 8.0000

17、00 8.666666 3.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30.000000 20.000000 14.999999 3 10.000000 10.000000 4.000000,c1 的变化范围 c2 的变化范围,剩余变量和松弛变量的取值,LP问题的解（对应变量的取值）,目标函数的值,影子价格（对偶问题的解）,b1 的变化范围 b2 的变化范围,单纯形法在两次迭代（旋转）后得到最优解,F2 厂的数学模型为：,最优解如下表所示：,LP OPTIMUM FO

18、UND AT STEP 0 OBJECTIVE FUNCTION VALUE 1)52.00000 VARIABLE VALUE REDUCED COST X1 2.000000 0.000000 X2 5.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.500000 3)0.000000 0.500000 NO.ITERATIONS=0 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE AL

19、LOWABLE COEF INCREASE DECREASE X1 6.000000 14.000000 2.000000 X2 8.000000 4.000000 5.600000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 12.000000 8.000000 8.000000 3 20.000000 40.000000 8.000000,b1 的变化范围 b2 的变化范围,c1 的变化范围 c2 的变化范围,剩余变量和松弛变量的取值,LP问题的解,目标函数的值,影子价格,（L1

20、）、（L2）中b1（原料A的总量）、b2（原料B的总量）分别在下面的范围内变化时，对偶问题的最优解（即原料A、原料B的影子价格）保持不变。,两种原料在两个工厂的影子价格,可见,A在F1 的影子价格小于在F2 的影子价格,B在F1 的影子价格大于在F2 的影子价格,b的变化只影响原问题的基本解，不影响检验数（对偶问题的解）。,约束条件中资源数量bi的变化分析,设某个资源数量变化为，并假设原问题的其它系数不变，则使最终单纯形表中原问题的解相应地变化为：其中，即 若要求最优基B不变，则必须 0，因而可求出 br 的变化范围。（i=1,2,m）当b改变为以后，若解的可行性不变，则目标函数变为,公司的O

21、R人员建议：将F1 厂的原料A调一部分给F2 厂；将F2 厂的原料B调一部分给F1 厂。,对原料A而言，F1 厂最多可调出15公斤；F2 厂最多可增加8公斤；对原料B而言，F2 厂最多可调出8公斤；F1 厂最多可增加10公斤。,由上表可知：,决策：,从F1 厂调出8公斤原料A给F2 厂；从F2 厂调出8公斤原料B给F1 厂。,公司利润增加：,公司经理非常高兴地接受了OR工作者的建议，调整了两种资源的分配计划，没有增加一分钱，却使公司的经济效益提高了,实例*某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示:大轿车 载重汽车 可用量钢材（吨）2 2 1600工时(小时)5 2

22、.5 2500座椅 400（辆）获利(千元/辆)4 3问应如何组织生产才能使工厂活力最大？,此问题求解后的最终单纯形式表如下：,在最终单纯形式表中若 的系数变化了 则,为保持最优解不变，应当有,因此得,也就是,即,在最终单纯形式表中若b1的值变化了 那么由下表,实例*中如果b1变化了，则,若要保持最优基不变，则上述解仍可行,因此得,或者,对偶单纯形法的计算步骤：,（1）根据线性规划问题，列出初始单纯形表，检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b 列的数字时，至少还有一个负分量，检验数保持非正，则转（2）。,（2）确定离基变量,按 min(B-1b)i(B-

23、1b)i 0=(B-1b)l 对应的基变量 xl 为离基变量。,（3）确定进基变量,在单纯形表中检查xl 所在行的各系数 alj(j=1,2,n)，若所有 alj 0，则无可行解，停止计算；若存在 alj 0(j=1,2,n)，计算,按 规则所对应的列的非基变量xk 为进基变量,（4）以 alk 为主元，按单纯形法在表中进行迭代运算，得到新的计算表。,重复（1）（4），直至求出最优解或确定无可行解。,2.6 对偶单纯形法,其中 cj zj,j,其中 cj zj,j,k,alk,例2-4 用对偶单纯形法求解,Min=2x1+3x2+4x3 St.x1+2x2+x3 3 2x1 x2+3x3 4

24、x1,x2,x3 0,解：,化为等号约束：,Max z=2x1 3x2 4x3 St.x1 2x2 x3+x4=3 2x1+x2 3x3+x5=4 x1,x2,x3,x4,x5 0,2,1,0,1,2,0,0,3,4,1,3,b,x5,0,1,4,XB,CB,0,0,x4,x1 x2 x3 x4 x5,2 3 4 0 0,1,3,2,初始单纯形表为：,x5 离基,x1 进基,1/2,0,1/2,0,0,1,4,1,1/2,1,b,x1,1/2,0,2,XB,CB,0,2,x4,x1 x2 x3 x4 x5,2 3 4 0 0,1,3/2,5/2,x4 离基,x2 进基,1,0,1/5,2/5,

25、0,8/5,1/5,0,3/5,1/5,2/5,b,x1,1/5,0,11/5,XB,CB,3,2,x2,x1 x2 x3 x4 x5,2 3 4 0 0,2/5,7/5,1,1,由于b 列中的数字全为非负，检验数全为非正，故得最优解为,X*=（11/5，2/5，0，0，0）T,对偶单纯形法的理论依据及说明：（详见教材p53),对偶单纯形法不能理解为是求解对偶问题，原始单纯形法适用于一切线性规划问题，但对特殊问题用对偶单纯形法更好求解，主要应用于下面问题：,s.t.Axb,x0,化为标准形式,s.t.,0,s.t.,0,某工厂制造三种产品A、B和C，需要两种资源（原材料和设备）。每生产一件各种

26、产品所需要的原材料和设备时数及每件产品的单位利润如下表所示：产品 A B C 资源总量 资源耗用 原材料 6 3 5 45 设备时数 3 4 5 30 单位利润 3 1 5设x1,x2,x3 分别是产品A、B、C的产量，经求解得最优单纯形表如下：,综合练习1,试求解：（1）最优生产计划中A、B、C产品的产量；（2）最优生产计划中原材料和设备这两种资源实际耗用多少？剩余多少？（3）最优生产计划中，原材料和设备这两种资源哪种资源每增加一个单位对利润的贡献大？为什么？（4）若该厂欲将设备出让或出租，应如何定价才能保证出让和出租所得的收益不低于生产产品所得的收益，而又使得受让方所支付的租金最少？（5）

27、此问题是否有多个最优生产计划？若有多个，请再给出一个最优生产计划。,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1)30.00000 VARIABLE VALUE REDUCED COST X1 0.000000 0.000000 X2 0.000000 3.000000 X3 6.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)15.000000 0.000000 3)0.000000 1.000000 NO.ITERATIONS=1 RANGES IN WHICH THE BA

28、SIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 3.000000 0.000000 INFINITY X2 1.000000 3.000000 INFINITY X3 5.000000 INFINITY 0.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 45.000000 INFINITY 15.000000 3 3

29、0.000000 15.000000 30.000000,解：（1）最优生产计划中A、B、C产品的产量x1,x2,x3分别为 0,0,6；（2）最优生产计划中原材料和设备这两种资源实际耗用30,30,剩余15,0.（3）最优生产计划中，原材料和设备这两种资源中设备资源每增加一个单位对利润的贡献大？因为设备的影子价格为1大于原材料的影子价格0？（4）若该厂欲将设备出让或出租，应将原材料按进价出让、设备按1元/小时出租所得的收益不低于生产产品所得的收益，而又使得受让方所支付的租金最少。（5）此问题有多个最优生产计划，可求出另一个最优生产计划中A、B、C产品的产量x1,x2,x3分别为 5,0,3；

30、目标函数的值为30。设X1=(0,0,6)T，X2=(5,0,3)T，则 所有的解为：XX1(1-)X2 其中 0 1,某工厂制造二种产品A和B，需要两种资源（原材料和设备）。每生产一件各种产品所需要的原材料和设备时数及每件产品的单位利润如下表所示：产品 A B 资源总量资源耗用 原材料 3 4 9 设备时数 5 2 8 单位利润 10 51)列出该问题的数学模型并分别用图解法和单纯形法求解，并指出单纯形法迭代中每一基本可行解与图解法可行域中哪一极点相互对应?2)若设目标函数为：z=c1x1+c2x2则c1与c2满足什么条件时能使该LP问题有多重最优解?3)最优生产计划中，原材料和设备这两种资

31、源哪种资源每增加一个单位对利润的贡献大？为什么？4)求参数b1,c1的影响范围。5)若要求生产的产品必须是整套的，试用分枝定界法求该整数规划的最优解。,综合练习2,某工厂用甲、乙、丙三种设备生产A、B、C三种产品，有关的技术经济数据如下表所示：,据此，可安排最优生产计划，使得总利润达到最大。设使总利润达到最大的线性规划模型的最优单纯形表如下：,其中，x1,x2,x3 分别为三种产品的产量，x4,x5,x6 分别为三个约束条件的松弛变量。（1）如何安排生产使总利润达到最大？写出此问题的线性规划模型；（2）指出最优生产计划中A、B、C产品的产量；（3）最优生产计划中设备甲、乙、丙的实际耗用机时及剩

32、余机时为多少？（4）最优生产计划中，甲、乙、丙三种设备哪种设备每增加1机时数对总利润的贡献最大？为什么？（5）若该厂欲将甲、乙、丙三种设备出租，应如何定价才能保证出租设备所得的收益不低于生产产品所得的收益，又使得受让方所支付的租金最少？,综合练习3,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)35000.00 VARIABLE VALUE REDUCED COST X1 2000.000000 0.000000 X2 1000.000000 0.000000 X3 0.000000 6.666667 ROW SLACK OR SU

33、RPLUS DUAL PRICES 2)1000.000000 0.000000 3)0.000000 1.666667 4)0.000000 5.000000 NO.ITERATIONS=2 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 10.000000 5.000000 2.500000 X2 15.000000 5.000000 4.000000 X3 5.000000 6.66666

34、7 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 6000.000000 INFINITY 1000.000000 3 9000.000000 1000.000000 3000.000000 4 4000.000000 2000.000000 1000.000000,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)35000.00 VARIABLE VALUE REDUCED COST Y1 0.000000

35、 1000.000000 Y2 1.666667 0.000000 Y3 5.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000-2000.000000 3)0.000000-1000.000000 4)6.666667 0.000000 NO.ITERATIONS=2 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE Y1 6000.000000 INFINITY 1000.000000 Y2 9000.000000 1000.000000 3000.000000 Y3 4000.000000 2000.000000 1000.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 10.000000 5.000000 2.500000 3 15.000000 5.000000 4.000000 4 5.000000 6.666667 INFINITY,