对偶与灵敏度分析PPT讲稿.ppt

《对偶与灵敏度分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《对偶与灵敏度分析PPT讲稿.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶与灵敏度分析第1页，共45页，编辑于2022年，星期六对偶模型的一般式以例7为例，原问题为（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：原问题（P）对偶问题（D）目标max型 目标min型 有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数 资源向量 资源向量 价格系数 技术系数矩阵 技术系数矩阵的转置第2页，共45页，编辑于2022年，星期六此外，还有一种情形 原问题（P）对偶问题（D）第j个变量为自由变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自由变量例8：写出下面线性规划的对偶规划模型：

2、第3页，共45页，编辑于2022年，星期六例8：写出下面线性规划的对偶规划模型：第4页，共45页，编辑于2022年，星期六二、对偶的性质（P）（D）考虑1.对称性 （P）与（D）互为对偶。证：由（P）、（D）的约束可得几何意义：CXYb第5页，共45页，编辑于2022年，星期六4.对偶定理 若（P）有最优解，则（D）也有最优解，且最优值相同。证：对（P）增加松弛变量Xs，化为设其最优基为B，终表为其检验数为第6页，共45页，编辑于2022年，星期六得证。第7页，共45页，编辑于2022年，星期六问题：(1)由性质4可知，对偶问题最优解的表达式 Y*=？(2)求Y*是否有必要重新求解（D）？CB

3、B-1 不必。可以从原问题（P）的单纯形终表获得。例如，在前面的练习中已知的终表为请指出其对偶问题的最优解和最优值。第8页，共45页，编辑于2022年，星期六5.互补松弛定理第9页，共45页，编辑于2022年，星期六y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0直观上第10页，共45页，编辑于2022年，星期六 6.对偶问题的经济解释（1）对偶最优解的经济解释资源的影子

4、价格（Shadow Price）CBB-1 对偶问题的最优解 买主的最低出价；原问题资源的影子价格 当该资源增加1单 位时引起的总收入的增量卖主的内控价格。例10：例1（煤电油例）的单纯形终表如下：（1）请指出资源煤电油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？第11页，共45页，编辑于2022年，星期六例10：例1（煤电油例）的单纯形终表如下：（1）请指出资源煤、电、油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？解：（1）煤、电、油的影子价格分别是0、1.36、0.52；其经济意义是当煤、电、油分别增加1单位时可使总 收入分别增加0、

5、1.36、0.52。（2）由单纯形终表还可得到：原问题的最优生产计划、最大收入、资源剩余，对偶问题的最低购买价格、最少的购买费用等。第12页，共45页，编辑于2022年，星期六y1y2ym（2）对偶约束的经济解释产品的机会成本(Opportunity Cost)机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源第13页，共45页，编辑于2022年，星期六机会成本利润差额成本（3）对偶松弛变量的经济解释产品的差额成本（Reduced Cost）差额成本=机会成本 利润第14页，共45页，编辑于2022年，星期六 在利润最大化的生产计划中（1）影

6、子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。（4）互补松弛关系的经济解释第15页，共45页，编辑于2022年，星期六三、对偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时,已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的基础上，通过逐步

7、迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。第16页，共45页，编辑于2022年，星期六设原问题为 max z=CX AX=b X0又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为 XB=(x1，x2，,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是 (1)对应基变量x1，x2，,xm的检验数是i=ci CBB-1Pj=0，i=1,2,m (2)对应非基变量xm+1，xn的检验数是

8、j=cj CBB-1Pj0，j=m+1,n第17页，共45页，编辑于2022年，星期六每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。第18页，共45页，编辑于2022年，星期六对偶单纯形法的计算步骤如下：(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量。按min(B-1b)i(B-1b)i0(B-1

9、b)l对应的基变量xi为换出变量 (3)确定换入变量。在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。若存在lj0 (j=1,2,，n),计算 第19页，共45页，编辑于2022年，星期六对偶单纯形法的计算步骤如下：按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4)以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。第20页，共45页，编辑于2022年，星期六例:用对偶单纯形法求解min w=2x1+3x2+4x3x1+2x2+x332x1x2+3x34x1，x2，x30

10、解：解：先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=2x1 3x2 4x3 x1 2x2 x3+x4 =32x1+x2 3x3 +x5=4xj0，j=1,2,5第21页，共45页，编辑于2022年，星期六例6的初始单纯形表，见表。从表看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。第22页，共45页，编辑于2022年，星期六换出变量的确定：换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。按上述对偶单纯形法计算步骤(2)，即按min(B-1b)i

11、(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算min(3,4)=4故x5为换出变量。故x1为换入变量。换入、换出变量的所在列、行的交叉处“2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。第23页，共45页，编辑于2022年，星期六第24页，共45页，编辑于2022年，星期六表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)第25页，共45页，编辑于2022年，星期六对偶单纯形法有以下优点：l(1)初始解可以是非可

12、行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。l(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。l(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第26页，共45页，编辑于2022年，星期六三、灵敏度分析 讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范

13、围内变化时可使原最优解或最优基不变？）我们主要讨论C、b和变量结构变化时对解的影响。对解怎样影响？影响解的-最优性 -可行性第27页，共45页，编辑于2022年，星期六1.b变化时的分析第28页，共45页，编辑于2022年，星期六例11：在例1（煤电油例）中，其单纯形终表如下：（1）电的影子价格是多少？使最优基仍适用的电的变 化范围为何？解：（1）电的影子价格是1.36。第29页，共45页，编辑于2022年，星期六例11：在例1（煤电油例）中，其单纯形终表如下：（2）若有人愿以每度1元的价格向该厂供应25度电，是 否值得接受？解：（2）值得。因25在B的适用范围内（即影子价格适用），且 1.0

14、0-1.360。第30页，共45页，编辑于2022年，星期六2.C变化时的分析第31页，共45页，编辑于2022年，星期六例11：在例1（煤电油例）中，其单纯形终表如下：（3）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格c1是基变量的价格系数。第32页，共45页，编辑于2022年，星期六3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。经济意义：市场价影子价第33页，共45页，编辑于2022年，星期六例11：在例1（煤电油例）中，其单纯形终表如下：（4）若现又考虑一新产品丙，其资源单耗为10，2，5

15、，售价为6.5，问该产品是否可投产？故丙产品可以投产。第34页，共45页，编辑于2022年，星期六首先将线性规划与经济问题联系起来的是 T.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）二人因此而共同分享了1975年的第7届诺贝尔经济学奖。第35页，共45页，编辑于2022年，星期六求解线性规划的计算机软件举例LINDO、EXCELLINDO可以从下面的网址下载：WWW.L LINDO由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。输入例 ：MAX 2X+3Y ST 2)4X+9Y9 3)7X+6Y13 END 可用HELP

16、命令得到帮助。第36页，共45页，编辑于2022年，星期六计算结果说明：REDUCED COST 为使该变量进基，其价格系数至少应 增加的数值；SLACK OR SUPLUS 松弛或剩余变量；DUAL PRICES 影子价格;ALLOWABLE INCREASE 灵敏度分析中可使最优基不 变的系数可增量之上界；ALLOWABLE DECREASE 灵敏度分析中可使最优基不 变的系数可减量之上界；第37页，共45页，编辑于2022年，星期六例例1 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时

17、间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：第38页，共45页，编辑于2022年，星期六1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 2

18、43x1 获利获利 164 x2 原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天第39页，共45页，编辑于2022年，星期六模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDU

19、CED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第40页，共45页，编辑于2022年，星期六结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000

20、 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零

21、的约束为紧约束（有效约束）第41页，共45页，编辑于2022年，星期六结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增量的增量

22、原料增加原料增加1单位单位,利润增长利润增长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！第42页，共45页，编辑于2022年，星期六RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE D

23、ECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标函数最优解不变时目标函数系数允许变化范围系数允许变化范围 DO RANGE(SENSITIVITY

24、)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到 30元元/千克，应否改变生产计划千克，应否改变生产计划 x1系数由系数由24 3=72增增加加为为30 3=90，在，在允允许范围内许范围内 不变！不变！(约束条件不变约束条件不变)第43页，共45页，编辑于2022年，星期六结果解释结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECRE

25、ASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)第44页，共45页，编辑于2022年，星期六使用EXCEL求解线性规划第45页，共45页，编辑于2022年，星期六