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

1、百度文庫-讓毎個人平尊地提升門我練習題一1、建立優(yōu)化模型應考慮哪些要素？答：決策變量、目標函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準則。nuii/（x）答：針對一般優(yōu)化模型M gj（x）nO,j = l,2,.m 討論解的可行域D,若存在一點l（x） = OJ = l,.,pX上D,對于VXeD均有則稱X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列X,X（2）,X.，滿足 則迭代法收斂；收斂的停止準則有|卅+_卅|10s.t. 18兒兒，兒0*2、研究線性規(guī)劃的對偶理論和方法（包括對偶規(guī)劃模型形式、對偶理論和對偶單 純形法）。答：略。1百度

2、文庫讓每個人平尊地提升自我3、用單純形法求解下列線性規(guī)劃問題:111U1 z = X _ + 兀3X + %2 2*3 22刁 + x2 +0解：(1 )引入松弛變量X4，兀5，X65/mill z = 4 - x2 + “3- 2x2 + 牙3%2 2%3 + *4x2 + X3 + x5=2=2=5x,-0 (心 1,2,5)3niin z =召_兀 +兀+ 0 *兀 + 0 *乞+ 0 *為兀 + x2 - 2 + x2兀+x2 +迅-xl + x34=2+ x5=3+ x6=4CL111000Cb基hAlA2A3X4A5A60X4211-21000X532110100X64-10100

3、1cz111000因檢驗數(shù)。20,表明己求得最優(yōu)解：X* = (0,8/3,l/3,0,0,ll/3),去除添加的松弛變 量，原問題的最優(yōu)解為：X* = (0,8/3,1。(2)根據(jù)題意選取X1，汕，X5，為基變量：nun Z = 4 七 + 兀3X 2*2 + *3= 2%2 一 2%3 + 兀4 =2S.tAx2 + x3 + x5 = 5Xj 0 (j = 12,5)CL01100Cb基bAlX2A3X4X50xi2121000X4201-2100X550110101100因檢驗數(shù)。20最小，故確定X2為換入非基變量，以X2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量汕作為

4、換出的基變量。CL01100Cb基bAl-V2A3X4-V50Xi610320-1A2201-2100X53003100110因檢驗數(shù)。30,表明已求得最優(yōu)解：%* = (9,4丄0,0)。4、分別用大M法、兩階段法和Matlab軟件求解下列線性規(guī)劃問題：niin z = 4心 + x2max z = 10xx + 15x2 + 12x33xl + 七=35.vj + 3x2 + 兀3 S 9(1) E9心 + 3x2 6 .皿一 5.X + 6x2 + 15x3 15X + 2x2 5X ,x2 0xx2,x5 0解：（1）大M法根據(jù)題意約束條件1和2可以合并為1,引入松弛變量X3,汕，構(gòu)造

5、新問題。niiii z=4xx +x2+Mx3 +0*x43xk + x2 + x3= 3s.t. 0CL41M0Cb基b-Vi.V2X4MX3331100X431201Cj-Zf4-3M1-M004XI111/31/300X4205/3-1/31CjV0-1/3M 4304Xl3/5102/5-1/51Xi6/501-1/53/5Cj-Zi00M-7/51/5因檢驗數(shù)50,表明己求得最優(yōu)解：X4= (3/5,6/5) oMatlab調(diào)用代碼：H4；l；A=-9,-3;l,2;b=-6;3;Aeq=3,l;beq=3;lb=O;O;xfval = linpiog(f A,b,Aeq,beqJb

6、)輸出結(jié)果：百度文庫-讓毎個人平尊地提升門我Optimization temunated.x =fval =(2)大M法引入松弛變量X5, X6, X7構(gòu)造新問題。max z = 10人 + 15x2 + 12兀 + 0兀 + 0x5 + 0x6 一 Mx15xl + 3x2 + x4=9-35#=15-a6 + x7 = 5-5a; + 6乙 +1 5x3 + x52兀+ & +兀占,，馮0單純形表計算略；當所有非基變量為負數(shù)，人工變量心=,所以原問題無可行解。請同學們自己求解。Matlab調(diào)用代碼：H-10;-15;-12;A=5,3,l；-5,6,15;-2,-l,-l;b=9;15;-

7、5;lb=0;0;0;x = linprog(f,A,b,lb)輸出結(jié)果：無可行解。5、用內(nèi)點法和Matlab軟件求解下列線性規(guī)劃問題:mui z = 2勺 + x2 + X3s.t.0解：用內(nèi)點法的過程自己書寫，參考答案：最優(yōu)解X=4/3 7/3 0；最優(yōu)值5Matlab調(diào)用代碼：Aeq=l,2、2;2 丄 0;beq=6;5;lb=0;0;0;x,fval = linpiog(f , , Aeq, beq Jb) 輸出結(jié)果：Optimization temunated fval =6、用分支定界法求解下列問題:(1)max z = 5xj + 8x2xy + X2 5 65x + 9牙2

8、S 45?1,%20且均為整數(shù)(2)max z = 7“ + 9x2一 X + 3x2 67x + x2 35/i, x2為整數(shù)解：(1)調(diào)用matlab編譯程序bbmethod f=-5;-8;G=l1;5 9;h=6; 45x,y=bbmethod(f,Gh,J0;0Ql;l,l)33v =-39最優(yōu)解3 3；最優(yōu)值39(2)調(diào)用matlab編譯程序bbmethod f=-7; -9;G=-13; 7l;h=6; 35x,y=bbmethod(f,G,h,0 ；0,l;0,l)百度文庫讓毎個人平等地提升自我最優(yōu)解5 0；最優(yōu)值357、用隱枚舉法和Matlab軟件求解下列問題: b 0) (

9、b b 1)分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是(0, 0, 1),(1)解:(1)mill z = 4刁 + 3x2 + 2x3 2丫1 -52 + 3*3 4 4“ + 勺 + 3*3 X 3s.t.；+ 兀3 n 1X j = 0或1U = 1,2,3)隱枚舉法:將(0, 0, 0) (0, 0, 1)(2)(0,max z = 3“ + 2x2 一 一 2x4 + 3x5X + 勺 + 2% + x5 47Xj + 3*3 4兀4 + 3兀5 5 81 lxj 6*2+ 3a*4 3%5 1廠=0或1() = 1,2,5)s.t. As，甲、乙、丙、丁四個產(chǎn)糧區(qū)為Bi、B2

10、、B3、B4; Gj為由A】運化肥至Bj的運價，單位是元/噸；殉為由A】運往Ej的化肥數(shù)量(i=l,2,3;j=l,2,3,4)單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學模型為:34mmz =工工r=l y=l11+1+1 =6X12 + x22 + x32 = 6x13 + x23 + x33 = 3x14 + x24 += 3xn + xI2 + x13 + x14 = 7x21 + x22 + 耳 3 + x24 = 8x31 + x32 + x33 + x34 = 7該題可以用單純形法或matlab自帶工具箱命令(linprog)求解。*9、求解下列不平衡運輸問題(各數(shù)據(jù)表中，

11、方框內(nèi)的數(shù)字為單位價格印，框外右 側(cè)的一列數(shù)為各發(fā)點的供應量的，框底下一行數(shù)是各收點的需求量巧)：10要求收點3的需求必須正好滿足。801520101515要求收點1的需求必須由發(fā)點4供應。75 20 50解答略。10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng) 驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-29所示。公 司經(jīng)理應怎樣分派才使總利潤最大？表2 2區(qū)1234135272837228342940335243233424322528解：用求極大值的“匈牙利法”求解。 效率矩陣表示為：9百度文庫-讓毎個人平等地提升門我（2106(0)、，2

12、10901 *126110列約簡rK12680011321 (0)11(T2標號 8074/8(0)44丿/所畫（）0元素少于n3528353, 42此時總利潤W=35十40+32+32=139練習題三1、用法求解問題min 0(/) = 一2f + lr0的近似最優(yōu)解，己知0(/)的單谷區(qū)間為0,3,要求最后區(qū)間精度0 = 0.5。答：t=；最小值.(調(diào)用函數(shù))2、求無約束非線性規(guī)劃問題nun /(X,兀,X3) = xi + Xj 一 2兀的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：=2.-2 , = Sx, = 2x3,則由 Vf(x) = 0得兀=1, x,=0, x3 = 0 dx

13、Ldx2dx3再用充分條件進行檢驗: 空=2, 4 = 8,空=2,也=0,空=0,空=0dxdx; 說 dxfix2 dxfix5 dx2dx52 0 0、即V7= 0 8 0為正定矩陣得極小點為x* = (l,0,0)T,最優(yōu)值為-1。0 0 2 /解二：目標函數(shù)改寫成nun f(xl,x2,xi)=3 -1)，+ x； -1易知最優(yōu)解為(1Q0),最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。ni f(X ) = x-x2 + 2x + 2xlx2 + x；其中X=(x“2)，給定初始點% = (0,0)解一：目標函數(shù)于(x)的梯度W(x) =茅(列|_迤)1 + 4兀 + 2

14、x2一1 + 2兀+ 2兀 1-1(X)=令搜索方向d= _Y/(x)=再從X出發(fā)，沿d方向作一維尋11優(yōu)，令步長變量為幾，最優(yōu)步長為血，則有x+加故 /(x) = /(X + /Id )=(-2)-2 + 2(-2)2 + 2(-2)2 + 2,=幾 一2幾=% (2)0 -1 -1令0(刃=2久一2 = 0可得人=1 X= X+d= + = 求出X點之后, _11與上類似地，進行第二次迭代：v/(x(1)= 令J(2)=-V/(X(1)= 11令步長變量為幾,最優(yōu)步長為人，則有-f1 + - 1-0.81511.2W(x)=0.2-0.2此時所達到的精度岡(X)卜0.28281-1+ 21

15、2-1112 + 1X+3 =/(x) = /(X +2d)=(2 1) 一(2 + 1) + 2(幾一1)2 + 2(2 -1)(2 +1) + (2 +1)2 = 522 -22-1 =輕(2)令(刃=10兄_2 = 0可得 入=X(2) = Xw+A2d(2) =本題最優(yōu)解=解二：利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=fiin(x)f=x( 1 )-x(2)十 2 *x( l)*x( 1)+2 *x(l) *x(2)十 x(2) *x(2); function g=gfiin(x)g=l+4*x(l)+2*x(2),-l+2*x(l) +2*

16、x(2);調(diào)用文件x0=0,0;x,val,k=giad(,fun,gftin,xO)結(jié)果X= Jval=k=33即迭代33次的到最優(yōu)解x=,：最優(yōu)值val= o4、試用Newton法求解第3題。解一：計算目標函數(shù)的梯度和Hesse陣目標函數(shù)/(切的梯度V/ (x) =茅(x)|_怒)l + 4xl + 2x2-1 + 2x1 + 2x2V2/(%) =2 4其逆矩陣為b0.5-0.51X=X_G7Vf(X)=0,07 -0.5-0.5= _U瑋本題最優(yōu)解X*=, /(Xj = -1,251.5解二：除了第3題建立兩個M文件外，還需建立Hesse矩陣的M文件 利用matlab程序求解首先建立目

17、標函數(shù)及其梯度函數(shù)的M文件fiuiction f=ftin(x)f=x( 1 )-x(2)十 2 *x( l)*x( 1)+2 *x(l) *x(2)十 x(2) *x(2);fiinction g=gfun(x)g=l+4*x(l)+2*x(2),-l+2*x(l) +2* x(2);fiinction h=hess(x)g=4 2;2 2;調(diào)用文件x0=0,0;x,val,k=newton(ftmTgfimThess/0)結(jié)果X=,val=k=l5、用Fletcher一Reeves法求解問題niii f(X)=對 + 25x；其中X = U，x2)r ,要求選取初始點X0 = (2,2)r

18、 = 106 o解一： 1 2 0 - 2 0 。 T /(x) = _(x &), G=, r = Vf(x) = (2x ,50-r,).八 20 50 乙0 501-J L. JL第一次迭代:令po = - = (-4,-100)r,4t(4J00)100_ 1P7Gp (-4,-100)20_-4 _50050-100即，x = x + aopo = (1.92,0/第二次迭代:肚殊=爲PF + 恥心.叫5(3.84,0)T84020-3.846(-3.846,-0.15)050-0.15=0.4802= ，lXUJ = XU) + 4 p = (0.0732,-0.072/第三次迭代

19、：/; =(0.1464,-3.6/(建議同學們自己做下去，注意判別阪卜)解二：利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=ftin(x)fx(l)A2+25* x(2)*x(2);fiuiction g=gfiin(x)g=2*x(l), 50* x;調(diào)用文件x0=2;epsilon= 1 e-6;x,val,k=ficg(,fiin,gfiinxO, epsilon)結(jié)果X= *,val =k = 616、試用外點法(二次罰函數(shù)方法)求解非線性規(guī)劃問題min f(X) =- 2尸 + X：s.t. g(X) = x2 -1 0其中 X =(xpx2)e

20、 R2解：設計罰函數(shù) P(x,M) = /(X) + M*g(X)人 2釆用Matlab編程計算，結(jié)果x=10；最優(yōu)結(jié)果為1。(調(diào)用)7、用內(nèi)點法(內(nèi)點障礙罰函數(shù)法)求解非線性規(guī)劃問題:min (再 +1)3 + x2s.t. -1 0解：容易看出此問題最優(yōu)解為x=l 0；最優(yōu)值為& 給出罰函數(shù)為 F(x, r) = (y +1)3 +兀+廠(1/(召-1) + 1/兀)從而當時，x(r)=(1 +心(建議同學自己編程序計算)8、用乘子法求解下列問題解：建立乘子法的增廣目標函數(shù):百度文庫-讓毎個人平等地提升門我(a2,cf) = x； +x； -2(xx +x2 -2)+ y (a + x2

21、一2)人2令：空竺竺2 = 2坷一久+ 7(並+凡一 2) = 06 以。)=2工+ 0解：X = 9以2 = 9,3 = 9 ,最優(yōu)值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃max z = 7x; + 6xx +si.兀 + 2耳510Xi 3 兀2 5 90解：用順序算法階段：分成兩個階段，且階段1、2分別對應心疋。決策變量：兀,耳狀態(tài)變量：,w,分別為第丿階段第一、第二約束條件可供分配的右段數(shù)值。f：（叫,wj = max 7x + 6. = nun7v; + 6v, 7 w； + 6叫 x* = minv1,vv1 f；（y2，叫）=max5%2 + f；（y2 - 2x2，叫 + 3耳

22、）max5x + min7（冬一 2xJ + 6（冬一 2xJ,7（叫 +3xJ + 6（% + 3耳）由于冬=10,w2 =9 ,f； （wJ = f； （10,9） = niaxniui33x - 292x2 + 760,68x； + 396x2 + 621可解的Xj = 9.6, x2 = 0.2 ,最優(yōu)值為。4、設四個城市之間的公路網(wǎng)如圖47。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應的最短距離。圖4- 2城市公路網(wǎng)解：城市1到城市4路線一一1-3-4距離10；城市2到城市4路線一一2-4距離8；城市3到城市4路線一一3-4距離4。5、某公司打算在3個不

23、同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地 區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表4-19所示。試問在各地區(qū)如何設置銷 售點可使每月總利潤最大。表4- 1地 區(qū)銷售點01234123016253032012172122010141617解：將問題分為3個階段，k=, 2, 3；決策變量q表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù);狀態(tài)轉(zhuǎn)移方程：sk+l=skxkf其中$1=4； 允許決策集合:Dk (嘆)=q|0WqWsQ階段指標函數(shù)：gk (q)表示q個銷售點分配給第R個地區(qū)所獲得的利潤;最優(yōu)指標函數(shù)人(嘆)表示將數(shù)量為sk的銷售點分配

24、給第k個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為：fk ()=嚴 X gk (x,) + fksk-xk)k = 3.2,1/(為)=0R=3 時，/；(53) = niax(x3)&3 (兀3)厶（$3）012340000110101214142316163417174k=2 時，人(幾)=maxgr(&) +厶一xj0A：5：*&2（兀2）耳（$2 一兀2）fl（S2） 兀201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312,3日時仏）=懿諒3）+從-和，伽）

25、=帶g） +厶（4-和&191）憶（耳一叼）恥）0123440+3116+2725+2230+1232+()472最優(yōu)解為：x=2, x2*=l, x3*=l, f=47,即在第1個地區(qū)設置2個銷售點，第2個 地區(qū)設置1個銷售點，第3個地區(qū)設置1個銷售點，每月可獲利潤47。6、設某廠計劃全年生產(chǎn)某種產(chǎn)品Ac其四個季度的訂貨量分別為600公斤，700 公斤，500公斤和1200公斤。己知生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品的平方成正比，系數(shù) 為。廠內(nèi)有倉庫可存放產(chǎn)品，存儲費為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個季度為四個階段，釆用階段編號與季度順序一致。設Sk為第R季初的庫存量，則邊

26、界條件為5!=55=0設Xk為第R季的生產(chǎn)量，設yk為第k季的訂貨量；sk , M , yk都取實數(shù)，狀 態(tài)轉(zhuǎn)移方程為sk+i=sk+xk-yk仍采用反向遞推，但注意階段編號是正向的目標函數(shù)為:4fx） = niin V （0.005x; + ）第一步：（第四季度）總效果 九（$4山4）=2十由邊界條件有：巧=$4十4-4=，解得：A4*=1200 -54將*代入A（544）得：/k*（A4）=（1200 _ $4）2十$4=7200 -11 * 十第二步：（第三、四季度）總效果總與力戶勺?七3十九*（*）將*=S3十與- 500代入力（$3心）得：厶（53 ,x3） = 0.005Xj +

27、耳 + 7200 - ll（x3 + $3 - 500）+0005（兀 + $3 500）=0.01 + 001兀耳 一I6X3 + 0005s； -15耳 + 13950弘,W）= 002% +0.015,-16 = 0解得 X； = 800-0.553,代入/；（歸，禺）得人（耳）=7550-7%+0.0025尺第三步：（第二、三、四季度）總效果/2（522）=芒?十 $2 十力 *G3）將 $3= $2 十 -700 代入 72（52?x2）得：f2(s2,x2) = 0005x； + t + 7550-7(兀 + s2 -700) 4-0.0025(%, + s2- 700)爼= 0.

28、015x, + 0.005(5. -700)-7 = 0dx2解得x： = 700-(1/3)5,代入人忑)得j；(52) = 10000 - 6s2 + (0.005/3) $；第四步：(第一、二、三、四季度)總效果/1（$1）=門2十兒十力*（32）將 $2=$1 十勺 一 600=X - 600 代入 /（$“）得: / G,召)=0.005x; + S +10000 一 6(壬 一 600)+(0005/3)(為 一 600)dxt=(0.04/3)兀 8 = 0解得 = 600,代入A G眄）得 /；(52) = 11800由此回溯：得最優(yōu)生產(chǎn)-庫存方案X|*=600,$2*=0；兀

29、2*=700,$3*=。；x=S009S4*=300：x=900o7、某種機器可在高低兩種不同的負荷下進行生產(chǎn)。設機器在高負荷下生產(chǎn)的產(chǎn)量 函數(shù)為g=8山，其中為投入生產(chǎn)的機器數(shù)量，年完好率。=；在低負荷下生產(chǎn)的產(chǎn)量函 數(shù)為h=5yf其中y為投入生產(chǎn)的機器數(shù)量，年完好率為b=。假定開始生產(chǎn)時完好機器 的數(shù)量小=1000。試問每年如何安排機器在高、低負荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn) 品總產(chǎn)量最高。解：構(gòu)造這個問題的動態(tài)規(guī)劃模型：設階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機器數(shù)量，同時也是第k-1年度末時的完好機器 數(shù)量。決策變量uk為第k年度中分配高負荷下生產(chǎn)的機器數(shù)量，于是sk-

30、uk為該年度中分配在低負荷下生產(chǎn)的機器數(shù)量。這里Sk和l】k均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如Sk=，就表示一臺機器 在k年度中正常工作時間只占6/10： i】k=，就表示一臺機器在該年度只有3/10的時間能 在高負荷下工作。狀態(tài)轉(zhuǎn)移方程為：+ = auk + b(sk-uk) = 0.7似 + 0.9($& -uk), R = 1,2,5k段允許決策集合為：9() = 坯|0冷sk設嘰耳，你)為第k年度的產(chǎn)量,則* =8姝+5(-境)故指標函數(shù)為：匕5 =工弘(耳，11 k)令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆

31、推關(guān)系式：fe ($6)= 251,2,3,4,5從第5年度開始，向前逆推計算。當k二5時，有：max 8“5 + 5（ -5） + f6 。二心 + 0.9（$=max0m5j5厶($5)=遼因f5是丐的線性單調(diào)增函數(shù),故得最大解吒*,相應的有:當24時，有: 百度文庫-讓每個人平等地提升自我故得最大解，U4*=S4，相應的有（$斗）=13.6 為依此類推，可求得“； = %,相應的 fs.） = 17.5s. ul = 0,相應的人G） = 20.8屯； = 0,相應的仏）=23.7以因 S=1000,故：AG） = 23700計算結(jié)果表明：最優(yōu)策略為；=0,2 = 0,3 = 53,W*

32、 = 54,tt* = $5即前兩年應把年初全部完好機器投入低負荷生產(chǎn)，后三年應把年初全部完好機器投入高負荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即 從始端向終端遞推計算出每年年初完好機器數(shù)。己知sr1000臺，于是可得：s2 = 0.7 h： + 0.9（ - ”：）= 0.9幾=900（臺）53 = 0.7； + 0.2（4 - “；）= 09歸=810（臺）s4 = 0.7”； + 0.9（$3 - ”；）= 0.7昌=567（臺）s5 = 0.7”： + 0.9（54 -*） = 0.7$4 = 3

33、97（臺）s6 = 0.7”； + 0.9（55 -/*） = 0.755 = 278（臺）8、有一輛最大貨運量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應單位價值如表4-20所示。應如何裝載可使總價值最大？表4一 2貨物編號1123單位重量（t）345單位價值C1456解：建模設三種物品各裝”吃,禺件max（4“q + 5耳 + 6兀）3 兀+ 4冷+53 0,x. g /,j = 1,2,3 J丿利用動態(tài)規(guī)劃的逆序解法求此問題。51=C,P1（51） = X1|O%1 5耳=sl-xl,D2（s2） = x2 |0X2 52狀態(tài)轉(zhuǎn)移方程為:耳=一心2（$3）= 心1禺 （52

34、）= max 5兀+厶（sJ忑=0丄吟】=max 5x2 + 厶（$三 _ 4xz） 七=0,芋k = l,仏）=max 4x1 + /2（52）=04,2,3=max 4a; + ZG _ 3xJ=0,1,2,3計算最終結(jié)果為x： = 2,x； = l,x； = 0,最大價值為13 o9、設有A, B, C三部機器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn) 次品。統(tǒng)計結(jié)果表明，機器A, B, C產(chǎn)生次品的概率分別為a=30%, Pb=40%, Pc=20%, 而產(chǎn)品必須經(jīng)過三部機器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬 元進行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標?，F(xiàn)

35、提出如下四種改進方案：方案1：不撥款，機器保持原狀；方案2：加裝監(jiān)視設備，每部機器需款1萬元;方案3：加裝設備，每部機器需款2萬元；方案4：同時加裝監(jiān)視及控制設備，每部機器需款3萬元;采用各方案后，各部機器的次品率如表4-2lo表4一 3AEC不撥款30%40%20%撥款1萬元20%30%10%撥款2萬元10%20%10%撥款3萬元5%10%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺機器分配改造撥款，設撥款順序為A, B,C,階段序號反向編號為即第一 階段計算給機器C撥款的效果。設為第k階段剩余款，則邊界條件為53=5;設M為第k階段的撥款額；狀態(tài)轉(zhuǎn)移方程為SkJ=Sk-Xk；目

36、標函數(shù)為 max /?=( 1 -PA)( 1 -Pg)( 1 -Pq)仍采用反向遞推第一階段：對機器C撥款的效果心(21)=1(1 /?o(go)=心(1)XS10123X1*Ri（51, ATi*）001121,2334353第二階段：對機器B,C撥款的效果由于機器A最多只需3萬元，故 2遞推公式：/?2(2)=2(42” 心(1*)例：/?2(3,2)=J2(3,2)x/?!(!,!)= x=得第二階段最優(yōu)決策表X1*/?!產(chǎn)）001121,2334353X$20123X2*R2($2, ”)2232,34353第三階段:對機器A.B.C撥款的效果邊界條件：53 = 5遞推公式：/?33

37、仏3）=“3（$3丿3勺（丿2*）例：/?3（5,3）=d3（5,3）x 尺2（2,2）= x=得第三階段最優(yōu)決策表$2Ri（仏”2來）29百度文庫-讓毎個人平等地提升門我I：勺=1，兀2=3/=1、/?3= x x=II：勺=2, 2=2, X|=l, /?3= xx=III： 勺=2, 2=3, X|=0,/?3= xx=31百度文庫-讓毎個人平尊地提升門我練習題五1、考察多目標規(guī)劃問題-x+2, - 2 x 1其中fM = xf2（x）= t 1，ix 2心心心，心“，心，這里K是nun fM的最優(yōu)解集。解：2、用線性加權(quán)法中的法求解下述多目標規(guī)劃問題 niiii /(X)= 4兀 +

38、6x2 max f2 (x) = 3xa + 3x2。2石 + 4x2 14 5/J 6a; + 3x2 0解:min(x) = 4為+ 6*2 最優(yōu)解為 x(1)=0 0T；max/；(x) = 3x1 + 3x2 最優(yōu)解為 x(2)=3 2T；利用&法得線性方程組：Z * 0 + 人 * 0 = Q 2/24-*15 = 67 人+入=1解得唯一加權(quán)系數(shù)久=3846、0.6154丁原多目標規(guī)劃加權(quán)后min F(x) = 0.3846/j (x) - 0.6154 f2 (x)解得加權(quán)后的最優(yōu)解為：x*=4 0T,最優(yōu)值為3、用線性加權(quán)求和法求解下述多目標規(guī)劃問題，取人=06人= 0.4。v

39、 - mill F(x) =( - 3x2,+ x2)T3為 + 2xz 6A + 3x 3s.t.2兀0解：將問題轉(zhuǎn)化為一個新的單目標規(guī)劃問題。niin v(F(x) = 06(兀 一 3xJ + 0.4(2xx + x2)約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab 命令求解(求解過程略)。解得加權(quán)后的最優(yōu)解為：x*=0 1T ,最優(yōu)值為。4、用平方和加權(quán)法求解多目標規(guī)劃問題：v 一卿(乞()，久(刃)7x -X. 4 1 ?其中/；(a) = xp/,(a) = x, , D: 0解：不難看出兩個目標函數(shù)下界均為0,得平方和加權(quán)法后的新目標規(guī)劃問題: nun F(x) = -x + -xxl-x2 4:x, + x: 0利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件fiuiction f=fini(x)Ql/3*x(l)人2十2/3* x(2)*x(2);x,fval=fiuincon(f0 0,1 -1;1 1,4;8,0 0)解得最優(yōu)解為：x*=0 0T ,最優(yōu)值為0。5、用極小極大法和Matlab軟件求解下述多目標規(guī)劃問題v - nun F (x)=(召 _ 3) + x；, f + (x? 2) )丁os.t. x + x2