对偶理论与灵敏度分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第4章 主要内容：,对偶规划,对偶理论,对偶单纯形算法,1,4.1对偶问题的提出,现从另一个角度来讨论，假定工厂考虑不安排生产，而是出售原材料，出租工时或转产新产品等。问如何定价，可使工厂获利不低于安排生产所获得的收益，且又能使这些定价具有竞争力？,设出售原料的定价为毎公斤,y,1,元，,出租工时的定价为毎工时,y,2,元.从工厂考虑，这些定价下的获利不应低于安排生产所获得的收益。否则工厂宁可生产，而不出售或出租或转产等,由此考虑出售或出租或转产的数学模型.,2,对偶问题?,任何线性规划问题都有其对偶问题,对偶问题有其明显的经济含义,假设有商人要向厂方购买资源A和B，问他们谈判原料,价格的模型是怎样的？,3,原问题简单的生产计划问题,如何安排一天的生产计划，使企业利润最大？,某工厂生产甲、乙两种产品，单位产品,利润、耗工耗料及工料限额为下表,4,解：,限制条件,：,“s.t.”:Subject to,目标函数,决策变量,约束条件,5,新问题简单的生产计划问题,设出售原料的定价为毎公斤,y,1,元，,出租工时的定价为毎工时,元.,6,例,生产计划问题,某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划。,单位产品所需原料数量（公斤）,产品Q1,产品Q2,产品Q3,原料可用量,（公斤/日）,原料P1,2,3,0,1500,原料P2,0,2,4,800,原料P3,3,2,5,2000,单位产品的利润（千元）,3,5,4,7,（原问题）,8,*,对偶问题,9,原问题与对偶问题的关系,（一）对称形式的对偶问题,比较上述的两个互为对偶问题：,10,1、一个问题中的约束条件个数等于它的对偶问题中的变量数。,2、一个问题中目标函数的系数是其对偶问题中约束条件的右端项。,3、约束条件在一个问题中为“”，则在其对偶问题中为“”.,4、目标函数在一个问题中求最大值，在其对偶问题中则为求最小值。,显然：对称形式的对偶问题，若已知其中一个问题，立即就可以写出相应的对偶问题。,11,表2.13 对偶变换的规则,约束条件的类型与非负条件对偶,非标准的约束条件类型对应非正常的非负条件,对偶变换是一一对应的,12,原问题（或对偶问题）,对偶问题（或原问题）,目标函数,MaxZ,目标函数,MinW,约束条件数：,m,个,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,=,”,对偶变量数：,m,个,第,i,个变量,0,第,i,个变量,0,第,i,个变量是自由变量,决策变量数：,n,个,第,j,个变量,0,第,j,个变量,0,第,j,个变量是自由变量,约束条件数：,n,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,”,第,i,个约束条件类型为“,=,”,13,课堂练习：写出下面线性规划的对偶规划：,14,下面的答案哪一个是正确的？为什麽？,（原问题是极小化问题，因此,应从原始对偶表的,右边,往,左边,查！,）,15,（二）非对称形式的对偶问题,（1）如果原问题约束中包含等式约束，如AX=b,等价于,16,对偶问题的基本性质定理,1、,对称性定理：,对偶问题的对偶是原问题。,2、,弱对偶定理：,若X,(0),是原问题的可行解,Y,(0),是对偶问题的可行解,则有CX,(0),Y,(0),b.,3、最优性定理：若X,(0),是原问题的可行解,Y,(0),是对偶问题的可行解,且有CX,(0),=Y,(0),b则 X,(0)、,Y,(0),分别是原问题和对偶问题的最优解。,4、,对偶定理：,若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等。,5、互补松弛性定理：X,*、,Y,*,分别是原问题和对偶问题的可行解，则 X,*、,Y,*,是最优解的充分必要条件是X,*,Y,S,=0和Y,*,X,L,=0,6、,解的对应定理：,原问题的单纯形表的检验数行对应其对偶问题的一个基解.,由解的对应定理可知，当在检验数行得到对偶问题的解可行时，原问题已达到最优解。,17,对偶定理,是揭示,原始问题的解与对偶问题的解之间重要关系,的,一系列定理。,18,2.4.4 对偶单纯形法,什麽是对偶单纯形法？,对偶单纯形法,是应用,对偶原理,求解原始线性规划的一种方法在原始问题的单纯形表格上进行,对偶处理,。,注意：,不是解对偶问题的单纯形法！,19,2.4.4,对偶单纯形法,1、两种方法的特点,单纯形法特点：在保持基可行解的情况下，每迭代一次，就使目标函数值增大一次，当问题取得最优解时，目标函数达到最大值。,对偶单纯形法特点：将单纯形法应用于对偶问题的计算，在保持对偶问题有可行解的基础上，每迭代一次，就使目标函数值减少一次，当问题得到最优解时，目标函数取到最小值。,20,2、对偶单纯形法的计算步骤,（1）把对偶问题化为标准形，但允许主约束条件右边常数 为任意数。,(注意到这里并不需引进人工变量),（2）通过对约束等式两边同乘“1”产生初始基（单位矩阵），列出初始表。,（3）确定“出基”变量：,21,出,基原则：小于0的 中最小者（绝对值最大者）所对应的,行,变量。即在所有 0中，,对应的变量y,r,出基，y,r,所在行为主元行。,原问题的,进,基原则：中最小对应的,列,变量。,（4）确定“进基”变量,若主元行中没有负元素，可以证明问题没有可行解，计算结束。,（原问题中：若主元列都是负元素，可以证明问题有无数可行解，无最优解。）,否则，按最小比值原则确定进基变量：,（5）用进基变量替换出基变量得到新基，继续迭代。,（6）重复35步。,22,23,约束条件两端乘以“-1”得,24,c,j,-15 -24 -5 0 0,C,B,Y,B,b,y,1,y,2,y,3,y,4,y,5,0,0,y,4,y,5,-2,-1,0,-6,-1 1 0,-5 -2 -1 0 1,w,0,15 24 5 0 0,-24,0,y,2,y,5,1/3,-1/3,0 1 1/6 -1/6 0,-5 0,-2/3,-1/3 1,w,-8,15 0 1 4 0,-24,-5,y,2,y,3,1/4,1/2,-5/4 1 0 -1/4 1/4,15/2 0 1 1/2 -3/2,w,-17/2,15/2 0 0 2/7 3/2,原问题的最优解为(0,1/4,1/2),最优值为17/2,25,由上例得结论：,（1）当约束条件为“”时，不必引进人工变量，使计算简化。,（2）由对偶问题的性质知道：用单纯形法求解L.P问题时，每一次迭代可得一个基解，这时检验数行的数是对偶问题的一个基解。原问题的松驰变量对应着对偶问题的决策变量，对偶问题的松驰变量对应着原问题的决策变量。在一个问题中是基变量，则在另一个问题中就是非基变量，反之亦然。,（3）,对偶问题的解正是原问题的最优表中松驰变量 在检验数行中的数。反之，原问题的解正是对偶问题的最优表中松驰变量 在检验数行中的数。,（4）对偶问题的解y,i,称为资源的影子价格。,26,原问题 对偶问题,每次迭代，检验数行的数,基解（最优表中是最优解,-影子价格）,松馳变量 决策变量,决策变量 松馳变量,基变量 非基变量,非基变量 基变量,目标函数值 =目标函数值,练习P.30例14,27,2.4.5 对偶变量的经济意义和影子价格,1、影子价格（Shadow Pyice)：对资源在生产中做出的贡献而做出的评价。它不是市场价格。资源的市场价格是已知的，而影子价格有赖于资源的利用情况，是未知的。,对偶变量的经济意义就是影子价格.,2、影子价格是一种边际价格。（随着资源量的改变而改变）,28,3、没有最优决策，就没有影子价格。影子价格真实反映了资源在最优决策下对总收益（目标函数值）的影响和贡献大小。由松紧定理知，影子价格为正数，表明该种资源在最优决策下已充分利用耗尽，并成为进一步增加总收益的紧缺资源（短线资源），影子价格为零，表明该种资源在最优决策下尚有剩余（长线资源）。,4、影子价格是机会成本。,当某种资源的市场价格低于影子价格时，可购进该种资源，组织和增加生产。,当某种资源的市场价格高于影子价格时，可卖出该种资源，不安排生产或提高产品价格。,当某种资源的市场价格等于影子价格时，则处于平衡状态。,5、有效利用资源的影子价格指导经济活动是有积极意义。,29,复习单纯形法（P16的例5）,引例：解L.P问题,30,c,j,4 3 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,0,0,x,3,x,4,24,26,2 3 1 0,3,2 0 1,12,26/3,Z,0,-4 -3 0 0,0,4,x,3,x,1,20/3,26/3,0,5/3,1 -2/3,1 2/3 0 1/3,4,13,Z,104/3,0 -1/3 0 4/3,3,4,x,2,x,1,4,6,0 1 3/5 -2/5,1 0 -2/5 3/5,Z,36,0 0 1/5 6/5,注意:哪个数是影子价格?有可意义?,31,2.5灵敏度分析(优化后分析),一、问题的提出：,在前面的讨论中都假定问题中的,a,ij,b,i,c,j,是已知常数。但在实际中，这些数据大多数是预测、统计、评估的结果。因而有必要分析：,（1）当这些参数中的一个或多个发生变化时，问题的最优解会发生什么变化？,（2）这些参数在多大范围内变化时，问题的最优解才不会改变。,（3）若问题的最优解起了变化，怎样在先前优化的基础上迅速求得新的最优方案？,32,二、最优单纯形表中各块与各系数的关系,C,C,B,X,B,b,X,b,A,Z,C,B,B,-1,b,C,B,B,-1,A-C,各块与各系数的关系：,（,1,）,B,-1,A与a,ij,有关；（2)B,-1,b与a,ij,b,i,有关;,（3),C,B,B,-1,A-C与a,ij,c,j,有关;（4）Z=C,B,B,-1,b与 a,ij,b,i,c,j,都有关。,注意：,B,为最,优,基，其相应元素及,b，A,的元素都是,初始表,中的相应元素。,C,C,B,X,B,b,X,B,-1,b,B,-1,A,Z,C,B,B,-1,b,C,B,B,-1,A-C,初始表,最优表,33,由上，分析可以从以下两方面入手：,（1）数据的变化是否影响基,B,的初始可行性（,B,-1,b0,);,（2）数据的变化是否影响基,B,的对偶可行性（,C,B,B,-1,A-C0,);,从五个方面开展讨论：,（1）价值系数,c,j,的变化分析,（2）资源数量,b,i,的变化分析,(3)技术系数,a,ij,的变化分析,(4)对增加约束条件分析,(5)增加一个变量的分析(不讲),34,2.5.1 价值系数c,j,的变化分析,(1)若c,j,是最优表中非基变量x,j,的系数（此情况实际中很少)当c,j,c,j,+,c,j,，为保持原基B的最优性，须,35,例1 已知L.P问题,s.t,解得 最终表如下：,C,j,2 1 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,2,1,X,3,x,1,x,2,7.5,3.5,1.5,0 0 1 5/4 -15/2,1 0 0 1/4 -1/2,0 1 0 -1/4 3/2,Z,8.5,0 0 0 1/4 1/2,36,试确定：（1）当目标函数变为maxZ=5x,1,+1.5x,2,时，最优解会出现什么变化;,(2)目标函数变为maxZ=(2+,c)x,1,+x,2,时，,c在什么范围内变化，最优解不变。,解（1）将目标函数系数的变化直接反映到最终表：,C,j,5 1.5 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,5,1.5,X,3,x,1,x,2,7.5,3.5,1.5,0 0 1 5/4 -5/2,1 0 0 1/4 -1/2,0 1 0 -1/4 3/2,Z,19.75,0 0 0 7/8 -1/4,37,因x,5,的检验数为负，继续迭代得新解为 x,1,