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

*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 线性规划的对偶理论,窗含西岭千秋雪，门泊东吴万里船,本章主要内容,：,线性规划的对偶问题概念、理论及经济意义,线性规划的对偶单纯形法,线性规划的灵敏度分析,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.,两个问题，一个是极大化，另一个是极小化；,2.,一个问题的,变量,数等于另一问题的,方程,数，反之亦然；,3.,一个问题的,目标,函数系数是另一个问题的约束方程,右端,常数，反之亦然；,4.,两个问题的约束方程系数矩阵互为转置。,称变量,y,i,为第,一个,LP,的第,i,个对偶变量，,或第,一个,LP,的第,i,约束相应的对偶变量,3,二、对偶问题,（,1,）对称,LP,问题的定义,（,2,）对称,LP,问题的对偶问题,第一类对称形式,第二类对称形式,（,1,）变量为非负；,（,2,）约束条件为不等式。,对于,max,，约束为“,”；,对于,min,，约束为“”,4,例,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,5,三、非对称,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,x,1,-,x,2,+,x,3,1,x,1,-,x,2,+,x,3,1,x,1,-,x,2,+,x,3,1,-x,1,+,x,2,-,x,3,-,1,-2,x,1,-,x,2,-,x,3,-,2,8,上述第一类对称形式,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,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,-,y,1,+,y,2,-,y,3,-,y,4,1,y,1,-,y,2,+,y,3,-,y,4,2,9,(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,个约束不等式的方向，反之亦然。,正常的对正常的，不正常的对不正常的,原问题约束条件是等式对应于对偶问题决策变量无约束，反之亦然,10,例,3,直接写出,LP,问题的对偶问题,11,12,原问题,对偶问题,目标函数,Max z,Min w,变量,n,个,约束条件,n,个,=,0,0,无约束,约束条件,m,个,=,变量,m,个,0,0,无约束,约束条件右端项,目标函数变量的系数,目标函数变量的系数,约束条件右端项,原问题,对偶问题,13,第二节,LP,问题的对偶理论,若,X,(0),Y,(0),分别为,(L),(D),的可行解，则有,CX,(0),Y,(0),b,定理,1(,弱对偶定理,):,极大化原问题目标函数值总是不大于其对偶问题的目标函数值。,证明：,max z=CX;AX,b;X,0(L),min w=Yb;YAC;Y0(D),由于,X,(0),是,(L),的可行解，有,AX,(0),b,X,(0),0.,由于,Y,(0),是,(D),的可行解，有,Y,(0),0.,Y,(0),左乘不等式组,AX,(0),b,的两边得：,Y,(0),AX,(0),Y,(0),b,(1),14,min w=Yb;YAC;Y0(D),又,Y,(0),A,C,用,X,(0),(,X,(0),0),右乘上式，得,Y,(0),AX,(0),CX,(0),(2),由（,1,），（,2,）,得：,CX,(0),Y,(0),AX,(0),Y,(0),b,所以,CX,(0),Y,(0),b,15,推论,1,若对偶问题有无界解，则其原问题无可行解；,若对偶问题无可行解，则其原问题或有无界解或无可行解。,x,2,x,1,1,1,-1,-1,y,2,y,1,1,1,-1,-1,原问题,对偶问题,若,LP,问题有无界解，则其对偶问题无可行解,(,弱对偶性,),；,若,LP,问题无可行解，则对偶问题或有无界解或无可行解。,16,推论,2,极大化问题（,L,）的任何一个可行解所对应的目标函数值都是其对偶问题,（,D,）,目标函数值的下界。,极小化问题（,D,）的任何一个可行解所对应的目标,函数值都是其对偶问题,（,L,）,目标函数值的上界。,推论,3,Yb,C,X,(0),CX,Y,(0),b,max z=CX;AX,b,;,X,0(L),min w=Yb;YAC;Y0(D),17,例,4,考虑下面一对,LP,问题,其对偶问题为：,由于,X,(0),=(1,1,1,1),T,Y,(0),=(1,1),T,分别为,(L),(D),的可行解，,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,Z,(0),=10,W,(0),=40,W,10,推论,2,Z,40,推论,3,故,Z,40,W,10.,18,例,试用对偶理论证明上述线性规划问题无最优解,证明：首先看到该问题存在可行解，如,X=(0,0,0),上述问题的对偶问题为,由第一约束条件知对偶问题无可行解，因原问题有可行解，由推论,1,，原问题无最优解。,若对偶问题无可行解，,则原问题或有无界解,或无可行解。,19,定理,2,（最优性准则）,当,LP,问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。,若,X,(0),Y,(0),分别为,(L),，,(D),的可行解,且,CX,(0),Y,(0),b,则,X,(0),Y,(0),分别为,(L),，,(D),的最优解。,证明：,由定理,1,可知，对于,(L),的任意可行解,X,，有,CX,Y,(0),b,由于,CX,(0),=,Y,(0),b,，,CX,CX,(0),，,故,X,(0),为,(L),的最优解；,同理，,由定理,1,可知，,对于,(D),的任意可行解,Y,，有,YbC,X,(0),，,由于,CX,(0),=,Y,(0),b,，,Yb,Y,(0),b,，,Y,(0),为,(D),的最优解。,20,例,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),的最优解。,21,线性规划的矩阵表示,Max,Z,=,CX,s.t.,AX,b,X,0,令,A,=(,B,N,),X,=,X,B,C,=(,C,B,C,N,),X,N,由,AX+IX,s,=b (,B,N,I,),X,B,=,b,BX,B,+,NX,N,+IX,s,=,b,BX,B,=,b-NX,N,-IX,s,X,N,X,s,X,B,=,B,-1,b,-,B,-1,NX,N,-,B,-1,X,s,(1),将,(1),式代入目标函数得,Z,=,CX,=(,C,B,C,N,),X,B,=,C,B,X,B,+,C,N,X,N,=,C,B,(,B,-1,b,-,B,-1,NX,N,-,B,-1,X,s,)+,C,N,X,N,X,N,=,C,B,B,-1,b,+(,C,N,-,C,B,B,-1,N,),X,N,-,C,B,B,-1,X,s,(2),Max,Z,=,CX+,0,X,s,s.t.,AX+IX,s,=,b,X,X,s,0,用非基变量表示基变量,用非基变量表示目标函数,22,=(0,C,N,-,C,B,B,-1,N,-,C,B,B,-1,)=(,C,-,C,B,B,-1,A,-,C,B,B,-1,),(,C,-,C,B,B,-1,A,-,C,B,B,-1,)=(,C,-,C,B,B,-1,(,B,N,),-,C,B,B,-1,),=(,C,B,-,C,B,B,-1,B,C,N,-,C,B,B,-1,N,-,C,B,B,-1,),=(0,C,N,-,C,B,B,-1,N,-,C,B,B,-1,),若,C,N,-,C,B,B,-1,N,0,-,C,B,B,-1,0,则,Z,为最优解,令,X,N,=0,X,s,=0,，,可以得到基,B,的基可行解和目标函数值,X,B,=,B,-1,b,-,B,-1,NX,N,-,B,-1,X,s,Z,=,C,B,B,-1,b,+(,C,N,-,C,B,B,-1,N,),X,N,-,C,B,B,-1,X,s,X,=(,X,B,X,N,X,s,)=(,B,-1,b,0,0),Z,=,C,B,B,-1,b,23,C,C,B,X,B,b,X,B,X,N,X,S,-Z,C,B,X,B,B,-1,b,C,B,C,N,0,I,C,N,-,C,B,B,-1,N,B,-1,N,B,-1,0,-,C,B,B,-1,-C,B,B,-1,b,24,初始单纯形表,c,j,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,j,c,j,2 3 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,0,x,4,3,x,2,2,16,3,1 0 1 0 -1/2 2,4 0 0 1 0 4,0 1 0 0 1/4 -,j,-9,2 0 0 0 -3/4,0,x,3,0,x,4,0,x,5,2 3 0 0 0,8,16,12,1 2 1 0 0,4 0 0 1 0,0 4 0 0 1,2 3 0 0 0,0,4,-,3,经过一次迭代,初始基,第一轮迭代后的基,P,3,P,4,P,5,1 0 0,0 1 0,0 0 1,B,=,P,3,P,4,P,2,1 0 2,0 1 0,0 0 4,B,=,1 0 -1/2,0 1 0,0 0 1/4,B,-,1,=,25,初始单纯形表,c,j,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,j,c,j,2 3 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,0,x,4,3,x,2,2,16,3,1 0 1 0 -1/2 2,4 0 0 1 0 4,0 1 0 0 1/4 -,j,-9,2 0 0 0 -3/4,0,x,3,0,x,4,0,x,5,2 3 0 0 0,8,16,12,1 2 1 0 0,4 0 0 1 0,0 4 0 0 1,2 3 0 0 0,0,4,-,3,经过一次迭代,1 0 -1/2,0 1 0,0 0 1/4,B,-,1,=,B,-,1,b=,1 0 -1/2,0 1 0,0 0 1/4,8,16,12,2,16,3,=,Z,=,C,B,B,-1,b=,9,26,初始单纯形表,c,j,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,j,c,j,2 3 0 0 0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,0,x,4,3,x,2,2,16,3,1 0 1 0 -1/2 2,4 0 0 1 0 4,0 1 0 0 1/4 -,j,-9,2 0 0 0 -3/4,0,x,3,0,x,4,0,x,5,2 3 0 0 0,8,16,12,1 2 1 0 0,4 0 0 1 0,0 4 0 0 1,2 3 0 0 0,0,4,-,3,经过一次迭代,1 0 -1/2,0 1 0,0 0 1/4,B,-,1,=,B,-1,A=,-,C,B,B,-1,=(0,0,-3/4),A,27,定理,3,（强对偶定理）,若,(L),，,(D),均有可行解，则,(L),，,(D),均有最优解，,且目标函数最优值相等。,证明：,设,X,(0),Y,(0),分别为,(L),，,(D),的可行解,由弱对偶定理,(,推论,3),，对于,(L),的任意可行解,X,，有,CX,Y,(0),b,，所以,CX,在可行域内有上界，故,(L),有最优解。,同理，对于,(D),的任意可行解,Y,，,由弱对偶定理,（推论,2,）,，,有,Y,b,CX,(0),，所以,Yb,在可行域内有下界，故,(D),有最优解。,设,(L),的最优解为,X,(0),，且,X,(0),所对应的最优基为,B,，,X,(0),可以表示为,X,(0),=,X,B,(0),=,B,-1,b,X,N,(0),0,max z=CX;AX,b,;,X,0(L),min w=Yb;YAC;Y0(D),28,则,(,A,S,)=,(,C,0,),C,B,B,-1,(,A,I,)=,(,C,C,B,B,-1,A,C,B,B,-1,),0,由于,C,C,B,B,-1,A,0,，,所以,C,B,B,-1,A,C,(1),又,C,B,B,-1,0,，,故,C,B,B,-1,0,.(2),令,Y,(0),=,C,B,B,-1,，,由,(1),、,(2),知,Y,(0),是,(D),的可行解,.,因为,CX,(0),=(,C,B,C,N,),X,B,(0),=,C,B,X,B,(0),+,C,N,X,N,(0),=,C,B,B,-1,b,X,N,(0),而,Y,(0),b,=,C,B,B,-1,b,则,CX,(0),=,Y,(0),b,，由最优性准则知，,X,(0),Y,(0),分别为,(L),，,(D),的最优解,且目标函数最优值相等。,29,推论：,在用单纯形法求解,LP,问题,(L),的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题,(D),的最优解。,例,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,C,C,B,X,B,b,X,B,X,N,X,S,-Z,C,B,X,B,B,-1,b,C,B,C,N,0,I,C,N,-,C,B,B,-1,N,B,-1,N,B,-1,0,-,C,B,B,-1,-C,B,B,-1,b,Y,*=(,C,B,B,-1,),T,30,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,运用单纯形法计算得原问题的最终表如下：,31,推论：对偶问题的最优解对应于原问题的最优单纯型表中松弛变量检验数的相反数或剩余变量的检验数。,32,Min z=2,x,1,+3,x,2,x,1,+,x,2,350,x,1,125,2,x,1,+,x,2,600,x,1,x,2,0,Max,w,=350,y,1,+125,y,2,+600,y,3,s.t.,y,1,+,y,2,+2,y,3,2,y,1,+,y,3,3,y,1,y,2,0,;y,3,0,c,j,2 3 0 0 0 M M,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,3,x,2,2,x,1,0,x,4,100,250,125,0 1 -2 0 -1 2 0,1 0 1 0 1 -1 0,0 0 1 1 1 -1 -1,原问题的最优单纯型表如下所示：,0 0 4 0 1 -4+M M,Y,*=(4,0,-1),T,w*=,800,例,33,定理,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),得,由互补松弛性知，,37,若,X*,Y*,分别为,(L),(D),的最优解，那么,CX*=Y*b,。,由,Z*=,Y*b,=y,1,*b,1,+y,2,*,b,2,+,+,y,m,*,b,m,可知,Z,*/,b,=,Y,*,y,i,*,=,Z,*/,b,i,y,i,*,表示资源量,b,i,变化,1,个单位对目标函数最优值,Z,产生的影响，称之为,第,i,种资源的影子价格,。,第三节 对偶问题的经济解释,-,影子价格,一、影子价格,(Shadow Price),1.,定义,影子价格是最优配置下资源的理想价格。,2.,含义,对偶问题的最优解实际上就是右端常数项的单位变化所引起的目标值的变化。,38,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,例,8,下面是一张,LP,问题的最优单纯形表，其中,x,3,x,4,x,5,为松弛变量,则对偶问题的最优解为,Y,*=(1.5,0.125,0),T,39,例,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,40,资源进行最优配置后获得的收益,资源,i,的数量,资源,i,的价格,它代表在资源最优利用条件下对,各种单位资源的估价,，这种估价不是资源的市场价格，而是根据资源在企业生产中所作出的贡献而作出的估价，为区别起见，称之为,影子价格,(shadow price),。,41,资源的影子价格是针对具体生产或具体企业而言的：,同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；,A,产品的市场价格发生变化，资源的影子价格也会发生变化；,C,资源的数量结构不同，资源的影子价格也不同。,b,I II,设 备,1 2 8,台时,原材料,A 4 0 16,公斤,原材料,B 0 4 12,公斤,2 3,a,21,=3 (1.5,1/6,0),c,2,=4 (2,0,0),b,1,=10 (0,0.5,0.75),42,（,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,）为新产品定价提供依据。,二、影子价格的作用,43,第四节 对偶单纯形法,正则解：,设,X,(0),是线性规划问题,(Max),的一个基本解，如果它的检验数,j,0(jJ),，则称,X,(0),是该线性规划问题的一个正则解。相应的基称为正则基。,c,j,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,j,0,x,4,0,x,5,0,x,6,-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,-1 -2 -3 0 0 0,正则解若是可行解，则它是最优解。,44,第四节 对偶单纯形法,从一基可行解,(,B,-1,b,0),出发，在满足可行解的基础上，通过逐次基可行解的转换，直至,j,0(,j,J),成立,（对,max,问题）,，即达到可行的正则解，从而判断是否得到最优解或无最优解。,从一正则解,(,j,0(,j,J,),出发,（对,max,问题）,，在满足正则解的基础上，通过逐次转换，直至,B,-1,b,0,成立，即达到满足正则解条件的可行解，从而判断是否得到最优解或无最优解。,单纯形法的基本思想,：,对偶单纯形法的基本思想：,45,例,9,用对偶单纯形法求解下列,LP,问题,解：原问题变形为,Min,Z,=,x,1,+2,x,2,+3,x,3,s.t.,x,1,-,x,2,+,x,3,4,x,1,+,x,2,+2,x,3,8,x,2,-,x,3,2,x,1,x,2,x,3,0,Max,Z,=-,x,1,-2,x,2,-3,x,3,s.t.-,x,1,+,x,2,-,x,3,-4,x,1,+,x,2,+2,x,3,8,-x,2,+,x,3,-2,x,1,x,2,x,3,0,Max,Z,=-,x,1,-2,x,2,-3,x,3,s.t.-,x,1,+,x,2,-,x,3,+x,4,=-4,x,1,+,x,2,+2,x,3,+,x,5,=8,-x,2,+,x,3,+,x,6,=-2,x,1,x,2,x,3,x,4,x,5,x,6,0,一、对偶单纯形法的举例,第一类对称形式,46,c,j,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,j,0,x,4,0,x,5,0,x,6,-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,c,j,-1,-2,-3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,-1,x,1,4,1,-1,1,-1,0,0,0,x,5,4,0,2,1,1,1,0,0,x,6,-2,0,-1,1,0,0,1,j,4 0 -3 -2 -1 0 0,-1 -2 -3 0 0 0,Min-4,，,-2,=Min ,-1,-1,-3,-1,Min-2,=Min ,-3,-1,47,c,j,-1,-2,-3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,-1,x,1,6,1,0,0,-1,0,-1,0,x,5,0,0,0,3,1,1,2,-2,x,2,2,0,1,-1,0,0,-1,j,10 0 0 -5 -1 0 -3,Z,*,=,x,1,*,+2,x,2,*,+3,x,3,*,=10,所以,48,二、对偶单纯形法的步骤,(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,的检验数为,66,例,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,的变化范围。,67,解：最优单纯形表为,从表中看到,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,68,2.,基变量价值系数的改变,五、价值系数,C,的变化分析,公式推导,即,若基变量,的价值系数,变为 则,非基变量,x,j,的检验数由,j,=,c,j,-,C,B,B,-1,P,j,变为,69,2.,基变量价值系数的改变,五、价值系数,C,的变化分析,公式推导,70,例,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,的变化分析,例题,71,当,-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,3,=0-1/2(3+,c,2,)=,-3/2,-,c,2,/2,0,4,=,0-2/4+1/8(3+,c,2,)=-1/8+,c,2,/8,0,72,1.,增减变量,(2),删除变量,删除非基变量最优解不变,删除基变量的处理方法：,将,x,j,的系数,c,j,变为,-,M(,最大化问题,),，迫使,x,j,0,(1),增加变量,若所增加变量的检验数,0,，则原最优解不变；,否则，用单纯形法迭代求最优解。,六、技术矩阵,A,的变化分析,73,例,9,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,I II,设 备,1 2 8,台时,原材料,A 4 0 16,公斤,原材料,B 0 4 12,公斤,2,6,3,利润,(,元,)2 3,5,5,x,3,B,-1,74,例,9,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,5,x,3,1.5,2,0.25,3,=,c,3,-,C,B,B,-1,P,3,=5-(2,0,3)(1.5,2,0.25),T,=1.250,1.25,说明增加产品,的生产，可以提高企业的的收益。,利用单纯形法进行迭代,75,例,9,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,1,1,0,1.5,-0.125,-0.75,5,x,3,2,0,0,-1,0.25,0.5,3,x,2,1.5,0,1,0.75,-0.1875,-0.125,j,0,0,-0.25,-0.4375,-0.625,5,x,3,0,1,0,0,最优生产计划：,生产产品,I 1,件,产品,II 1.5,件,产品,III 2,件,总利润为：,16.5,元。,76,2.,P,j,的变化,则最优解不变,则原最优解改变,六、技术矩阵,A,的变化分析,如生产产品的工艺发生变化,77,例,10,设 备,8,台时,原材料,A 16,公斤,原材料,B 12,公斤,I,2,5,2,利润,(,元,),4,II,2,0,4,3,I,1,4,0,2,c,j,3,0,0,0,C,B,X,B,b,x,2,x,3,x,4,x,5,2,x,1,4,0,0,1/4,0,0,x,5,4,0,-2,1/2,1,3,x,2,2,1,1/2,-1/8,0,j,0,-3/2,-1/8,0,2,x,1,1,0,0,0,4,x,1,78,c,j,3,0,0,0,C,B,X,B,b,x,2,x,3,x,4,x,5,2,x,1,4,0,0,1/4,0,0,x,5,4,0,-2,1/2,1,3,x,2,2,1,1/2,-1/8,0,j,0,-3/2,-1/8,0,4,x,1,1,=,c,1,-,C,B,B,-1,P,1,=4-(2,0,3)(1.25,0.5,0.375),T,=0.3750,利用单纯形法进行迭代,1.25,0.5,0.375,0.375,1.25,79,c,j,3,0,0,0,C,B,X,B,b,x,2,x,3,x,4,x,5,4,x,1,3.2,0,0,0.2,0,0,x,5,2.4,0,-2,0.4,1,3,x,2,0.8,1,0.5,-0.2,0,j,0,-1.5,-0.2,0,4,x,1,1,0,0,0,最优生产计划：,生产产品,I 3.2,件,产品,II 0.8,件,总利润为：,15.2,元,80,六、技术矩阵,A,的变化分析,化约束条件为,的形式，引入松弛变量,x,n+,1,；,把增加的约束条件直接写入最优表,(,以松弛变量,x,n+,1,为基变量,),，得到一个非标准表；,化非标准表为标准表，若,b,n+,1,，则最优解仍为最优解，,若,b,n+,1,，则用对偶单纯形法迭代找出最优解。,3.,增加约束条件,81,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,的变化分析,x,1,*=1,x,2,*=2 Z*=8,82,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,