运筹学——2.对偶理论和灵敏度分析

*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 线性规划的对偶理论,窗含西岭千秋雪，门泊东吴万里船,本章主要内容,：,线性规划的对偶问题概念、理论及经济意义,线性规划的对偶单纯形法,线性规划的灵敏度分析,1,第一节 对偶问题的提出,材料,产品,甲,乙,丙,丁,单件,收益,A,3,2,1,1,2000,B,4,1,3,2,4000,C,2,2,3,4,3000,限额,600,400,300,200,假设工厂考虑不进行生产而把全部资源都转让，问如何定价这些资源，既能使其获利不低于安排生产所获得的收益，又能使资源租让具有竞争力。,一、引例,Max,Z,= 2000,x,1,+4000,x,2,+3000,x,3,s.t. 3,x,1,+4,x,2,+2,x,3,600,2,x,1,+,x,2,+2,x,3,400,x,1,+,3,x,2,+3,x,3,300,x,1,+2,x,2,+4,x,3,200,x,1, x,2,x,3,0,Min,W,=600,y,1,+400,y,2,+300,y,3,+200,y,4,s.t. 3,y,1,+2,y,2,+,y,3,+,y,4,2000,4,y,1,+,y,2,+3,y,3,+2,y,4,4000,2,y,1,+,2,y,2,+3,y,3,+4,y,4,3000,y,1, y,2,y,3,y,4,0,x,1,x,2,x,3,y,1,y,2,y,3,y,4,2,二、对偶问题,（,1,）对称,LP,问题的定义,（,2,）对称,LP,问题的对偶问题,第一类对称形式,第二类对称形式,3,例,1,写出下列,LP,问题的对偶问题,对偶,Max,Z,=2,x,1,+3,x,2,s.t.,x,1,+ 2,x,2,8,4,x,1, 16,4,x,2, 12,x,1,x,2,0,Min,W,=8,y,1,+16,y,2,+12,y,3,s.t.,y,1,+4,y,2,2,2,y,1,+4,y,3,3,y,1,y,2,y,3,0,4,（,3,）对偶问题的对偶是原问题,推导过程,变形,对偶,变,形,对偶,对偶,变,形,Max,Z=C,T,X,s.t.,AX,b,X,0,Min,W,=,b,T,Y,s.t.,A,T,Y,C,Y,0,Max,W,= -,b,T,Y,s.t. -,A,T,Y, -,C,Y,0,Min,Z,= -,C,T,X,s.t. -(,A,T,),T,X, -,b,X,0,5,例,2,写出下列,LP,问题的对偶问题,解,:,上述,LP,问题的,对偶问题为：,6,三、非对称,LP,问题的对偶问题,例,3,写出下列,LP,问题的对偶问题,解：用,x,2,= -,x,2,x,3,=,x,3,-,x,3,代入上述,LP,问题，并将其,化为第一类对称形式,Max,Z,=,x,1,+2,x,2,+,x,3,x,1,+,x,2,-,x,3,2,s.t.,x,1,-,x,2,+,x,3,= 1,2,x,1,+,x,2,+,x,3,2,x,1,0, x,2,0,x,3,无约束,Max,Z,=,x,1,-2,x,2,+,x,3,-,x,3,x,1,-,x,2,-,x,3,+,x,3, 2,x,1,+,x,2,+,x,3,-,x,3,1,s.t.,-x,1,-,x,2,-,x,3,+,x,3,-1,-,2,x,1,+,x,2,-,x,3,+,x,3,-2,x,1, x,2,x,3,x,3,0,7,上述第一类对称形式,LP,问题的对偶问题为：,则上述问,题变为：,Min,W,=2,y,1,+,y,2,-,y,3,-2,y,4,y,1,+,y,2,-,y,3,-2,y,4, 1,-,y,1,+,y,2,-,y,3,+,y,4,-2,s.t. -,y,1,+,y,2,-,y,3,-,y,4, 1,y,1,-,y,2,+,y,3,+,y,4,-1,y,1, y,2,y,3,y,4,0,Min,W,=2,u,1,+,u,2,+2,u,3,u,1,+,u,2,+2,u,3,1,s.t.,u,1,-,u,2,+,u,3,2,-,u,1,+,u,2,+,u,3,=1,u,1,0, u,3,0,u,2,无约束,令,u,1,=,y,1,u,2,=,y,2,-,y,3,u,3,=-,y,4,8,(D),Min,W,=2,u,1,+,u,2,+2,u,3,u,1,+,u,2,+2,u,3,1,s.t.,u,1,-,u,2,+,u,3,2,-,u,1,+,u,2,+,u,3,=1,u,1,0, u,3,0,u,2,无约束,(L),Max,Z,=,x,1,+2,x,2,+,x,3,x,1,+,x,2,-,x,3,2,s.t.,x,1,-,x,2,+,x,3,= 1,2,x,1,+,x,2,+,x,3,2,x,1,0, x,2,0,x,3,无约束,对偶关系：,一个问题第,i,个变量的约束情况决定另一问题第,i,个约束不等式的方向，反之亦然。,正常的对正常的，不正常的对不正常的,9,例,3,直接写出,LP,问题的对偶问题,10,11,第二节,LP,问题的对偶理论,若,X,(0),Y,(0),分别为,(L),(D),的可行解，则有,C,T,X,(0),b,T,Y,(0),定理,1(,弱对偶定理,):,极大化原问题目标函数值总是不大于其对偶问题的目标函数值。,证明：,由于,X,(0),是,(L),的可行解，有,AX,(0),b,X,(0),0.,由于,Y,(0),是,(D),的可行解，有,Y,(0),0.,Y,(0)T,左乘不等式组,AX,(0),b,的两边得：,Y,(0)T,AX,(0),Y,(0)T,b.,两边同时转置得,X,(0)T,A,T,Y,(0),b,T,Y,(0),（,1,）,12,又,A,T,Y,(0),C,X,(0)T,0.,所以,X,(0)T,A,T,Y,(0),X,(0)T,C = C,T,X,(0),(2),由（,1,），（,2,）,得：,C,T,X,(0),b,T,Y,(0),13,推论,1,若,LP,问题有无界解，则其对偶问题无可行解；,若,LP,问题无可行解，则对偶问题或有无界解或无可行解。,推论,2,极大化问题的任何一个可行解所对应的目标,函数值都是其对偶问题目标函数值的下界。,极小化问题的任何一个可行解所对应的目标,函数值都是其对偶问题目标函数值的上界。,推论,3,14,例,4,考虑下面一对,LP,问题,其对偶问题为：,由于,X,(0),=(1,1,1,1),T,Y,(0),=(1,1),T,分别为,(L),(D),的可行解，故,Z,40,W,10.,Max,Z,=,x,1,+2,x,2,+3,x,3,+4,x,4,x,1,+2,x,2,+2,x,3,+3,x,4,20,s.t. 2,x,1,+,x,2,+3,x,3,+2,x,4,20,x,1,x,2,x,3,x,4,0,Min,W =,20,y,1,+20,y,2,y,1,+2,y,2, 1,2,y,1,+,y,2, 2,s.t.,2,y,1,+3,y,2, 3,3,y,1,+2,y,2, 4,y,1,y,2,0,15,定理,2,（最优性准则）,当,LP,问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。,若,X,(0),Y,(0),分别为,(L),，,(D),的可行解,且,C,T,X,(0),b,T,Y,(0),，,则,X,(0),Y,(0),分别为,(L),，,(D),的最优解。,证明：,由定理,1,可知，对于,(L),的任意可行解,X,，有,C,T,X,b,T,Y,(0),由于,C,T,X,(0),=,b,T,Y,(0),，故,X,(0),为,(L),的最优解。,同理,Y,(0),为,(D),的最优解。,16,例,5,Max,Z,=,x,1,+2,x,2,+3,x,3,+4,x,4,x,1,+2,x,2,+2,x,3,+3,x,4,20,s.t. 2,x,1,+,x,2,+3,x,3,+2,x,4,20,x,1,x,2,x,3,x,4,0,Min,W =,20,y,1,+20,y,2,y,1,+2,y,2, 1,2,y,1,+,y,2, 2,s.t.,2,y,1,+3,y,2, 3,3,y,1,+2,y,2, 4,y,1,y,2,0,由于,X,(0),=(0,0,4,4),T,Y,(0),=(6/5,1/5),T,是,(L),，,(D),的,可行解且,CX,(0),=,b,T,Y,(0),=28,，所以,X,(0),Y,(0),分别为,(L),，,(D),的最优解。,17,定理,3,（强对偶定理）,若,(L),，,(D),均有可行解，则,(L),，,(D),均有最优解，,且目标函数最优值相等。,证明：,设,X,(0),Y,(0),分别为,(L),，,(D),的可行解,由弱对偶定理，对于,(L),的任意可行解,X,，有,C,T,X,b,T,Y,(0),，所以,C,T,X,在可行域内有上界，故,(L),有最优解。,同理，对于,(D),的任意可行解,Y,，,有,b,T,Y,C,T,X,(0),，所以,b,T,Y,在可行域内有下界，故,(D),有最优解。,设,(L),的最优解为,X,(0),，且,X,(0),所对应的最优基为,B,，,X,(0),可以表示为,X,(0),=,X,B,(0),=,B,-1,b,X,N,(0),0,18,则,(,A,T,S,T,)=,(,C,T,0,T,) ,C,B,T,B,-1,(,A,I,),0,由于,C,T,C,B,T,B,-1,A,0,，,所以,C,B,T,B,-1,A,C,T,即,A,T,(,C,B,T,B,-1,),T,C,(1),又,0,T,C,B,T,B,-1,I,0,，,故,(,C,B,T,B,-1,),T,0,. (2),令,Y,(0),=(,C,B,T,B,-1,),T,，,由,(1),(2),知,Y,(0),是,(D),的可行解,.,因为,C,T,X,(0),=(,C,B,T,C,N,T,),X,B,(0),=,C,B,T,X,B,(0),+,C,N,T,X,N,(0),=,C,B,T,B,-1,b,X,N,(0),而,b,T,Y,(0),=,b,T,(,C,B,T,B,-1,),T,=,C,B,T,B,-1,b,则,C,T,X,(0),=,b,T,Y,(0),，由最优性准则知，,X,(0),Y,(0),分别为,(L),，,(D),的最优解,且目标函数最优值相等。,19,推论：,在用单纯形法求解,LP,问题,(L),的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题,(D),的最优解。,证明：因为,s,T,=,0,T,-,C,B,T,B,-1,I,=,-C,B,T,B,-1,y,*,T,=,C,B,T,B,-1,所以,y,*= -,s,例,5,求下列问题对偶问题的最优解,Max,Z,=2,x,1,+3,x,2,s.t,.,x,1,+ 2,x,2,8,4,x,1, 16,4,x,2, 12,x,1,x,2,0,解：化为标准型,Max,Z,=2,x,1,+3,x,2,+0,x,3,+0,x,4,+0,x,5,s.t.,x,1,+ 2,x,2,+,x,3,= 8,4,x,1,+,x,4,=16,4,x,2,+,x,5,=12,x,1,x,2,x,3,x,4,x,5,0,20,c,j,2 3 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,0,x,5,3,x,2,4,4,2,1 0 0 1/4 0,0 0 -2 1/2 1,0 1 1/2 -1/8 0,-14,0 0 -3/2 -1/8 0,此时达到最优解,X,*,=(4, 2),T, Max,Z,=14,。,对偶问题的最优解为,Y,*,=(3/2, 1/8, 0),T,运用单纯形法计算得原问题的最终表如下：,21,定理,4,（互补松弛定理）,在最优情况下，原问题的第,i,个决策变量与其对偶问题第,i,个约束中的松弛变量的乘积恒为零,。,设,X,(0),Y,(0),分别为,(L),(D),的,可行解，则,X,(0),Y,(0),分别为,(L),(D),的最优解的充要条件为,有,m,(1),若,x,l,(0),0,，,则,a,il,y,i,(0),=,C,l,i,=1,m,(2),若,a,il,y,i,(0),C,l,，,则,x,l,(0),= 0,i,=1,n,(3),若,y,k,(0),0,，,则,a,kj,x,j,(0),=,b,k,j,=1,n,(4),若,a,kj,x,j,(0), 0,y,2,* 0,由互补松弛性知,解得,x,3,*=,x,4,*=4.,所以,(L),的最优解为,X*=(0,0,4,4),T,因为,代入,(1),(2),得,24,若,X*,Y*,分别为,(L),(D),的最优解，那么,C,T,X*=b,T,Y*,。,由,Z*=,b,T,Y*,=b,1,y,1,*+b,2,y,2,*+,+,b,m,y,m,*,可知,Z,*/ ,b,i,=,y,i,*,y,i,*,表示资源量,b,i,变化,1,个单位对目标函数最优值,Z,产生的影响，称之为,第,i,种资源的影子价格,。,第三节 对偶问题的经济解释,-,影子价格,一、影子价格,1.,定义,影子价格是最优配置下资源的理想价格。,2.,含义,25,1 0 0 1/4 0,0 0 -2 1/2 1,0 1 1/2 -1/8 0,4,4,2,2,x,1,0,x,5,3,x,2,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,2 3 0 0,0,c,j,-14 0 0 -3/2 -1/8 0,例,7,下面是一张,LP,问题的最优单纯形表，其中,x,3,x,4,x,5,为松弛变量,则对偶问题的最优解为,Y,*=(1.5, 0.125, 0),T,26,例,8,X* =,(4, 2),T,，,Z,* =14,Q(4, 2),Z,=14,x,1,x,2,4,x,1,=16,4,x,2,=12,x,1,+2,x,2,=8,4,4,0,8,3,Q(4.25, 1.875),Z,=14.125,Q(4, 2.5),Z,=15.5,Q(4, 2),Z,=14,Max,Z,=2,x,1,+3,x,2,x,1,+ 2,x,2,8,s.t,. 4,x,1, 16,4,x,2, 12,x,1,x,2,0,8,X,1,* =,(4, 2.5),T,，,Z,1,*=15.5,X,2,* =,(4.25, 1.875),T,，,Z,2,* =14.125,X,3,* =,(4, 2),T,，,Z,3,* =14,27,（,1,）告诉管理者增加何种资源对企业更有利；,c,j,2 3 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,0,x,5,3,x,2,4,4,2,1 0 0 1/4 0,0 0 -2 1/2 1,0 1 1/2 -1/8 0,-14,0 0 -3/2 -1/8 0,（,2,）告诉管理者花多大代价买进资源或卖出资源是合适的；,（,3,）为新产品定价提供依据。,二、影子价格的作用,28,一、对偶单纯形法的步骤,(1),化,LP,问题的约束条件为,“,”,形式,引入松弛变量,建立初始表,;,(2),若所有常数项,b,i,0,，则最优解已经达到，否则,b,l,=,Min,b,i,|,b,i,0,，,选取,b,l,所对应的变量为出基变量；,(3),计算,k,=,Min,j,/,a,lj,|,a,lj,0,，即,c,j,-,j,时，原最优解改变。,五、价值系数,C,的变化分析,公式推导,则,x,j,的检验数为,47,例,6,Max,Z,= -2,x,1,- 3,x,2,- 4,x,3,s.t,.,-,x,1,-2,x,2,-,x,3,+,x,4,= - 3,-2,x,1,+,x,2,-3,x,3,+,x,5,= - 4,x,1,x,2,x,3,x,4,x,5,0,五、价值系数,C,的变化分析,例题,最优单纯形表为,c,j,-2,-3,-4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,-3,x,2,2/5,0,1,-1/5,-2/5,1/5,-2,x,1,11/5,1,0,7/5,-1/5,-2/5,j,0,0,-9/5,-8/5,-1/5,为使原最优解不变，求,c,3,的变化范围。,48,解：最优单纯形表为,从表中看到,3,=-9/5+,c,3,可见,当,c,3, 9/5,，即,c,3,-4,9/5,-11/5,时，原最优解不变。,c,j,-2,-3,-4,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,-3,x,2,2/5,0,1,-1/5,-2/5,1/5,-2,x,1,11/5,1,0,7/5,-1/5,-2/5,j,0,0,-9/5,-8/5,-1/5,c,j,-2,-3,-4+,c,3,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,-3,x,2,2/5,0,1,-1/5,-2/5,1/5,-2,x,1,11/5,1,0,7/5,-1/5,-2/5,j,0,0,-9/5+,c,3,-8/5,-1/5,49,2.,基变量价值系数的改变,五、价值系数,C,的变化分析,公式推导,若基变量的价值系数,变为 则,即,50,例,7,下表为最优单纯形表,计算,c,2,变化的范围，使得原最优解不变。,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,4,1,0,0,1/4,0,0,x,5,4,0,0,-2,1/2,1,3,x,2,2,0,1,1/2,-1/8,0,j,0,0,-3/2,-1/8,0,五、价值系数,C,的变化分析,例题,51,当,-3,c,2,1,，,即,0,c,2,4,时，原最优解不变。,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,4,1,0,0,1/4,0,0,x,5,4,0,0,-2,1/2,1,3,x,2,2,0,1,1/2,-1/8,0,j,0,0,-3/2,-1/8,0,c,j,2,3+,c,2,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,4,1,0,0,1/4,0,0,x,5,4,0,0,-2,1/2,1,3+,c,2,x,2,2,0,1,1/2,-1/8,0,j,0,0,-3/2 -,c,2,/2,-1/8+,c,2,/8,0,52,1.,增减变量,(2),删除变量,删除非基变量最优解不变,删除基变量的处理方法：,将,x,j,的系数,c,j,变为,-,M,，迫使,x,j,0,(1),增加变量,若所增加变量的检验数,0,，则原最优解不变；,否则，用单纯形法迭代求最优解。,六、技术矩阵,A,的变化分析,53,2.,P,j,的变化,则最优解不变,则原最优解改变,六、技术矩阵,A,的变化分析,54,3.,增减约束条件,(1),删除约束条件,当,n,+,1,0,n,+2,0,时最优解不变,;,否则,运用单纯形法迭代求最优解。,六、技术矩阵,A,的变化分析,55,(2),增加约束条件,六、技术矩阵,A,的变化分析,化约束条件为,的形式，引入松弛变量,x,n+,1,；,把增加的约束条件直接写入最优表,(,以松弛变量,x,n+,1,为基变量,),，得到一个非标准表；,化非标准表为标准表，若,b,n+,1,，则最优解仍为最优解，,若,b,n+,1,，则用对偶单纯形法迭代找出最优解。,56,c,j,2,3,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,1,1,0,-1,3,-1,3,x,2,2,0,1,2,-1,1,j,-8,0,0,-3,-3,-1,例,8,已知某,LP,问题的最优单纯形表如下：,如果增加约束条件,x,1,+,x,3,2,，,最优解将如何变化？,六、技术矩阵,A,的变化分析,57,c,j,2,3,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,1,1,0,-1,3,-1,3,x,2,2,0,1,2,-1,1,0,-8,0,0,-3,-3,-1,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,1,1,0,-1,3,-1,0,3,x,2,2,0,1,2,-1,1,0,0,x,6,-1,0,0,-2,3,-1,1,-8,0,0,-3,-3,-1,0,x,6,-2,-1,0 -1 0 0,0,x,6,0 0 1,非标准表,标准表,x,1,+,x,3,2,-,x,1,-,x,3,+,x,6,= -2,58,c,j,2,3,1,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,2,1,0,1,0,0,-1,3,x,2,1,0,1,0,2,0,1,0,x,5,1,0,0,2,-3,1,-1,-7,0,0,-1,-6,0,-1,59,c,j,2,3,1,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,2,x,1,1,1,0,-1,3,-1,3,x,2,2,0,1,2,-1,1,-8,0,0,-3,-3,-1,课堂练习,下面是某,LP,问题的最优单纯形表，当增加约束条件,x,1,+,x,2,4,时,，最优解如何变化？,60,c,j,2,3,1,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,1,1,0,-1,3,-1,0,3,x,2,2,0,1,2,-1,1,0,0,x,6,4,1,1,0,0,0,1,-8,0,0,-3,-3,-1,0,c,j,2,3,1,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,1,1,1,0,-1,3,-1,0,3,x,2,2,0,1,1,-1,1,0,0,x,6,1,0,0,-1,-2,0,1,-8,0,0,0,-3,-1,0,原最优解不变,61,