运筹学二章对偶线性规

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浙江科技学院经济管理学院管工系,*,第二章 对偶理论与灵敏度分析,2.1,线性规划的对偶问题,2.2,对偶问题的基本性质,2.3,影子价格,2.4,对偶单纯形法,2.5,灵敏度分析,DUAL,11/26/2024,1,本章学习要求,掌握对偶理论及其性质,掌握影子价格的应用,掌握对偶单纯形法,熟悉灵敏度分析的概念和内容,掌握右侧常数，价值系数，工艺系数的变换对原最优解的影响,掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素的灵敏度范围,11/26/2024,2,浙江科技学院经济管理学院管工系,2.1,线性规划的对偶问题,问题的提出,对称形式下对偶问题的一般形式,非对称形式下的原问题与对偶问题的关系,11/26/2024,3,浙江科技学院经济管理学院管工系,一、对偶问题的提出,每一个,LP,问题，都伴随着另一个,LP,，而且二者有密切关系，互为对偶，另其中一个问题为原问题，另一个问题为对偶问题，只要得到了其中一个问题的解（目标值），也得到另一问题的解，因此通常只求解一个问题就可以了。,例,1,：（美佳公司）,美佳公司应如何生产安排，使已有资源利润最大化。,某公司至少该出多大代价，使美佳公司愿意放弃自己的资源，,产品,资源,资源约束,A,0,5,15,B,6,2,24,调试工序,1,1,5,单位产品利润,2,1,产品,资源,A,B,调试,工序,单位资源利润,0,6,1,2,5,2,1,1,资源量,15,24,5,11/26/2024,4,浙江科技学院经济管理学院管工系,数学模型,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,15/2,0,0,1,5/4,-15/2,2,x1,7/2,1,0,0,1/4,-1/2,1,x2,3/2,0,1,0,-1/4,3/2,j,0,0,0,-1/4,-1/2,cj,-15,-24,-5,0,0,-M,CB,YB,b,y1,y2,y3,y4,y5,y6,-M,y6,2,0,6,1,-1,0,1,1/3,-15,y1,1/5,1,2/5,1/5,0,-1/5,0,5/2,j,0,6M-18,M-2,-M,-3,0,-24,y2,1/3,0,1,1/6,-1/6,0,1/6,2,-15,y1,1/5,1,0,2/15,1/15,-1/5,-1/15,1/2,j,0,0,1,-3,-3,-M+8,-24,y2,1/4,-5/4,1,0,-1/4,1/4,1/2,-5,y3,1/2,15/2,0,1,1/2,-3/2,-3,j,-15/2,0,0,-7/2,-3/2,-M-3,Z*=8.5,W*=8.5,11/26/2024,5,浙江科技学院经济管理学院管工系,二、对偶问题的一般形式,一般认为变量均为非负约束的情况下，约束条件在目标函数取,Max,时均取“,”,号；当目标函数求,Min,值时均取“,“,号。则称这些线性规划问题具有对称性。,max z=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,1, x,2, ,x,n,0,min w=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,y,1, y,2, ,y,m,0,Max Z=CX,s.t,.,AXb,X0,Minw,=,Yb,s.t,. AYC,Y0,11/26/2024,6,浙江科技学院经济管理学院管工系,原问题,max z=CX,s.t.,AX,b,X 0,对偶问题,min w=,Yb,s.t. AY,C,Y,0,max,b,C,C,A,T,b,min,m,n,m,n,A,11/26/2024,7,浙江科技学院经济管理学院管工系,举例：,maxZ,=3x,1,+2x,2,s.t,. -x,1,+2x,2,4,3x,1,+2x,2,14,x,1,-x,2,3,x,1,x,2,0,minw,=4y,1,+14y,2,+y,3,s.t,. -y,1,+3y,2,+y,3,3,2y,1,+2x,2,-y,3,2,y,1,y,2,y,3,0,y,1,y,2,y,3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x,1,x,2,11/26/2024,8,浙江科技学院经济管理学院管工系,原始问题为,min z=2x,1,+3x,2,-x,3,s.t. x,1,+2x,2,+x,3,6,2x,1,-3x,2,+2x,3,9,x,1, x,2, x,3,0,根据定义，对偶问题为,max y=6y,1,+9y,2,s.t. y,1,+2y,2,2,2y,1,- 3y,2,3,y,1,+2y,2,-1,y,1, y,2,0,原始问题是极小化问题,原始问题的约束全为,原始问题有,3,个变量，,2,个约束,原始问题的变量全部为非负,对偶问题是极大化问题,对偶问题的约束全为,对偶问题有,2,个变量，,3,个约束,原始问题的变量全部为非负,11/26/2024,9,浙江科技学院经济管理学院管工系,对偶问题的对偶,max z=6x,1,+9x,2,s.t. x,1,+2x,2,2,2x,1,- 3x,2,3,x,1,+2x,2,-1,x,1, x,2,0,minw,=2y,1,+3y,2,-y,3,s.t. y,1,+2y,2,+y,3,6,2y,1,-3y,2,+2y,3,9,y,1, y,2, y,3,0,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题。另一个就是它的对偶问题。,根据定义写出对偶问题,根据定义写出对偶问题,max u=6w,1,+9w,2,s.t. w,1,+2w,2,2,2w,1,- 3w,2,3,w,1,+2w,2,-1,w,1, w,2,0,11/26/2024,10,浙江科技学院经济管理学院管工系,对偶问题的性质总结,对偶的对偶就是原始问题,max z=CX,s.t.,AX,b,X 0,min w=,Yb,s.t. A,T,Y,C,Y0,对偶的定义,max u=CW,s.t. AW,C,W,0,11/26/2024,11,浙江科技学院经济管理学院管工系,maxZ,=x,1,+4x,2,+2x,3,s.t,. 5x,1,-x,2,+2x,3,8,x,1,+3x,2,-3x,3,5,x,1,x,2,x,3,0,minw,=8y,1,+5y,2,s.t,. 5y,1,+y,2,1,-y,1,+3y,2,4,2y,1,-3y,2,2,y,1,y,2,0,11/26/2024,12,浙江科技学院经济管理学院管工系,三、非对称形式的原,对偶问题,minz,=2x,1,+3x,2,-5x,3,+x,4,s.t,. x,1,+x,2,-3x,3,+x,4,5,2x,1,+2x,3,-x,4,4,x,2,+x,3,+x,4,=6,x,1,0,x,2,x,3,0,minz,=-2x,1,+3x,2,-5x,3,+(x,4,-x,4,”),s.t.-x,1,+x,2,-3x,3,+(x,4,-x,4,”)5,2x,1,-2x,3,+(x,4,-x,4,”)-4,x,2,+x,3,+(x,4,-x,4,”) 6,-x,2,-x,3,-(x,4,-x,4,”) -6,x,1,x,2,x,3,x,4,x,4,”,0,变为对称形式,y,1,y,2,y,3,y,3,”,maxw,=5y,1,-4y,2,+6(y,3,-y,3,”),s.t.-y,1,+2y,2,-,2,y,1,+(y,3,-y,3,”),3,-3y,1,-2y,2,+(y,3,-y,3,”),-5,y,1,+y,2,+(y,3,-y,3,”),1,-,y,1,-y,2,-(y,3,-y,3,”) - 1,y,1,y,2, ,y,3,y,3,”0,写出对偶问题,maxw,=5y,1,+4y,2,+6y,3,s.t,. y,1,+2y,2,2,y,1,+y,3,3,-3y,1,+2y,2,+y,3, -5,y,1,-y,2,+y,3,= 1,y,1,0 ,y,2,0,y,3,无约束,11/26/2024,13,浙江科技学院经济管理学院管工系,结论,LP(LD),Max,X0,X0,X,无约束,St ,st,St=,LD(LP),Min,st,St ,St=,Y0,Y0,Y,无约束,11/26/2024,14,浙江科技学院经济管理学院管工系,min z= 2x,1,+4x,2,-x,3,s.t. 3x,1,- x,2,+2x,3,6,-x,1,+2x,2,-3x,3,12,2x,1,+x,2,+2x,3,8,x,1,+3x,2,-x,3,15,max w=6y,1,+12y,2,+8y,3,+15y,4,s.t. 3y,1,- y,2,+2y,3,+ y,4,2,-y,1,+2y,2,+ y,3,+3y,4,4,2y,1,- 3y,2,+2y,3,- y,4,-1,y,1,0,y,2,y,3,0,y,4,0,=,Free,=,x,1,0,x,2,0,x,3,: Free,原始问题变量的个数,(3),等于对偶问题约束条件的个数,(3),；,原始问题约束条件的个数,(4),等于对偶问题变量的个数,(4),。,原始问题变量的性质影响对偶问题约束条件的性质。,原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（,1,）,11/26/2024,15,浙江科技学院经济管理学院管工系,写对偶问题的练习（,2,）,原始问题,max z=2x,1,-x,2,+3x,3,-2x,4,s.t,. x,1,+3x,2,- 2x,3,+ x,4,12,-2x,1,+ x,2,-3x,4,8,3x,1,- 4x,2,+5x,3,- x,4,= 15,x,1,0, x,2,:Free, x,3,0, x,4,0,min w=12y,1,+8y,2,+15y,3,s.t,. y,1, 2y,2,+ 3y,3,2,3y,1,+ y,2, 4y,3,=-1,-2y,1,+5y,3,3,y,1, 3y,2,- y,3,-2,y,1,0,y,2,0, y,3,:Free,对偶问题,11/26/2024,16,浙江科技学院经济管理学院管工系,maxZ,=x,1,-2x,2,+3x,3,s.t,. 2x,1,+4x,2,+3x,3,100,3x,1,-2x,2,+6x,3,200,5x,1,+3x,2,+4x,3,=150,x,1, x,3,0,练习,minw,=100y,1,+200y,2,+150y,3,s.t,. 2y,1,+3y,2,+5y,3,1,4y,1,-2y,2,+3y,3,= -2,3y,1,+6y,2,+4y,3,3,y,1,0,y,2,0,minZ,=2x,1,+2x,2,+4x,3,s.t,. x,1,+3x,2,+4x,3,2,2x,1,+ x,2,+3x,3,3,x,1,+4x,2,+3x,3,=5,x,1,0, x,2,0,maxw,=2y,1,+3y,2,+5y,3,s.t,. y,1,+2y,2,+ y,3,2,3y,1,+ y,2,+4y,3, 2,4y,1,+3y,2,+3y,3,4,y,1,0,y,2,0,11/26/2024,17,浙江科技学院经济管理学院管工系,课后作业,P74 2.1(4),11/26/2024,18,浙江科技学院经济管理学院管工系,2.2,对偶问题的基本性质,单纯形法的矩阵描述,对偶问题的基本性质,11/26/2024,19,浙江科技学院经济管理学院管工系,一、单纯形法计算的矩阵描述,Max Z=CX,AXb,X0,Max Z=CX,AX+X,s,=b,X 0,Xs0,引入松弛变量,令,X=(X,B,X,N,),T,C=(C,B,C,N,),A=(B,N),BX,B,+NX,N,+X,S,=b,B,-1,BX,B,+B,-1,NX,N,+B,-1,X,S,=B,-1,b,X,B,=B,-1,b-B,-1,NX,N,-B,-1,X,S,MaxZ,=C,B,(,B,-1,b-B,-1,NX,N,-B,-1,X,S,)+C,N,X,N,=C,B,B,-1,b,（,C,N,-,C,B,B,-1,N)X,N,-,C,B,B,-1,X,S,11/26/2024,20,浙江科技学院经济管理学院管工系,某一决策变量,x,k,系数列向量迭代前为,P,k,，迭代后为,B,-1,P,k,。,当,B,为最优基时,MaxZ,=C,B,B,-1,b,（,C,N,-,C,B,B,-1,N)X,N,-,C,B,B,-1,X,S,令,Y,=C,B,B,-1,由此可以看出，当,X,为最优解时，,Y,为对偶问题的可行解。,且该可行解对应的目标函数值,W=,Yb,=CX*,11/26/2024,21,浙江科技学院经济管理学院管工系,非基变量,基变量,X,B,X,N,X,s,0,X,s,b,B,N,I,c,j,-z,j,C,B,C,N,0,基变量,非基变量,X,B,X,N,X,s,C,B,X,B,B,-1,b,I,B,-1,N,B,-1,c,j,-z,j,0,C,N,-C,B,B,-1,N,-C,B,B,-1,对应初始单纯形表中的单位矩阵,I,，迭代后的单纯形表中为,B,-1,；,初始单纯形表中基变量,Xs=b,，迭代后的表中为,X,B,=B,-1,b,；,约束矩阵（,A,，,I,）（,B,，,N,，,I,），迭代后为,（,B,-1,B,，,B,-1,N,，,B,-1,I,）（,I,，,B,-1,N,，,B,-1,),；,初始单纯形表中,x,j,的系数向量为,P,j,，迭代后为,P,j,，且,P,j,=B,-1,P,j,。,11/26/2024,22,浙江科技学院经济管理学院管工系,二、对偶问题的基本性质,原始问题,max z=CX,s.t.,AX,b,X 0,对偶问题,min w=,Yb,s.t. A,Y,C,Y,0,1.,弱对偶性,若,X,0,为原问题的可行解，,Y,0,为对偶问题的可行解，则恒有,CX,0,Y,0,b,证明：,X,0,0,为,LP,的可行解，,Y,0,0,为,LD,的可行解，则有：,AX,0,b A,Y,0, C,Y,0,AX,0,Y,0,b (A,Y,0,)X,0, (C)X,0,Y,0,b Y,0,AX,0,CX,0,11/26/2024,23,浙江科技学院经济管理学院管工系,推论,: (LP-Max LD-Min),1.LP,任一可行解的目标函数是其,LD,目标函数值的下界，,反之,LD,任一可行解的目标函数是其,LP,目标函数的上界。,Z=,CXMaxZ,=,MinW,Yb,2.,如,LP,有可行解且目标函数值,无界,，则其,LD,无可行解,；,反之,LD,有可行解且目标函数,无界,，则,LP,无可行解,。,(,对偶问题无可行解时，其原问题无界解或无可行解。,),Z=CX+ ,Yb,W=,Yb,- CX,3.,若,LP,有可行解而其,LD,无可行解时，,LP,目标函数,无界,反之，若,LD,有可行解而其,LP,无可行解时，,LD,目标函数,无界,。,11/26/2024,24,浙江科技学院经济管理学院管工系,2.,最优性,若,X,0,为,LP,的可行解，,Y,0,为,LD,的可行解，且,CX,0,Y,0,b,则,X,0,，,Y,0,分别为,LP,和,LD,的最优解。,证明：设,LP,的最优解为,X*,LD,的最优解为,Y*,又因为：,CX* CX,0,=Y,0,b Y*b,又由弱对偶性定理：,CX ,Yb,则,X,0,必为,X*,Y,0,必为,Y*,3.,强对偶性,若原问题和对偶问题均具有可行解，则两者均具有最优解，且他们的最优解的目标值相等。,11/26/2024,25,浙江科技学院经济管理学院管工系,4.,互补松弛定理,如果,X*,Y*,分别为,LP,LD,问题的可行解，则,X*,Y*,为最优解的充要条件为：,Y*X,S,*=0,Y,S,*X*=0,当,LP,中第,i,个约束是严格不等式，则,Y,中的,Yi,必为,0,，如果,Yi,不为,0,则,LP,中第,i,个约束为严格等式。,当,LD,中第,j,个约束是严格不等式，则,X,中的,xj,必为,0,，如果,xj,不为,0,则,LD,中第,j,个约束为严格等式。,11/26/2024,26,浙江科技学院经济管理学院管工系,课堂作业,P74 2.3,课后作业,(P75-P76),2.4,2.5,2.6,2.7,11/26/2024,27,浙江科技学院经济管理学院管工系,2.3,影子价格,阐述对偶变量的经济意义，即对偶变量的经济解释,引例：美佳公司,如果已知,LP,的,X*=(7/2,3/2,15/2,0,0) Z*=8.5,求解,Y*,W*,？,由对偶问题的基本性质知：,W*=Z*=8.5,15Y,1,+24y,2,+5y,3,=8.5,又因为,Y*X,S,*=0 X*,代入,LP,的约束条件中，知,为严格不等式，则,x,S1,0,，则,y,1,=0,由互补松弛定理：,因为,Y,S,*X*=0 X10,X20,则,y,S1,*=0, y,S2,*=0,，即,LD,的,，,为严格等式,6y,2,+y,3,=2,5y,1,+2y,2,+y,3,=1,Y,1,=0,Y,2,=1/4,y,3,=1/2,11/26/2024,28,浙江科技学院经济管理学院管工系,1.,定理：根据对偶问题的基本性质,对,LP,为生产问题而言：,bi,表示,LP,中第,i,种资源的拥有量；,Cj,表示第,j,种产品的利润或产值,其中,Yi*,可用下面数学式求得：,1,）,yi,*,可解释为第,i,种资源的边际价格，即在其他条件不变的情况下，只增加单位第,i,种资源所引起的目标函数最优值的变化，,bibi+1,bi=1,，,Z*,的值为,yi,*,。,2,）,yi,*,也可解释为出让单位第,i,种资源的收益；,3,）,yi,*,的取值随,cj,xj,Aij,的变化而变化，因此企业不同，产业不同，资源拥有量不同，,yi,*,的值不同，是具体企业，具体产品和具体资源拥有量的特定价格。,11/26/2024,29,浙江科技学院经济管理学院管工系,例：美佳公司,X*=(7/2,3/2,15/2,0,0) Z*=8.5,由,1,）可知：,y1*,为,变为,5x216,时,Z*,的增量，,y1*,Z*,0,Y2*,为,变为,6x1,2x225,时,Z*,的增量,所以当,A,的资源增加时，,Z*,无变化，,Y1*,0,LP,中,约束为严格的不等式，表明,A,没有被充分利用。,11/26/2024,30,浙江科技学院经济管理学院管工系,2.,影子价格的应用（对偶问题的应用）,1,）,yi,*,实际上是一种机会成本，当,A,的单位市场价格无论多低时，还应卖出,A,资源，直到,15/2,；当,B,的单位市场价格,0,表明该资源已充分利用，因此该资源的增加或减少均会引起,Z*,的变动，,Yi*,越大，变动越大。,由美佳可得：,Y1=0,表明,A,没有充分利用，,y2=1/4,y3=1/2,表明,y3,的变动对美佳公司利益的影响要大。,3,）新产品是否投产以及合理定价的问题,例：美佳考虑生产,电器,，要耗,A 3,，,B 2,，调试,1,个单位，市场价格,2,元，问是否值得生产。又如果美佳决定生产该种产品，则要定价多少该公司才不会亏本。,11/26/2024,31,浙江科技学院经济管理学院管工系,4,）合理调配资源,因为影子价格是资源在特点环境下的价值，随环境的变化而变化，同一资源在有些使用中价值低，有些使用中价值高。,例：美佳公司有两个子公司,（,1,）,A0,B 1/4,C 1/2,(2) A2,B 0,C 1,因此： （,1,） （,2,）,A A,B,B,C C,11/26/2024,32,浙江科技学院经济管理学院管工系,课后作业,P76 2.8,11/26/2024,33,浙江科技学院经济管理学院管工系,2.4,对偶单纯形法,一、基本思路,从,LP,的一个基解出发，转换到另一个基解；在转换过程中，保持对应的,LD,的解,Y,的可行性（相当于,LP,的,j,0,），逐步消除该基解的不可行性，直到基解变成可行解，就获得了最优解。,注：该方法不是求解,LD,的单纯形法，而是利用对偶关系求解,LP,的另一种方法。,11/26/2024,34,浙江科技学院经济管理学院管工系,二、计算步骤：,1.,假定已给一对偶可行基单位阵,B,（对应,LD,问题的解可行），相应的基解,X,B,b,。,2.,若,b,的各个分量均非负，则这个解就是最优解，停止迭代。,3.,如果,X,B,有分量,x,l,0,，且,x,l,所在行的所有系数,a,lj,0,，则,LP,无可行解，停止迭代,。,如果,X,B,有分量,x,l,0,，且该分量所在行的系数,a,lj,有负分量，则该解不是,LP,的最优解，继续。,4.,如果,min b,i,/ b,i,0,b,l,，则,x,l,为换出变量,min,j,/,a,lj,|al,j,0=,k,/,a,lk,则,x,k,为换入变量,5.,以,a,lk,为主元，进行系数行变换，得一新的对偶可行基解,(,也称正则解），转第,2,步。,11/26/2024,35,浙江科技学院经济管理学院管工系,比较,单纯形法,和,对偶单纯形法,单纯形法：,先从基解、可行解出发，通过若干次迭代使满足,j,0,对偶单纯形法,:,先从基解， 对偶可行解（等价于,j,0,）出发，再通过若干次迭代使之可行。,对偶单纯形法的优缺点：,优点,:,初始基解可为负，减少人工变量数量，使计算简单；灵敏度分析时使用方便。,缺点：,不能保证所有的,Lp,问题的初始单纯形表中的,j,0,。,11/26/2024,36,浙江科技学院经济管理学院管工系,例,:,cj,-2,-3,-4,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,X4,-3,-1,-2,-1,1,0,0,x5,-4,-2,1,-3,0,1,j,-2,-3,-4,0,0,1,4/3, ,0,x4,-2,x1,1,2,-1/2,3/2,0,-1/2,-1,0,-5/2,1/2,1,-1/2,j,0,-2,-1,0,-1,4/5,2,-3,x2,-2,x1, ,1,2/5,0,-1/5,-2/5,1/5,11/5,1,0,7/5,-1/5,-2/5,j,0,0,-9/5,-8/5,-1/5,所以：,X*=(x,1,x,2,),T,=(11/5,2/5),T,Z*=28/5,11/26/2024,37,浙江科技学院经济管理学院管工系,课后作业,2.9,（,1,）,11/26/2024,38,浙江科技学院经济管理学院管工系,2.5,灵敏度分析,C,j,变化时,b,i,变化时,增加一个变量,x,j,时,增加一个约束条件时,技术系数,P,j,发生变化时,11/26/2024,39,浙江科技学院经济管理学院管工系,LP,变化导致的变化可分为：,X*,不变，,Z*,改变,X*,中基变量不变，取值改变，,Z*,改变。,X*,中基变量改变，,Z*,改变,X,B,X,N,X,S,X,S,B,N,I,b,X,B,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,11/26/2024,40,浙江科技学院经济管理学院管工系,一、分析,c,j,变化,当,C,Nj,发生变化时， 对应的,Nj,变化,N,j,0 X*,Z*,不变,Nj,0,用单纯形法进行基变换,X,B,X,N,X,S,X,S,B,N,I,b,X,B,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,当,C,Bi,发生变化时， 所有,Nj,变化,Nj,0 X*,不变,Z*,变化,Nj,0,用单纯形法进行基变换,11/26/2024,41,浙江科技学院经济管理学院管工系,例,5,：美佳公司,1.,当,C1,由,2,变为,1.5,时， 当,C2,由,1,变为,2,时，最优解有什么变化？,2.,当,C1,不变，,C2,在什么范围内变换时，最优解不变？,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,15/2,0,0,1,5/4,-15/2,2,x1,7/2,1,0,0,1/4,-1/2,1,x2,3/2,0,1,0,-1/4,3/2,j,0,0,0,-1/4,-1/2,解：,1,Cj,1.5,2,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x4,6,0,0,4/5,1,-6,1.5,x1,2,1,0,-1/5,0,1,2,x2,3,0,1,1/5,0,0,j,0,0,-1/10,0,-3/2,1.5,1.5,1/8,-9/4, ,2,2,解：,2,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,15/2,0,0,1,5/4,-15/2,2,x1,7/2,1,0,0,1/4,-1/2,1,x2,3/2,0,1,0,-1/4,3/2,j,0,0,0,-1/4,-1/2,c,2,c,2,4,5,4,=,（,c,2,-2,）,/40,5,=,（,2,3c,2,）,/2,0,2/3,c,2,2,11/26/2024,42,浙江科技学院经济管理学院管工系,二、分析,b,i,变化,该变化只会引起右侧常数的变化：,B,-1,b,0,则基变量不变，,X*,的取值变化，,Z*,变化,B,-1,b,0,用对偶单纯形法进行基变换,X,B,X,N,X,S,X,S,B,N,I,b,X,B,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,11/26/2024,43,浙江科技学院经济管理学院管工系,例,6,：美佳公司,1.,当其他能力不变，,B,设备由,24,变为,32,时，最优解有什么变化？,2.,当,A,B,不变，调试工序能力在什么范围内变换时，基变量不变？,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,35/2,0,0,1,5/4,-15/2,2,x1,11/2,1,0,0,1/4,-1/2,1,x2,-1/2,0,1,0,-1/4,3/2,j,0,0,0,-1/4,-1/2,解：,1,：,Cj,2,1,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,0,x3,15,0,5,1,0,0,2,x1,5,1,1,0,0,1,0,x4,2,0,-4,0,1,-6,j,0,-1,0,0,-2, ,解：,2,4,b,3,6,11/26/2024,44,浙江科技学院经济管理学院管工系,三、增加一个变量,x,j,的分析,相当于在单纯形表中增加了一列,x,k,：,k,0,则,X*,Z*,不变,k,0,在最终单纯形表上进行基变换（添加一个变量，增加一列），系数列向量应相应变化,P,k,=B,-1,P,k,例,7,：新产品,，,耗,A3,小时，,B4,小时，调试时间,2,小时，预期盈利,3,元,/,件，问是否值得投产？如投产，该生产计划如何变化？,解：设,x6,代表生产产品,的件数。,表示值得投产,11/26/2024,45,浙江科技学院经济管理学院管工系,四、增加一个约束条件的分析,相当于添加一道工序。通常把,X*,代入新的约束条件。,若满足，,X*,Z*,不变。,若不满足，把新约束放入最终单纯形表中，用初等行变换使变成基解，再用对偶单纯形法变换。,11/26/2024,46,浙江科技学院经济管理学院管工系,例,9,：美佳公司增加一道环境检测工序，,：,3h,，,：,2h,，能力是,12h,，分析,该生产计划如何变化？,解：把,X*=(x1,x2,x3)=(7/2,3/2,15/2),代入新约束：,37/2,23/2,27/2,12,不满足新约束。,cj,2,1,0,0,0,0,CB,XB,b,x1,x2,x3,x4,x5,x6,0,x3,15/2,0,0,1,5/4,-15/2,0,2,x1,7/2,1,0,0,1/4,-1/2,0,1,x2,3/2,0,1,0,-1/4,3/2,0,0,x6,12,3,2,0,0,0,1,j,0,0,0,-1/4,-1/2,0,0,x3,15/2,0,0,1,5/4,-15/2,0,2,x1,7/2,1,0,0,1/4,-1/2,0,1,x2,3/2,0,1,0,-1/4,3/2,0,0,0,0,1,0,x6,-3/2,-1/4,-3/2,j,0,0,0,-1/4,-1/2,0,-,-,-,1,1/3,-, ,0,x5,1,0,0,0,1/6,1,-2/3,0,x3,15,0,0,1,5/2,0,-5,2,x1,4,1,0,0,1/3,0,-1/3,1,x2,0,0,1,0,-1/2,0,1,j,0,0,0,-1/6,0,-1/3,11/26/2024,47,浙江科技学院经济管理学院管工系,五、技术系数,Pj,发生变化分析,通常是按列即,P,j,发生变化，该变化可转变为增加,x,j,的情况：,k,0,则,X*,Z*,不变,k,0,在最终单纯形表上进行基变换（添加一个变量，增加一列），系数列向量应相应变化,P,k,=B,-1,P,k,11/26/2024,48,浙江科技学院经济管理学院管工系,课后作业,2.14,2.16,11/26/2024,49,浙江科技学院经济管理学院管工系,