敏感性分析运筹学课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,18:27,#,19:59,第三,讲,线性规划：灵敏度分析与对偶,李勇建 博士,17:23第三 讲 线性规划：灵敏度分析与对偶,1,主要内容,线性规划的对偶问题,线性规划的灵敏度分析问题,19:59,主要内容17:23,2,19:59,线性规划的对偶问题,对偶问题的来源,对偶问题的应用和经济解释,对偶问题的转化,17:23线性规划的对偶问题对偶问题的来源,3,19:59,原问题,约束：,对偶问题,最优解：,x,1,=50,x,2,=250,；,Z,*,=27500,17:23原问题约束：对偶问题最优解：x1=50,x2,4,19:59,如果把三种资源分别以价格,出租或买出，那么出让相对于生产一单位第,j,种产品的资源消耗的价值应不低于第,j,种产品的单位利润价值,因此有,但是买方会把价格压到最低：,y,1,：,y,2,：,y,3,：,17:23如果把三种资源分别以价格,5,19:59,对偶问题,决策变量：,y,i,收买该公司一单位,i,种资源时付给的价格,目标函数：,约束：,此极小问题称为原问题的,对偶问题,，解是,分别称为原料,1,，,2,，,3,的,影子价格或对偶价格,.,.,17:23对偶问题决策变量：yi 收买该公司一单位 i,6,19:59,y,1,y,2,y,3,17:23y1,y2,y3,7,19:59,举例,原问题,Max 50,x,1,+30,x,2,S.t.,4,x,1,+3,x,2,120,2,x,1,+,x,2,50,x,1,x,2,0,对偶问题,Min 120,y,1,+50,y,2,S.t.,4,y,1,+2,y,2,50,3,y,1,+,y,2,30,y,1,y,2,0,17:23举例原问题对偶问题,8,19:59,对偶规划的应用,一般来说，线性规划问题是确定资源的最优分配方案；对偶问题则是确定对资源的恰当估价，以确定资源的最有效利用；,可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏；,对于一些紧缺资源，可以借助于影子价格机制规定上交的利润额，控制一些经济效益低的公司自觉地节约使用紧缺资源。,17:23对偶规划的应用一般来说，线性规划问题是确定资源的最,9,影子价值的内涵,影子价格不是资源的实际价格，反映了资源配置结构，,其它数据固定，某资源增加一单位导致目标函数的增量。,对资源,i,总存量的评估：,购进,or,出让,对资源,i,当前分配量的评估：,增加,or,减少,第一，影子利润说明增加哪种资源对经济效益最有利,第二，影子价格告知以怎样的代价去取得紧缺资源,第三，影子价格是机会成本，提示资源出租,/,转让的基价,第四，利用影子价格分析新品的资源效果：定价决策,第五，利用影子价格分析现有产品价格变动的资源紧性,第六，可以帮助分析工艺改变后对资源节约的收益,第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺,影子价值的内涵影子价格不是资源的实际价格，反映了资源配置结构,10,资源定价的决策方案,例：,某厂生产甲乙产品,，（,1,）如何安排每周的利润为最大,?,（,2,）如果企业可以不生产，那资源出让如何定价？,甲,乙,资源成本,资源拥有量,原材料,(kg),设备,(,工时,),电力,(,度,),9,4,3,4,5,10,20,50,1,360,200,300,销售价格,(,元,),390,352,1,、最优生产决策,资源定价的决策方案例：某厂生产甲乙产品，（1）如何安排每周的,11,资源定价的决策方案,2,、资源获利决策,如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。,设原材料的单位出让获利为,y,1,，设备工时的单位出让获利为,y,2,，电量的单位出让获利为,y,3,。,出让决策的线性规划模型：,资源定价的决策方案2、资源获利决策如果决策者考虑自己不生产甲,12,19:59,阅读和自学,：,参考书,P60-61,，第,3.3.4,节,17:23阅读和自学：,13,19:59,想一想,产品的机会成本是什么,:,表示减少一件产品,j,所节省的资源可以增加的利润,.,产品的差额成本是什么,:,17:23想一想产品的机会成本是什么:,14,19:59,如果,则用这些资源来生产这种产品更为有利可图,.,如果,表明已经在其他地方以更为有利可图的方式使用这些资源，没有必,要生产产品,j,.,其经济解释是,:,在利润最大化的生产计划中,(1),边际利润大于,0,的资源没有剩余,;,(2),有剩余的资源边际利润等于,0;,(3),安排生产的产品机会成本小于等于利润,;,(4),机会成本大于利润的产品不安排生产,.,对偶问题的经济解释,17:23如果对偶问题的经济解释,15,19:59,对偶的一般形式,17:23对偶的一般形式,16,19:59,17:23,17,19:59,例,1,：,写出下面线性规划的对偶规划,17:23例1：写出下面线性规划的对偶规划,18,19:59,1,，建立对偶表,17:231，建立对偶表,19,19:59,y,1,y,2,y,3,2,，写出对偶规划,17:23y12，写出对偶规划,20,19:59,阅读和自学：,参考书,P56-59,，第,3.3.1,和,3.3.2,节,17:23阅读和自学：,21,19:59,线性规划的敏感性分析,什么是敏感性分析,伟恩德公司案例研究,目标函数系数分析,右端项的影子价格分析,17:23线性规划的敏感性分析什么是敏感性分析,22,19:59,原材料,6,大块,8,小块,产品,桌,椅,Profit=$20/TableProfit=$15/Chair,自己动手,17:23原材料6 大块8 小块产品 桌,23,19:59,如果桌子的利润是,$35,，最优解会怎样变化呢？,如果又有一个额外的大块，会增加总利润吗？,如果桌子和椅子构成改变，最优解会变化吗？,如果还有一些原材料，你愿意以多大的代价购买呢？,拼装玩具生产,自己动手,你怎么来分析这些问题？,想想看！,17:23如果桌子的利润是$35，最优解会怎样变化呢？自己动,24,19:59,什么是敏感性分析,定义：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）,c,i,a,ij,b,j,变化时，对最优解产生的影响,数学模型只是实际问题的一个粗略的抽象,最优解一般只是针对某一特定的数学模型,管理者要对未来做各种假设，在这些假设下，测试可能产生的结果，通过对各种结果深入分析来指导决策,通常，在取得最初版本模型的最优解之后，进行分析才能取得对问题深入的认识,这种分析称为,what-if,分析,或敏感性分析（,Sensitivity Analysis,）,意义：,what-if,分析可以表明改变这些决策对结果的影响，从而有效指导管理者作出最终的决策,17:23什么是敏感性分析 定义：建立数学模型和求得最优解后,25,19:59,伟恩德公司案例研究,实际举例,17:23伟恩德公司案例研究实际举例,26,19:59,伟恩德公司案例研究,修正的伟恩德例子，门的单位利润,P,D,=$300,降到,P,D,=$200,，而最优解不变,实际举例,17:23伟恩德公司案例研究修正的伟恩德例子，门的单位利润P,27,19:59,伟恩德公司案例研究,修正的伟恩德例子，门的单位利润,P,D,=$300,增加到,P,D,=$500,，而最优解不变,实际举例,17:23伟恩德公司案例研究修正的伟恩德例子，门的单位利润P,28,19:59,伟恩德公司案例研究,修正的伟恩德例子，门的单位利润从,P,D,=$300,增加到,P,D,=$1000,，最优解改变,实际举例,17:23伟恩德公司案例研究修正的伟恩德例子，门的单位利润从,29,19:59,伟恩德公司案例研究,在伟恩德的例子中系统改变门的单位利润得到数据表,实际举例,17:23伟恩德公司案例研究在伟恩德的例子中系统改变门的单位,30,19:59,伟恩德公司案例研究,其中最后三栏表示了门窗单位利润的最优域。,实际举例,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,17:23伟恩德公司案例研究其中最后三栏表示了门窗单位利润的,31,19:59,最优域敏感性分析,如何在不重新求解模型的条件下，确定如果目标函数的几个系数同时变化，可能造成对最优解的影响,如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？,17:23最优域敏感性分析如何在不重新求解模型的条件下，确定,32,19:59,伟恩德公司案例研究,修正的伟恩德问题模型，其中门，窗的单位利润分别被改为,P,D,=$450,P,W,$400,，但是最优解不变,实际举例,17:23伟恩德公司案例研究修正的伟恩德问题模型，其中门，窗,33,19:59,伟恩德公司案例研究,修正的伟恩德问题模型，其中门，窗的单位利润分别被改为,P,D,=$600,P,W,$300,，从而最优解改变,实际举例,17:23伟恩德公司案例研究修正的伟恩德问题模型，其中门，窗,34,19:59,伟恩德公司案例研究,伟恩德例子中系统改变门，窗单位利润得到的数据表,实际举例,17:23伟恩德公司案例研究伟恩德例子中系统改变门，窗单位利,35,19:59,百分之百法则,目标函数系数同时变动的百分之百法则,(The 100 percent rule for simultaneous changes in objective function coefficients),：,如果目标函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。,17:23百分之百法则目标函数系数同时变动的百分之百法则(T,36,19:59,可用于确定在保持最优解不变的条件下，目标函 数系数的变动范围,百分百法则通过将允许的增加或减少值在各个系数之间分摊，从而可以直接显示出每个系数的允许变动值,线性规划研究结束以后，如果将来条件变 化，致使目标函数中一部分或所有系数都发生变动，百分百法则可以直接表明最初最优解是否保持不变,百分之百法则的作用,17:23可用于确定在保持最优解不变的条件下，目标函 数系数,37,19:59,右端项的影子价格分析,分析,函数约束右端值,变动的原因也是不能得到模型的参数的精确值，只能对其作大略的估计。因此要知道万一这些估计不准确产生的后果,更主要的理由是因为这些常数往往不是由外界决定的而是,管理层的政策决策,。在建模并求解后，管理者想要知道如果改变这些决策是否会提高最终收益,影子价格分析就是为管理者提供这方面的信息,17:23右端项的影子价格分析分析函数约束右端值变动的原因也,38,19:59,影子价格,在给定线性规划模型的最优解和目标函数相应值的条件下，影子价格（,shadow price,）就是约束常数增加微小的量，使得目标函数值增加的量。,17:23影子价格在给定线性规划模型的最优解和目标函数相应值,39,19:59,Max z=20A+30B,S.t.,工序,1:2A+B40,工序,2:A+2B40,工序,3:A+B25,非负约束：,A0,B0,最优解：,A=10,B=15,Z=650,影子价格：工序,1,的为,0,；工序,2,的为,10,；工序,3,的为,10,实际举例,17:23Max z=20A+30B实际举例