对偶理论与灵敏度分析

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),

8、Y(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,

9、y20,由于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)，

10、且X(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 则CT

11、X(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+

13、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,已知(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* 可

14、知 Z*/ 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

15、) Z=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|bi -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 -49/5-11/5时，原最优解不变。,47,2. 基变量价值系数的

17、改变,五、价值系数 C 的变化分析公式推导,若基变量的价值系数 变为 则,即,48,例6 下表为最优单纯形表,计算 c2 变化的范围，使得原最优解不变。,五、价值系数 C 的变化分析例题,49,当-3c21，即 0c24 时，原最优解不变。,50,1.增减变量,(2)删除变量 删除非基变量最优解不变 删除基变量的处理方法： 将xj 的系数cj 变为-M，迫使xj0,(1)增加变量 若所增加变量的检验数0，则原最优解不变； 否则，用单纯形法迭代求最优解。,六、技术矩阵 A 的变化分析,51,2.Pj 的变化,则最优解不变,则原最优解改变,六、技术矩阵 A 的变化分析,52,3.增减约束条件,(1)删除约束条件,当n+10,n+20时最优解不变;否则,运用单纯形法迭代求最优解。,六、技术矩阵 A 的变化分析,53,(2)增加约束条件,六、技术矩阵 A 的变化分析,化约束条件为的形式，引入松弛变量xn+1； 把增加的约束