05-对偶规划与敏感性分析.pdf

《05-对偶规划与敏感性分析.pdf》由会员分享，可在线阅读，更多相关《05-对偶规划与敏感性分析.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北京大学2010-9-91对偶规划与对偶规划与灵敏度灵敏度分析分析孙晓云孙晓云2010-9-92一、对偶线性规划一、对偶线性规划引例：引例：某工厂在计划期内安排，两种产品，已知生产单位产品所需设备A,B,C的台时和售价如下表所示：产品设备产品产品 资源限量设备A11300设备B21400设备C01250价格50100北京大学2010-9-93线性规划模型线性规划模型（1）X1产品的计划产量X2产品的计划产量（2）max z=50 x1+100 x2s.t.X1+x2 3002x1+x2 400 x2 250 x1,x2 02010-9-94线性规划模型求解线性规划模型求解用用LINDO求解（求

2、解（4-LP1.LTX)LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE VALUE REDUCED COSTX1 50.000000 0.000000X2 250.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 50.0000003)50.000000 0.0000004)0.000000 50.000000最优目标函数最优目标函数生产产量生产产量资源剩余量资源剩余量影子价格影子价格北京大学2010-9-95换个思路出租资源换个思路出租资

3、源如果有另一个工厂要求租用该厂的设备，那么该厂的厂长应该如何来确定合理的租金？设y1、y2、y3分别为设备A、B、C每台时的租金。因为生产一个产品只需要设备A 1台时和设备B 2台时，生产出来后可以卖50元。所以，若出租1台时设备A和2台时设备B，至少不应该少于50元。写出相应的约束为：y1+2y2 50同理，相应产品有约束：y1+y2+y3100当然，资源价格非负，即：y1,y2,y30如果有另一个工厂要求租用该厂的设备，那么该厂的厂长应该如何来确定合理的租金？设y1、y2、y3分别为设备A、B、C每台时的租金。因为生产一个产品只需要设备A 1台时和设备B 2台时，生产出来后可以卖50元。所

4、以，若出租1台时设备A和2台时设备B，至少不应该少于50元。写出相应的约束为：y1+2y2 50同理，相应产品有约束：y1+y2+y3100当然，资源价格非负，即：y1,y2,y302010-9-96目标函数是什么？目标函数是什么？若资源全租出，总的租金是：若资源全租出，总的租金是：300y1+400y2+250y3通常，总的租金越大越好，建模型如下：通常，总的租金越大越好，建模型如下：max f=300y1+400y2+250y3s.t.y1+2y2 50y1+y2+y3100y1,y2,y30北京大学2010-9-97求解求解用用LINDO求解（求解（4-LP2.LTX)，得如下结果：，得

5、如下结果：无界解，为什么？怎么办？无界解，为什么？怎么办？2010-9-98目标函数只能最小化目标函数只能最小化道理：道理：既然约束已经保证了出租不比生产差，总的租金越小越有市场竞争力，建模型如下：既然约束已经保证了出租不比生产差，总的租金越小越有市场竞争力，建模型如下：min 300y1+400y2+250y3s.t.y1+2y2 50y1+y2+y3100y1,y2,y30北京大学2010-9-99求解求解用用LINDO求解（求解（4-LP3.LTX)：LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE

6、VALUE REDUCED COSTY1 50.000000 0.000000Y2 0.000000 50.000000Y3 50.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 -50.0000003)0.000000 -250.000000目标函数值与目标函数值与LP1相同相同租金等于前面的影子价格租金等于前面的影子价格2010-9-910比较LP与DLP结果比较LP与DLP结果原规划与对偶规划的结果有如此密切的关系！因为它们的模型之间有密切关系。原规划与对偶规划的结果有如此密切的关系！因为它们的模型之间有密切关系。LP

7、结果结果OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE VALUE REDUCED COSTX1 50.000000 0.000000X2 250.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICE2)0.000000 50.0000003)50.000000 0.0000004)0.000000 50.000000DLP 结果结果OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE VALUE REDUCED COSTY1 50.000000 0.000000Y2 0.000000

8、 50.000000Y3 50.000000 0.000000ROWSLACK OR SURPLUSDUAL PRICES2)0.000000 -50.0000003)0.000000 -250.000000北京大学2010-9-911DLP模型模型min 300y1+400y2+250y3s.t.y1+2y2 50y1+y2+y3 100y1 0y2 0y30LP模型模型max 50 x1+100 x2s.t.X1+x2 3002x1+x2 400 x2 250 x1 0 x2 0比较LP与DLP模型系数比较LP与DLP模型系数2010-9-912DLP模型模型min 300y1+400y2

9、+250y3s.t.y1+2y2 50y1+y2+y3 100y1 0y2 0y3 0LP模型模型max 50 x1+100 x2s.t.X1+x2 3002x1+x2 400 x2 250 x1 0 x2 0比较比较LP与与DLP模型约束模型约束北京大学2010-9-913线性规划的对偶理论，从另一个角度来思考同一个问题，如上例中，线性规划的对偶理论，从另一个角度来思考同一个问题，如上例中，将一个生产计划问题转化为资源定价问题将一个生产计划问题转化为资源定价问题：没有机会损失时的最低资源出租收入。：没有机会损失时的最低资源出租收入。原问题和对偶问题之间互为对偶。原问题和对偶问题之间互为对偶。

10、线性规划问题转化为对偶规划的一般形式：线性规划问题转化为对偶规划的一般形式：0.0.min maxycyAt sxbAxt sybwcxz1.对偶规划的一般形式1.对偶规划的一般形式2010-9-914原问题：原问题：目标函数求max，约束条件为=目标函数求max，约束条件为=对偶问题：对偶问题：目标函数求min，约束条件为=，变量=目标函数求min，约束条件为=，变量=原问题和对偶问题之间约束条件和变量互换原问题和对偶问题之间约束条件和变量互换如果和标准形式反号，则对偶中对应部分也会反号如果和标准形式反号，则对偶中对应部分也会反号如果约束为对应于对偶中的变量无限制如果约束为对应于对偶中的变量

11、无限制2.求对偶规划一般原则2.求对偶规划一般原则北京大学2010-9-915例：LPmax z=2x1+4x2-3x3s.t.x1 -x2+x3 10 -x1+4x2-3x3=-53x1+2x2-5x3 8 x1 0 x2 0 x3 是自由变量求线性规划的对偶问题举例求线性规划的对偶问题举例例：DLPMin 10y1-5y2+8y3s.t.y1 -y2+3y3 2-y1+4y2+2y3 4y1 -3y2 -5y3 =-3y1 0y2 自由变量y30 2010-9-9163.对偶规划的性质3.对偶规划的性质相互对偶相互对偶-对偶规划的对偶是原规划-对偶规划的对偶是原规划弱对偶定理：如果x,y

12、分别是线性规划与对偶规划可行解，则 CX Yb弱对偶定理：如果x,y 分别是线性规划与对偶规划可行解，则 CX Yb对偶定理对偶定理:X:X*,Y,Y*分别是线性规划与对偶规划最优解的充要条件是 CX分别是线性规划与对偶规划最优解的充要条件是 CX*=Y=Y*b；b；北京大学2010-9-917LP与DLP解的关系LP与DLP解的关系DLPLP最优解无界解无解最优解无界解无解最优解无界解无解最优解无界解无解有可能有可能2010-9-9184.对偶解-影子价格经济解释4.对偶解-影子价格经济解释注意原规划的最优解和对偶规划的最优解对应的目标函数值相等：z*=cx*=y*b，则dz*/db=y*注

13、意原规划的最优解和对偶规划的最优解对应的目标函数值相等：z*=cx*=y*b，则dz*/db=y*对偶规划的解Y的元素分别是z对约束右端项的偏导数。对偶规划的解Y的元素分别是z对约束右端项的偏导数。对偶规划的解对应原规划中资源的对偶规划的解对应原规划中资源的影子价格影子价格即：右端项bi增加一个小的增量bi，目标函数增加yibi即：右端项bi增加一个小的增量bi，目标函数增加yibi相当于资源数量增加一个单位时，最优目标函数值增加的值。相当于资源数量增加一个单位时，最优目标函数值增加的值。北京大学2010-9-919影子价格经济解释（续）影子价格经济解释（续）影子价格的解释要看目标函数是什么;

14、影子价格的解释要看目标函数是什么;影子价格是在系统具有一定数量资源的前提下，在系统达到最优状态时，对资源价格的一种估计。影子价格是在系统具有一定数量资源的前提下，在系统达到最优状态时，对资源价格的一种估计。对于有剩余的资源，影子价格等于零。对于有剩余的资源，影子价格等于零。对于已经用尽的资源，影子价格一般大于零；在临界的情况，也可能资源没有剩余，影子价格也等于零。对于已经用尽的资源，影子价格一般大于零；在临界的情况，也可能资源没有剩余，影子价格也等于零。如果资源的数量有了变化，或者LP其它系数有变化，影子价格也可能变化。所以，影子价格是会动态变化的。如果资源的数量有了变化，或者LP其它系数有变

15、化，影子价格也可能变化。所以，影子价格是会动态变化的。2010-9-920用电子表格解LP结果分析用电子表格解LP结果分析用Excel求解伟恩德公司门窗生产的问题输出的敏感性报告：用Excel求解伟恩德公司门窗生产的问题输出的敏感性报告：北京大学2010-9-921用LINDO解LP结果分析用LINDO解LP结果分析用LINDO求解LP：用LINDO求解LP：LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE VALUE REDUCED COSTX1 50.000000 0.000000X2 250.0000

16、00 0.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 50.0000003)50.000000 0.0000004)0.000000 50.0000002010-9-922二、线性问题灵敏度分析二、线性问题灵敏度分析什么是灵敏度分析什么是灵敏度分析数学模型只是实际问题的一个粗略的抽象，得到的最优解只是针对某一特定情景的数学模型而言的。数学模型只是实际问题的一个粗略的抽象，得到的最优解只是针对某一特定情景的数学模型而言的。管理者关心：如果某些条件发生了一些变化，最优解会不会改变？管理者关心：如果某些条件发生了一些变化，最优解会不会改变？如果最

17、优解相对稳定，就会比较放心地应用最优解对应的决策方案。如果最优解相对稳定，就会比较放心地应用最优解对应的决策方案。如果能通过分析给出在最优解（最优基）不变的前提下，参数变化的范围，决策者也就更能应对客观情况的变化。如果能通过分析给出在最优解（最优基）不变的前提下，参数变化的范围，决策者也就更能应对客观情况的变化。以上所说的分析称为以上所说的分析称为what-if分析what-if分析 或或灵敏度分析（Sensitivity Analysis）灵敏度分析（Sensitivity Analysis）北京大学2010-9-923灵敏度分析直观解释灵敏度分析直观解释2010-9-9241.目标函数系数

18、的变化1.目标函数系数的变化P1P2(0,0)Max 3 P1+5 P2s.t.P1 +4 (Plant 1)2 P2 12(Plant 2)3 P1+2 P2 0(非负约束非负约束)(4,0)(0,6)(2,6)(4,3)(9,0)目标函数系数的变化可能会改变最优解.若最优解没有改变，目标函数最优值也可能改变目标函数系数的变化可能会改变最优解.若最优解没有改变，目标函数最优值也可能改变北京大学2010-9-9252.目标函数系数C1在多大范围内变化最优解不变2.目标函数系数C1在多大范围内变化最优解不变P1P2(0,0)最优解对应的起作用的约束：最优解对应的起作用的约束：2 P2 12(Pl

19、ant 2)3 P1+2 P2 18(Plant 3)(4,0)(0,6)(2,6)(4,3)(9,0)0/2 C1/5 3/20 C1 7.5现在现在C1=3，最多减少，最多减少 3，最多增加，最多增加 4.5，在此范围内最优解不变，在此范围内最优解不变.2010-9-9263.目标函数系数C2在多大范围内变化最优解不变3.目标函数系数C2在多大范围内变化最优解不变P1P2(0,0)最优解对应的起作用的约束：最优解对应的起作用的约束：2 P2 12(Plant 2)3 P1+2 P2 18(Plant 3)(4,0)(0,6)(2,6)(4,3)(9,0)0/2 3/C2 3/22 C2 现

20、在现在C2=5，最多减少，最多减少 3，可任意增加，在此范围内最优解不变，可任意增加，在此范围内最优解不变.北京大学2010-9-9274.约束条件右端项的改变（Right-Hand-Side）4.约束条件右端项的改变（Right-Hand-Side）P1P2(0,0)Max 3 P1+5 P2s.t.P1 +4 (Plant 1)2 P2 12(Plant 2)3 P1+2 P2 0(非负约束非负约束)(4,0)(0,6)(2,6)(9,0)变松变松可行域最优解多余的约束：不变不变无作用约束：变大不变有作用约束：变大改善或无界可行域最优解多余的约束：不变不变无作用约束：变大不变有作用约束：变

21、大改善或无界(4,3)2010-9-928灵敏度分析 EXCEL&Lindo 实现灵敏度分析 EXCEL&Lindo 实现北京大学2010-9-929伟恩德（伟恩德（Wyndor）公司案例研究）公司案例研究伟恩德公司问题电子表格模型及最优解伟恩德公司问题电子表格模型及最优解2010-9-930伟恩德（伟恩德（Wyndor）公司案例研究）公司案例研究伟恩德模型用规划求解，输出灵敏度分析。伟恩德模型用规划求解，输出灵敏度分析。第一部分，保持最优解不变的目标函数系数变化区间第一部分，保持最优解不变的目标函数系数变化区间门的售价：300-300，300+450=0，750门的售价：300-300，30

22、0+450=0，750窗的售价：500-300，500+）=200，）窗的售价：500-300，500+）=200，）在区间边界上，最优解有可能改变；出了边界会改变。在区间边界上，最优解有可能改变；出了边界会改变。两个系数同时变呢？两个系数同时变呢？北京大学2010-9-931多个目标函数系数变化的敏感性分析多个目标函数系数变化的敏感性分析如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？可以试算，但很麻烦！可以试算，但很麻烦！如何在不重新求解模型的条件下，确定如果目标函数的几个系数同

23、时变化，可能造成对最优解的影响？如何在不重新求解模型的条件下，确定如果目标函数的几个系数同时变化，可能造成对最优解的影响？2010-9-932The 100 percent rule 百分之百法则百分之百法则如果目标函数的系数同时变动，计算出如果目标函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量的百分比每一系数变动量占该系数最优域允许变动量的百分比，而后，而后，将各个系数的变动百分比相加将各个系数的变动百分比相加，如果所得的和不超过百分之百，最优解不会改变，如果超过百分之百，则不能确定最优解是否改变。，如果所得的和不超过百分之百，最优解不会改变，如果超过百分之百，则不能确定最

24、优解是否改变。北京大学2010-9-933伟恩德公司案例分析伟恩德公司案例分析当门、窗的单位利润分为改为当门、窗的单位利润分为改为Pd$150，Pw$400Pd$150，Pw$400各自的变化占最大可以变化的 150/300=1/2，100/300=1/3，相加小于1，(D,W)（2，6）还是最优解各自的变化占最大可以变化的 150/300=1/2，100/300=1/3，相加小于1，(D,W)（2，6）还是最优解当门、窗的单位利润分为改为 Pd$600，Pw$800当门、窗的单位利润分为改为 Pd$600，Pw$800各自的变化占最大可以变化的 300/450=2/3，300/=0，相加小于

25、1，（2，6）仍是最优解。各自的变化占最大可以变化的 300/450=2/3，300/=0，相加小于1，（2，6）仍是最优解。当门、窗的单位利润分为改为 Pd$600，Pw$350当门、窗的单位利润分为改为 Pd$600，Pw$350各自的变化占最大可以变化的 300/450=2/3，150/300=1/2，相加大于1，不能判定（2，6）是否最优解。各自的变化占最大可以变化的 300/450=2/3，150/300=1/2，相加大于1，不能判定（2，6）是否最优解。2010-9-934用于确定在保持用于确定在保持最优解不变最优解不变的条件下，目标函数系数的变动范围。的条件下，目标函数系数的变动

26、范围。通过将允许的增加或减少值在各个系数之间分摊，可以计算出每个系数的允许变动值。注意：通过将允许的增加或减少值在各个系数之间分摊，可以计算出每个系数的允许变动值。注意：增加或减少的改变，都按绝对值计算。增加或减少的改变，都按绝对值计算。以现在系数取值为基准，向左(减)或向右(加)，无正负之分，不相互抵消。以现在系数取值为基准，向左(减)或向右(加)，无正负之分，不相互抵消。不是与整个区间比较，是与相同方向的半边比较。不是与整个区间比较，是与相同方向的半边比较。百分之百法则的作用与注意事项百分之百法则的作用与注意事项北京大学2010-9-935右端项的敏感性分析右端项的敏感性分析分析分析函数约

27、束右端项函数约束右端项变动的原因，是往往不能得到模型参数的精确值，只能对其作大略的估计。要分析万一这些估计不准确产生的后果。变动的原因，是往往不能得到模型参数的精确值，只能对其作大略的估计。要分析万一这些估计不准确产生的后果。这些常数往往不是由外界决定的而是这些常数往往不是由外界决定的而是管理层的决策的管理层的决策的。在建模并求解后，管理者想要知道如果改变这些决策是否会提高最终收益。在建模并求解后，管理者想要知道如果改变这些决策是否会提高最终收益影子价格分析就是为管理者提供这方面的信息影子价格分析就是为管理者提供这方面的信息2010-9-936伟恩德公司案例研究伟恩德公司案例研究伟恩德模型用规

28、划求解，输出灵敏度分析，第二部分。伟恩德模型用规划求解，输出灵敏度分析，第二部分。保持最优基不变的约束右端项（资源）的变化区间保持最优基不变的约束右端项（资源）的变化区间车间1：4-2，4+=2，）车间1：4-2，4+=2，）车间2：12-6，12+6=6，18车间2：12-6，12+6=6，18车间3：18-6，18+6=12，24车间3：18-6，18+6=12，24北京大学2010-9-937影子价格影子价格 Shadow Price在线性规划得到最优解的前提下，在线性规划得到最优解的前提下，影子价格影子价格就是约束右端项的增加一个单位，目标函数增加的量。就是约束右端项的增加一个单位，目

29、标函数增加的量。若约束式右端项在敏感性分析得到的区间内变动，若约束式右端项在敏感性分析得到的区间内变动，相应的影子价格不变相应的影子价格不变。如果影子价格是负的，那就表明约束右端值每增加一个单位，最优目标函数值会降低的量。如果影子价格是负的，那就表明约束右端值每增加一个单位，最优目标函数值会降低的量。多个右端项同时变呢？多个右端项同时变呢？百分之百法则还适用吗？百分之百法则还适用吗？2010-9-938同时改变多个约束的右端值同时改变多个约束的右端值，计算出每一右端项的变动量占其允许变动量的百分比，而后，将各个右端项的变动百分比相加，如果所有的百分比之和不超过百分之一百，那么，相应“资源”对应

30、的影子价格不变，计算出每一右端项的变动量占其允许变动量的百分比，而后，将各个右端项的变动百分比相加，如果所有的百分比之和不超过百分之一百，那么，相应“资源”对应的影子价格不变如果所有的百分比之和超过百分之一百，那就无法确定影子价格是否有效。如果所有的百分比之和超过百分之一百，那就无法确定影子价格是否有效。百分之百法则百分之百法则北京大学2010-9-939用LINDO解LP结果分析(1)用LINDO解LP结果分析(1)LP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)27500.00VARIABLE VALUE REDUCED COSTX1

31、 50.000000 0.000000X2 250.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2)0.000000 50.0000003)50.000000 0.0000004)0.000000 50.000000目标函数值目标函数值影子价格影子价格最优解最优解2010-9-940用LINDO解LP结果分析(2)用LINDO解LP结果分析(2)用LINDO求解LP：用LINDO求解LP：RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLE CURRENT A

32、LLOWABLE ALLOWABLECOEF INCREASE DECREASEX1 50.000000 50.000000 50.000000X2 100.000000 INFINITY 50.000000RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE2 300.000000 25.000000 50.0000003 400.000000 INFINITY 50.0000004 250.000000 50.000000 50.000000目标函数系数变化区间目标函数系数变化区间右端项变化区间右

33、端项变化区间北京大学2010-9-941小结小结对偶线性规划的解为影子价格；影子价格对管理者更好的了解资源的价值具有决策支持作用；对偶线性规划的解为影子价格；影子价格对管理者更好的了解资源的价值具有决策支持作用；what-if 分析是在求得基本模型的最优解之后进行的，这些分析可以为管理层决策提供非常有用的信息；what-if 分析是在求得基本模型的最优解之后进行的，这些分析可以为管理层决策提供非常有用的信息；规划求解 或 LINDO 能生成灵敏度报告；规划求解 或 LINDO 能生成灵敏度报告；运用目标函数系数的百分百法则，可方便地检验多个系数的同时变动情况；运用目标函数系数的百分百法则，可方便地检验多个系数的同时变动情况；用约束右端值变动的百分百法则来判断右端项变动的幅度。用约束右端值变动的百分百法则来判断右端项变动的幅度。2010-9-942作业作业P1775.1 写出写出LP模型及其对偶规划，用模型及其对偶规划，用LINDO求解，并做灵敏度分析求解，并做灵敏度分析5.65.8