《对偶问题与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《对偶问题与灵敏度分析.ppt（56页珍藏版）》请在三一办公上搜索。
1、运筹学第3章 对偶问题与灵敏度分析,湖南大学工商管理学院,本讲内容,什么是对偶问题单纯形法的矩阵描述对偶问题的性质线性规划的灵敏度分析,什么是对偶问题？,例1（生产计划问题）：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：,问：如何安排生产使该厂获利最大？,max z=70 x1+120 x2 s.t.9x14x2360 4x1+5x2200 3x1+10 x2300 x1,x20,对偶问题的提出,考虑上一讲的生产计划问题，若设备和原料都用于对外加工，工厂收取加工费。试问：该厂设备工时、劳动力和原料该如何定价？,显然，工厂给这些生产
2、要素定价，既要保证自己的利益，又要使自己的价格具有竞争力,价格越高越好,价格越低越好,一个合理的定价是：收取的加工费不能低于自己生产所得收益，在此前提下使总加工费尽量小。即：,Min w=360y1+200y2+300y3s.t.9y1+4y2+3y370 4y1+5y2+10y3120 y1,y20,对偶的定义,(LP)Max z=CX(DP)Min w=Yb s.t.AX b s.t.YA C X 0 Y 0,若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之，若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。,建立对偶问题的规则,对于上表，特别把握以下
3、要点：,求max的对偶问题时，变量反号求min的对偶问题时，约束反号,例1：写出下列规划问题的对偶问题,Max z=2x1+2x2-4x3 s.t.X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30,解：min w=30y1+80y2 s.t.y1+4y22 3y1+2y22 3y1+4y2-4 y1,y20,例2：写出下列规划问题的对偶问题,min z=2x1+8x2-4x3 s.t.X1+3x2-3x330-x1+5x2+4x3=80 4x1+2x2-4x350 X10,x20,x3无限制,解：max w=30y1+80y250y3 s.t.y1-y2+4y32 3y
4、1+5y2+2y38 3y1+4y24y3-4 y10,y2无限制,y30,单纯形法的矩阵描述,单纯形法的矩阵描述,设有线性规划问题,Max z=CX AXb X0,加上松弛变量XS=(xn+1,xn+2,xn+m),化为标准型,Max z=CX0Xs AX+IXS=b X0,XS0,单纯形法的矩阵描述,设A中存在一可行基B，相应的变量可分为基变量XB和非基变量XN，价值系数也分为CB,CN，即,A=(B,N)X=(XB,XN)TC=(CB,CN),Max z=CX0Xs AX+IXS=b X0,XS0,因而,于是,Max z=CX0Xs AX+IXS=b X0,XS0,代入XB,目标值,矩阵
5、形式描述的单纯形表,关于对偶问题的基本定理,定理1（弱对偶定理）,若 X(0),Y(0)分别为（LP）和（DP）的可行解，那么 CX(0)Y(0)b。(证明),该定理说明：如果原问题是最大化问题，则它的任意可行解对应的目标函数值都会小于等于其对偶问题(极小化)的任一可行解对应的目标函数值,证明：由X(0),Y(0)分别为原问题和对偶问题的可行解,则,AX(0)b,X(0)0 Y(0)AC,Y(0)0,于是，CX(0)Y(0)b,Max z=2x1+2x2-4x3 s.t.X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30,min w=30y1+80y2 s.t.y1+4y
6、22 3y1+2y22 3y1+4y2-4 y1,y20,例如,任意取一些可行解试试看？,定理2（无界性）,若一个问题无界，则另一个问题不可行,max z=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0,可行域,例如,定理3（最优性定理）,若 X(0),Y(0)分别为（LP）和（DP）的可行解，且 CX(0)=Y(0)b，那么 X(0),Y(0)分别为（LP）和（DP）的最优解,证明,设X*是LP问题的任一可行解，由弱对偶性CX*Y(0)b=CX(0),从而X(0)是最优解,同理Y(0)是最优解,定理4（对偶定理）,若其中一个问题有最优解，则另一个问题也有最优解，且
7、两者最优值相等,证明,证明：设X*是LP问题的最优解，相应的最优基为B，则检验数必定满足,令,定理5（互补松弛定理）,原问题及其对偶问题的可行解X(0)和Y(0)是最优解的充要条件是：Y(0)XS=0，YSX(0)=0,XS,YS分别为原问题松弛向量和对偶问题剩余向量,该定理说明：一对对偶问题达到最优，当且仅当松约束对应的对偶变量必定是紧的,利用互补松驰定理，可以在知道一个问题的最优解时，求解其对偶问题的最优解,4/5-2*3/5=-2/53,约束条件是松的,也即ys0,由互补松弛定理知X(0)ys=0所以x2=0,同理，x3=0,x4=0,又y1*0,而Y(0)xs=0,知xs0，即原问题第
8、一个约束取等式,同理，第2个约束也取等式,定理6,若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量的检验数和剩余变量的检验数的相反数即为对偶问题最优解,对偶最优解的经济含义影子价格,由对偶定理,求z*对bi的偏导数,所以对偶最优解为原问题各资源的影子价格,影子价格非资源的市场价格，而是指系统达到最优状态时，资源的单位变化引起目标最优值的变化,对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。
9、,什么是对偶单纯形法？,也就是说，求解原问题（LP）时，可以从（LP）的一个基本解（并不一定是基可行解）开始，逐步迭代，使目标函数值（Z=Y b=CB B-1b=CX）减少，当迭代到XB=B-1b0时，即找到了（LP）的最优解，这就是对偶单纯形法。,同原始单纯形求法一样，求解对偶问题（DP），也可以从（DP）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。,例一、用对偶单纯形法求解：,解：将模型转化为,所以，X*=（2.2.2.0.0.0），Z*=72，原问题 Z*=72 其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72,练习：,灵敏度分析,为
10、什么要进行灵敏度分析？,前面对线性规划的讨论，价值系数c，资源系数b和技术系数矩阵A都是已知常数。但现实中，这些系数可能只是估计量，存在误差或随着时间的推移可能有些许变化,糟糕！这个月产品市场价格与原计划时发生变化了。年初安排的生产计划还是最优的么？,价值系数变化的灵敏度分析,设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？,例(生产计划问题),价值系数变化的灵敏度分析,设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？,例(生产计划问题),最优单纯形表,考虑C2发生变化,价值系数变化的灵敏度分析,设只有一个价值系数cj
11、发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？,例(生产计划问题),最优单纯形表,显然只要-28+0.12c2 014-0.16c2 0 成立，则最优解不变！,即 87.5 c2233.33,右端项变化的灵敏度分析,考察单纯形表,0,z,I,b,0,C,因此，只要B-1b0,则最优基不变从而对偶最优解不变，也即影子价格不变,例如生产计划问题,考虑b3变化的灵敏度分析,最优单纯形表,由此可见，(p3,p1,p2)是最优基，即,计算机灵敏度分析的例子,生产计划问题Excel,生产计划问题DM,多个参数变化的灵敏度分析,百分之百法则：(1)对于所有变化的目标函数系数，当其所有允许增
12、加百分比和允许减少百分比之和不超过100时，则最优解不变(2)对于所有变化的右端项系数，当其所有允许增加百分比和允许减少百分比之和不超过100时，则对偶最优解不变,例,上述生产计划问题，若市场条件变化，产品A的单位利润下降为53元，产品B单位利润上升至160元，最优生产计划是否会发生变化？若A产品利润升为95元，而B产品降到90元呢？,(1)解：产品A利润降为53元，则C1=-17 产品b利润升为160元，则C2=40。根据前面的计算结果，计算变化率：,因此，最优生产计划不会改变！,V1=(-17)/(36-70)=0.5=50%,V2=40/(233.333-120)=0.353=35.3%
13、,V=v1+v2=83.5%,(2)解：产品A利润升为95元，则C1=25 产品B利润降为90元，则C2=30。根据前面的计算结果，计算变化率：,因此，最优生产计划会改变！,V1=25/(96-70)=0.9615=96.15%,V2=(-30)/(87.5-120)=0.9231=92.31%,V=v1+v2=188.46%100%,作业,某厂生产甲、乙、丙三种产品，已知有关数据如表所示，试分别回答下列问题：,（a）建立线性规划模型，求使该厂获利最大的生产计划；,（b）若产品乙、丙的单件利润不变，则产品甲的利润在什么范围内变化时，上述最优解不变。,（c）若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B如数量不足可去市场购买，单价为0.5，问该厂应否购买，以购进多少为宜；,
