2.对偶理论与灵敏度分析.ppt

1、1,第二章 线性规划的对偶理论,窗含西岭千秋雪，门泊东吴万里船,本章主要内容： 线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析,2,第一节 对偶问题的提出,假设工厂考虑不进行生产而把全部资源都转让，问如何定价这些资源，既能使其获利不低于安排生产所获得的收益，又能使资源租让具有竞争力。,一、引例,Max Z = 2000 x1+4000 x2+3000 x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30,Min W =600y1+400y2+300y3+2

2、00y4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40,x1 x2 x3,y1 y2 y3 y4,3,二、对偶问题,（1）对称LP问题的定义,（2）对称LP问题的对偶问题,第一类对称形式,第二类对称形式,4,例1 写出下列LP问题的对偶问题,Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0,Min W =8y1+16y2+12y3 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 0,5,（3）对偶问题的对

3、偶是原问题,推导过程,变形,对偶,Max Z=CTX s.t. AXb X0,Min W=bTY s.t. ATYC Y0,Max W = -bTY s.t. -ATY -C Y0,Min Z = -CTX s.t. -(AT)TX -b X0,6,例2 写出下列LP问题的对偶问题,解: 上述LP问题的 对偶问题为：,7,三、非对称LP问题的对偶问题,例3 写出下列LP问题的对偶问题,解：用x2= -x2, x3=x3-x3代入上述LP问题，并将其化为第一类对称形式,Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10,

4、 x20 ,x3无约束,Max Z = x1-2x2 +x3-x3 x1 -x2 -x3+x3 2 x1+x2+x3 -x3 1 s.t. -x1 -x2 -x3+x3 -1 -2x1+x2 -x3+x3 -2 x1, x2, x3, x3 0,8,上述第一类对称形式LP问题的对偶问题为：,则上述问 题变为：,Min W =2y1+y2 -y3-2y4 y1+y2 -y3-2y4 1 -y1+y2 -y3 +y4 -2 s.t. -y1+y2 -y3 -y4 1 y1 -y2+y3 +y4 -1 y1, y2, y3, y4 0,Min W =2u1+u2+2u3 u1+u2+2u3 1 s.

5、t. u1 -u2+ u3 2 -u1+u2+ u3 =1 u10, u30 ,u2无约束,令 u1= y1 u2=y2-y3 u3=-y4,9,对偶关系：一个问题第i个变量的约束情况决定另一问题第i个约束不等式的方向，反之亦然。,正常的对正常的，不正常的对不正常的,10,例3 直接写出LP问题的对偶问题,11,12,第二节 LP问题的对偶理论,若X(0),Y(0)分别为(L),(D)的可行解，则有CTX(0)bTY(0),定理1(弱对偶定理): 极大化原问题目标函数值总是不大于其对偶问题的目标函数值。,证明： 由于X(0)是(L)的可行解，有AX(0)b, X(0)0. 由于Y(0)是(D)

6、的可行解，有Y(0)0. Y(0)T左乘不等式组AX(0)b的两边得： Y(0)TAX(0) Y(0)Tb. 两边同时转置得 X(0)TATY(0) bTY(0) （1）,13,又ATY(0) C, X(0)T0. 所以 X(0)TATY(0) X(0)TC = CTX(0) (2) 由（1），（2）得： CTX(0) bTY(0),14,推论1,若LP问题有无界解，则其对偶问题无可行解； 若LP问题无可行解，则对偶问题或有无界解或无可行解。,推论2,极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题目标函数值的下界。,极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题目标

7、函数值的上界。,推论3,15,例4 考虑下面一对LP问题,其对偶问题为：,由于X(0) =(1,1,1,1)T, Y(0)=(1,1)T分别为(L),(D)的可行解，故Z40,W10.,Max Z = x1+2x2+3x3+4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,16,定理2（最优性准则） 当LP问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。,若X(0),Y

8、(0)分别为(L)，(D)的可行解,且CTX(0)bTY(0) ， 则X(0),Y(0)分别为(L)，(D)的最优解。,证明： 由定理1可知，对于(L)的任意可行解X，有CTX bTY(0) 由于CTX(0) = bTY(0) ，故X(0)为 (L) 的最优解。 同理Y(0)为(D)的最优解。,17,例5,Max Z = x1+2x2+3x3+4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y2

9、0,由于X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是(L)，(D)的可行解且 CX(0)=bTY(0)=28，所以X(0),Y(0)分别为(L)，(D)的最优解。,18,定理3（强对偶定理） 若(L)，(D)均有可行解，则(L)，(D)均有最优解，且目标函数最优值相等。,证明： 设X(0),Y(0)分别为(L)，(D)的可行解,由弱对偶定理，对于(L)的任意可行解X，有CTX bTY(0)，所以CTX在可行域内有上界，故(L)有最优解。 同理，对于(D)的任意可行解Y，有bTY CTX(0)，所以bTY在可行域内有下界，故(D)有最优解。,设(L)的最优解为X(0)，且X

10、(0)所对应的最优基为B， X(0)可以表示为X(0) = XB(0) = B-1b XN(0) 0,19,则(AT,ST)= (CT,0T) CBTB-1(A, I) 0 由于CTCBTB-1A0， 所以CBTB-1A CT 即AT(CBTB-1)TC (1) 又0TCBTB-1I 0，故(CBTB-1)T0. (2),令Y(0)=(CBTB-1)T，由(1) (2)知Y(0)是(D)的可行解. 因为CTX(0)=(CBT, CNT) XB(0) =CBT XB(0)+CNT XN(0) = CBTB-1b XN(0) 而bTY(0) =bT(CBTB-1)T = CBTB-1b 则CTX(

11、0)=bTY(0)，由最优性准则知， X(0),Y(0)分别为(L)，(D)的最优解, 且目标函数最优值相等。,20,推论： 在用单纯形法求解LP问题(L)的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题(D)的最优解。,证明：因为sT=0T-CBTB-1I= -CBTB-1 y*T=CBTB-1 所以 y*= -s,例5 求下列问题对偶问题的最优解,Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0,解：化为标准型,Max Z =2x1+3x2+0 x3+0 x4+0 x5 s.t. x1+ 2x2+x3 = 8 4x1 +x4 =

12、16 4x2 +x5=12 x1 ,x2 , x3, x4, x50,21,此时达到最优解X*=(4, 2)T, Max Z=14。 对偶问题的最优解为Y*=(3/2, 1/8, 0)T,运用单纯形法计算得原问题的最终表如下：,22,定理4（互补松弛定理）在最优情况下，原问题的第i个决策变量与其对偶问题第i个约束中的松弛变量的乘积恒为零。,设X(0),Y(0)分别为(L),(D)的可行解，则X(0),Y(0)分别为(L),(D)的最优解的充要条件为 ,有,23,例6 考虑下面问题,Max Z = x1+2x2+3x3+3x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3

13、+2x4 20 x1,x2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,已知(D)的最优解为 Y*=(6/5,1/5)T 用互补松弛定理求出(L)的最优解。,24,所以x1*=x2*=0.,解：由于y1* 0, y2* 0,由互补松弛性知,解得x3*= x4*=4. 所以(L)的最优解为X*=(0,0,4,4)T,因为,代入(1),(2)得,25,若X*,Y* 分别为(L),(D)的最优解，那么CTX*=bTY* 。 由 Z*= bTY* =b1y1*+b2y2*+bmym* 可知 Z

14、*/ bi = yi* yi*表示资源量bi 变化1个单位对目标函数最优值Z 产生的影响，称之为第i 种资源的影子价格。,第三节 对偶问题的经济解释-影子价格,一、影子价格,1.定义 影子价格是最优配置下资源的理想价格。,2.含义,26,-14 0 0 -3/2 -1/8 0,例7 下面是一张LP问题的最优单纯形表，其中x3, x4, x5为松弛变量,则对偶问题的最优解为Y*=(1.5, 0.125, 0)T,27,例8,X* =(4, 2)T，Z* =14,Q(4, 2) Z=14,x1,x2,4x1=16,4x2=12,x1+2x2=8,4,4,0,8,3,Q(4.25, 1.875) Z

15、=14.125,Q(4, 2.5) Z=15.5,Q(4, 2) Z=14,Max Z =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0,8,X1* =(4, 2.5)T，Z1*=15.5,X2* =(4.25, 1.875)T，Z2* =14.125,X3* =(4, 2)T，Z3* =14,28,（1）告诉管理者增加何种资源对企业更有利；,（2）告诉管理者花多大代价买进资源或卖出资源是合适的； （3）为新产品定价提供依据。,二、影子价格的作用,29,一、对偶单纯形法的步骤,(1)化LP问题的约束条件为“”形式,引入松弛变量,建立初始表; (2)若所

16、有常数项bi0，则最优解已经达到，否则bl=Minbi|bi0， 选取bl所对应的变量为出基变量； (3)计算k=Minj /alj |alj0，选取k所对应的变量为进基变量； (4)以alk为主元素进行旋转运算，转第二步。,第四节 对偶单纯形法,30,例9 用对偶单纯形法求解下列LP问题,解：原问题变形为,Min Z = x1+2x2+3x3 s.t. x1 -x2+ x34 x1+x2+2x38 x2 - x32 x1, x2, x30,Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3-4 x1+x2+2x38 -x2+ x3-2 x1, x2, x30,Max Z

17、 = -x1-2x2-3x3 s.t. -x1+x2 - x3+x4 =-4 x1+x2+2x3 +x5 = 8 -x2+ x3 +x6=-2 x1, x2, x3, x4, x5, x60,二、对偶单纯形法的算例,31,0 x4 0 x5 0 x6,-4 8 -2,-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1,0 -1 -2 -3 0 0 0,4 0 -3 -2 -1 0 0,-1 -2 -3 0 0 0,32,10 0 0 -5 -1 0 -3,33,三、几个问题的讨论,1.对偶单纯形法只适用于具有正则解的LP问题。 正则解：若LP问题存在基解X，且对应于此

18、 基解的检验数均0(对于极大化问题)，则称X为LP问题的正则解。 2.若最小比值原则失效，则无可行解。 3.对偶单纯形法所包含的创新思想。,34,1.最优性：j cj - CBTB-1Pj0（Max） 2.可行性：XB* B-1b0,二、灵敏度分析常用的两个公式,一、灵敏度分析的定义,三、灵敏度分析的几种可能结果 1.最优解保持不变 2.最优基不变，但最优解改变 3.最优基改变,第五节 线性规划的灵敏度分析,35,1.直接用单纯形表求B-1,四、右端项 b 的变化分析求B-1,由AXb AX+IXS=b （初始表）,两边左乘B-1得 B-1AX+ B-1XS= B-1b （最优表）,例1 LP

19、问题,Max Z =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0,的初始单纯形表和最优单纯形表如下,36,最优表：,四、右端项 b 的变化分析求B-1,初始表：,37,2.公式推导,假设b只有一个分量br 发生变化，br=br+br， 则B1(b+b )B-1b +B-1b,四、右端项 b 的变化分析公式推导,38,即,则,解不等式组得 br 的变化范围：,注：(1) 此时最优基不变，但最优解发生改变。 (2) 此变化范围仅适用于b 的一个分量发生变化的情形。,四、右端项 b 的变化分析公式推导,39,例2 下面是求解同一LP问题的初始单纯形表和最优

20、单纯形表，求b1,b2,b3的变化范围，使原最优基不变。,初始表,最优表,四、右端项 b 的变化分析例题,40,解：,41,例3 下面是某LP问题的单纯形表，x4, x5为松弛变量。,（1）求的取值范围，使得原最优基仍为最优基； （2）求为何值时，使得原最优基不变而目标函数值最大。,假设原来的b被 b + b* 代替，其中b* = 1 -1,四、右端项 b 的变化分析例题,42,解: (1) B-1= 3 -1 -1 1,所以 -1/41。,XB* = B-1 b = B-1 ( b + b* ) = B-1b +B-1 - = 1 + 3 -1 2 -1 1 - = 1+4 0 2 -2,当

21、1时，Z*=10，达到最大。,43,例4 下面是一张LP问题的最优单纯形表,观察其目标函数系数的改变对检验数的影响,五、价值系数 C 的变化分析,cj 的变化会引起检验数j= cj -CBTB-1Pj 的变化,有两种情况: 非基变量的价值系数cj 变化，不影响其它检验数. 基变量的价值系数cj 变化，影响所有非基变量检验数.,44,1.非基变量价值系数的改变,若非基变量的价值系数cj 变为cj = cj +cj ，,讨论： (1)当j0，即cj -j 时，原最优解不变； (2)当j 0，即cj -j 时，原最优解改变。,五、价值系数 C 的变化分析公式推导,则xj 的检验数为,45,例5 Max Z = -2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1, x2, x3, x4, x5 0,五、价值系数 C 的变化分析例题,最优单纯形表为,为使原最优解不变，求 c3 的变化范围。,46,解：最优单纯形表为,从表中看到3=-9/5+c3 ,可见,当c3 9/5 ，即 c3 -