运筹学 03 对偶理论及灵敏度分析.ppt

1、对偶理论及灵敏度分析Dual Theory and Sensitivity Analysis,对偶理论 Dual Theory 影子价格 Shadow price 对偶单纯形法 Dual Simplex Method 灵敏度分析 Sensitivity Analysis 参数线性规划Parameter LP,1 对偶理论,对偶问题的提出 原问题与对偶问题的数学模型 原问题与对偶问题的对应关系 对偶问题的基本性质 影子价格 对偶单纯形法,对偶问题的提出,例1：某厂利用现有资源(设备A、设备B、调试工序)生产两种产品(产品、产品)，有关数据如下表。问如何安排生产，使厂家利润最大？,分析：设产品的产

2、量为x1，产品的产量为x2；又设利润为z。则该问题的线性规划数学模型为： max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20,换一种思路：厂家的资源只出让而不自己生产，该如何解决？ 设备A出让单价为y1，设备B出让单价为y2，调试工序出让单价为y3。,收 购,收购代价最小,厂 家,出让所得应不低于用同等数量的资源自己生产的利润。,厂家接受的条件：利润需要保证，即 6y2+y32 5y1+2y2+y31 收购方接受的条件：收购成本最低，即 min w=15y1+24y2+5y3 于是得到一个线性规划模型 min w=15y1+24y2+5y3 6y2+y32 5

3、y1+2y2+y31 y1,y2,y30,原问题与对偶问题的数学模型,原问题 max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20,对偶问题 min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 y1,y2,y30,互为对偶问题,厂 家,收 购,原问题及其对偶问题的最终单纯形表,尝试求解上述两个线性规划问题，你会发现 目标函数值一致 两个问题的解都出现在单纯形法表格中 其他规律 结论 原问题与其对偶问题实质上一样 两个问题互为对方的另一种表达形式,原问题与对偶问题的对应关系,例2：将下述线性规划作为原问题，请转换为对偶问题 max z=

4、5x1+3x2+2x3+4x4 5x1+x2+x3+8x48 2x1+4x2+3x3+2x4=10 x10,x20,x3任意,x4任意,解法1：将原问题写成对称形式的线性规划问题。得到 max z=5x1+3x2+2(x3-x3)+4(x4-x4) 5x1+x2+(x3-x3)+8(x4-x4)8 2x1+4x2+3(x3-x3)+2(x4-x4)10 -2x1-4x2-3(x3-x3)-2(x4-x4)-10 x10,x20,x30,x30,x40,x40,设对偶问题变量y1,y2,y20，直接转换，得 min f=8y1+10y2-10y2 5y1+2y2-2y25 y1+4y2-4y23

5、 y1+3y2-3y22 -y1-3y2+3y2-2 8y1+2y2-2y24 -8y1-2y2+2y2-4 y1,y2,y20,令y2=y2-y2(即y2取值任意)，合并第3、4个约束条件和第5、6个约束条件，得到原问题的对偶问题 min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2y2=4 y10,y2任意,解法2：也可以根据原问题与对偶问题的对应关系，直接得到对偶问题： min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2y2=4 y10,y2任意,对偶问题的基本性质,对称性：对偶问题的对偶是原问题(对称定理

6、)。 证明： 设原问题为max z=CX,AXb,X0；则其对偶问题为min f=bTY,ATYCT,Y0。 把对偶问题看作原问题，得到线性规划模型为max f=-bTY,-ATY-CT,Y0。 将上述问题转换为对偶问题，得到min z=-(CT)TX,-(AT)TX-(bT)T,X0，即max z=CX,AXb,X0。 所以对偶问题的对偶即为原问题。,弱对偶性：若X是原问题的可行解，Y是其对偶问题的可行解，则恒有CXbTY。 证明： 因为X为原问题的可行解，故AXb，且X0；因为Y为对偶问题的可行解，故ATYCT，且Y0。 由上述可得CX=XTCTXTATY=YTAXYTb=bTY。,原问题

7、,对偶问题,CX*=bTY*,CXbTY,从弱对偶性可得到以下重要结论： (1)极大化问题(原问题)的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。 (2)极小化问题(对偶问题)的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。 (3)若原问题可行，但其目标函数值无界，则对偶问题无可行解。 (4)若对偶问题可行，但其目标函数值无界，则原问题无可行解。 (5)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 (6)对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,最优性：若X是原问题的可行解，Y是其对偶问题的可行解，且有CX=bTY，则X是原

8、问题的最优解，Y是其对偶问题的最优解。 证明： 根据弱对偶性及已知条件，对于对偶问题任意可行解Y*都有bTY*CX=bTY，故Y为对偶问题的最优解。 根据弱对偶性及已知条件，对于原问题的任意可行解X*都有CX*bTY=CX，故X为原问题的最优解。,强对偶性：若原问题及其对偶问题都有可行解，则两者都有最优解，且最优解的目标函数值相等(对偶定理)。 证明：根据弱对偶性可知，由于原问题与对偶问题都有可行解，故原问题目标函数有上界且对偶问题目标函数有下界，所以两者都有最优解。 同时，原问题的影子价格即为对偶问题的一个可行解，这个可行解的目标函数即为原问题的目标函数值，且为最优。,互补松弛性：在线性规划

9、问题的最优解中，有以下结论成立：(1)若yi0，则aijxj=bi；(2)若aijxjbi，则yi=0。 证明：由弱对偶性可知，CXYTAXYTb。 且由CX=YTb=YTAX，得到YT(AX-b)=0。 这就说明了Y的第i个分量和AX-b的第i个分量若其中一个不为零，另外一个必定为零。结论得证。,2 影子价格,影子价格的定义 影子价格的经济意义,影子价格的定义,当线性规划原问题求得最优解X*时，其对偶问题也得到最优解Y*，且有z*=CX*=bTY*=f* 式中b是线性规划问题约束条件的右端项，表示各种资源的拥有量；对偶变量Y*的意义代表在资源最优利用条件下对单位资源的估价。这种估价不是资源的

10、市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price),影子价格的经济意义,(1)资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。,(2)影子价格是一种边际价格。在z*=bTY*中对b求导数，得到dz*/dbT=Y*，这说明Y*的值相当于在资源得到最优利用的生产条件下，b每增加一个单位时目标函数z的增量。,(3)资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当资源的市场价格低于影子价格时，可以买进这种资源；相反当市场价格高于影子

11、价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,(4)在对偶问题的互补松弛性质中有：当ai1xi1+ai2xi2+ainxin0时，ai1xi1+ai2xi2+ainxin=bi，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,(5)从影子价格的含义上再来考察单纯形表的计算。检验数j=cj-CBB-1Pj=cj-aijyi，式中cj代表第j种产品的产值，aijyi是生产该种产品所消耗各种资源的影子价格的总和，即产品的隐含成

12、本。当产品产值大于隐含成本，表明生产该项产品有利，可在计划中安排；否则，用这些资源来生产别的产品更为有利(准确地说，出售更有利)，就不在生产计划中安排。这就是检验数的经济意义。,(6)一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。,3 对偶单纯形法,对偶单纯形法的基本思路 对偶单纯形法的计算步骤 对偶单纯形法的应用举例,对偶单纯形法的基本思路,当一个线性规划的约束条件中包含“”约束时，为了获得初始可行基，必须用大M法，略嫌麻烦。 若减去一个剩余变量，认定为基变量，则成为系数为-1的基变量，其基本解不可行。

13、但是，若基本解满足最优性检验，也就是说其对偶问题所对应的解可行，那么通过迭代，可以使得原问题的解逐渐变得可行，也就得到了原问题的最优解。这就是对偶单纯形法的原理。优点是不需要添加人工变量。,单纯形法的基本思路,对偶问题的可行解,对偶问题最优解判断,对偶单纯形法 基本思路,最优解判断 j=cj-zj0,原问题基可行解 xB=B-1b0,对偶单纯形法的计算步骤,第一步：给出一组满足最优检验的基本解 第二步：若当前解可行，则得最优解 第三步：确定出基变量。选择负数基本解中最小值所对应的变量作为出基变量。即当 minbi|bi0=br时第r行对应变量为出基变量 第四步：确定入基变量。若第r行都大于等于

14、0则无可行解，停止计算；否则计算=minj/arj|arj0,j0=s/ars，即选择xs为入基变量 第五步：以ars为主元素进行消元，转第二步,对偶单纯形法的应用举例,例3：已知线性规划问题及其对偶问题 max z=7x1+5x2 2x1+2x220 x1+3x215 4x1+x232 2x1+3x221 x1,x20 min w=20y1+15y2+32y3+21y4 2y1+y2+4y3+2y47 2y1+3y2+y3+3y45 y1,y2,y3,y40 试用对偶单纯形法求解对偶问题,对偶单纯形法的优点： 不需要人工变量； 当变量多于约束时，用对偶单纯形法可减少迭代次数； 在灵敏度分析中

15、，有时需要用对偶单纯形法处理简化。 对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。 因此，对偶单纯形法一般不单独使用。,练习,用对偶单纯形法求解线性规划问题： min w=2x1+3x2+4x3 x1+2x2+x33 2x1-x2+3x34 x1,x2,x30,4 灵敏度问题及其图解分析,灵敏度问题 灵敏度分析图解法 灵敏度分析对偶理论分析,灵敏度问题,线性规划问题中，aij,cj,bi都是常数，但这些系数是估计值和预测值。 市场的变化cj值变化； 工艺的变化aij值变化； 资源的变化bj值变化。 这样，自然就出现了如下的问题： 当这些系数中的一个或多

16、个发生变化时，原最优解会怎样变化？ 当这些系数在什么范围内变化时，原最优解仍保持不变？ 若最优解发生变化，如何用最简单的方法找到现行的最优解？,研究内容 研究线性规划中，aij,bi,cj的变化对最优解的影响。 研究方法 图解法 对偶理论分析,仅适用于含2个变量的线性规划问题,在单纯形表中进行分析,灵敏度分析图解法,例4：用图解法求解下列线性规划模型 max z = 34 x1 + 40 x2 4 x1 + 6 x2 48 2 x1 + 2 x2 18 2 x1 + x2 16 x1,x20,灵敏度分析对偶理论分析,分析cj的变化 分析bi的变化 分析aij的变化 增加一个变量xj的分析 增加

17、一个约束条件的分析,研究内容 研究线性规划中，aij,bi,cj的变化对最优解的影响。 常用公式 检验数NT=cNT-cBTB-1N；j=cj-cBTB-1pj 基本解z=cBTB-1b+cNTxN=cBTB-1b,(1)非基本变量系数ck的灵敏度分析 系数： 原来ck 变化后ck=ck+ck 检验数： 原来k=ck-cBTB-1pk 改变后k=ck-cBTB-1pk=k+ck 为了保持最优解不变，必须k0，即 ck-k ck=ck+ckck-k,(2)基本变量系数cl的灵敏度分析 系数： 原来cl 变化后cl=cl+cl 检验数： 原来j=cj-cBTB-1pj(jl) 改变后j=cj-(c

18、BT+cT)B-1pj=j-clalj 为了保持最优解不变，必须j0，即 maxj/alj|alj0clminj/alj|alj0,(3)右端常数项br的灵敏度分析 常数项： 原来br 变化后br=br+br 基本解： 原来xB=B-1b 改变后xB=B-1b=B-1b+B-1(0,br,0)T =(b1,bm)T+br(1r,mr)T 为了保持最优基不变，必须xB0，即 bi+brir0，i=1,2,m，亦即 max-bi/ir|ir0brmin-bi/ir|ir0,(4)约束条件中系数aij的灵敏度分析(非基变量) 约束条件系数： 原来aij 变化后aij=aij+aij 检验数： 原来j=cj-cBTB-1pj=cj-yTpj 改变后j=cj-yTpi=j-yiaij 为了保持最优解不变，必须j0，即 当yi0时，aijj/yi 当yi0时，aijj/yi,(5)增加新的变量 略 (6)增加新的约束条件 略,例5：某家电厂家利用现有资源生产两种产品，有关数据如下表。,试问 问题1：如何安排生产，使厂家获利最多？ 问题2：当c1=1.5时，最优生产计划有何变化？ 问题3：当c2=2时，最优生产计划有何变化？ 问题4：求原最优解不变时c2的范围。 问题5：b1和b2分别如何改变，原计划不变？ 问题6：为保持最优解不变，