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

《对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《对偶理论与灵敏度分析.ppt（91页珍藏版）》请在三一文库上搜索。

1、1,第二章 线性规划的对偶理论,窗含西岭千秋雪，门泊东吴万里船,本章主要内容： 线性规划的对偶问题概念、理论及经济意义 线性规划的对偶单纯形法 线性规划的灵敏度分析,2,第一节 对偶问题的提出,假设工厂考虑不进行生产而把全部资源都转让，问如何定价这些资源，既能使其获利不低于安排生产所获得的收益，又能使资源租让具有竞争力。,一、引例,Max Z = 2000x1+4000x2+3000x3 s.t. 3x1+4x2+2x3600 2x1+ x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1, x2, x30,Min W =600y1+400y2+300y3+200y

2、4 s.t. 3y1+2y2+ y3+ y42000 4y1+ y2+3y3+2y44000 2y1+2y2+3y3+4y43000 y1, y2, y3, y40,x1 x2 x3,y1 y2 y3 y4,3,比较上述模型，可以得出两者之间的一些关系： 1. 两个问题，一个是极大化，另一个是极小化； 2. 一个问题的变量数等于另一问题的方程数，反之亦然； 3. 一个问题的目标函数系数是另一个问题的约束方程右端常数，反之亦然； 4. 两个问题的约束方程系数矩阵互为转置。,称变量yi为第一个LP的第i个对偶变量， 或第一个LP的第i约束相应的对偶变量,4,二、对偶问题,（1）对称LP问题的定义,

3、（2）对称LP问题的对偶问题,第一类对称形式,第二类对称形式,（1）变量为非负； （2）约束条件为不等式。 对于max ，约束为“” ； 对于min，约束为“”,5,例1 写出下列LP问题的对偶问题,Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0,Min W =8y1+16y2+12y3 s.t. y1+4y2 2 2y1 +4y3 3 y1 ,y2,y3 0,6,（3）对偶问题的对偶是原问题,推导过程,变形,对偶,Max Z=CX s.t. AXb X0,Min W=Yb s.t. YAC Y0,Max W = -Yb s.t. -YA

4、 -C Y0,Min Z = (-C)X s.t. (-A)X (-b) X0,Max W = Y(-b) s.t. Y(-A) (-C) Y0,7,例2 写出下列LP问题的对偶问题,解: 上述LP问题的 对偶问题为：,8,三、非对称LP问题的对偶问题,例3 写出下列LP问题的对偶问题,解：用x2= -x2, x3=x3-x3代入上述LP问题，并将其化为第一类对称形式,Max Z = x1+2x2+x3 x1+x2-x3 2 s.t. x1 -x2+x3 = 1 2x1+x2+x3 2 x10, x20 ,x3无约束,Max Z = x12x2 +x3 x3 x1 x2 x3+x3 2 x1+

5、x2+x3 x3 1 s.t. x1 x2 x3+x3 1 2x1+x2 x3+x3 2 x1, x2, x3, x3 0,x1 -x2+x3 1 x1 -x2+x3 1,x1 -x2+x3 1 -x1 +x2-x3 - 1,-2x1-x2-x3 -2,9,上述第一类对称形式LP问题的对偶问题为：,则上述问 题变为：,Min W =2y1+y2 y32y4 y1+y2 y32y4 1 y1+y2 y3 +y4 -2 s.t. y1+y2 y3y4 1 y1 y2+y3 +y4 -1 y1, y2, y3, y4 0,Min W =2u1+u2+2u3 u1+u2+2u3 1 s.t. u1 u

6、2+ u3 2 u1+u2+ u3 =1 u10, u30 ,u2无约束,令 u1= y1 u2=y2y3 u3=y4,Max Z = x12x2 +x3 x3 x1 x2 x3+x3 2 x1+x2+x3 x3 1 s.t. x1 x2 x3+x3 1 2x1+x2 x3+x3 2 x1, x2, x3, x3 0,-y1+y2 -y3 -y4 1,y1-y2+y3 -y4 2,10,对偶关系：一个问题第i个变量的约束情况决定另一问题第i个约束不等式的方向，反之亦然。,正常的对正常的，不正常的对不正常的,原问题约束条件是等式对应于对偶问题决策变量无约束，反之亦然,11,例3 直接写出LP问题

7、的对偶问题,12,13,原问题,对偶问题,目标函数,Max z,Min w,变量,n个,约束条件,n个,=,0,0,无约束,约束条件,m个,=,变量,m个,0,0,无约束,约束条件右端项,目标函数变量的系数,目标函数变量的系数,约束条件右端项,原问题,对偶问题,14,第二节 LP问题的对偶理论,若X(0),Y(0)分别为(L),(D)的可行解，则有CX(0)Y(0)b,定理1(弱对偶定理): 极大化原问题目标函数值总是不大于其对偶问题的目标函数值。,证明：max z=CX;AXb;X0(L) min w=Yb;YAC;Y0(D) 由于X(0)是(L)的可行解，有AX(0)b, X(0)0. 由

8、于Y(0)是(D)的可行解，有Y(0)0. Y(0)左乘不等式组AX(0)b的两边得： Y(0)AX(0) Y(0)b (1),15,min w=Yb;YAC;Y0(D) 又Y(0)AC 用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,16,推论1,若对偶问题有无界解，则其原问题无可行解； 若对偶问题无可行解，则其原问题或有无界解或无可行解。,原问题,对偶问题,若LP问题有无界解，则其对偶问题无可行解(弱对偶性)； 若LP问题无可行解，则对偶问题或有无界解或无可行解。,17,

9、推论2,极大化问题（L）的任何一个可行解所对应的目标函数值都是其对偶问题（D）目标函数值的下界。,极小化问题（D）的任何一个可行解所对应的目标 函数值都是其对偶问题（L）目标函数值的上界。,推论3,YbCX(0),CX Y(0)b,max z=CX; AXb; X0(L) min w=Yb; YAC; Y0(D),18,例4 考虑下面一对LP问题,其对偶问题为：,由于X(0) =(1,1,1,1)T, Y(0)=(1,1)T分别为(L),(D)的可行解，,Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x

10、2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,Z(0)=10,W(0)=40,W10,推论2,Z40,推论3,故Z40,W10.,19,例,试用对偶理论证明上述线性规划问题无最优解,证明：首先看到该问题存在可行解，如X=(0,0,0) 上述问题的对偶问题为,由第一约束条件知对偶问题无可行解，因原问题有可行解，由推论1，原问题无最优解。,若对偶问题无可行解， 则原问题或有无界解 或无可行解。,20,定理2（最优性准则） 当LP问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为

11、最优解。,若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，有YbCX(0)，由于CX(0) =Y(0)b，YbY(0)b，Y(0)为(D)的最优解。,21,例5,Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0,

12、Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,由于X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是(L)，(D)的可行解且 CX(0)=bTY(0)=28，所以X(0),Y(0)分别为(L)，(D)的最优解。,22,线性规划的矩阵表示,Max Z=CX s.t. AX b X0,令A=(B,N), X= XB ,C=(CB,CN) XN,Max Z=CX+0Xs s.t. AX+IXs=b X, Xs0,用非基变量表示基变量,用非基变量表示目标函数,23,=(0, CN-CBB-1N,

13、 -CB B-1) =(C-CBB-1A, -CB B-1),(C-CBB-1A, -CB B-1)= (C-CBB-1(B,N), -CB B-1),=(CB-CBB-1B, CN-CBB-1N, -CB B-1),=(0, CN-CBB-1N, -CB B-1),若CN-CBB-1N0, -CB B-10,则Z为最优解,令XN=0, Xs=0，可以得到基B的基可行解和目标函数值,XB=B-1b-B-1NXN -B-1Xs,Z= CBB-1b+(CN-CBB-1N)XN -CB B-1Xs,X=(XB, XN, Xs)=(B-1b,0,0),Z= CBB-1b,24,CB,XB,B-1b,C

14、B,CN,0,I,CN-CBB-1N,B-1N,B-1,0,-CBB-1,-CBB-1b,25,初始单纯形表,0 x3 0 x4 0 x5,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,经过一次迭代,初始基,第一轮迭代后的基,26,初始单纯形表,0 x3 0 x4 0 x5,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,经过一次迭代,B-1 b=,Z= CBB-1b=9,27,初始单纯形表,0 x3 0 x4 0 x5,2

15、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,经过一次迭代,B-1A=,-CBB-1,=(0, 0, -3/4),A,28,定理3（强对偶定理） 若(L)，(D)均有可行解，则(L)，(D)均有最优解，且目标函数最优值相等。,证明： 设X(0),Y(0)分别为(L)，(D)的可行解,由弱对偶定理(推论3)，对于(L)的任意可行解X，有CX Y(0)b，所以CX在可行域内有上界，故(L)有最优解。 同理，对于(D)的任意可行解Y，由弱对偶定理（推论2），有Y bCX(0)，所以Yb在可行域内有下界，故(D)有最优解

16、。,设(L)的最优解为X(0)，且X(0)所对应的最优基为B， X(0)可以表示为X(0) = XB(0) = B-1b XN(0) 0,max z=CX; AXb; X0(L),min w=Yb; YAC; Y0(D),29,则(A,S)= (C,0) CBB-1(A, I)=(C CBB-1A, CBB-1)0 由于CCBB-1A0， 所以CBB-1A C (1) 又CBB-10，故CBB-10. (2),令Y(0)=CBB-1，由(1)、(2)知Y(0)是(D)的可行解. 因为CX(0)=(CB, CN) XB(0) =CBXB(0)+CNXN(0) = CBB-1b XN(0) 而Y(

17、0)b = CBB-1b 则CX(0)=Y(0)b ，由最优性准则知， X(0),Y(0)分别为(L)，(D)的最优解, 且目标函数最优值相等。,30,推论： 在用单纯形法求解LP问题(L)的最优单纯形表中，松弛变量的检验数的相反数就是其对偶问题(D)的最优解。,例5 求下列问题对偶问题的最优解,Max Z =2x1+3x2 s.t. x1+ 2x28 4x1 16 4x2 12 x1 ,x2 0,解：化为标准型,Max Z =2x1+3x2+0x3+0x4+0x5 s.t. x1+ 2x2+x3 = 8 4x1 +x4 =16 4x2 +x5=12 x1 ,x2 , x3, x4, x50,

18、CB,XB,B-1b,CB,CN,0,I,CN-CBB-1N,B-1N,B-1,0,-CBB-1,-CBB-1b,Y*=(CBB-1)T,31,此时达到最优解X*=(4, 2)T, Max Z=14。 对偶问题的最优解为Y*=(3/2, 1/8, 0)T,运用单纯形法计算得原问题的最终表如下：,32,推论：对偶问题的最优解对应于原问题的最优单纯型表中松弛变量检验数的相反数或剩余变量的检验数。,33,Min z=2x1+3x2 x1+x2 350 x1 125 2x1+x2 600 x1, x2 0,Max w=350y1+125y2+600y3 s.t. y1+ y2+2y32 y1 + y3

19、 3 y1 ,y2 0 ;y3 0,原问题的最优单纯型表如下所示：,0 0 4 0 1 -4+M M,Y*=(4, 0, -1)T,w*=800,例,34,定理4（互补松弛定理）在最优情况下，原问题的第i个决策变量与其对偶问题第i个约束中的松弛变量的乘积恒为零。,设X(0),Y(0)分别为(L),(D)的可行解，则X(0),Y(0)分别为(L),(D)的最优解的充要条件为 ,有,35,互补松弛性:在线形规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之,如果约束条件取严格不等式,则其对应的对偶变量一定为零。,36,例7 考虑下面问题,Max Z = x1+

20、2x2+3x3 +4x4 x1+2x2+2x3+3x4 20 s.t. 2x1+ x2+3x3+2x4 20 x1,x2,x3,x4 0,Min W = 20y1+20y2 y1+2y2 1 2y1+ y2 2 s.t. 2y1+3y2 3 3y1+2y2 4 y1,y20,已知(D)的最优解为 Y*=(6/5,1/5)T 用互补松弛定理求出(L)的最优解。,37,x1*=x2*=0.,解：由于y1* 0, y2* 0,由互补松弛性知,解得x3*= x4*=4. 所以(L)的最优解为X*=(0,0,4,4)T,因为,代入(1),(2)得,由互补松弛性知，,38,若X*,Y* 分别为(L),(D

21、)的最优解，那么CX*=Y*b。 由 Z*= Y*b =y1*b1+y2*b2+ym*bm 可知 Z*/ b= Y* yi*=Z*/ bi yi*表示资源量bi 变化1个单位对目标函数最优值Z 产生的影响，称之为第i 种资源的影子价格。,第三节 对偶问题的经济解释-影子价格,一、影子价格 (Shadow Price),1.定义 影子价格是最优配置下资源的理想价格。,2.含义,对偶问题的最优解实际上就是右端常数项的单位变化所引起的目标值的变化。,39,-14 0 0 -3/2 -1/8 0,例8 下面是一张LP问题的最优单纯形表，其中x3, x4, x5为松弛变量,则对偶问题的最优解为Y*=(1

22、.5, 0.125, 0)T,40,例8,X* =(4, 2)T，Z* =14,Q(4, 2) Z=14,x1,x2,4x1=16,4x2=12,x1+2x2=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 =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0,8,X1* =(4, 2.5)T，Z1*=15.5,X2* =(4.25, 1.875)T，Z2* =14.125,X3* =(4, 2)T，Z3* =14,41,资源进行最优配置后获得的收益,资源i的数

23、量,资源i的价格,它代表在资源最优利用条件下对各种单位资源的估价，这种估价不是资源的市场价格，而是根据资源在企业生产中所作出的贡献而作出的估价，为区别起见，称之为影子价格(shadow price)。,42,资源的影子价格是针对具体生产或具体企业而言的： 同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；A 产品的市场价格发生变化，资源的影子价格也会发生变化；C 资源的数量结构不同，资源的影子价格也不同。b,I II 设 备 1 2 8台时 原材料A 4 0 16公斤 原材料B 0 4 12公斤,2 3,a21=3 (1.5, 1/6, 0),c2=4 (2, 0, 0),b1=

24、10 (0, 0.5, 0.75),43,（1）告诉管理者增加何种资源对企业更有利；,（2）告诉管理者花多大代价买进资源或卖出资源是合适的（在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当当某种资源的市场价高于影子价格时，企业决策者应把已有资源卖掉）； （3）为新产品定价提供依据。,二、影子价格的作用,44,第四节 对偶单纯形法,正则解：设X(0)是线性规划问题(Max)的一个基本解，如果它的检验数j0(jJ)，则称X(0)是该线性规划问题的一个正则解。相应的基称为正则基。,0 x4 0 x5 0 x6,-4 8 -2,-1 1 -1 1 0 0 1

25、 1 2 0 1 0 0 -1 1 0 0 1,0 -1 -2 -3 0 0 0,-1 -2 -3 0 0 0,正则解若是可行解，则它是最优解。,45,第四节 对偶单纯形法,从一基可行解(B-1b0)出发，在满足可行解的基础上，通过逐次基可行解的转换，直至j0(jJ)成立（对max问题），即达到可行的正则解，从而判断是否得到最优解或无最优解。,从一正则解(j0(jJ)出发（对max问题），在满足正则解的基础上，通过逐次转换，直至B-1b0成立，即达到满足正则解条件的可行解，从而判断是否得到最优解或无最优解。,单纯形法的基本思想：,对偶单纯形法的基本思想：,46,例9 用对偶单纯形法求解下列LP

26、问题,解：原问题变形为,Min Z = x1+2x2+3x3 s.t. x1 -x2+ x34 x1+x2+2x38 x2 - x32 x1, x2, x30,Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3-4 x1+x2+2x38 -x2+ x3-2 x1, x2, x30,Max Z = -x1-2x2-3x3 s.t. -x1+x2 - x3+x4 =-4 x1+x2+2x3 +x5 = 8 -x2+ x3 +x6=-2 x1, x2, x3, x4, x5, x60,一、对偶单纯形法的举例,第一类对称形式,47,0 x4 0 x5 0 x6,-4 8 -2,-

27、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,4 0 -3 -2 -1 0 0,-1 -2 -3 0 0 0,Min-4，-2,=Min ,Min-2,=Min ,48,10 0 0 -5 -1 0 -3,Z* = x1* +2x2*+3x3*=10,所以,49,二、对偶单纯形法的步骤,(1)化LP问题的约束条件为“”形式,引入松弛变量,建立初始表; (2)若所有常数项bi0，则最优解已经达到，否则bl=Minbi|bi0， 选取bl所对应的变量为出基变量； (3)计算k=Minj /alj |alj0，选取k所对应的变量为进基变

28、量； (4)以alk为主元素进行旋转运算，转第二步。,50,三、几个问题的讨论,1.对偶单纯形法适用于具有正则解的LP问题。 正则解所对应的对偶问题的解是基可行解 2.对偶单纯形法所包含的创新思想：原问题的初始可行解不一定要是基可行解，可以从非基可行解开始迭代。 3.当变量多于约束条件时，对这样的线性规划问题用对偶单纯形法计算可以减少工作量。 4.在灵敏度分析时，有时需要用对偶单纯形法。,51,单纯形法,原问题,对偶问题,基可行解,非可行解,基可行解,基可行解,对偶单纯形法,原问题,对偶问题,非可行解,基可行解,基可行解,基可行解,52,1.最优性：j cj - CBB-1Pj0（Max） 2

29、.可行性：XB* B-1b0,二、灵敏度分析常用的两个公式,一、灵敏度分析的定义,三、灵敏度分析的几种可能结果 1.最优解保持不变 2.最优基不变，但最优解改变 3.最优基改变,第五节 线性规划的灵敏度分析,53,1.直接用单纯形表求B-1,四、右端项 b 的变化分析求B-1,由AXb AX+IXS=b （初始表）,两边左乘B-1得 B-1AX+ B-1XS= B-1b （最优表）,例1 LP问题,Max Z =2x1+3x2 x1+ 2x28 s.t. 4x1 16 4x2 12 x1 ,x2 0,的初始单纯形表和最优单纯形表如下,54,最优表：,四、右端项 b 的变化分析求B-1,初始表：

30、,最优基 的逆B-1,B-1b=,B-1A=,B-1I=B-1,55,2.公式推导,假设b只有一个分量br 发生变化，br=br+br， 则B1(b+b )B-1b +B-1b,四、右端项 b 的变化分析公式推导,56,即,则,解不等式组得 br 的变化范围：,注：(1) 此时最优基不变，但最优解发生改变。 (2) 此变化范围仅适用于b 的一个分量发生变化的情形。,四、右端项 b 的变化分析公式推导,57,例2 下面是求解同一LP问题的初始单纯形表和最优单纯形表，求b1,b2,b3的变化范围，使原最优基不变。,初始表,最优表,四、右端项 b 的变化分析例题,58,解：,59,解：,对b1，有,

31、60,例3 下面是某LP问题的单纯形表，x4, x5为松弛变量。,（1）求的取值范围，使得原最优基仍为最优基； （2）求为何值时，使得原最优基不变而目标函数值最大。,假设原来的b被 b + b 代替，其中 b= 1 -1,四、右端项 b 的变化分析例题,B-1,-CBB-1,61,解: (1) B-1= 3 -1 -1 1,所以 -1/41。,XB* = B-1 ( b + b ) = B-1b +B-1 - = 1 + 3 -1 2 -1 1 - = 1+4 0 2 -2,当1时，Z*=10，达到最大。,62,解：（1）设I、II两种产品的产量分别为x1, x2。建立该问题的数学模型为:,例

32、4,I II 设 备 1 2 8台时 原材料A 4 0 16公斤 原材料B 0 4 12公斤,工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。 （1）应如何安排生产使该厂获利最多？ （2）工厂新增24公斤原材料A，问如何安排新的生产计划以使获利最多？,四、右端项 b 的变化分析例题,63,用单纯形法求得最优单纯形表如下：,最优生产计划为：生产4件产品I，2件产品II；最大利润为14。,B-1,64,（2）工厂新增24公斤原材料A，则,新的最优生产计划为：生产8件产品I，0件产品II；最大利润为16。,将其代入原最优表，并利用对偶单纯形法迭代：,(-8),x4,65,例5 下面是一

33、张LP问题的最优单纯形表,观察其目标函数系数的改变对检验数的影响,五、价值系数 C 的变化分析,cj 的变化会引起检验数j= cj -CBB-1Pj 的变化,有两种情况: 非基变量的价值系数cj 变化，不影响其它检验数. 基变量的价值系数cj 变化，影响所有非基变量检验数.,66,1.非基变量价值系数的改变,若非基变量的价值系数cj 变为cj = cj +cj ，,讨论： (1)当j0，即cj -j 时，原最优解不变； (2)当j 0，即cj -j 时，原最优解改变。,五、价值系数 C 的变化分析公式推导,则xj 的检验数为,67,例6 Max Z = -2x1 - 3x2 - 4x3 s.t

34、. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1, x2, x3, x4, x5 0,五、价值系数 C 的变化分析例题,最优单纯形表为,为使原最优解不变，求 c3 的变化范围。,68,解：最优单纯形表为,从表中看到3=-9/5+c3 ,可见,当c3 9/5 ，即 c3 -49/5-11/5时，原最优解不变。,69,2. 基变量价值系数的改变,五、价值系数 C 的变化分析公式推导,即,若基变量 的价值系数 变为 则,非基变量xj的检验数由j= cj -CBB-1Pj 变为,70,2. 基变量价值系数的改变,五、价值系数 C 的变化分析公式推导,71,例7

35、 下表为最优单纯形表,计算 c2 变化的范围，使得原最优解不变。,五、价值系数 C 的变化分析例题,72,当-3c21，即 0c24 时，原最优解不变。,3=0-1/2(3+c2)=-3/2 -c2/2 0 4=0-2/4+1/8(3+c2)=-1/8+c2/8 0,73,1.增减变量,(2)删除变量 删除非基变量最优解不变 删除基变量的处理方法： 将xj 的系数cj 变为-M(最大化问题)，迫使xj0,(1)增加变量 若所增加变量的检验数0，则原最优解不变； 否则，用单纯形法迭代求最优解。,六、技术矩阵 A 的变化分析,74,例9,I II 设 备 1 2 8台时 原材料A 4 0 16公斤

36、 原材料B 0 4 12公斤, 2 6 3,利润(元) 2 3,5,B-1,75,例9,1.5 2 0.25,3= c3-CBB-1P3,=5-(2, 0, 3)(1.5, 2, 0.25)T=1.250,1.25,说明增加产品的生产，可以提高企业的的收益。,利用单纯形法进行迭代,76,例9,最优生产计划： 生产产品I 1件 产品II 1.5件 产品III 2件 总利润为： 16.5元。,77,2.Pj 的变化,则最优解不变,则原最优解改变,六、技术矩阵 A 的变化分析,如生产产品的工艺发生变化,78,例10,设 备 8台时 原材料A 16公斤 原材料B 12公斤,I 2 5 2,利润(元),

37、4,II 2 0 4 3,I 1 4 0 2,4 x1,79,4 x1,1= c1-CBB-1P1,=4 - (2, 0, 3)(1.25, 0.5, 0.375)T=0.3750,利用单纯形法进行迭代,1.25 0.5 0.375,0.375,1.25,80,4 x1,1 0 0,0,最优生产计划： 生产产品I 3.2件 产品II 0.8件 总利润为： 15.2元,81,六、技术矩阵 A 的变化分析,化约束条件为的形式，引入松弛变量xn+1； 把增加的约束条件直接写入最优表(以松弛变量xn+1为基变量)，得到一个非标准表； 化非标准表为标准表，若b n+1 ，则最优解仍为最优解，若bn+1，

38、则用对偶单纯形法迭代找出最优解。,3.增加约束条件,82,例8 已知某LP问题的最优单纯形表如下：,如果增加约束条件x1+x32，最优解将如何变化？,六、技术矩阵 A 的变化分析,x1*=1, x2*=2 Z*=8,83,x6 -2 -1 0 -1 0 0,0 x6 0 0 1,非标准表,标准表,x1+x32 -x1-x3 -2 -x1-x3+x6= -2,84,x1*=2, x2*=1 Z*=7,85,课堂练习,下面是某LP问题的最优单纯形表，当增加约束条件 x1+x24时，最优解如何变化？,86,原最优解不变,第3行-第1行 第3行-第2行,87,例：某家具厂制造桌子和椅子，所用的资源有木

39、工和油漆工，生产数据如下表：,(1) 用单纯形法求利润最大的生产方案； (2) 若桌子的利润有可能下降，求使最优解不变的允许下降幅度； (3) 若要扩大生产规模，该家具厂应优先增加哪种资源，为什么？,88,解：（1）该问题的数学模型：,化为标准型,89,因此，该问题最优解是x1*=15，x2*=20，最优利润z*,90,（2）,要使得(1)中求得的最优解仍为最优，必须有-5+c1/20且 -15-3c1/20，则-10c110，因此最优解不变的允许 下降幅度为-10，0。,91,（3）从最终最优单纯型表可看出松弛变量x3，x4的检验数分 比为-5，-15，而最大化线性规划问题的最优单纯型表中， 松弛变量的检验数的相反数就是其对偶问题的最优解，因此 其对偶问题的最优解为 ， 的经济含义是在其他资 源不变的情况下，第i资源变化1单位时，原问题的最优目标函 数值的变化量，因此，若要扩大生产规模，该家具厂应优先增 加油漆工资源。,，,