最优化方法及其应用课后答案(郭科-陈聆-魏友华)1

1、最优化方法部分课后习题解答习题一直优化问题的数学模型为：mill/(a)=(西-3)3+(x2-4)2|I(a)=x1-x2-50品m+520gQn&U)p2O试用图解法求出：无约束最优点，并求出最优值。约束最优点，并求出其最优值。(3)如果加一个等式约束/(R二入-勺二0，其约束最优解是什么？解：(1)在无约束条件下，/(a)的可行域在整个qO勺平面上，不难看出，当x=(*4)时，/(取最小值，即，最优点为=(3，4):且最优值为：/(X)=0(2)在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点(心逅)，使其落在半径最小的同心圆上，显然，从图示

2、中可以看出，当二(,-)时，所在的圆的半径最小。44;5鼻二匕其中：点为&(和於(为的交点，令和沪X：J0求解得到：|多(坊二_/一禺+5二0心二二-4即最优点为=(,-):最优值为：/(/)=6448.若増加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。2.个矩形无盖油箱的外部总面积限定为S，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：max二狂西陆疋+2衲+2幸S0该优化问题属于三维的优化问题。禺0无0a=Jsl3、y二a=Jsl3、y二Jsl3忆二5/5/128-2将它对变量x(z=l,2,.4球偏

3、导数得:XX八丿工iiipi户1j=iv/(+A1-2-v/(+A1-2-+Aa-1-25求下列函数的梯度和Hesse矩阵(204(1)/(a)=珂+2,扌3.#34xx13解：V2/W=o40-406(2)血二3山+声解:V2/(.x)=计唱6判断下列函数是凸函数凹函数还是既不凸也不凹函数:(1)/(心心二古2兀2护XX2解：v3/w不是半正定，即/非凸，然后判断-/(、)，经验证：v3(-/()不是半正定，由此可知：/(.X)非凸非凹。(2)f(xx=lx2j-4xx+?x2_jx-6解：V2/(.x)半正定，故/(.为凸函数。由约束条件为&(R50由约束条件为&(R50时的K-T条件得，

4、应有:(3)/($令忑)二2+2才-3无2-4卫解：v3/w不是半正定，即/(非凸，然后判断-/(经验证：v3(-/)不是半正定，由此可知：/(非凸非凹。7设约束优化问题的数学模型为：min/(耳=x24xx254x+10&m+220叫00f2x+gxQ试用K-T条件判别点卜1,1是否为最优点。解：对于点x=-l,l7ga=0,g($20，点满足约束条件，故点X是可行解。且&(是起作用约束，/二1,v/3二|Vg(.x)=|11由0条件下的2丿1KT条件得：W-IW=0A得到入=2，点x=-l,l满足KT条iel件。又因V3/。)正定，故/(.X)为严格凸函数，该最优化问题是凸规划问题，由x=

5、-l,lr是K-T点，所以/=-1,17也是该问题的全局最优点。8设约束优化问题：min/(A)=(XY2)2+x22Jg二一$1、(.9二-1+彳+心0它的当前迭代点为兀二1,0，试用KT条件判定它是不是约束最优解。解：对于点xk=l,o7g(jX*)A=-1所以x=l.o7为KT点。直/现判断该问题是否为凸规划问题因旷/(正定故/(.X)为凸函数g(心g(A)线性函数，亦为凸函数，V2g(.X)誉正定，所以gS为凸函数，所以该优化问题为凸规划问题，即点x,=l,o7是该问题的约束最优解。习题三1.对于下列线性规划问题找出所有基解指出哪些是基可行解并确定出最优解。max/（A）二3/+忑+2

6、无12入+3忑+6勺+无=9阿+勺-4无+2勺二103-弋二0Q0,二1,2.6）1236300解：令4二81-4020吨,朋,朋)30000-11基解X】二十学J。)不是基可行解，6(2)基解忑二(0,10,0,7,0,0)不是基可行解，(3)基解寿=(0,3,0,03.5,0)是基可行解且/(.X)=3，基解北二(#-4,0,0,0,晋)不是基可行解，(5)基解马=(0,0,-,8,0,0)不是基可行解2(6)基解x6=(0,0,罗,16,0)是基可行解，且/(二3,(7)基解*7二(1,0,-1,0,0,3)不是基可行解2(8)基解忑=(0,0,0,3,5,0)是基可行解且/(.)=0(

7、10)基解总=(；0,0,0,4,$是基可行解，且/(R=(9(9)基解冯二心0,0,-2,0,44基解忌=(0,Io,0,0)不是基可行解。36(12)基解七=(0,10,0,-7,0,0)不是基可行解。(13)基解七=(0,3,0,0,是基可行解，且/(.)=3。2(14)基解X4二(0,0,-5,8,0,0)不是基可行解。2(15)基解“5二(0,0,彳寸),8,0)是基可行解且/(R=3(16)基解屁二(0,0,03,5,0)是基可行解，且/(.X)=3。用单纯形法求解下列线性规划问题：max=10.y+5x,(1)3+仆9si5.勺+2工20作初始单纯形表，并按单纯形表步骡进行迭代，

8、如下:b-10-50勺000、934103085011.60-1050004.202-810.61.5-101.610.400.24160-10-51.501514314-10110172717.5005142514此时，o均为正，目标函数已不能再减小，于是得到最优解为：=(1,30,0)目标函数值为：/(x)二17.5分别用单纯形法中的大M法和两阶段法求解下列线性规划间题:minmin二5q_2忑+_6忑(1)x2x/3x扌4x亍7(1)%+2号=3解：(1)大M法：把原问题化为标准形式，并加入人工变量如下：min/(a)二5q-2勺+3$-6无+咙+性+2勺+3马+4不+忑二7&gx古x-

9、t,x+#二2作初始单纯形表并按单纯形表步骤进行迭代如下:GX”b5孑3勺-6-6-6QMX571?34101.75MX632112011.5-1OM5-3M-2-3M3-4M-6-6M00MX51-30101-?A/1-61.510.50.5100.539-M11+3M16-M003M+331-30101-?A/-612.50.501-0.51.5329100M-6M+15因为M是一个很大的正数此时J均为正所以，得到最优解：x=(0,0,11,)7最优值为/(/)=-3(2)两阶段法首先构造一个仅含人工变量的新的线性规划如下：mingR二+0忑+0西+0忑+g+弋人+2勺+3召+4召+勺=7

10、0XX+?X+4二g心逅”勺心忑疋20按单纯形法迭代如下：h000占0北1北1忑q171?34101.7513?112011.5-103-346001130101101.510.50.5100.53-14010030130101-?0V12.50.5010.51.5最优解为:x=(0,0,HO,0)最优值:酌=0因人工变量芒二七二0，则原问题的基可行解为：X*=(0,0,u)T，进入第二阶段计算如下表所示：b53勺6313010612.50.501329100由上表可知检验数均大于等于0所以得到最优解：x二(0、0丄1/最优值为fx)=-34某糖果厂用原料A，B、C加工成三中不同牌号的糖果，甲

11、，乙，丙，已知各种牌号糖果中AZBX含量原料成本各种原料的每月限用量三中牌号糖果的单位加工费及售minmin二5q_2忑+_6忑价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。甲乙丙原料成本（元/千克）每月限用星（千克）A60%15%2.002000B1.502500C20%60%构造此问题的数学规划模型如下:max/CO二09丫+1.4范+19忑+045为+0.95另+145号一05勺+0.45+0.95仓q+$+&520002500无+牙+召12000.4.一0.6忑一06忑3002X+02x308x?006为一06月+04占200

12、.5+0.52)-0.50禺帖20二1,2,35求解下列线性规划问题的对偶问题min/(a)二2彳+2忑+4忑2+3忑+5无22(1)|#+x扌7x$3&+4忑+6无5眄20max/(=5%+6忑+3无入+2呂+2无二5(2)-入+5忑-西23S14%+7勺+38x无约束,兀玄0,x00解：（1）由表37可得该问题的对偶问题为：max我）二2刃+3力+5必2)1+3北+沙2甲+戈+4沪25乳+7北+6号W4)120,月，月0（2）该问题的对偶问题为:min取）=5为+3昱+8月严-3月+4牙二52）1+5月+7輕6|2）1-+30建立初始单纯形表如下图所示，所有o,0。则对应对偶问题解是可行的

13、则继续迭代：GXrh412180斥0马0310310050卜22014121800计算min-3,-5=-5，所以为换出变量0=min（6,9）=6，确定勺为换入变量继续迭代得到如下单纯形表:Gh41218无0斥0马0310卜31002.501100.540600min-3）=-3,不换出min（42）=2勺换入Gh41218无00冯011011001.511010.5?0026此时，所有o0.故原问题的最优解为八0,-,17优值为：/(巧二362其对偶问题得到最优解为：二2,6卩,最优值为：/(f)二36。7已知线性规划问题niin/(二2q_+马X+F礬6st-xj2x$4眄o先用单纯形法

14、求出最优解，再分别就下列情况进行分析：(1)目标函数中变量齐込必的系数分别在什么范围内变化，问题的最优解不变;(2)两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量易心min/(R=2q-兀十忑+0土+0,低+忑+无二6口|一坷+2x?+xf4忑眄用/0用单纯形法求解，如下表:bA/q-11忑0无0马0111110601.5-12001?A/1100041.5011-0.5-1-0.51000.51.50100.5由上表可知所有的检验数均大于等于零，得最优解：二(0、2gO)7：所以原问题的最优解为：x二(0,2A)；最优值/(x)=-2(1)

15、变量、忑中，勺为非基变量勺为基变量。护以，当C勺护以，当C勺1寸8),此时最优解不变。minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑由a3=1当冬2-1时=q+Aq0所以当qG0,+8),此旳最优解不变。Ace(-3,1)，最优解不变。综上，当qe-,+oo)c2e-4,0c3G0,+oo),此时最优解不变。2(2)创的变化范围4fli4fli11110得到：4+A/p0nA/p-4，则Q的变化范围是恥2，最优解保持不变。沪決沪1卩一5口11-0.51ro二+二+A/?厨M|o0.5购丿Mo.5)2W得到:-4Afe则的变化范围是0,12最优解保持不变。习题四3用Newton

16、法求解（X0二户-2/+1用第1题求得的区间，按精度=0.01计算。解:忸）二叹o）社+4，樹）二0血二0,因为帕）他），则彳二4=2A二（+彳=1讽4）二22Q二22,（|）（）b=3继续迭代t=t5-6则搜索区间为te0,30(D-3f-2/0继续迭代t=t5-6心二i,E(/)o=)ua所以t=i-1=/o/船4加/船4加二0.01,令/二一则I-0.8165，6060|/-()|=0.0005(KO=0.115136,(X0=7.667136，因为帕)廉)，则新的搜索区间为3，1.944：A=(二0.056,Wg)二0.115136,(=-1.11392,(X0=一0.987592，|

17、&继续迭代，因为忸)枢)，则新的搜索区间为卜3，0.056:4=-1.832608,(H()=-0.306764站=-1.111392,(XA)=-0.987592，|&继续迭代，因为(X()帼)，所以新的搜索区间为-1.832608.0.056:4=-1.111292,|)()=一0.987592,$=-0.665448,X)=-0.888075，|&继续，牠)，所以新的搜索区间为-1.832608，-0.665448:4=T.386753,(X0=-0.854402,A=-1.1U392,(|)(A)=-0.987592|&继续，因为忸)帼)，所以新的搜索区间为-1.386753，-0.6

18、65448A=-0.940987,惟)=-0.996518,(=-1.111392,(X()=一0.987592，|&继续，因为(W)g)，所以新的搜索区间为-1.111392-0.6654484=-0.940987,0(0=-0.996518,$=-0.835799,牠)=-0.973038，|&继续，因为帕)廉)，所以新的搜索区间为-1.111392.-0.835799A=-0.940987,(Kg)=-0.996518,(=-1.006115,0()=一0.999962，|&继续，因为帕)廉)，所以新的搜索区间为-1.111392-0.940987h=-1.046295,(X()=-0.

19、9978574=-1.006115,(|(A)=-0.999962，|&继续，因为帕)廉)，所以新的搜索区间为-1.046295-0.940987A=-0.981215,帼)=-0.999647,(=-1.006115,(X0=0.999962，|&继续，因为帕)廉)，所以新的搜索区间为-1.046295-0.9812154=-1.021434,(X()=-0.999540,A=-1.006115,g)=-0.999962，|&继续，因为帕)廉)，所以新的搜索区间为-1.021434，-0.981215A=-0.996579,(X0=-0.999987,(=-1.006115,(X0=一0.9

20、99962，|&继续，因为帕)廉)，所以新的搜索区间为-1.006115-0.9812154=-0.996579,(X0=-0.999987,A=-0.990727,()()=-0.999914，|&继续，因为帕)-0.990727A=-0.996579,艳)=-0.999987,(=-1.000237,&继续，因为(M)-0.9965794=-1.000237,0(0=-0.99999364,A=-1.000237,(X0=-1.00000016.|&继续，因为帕)廉)，所以新的搜索区间为-1.002472-0.996579A=-0.998830,(XA)=-0.999998505,(=-1

21、.000237,(X0=-1.00000016，|-A|&继续因为(|)()，新的搜索区间为-1.002472-0.998830=-1.001081,(KO=-0.999999075易=-1.000237枫)=-1.00000016，因为|(|停止迭代。所以：t=-1.000659,8=(K/)=-0.9999999565。5用抛物线插值法求解niin/W=8-2r-7x+3已知初始单谷区间a，b=02s=-0.001。解：=0,A=2,取二1三0.5227t_|=-0.063(0=2新搜索区间为0，1y二0仏=1,()=0.5227t=0.5704,fcp=-0.1588s,F=-0.200

22、4t三06232,It-r|,/(,!)(/)=-0.2029(0=-0.2004，所以新的搜索区间为:0.6146.1-二0.6146,$二1,6=0.6232，t三0.6260,卜f(X/J=-0.2032,f(j,XO=-0.2034t=0.6276,|)-F|*=(f)-0.2034。习题五1用最速下降法求解mill/(=x2i+25x2jx0=2278=0.01.1、解：呼（耳二2$50还minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑ft=W)=4,100。亂=2-002003-4-191988虑02.100.-0.003T|=100.07997召=心一&二VTQ)

23、二3&976-0.15:/$)=3.686551.91988-0003.-0.4808938976,0.1500734&0.06913Iminmin二5q_2忑+_6忑金）=0.124872|&|eroi01T同理继续迭代，最后至x=L此时最优解I,=02用Newton法求解niin/(=60-10-4+2+.2-初始点弔二0078=0.01.解：如)=V/W=-10+2X一$,g+2x122-11的二=对二33I1-12132si211IroiL,3-107.fq二心-6(沪血)亍|-|J|=8,61|12|L4k3J叭)二0,0II恥)11=0O7s=0.01.解：曲）二号3二岡+9,4丕

24、-3畝二|解：曲）二号3二岡+9,4丕-3畝二|91?ZI,I8O04fl，时f.00I，g(二974lf91则卩二-QB如X）二-3=VU=3W)|=oo.oif(x=备-勿辔6=/=10寸J(.最1W)|=o取初始点x0=1I7s=0.01.解：令血二卄4己附（9二2x,8订畀0=-欧叫=-2,8%:卜7,18则令min(l-202+4(1-8Q，=niin(|(0=520/玄68二0=f=0.130969则;q二0.738062,-0.047752/V/(r)r1-476124,-0.3820167IIV/W|；=2324878=0034189|恥)II368新搜索方向为M二-V/G)+

25、入用T6鬥+0034892一二-1.5445020.382016Jb8.0.108504.因此有忑二中/pr0.738062-1.544502r,10.047752+0.108504/由4/(x亍0=/二p.477127at因而得下-迭代点因而得下-迭代点切話薦;752),0.007y0.477127II=00.108504J|V/()卜0pQ=-21701A=+U=|J何一2二旷令min2略+(1-2厅-(1-2Q二mingminmin二5q_2忑+_6忑minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑吗二03125,-03757呼(兀)尸08

26、75,04375=0.1914062二I附Q)_0.95703125o_ww一=0.191406新搜索方向为M二-VZQJ+入a-0.875+0.1914061二-0.683594-0.4375.1-2.-0.82012.则搜索方向则搜索方向A=-0.28017,4.48248minmin二5q_2忑+_6忑因而得下一迭代点忑二忑+4卜0.3125-0.683594/f.375-0.820312/由和刃亍0=f二p.456927，dt则x2=0.000,0.0007，W)2=，r，|w)II二0综上所述，原问题的最优解x=0,07最优值为/()二06用DFP法求解min/(=4(Xj-5f+(

27、x26)2，初始点x8，邯吃=0.01.6、解:取弘-1,人二町:，酌二&丫-40,2勺-121遍二8,19,&二24,6第一步迭代得:=4.86154,8.215387,g=-1.10768,4.430767用DFP法第二次迭代:sQ=xrx亍-3.13846,-0.78462，y0=grS-25.10768,-1.569247rpilH_HIodoo)onno因：=80.03071,収比哉“=632.858119.849932.462502.462500.61563o9.849932.462502.462500.61563o=|9.849932.462502.462500.61563则搜索

28、方向则搜索方向A=-0.28017,4.48248minmin二5q_2忑+_6忑则搜索方向则搜索方向A=-0.28017,4.48248minmin二5q_2忑+_6忑1(T14.0.123080.030770.996110.062260.12697-0.0314901.T0.030770.00770.0.062260.00390.一0.031491.0038J=minmin二5q_2忑+_6忑从无出发沿A进行直线搜索，即：q二4+二4.86154-0.2801748.21538+4.48248/由为(xfp)f0ir=-0.48674所以x2=xf)电5.000,6.000，由于g(x)二

29、0,0/，所以x3=5,67是极小占。/习题六1用外点罚函数法求解：minf（9二q+逅冷（二-扌+吋0I&G）T20解：利用外点罚函数法构造増广目标函数，如下：lrv+5+h(联。l-S+运(氏D)对于尤年。的情况:由H肖ax.112+2由H肖ax.112+2卩，4(1+0当yT+8时，#（2T（0,0）即：x=（0,0）且/（x）=02用外点罚函数法求解：minmin二5q_2忑+_6忑解：构造増广目标函数：minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑(珑。(xeD)minmin二5q_2忑+_6忑minmin二5q_2忑+_6忑对于x年D的情况:=0,0oaxy得：f

30、(x)T(i,0)x=(l,O)/(/)=8-35用内点罚函数法求解:min-(x1+l)3+x3x-100解法同上。习题七用动态规划求解：maxE-3*+忑+注4si20(=1,2,3)解:将原问题表示为:maxE二以(区3U+W+lA0(/=1,2,3)由此，确定状态变量为:、丕，忑，决策变量为:4,线，均状态转移方程：入二1(；召二堆+4；忑二均+忑k二1:人=max】=心且匚r。0第二步*2:&二maxMWG)二max*他-处)二maxWQF(Eg令：(K=U5(X2-2)由eQ2)=0，得=-x22./Q)=max0-4,0=Si=2第三步k二3:g声号=maxORn3-)J(E0=

31、max心%3皿g,笛4同理令：(K0pjy；W)y由(3)=得-扌心.-./X)=max0土,0二二总国二=64642.样4/(X)=-X44=464将ZG)二4代入上述表达式逆序递推求出：x3-4,亍2x2二2,m-r1x1=l,fZ1=l.新问题的最优解为:u=(1,1,2)耳3)=4原问题的最优解为：x=(1,1,2)耳()=4.2设有5个城市编号从1到5，记第i个城市与第j个城市的距离为4记:22|5722|5751I03301600.5。二畑二150.50151试分别用函数迭代法和策略迭代法求出各城市到第5个城市的最短距离。解：法一，函数迭代法：k二1时了(二必(匸1,2,3,4,5)X(l)=2,jf(2)=7,jf(3)=5,jf(4)=3,jf(5)=0.R二2时活0二minM+Jf(力，(1)=min0+2,6+7,5+5,2+3,2+0二2=(1),(2)=min6+2,0+7,0.5+5,5+3,7+0二5.5主jf(2),(3)=min5+2,0.5+7,0+5,1+3,5+0二4工jf(3),(4)=min2+厶5+7,1+5,0+3,3+0二3=jf(4),(5)二0二/(5).对于所有并不满足(D二jf故须继续迭代。3时，的二min4+ZO)，0巧5(1)=min0+2,6+5.5,5+4,2+3