最優(yōu)化方法習題答案

1、AAV習題一1.1利用圖解法求下列線性規(guī)劃問題：maxz=X+x23X+x22s.tJxj+2x20解：根據條件，可行域為下而圖形中的陰影部分,，有圖形可知，原問題在A丿最優(yōu)值z=5(2)minz=-6x22X+x21-X+x20解：圖中陰影部分表示可行域，由圖可知原問題在點A處取得最優(yōu)值，最優(yōu)値-x,+x2-4xpx20解：如圖所示，可行域為圖中陰影部分，易得原線性規(guī)劃問題(4)minz=2x,-5x2X,+2x26s.tJX)+x20解：由圖可知該線性規(guī)劃可行域為空，則原問題無可行解。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是最優(yōu)解，最優(yōu)值是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；所以原線性規(guī)劃的基可行解是x,x(Hx,x),最優(yōu)解是x，最優(yōu)值是z1.3用單純形法求解下列線性規(guī)劃問題；(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根據單純形表可知，原問題的最優(yōu)解為X*=(5,0,0,3),最優(yōu)值為=10(2)maxz=x1+x2-2x33Xj+x2-x37

6、xpx2,x30解：引入松弛變量X,剩余變量X5和人工變fix6,把原問題規(guī)范化為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所以原問題最優(yōu)解為x=(3A4),最優(yōu)值為z=-5ominz=2x1+3x2+x3X+4x2+2X38s.tx

7、3X+2x26xpx2,x30解：引入剩余變量X4,X5和人工變量x6,x7，利用兩階段法得到輔助線性規(guī)劃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,將原問題化為規(guī)范式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設目標函數極大化的線性規(guī)劃問題的單純形表如下，表中無人工變量，

9、哲衛(wèi)2，”5工2為何值時，表中的解：（1）為唯一最優(yōu)解，（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種食品的單位售價為耳，每種食品含營養(yǎng)成分，第j種食品每一個單位含第i種營養(yǎng)成分為,每人每天對第i種空要量不少于S,試確定在保持營養(yǎng)成分要求條件下的最經濟食譜。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寫出下列線性規(guī)劃問題的對偶問題: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寫出該線性規(guī)劃問題的對偶問題；已知對偶為題的最優(yōu)解為(2,6),試用互補松弛定理求其原問題的最優(yōu)斛解：(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聯(lián)立聯(lián)立解得2x2=3即原問題的最優(yōu)解為(0,3,1)2.4對線性規(guī)

14、劃問題maxz=2x,+x2+5x3+6x42X+X3+X40寫出該線性規(guī)劃問題的對偶問題；已知原問題的最優(yōu)解為(0,0,4,4)，試用互補松弛定理求對偶問題的最優(yōu)解：(1)原問題的對偶問題為：minz=8y+12y2(2)利用互補松弛定理有(yA-c)x=O0201V呵231201V呵231有1-(2,1,5,6)=0力+2=5有卜+22二6即門72=1所以對偶問題的最優(yōu)解為(4)2.5用對偶單純形法求解下列線性規(guī)劃問題：(1)minz=2x)+4x2+5x3X+x2-3x31s.tJ-x,+x26xpx2,x30解：利用對偶單純形，添加松弛變量X4,x5,原問題化為規(guī)范式Imaxz=-2X

15、|-4x2-5xs-Xj-X2+3X3+X4=-ls.t.0X1X2X3X4X52-4-500X4113101X510016由表可知。原問題的最優(yōu)解為(0,6,0)(2)maxz=-x,-x2-2x3X)-5x2+3x310Set/X-2x2+3x30解：利用對偶單純形，添加松弛變量X4,x5,x6,原問題化為規(guī)范式: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由表知原問題無最優(yōu)解。2.6設有線性規(guī)劃minz=-2x1+x2+x33Xj+x2+x360Xj-x2+2X310S.t/X,+x2-x30求出最優(yōu)解，并進行以下分析（1）C2在什么范圍內變動而不影響最優(yōu)解？（2）b?從20變?yōu)?6,求最優(yōu)解；（3）X3的系數變?yōu)椋?,3,-1）,其價值系數從1變?yōu)?,試問最優(yōu)解是否會發(fā)占（4）增加約束條件2X14-x2+x531,最優(yōu)解

17、有何變化？解：引入松弛變量x4,x5,x6,將原問題化為規(guī)范行：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所以原問題的最優(yōu)解為(15,5,0,10,0,0)_173因為X?是基變量，由書中(2.6)式有max(-)=-l,min(-2-,-2-)

18、1-1-2_0)10、所以此時原問題的最優(yōu)解為(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所以原問題的最優(yōu)解變。(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得最優(yōu)解為(41/3,11/3,0,46/3,0,8/3,0),最優(yōu)值為-71/32.7某廠生產A15A2,A3三種產品，需要BpB2,B3三種設備加工，需要單位莘要的設備臺時、設備的現(xiàn)有加工能力及每件產品的預期利潤如下表所示臺/hA】A2A?設備談B】111100b21045600B3226300單位產品利潤1064求獲利最大的產品生產計劃；每件產品A?的利潤增加到多大時，才值得安排生產？如果每件產品A3白a）如

20、合同規(guī)定該廠至少生產10件產品A3,試確定最優(yōu)計劃的變化。解：設計劃生產產品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得最優(yōu)生產計劃，即(100

21、/3,200/3,00000)為最優(yōu)解，獲利2200/3元由于X3為非基變量，則只有a0才值得3Ac3-c3,即Ac38/3,即c20/3時A3才值得生產。而當c3解發(fā)生變化，根據計算，當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此時生產最優(yōu)計劃為(175/6,275/6,2500,0)由于召的生產量為基變量，則有呎需，課卜-4,gw-4,5時，原最優(yōu)生產計劃保持不變。得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，則此時最優(yōu)解發(fā)生變化，且該產品值得生產(6)原最優(yōu)解不滿足新的約束條件，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時，首先出現(xiàn)60,故當0t-時，得最優(yōu)解(0,3目標函數的最優(yōu)值為maxz=220(0t-)ot=為第一臨界點33當10,故當*4時，得最們目標函數的最優(yōu)值為180+151,匸5為第二臨界點。當t5時，60,X】作為換入變量，由8規(guī)則確定X2為換出變星，用單鄉(xiāng)代：Cj7+2t12+t10-t00CbXbbX】X2X3X4X50X45001/21-1/27+2tX115111/201/2-z-105-30t05-t13/2-2t07/2-t由表知當t繼續(xù)增大時，所有檢驗數都非正，所以當t5時，得最優(yōu)解(15,目標函數的最優(yōu)值為105+301(1)用單純形方法求出最優(yōu)

25、解;廠-2、廠-2、改變?yōu)?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、-，問題的最優(yōu)解為(8/3-t/3,4/3-5t/3)當t+時，利用對偶單純形有XlX2X3X4023/2/3X403214X1110z由表可知當時，問題的最優(yōu)解為(42t,0),當02時，原問題無解。習題三3.1用割平而法求解下列整數線性規(guī)劃。(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所以，原線性規(guī)劃問題的最優(yōu)解為X瘁=(0,4),是整數解所以也是原整數規(guī)劃f(2)maxz=-12Xj+9x22X+x2+x310-X,+5x2+x46maxz=-12x+9x2s.tx3x1-2x2+x5oja為整數先不考慮整數條件，則對應線性規(guī)劃單純形表如下兀2x3兀4X5Z-129000兀321100兀4-15010X532001以七作為換入變量，兀4為換出變屋得兀卷兀3兀4X5Z51/500-9/50屯11/501-1/50兀2-1/5101/50X513/5002/51所以線性規(guī)劃的最優(yōu)解為(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由表可知最優(yōu)解為(0,1)最優(yōu)值為9.3.2用分支定界法求解下列整數線性規(guī)劃問題:(1)maxz=X+5x23X+4x2113X+4x2117X+6x242s.tJ(1)

29、x22x15x2no且為整數和maxz=X+5x23X+4x2117Xj+6x23x15x2o_a為整數先不考慮整數的約束條件，求解(1)所對應的線性規(guī)劃子問題得到最優(yōu)解X二值為Zj=11,(2)所對應的線性規(guī)劃子問題沒可行解。故原整數規(guī)劃的最優(yōu)解廣最優(yōu)值為Z=11。(2)minz=3x2x2-X+2x27s.t.9X1?x20且為整數3.3求解下列01規(guī)劃問題：(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由表可知，原問題的最優(yōu)解為（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種規(guī)格的服裝，數量如下A為1500套,B為2000套，C為3000套，D為3500套。有三個城市可供應上述規(guī)格服裝，各城市供應數量如下1為2500套，II為2500套，III為500套。由于這些城市的服裝質量、運價和銷售情況不同預計售出的利潤也不同如下表所示，請幫該公司確定一個預期盈利最大的采購方案。4.5求解下

32、列最大值的指派問是(1)10961715141020181313191681226城市規(guī)格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利用最優(yōu)

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（這是經過反復計算確定的，計算中發(fā)現(xiàn)初值的選擇對方響很大。）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)|巧(兀)卜“則原非線性規(guī)劃問題的最優(yōu)解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創(chuàng)=生)宀八心0.5+0.53/(兀)=(/一1尸+0.25+0.125(1)2,令其導數等于0,得到Tx(V/(x(2)=(0,0)r,即|巧(兀)卜,所以原非線性規(guī)劃問題的最優(yōu)解兀7優(yōu)值為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,即岡(兀)卜非線性規(guī)劃問題的最優(yōu)解x*=x(2)=(-1,3/2)t,最優(yōu)值為1.25o5.9用DPF方法求解下列問題minf（兀）=2xf+卅-兀+3：（1、解:V/（x）=（4x1-1,2x2）t,取兀（o）=（0,0）,Hq=,v丄丿故得駐點=（1/4,0）T,有定理知.最優(yōu)值/（兀）=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=，得&詡,問題的最優(yōu)解是匚=九=，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點。解：將原規(guī)劃化為標準型為：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求非線性規(guī)劃問題minf(x)=x-xs.t.x,1的Kuhn-Tucker點，并驗證該點是否是極小值點。解：將原線性規(guī)劃化為標準型為minf(x)=x-xls.t.-Xj+10s.t.2x|x21=0的全局最優(yōu)解。解：將原規(guī)劃化為標準型為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規(guī)劃的約束條件有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)是原問題的最優(yōu)解。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、得該規(guī)劃的最優(yōu)解為xe）=（0,0）（2）同理可求的該線性規(guī)劃的最優(yōu)解兀=（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“題的最優(yōu)解為=(0.75,1.25)(2)同理可求的原規(guī)劃問題的最優(yōu)解為/=(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.第一次迭代：構造近似線性規(guī)劃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)第二輪迭代構造近似線性規(guī)劃minV/-(x(,)Tx=-2旺2%|兀210s.tAx+x2-20求得該

56、線性規(guī)劃的解為y(1)=(l,l)T,又|號(兀)丁。一兀)門=丁一兀=(1,_1),min/(兀+/!“)=2才一22+2,維入=l/2=x=兀+入=(0.5,1.5)1第三次迭代構造近似線性規(guī)劃函數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丿構造輔助線性規(guī)劃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/構造輔助線性規(guī)劃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,則有等式約束二次規(guī)劃汕P；-皿2+2pI-3。-P2f-Pi=s.t.-“2=0用Lagrange乘子法求此等式約束二次規(guī)劃，由（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,取?“二兀心丿+衛(wèi)心丿=(0,0.25丿T,可行點可進一步迭代求得原問題的最優(yōu)解：=(0.875,0.625/,最優(yōu)值為2IfII.KtB.1IfII.KtB.1、T習題習題77.1利用理想點法求解多目標規(guī)劃max/j(x)=_2兀+兀？max/2)=xx+3x2Xj+x212s.t/3兀+2兀20解：求出(%),(兀)的最優(yōu)解為x(1)=(0,10)T,x=(0,10)T,f=(10,30)r得到單目標規(guī)劃問題minw(y)=(2xj+Xj10)兀+6兀2-24jq+2x2兀

60、+6兀2-24jq+2x210-0解：將“極大化問題”轉化為“極小化問題”得多目標規(guī)劃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解此約束非線性規(guī)劃得X*=(6,2)T,由于權向量大于0,故/=(6,2)r；最優(yōu)解。7.3利用極大極小法求解如下問題：minf(x)=2x1+(x2-l)minfx)=x+3兀？+11州兀2一4s.t