最优化方法习题答案

1、AAV习题一1.1利用图解法求下列线性规划问题：maxz=X+x23X+x22s.tJxj+2x20解：根据条件，可行域为下而图形中的阴影部分,，有图形可知，原问题在A丿最优值z=5(2)minz=-6x22X+x21-X+x20解：图中阴影部分表示可行域，由图可知原问题在点A处取得最优值，最优値-x,+x2-4xpx20解：如图所示，可行域为图中阴影部分，易得原线性规划问题(4)minz=2x,-5x2X,+2x26s.tJX)+x20解：由图可知该线性规划可行域为空，则原问题无可行解。3434X+2x2+3X3+4X4=7s.t.s2x,+xs.t.s2x,+x2+x3+2x4=33434

2、34342)解:易知X的系数列向gP1=，X2的系数列向量P2=,X3的系数列向X4的系数列向Sp4=xpx2,x3,x40(2丿X+2x?=7-3x3-4x4因为P，P2因为P，P2线性无关，故有2x,+x2=3-x3-2x41Xi=一一TOC o 1-5 h z3i11,所以得到一个基解xo)=(-,-,O,O)是非基可行解;1133x?23因为P】，P3线性无关，可得基解X=(-,0,-,0),Z2=；555因为Pl，P4线性无关，可得基解X=(-丄,0,0,-),是非基可行解;36因为p2,p3线性无关，可得基解x=(0,2,1,0),z4=-l；因为p2,p4线性相关，x2?x4不能

3、构成基变塑；因为P3，P4线性无关，可得基解X=(0,0,1,1),z6=-3；所以x,x,x是原问题的基可行解，x是最优解，最优值是z=-3。maxz=Xj+x2-2x3+x4-x5X+X2+X3+X4=1s.tJ-Xj+2x?+x=4因为P2线性无关，故有，令非基变量为X3=X4=X+2x=42X】=一3nc,所以得到一个基解x(1)=(-/,0,0,0),是非基可行解；533x?=3因为P】，P3线性无关，可得基解x=(-4,0,5,0,0),是非基可行解；因为pP4线性无关，可得基解x=(-4,0,0,5,0),是非基可行解；因为P】，P5线性无关，可得基解x=(1,0,0,0,5),

4、z4=-4；因为p2,p3线性相关，得基解x(5)=(0,2-1.0,0),是非基可行解；因为p2,p4线性无关，可得基解x=(0,2,0-1,0),是非基可行解；因为p2,p5线性无关，可得基解x二(0,1,0,0,2),z7=-l；因为p3,p4线性相关，x3,x4不能构成基变量；因为p3,p5线性无关，可得基解x=(0,0,1,0,4),z9=-6；因为P4，p_5线性无关，可得基解x(1(,)=(0,0,04,4)，z10=-3；所以原线性规划的基可行解是x,x(Hx,x),最优解是x，最优值是z1.3用单纯形法求解下列线性规划问题；(1)maxz=2X+3x2x,+3x22X+3x2

5、+x3=5s.tJX)+x2-x4+x5=2,其中M无限大,Xj0,i=l,2.5构造初始单纯形表并计算如下:XX2X3X4X52+M3+M0-M0X3131005X5110112以X?作为换入基，X?作为换成基，计算得XX2X3X4X51+-M30亠M3-M0X2I31丄30053X5230_丄3-11丄3以X为换入基，x5作为换出基有xiX2X3X4X500_232_9_m2-5011111.X1X2X3X4X50320-3-M-1X40211-13X131005根据单纯形表可知，原问题的最优解为X*=(5,0,0,3),最优值为=10(2)maxz=x1+x2-2x33Xj+x2-x37

6、xpx2,x30解：引入松弛变量X,剩余变量X5和人工变fix6,把原问题规范化为maxz=X+X?2x3一Mx63X+x2-x3+x4=5X-4x2X-4x2+x3-x5+x6=7Xj0,i=1,2.6X1X2X3X4X5X61+M1-4M2+M0-M0V3111000213M4M351-M3-M33X113丄3130X6013T43131以X3为换入变量，X6为换出变量，得X1X2x?X4X5X6019彳M01554M41244v1501-1X1643Y0131_133X34444所以原问题最优解为x=(3A4),最优值为z=-5ominz=2x1+3x2+x3X+4x2+2X38s.tx

7、3X+2x26xpx2,x30解：引入剩余变量X4,X5和人工变量x6,x7，利用两阶段法得到辅助线性规划maxw=-x6-x7XX2X3X4X5X6X7Z-230000W4621100X61421010X73200-101以X?为换入变量，X6为换出变量，得X】X2X3X4X5X6X71Z_540丄2_340340W5201丄21320X2丄41丄2140丄40X75201丄21丄1以X为换入变量，x7为换出变量，得X1X2X3X4X5Z00012丄2X2010.6-0.30.11.85x,+3x2+x39-5xj+6x2+15x35xjOJ=1,2,3解：引入松弛变fix4x5,剩余变fi

8、x6,人工变量X7,将原问题化为规范式maxz=10Xj+15x2+12x3-Mx75X+3x2+x3+x4=9一5X+6x2+15x3+X5=152X+x2+x3-x6+x7=5xj0,j=l,2,.,7构造初始单纯形表并计算得以X为换入变量，X4为换出变量，得XX2X3X4X5X6Z10+2M15+M12+M00-MX4531100X55615010X7211001Z09M510+3M522M50MX10.60.20.200X50916110X70-0.20.6-0.40-1进一步计算知道，X7HO,所以原问题没有可行解。1.4设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变量，

9、哲卫2，”5工2为何值时，表中的解：（1）为唯一最优解，（2）为多重解，（3（4）为退化解。X1X2X3X4X5X650C2-900X2ai1a2100X5105010X6402101解：当60心20,0,=0,c20或C0,c2=0,为多重解;时受到进货量的限制，不考虑货物存放在仓库的耗损与保管费用。月份买进单价/（元/件）售出单价/（元/件）41718516.51861719解：设Xi表示每个月进货量，表示相应月份售货量，其中i=1,2,3,贝I有粪maxz=18yj+18y2+19y3-17X,-16.5x2-17x3Xj600-200X,-y,+x2600-200 x1-y1+x2-y

10、2+x3600-200s.t/-X,+Yj200-x1+y1-x2+y2200-X+y,-x2+y2-x3+y30,i=1,2,3经计算，当X1=400,y,=600,x2=500,y2=600,x3=600,y3=600时,即400件，售货600件，五月份进货500件，售货600件，六月份进货600件售1最大利润为6100元。1.6设市场上可买到n种不同的食品，第j种食品的单位售价为耳，每种食品含营养成分，第j种食品每一个单位含第i种营养成分为,每人每天对第i种空要量不少于S,试确定在保持营养成分要求条件下的最经济食谱。s.t/j=ix.0,j=l,2,nbJ1.7A,B两种产品都需要经过前

11、、后两道工序加工，每一个单位产品A需要和后道工序2h,每一个位产品B需要前道工序2h和后道工序3h.可利用的前泄后道工序有17ho没加工一个单位产品B的同时，会产生2个单位的副产晶C,任何费用，产晶C一部分可出售盈利，其余的只能加以销毁。出售单位产品/分别为3元，7元，2元，每单位产品C的销毁费为1元。预测表明，产品C售13个单位。试建立总利润最大的生产计划数学模型。解：设x1?x2分别为产品A,B的产量，X3为副产品C的销售量，X4为副产品于是有x3+x4=2x2,z为总利润，则数学模型如下：maxz=3x+7x2+2x3-x4x,+2x2112Xj+3x217s.t.-2x2+x3+x4=

12、0 x30习题二2.1写出下列线性规划问题的对偶问题:minz=10 x1-5x2+x3X+2x2+4x310X+6x2-5x32s.t.-1X20,x2自由变量解：原问题的对偶问题为：maxw=10丫+2y2+y3+7y4yi+y2102y+6y2-y3+y4=-5S.t/4力一521Yi0,y2,y3,y40maxz=x,-2x2+3x3-4x4X+5x2-x3+2x4=62X+x2+x3-5x45x19x2,x30,x4自由变量解：原问题的对偶问题是minw=6y】+13y2+5y3yi+2y2+4y3l5y】+y2一2y3-22X+x2-2x3=3X-2x2+3x32minz=x,-2

13、x2-2x3s.t.1x?O,x3p由变量证明：原问题的对偶问题为maxw=3y,+2y22yj+y2l力一2丫23s.txx2+2X35XpX2,x30写出该线性规划问题的对偶问题；已知对偶为题的最优解为(2,6),试用互补松弛定理求其原问题的最优斛解：(1)原问题的对偶问题为：maxw=3y,+5y2y】4y26Set/10_(x15x2,x3)01-(3,5)_32_丿(2,6)=0X+3x3=3x2+2x3=5又因为yb=cx有(xp(xpx2,x3)=(3,5)18丿即：2Xj+3x2+9x3=18Xj=0 x3=1联立联立解得2x2=3即原问题的最优解为(0,3,1)2.4对线性规

14、划问题maxz=2x,+x2+5x3+6x42X+X3+X40写出该线性规划问题的对偶问题；已知原问题的最优解为(0,0,4,4)，试用互补松弛定理求对偶问题的最优解：(1)原问题的对偶问题为：minz=8y+12y2(2)利用互补松弛定理有(yA-c)x=O0201V呵231201V呵231有1-(2,1,5,6)=0力+2=5有卜+22二6即門72=1所以对偶问题的最优解为(4)2.5用对偶单纯形法求解下列线性规划问题：(1)minz=2x)+4x2+5x3X+x2-3x31s.tJ-x,+x26xpx2,x30解：利用对偶单纯形，添加松弛变量X4,x5,原问题化为规范式Imaxz=-2X

15、|-4x2-5xs-Xj-X2+3X3+X4=-ls.t.0X1X2X3X4X52-4-500X4113101X510016由表可知。原问题的最优解为(0,6,0)(2)maxz=-x,-x2-2x3X)-5x2+3x310Set/X-2x2+3x30解：利用对偶单纯形，添加松弛变量X4,x5,x6,原问题化为规范式:maxz=-X-x2-2x3Xj-5x2+3X3+X4=4-2Xj-x9-6X3+X5=-10S.tJ,则有单纯形表X-2x2+3x3+x6=7x.0,i=l,2,3,4,5,6X3-1/3-2/30X40X6X3-1/3-2/30X40X6-1/30X1X2X3X4X5X612

16、000X41-53100X5216010X6123001以X3为换入量，换岀得X1X2X3X4X5X6-1/3002/3-3/110X20102/ll-1/110X31/3011/33-5/330X6000-5/113/111由表知原问题无最优解。2.6设有线性规划minz=-2x1+x2+x33Xj+x2+x360Xj-x2+2X310S.t/X,+x2-x30求出最优解，并进行以下分析（1）C2在什么范围内变动而不影响最优解？（2）b?从20变为16,求最优解；（3）X3的系数变为（1,3,-1）,其价值系数从1变为5,试问最优解是否会发占（4）增加约束条件2X14-x2+x531,最优解

17、有何变化？解：引入松弛变量x4,x5,x6,将原问题化为规范行：Imaxz=2X-x2-x33X+X2+X3+X456021000X4311100X512010X6111001列单纯形表有以X为换入变量，X5为换出变量有X1X2X3X4X5X6015020X4045130X112010X602301以X?为换入变量，X&为换出变量有XX2X3X4X5X600-7/20-3/2-1/2X400112X1101/201/21/2X201-3/20-1/21/2所以原问题的最优解为(15,5,0,10,0,0)_173因为X?是基变量，由书中(2.6)式有max(-)=-l,min(-2-,-2-)

18、1-1-2_0)10、所以此时原问题的最优解为(13,3Ql&0,0)(3)0*3=03CpB*3=1(2厂11)(3)0*3=03CpB*3=1(2厂11)11-1-201/21/230-1/21/2-J-1=-20所以原问题的最优解变。(4)添加松弛变量X?,在原最终单纯形表中添加一行一列并计算有X】X2X3X4X5X6X700-7/20-3/2-1/2X400111-20X】101/201/21/20X201-3/20-1/21/20X70010932以X3为换入量，x7为换出量有X】X2X3X4X5X6X7cn/rcn/rp匕具Z4：丄41hhziK11/X30010932以为换入量，

19、X3为换岀量有XX2X3X4X5X6X700-40-9/2013/2X4001/31-701/3X10-2/30201/3X201-4/30101/3X600-1/30-31-2/3得最优解为(41/3,11/3,0,46/3,0,8/3,0),最优值为-71/32.7某厂生产A15A2,A3三种产品，需要BpB2,B3三种设备加工，需要单位莘要的设备台时、设备的现有加工能力及每件产品的预期利润如下表所示台/hA】A2A?设备談B】111100b21045600B3226300单位产品利润1064求获利最大的产品生产计划；每件产品A?的利润增加到多大时，才值得安排生产？如果每件产品A3白a）如

20、合同规定该厂至少生产10件产品A3,试确定最优计划的变化。解：设计划生产产品ApA2,A3各X,X2，X3件，贝I有maxz=lOx,+6x2+4x3X,+x2+x310010 x)+4x?+5X3-600st2Xj+2x2+6X30(1)构造单纯形表如下：X1X2X3X4X5X61064000X4111100X51045010X6226001以X为换入量，为换出量有X1X2X3X4X5X6021010X403/51/21-1/100X12/51/201/10000-8/3-10/3-2/30X2015/65/3-1/60X101/6-2/31/60X6004-201得最优生产计划，即(100

21、/3,200/3,00000)为最优解，获利2200/3元由于X3为非基变量，则只有a0才值得3Ac3-c3,即Ac38/3,即c20/3时A3才值得生产。而当c3解发生变化，根据计算，当c=50/6时，-=5/30时，此时将x为换出变量，得XX2X3X4X5X6000-5/2-2/3-5/12X201025/12-1/6-5/24X1100刀121/6-1/24X3001-1/201/4此时生产最优计划为(175/6,275/6,2500,0)由于召的生产量为基变量，则有呎需，課卜-4,gw-4,5时，原最优生产计划保持不变。得c】w6,15若矩阵110_5/3-1/60_4100,其逆矩阵

22、B-=-2/31/60rr(5)经计算B_p7=0cBB_1p7=(6,10,0)0=6iia7=c7-cBB_1P7=8-6=20，则此时最优解发生变化，且该产品值得生产(6)原最优解不满足新的约束条件，x310,即-x3-10,引入松弛变虽终单纯形表中增加一行或一列有：XX2X3X4X5X600-8/3-10/3-2/300X2015/65/3-1/600X101/6-2/31/600X6004-2010X7000001将X?做为换出变量，x?作为换入变量，利用对偶单纯形有xiX2X3X4X5X6000-10/3-2/301X20105/3-1/605X100-2/31/601maxz=(

23、7+2t)x+(12+t)x2+(10-t)x3X+x2+x320st2x)+2x2+x30,t0解：将上述问题转化为标准型有maxz=(7+2t)x+(12+t)x2+(10-t)x3X+x2+x3+x4202x)+2x2+x3+x50,t0令=（）,用单纯法求解如下:Cj7121()00CBXbbX】X2X3X4X50X420111100X53022101z071210000X45001/21-1/212X215111/201/2z1805040610X3100012112X21011011-z22050082、i“砧才斗/iz占彳立r;E盜ii貝轴iVi加1“土Hiz-220IT-50|

24、03t8T开始增大，当t8/3时，首先出现60,故当0t-时，得最优解(0,3目标函数的最优值为maxz=220(0t-)ot=为第一临界点33当10,故当*4时，得最们目标函数的最优值为180+151,匸5为第二临界点。当t5时，60,X】作为换入变量，由8规则确定X2为换出变星，用单乡代：Cj7+2t12+t10-t00CbXbbX】X2X3X4X50X45001/21-1/27+2tX115111/201/2-z-105-30t05-t13/2-2t07/2-t由表知当t继续增大时，所有检验数都非正，所以当t5时，得最优解(15,目标函数的最优值为105+301(1)用单纯形方法求出最优

25、解;厂-2、厂-2、改变为+t(4)(2)将约束右端b=匕丿(t0),对t的所有值求出问题(解:(1)引入松弛变量x3,x4,把原问题化为标准形maxz=3x,+x2X)+x2+x3=4s.t?2Xj-x2+x4=4,建立初始单纯形表xpx2,x3,x40X1X2X3X43100X31110zX42101z以X为换入变量，X4为换出变量，有XX2X3X405/20-3/2X3011-1/2/-X1-1/201/2A以X?为换入变量，X3为换岀变量有XX2X3X400-5/3-2/3X2012/3-1/3LXX2X3X400-5/3-2/3X2012/3-1/3X101/31/3A由表可知当0t

26、-，问题的最优解为(8/3-t/3,4/3-5t/3)当t+时，利用对偶单纯形有XlX2X3X4023/2/3X403214X1110z由表可知当时，问题的最优解为(42t,0),当02时，原问题无解。习题三3.1用割平而法求解下列整数线性规划。(1)minz=2xj-x2x-3%21s.txX)+x24丹兀2no且为整数解：增加松弛变Sx39x4f将其化为标准形为西3兀2+兀3=1minw=-2x+x2s.t.x,+x2+x4=4先不考虑整数条件，则对应纟西，兀2,兀3,兀410且为整数形表如下兀2兀3兀4w2100兀31-310兀41101以兀4为换出基，兀2为换入基，进步得单纯形表兀兀2

27、x3兀4W3001x34013X21101所以，原线性规划问题的最优解为X瘁=(0,4),是整数解所以也是原整数规划f(2)maxz=-12Xj+9x22X+x2+x310-X,+5x2+x46maxz=-12x+9x2s.tx3x1-2x2+x5oja为整数先不考虑整数条件，则对应线性规划单纯形表如下兀2x3兀4X5Z-129000兀321100兀4-15010X532001以七作为换入变量，兀4为换出变屋得兀卷兀3兀4X5Z51/500-9/50屯11/501-1/50兀2-1/5101/50X513/5002/51所以线性规划的最优解为(0,6/5,44/5,0,27/5)分量44/5取

28、整后分数最大，考虑单纯形表中该分量所对应的行约束-X.+X3-丄X4=414平而4-1y.仃询邕才勿由.兀311/501-1/50044/5兀2-1/5101/5006/5X513/5002/51127/5X6-1/500-4/501-4/5利用对偶单纯形法有兀2x3兀4X5X6z-203/200000-9/4兀343/200100-1/49兀2-4/2510001/41X55/200011/25X6-1/40010-5/41由表可知最优解为(0,1)最优值为9.3.2用分支定界法求解下列整数线性规划问题:(1)maxz=X+5x23X+4x2113X+4x2117X+6x242s.tJ(1)

29、x22x15x2no且为整数和maxz=X+5x23X+4x2117Xj+6x23x15x2o_a为整数先不考虑整数的约束条件，求解(1)所对应的线性规划子问题得到最优解X二值为Zj=11,(2)所对应的线性规划子问题没可行解。故原整数规划的最优解广最优值为Z=11。(2)minz=3x2x2-X+2x27s.t.9X1?x20且为整数3.3求解下列01规划问题：(1)maxz=-2xj+x2+3x3-5x4点条件满足条件？是W）否（X）(0,0,0,0)0X(0,0,0,1)5X(0,0,1,0)312-17(0,0,1,1)2X(0,1,0,0)1X(0,1,0,1)4X(0,1,1,0)

30、42207(0,1,1,1)1X(1,0,0,0)2X(1,0,0,1)7X(1,0,1,0)1X(1,0,1,1)-4X(1,1,0,0)X(1,1,0,1)6X(1,1,1,0)2X(1,1,1,1)3X由表可知，原问题的最优解为（0丄0）,最大值是4.(2)minz=x1-x2+x3*-x,+x2-x33S.t/X-7X2+x30%)=0或1，j=1,2,3解：显然（1Q1）是原问题的一个解，增加约束条件x1-x2+x3lO,建立下表:点条件满足条件？是（7）否（）厶心二公占厶心二公占E匸丰宀T击亠T冲z/znr心4.4求解下列最小值的指派问产地销地Bib2b3b4产量A】59315a2

31、13418a382617销售1812164.1已知某运输问题的产销需求和单位运价如下表，求解运输最少的方案和总运价。51(C=11(2)3336832268111026384152272533445921203047562522314553204.2某百货公司去外地采购A,B,C,D4种规格的服装，数量如下A为1500套,B为2000套，C为3000套，D为3500套。有三个城市可供应上述规格服装，各城市供应数量如下1为2500套，II为2500套，III为500套。由于这些城市的服装质量、运价和销售情况不同预计售出的利润也不同如下表所示，请帮该公司确定一个预期盈利最大的采购方案。4.5求解下

32、列最大值的指派问是(1)10961715141020181313191681226城市规格ABCDI10567n8276m934894658(2)c=7109615798610_5121684.3甲乙、丙三个城市每年分别需要煤炭320万吨，250万吨，350万吨，由A,B两处煤矿负责供应，已知煤炭年供应量A为400万吨，B为450万吨，由煤矿至各城市的单ft.11ft.11rrnrui_L-r*l2.1C一口AliLfl.P、人nirl-/、P亢rH/口11丄lf习题五ft.11ft.11rrnrui_L-r*l2.1C一口AliLfl.P、人nirl-/、P亢rH/口11丄lf5.1利用最优

33、性条件求解minf(x)=+%2-x2xi解：=Xj21,2x29由V/(x)=0得驻点TOC o 1-5 h zdxdx2兀=(1,0),兀二(1,2=(1,0),兀=(1,2),又巧2(兀)=:1生-220A0si.6-6=0.0468750.05,所以此时x*=2.9765625oNewton切线法：取初值帀=2.25,计算过程如下：kXk/(a)J02.250000014.81250001.5112.1250000292.546875060/27.309413669.569617731.：35.125568614.30753691&44.36263881.746185714.54.23

34、945830.045520313.，64.23607050.000034413.，此时/(x5)=0.0455203（/+）/*=60,所以取n=10,计算结果kdk加兀kiXk27(Ai)心2）10.00000003.00000001.14583331.8541667-2.810700612.815601521.14583333.00000001.85416672.2916667-12.815601519.350188131.85416673.00000002.29166672.5625000-19.350188123.259521542.29166673.00000002.56250002

35、.729166723.259521525.549813752.56250003.00000002.72916672.833333325.5498137-26.921296362.72916673.00000002.83333332.895833326.9212963-27.718578272.83333333.00000002.89583332.937500027.7185782-28.238525482.89583333.00000002.93750002.958333328.2385254-28.494864092.93750003.00000002.95833332.9791667-28

36、.4948640-28.7487070102.95833333.00000002.97916672.9791667-28.7487070-28.7487070此时兀*=(dio+bio)/2=2.9791667。(2)为了计算简单，取精度=0.05,/(x)=3x2-4x+l,fx)=6x-4二分法：取兀o=O.5（这是经过反复计算确定的，计算中发现初值的选择对方响很大。）kXk畑/(Xk)00.00000003.00000000.50000001.0000000-0.250000010.00000000.50000000.25000001.00000000.187500002.2500000

37、7.18750009.511.49342111.71723514.921.14724100.35952182.831.02255630.04663892.141.00071480.00143112.C51.00000080.00000152.0由上表可知，当取精度8=0.05时，x*=l.0225563,当取精度=0.01时，x*=试探法：kXk皿）01.5000000-4.6250000(11.6000000-4.4240000-21.4500000-4.7063750-31.3500000-4.8346250-41.15000004.9741250-50.7500000-4.9531250

38、61.3500000-4.8346250-71.0500000-4.9973750-80.8500000-4.980875091.15000004.9741250-101.0000000-5.0000000-110.9000000-4.9910000(121.0500000-4.9973750-130.9750000-4.9993906当B12时，abs（h）=0.0250.05,所以此时x*=1.05o黄金分割法：k加XklXk2mi)y（xk2）00.00000003.00000001.14600001.8540000-4.9755719-3.647848110.00000001.8540

39、0000.70822801.1457720-4.9397079-4.975652S20.70822801.85400001.14591291.4163151-4.97560294754526：30.70822801.41631510.97871731.1458258-4.99955674975633Y40.70822801.14582580.87539040.9786635-4.98640734999554350.87539041.14582580.97869671.0425195-4.9995558-4.998115；60.87539041.04251950.93923370.9786762

40、-4.9965318-4.999555(70.93923371.04251950.97868891.0030643-4.9995555-4.999990(80.97868891.04251951.00307221.0181362-4.9999905-4.999665150.70833331.14583330.87500000.9791667-4.9863281-4.999575(60.87500001.14583330.97916671.0416667-4.9995750-4.998191(70.87500001.04166670.93750000.9791667-4.9963379-4.99

41、9575(80.93750001.04166670.97916671.0000000-4.9995750-5.000000(90.97916671.04166671.00000001.0208333-5.0000000-4.999556S100.97916671.02083331.00000001.0000000-5.0000000-5.000000(得到x*=(io+io)/2=1.0000000o5.4用最速下降法求解min/（兀）=（西-2）2+2兀；解：V（x）=（2x1-4,4x2）7,取精度=10,。A1X；-tk(2x；k)一4)、Y(k+1)A2丿卅)_tk(4时)x(w)=x

42、(k)-tkVf(xk),取初值x(0)=(2,2又/(兀(5)=兀丫)一2f(2兀$)-4)2+2讲)一tk(4讲)2；时，/(兀)=0+2(28尸，令/(兀)=一16(2-&。)=0,得巾=1/4。x(1)=(2,0)t,Vf(xo)=(O,O)r,即酚(兀)卜,得到x*=x0)=(2,0)To5.5求f（x）=xf-3xjX2+X2+2Xj-x2在点（1,-3）处的最速下降方向和卜解：Vf(x)=(2Xj3x2+2,-3西+2兀2-l)7，V2/(x)=2-3、曰2,对于最速下降法,其搜索方向Pk=-巧（*），贝眦时p（b_3）r=（一13,10）?对于Newton法,其搜索方向P严一V

43、/（卅）V/*0）,由于/（兀）-0.4-0.6、,-0.6-0.4,419r，得到此时P(1,_3/=(-,y)rfAfAV7-T/.(1)V7-T/.(1)Trr.fAfAV7-T/.(1)V7-T/.(1)Trr.解：(1)V/(x)=(4%j+2x24-1?2xj+2x2-l)7,V2/(x)=,卩2丿,厂？n-i(0.5一0.5)得到E)心1?0)=(o,o)r,W(兀()=(1,-1),A)=4vW0)r1-Wt0)=(-)=/(x(0)+/opo)=min/(x(0)+/oPo)知x(，)+姚=(T,L5(f,带入/(/)=2t2+2.25t2-2Zx1.5/-/-1.5/,令其

44、导数等于0,得片1。计算得到兀二兀()+甘0=(1,1.5)7,0W(1)=(0,0)|巧(兀)卜“则原非线性规划问题的最优解x*=x(1)=(-1,1.5)To(2)Y/G)=(4兀J+兀2,码+2(2)Y/G)=(4兀J+兀2,码+2兀2+2)丁,v2/W=12兀21、2丿x(0)=(0,0)r,V,此时Hesse定的，Newton法在此并不适用。5.7对问题minf(x)=xf+xf+xf9取初始点(1,1,1)和初始方向用Fletcher-Reeves法构造两个搜索方向，试考察这三个方向是否为共辘方向。200、解：W)=(2x1,x2,x3)r,=010,V/*(x(0)=(2,U)r

45、；oob/(x(1)=/(x(0)+Zp0)=(l-Z)2+丄(1一2/)2+丄令其导数等于0,卑2213153175则构造的第二个搜索方向P1=-vr（x）+/?中产（_几O/OO/O0/0V00、V00、131/676、P()t砂2=(T厂2,0)010-53/676(001丿、一175/676,32ho,所以这三个方向不13r200、J5/9、因为p（Hp、=（一1,一2,0）0105/9(001,丿=0,5.8用共辄梯度法求下列无约束条件极值，取初值兀=(0,0),精度=10,minf(兀)=(兀一I)V/(x)=(4xt+2x2V/(x)=(4xt+2x2+l,2x,+2x2-l)r

46、,p()=-Vf(x(0)=(-1?1)7minf(兀)=2兀?+2坷兀？+xf+x-x2解：(1)V7/(兀)=(8#+2兀一8西兀2-2,4兀2-4兀；)厂，p0=-V/(x(0)=(2,0兀=x(o)+/po=(2z,O)r,/(x(,)=/(x(0)+/p0)=(2t-1)2+32t4,令其导?到al/4,兀=(0.5,0)r巧(兀)=(0,1)厂，%J%?二1；|w(0)|4所以廿呵妙)+0创=生)宀八心0.5+0.53/(兀)=(/一1尸+0.25+0.125(1)2,令其导数等于0,得到Tx(V/(x(2)=(0,0)r,即|巧(兀)卜,所以原非线性规划问题的最优解兀7优值为0o

47、V7-T/.(1)V7-T/.(1)Trr.x(2)=兀+妬二(一1,1+2/)7,/(兀)=2-2(1+2。+(1+2/)2一1_(1+2t)其等于0,得到M/4,兀=(-l,3/2)r,Vf(x(2)=(0,0)r,即冈(兀)卜非线性规划问题的最优解x*=x(2)=(-1,3/2)t,最优值为1.25o5.9用DPF方法求解下列问题minf（兀）=2xf+卅-兀+3：（1、解:V/（x）=（4x1-1,2x2）t,取兀（o）=（0,0）,Hq=,v丄丿故得驻点=（1/4,0）T,有定理知.最优值/（兀）=2.875。5.10用Powell方法求解加丿丫兀丿=2兀；+兀；一2兀兀2-4卷，取

48、初值兀卩丿=(1,何Po=(1，丿1-Pi(丿r解：第一轮迭代：/(*丿+仇丿=2(1+02+1_2(1+。_4,由笑=0得dt兀=兀(丿+/oPo=(o.5,1y,f(x(v+/pj=o.5+n+o2-n+o-4fi+o得二1.5,x(2)=x(x)+tp=f0.5,2.5/，令卩2=兀丿=f-0.5,1.5)vf(x(2)+tp2)=2f0.5-0.52+f2.5+1.5/f-2(0.5-0.50(2.5+1.5。一4(由塹=o得(2=-言，从而解得”=X2；*也=(寻曇儿dt14加J丽2哙一2丹悄一2哙一2必罟悄由堂=o得斤dt2798匚+馮打口由堂=o得斤dt2798128982898

49、-(VXI人2严产丿_尹丿乂型df(tp2)-(VXIdt令9898，z=，得&詡,问题的最优解是匚=九=，ax13x(2)=x(v+%P=xw=(0.5,-,0.5+Xy/(兀+九“2丿=4-九2尸+(+入2，+(g+九2尸令=0=Z2=333Q九9X(3)=X(2)+九2P2=扌余丿T刃*(0,于一討，f(x(i+U=空-红)2+4人)2九)2,令%=0=九3兀=0.5平而上进行，且兀=3X2+l,二泌丿丸九=0二x(v=x(0)+九oP()=兀=(0.5,1,0.5/,f=f(x(v)=2幷e+j=2(i+九尸+九2,笙a二,dX3x(2)=x()+Z1jP1=xw=f0.5,I，0.5

50、/,f2=f(x(2)=兀+九八4_九尸+岸+九丿+d+入丿,令x2=z23333a9X(3)=X+入2P2=W，*，寻丿Tfi=f(X(i)=j因为/o-Z=2-2=O,/-/2=2-|=|,/2-/；=|-11,所以A=w兀0,*,号=,厂*(2兀一兀的=|，由于fZ)=:改变；第二次迭代：取几=(1,0,0儿几=(0,0QT匸2=(0,-右-詁T,令50的Kuhn-Tucker点。解：将原规划化为标准型为：minf(x)=(x1-2)2+x兀0,Xj-x21、-I=(0,0),匕0,解的入=。，入V7-T/.(1)V7-T/.(1)Trr.V7-T/.(1)V7-T/.(1)Trr.x(

51、1)=(0,0)不是Kuhn-Tucker点；同理可求的乂=(1,1)是Kuhn-Tucker点6.2求非线性规划问题minf(x)=x-xs.t.x,1的Kuhn-Tucker点，并验证该点是否是极小值点。解：将原线性规划化为标准型为minf(x)=x-xls.t.-Xj+10s.t.2x|x21=0的全局最优解。解：将原规划化为标准型为min/(x)=(西-2)2+(兀2-3)2(2x|)3-x2n0s.t.2Xj-x2-l=02%j4一6,Vg(x)3(州一2%j4一6,Vg(x)3(州一2)2、1V7i(x)=1丿，由Kuhn-TuV7-T/.(1)V7-T/.(1)Trr.V7-T/

52、.(1)V7-T/.(1)Trr.2(兀2)+3久(兀2)2+2“0解的/=(1,1),2=2，a2兀26+几一“=0规划的约束条件有b(x1-2)3解的/=(1,1),2=2，a(兀2)3+兀2然在x*=(1,1)处，g(x)=0是起作用的约束，/(x),g(x)在此点处均可微，j凸函数，加兀)是线性函数，故X*=(1,1)是原问题的最优解。6,4用外点法求解如下问题:(1)min/(x)=兀+兀2X,-x2oo时，x（k）=（0,0）当屛一兀20,西v0时，由VF（x,/J=0,得兀=（丄了竺1）,p2/4从时，严=（0,0）屛一兀2vO,-兀0时同样不存在使VF（兀，怂）=0的点。综上，

53、得该规划的最优解为xe）=（0,0）（2）同理可求的该线性规划的最优解兀=（0,1）6.5用内点法求解如下问题(1)minf(x)=xf-6x+9+2x2X,3s.txx23(2)min/(x)=xf+2xS.t.Xj+x21F(x,d.)=Xy-6x,+9+2x7+d.(F-解：(1)构造辅助函数-3-兀3VF(x.dk)=為VF(x.dk)=為-6+誥?0,得兀=（3+前-久/2,3+扯/2）,s.t.Xj+x2-20(2)min/(x)=ln(Xj-x2)Xj-10S.t/x：+x；-4=0解：(1)引入松弛变量y,原问题化为min/(%)=2xf+xf-xx2s.t.-x,-x2+2+

54、y2=0构造辅助函数F(x,=2兀;+兀；-XjX2+久(2-兀】-x2+y2)d(2-x,-x2+y2=2彳=2彳+分+(”+評(27“2)+盯_A22AV7-T/.(1)V7-T/.(1)Trr.V7-T/.(1)V7-T/.(1)Trr.取y2=lmax(0,-/g(x)-2),代入上式，则原不等式约束问题能化为可解纟nun(于(x)H(max(0,“(2西一兀?)+2)2才)2“兀2)+2)2A2)X,+x22兀=(+,5几+,取“=10,2=1,纟7+8“7+8“题的最优解为=(0.75,1.25)(2)同理可求的原规划问题的最优解为/=(1,73)解：Frank-Wolfe方法将原

55、问题化为标准型为：min/(x)=x+兀;-2x-4x2+62xx-x2-10s.tA+x2-20W(x)=2旺-W(x)=2旺-2、A-4,取初值沁)=(0,0),V7-T/.(1)V7-T/.(1)Trr.V7-T/.(1)V7-T/.(1)Trr.第一次迭代：构造近似线性规划2兀卷一10s.tsx,+x2-20minVf(x()12兀卷一10s.tsx,+x2-2z下降方向Po=y()一x(0)=(0,2)T,一维搜索求解min/(x(0)+勿()=4A2-Ao=l,x(1)=(O,2)第二轮迭代构造近似线性规划minV/-(x(,)Tx=-2旺2%|兀210s.tAx+x2-20求得该

56、线性规划的解为y(1)=(l,l)T,又|号(兀)丁。一兀)门=丁一兀=(1,_1),min/(兀+/!“)=2才一22+2,维入=l/2=x=兀+入=(0.5,1.5)1第三次迭代构造近似线性规划函数minVf(x)丁兀=-坷-兀2一nIfII.KtB.1IfII.KtB.1、TZoutendijk方法w)=2西-w)=2西-2),取初值艸=(0,0)IfII.KtB.1IfII.KtB.1、TIfII.KtB.1IfII.KtB.1、T(_10、(9(oA(1A第一轮迭代心)=3,4,Ao=n11、如二n,&20-1丿1丄1丿2丿构造辅助线性规划minV/*(x(0)*p=-2。-4p2一

57、PiS.tJ-p2,沿p(0)方斤一1pit()=1=x(1)=x()+t(p(.、(2一1)(一10)(1)第二轮迭代/(兀)=1,2,AJt=,A2=,bjj=,b2=1110/2/构造辅助线性规划minV/*(x(1)Tp=-2p22-0s.tlp.+p20解得p(1)=(-i,i),又|y/G)S-1pi1,Z=1,2沿P进行一维搜索纟=妇_码兀NW，=每4产(1，一1几以索求解min0rjl索求解min0rjx二兀+斤门=(0.5,1.5)r“2第三次迭代“2第三次迭代7(x(2)=2,A12=(1,1),bn=(2),A22=一10_1)0Z?22=7min/(%)=%,2一xx2

58、+2兀；一3x,一x2x,+x25s.t&3X-x20解：将原问题改写为：minf(x)=%j2-xx2+2xl-x2+x253x)-x22S.t/XjW0_兀20此时,=(U)ai=(3-l)a2=(-1,0/,tZ4=(0-1/,取初始可行丿兀二（0,0丿丁,第一轮迭代：I（）=3,4,则有等式约束二次规划汕P；-皿2+2pI-3。-P2f-Pi=s.t.-“2=0用Lagrange乘子法求此等式约束二次规划，由（6.19）有方程组2-1一10P_3_-140一1Pi1一1000X100一100kJ0解之得:p=（0,0几炉=（一3,-1几由于=-30,取严”二。几72V7N）V3；=/4

59、/2-1P3由(6.19)有方程组：-140Pi=1-100入0解之得/2丿=(0,0.25丿t,”2丿=_3.25,取?“二兀心丿+卫心丿=(0,0.25丿T,可行点可进一步迭代求得原问题的最优解：=(0.875,0.625/,最优值为2IfII.KtB.1IfII.KtB.1、T习题习题77.1利用理想点法求解多目标规划max/j(x)=_2兀+兀？max/2)=xx+3x2Xj+x212s.t/3兀+2兀20解：求出(%),(兀)的最优解为x(1)=(0,10)T,x=(0,10)T,f=(10,30)r得到单目标规划问题minw(y)=(2xj+Xj10)兀+6兀2-24jq+2x2兀

60、+6兀2-24jq+2x210-0解：将“极大化问题”转化为“极小化问题”得多目标规划min/,(x)=一3兀一5x2min/x)=-x-4x2x+x212s.t/3x+2x20解之得h=(2.8751,5.7143)t,相应的目标函数值为f、(/)=0J2(/)=2(7.2利用线性加权法求解如下问题:maxf(x)=3x+5x2s.tsmax/x)=兀+4x2s.ts2兀+6x224s.t.0解此约束非线性规划得X*=(6,2)T,由于权向量大于0,故/=(6,2)r；最优解。7.3利用极大极小法求解如下问题：minf(x)=2x1+(x2-l)minfx)=x+3兀？+11州兀2一4s.t