1、7:00第三第三 讲讲 线性规划：灵敏度分析与对偶线性规划：灵敏度分析与对偶李勇建 博士主要内容线性规划的对偶问题线性规划的灵敏度分析问题7:007:00线性规划的对偶问题对偶问题的来源对偶问题的应用和经济解释对偶问题的转化0,021xx7:00原问题 2110050maxxxz约束：30021 xx400221 xx2502x对偶问题对偶问题最优解：x1=50,x2=250；Z*=275007:00如果把三种资源分别以价格 出租或买出，那么出让相对于生产一单位第 j 种产品的资源消耗的价值应不低于第 j 种产品的单位利润价值因此有但是买方会把价格压到最低：321,yyy0,100502321
2、32121yyyyyyyy321250400300min yyyfy1：y2：y3：30021 xx400221 xx2502x2110050maxxxz7:00对偶问题对偶问题321250400300fmin yyy0,10050232132121yyyyyyyy决策变量：yi 收买该公司一单位 i 种资源时付给的价格目标函数：约束：50,0,50321yyy*27500minzf此极小问题称为原问题的对偶问题，解是分别称为原料1，2，3的影子价格或对偶价格.7:00y1,y2,y37:00举例举例原问题Max 50 x1+30 x2S.t.4x1+3x21202x1+x250 x1,x20
3、对偶问题Min 120y1+50y2S.t.4y1+2y2503y1+y2 30y1,y207:00对偶规划的应用对偶规划的应用一般来说，线性规划问题是确定资源的最优分配方案；对偶问题则是确定对资源的恰当估价，以确定资源的最有效利用；可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏；对于一些紧缺资源，可以借助于影子价格机制规定上交的利润额，控制一些经济效益低的公司自觉地节约使用紧缺资源。影子价值的内涵影子价值的内涵影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。对资源i总存量的评估：or 对资源i当前分配
4、量的评估：or 第一，影子利润说明增加哪种资源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租/转让的基价第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺资源定价的决策方案资源定价的决策方案例：例：某厂生产甲乙产品某厂生产甲乙产品，（，（1 1）如何安排每周的利润为最大）如何安排每周的利润为最大?（2 2）如果企业可以不生产，那资源出让如何定价？）如果企业可以不生产，那资源出让如何定价？甲甲乙乙资源成本资源成
5、本资源拥有量资源拥有量原材料原材料 (kg)(kg)设备设备 (工时工时)电力电力 (度度)9 94 43 34 45 51010202050501 1360360200200300300销售价格销售价格(元元)3903903523520,3001032005436049s.t.127max2121212121xxxxxxxxxxZ*T(20,24,84,0,0)X 1 1、最优生产决策、最优生产决策资源定价的决策方案资源定价的决策方案2 2、资源获利决策、资源获利决策如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料
6、、设备工时、电量资源全部出售给外单位，这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。或者做代加工，则应如何确定这三种资源的价格。123123123123min3602003009437s.t.451012,0wyyyyyyyyyy yy1*0y 2*1.36y 3*0.52y*428Z 45*0,0yy设原材料的单位出让获利为设原材料的单位出让获利为y1，设备工时的单位出让获利为，设备工时的单位出让获利为y2，电量的单位出让获利为电量的单位出让获利为y3。出让决策的线性规划模型：出让决策的线性规划模型：7:00阅读和自学阅读和自学：参考书参
7、考书 P60-61，第，第3.3.4节节7:00想一想想一想产品的机会成本是什么:表示减少一件产品 j 所节省的资源可以增加的利润.产品的差额成本是什么:j7:00如果则用这些资源来生产这种产品更为有利可图.如果表明已经在其他地方以更为有利可图的方式使用这些资源，没有必要生产产品j.其经济解释是:在利润最大化的生产计划中(1)边际利润大于0的资源没有剩余;(2)有剩余的资源边际利润等于0;(3)安排生产的产品机会成本小于等于利润;(4)机会成本大于利润的产品不安排生产.对偶问题的经济解释对偶问题的经济解释7:00对偶的一般形式对偶的一般形式7:007:00例1：写出下面线性规划的对偶规划0,0
8、677122167632.3min4321432143132131xxxxxxxxxxxxxxt sxxS7:001，建立对偶表原问题（求极小）1 0 3 0右边2 3 6 016 0 2 27 7 6 1710对偶问题（求极大）710右边1 0 3 07:00原问题（求极小）1 0 3 0右边2 3 6 016 0 2 27 7 6 1710对偶问题（求极大）710右边1 0 3 00,02362607317162.7max321323213132121yyyyyyyyyyyyytsyyTy1y2y32，写出对偶规划7:00阅读和自学：阅读和自学：参考书参考书 P56-59，第，第3.3.1
9、和和3.3.2节节7:00线性规划的敏感性分析线性规划的敏感性分析什么是敏感性分析什么是敏感性分析 伟恩德公司案例研究伟恩德公司案例研究目标函数系数分析目标函数系数分析右端项的影子价格分析右端项的影子价格分析7:00原材料原材料6 大块大块8 小块小块产品产品 桌桌 椅椅 Profit=$20/TableProfit=$15/Chair自己动手自己动手7:00如果桌子的利润是$35，最优解会怎样变化呢？如果又有一个额外的大块，会增加总利润吗？如果桌子和椅子构成改变，最优解会变化吗？如果还有一些原材料，你愿意以多大的代价购买呢？拼装玩具生产拼装玩具生产自己动手自己动手你怎么来分析这些问题？你怎么
10、来分析这些问题？想想看！想想看！7:00什么是敏感性分析什么是敏感性分析 定义：建立数学模型和求得最优解后，研究线性规划的一个或多个参定义：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）数（系数）ci,aij,bj 变化时，对最优解产生的影响变化时，对最优解产生的影响数学模型只是实际问题的一个粗略的抽象数学模型只是实际问题的一个粗略的抽象最优解一般只是针对某一特定的数学模型最优解一般只是针对某一特定的数学模型管理者要对未来做各种假设，在这些假设下，测试可能产生的结果，管理者要对未来做各种假设，在这些假设下，测试可能产生的结果，通过对各种结果深入分析来指导决策通过对各种结果深入
11、分析来指导决策通常，在取得最初版本模型的最优解之后，进行分析才能取得对问题通常，在取得最初版本模型的最优解之后，进行分析才能取得对问题深入的认识深入的认识这种分析称为这种分析称为what-if分析分析或敏感性分析（或敏感性分析（Sensitivity Analysis）意义：意义：what-if分析可以表明改变这些决策对结果的影响，从而有效分析可以表明改变这些决策对结果的影响，从而有效指导管理者作出最终的决策指导管理者作出最终的决策7:00伟恩德公司案例研究伟恩德公司案例研究实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究修正的伟恩德例子，门的单位利润修正的伟恩德例子，门的单位利润
12、PD=$300降到降到PD=$200，而最优解不变，而最优解不变 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究修正的伟恩德例子，门的单位利润修正的伟恩德例子，门的单位利润PD=$300增加到增加到PD=$500，而最优解不变，而最优解不变 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究修正的伟恩德例子，门的单位利润从修正的伟恩德例子，门的单位利润从PD=$300增加增加到到PD=$1000，最优解改变，最优解改变 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究在伟恩德的例子中系统改变门的单位利润得到数据表在伟恩德的例子中系统改变门的单位利润得到数据表
13、 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究其中最后三栏表示了门窗单位利润的最优域。其中最后三栏表示了门窗单位利润的最优域。实际举例实际举例RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 300.000000 450.000000 300.000000 X2 500.000000 INFINITY 300.000000 7:00最优域敏感性分析最优域敏感性分析如何在不重新求解模
14、型的条件下，确定如果目标函如何在不重新求解模型的条件下，确定如果目标函数的几个系数同时变化，可能造成对最优解的影响数的几个系数同时变化，可能造成对最优解的影响 如果伟恩德公司两种新产品单位利润的估计值都是如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？不精确的，将会对结果产生怎样的影响？7:00伟恩德公司案例研究伟恩德公司案例研究修正的伟恩德问题模型，其中门，窗的单位利润分别修正的伟恩德问题模型，其中门，窗的单位利润分别被改为被改为PD=$450,PW$400，但是最优解不变，但是最优解不变 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究修正的伟恩
15、德问题模型，其中门，窗的单位利润分别修正的伟恩德问题模型，其中门，窗的单位利润分别被改为被改为PD=$600,PW$300，从而最优解改变，从而最优解改变 实际举例实际举例7:00伟恩德公司案例研究伟恩德公司案例研究伟恩德例子中系统改变门，窗单位利润得到的数据表伟恩德例子中系统改变门，窗单位利润得到的数据表 实际举例实际举例7:00百分之百法则百分之百法则目标函数系数同时变动的百分之百法则目标函数系数同时变动的百分之百法则(The 100 percent rule for simultaneous changes in objective function coefficients)：如果目标
16、函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。7:00可用于确定在保持最优解不变的条件下，目标可用于确定在保持最优解不变的条件下，目标函函 数系数的变动范围数系数的变动范围 百分百法则通过将允许的增加或减少值在各个百分百法则通过将允许的增加或减少值在各个系数之间分摊，从而可以直接显示出每个系数系数之间分摊，从而可以直接显示出每个系数的允许变动值的允许变动值 线性规划研究结束以后，如果将来条件变线性规划研究结束以后，如果将来条件变 化化，致使目
17、标函数中一部分或所有系数都发生变，致使目标函数中一部分或所有系数都发生变动，百分百法则可以直接表明最初最优解是否动，百分百法则可以直接表明最初最优解是否保持不变保持不变 百分之百法则的作用百分之百法则的作用7:00右端项的影子价格分析右端项的影子价格分析分析函数约束右端值函数约束右端值变动的原因也是不能得到模型的参数的精确值，只能对其作大略的估计。因此要知道万一这些估计不准确产生的后果 更主要的理由是因为这些常数往往不是由外界决定的而是管理层的政策决策管理层的政策决策。在建模并求解后，管理者想要知道如果改变这些决策是否会提高最终收益影子价格分析就是为管理者提供这方面的信息影子价格分析就是为管理
18、者提供这方面的信息 7:00影子价格影子价格在给定线性规划模型的最优解和目标函数相应值的在给定线性规划模型的最优解和目标函数相应值的条件下，影子价格（条件下，影子价格（shadow price）就是约束常数）就是约束常数增加微小的量，使得目标函数值增加的量。增加微小的量，使得目标函数值增加的量。7:00Max z=20A+30BS.t.工序1:2A+B40工序2:A+2B40工序3:A+B25非负约束：A0,B0最优解：A=10,B=15,Z=650影子价格：工序1的为0；工序2的为10；工序3的为10实际举例实际举例7:00Max z=20A+30BS.t.工序1:2A+B 4041工序2:
19、A+2B40工序3:A+B25非负约束：A0,B0最优解：A=15,B=10,Z=650没有变化，工序1的影子价格是07:00Max z=20A+30BS.t.工序1:2A+B40工序2:A+2B4041工序3:A+B25非负约束：A0,B0最优解：A=9,B=16,Z=650 660增加了10元，工序2的影子价格是10但是若增加太多，例如增加100小时，该约束不再是限制约束了，增加的价值反而不是1000元。也就是说存在上限。7:00Max z=20A+30BS.t.工序1:2A+B40工序2:A+2B40工序3:A+B2526非负约束：A0,B0最优解：A=12,B=14,Z=650 660
20、增加了10元，工序3的影子价格是10同工序2，只有在生产能力有较小的变动时适用7:00同时改变右端项同时改变右端项如果，多个约束右端值同时变动，那么管理层又如果，多个约束右端值同时变动，那么管理层又该如何来评估可能造成的影响呢？该如何来评估可能造成的影响呢？这种问题很常见！这种问题很常见！7:00同时改变几个或所有函数约束的约束右端值同时改变几个或所有函数约束的约束右端值，如果这些变动的幅度不大，那么可以用影子价格预测变动产生的影响。如果所有的百分比之和不超过百分之一百，那么，影子价格还是有效的，如果所有的百分比之和超过百分之一百，那就无法确定影子价格是否有效 The 100 percent
21、rule百分之百法则百分之百法则7:00修正的伟恩德问题，其中一个小时的工作时间从工厂修正的伟恩德问题，其中一个小时的工作时间从工厂3移到工厂移到工厂2，模型的求解。，模型的求解。实际举例实际举例Wyndor Case Study 伟恩德公司案例研究伟恩德公司案例研究7:00不断将工厂不断将工厂3的工作时间转移到工厂的工作时间转移到工厂2，从而生成数据表，从而生成数据表 实际举例实际举例Wyndor Case Study 伟恩德公司案例研究伟恩德公司案例研究7:00百分之百法则设参数a变化的最优范围的上下限分别为a,a，若参数a变化增加到a*，则可行增加的百分比(a*-a)/(a-a)；若参数
22、a变化减少到a*，则可行减少的百分比(a-a*)/(a-a)。注意：不是(a-a*)/(a”-a)。对所有变化的目标函数系数，求其占可行增加和可行减少的百分比的绝对值之和。若绝对值之和不超过100%，则最优解不变；对所有变化的约束条件右侧的值系数，求其占可行增加和可行减少的百分比的绝对值之和。若绝对值之和不超过100%，则影子价格起作用；注意：当允许增加（减少）的量为无穷大时，则对任意增加（减少）的量，其允许增减（减少）的百分比均看做0；百分百法则是充分条件，非必要条件；该法则不能应用于目标函数系数和约束条件右边常数值同时变化的情况，此时需要重新计算。7:00本讲小结本讲小结 小结小结what-if 分析是在求得基本模型的最优解之后进行的，这些分析可以为管理层决策提供非常有用的信息；很多软件可以生成灵敏度报告，可以很快计算出最优域；运用目标函数系数的百分百法则百分百法则，可进一步方便地检验所有的同时变动情况；通过影子价格分析，发现改变决策会产生的影响，从而为管理层更好的决策提供指导；用约束右端值变动的百分百法则百分百法则来判断变动的幅度。
