管理运筹学--单纯形法的灵敏度分析与对偶对偶问题讲课讲稿.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,管理运筹学-单纯形法的灵敏度分析与对偶对偶问题,第六章,单纯形法的灵敏度分析与对偶,DUAL,窗含西岭千秋雪，门泊东吴万里船,对偶是一种普遍现象,1 单纯形表的灵敏度分析,(重点.难点.掌握),2 线性规划的对偶问题,(重点.理解.掌握),3 对偶规划的基本性质,(重点.应用),4 对偶单纯形法,(难点.掌握-前面已讲),学习,重点,与,难点,1 单纯形表的灵敏度分析,(重点.难点.掌握),2 线性规划的对偶问题,一、对偶问题实例,例1 某工厂生产甲、乙两种产品，要消耗,A,、,B,和,C,三种资源，已知每件产品对这三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润如表所示.问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？,产品,资源,甲,乙,资源限制,A,3,2,65,B,2,1,40,C,0,3,75,单件利润,1500,2500,该问题的数学模型为：,max Z=1500 x,1,+2500 x,2,s.t.3x,1,+2x,2,65 A资源,2x,1,+x,2,40 B资源,3x,2,75 C资源,x,1,x,2,0,考虑：,1、定价不能,太高,？,2、定价不能,太低,？,假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？,咋办？,设A、B、C资源的出售价格分别为,y,1,、,y,2,和,y,3,甲,乙,资源限制,A,3,2,65,y1,B,2,1,40,y2,C,0,3,75,y3,单件利润,1500,2500,1500,2500,0,原问题：,max Z=1500 x,1,+2500 x,2,s.t.3x,1,+2x,2,65 A资源,2x,1,+x,2,40 B资源,3x,2,75 C资源,x,1,x,2,0,对偶问题：,Min W=65 y,1,+40 y,2,+75 y,3,s.t.3y,1,+2 y,2,1500,2y,1,+y,2,+3y,3,2500,y,1,y,2,y,3,0,2,1,0 3,A=,65,40,75,b=,1500 2500,c=,2 0,2 1 3,A=,1500,2500,b=,65 40 75,c=,max,min,对偶问题,Min,W=b,T,Y s.t.A,T,Y,C,T,Y,0,max,b,A,C,C,T,A,T,b,T,min,m,n,m,n,二、对偶问题的形式,1、对称型对偶问题,原问题,Max,Z=cX s.t.AXb,X,0,对偶关系表,x,1,x,2,x,m,x,n,c,1,c,2,c,m,c,n,maxZ minW,Y,1,A,11,a,12,a,1m,a,1n,b,1Y,2,a,21,a,22,a,2m,a,2n,b,2,Y,m,a,m1,a,m2,a,mm,a,mn,b,m,由表可以看出：,从行看是原问题（），从列看是对偶问题（），两个问题的变量系数矩阵互为转置矩阵。,原问题（）的常数项是对偶问题（）的目标系数，反之，原问题（）的目标系数是对偶问题（）的常数项。,原问题（）有n个决策变量，对偶问题（）有n个约束方程；原问题有m个约束方程，对偶问题就有m个决策变量。,原问题的约束是“”型，对偶问题的约束是“”型。,原问题的目标函数是求极大，对偶问题的目标是求极小。,max Z,5x,1,+4x,2,例2 请给出下列线性规划问题的对偶问题：,对称型线性规划问题,怎么样简单吧,2、非对称型对偶问题,表 对偶变换的规则,约束条件的类型(规范与否)与非负条件相互对应,非标准的约束条件类型对应非正常的非负条件,对偶变换是一一对应的,好难记呀！,例3：,Min z=5x,1,+25x,2,7x,1,+75x,2,98,s.t.5x,1,+6x,2,=78,24x,1,+12x,2,54,x,1,0、x,2,0,Max w=98y,1,+78y,2,+54y,3,7y,1,+5y,2,+24y,3,5,s.t.75y,1,+6y,2,+12y,3,25,y,1,0、y,2,无限制、y,3,0,怎么样，,没问题吧！,对称形式线形规划问题为:,Max,Z=cX s.t.AXb,X,0,加上松弛变量化为标准形后为:,Max,Z=cX+0X,s,s.t.AX+IX,s,=b,X,0,X,s,0,3 对偶规划的基本性质,一、单纯形法计算的矩阵描述:,检验数,j,当迭代若干步，基变量为,X,B,时，新的单纯形表:,b,X,S,0,C,j,X,B,X,N,X,S,B N,I,C,B,C,N,0,C,B,C,N,0,检验数,j,B,-1,b,X,B,C,B,C,j,X,B,X,N,X,S,I,B,-1,N B,-1,0 C,N,-C,B,B,-1,N -C,B,B,-1,C,B,C,N,0,初始单纯形表为:,maxZ=3x,1,+5,x,2,+0,x,3,+0x,4,+0,x,5,=0,x,1,+,x,3,=8,2,x,2,+,x,4,=12,3x,1,+4,x,2,+,x,5,=36,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,12,0,2,0,1,0,36,3,4,0,0,1,x,3,x,4,x,5,0,0,0,3,5,0,0,0,举例,最优基,C,j,3,5,0,0,0,比,值,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,4,0,0,1,2/3,-1/3,5,x,2,6,0,1,0,1/2,0,3,x,1,4,1,0,0,-2/3,1/3,检验数,j,0,0,0,-1/2,-1,x,3,x,2,x,1,最优基的逆,最优基和最优基的逆,maxZ=2x,1,+x,2,5x,2,15,s.t.6x,1,+2x,2,24,x,1,+x,2,5,x,1,x,2,0,maxZ=2x,1,+x,2,+0 x,3,+0 x,4,+0 x,5,5x,2,+x,3,=15,s.t.6x,1,+2x,2,+x,4,=24,x,1,+x,2,+x,5,=5,x,1,x,2,x,3,x,4,x,5,0,例4：对称形线性规划问题,：,标准型：,j,x,3,x,1,x,2,0,2,1,0,0 0 -1/4 -1/2,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,2 1 0 0 0,x,3,x,4,x,5,0,0,0,15 0,5 1 0 0,24 6,2 0 1 0,5 1,1 0 0 1,2,1 0 0 0,初始单纯形表,最终单纯形表,B=(P,3,P,1,P,2,),15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,B,-1,=(P,3,P,4,P,5,),初表中,终表中,minZ=2x,1,+3x,2,+x,3,x,1,+4x,2,+2x,3,8,S.t.3x,1,+2x,2,6,x,1,x,2,x,3,0,C,j,C,B,X,B,b检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1,0,0,-M,-M,8,1,4,2,-1,0 1 0,x,6,x,7,-M,-M,初始单纯形表格,4M-2 6M-3 2M-1,-M,-M,0,0,6,3,2,0,0,-1 0 1,C,j,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1,0,0,-M,-M,9/5,0,1,3/5,-3/10,1/10 3/10 -1/10,X,2,x,1,-3,-2,最终单纯形表格,0 0 0,-1/2,-1/2,-M,-M,4/5,1,0,-2/5,1/5,-2/5 -1/5 2/5,maxZ=50 x,1,+100 x,2,x,1,+x,2,300,s.t.2x,1,+x,2,400,x,2,250,x,1,x,2,0,maxZ=50 x,1,+100 x,2,+0 x,3,+0 x,4,+0 x,5,x,1,+x,2,+x,3,=300,s.t.2x,1,+x,2,+x,4,=400,x,2,+x,5,=250,x,1,x,2,x,3,x,4,x,5,0,例5：对称形线性规划问题：,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,x,3,x,4,x,5,0,0,0,300 1,1 1 0 0,400 2,1 0 1 0,250 0,1 0 0 1,50,100 0 0 0,原问题初始单纯形表,50 100 0 0 0,已知最优基的基变量为x,1,，x,4,，x,2,，请直接写出该线性规划问题的最终单纯形表。并给出其对偶问题的最优解,最优基为 B=（p,1,，p,4,，p,2,）=,B,-1,=,（p,3,，p,4,，p,5,）=,b,=B,-1,b=,1 0 -1,-2 1 1,0 0 1,1 0 1,2 1 1,0 0 1,1 0 -1,-2 1 1,0 0 1,300,400,250,50,50,250,=,j,=C,j,-C,B,B,-1,P,j,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,x,1,x,4,x,2,50,0,100,50 1,0 1 0 -1,50 0,0 -2 1 1,250 0,1 0 0 1,0,0 -50 0 -50,原问题最终单纯形表,50 100 0 0 0,原问题初始单纯形表,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,x,3,x,4,x,5,0,0,0,400 2,1 0 1 0,250 0,1 0 0 1,50,100 0 0 0,50 100 0 0 0,300 1,1 1 0 0,检验数,j,当迭代若干步，基变量为,X,B,时，新的单纯形表:,b,X,S,0,C,j,X,B,X,N,X,S,B N,I,C,B,C,N,0,C,B,C,N,0,检验数,j,B,-1,b,X,B,C,B,C,j,X,B,X,N,X,S,I,B,-1,N B,-1,0 C,N,-C,B,B,-1,N -C,B,B,-1,C,B,C,N,0,初始单纯形表为:,对应初始单纯表中的单位矩阵,I，迭代后的单纯形表中为B,-1,初始单纯表中的基变量X,s,=b，迭代后的单纯形表中为X,B,=B,-1,b,初始单纯表中的约束系数矩阵为：,A,I=B,N,I,迭代后的单纯形表中约束系数矩阵为：,B,-1,A,B,-1,I=B,-1,B,B,-1,N,B,-1,I=I,B,-1,N,B,-1,若初始矩阵中变量x,j,的系数向量为Pj,，迭代后为P,j,，则有：,P,j,=B,-1,P,j,小结,当B为,最优基,时，迭代后的单纯表中检验数：,C,N,-C,B,B,-1,N,0,-C,B,B,-1,0,因,X,B,的检验数可写 为：,C,B,-C,B,B,-1,B,故可重写为：,C-C,B,B,-1,A,0,-C,B,B,-1,0,C,B,B,-1,称为单纯形乘子,。若令,Y,T,=C,B,B,-1,则：C-Y,T,A,0 A,T,Y,C,所以：A,T,Y,C,T,Y,0,可见检验数的相反数恰好是其对偶问题的一个可行解，将这个解代入对偶问题的目标函数，有：,W=Y,T,b=C,B,B,-1,b=Z,当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，根据对偶问题的基本性质，将看到这时对偶问题的解也为最优解。,所以从最优解的单纯形表中同时可以得到其对偶问题的最优解。,maxZ=2x,1,+x,2,5x,2,15,s.t.6x,1,+2x,2,24,x,1,+x,2,5,x,1,x,2,0,maxZ=2x,1,+x,2,+0 x,3,+0 x,4,+0 x,5,5x,2,+x,3,=15 y,1,s.t.6x,1,+2x,2,+x,4,=24 y,2,x,1,+x,2,+x,5,=5 y,3,x,1,x,2,x,3,x,4,x,5,0,minW=15y,1,+24y,2,+5y,3,6y,2,+y,3,-y,4,=2 x,1,s.t.5y,1,+2y,2,+y,3,-y,5,=1 x,2,y,1,y,2,y,3,y,4,y,5,0,minW=15y,1,+24y,2,+5y,3,6y,2,+y,3,2,s.t.5y,1,+2y,2,+y,3,1,y,1,y,2,y,3,0,例5：对称形线性规划问题：,对偶问题：,标准型：,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,2 1 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,0,0 0 -1/4 -1/2,y,1,y,2,y,3,y,4,y,5,C,B,X,B,b,C,B,j,-15 -24 -5 0 0,y,2,y,3,-24,-5,1/4 -5/4 1,0 -1/4 1/4,1/2 15/2,0 1 1/2 -3/2,-15/2,0 0 -7/2 -3/2,-y,4 -,y,5,-y,1,-y,2,-y,3,-,x,3,-x,4,-x,5,-x,1,-x,2,原问题最终单纯形表,对偶问题最终单纯形表,松弛变量,对偶变量,剩余变量,决策变量,例6、利用原问题的最优单纯形表求解对偶问题的最优解,s.t.100,100,0,解:对偶问题为,s.t.4,3,7,0,C,j,C,B,X,Bb,检验数,j,x,1,x,2,x,3,x,4,x,5,4,3,7,0,0,25,-3/4,1,0,3/4,-1/2,25,5/4,0,1,-1/4,1/2,x,2,x,3,3,7,-5/2,0,0,-1/2,-2,最终单纯形表格,x4x5松弛变量,可见原问题的最优解为:X*=(0,25,25)T,其对偶问题的最优解为:y*=(1/2,2)T,为了便于讨论，下面不妨总是假设:,定理1,（对称性定理）对偶问题的对偶是原问题,。,根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为,原问题，而把另一个称为其对偶问题。,:,=,0,Y,C,T,A,T,Y,b,T,Y,.,.,min,t,s,W,对偶问题,=,:,0,X,b,AX,CX,.,.,max,t,s,Z,原问题,二、对偶问题的基本性质:,=,0,Y,C,T,A,T,Y,b,T,Y,.,.,min,t,s,W,=,0,Y,-C,T,-A,T,Y,-b,T,Y,.,.,max,t,s,(-W),=,0,.,.,max,X,b,AX,t,s,CX,Z,证明:由前面可知对偶问题为:,等价于该问题:,可见此问题为对称型的规划问题,其对偶问题表示为:,令Z=-f,则化简为:,即为原问题,可见对偶问题的对偶是原问题。证毕,定理,2,（弱,对偶性定理）,对偶问题(min)的任何可行解,Y,0,，,其目标函数值总是不小于原问题(max)任何可行解,X,0,的目标函数值。,证:假设X,0,Y,0,分别为原问题和对偶问题的可行解,故有:,0,X,0,b,AX,0,CX,0,.,.,max,t,s,Z,=,0,Y,0,C,T,A,T,Y,0,b,T,Y,0,.,.,min,t,s,W,=,-(1),-(2),因为Y,0,是对偶问题的可行解,用Y,0,T,左乘(1)得:Y,0,T,AX,0,Y,0,T,b,转置得:X,0,T,A,T,Y,0,b,T,y,0,因为X,0,是原问题的可行解,用X,0,左乘(2)得:X,0,T,A,T,Y,0,X,0,T,C,T,转置得:Y,0,T,AX,0,CX,0,可见CX,0,Y,0,T,AX,0,Y0,T,b=b,T,Y,0,即CX,0,b,T,Y,0,例7、应用弱对偶定理，证明下列线性规划问题的最大值不超过1.,s.t.,证明：该线性问题的对偶问题为：,弱,对偶定理推论,推论 1,最优解判别,定理,若原问题的某个可行解,X,0,的目标函数值与对偶问题某个可行解,Y,0,的目标函数值相等，则,X,0,Y,0,分别是相 应问题的最优解,证：由弱对偶定理可知结论是显然的,即,CX,0,=,b,T,Y,0,CX,b,T,Y,0,=,CX,0,Yb,。,证毕。,推论 2,如果原max(min)问题为无界解，则其对偶 min(max)问题无可行解(反之不然),maxZ=x,1,+x,2,x,1,x,2,-1,s.t.-x,1,+x,2,-1,x,1,x,2,0,minW=-y,1,-y,2,y,1,-y,2,1,s.t.-y,1,+y,2,1,y,1,y,2,0,原问题和对偶问题同时无可行解,推论 3,原问题(max)的任何可行解目标函数值是其对偶问题(min)目标函数值的下界；原问题(min)的任何可行解目标函数值是其对偶问题(max)目标函数值的上界,推论 4,如果原问题max(min)有可行解，其对偶 问题min(max)无可行解，则原问题为无界解,例8、,应用对偶理论证明下列线性规划问题目标函数值无界.,s.t.,证明：,是线性问题的可行解，即该问题存在可行解；,又其对偶问题为：,定理 3 主对偶,定理(强对偶性定理),如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解所对应的目标函数值相等。,证:,由弱对偶定理推论1可知，原问题和对偶问题的目标函数,有界，故一定存在最优解。,现证明定理的后一句话。,设,X,0,为原问题的最优解，它所对应的基矩阵是,B,，,X,0,=,B,1,b,，则其检验数满足,C,C,B,B,1,A,0,令,Y,0,=,C,B,B,1,，则有,Y,0,A,C,显然,Y,0,为对偶问题的可行解。因此有对偶问题目标函数值,W,=,Y,0,b,=,C,B,B,1,b,而原问题最优解的目标函数值为,Z,=,CX,0,=,C,B,B,1b,故由最优解判别定理可知,Y,0,为对偶问题的最优解。证毕。,定理 4 互补松弛,定理,定理,设,X,0,Y,0,分别是原问题和对偶问题的可行解，,U,0,为原问题的松弛变量的值、,V,0,为对偶问题剩余变量的值。,X,0,Y,0,分别是原问题和对偶问题最优解的充分必要条件是,Y,0,U,0,=,V,0,X,0,=,0,证,：,由定理所设，可知有,A X,0,+U,0,=,b X,0,U,0,0,(1),Y,0,A,V,0,=,C Y,0,V,0,0,(2),分别以,Y,0,左乘(1)式，以,X,0,右乘(2)式后，两式相减，得,Y,0,U,0,+,V,0,X,0,=Y,0,b,C X,0若,Y,0,U,0,+,V,0,X,0,=,0，根据最优解判别定理，,X,0,Y,0,分别是原问题和对偶问题最优解。反之亦然。,证毕。,例9、考虑下列原始线性规划,(,1)写出其对偶问题；,(2)已知（3,2,0）是上述原始问题的最优解，根据互补松弛定理，求出对偶问题的最优解；,(3)如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格.,解：（1）对偶问题：,（2）由题知原问题的最优解为,由互补松弛定理得：在对偶问题中对应第一，二个约束为紧约束，第三个约束条件为松约束，即，,对偶规划问题的最优解,（3）影子价格为 y,1,=4,-1,(4,-1),例 10：利用互补松弛定理,原问题检验数与对偶问题的解的总结,在主对偶定理(强对偶性)的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值,容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值,由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。,更一般地讲，不管原问题是否标准，在,最优解的单纯型表中，都有原问题,虚变量,(松弛或剩余)的检验数对应其对偶问题,实变量,(对偶变量)的最优解,，,原问题,实变量,(决策变量)的检验数对应其对偶问题,虚变量,(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,4 对偶单纯形法,一、对偶单纯形法的基本思路,单纯形迭代要求每步都是基本可行解,达到最优解时，检验数,c,j,z,j,0(max),但对于所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决,大M法和二阶段法较繁,能否从剩余变量构成的初始基础非可行解出发迭代，但保证,检验数满足最优条件，,c,j,z,j,0(max),b,=,B,1,b,0,0,0？,二、对偶单纯形法的计算步骤,对某线形规划问题存在一个对偶问题的可行基，即必须所有的c,j,-z,j,0,，b,i,的值不要求全为正:,1、确定换出变量（离基变量）,在小于0的b中找出最小者，其所对应的变量x,r,为换出变量,2、确定换入变量（进基变量）,=min,j,/a,rj,|a,rj,0，则按单纯形法继续迭代计算找出最优解,j,最终单纯形表,b,X,S,0,C,j,X,B,X,N,X,S,B N,I,C,B,C,N,0,C,B,C,N,0,j,B,-1,b,X,B,C,B,C,j,X,B,X,N,X,S,I,B,-1,N B,-1,0 C,N,-C,B,B,-1,N,-,C,B,B,-1,C,B,C,N,0,初始单纯形表,例15、在佳美公司例子中，设该公司又计划推出新产品，生产一单位产品，所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3百元/单位，试分析该新产品是否值得投产；如投产对该公司的最优生产计划有何变化。,解：,设新产品的生产数量为x,6,件，有：,将其反映到最终单纯形表中得表,1 5/4 -15/2,0 1/4 -1/2,0 -1/4 3/2,3,4,2,-7,0,2,P,6,=B,-1,P,6,=,=,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,2 1 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,0,0 0 -1/4 -1/2,j,51/4 0,7/2 1 3/8 -9/4,0,7/2 1,0 0 1/4 -1/2,0,3/4 0,1/2 0 -1/8 3/4,1,0,-1/2 0 -1/8 -5/4,0,x,3,x,1,x,6,0,2,3,可见变化后的问题具有唯一最优解:X*=(7/2,0),T,Z*=37/4,比原方案17/2获利多，所以值得生产,-7,0,2,x,6,3,1,(2)减少决策变量的灵敏度分析,若减少的决策变量不在最优解的基变量之中，,是非基变量，,对这种情况可以认为决策变量本来就是多余的。减少这个变量,不影响最优解、最优值,。,j,-5,-15,13/7,0,1 4/7 -5/7,3/7,3/7,1,0 2/7 1/7 -2/7,0,0 -27/7 -10/7 -15/7,x,2,x,1,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,-15 -5 -11 0 0,减少决策变量,x,3,，最优生产计划如何？,(2)减少决策变量的灵敏度分析,若减少的决策变量,是基变量,，要考虑去掉这个变量的影响，可用单纯形法或对偶单纯形法重新求解。,j,-5,-15,13/7,0,1 4/7 -5/7,3/7,3/7,1,0 2/7 1/7 -2/7,0,0 -27/7 -10/7 -15/7,x,2,x,1,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,-15 -5 -11 0 0,j,-11,-15,13/4,0,1 1 -5/4,3/41/2,1,0 0 1/2 -1/2,0,0 0 -25/4 3/4,x,3,x,1,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,-15 -5 -11 0 0,引入人工变量,x,6,，采用大M法继续求解,减少决策变量,x,2,，最优生产计划如何？,四、系数矩阵的灵敏度分析,a,ij,的变化使线形规划的约束系数矩阵A发生变化。若变量x,j,在最终单纯性表中,为非基变量,，其约束条件中系数a,ij,的变化分析步骤可参照三中增加决策变量的情形；若变量x,j,在最终单纯性表中,为基变量,，其约束条件中系数a,ij,的变化将使相应的B和B,-1,发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需要引进人工变量先将原问题的解转化为可行解，再用单纯性法求解。,下面就变量x,j,在最终单纯性表中,为基变量,这种情形举例说明,例16、,在佳美公司的例子中，若产品每单位需设备A、B和调试工时8小时、4小时、1小时，该产品的利润变为3百元/单位，试重新确定该公司最优生产计划.,解：先将生产工时变化后的产品看作是一种新产品，生产量为,x,2,，按本节三的方法直接计算,2,和,P,2,：,2,=3-（0，1/4，1/2）=3/2,1 5/4 -15/2,0 1/4 -1/2,0 -1/4 3/2,8,4,1,11/2,1/2,1/2,P,6,=,8,41,将其反映到最终单纯形表中得表,j,最终单纯形表,b,X,S,0,C,j,X,B,X,N,X,S,B N,I,C,B,C,N,0,C,B,C,N,0,j,B,-1,b,X,B,C,B,C,j,X,B,X,N,X,S,I,B,-1,N B,-1,0 C,N,-C,B,B,-1,N,-,C,B,B,-1,C,B,C,N,0,初始单纯形表,x,1,x,2,x,3,x,4,x,5,x,2,C,B,X,B,b,C,B,j,2 1 0 0 0,3,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,11/2,7/2 1,0 0 1/4 -1/2,1/2,3/2 0,1 0 -1/4 3/2,1/2,0,0 0 -1/4 -1/2,3/2,原问题与对偶问题均为非可行解，故先设法使原问题变为可行解,j,-9 0,7/2 1 4 -24,0,2 1,0 0 1/2 -2,0,3 0,1/2 0 -1/2 3,1,0,-1/2 0 1/2 -5,0,x,3,x,1,x,2,0,2,3,j,3/8 0,-1/24 -1/6,1,0 1/24,11/4 1,-1/12 1/6,0,0 1/12,15/8 0,1/8 0,0,1 -1/8,0,-5/24 -1/3,0,0 -M+5/24,x,5,x,1,x,2,0,2,3,j,9 0,-1 -4 24,0 1,2 1,0 1/2 -2,0 0,3 0,0 -1/2 3,1 0,0,-M 1/2-4M -5+24M 0,0,x,6,x,1,x,2,-M,2,3,x,1,x,3,x,4,x,5,x,2,x,6,C,B,X,B,b,C,B,2 0 0 0,3 -M,x,3,+4x,4,-24x,5,=-9,-x,3,-4x,4,+24x,5,+,x,6,=9,可见变化后的问题具有唯一最优解:X*=(11/4,15/8),T,Z*=89/8,五、增加或减少约束条件的灵敏度分析,增加一个约束条件在实际问题中相当增添一道工序，设在原线性规划问题中，增加一个新的约束条件,：,代入新增加的约束条件，,如果条件满足,，则原问题的最优解仍为新问题的最优解，结束.,如果条件不满足，,则将新增加的约束条件直接反映到最终单纯形表中再进一步分析.,则首先把已求得的原问题的最优解,例17、假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力为12小时，试分析增加该工序后的佳美公司最优生产计划.,解：,环境试验工序的约束条件为：3,x,1,+2x,2,12,将原问题的最优解:x,1,=7/2,x,2,=3/2 代入环境试验工序的约束条件：,3*7/2+2*3/2=27/2,可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。,12,以,x6,为基变量将其反映到最终单纯形表中,将3,x,1,+2x,2,12化为标准型,3,x,1,+2x,2,+x,6,=12,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,2 1 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,0,0 0 -1/4 -1/2,0,x,6,12 3 2 0 0 0,0,x,6,0,0,0,1,0,(1),(2),(3),(4),因为表中,x,1,、,x,2,列不是单位向量，所以需要进行变换,x,1,x,2,x,3,x,4,x,5,x,6,C,B,X,B,b,C,B,j,2 1 0 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2 0,7/2 1,0 0 1/4 -1/2 0,3/2 0,1 0 -1/4 3/2 0,0,0 0 -1/4 -1/2 0,0,x,6,-3/2,0,0,0 -1/4 -3/2 1,(1),(2),(3),(4),x,1,x,2,x,3,x,4,x,5,x6,C,B,X,B,b,C,B,j,2 1 0 0 0 0,x,3,x,1,x,2,0,2,1,15 0,0 1 5/2,0,-5,4 1,0 0 1/3,0,-1/3,0 0,1 0 -1/20,1,0,0 0 -1/6,0,-1/3,0,x,5,1 0 0 0 1/6,1,-2/3,可见变化后的问题具有唯一最优解:X*=(4,0),T,Z*=8,例18、假设产品、经调试后，还需经过一道环境试验工序，产品每单位须环境试验3小时，产品每单位须2小时，又环境试验工序每天生产能力至少为15小时，试分析增加该工序后的佳美公司最优生产计划.,解：,环境试验工序的约束条件为：3,x,1,+2x,2,15,将原问题的最优解:x,1,=7/2,x,2,=3/2 代入环境试验工序的约束条件：,3*7/2+2*3/2=27/2,可见新增加的约束条件对原问题的最优解起作用，所以原问题的最优解不是本问题的最优解。,以,x,6,为基变量将其反映到最终单纯形表中,将3,x,1,+2x,2,15化为标准型 -,3,x,1,-2x,2,+x,6,=-15,可以采用大M法，最好采用对偶单纯形法,避免用人工变量,x,1,x,2,x,3,x,4,x,5,C,B,X,B,b,C,B,j,2 1 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,0,0 0 -1/4 -1/2,0,x,6,-15 -3 -2 0 0 0,0,x,6,0,0,0,1,0,(1),(2),(3),(4),因为表中,x1,、,x,2,列不是单位向量，所以需要进行变换,x,1,x,2,x,3,x,4,x,5,x,6,C,B,X,B,b,C,B,j,2 1 0 0 0 0,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2 0,7/2 1,0 0 1/4 -1/2 0,3/2 0,1 0 -1/4 3/2 0,0,0 0 -1/4 -1/2 0,0,x,6,-3/2,0,0,0 1/4 3/2 1,(1),(2),(3),(4),可见变化后的问题没有可行解，对偶问题具有无界解,减少约束条件的灵敏度分析,减少一个约束条件在实际问题中相当去掉一道工序，即在原线性规划问题中，去掉一个约束条件,反映到最终单纯形表中就是去掉一行，重新计算检验数行，可能利用单纯形法继续求解,j,x,3,x,1,x,2,0,2,1,15/2 0,0 1 5/4 -15/2,7/2 1,0 0 1/4 -1/2,3/2 0,1 0 -1/4 3/2,0,0 0 -1/4 -1/2,x,1,x,2,x,3,x,4,x,5,C,B,2 1 0 0 0,终表,C,B,X,B,b,0,1 0 -1/2 1,该问题存在无界解,假如去掉调试工序，原问题的最优生产方案如何？,以上的几种灵敏度分析，仅限于某数值、变量、约束条件的变化对解的影响，这是一些基本的分析方法。若要考虑某区间上一个或几个参数作连续变化的灵敏度分析请同学们参阅线性规划方面的资料或书籍。,对偶问题的经济解释,影子价格,补充内容,30,20,10,max Z=5x,1,+4x,2,s.t.x,1,+3x,2,90 ,2x,1,+x,2,80,x,1,+x,2,45,x,1,x,2,0,由图示可知最优点为,B（35，10）,最优值为215,100,80,60,40,20,20,40,60,80,x,1,100,B,1、影子价格含义的图解法,20,10,max Z=5x,1,+4x,2,s.t.x,1,+3x,2,91,2x,1,+x,2,80,x,1,+x,2,45,x,1,x,2,0,由图示可知最优点为,B(35,10),最优值为215,称为资源A的影子价格为0,100,80,60,40,20,20,40,60,80,x,1,100,B,30,20,10,max Z=5x,1,+4x,2,s.t.x,1,+3x,2,90 ,2x,1,+x,2,81,x,1,+x,2,45,x,1,x,2,0,由图示可知最优点为,B（36，9）,最优值为216,称为资源B的影子价格为1,100,80,60,40,20,20,40,60,80,x,1,100,B,20,10,max Z=5x,1,+4x,2,s.t.x,1,+3x,2,90 ,2x,1,+x,2,80,x,1,+x,2,46,x,1,x,2,0,由图示可知最优点为,B(34，12最优值为218,称为资源C的影子价格为3,100,80,60,40,20,20,40,60,80,x,1,100,B,可见影子价格的含义是,当某,约束条件常数项,每增加一个单位时,最优目标函数值,的增加量,2、影子价格在经营管理中的应用（一）,(1)影子价格说明增加哪一种,资源,对增加经济效益最有利.三种资源的影子价格为（0,1,3），说明首先应考虑增加资源C，因为相比之下它能给收益带来的增加最大.,(2),影子价格,与某一约束条件相对应,(3)影子价格又是一种,机会成本,.企业经营决策者可以把本企业,资源的影子价格,与当时,资源的市场价格,进行比较:,当某种资源的,影子价格,高于,市场价格,时，则企业可以,买进,该种资源，因为资源带来的收益大于购买资源的费用,当某种资源的,影子价格,低于,市场价格时,（特别是当影子价格为零时），则企业可以,卖出,该种资源，以获得较大的利润.,所以,资源,的影子价格（,机会成本、收益,）和,市场价格,是2个不同的概念。,例如甲设备的影子价格为15元，如果通过外包能取得追加的加工工时，且外包加工的工时价格为10元，即影子价格大于市场价格，则通过外包可以增加总收益，因而采取外包是合理的。,概念区分（一）,生产,产品,的,机会成本,和产品的,市场价格,（收益）也是2个不同的概念：,第i种产品的,机会成本,：C,B,B,-1,P,j,第i种产品的,市场价格：,C,j,当产品的市场价格(收益)产品的机会成本时，即C,j,C,B,B,-1,P,j,亦即C,j,-C,B,B,-1,P,j,0，也就是检验数大于0，需要继续单纯形法迭代，目标值将增加，因此可以作出生产该产品的决策，,或者说公司对生产该产品有吸引力。,概念区分（二）,当,产品的市场价格,(收益),产品的机会成本,时，即C,j,C,B,B,-1,P,j,亦即C,j,-C,B,B,-1,P,j,173/60,市场销售部门提出需要一种新的室外帐篷，帐篷需要1.8小时弯管时间、0.5小时焊接时间和1.3公斤金属管材。这些新产品必须有多大的收益，才能使得这一产品对公司产生吸引力？,该问题相当于增