运筹学课件对偶理论及灵敏度分析.ppt

《运筹学课件对偶理论及灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学课件对偶理论及灵敏度分析.ppt（137页珍藏版）》请在三一办公上搜索。

1、1,对偶线性规划,对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的互补松弛关系对偶单纯形法对偶的经济解释灵敏度分析,DUAL,dual linear programming,2,2.1 线性规划的对偶问题,一、对偶问题的提出 现有甲乙两种原材料生产A1，A2两种产品，所需的原料，甲乙两种原料的可供量，以及生产A1,A2两种产品可得的单位利润见表。问如何安排生产资源使得总利润最大？,3,解:设生产A1为x1单位，生产A2为x2单位,则线性规划问题为：,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,解：设甲资源的出让单价为y1,乙资

2、源的出让单价为y2,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？,4,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源

3、？,5,解：设生产A1为x1件，生产A2为x2件，则线性规划问题为：,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,解：设甲资源的出让价格为y1,乙资源的出让价格为y2,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5y25 y1,y20,另一方面，假设另一公司想把资源买过来，它至少应付出多大代价才能使原来公司放弃生产，出让资源？,二、对称形式下对偶问题的一般形式,定义：变量均为非负约束的情况下，约束条件在目标函数取极大值时均取“”号；当目标函数求极小值时均取“”号，称此线性规划问题具有对称形式,max z=c1x1+c2x2

4、+cnxns.t.a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0,min w=b1y1+b2y2+bmyms.t.a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1,y2,ym 0,max Z=CX s.t.AXb X0,min w=bTY s.t.ATYCT Y0,原始问题max z=CXs.t.AXb X 0,对偶问题min w=bTYs.t.ATYCTY 0,max,b,A,C,CT,AT,bT,min,m,n

5、,m,n,maxZ=3x1+2x2 s.t.-x1+2x24 3x1+2x214 x1-x2 3 x1,x20,minw=4y1+14y2+3y3 s.t.-y1+3y2+y33 2y1+2x2-y32 y1,y2,y30,y1,y2,y3,第一种资源,第二种资源,第三种资源,第一种产品,第二种产品,x1,x2,举例,原问题：maxZ=x1+4x2+2x3 s.t.5x1-x2+2x38 x1+3x2-3x35 x1,x2,x30,对偶问题：minw=8y1+5y2 s.t.5y1+y21-y1+3y24 2y1-3y2 2 y1,y20,练习,结论：对偶问题的对偶为原问题,原始问题max Z

6、=CXs.t.AXb X 0,对偶问题min w=YTbs.t.ATYCTY 0,令w=-w,max w=-YTbs.t.-ATY-CTY 0,对偶,min Z=-CXs.t.-AX-bX 0,令Z=-Z,对偶问题的对偶就是原始问题。两个问题中的任一个都可以作为原始问题，另一个就是它的对偶问题。,11,对偶问题的对偶,max z=6x1+9x2s.t.x1+2x22 2x1-3x23 x1+2x2-1 x1,x20,minw=2y1+3y2-y3s.t.y1+2y2+y36 2y1-3y2+2y39 y1,y2,y30,根据定义写出对偶问题,根据定义写出对偶问题,max u=6w1+9w2s.

7、t.w1+2w22 2w1-3w23 w1+2w2-1 w1,w20,minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1+2x3-x44 x2+x3+x4=6 x10,x2,x30,x2+x3+x46x2+x3+x46,-x1=x1,x10;x4-x4”=x4,x4 0,x4”0,minz=-2x1+3x2-5x3+(x4-x4”)s.t.-x1+x2-3x3+(x4-x4”)5 2x1-2x3+(x4-x4”)-4 x2+x3+(x4-x4”)6-x2-x3-(x4-x4”)-6 x1,x2,x3,x4,x4”0,y1,y2,y3,y3”,maxw=5y1-4

8、y2+6(y3-y3”)s.t.-y1+2y2-2 y1+(y3-y3”)3-3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1-y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0,三、非对称形式的原对偶问题,引例,13,maxw=5y1-4y2+6(y3-y3”)s.t.-y1+2y2-2 y1+(y3-y3”)3-3y1-2y2+(y3-y3”)-5 y1+y2+(y3-y3”)1-y1-y2-(y3-y3”)-1 y1,y2,y3,y3”0,设y2=-y2,y3=y3-y3”,则y20,y3无约束此时对偶问题变为,maxw=5y1+4y2+6y3 s.t.y1

9、+2y2 2 y1+y3 3-3y1+2y2+y3-5 y1-y2+y3=1 y10,y20,y3无约束,14,maxw=5y1+4y2+6y3 s.t.y1+2y2 2 y1+y3 3-3y1+2y2+y3-5 y1-y2+y3=1 y10,y20,y3无约束,minz=2x1+3x2-5x3+x4 s.t.x1+x2-3x3+x45 2x1+2x3-x4 4 x2+x3+x4=6 x10,x2,x30,原问题,对偶问题,比较后得出什么结论？,min z=2x1+4x2-x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,ma

10、x w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2-y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4-1 y1 0,y2,y3 0,y4 0,=,Free,=,x10,x20,x3:Free,原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质。原始问题约束条件的性质影响对偶问题变量的性质。,写对偶问题的练习（1）,原始问题,max z=2x1-x2+3x3-2x4s.t.x1+3x2-2x3+x412-2x1+x2-3x48 3x1-4x2+5

11、x3-x4=15 x10,x2:Free,x30,x40,min w=12y1+8y2+15y3s.t.y1 2y2+3y32 3y1+y2 4y3=-1-2y1+5y33 y1 3y2-y3-2 y10,y20,y3:Free,对偶问题,写对偶问题的练习（2）,17,maxZ=x1-2x2+3x3 s.t.2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1,x30,练习,minw=100y1+200y2+150y3 s.t.2y1+3y2+5y31 4y1-2y2+3y3=-2 3y1+6y2+4y33 y10,y20,minZ=2x1+2x2+

12、4x3 s.t.x1+3x2+4x32 2x1+x2+3x33 x1+4x2+3x3=5 x1 0,x20,maxw=2y1+3y2+5y3 s.t.y1+2y2+y32 3y1+y2+4y3 2 4y1+3y2+3y3=4 y10,y20,原问题 Max Z=CX AXb X0其中X(x1,x2xn)T,Max Z=CX+0Xs AX+IXs=b X,Xs0其中Xs(xn+1,xn+2xn+m)TI 为mm的单位矩阵,2.2 对偶问题的基本性质,一、单纯性法计算的矩阵描述,其初始单纯性表及经过若干次迭代后的单纯性表如下：,20,(1)初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；(

13、2)初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；(3)约束矩阵（A，I）（B，N，I），迭代后为（B-1B，B-1N，B-1I）（I，B-1N，B-1)；(4)初始单纯形表中xj的系数向量为Pj，迭代后为Pj，且Pj=B-1Pj。,21,(5),当B为最优基，XB为最优解时，则有：,CN-CBB-1N0,-CBB-10,CB-CBI=0,CCBB-1 A0-CBB-10,令YTCBB-1，称 CBB-1为单纯形乘子,则：CYT A0-YT0,ATYCT Y 0,Y为对偶问题的可行解且WYTb=CBB-1b=Z,结论：当原问题为最优解时，Y为对偶问题为可行解且具有相同的目标函数值

14、。,maxZ=4.5x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5x25 y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0,minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40,例题,24,(x3,x4)=(0,0),(y3,y4)=(0,0),-y1,-y2,-y4,-y3,x1,x2,x4,x3,25,maxZ=4.5

15、x1+5x2 s.t.3x1+2x224 4x1+5x240 x1,x20,minw=24y1+40y2 s.t.3y1+4y24.5 2y1+5x25 y1,y20,y1,y2,x1,x2,maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,0,minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40,例题,原始问题max Z=CXs.t.AXb X 0,对偶问题min W=YTbs.t.ATYCTY 0,二、对偶问题的基本性质,二、对偶问题的基本性质,1.弱对偶性

16、,原问题任一可行解的目标函数是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数是其原问题目标函数的上界。如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。（对偶问题无可行解时，其原问题无界解或无可行解。若原问题有可行解而其对偶问题无可行解时，原问题目标函数无界。若对偶问题有可行解而其原问题无可行解时，对偶问题目标函数无界。,推论：,2.最优性,若原问题和对偶问题均具有可行解，则二者均具有最优解，且它们的最优解的目标值相等。,3.强对偶性（对偶性定理）,证：由于二者均有可行解，所以原问题的目标函数值具有上界，对偶问题的目标函

17、数值具有下界，因此二者均具有最优解。,当原问题有最优解时,对偶问题的解Y=CBB-1为可行解,且 Z=CBB-1b=W,由最优性知,二者的解均为最优解。,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非0，则该约束条件取严格等式；反之如果约束条件取严格不等式，则 对应的对偶变量值为0。,若yi 0,则aijxj，=bi，即xsi=0若aijxj，bi，即xsi0 则 yi 0,同理若xj 0,则aijyi，=cj若aijyi，cj，则 xj 0.,4.互补松弛定理,maxZ=4.5x1+5x2 s.t.3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4

18、,0,minw=24y1+40y2 s.t.3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y40,3x1+2x2=24，X3=0 4x1+5x2=40，X4=0,3y1+4y2=4.5，y3=0,2y1+5y2=5，y4=0,最优解X=(40/7，24/7，0，0)T，Y=(14/5，6/7，0，0)T,利用互补松弛关系求解线性规划,min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0,max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20,原始问题,对偶问题,最优解为(y1,y2)=

19、(6,0)max y=6,先用图解法求解对偶问题。,34,min z=6x1+8x2+3x3s.t.x1+x2 1 x1+2x2+x3-1 x1,x2,x3 0,max w=y1-y2s.t.y1+y2 6 y1+2y2 8 y2 3 y1,y20,max w=y1-y2s.t.y1+y2+y3=6 y1+2y2+y4=8 y2+y5=3 y1,y2,y3,y4,y50,(y1,y2)=(6,0),(y1,y2,y3,y4,y5)=(6,0,0,2,3),min z=6x1+8x2+3x3s.t.x1+x2-x4=1 x1+2x2+x3-x5=-1 x1,x2,x3,x4,x50,(x1,x2

20、,x3|x4,x5)(y1,y2|y3,y4,y5),x2=x3=x4=0,x1=1,x5=2,(x1,x2,x3,x4,x5)=(1,0,0,0,2),2.3 资源的影子价格(Shadow Price),yi=w/bi=最大利润的增量/第i种资源的增量=第i种资源的边际利润,w=b1y1+b2y2+biyi+bmym,w+w=b1y1+b2y2+(bi+bi)yi+bmym,w=biyi,Yi代表在资源最有利条件下对单位第i种资源的估价，称为影子价格。,36,Z*=8.5X=(7/2,3/2),Z*=8.75X=(15/4,5/4),Z=9X=(3,3),maxZ=2x1+x2 s.t.2x

21、215 6x1+2x224 x1+x25 x1,x20,思考:如果第一种资源增加1，也就是把15变为16,目标函数值将怎么变化?为什么?,最优解X=(7/2,3/2)T对偶问题最优解y=(0，1/4，1/2)T,由对偶问题的互补松弛性质当 时，当 时，.表明生产过程中某资源bi未得到充分利用时，该资源的影子价格为0；当该资源的影子价格不为0时，表明该资源在生产过程中以耗费完毕。,影子价格是一种机会成本，在完全市场经济条件下，当市场价格高于影子价格时，则会卖出该资源；当市场价格低于影子价格时，则会买入该资源。即影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种资源越充裕。,资源的影子

22、价格有赖于资源的利用情况，因企业的生产任务、产品结构等情况而变化。,maxz=4x1+10 x2 s.t.3x1+6x25 x1+3x22 2x1+5x24 x1,x20,已知原问题为：,则对偶问题为：,minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30,maxz=4x1+10 x2 s.t.3x1+6x2+x3=5 x1+3x2+x4=2 2x1+5x2+x5=4 xj0(j=1,2,5),minw=5y1+2y2+4y3 s.t.3y1+y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi0(i=1,2,5),2.4

23、 对偶单纯形法,39,初始单纯形表为：,此时对偶问题的基解为Y(0，0，0，4，10)T,不是对偶问题的可行解,40,初始单纯形表为：,此时对偶问题的基解为Y(0，0，0，4，10)T,不是对偶问题的可行解,41,迭代得：,此时对偶问题的基解为Y(0，10/3，0，-2/3，0)T,不是对偶问题的可行解,42,迭代得：,此时对偶问题的基解为Y(0，10/3，0，-2/3，0)T,不是对偶问题的可行解,43,迭代得：,此时对偶问题的基解为Y(2/3，2，0，0，0)T,是对偶问题的可行解,44,单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从

24、对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原问题可行的，又是对偶可行的，这个解就分别是原问题和对偶问题的最优解。,根据对偶问题的对称性，若保持对偶问题的解是可行的，即检验数0，而原问题在非可行解的基础上，不断改进其可行性，逐步达到基可行解，此时就达到原问题和对偶问题的最优解。,设有问题 max Z=CX，AX b，X 0 又设B是其一个基，当非基变量都为0时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对偶单纯形法来进行求解。,对偶单纯形法适用的情况：,46,step1.确定初始解 求初时基可行解

25、,列出初始单纯性表(一般取松弛变量为基变量)；若所有检验数 0，且所有的基变量值均0，则此解为线性规划问题的最优解；若存在基变量的值0，则问题还没有达到最优解，则进行如下计算；step 2.改进 选择换出变量：min B-1bi|B-1 bi0,假设选取xr为换出变量；选择换入变量：min(cj-zj)/arj|arj0,假设xl为换入变量；step 4.迭代 使得alk1，其余aik为0。,对偶单纯形法的计算步骤：,Minw=5y1+2y2+4y3 s.t.3y1+y2+2y34 6y1+3y2+5y310 y1,y2,y30,例1,Maxw=-5y1-2y2-4y3 s.t.-3y1-y2

26、-2y3-4-6y1-3y2-5y3-10 y1,y2,y30,Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3+y4=4-6y1-3y2-5y3+y5=10 yi0(i=1,2,5),48,Maxw=-5y1-2y2-4y3 s.t.-3y1-y2-2y3+y4=4-6y1-3y2-5y3+y5=10 yi0(i=1,2,5),49,50,51,52,53,54,55,56,57,此时对偶问题和原问题都达到可行，所以均达到了最优解Y（2/3.2,0,0,0)，W=-22/3，W=22/3,Minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+3x34

27、 x1,x2,x30,例2:用对偶单纯形法求对偶问题的最优解,Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3-3-2x1+x2-3x3-4 x1,x2,x30,Maxw=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=4-2x1+x2-3x3+x5=10 xi0(i=1,2,5),59,此时对偶问题和原问题都达到可行，所以均达到了最优解 原问题最优解为:X=(11/5,2/5,0,0,0)T,W=-28/5,W=28/5对偶问题最优解为：Y=(8/5,1/5,0,0,9/5)T,(1)初始解可以是非可行解，当检验数都时，就可以进行基的变换，这时不需要加入人工变量

28、，因此可以直接计算。(2)当变量多于约束条件，对这样的LP问题，用对偶单纯形法计算可以减少计算工作量。因此，对变量较少，而约束条件很多的LP问题，可以先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。,对偶单纯形法的优点,Maxz=3x1-4x2 s.t.x1+2x22 3x1+x24 x1-x21 x1+x23 x1,x20,Maxz=3x1-4x2 s.t.-x1-2x2-2-3x1-x2-4 x1-x21 x1+x23 x1,x20,Maxz=3x1-4x2 s.t.-x1-2x2+x3=-2-3x1-x2+x4=-4 x

29、1-x2+x5=1 x1+x2+x6=3 xj0,例3,62,可以看出，这时候原问题和对偶问题都不可行,列出初始单纯形表：,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,此时对偶问题和原问题都达到可行，所以均达到了最优解 X（4/3.1/3,0,1/3,0,4/3),Z=8/3,第五节 灵敏度分析,灵敏度分析的概念 对系统或事物（线性规划问题）因周围条件的变化（如cj,bi,aij 的变化）显示出来的敏感程度的分析,当cj、bi、ai j变化时会引起哪些数字的变化？,(1)参数A，b，C在什么范围内变动，对当前最优方案无影响？

30、,(2)参数A，b，C中的一个变动，对当前最优方案影响？,(3)如果最优方案改变，如何用简便方法求新方案？,灵敏度分析所解决的问题,例：佳美公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调整工序时间及每天可用于这两种家电的能力、各出售一件时的获利情况，如下表。问该公司应制造两种家电各生产多少,可获最大利润?,一、分析 cj 的变化,c j 的变化仅仅影响检验数,5x2 15 6x1+2x2 24 x1+x2 5 x1，x2 0,max Z=2x1+x2,解:设两种家电产量分别为变量x1，x2,s.t.,最终单纯形表如下：,87,（1）若家电的利润降至1.5元/件，而家

31、电的利润增至2元/件时，美佳公司最优生产计划有何变化？,88,(2)若家电的利润不变，则家电的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,设家电的利润为(1+)元，最终单纯形变为：,-1/4+1/4 0,-1/2-3/2 0,-1/3 1,2/3 c22,二、分析 bi的变化bi 的变化仅仅影响b列 的变化,b=B-1b,XB=B-1b，b=b+b XB，=B-1b=B-1(b+b)=B-1b+B-1 b,（3）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化。,1 5/4 15/20 1/4-1/20-1/4 3/2,B-1b=,08

32、0,=,102-2,B-1,080,102-2,（3）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化。,利用对偶单纯形法迭代后得：,最优计划为只生产5件家电。,（4）若设备A和B每天能力不变，而调试工序在什么范围内变化，问题的最优基不变。,1 14 b36,增加一个变量xj 相当于增加一种新产品,三、增加一个变量x j 的分析,（5）公司计划推出新产品，生产一件所需设备A,B及调试工序的时间分别为3小时、4小时、2小时，预期盈利3元/件，试分析该种产品是否值得投产，如投产，对该公司的最优生产计划有何影响。,1 5/4 15/20 1/4-1/20-1

33、/4 3/2,P,6=B-1P6=,342,-702,=,6=C6-CBB-1 P6=C6-Y P6 3=3-(0,1/4,1/2)4=1 2,设该公司生产x6件家电,有,四、分析 aij的变化,若aij对应的变量xj为非基变量，则Pj和j变化，参照增加一个变量的情况。,若aij对应的变量xj为基变量，即B-1变化，则常数列B-1b和检验数j变化。,（6）在佳美公司例子中，若家电每件需设备A，B和调试工时变为8h、4h、1h，该产品利润为3元/件，试重新确定该公司最优生产计划。,2=C2-CBB-1 P2=C2-Y P2 8=3-(0,1/4,1/2)4=3/2 1,102,用单纯形法将x2替

34、换基变量中的x 2并在下一张表中不再保留x2,103,用原问题与对偶问题均为非可行解，先设法使原问题可行。,第一行约束可写为：x3+4x4-24x5=-9,两端乘(-1)并加人工变量得：-x3-4x4+24x5+x6=9,（7）若美佳公司家电产品还需一道环境试验工序，家电每件需环境试验3小时，家电每件需环境试验2小时，环境试验工序每天的生产能力为12小时，试重新确定该公司的最优生产计划。,maxZ=2X1+X2,五、增加一个约束条件的分析,设备A设备B调试工序,再利用对偶单纯形法求解即可。,108,灵敏度分析总结,目标函数中价值系数发生变化,增加一个变量,aij发生变化,右端常数项发生改变,增

35、加一个约束条件,用单纯形法求解,用对偶单纯形法求解,若目标函数或约束右端向量是某个参数的线性函数称为参数线性规划,第六节 参数规划,分两种情况：(1)目标函数是参数的线性函数，即C+C*(2)约束右端向量是参数的线性函数，即b+b*,（1）令=0，求解得最终单纯形表；（2）将C*或b*反映到最终单纯形表中；（3）确定在最优基不变情况下允许取值的范 围；当取值超出该范围时，用单纯形法或对偶单纯形法求新的最优解；（4）,参数规划 的分析步骤,5x2 15 6x1+2x2 24 x1+x2 5 x1，x2 0,max Z()=(2+)x1+(1+2)x2,s.t.,当=0时的最终单纯形表如下：,例

36、求解下列参数线性规划问题,一、目标函数是参数的线性函数,112,将反映到最终单纯形表中得,113,114,当-1/5 1时，最优解不变，最优值为Z=17/2+13/2,115,当 1时，x4的检验数0，用单纯形法迭代得：,116,当 1时，最优解如表，最优值为 Z=7+8,117,当-1/5时，x5的检验数0，用单纯形法迭代得：,118,-2-1/5,-2,5x2 15 6x1+2x2 24+x1+x2 5 x1，x2 0,max Z()=2 x1+x2,s.t.,当=0时的最终单纯形表如下：,例 求解下列参数线性规划问题,二、约束右端向量是参数的线性函数,将反映到最终单纯形表中,1 5/4

37、15/20 1/4-1/20-1/4 3/2,B-1b=,00,5/4 1/4-1/4,=,b=,+5/4+1/4-1/4,+5/4+1/4-1/4,当-66时，最优解不变，最优值为 Z=17/2+1/4,当6时，利用对偶单纯形法求解。,当-6时，利用对偶单纯形法求解。,（1）对偶问题的提出（2）根据原问题写对偶问题（3）对偶问题的基本性质（4）对偶单纯形法（5）灵敏度分析（6）参数规划,第二章 总 结,123,习题,1.研究线性规划问题,Maxz=4x1+4x2 s.t.2x1+7x221 7x1+2x249 xj0(j=1,2),问：1）用图解法求该问题的最优解2）使（写x1*,x2*）保

38、持最优情况下目标函数系数的比值范围是多少？,124,2.研究方程组,x1+2x2-3x3+5x4+x5=45x1-2x2-6x4+x6=82x1+3x2-2x3+3x4+x7=3-x1+x3+2x4+x8=0 xj0(j=1,2,8),问：1）设(x5,x6,x7,x8)T为初始基变量，如果把x1换入为基变量，则应该把初始基变量中的哪个变量换出？2）如果将x1换入，x5换出，将得到什么解？3）如果将x1换入，x8换出，将得到什么解？,125,3.用图解法求下列线性规划问题,Maxz=-x1+2x2 s.t.x1+x22-x1+x21 x23 xj0(j=1,2),Maxz=-x1+3x2 s.

39、t.X1-2x24-x1+x23 xj0(j=1,2),126,4.研究以下线性规划问题,已知线性规划目标函数为maxz=5x1+3x2,约束条件均为“，所有变量均0.,此时Z10，求a-g?,127,5.求线性规划问题已知该问题约束条件均为“，所有变量0.x3,x4,x5为松弛变量，根据以下单纯形表求线性规划问题,128,6.研究线性规划问题,Maxz=5x1+2x2+3x3 s.t.x1+5x2+2x3b1 x1-5x2-6x3b2 xj0(j=1,2,3),问：1）用两种方法求b1,b22）求a-e3）求对偶问题最优解,129,在第k个约束条件两边同乘以，原问题和对偶问题的解有何变化？,

40、7.线性规划问题max z=CXs.t.AXb X 0,130,8.研究线性规划问题,问：1）写原问题2）写出对偶问题3）c2在什么范围内变化最优解不变4）增加一个约束条件 x2+x32,最优解是否发生变化，如果有求新解5）增加一个变量x6,P6=(1,2)T,c6=4,最优解是否发生变化，如果有求新解,131,9.线性规划问题为Maxz=6x1+14x2+13x3 s.t.1/2x1+2x2+x324 x1+2x2+4x360 xj0(j=1,2,3)计算得最优解,当约束条件1变为x1+4x2+2x368最优解有何变化？,132,10.线性规划问题为Maxz=5x1+3x2+6x3 s.t.

41、x1+2x2+x318 2x1+x2+3x316 x1+x2+x310 xj0(j=1,2),Maxz=5x1+3x2+6x3-6x3”s.t.x1+2x2+x3-x3”+x4=18 2x1+x2+3x3-3x3”=16 x1+x2+x-x3”=10 xj0(j=1,2,3),最有解为：,求对偶问题最有解?,133,11.已知线性规划问题max Z=3x1+2x2-x1+2x24 3x1+2x214 x1-x23 x1,x201）写出它的对偶问题2）应用对偶理论证明原问题和对偶问题都存在最优解,134,12.已知线性规划问题min Z=2x1-x2+2x3-x1+x2+x3=4-x1+x2-k

42、x36 x10,x20,x3 无约束其最优解为x1=-5,x2=0,x3=-11）求k的值2）写出并求出其对偶问题的最优解,135,13.已知线性规划问题min Z=8x1+6x2+3x3+6x4 x1+2x2+x43 3x1+x2+x3+x46 x3+x42 x1+x3 2 x1,x2 x3,x4 01）写出其对偶问题2）已知原问题最优解为X*（1，1，2，0），试根据对偶理论，直接求出对偶问题最优解。,136,14.某农场有100土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日，春夏季4000人日，如劳动力本身用不了时可外出干活，春夏季收入为2.1元人日,秋冬季收入为1.8元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入为400元、头奶牛。养鸡时不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收入为2元/只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收入情况如表所示。试决定该农场的经营方案，使年净收入为最大。,137,