运筹学第二章电子讲稿1

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 对偶理论与灵敏度分析,1.单纯形表的矩阵描述,max=CX,s.t.AX=b,X0,A=B,N,C=(C,B,C,N,),X=,则有,max=C,B,X,B,+C,N,X,N,x.t.BX,B,+NX,N,=b,X,B,X,N,0,X,B,=B,-1,b-B,-1,NX,N,=C,B,(B,-1,b-B,-1,NX,N,)+C,N,X,N,=C,B,B,-1,b+(C,N,-C,B,B,-1,N)X,N,X,B,X,N,单纯形表,X,B,X,N,X,S,B,-1,b I B,-1,N B,-1,-C,B,B,-1,b 0 C,N,-C,B,B,-1,N -C,B,B,-1,3.对偶问题的提出,原问题：有,n,种食物，每种食物含有,m,种营养成分，第,j,种食物每个单位含第,i,种营养成分为,a,ij,单位。现知每人每天需要第,i,种营养成分为,b,i,单位，第种食物的单价为,c,j,。,试问一个消费者如何选购食物，才能使得既满足需要，又花费最小？,问题归结为,min CX,s.t.AXb,X0,x,j,选购第,j,种食物的数量（单位）,对偶问题：设有一个制造商，要生产,m,种不同的药丸来代替上述,n,种不同的食物。试问每种药丸的价格如何确定，才能获利最大？,设第,i,种药丸的价格为,y,i,，,为了达到畅销的目的，药丸的价格当然不能超过与之相当的食品价格，,于是，问题变成：,max Yb,YAC,Y0,4.线性规划的对偶理论,4.1.原问题与对偶问题的关系,(,P),max=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.a,11,x,1,+a,12,x,2,+a,1n,x,n,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,b,m,x,j,0,j=1,2,n,min=b,1,y,1,+b,2,y,2,+b,m,y,m,s.t.a,11,y,1,+a,21,y,2,+a,m1,y,m,c,1,a,12,y,1,+a,22,y,2,+a,m2,y,m,c,2,a,1n,y,1,+a,2n,y,2,+a,mn,y,m,c,n,yi0,i=1,2,m,(,D),对偶问题,原问题,用矩阵表示为：,(,P)max=CX (D)min=Yb,AXb YAC,X0 Y0,x,1,x,2,x,n,y,1,a,11,a,12,a,1n,b,1,y,2,a,21,a,22,a,2n,b,2,y,m,a,m1,a,m2,a,mn,b,m,c,1,c,2,c,n,例 写出下面问题的对偶问题,max=8x,1,+9x,2,s.t.4x,1,+x,2,5,2x,1,+3x,2,6,x,1,x,2,0,对偶问题是：,min=5y,1,+6y,2,s.t.4y,1,+2y,2,8,y,1,+3y,2,9,y,1,y,2,0,max,min,对于标准形式的线性规划问题,max=CX,s.t.AX=b,X0,其对偶问题是,min=Yb,s.t.YAC,Y,无非负约束,证标准形式的线性规划问题可以写为,max=CX,s.t.AXb,-AX-b,X0,其对偶问题为,min=Yb-Y”b,s.t.YA-Y”AC,Y,Y”0,令,Y=Y-Y”，,则上述问题变为,min=Yb,s.t.YA0,Y,没有限制,例,max=2x,1,+x,2,+3x,3,+x,4,s.t.x,1,+x,2,+x,3,+x,4,5,2x,1,-x,2,+3x,3,=-4,x,1,-x,3,+x,4,1,x,1,x,3,0,x,2,x,4,无约束,其对偶问题为,min=5y,1,+4y,2,-y,3,s.t.y,1,-2y,2,-y,3,2,y,1,+y,2,=1,4.2.对偶问题的基本性质,1.,对称性,：对偶问题的对偶问题是原问题。,2.,弱对偶性,：若,X,和,分别为(,P)，(D),的可行解，则有,=CX,b=,3.,无界性,：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。,4.,可行解是最优解的性质,：若,X,分别是问题(,P),(D),的可行解。并且,CX=,b，,则,X,分别为(,P),(D),的最优解。,5.,对偶定理,：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。,6.,互补松驰性(松紧定理),：若,X，,分别是(,P),(D),问题的可行解，那么,X,为最优解的充要条件是：,X,S,=0,Y,S,X=0,(,即若,A,i,X,i,=0,A,i,X=b,i,0,P,j,=C,j,0,P,j,C,j,=X,j,=0),例1.求解下列线性规划问题,max=x,1,+2x,2,+3x,3,+4x,4,s.t.x,1,+2x,2,+2x,3,+3x,4,20,2x,1,+x,2,+3x,3,+2x,4,20,x,j,0,j=1,2,3,4,解其对偶问题为,min=20y,1,+20y,2,s.t.y,1,+2y,2,1,2y,1,+y,2,2,2,y,1,+3y,2,3,3y,1,+2y,2,4,y,1,y,2,0,(1.2,0.2),1,2,1,2,.,.,y,1,y,2,用图解法得最优解,y,1,=1.2,y,2,=0.2,根据松紧定理，原问题的最优解必满足,X,S,=0,及,Y,S,X=0,及 (,y,3,y,4,y5,y6)=0,x,5,(y,1,y,2,)x,6,=0,x1,x2,x3,x4,将,y,1,=1.2,y,2,=0.2,代入对偶问题的约束条件，得,y,3,0,y,4,0,所以,x,1,=x,2,=0,又因,y,1,0,y,2,0。,所以,x,5,=x,6,=0，,即原问题为等式约束,x,1,=x,2,=0,x,1,+2x,2,+2x,3,+3x,4,=20,2x,1,+x,2,+3x,3,+2x,4,=20,即,x,1,=x,2,=0，x,3,=4,x,4,=4,原问题的最优解为(0,0,4,4),T,7,.,原问题单纯形表的检验数行对应其对偶问题的一个基解.,其对应关系见表：,X,B,X,N,X,S,0 C,N,-C,B,B,-1,N -C,B,B,-1,Y,S1,Y,S2,-Y,Y,S1,为对应原问题中基变量,X,B,的剩余变量，,Y,S2,是对应原问题中非基变量,X,N,的剩余变量。,设,B,是原问题的一个基本可行基，则,A=(B,N),max=C,B,X,B,+C,N,X,N,BX,B,+NX,N,+X,S,=b,X,B,X,N,X,S,0,相应地对偶问题可表示为,min=Yb,YB-Y,S1,=C,B,YN-Y,S2,=C,N,Y,Y,S1,Y,S2,0,令,Y=C,B,B,-1,，,则,Y,S1,=0,-Y,S2,=C,N,-C,B,B,-1,N,例1.,max=x,1,+4x,2,+3x,3,s.t.2x,1,+2x,2,+x,3,4,x,1,+2x,2,+2x,3,6,x,j,0,对偶问题为,min=4y,1,+6y,2,s.t.,2y,1,+y,2,1,2y,1,+2y,2,4,y,1,+2y,2,3,y,1,y,2,0,初始单纯形表为,4 2 2 1 1 0,6 1 2 2 0 1,0 1 4 3 0 0,对偶问题的基本解为,y,1,=0,y,2,=0，y,s1,=-1，y,s2,=-4，y,s3,=-3,其最终表为,1 3/2 1 0 1 -1/2,2 1 0 1 1 1,-10 2 0 0 1 -1,由原问题的最终表可知，,y,1,=1,y,2,=1(,最优解)，,y,s1,=2,5.对偶问题的经济解释影子价格,设,B,是最优基，则目标函数的最优值是,*,=C,B,B,-1,b=Y,*,b,y,i,*,的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化。,影子价格：在其它数据不变的条件下，一个约束右边的项增加一个单位，目标函数,最优值的变化，称为与这个约束相联系的影子价格。,在完全市场经济的条件下，当某种资源的市价低于影子价格，企业应买进资源用于扩大生产；而当某种资源的市价高于企业影子价格时，则企业的决策者应把已有资源卖掉，因此影子价格有调节市场的作用。,例 某工厂以一种贵重金属为原料生产两种产品，两种产品都必须经过粗加工和精加工两道工序，生产每件,A,产品需粗加工1小时，精加工2小时，需贵金属3克，出厂价60元，生产,B,产品需粗加工7小时，精加工4小时，需贵金属2克，出厂价70元。在一个生产周期中，按该厂的设备和人员，粗加工能力为140，000小时，精加工能力为100，000小时，由计划渠道供应的贵金属只有120公斤。每个粗加工工时的成本计为1.5元，精加工工时为2.5元，每克贵金属成本为10元。因本厂的工人工资和设备折旧在同一个生产周期内是固定,的，所以不论产品多少，都以其最大加工能力的工时计入成本，而贵金属按实际使用量计入成本。,如设,A、B,产品分别生产,x,1,和,x,2,千件，则利润可按下式计算（单位：万元）,S=6x,1,+7x,2,-（3x,1,+2x,2,）+（14,1.5+102.5),=3x,1,+5x,2,-46,使得毛利最大的生产计划即为如下线性规划的最优解：,max S,1,=,3x,1,+5x,2,（S,1,=S-46）,s.t.x,1,+7x,2,140 (,粗加工能力约束）,2,x,1,+4x,2,100（,精加工能力约束）,3,x,1,+2x,2,120（,贵金属用量约束）,x,1,，x,2,0,用单纯形法求解可得如下最优表：,X,B,b x,1,x,2,x,3,x,4,x,5,x,2,7.5 0 1 0 0.375 -0.25,x,1,35 1 0 0 -0.25 0.5,x,3,52.5 0 0 1 -2.335 1.25,142.5 0 0 0 -1.125 -0.25,由松驰变量的检验数可知：粗加工能力的影子价格为0；精加工能力的影子价格为1.125，单位是万元/千小时；贵金属的影子价格为0.25万元/公斤。,6.对偶单纯形法,对偶单纯形法的思想是：使对偶问题保持可行，而使原问题从非可行的基本解，逐步达到基本可行解，这样就得到了两个问题的最优解。,计算步骤：,(1)列出初始单纯形表，检验,b,列数字，若其全部非负且检验数,j,0，,则已得到最优解，停止；若列中至少有一个负分量，且,j,0,转(2),(2)按,min (B,-1,b),i,(B,-1,b),i,0 =(B,-1,b),l,确定换出变量,x,l,；,(3),确定换入变量,若,x,l,所在行的各系数,a,lj,0(j=1,2,n),则无可行解，停止；,若,a,lj,0，,则计算,=min,j,/a,lj,a,lj,0,b,r,-b,i,/a,ir,若,a,ir,0,b,r,minb,i,/a,ir,a,ir,0,例.线性规划问题,max=-x,2,+3x,2,-2x,5,s.t.,x,1,+3x,2,-x,3,+2x,5,=7,-2x,2,+4x,3,+x,4,=12,-4x,2,+3x,3,+8x,5,+x,6,=10,x,j,0,X,B,b x,1,x,2,x,3,x,4,x,5,x,6,x,1,7 1 3 1 0 2 0,x,4,12 0 2 4 1 0 0,x,6,10 0 4 3 0 8 1,-1 0 3 0 2 0,最终表是,X,B,b x,1,x,2,x,3,x,4,x,5,x,6,x,2,4 5/2 1 0 1/10 4/5 0,x,3,5 1/5 0 1 3/10 2/5 0,x,6,11 1 0 0 1/2 10 1