最優(yōu)化方法練習(xí)題答案修改建議版本--刪減版

1、X(k1)x(k)x(k1 x(k)|x(k)|x(k1)x(k)f x(k fx(k)f x(k)x(k)練習(xí)題一1、建立優(yōu)化模型應(yīng)考慮哪些要素？答：決策變量、目標(biāo)函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)那么。min f(x)答：針對(duì)一般優(yōu)化模型s.t gi x 0,i 1,2,m，討論解的可行域D，假設(shè)存在一點(diǎn)X* D，hj x 0, j 1,，p對(duì)于X D均有f(X*) f(X)那么稱(chēng)X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭f(X(K)，那么迭代法收斂；收斂的停止準(zhǔn)那么有代所得到的序列X,X，,X(K)，滿足f(X(K1)等。練習(xí)題二1、某

2、公司看中了例中廠家所擁有的3種資源R1、R2、和R3,欲出價(jià)收購(gòu)可能用于生產(chǎn)附加值 更高的產(chǎn)品。如果你是該公司的決策者，對(duì)這 3種資源的收購(gòu)報(bào)價(jià)是多少？該問(wèn)題稱(chēng)為例的對(duì)偶 問(wèn)題。解：確定決策變量對(duì)3種資源報(bào)價(jià)2匚3作為本問(wèn)題的決策變量。確定目標(biāo)函數(shù)問(wèn)題的目標(biāo)很清楚一一“收購(gòu)價(jià)最小。確定約束條件資源的報(bào)價(jià)至少應(yīng)該咼于原生產(chǎn)產(chǎn)品的利潤(rùn)，這樣原廠家才可能賣(mài)。因此有如下線性規(guī)劃問(wèn)題：min w 170y1 100y2 150y35y1 2y2 y310s.t 2y1 3y2 5y3 18y1, y2, y302、研究線性規(guī)劃的對(duì)偶理論和方法包括對(duì)偶規(guī)劃模型形式、對(duì)偶理論和對(duì)偶單純形法 答：略。3、用單

3、純形法求解以下線性規(guī)劃問(wèn)題：minzx1x2x3minz 4 x2X3x1x22x32X2X2X321s.t.2x1 x2x33 ；2s.t.x2 2x3X42x1x34x2 X3x55X1,X2,X30Xi 0 (i1,2,5)解：1引入松弛變量X4，X5，X6min z x1 x2 x3 0* x4 0* x5 0* x6x1 x2 2x3 x4=2丄2x1X2X3x5=3s.tx1 x3x6=4x1,x2, x3,x4,x5,x6 0Cj1-11000Cb基bX1X2X3X4X5X60X4211-21000X532110100X64-101001Cj-zj1-11000因檢驗(yàn)數(shù)020，故

4、確定X2為換入非基變量，以X2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值 所在行對(duì)應(yīng)的基變量X4作為換出的基變量。Cj1-11000Cb基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-zj20-1100因檢驗(yàn)數(shù)03Q,說(shuō)明已求得最優(yōu)解：X*(0,8/ 3,1/3,0,0,11/ 3)，去除添加的松弛變量，原問(wèn)題的最優(yōu)解為：X (0,8/3,1/3)2根據(jù)題意選取X1,X4，X5，為基變量:min z 4 X2X3x3X4X12x2x22x3st. 23x2x3Xi0 (i1,2,x5,5)Cj -1Cb基bX1X2X3X4X50X121-21

5、000X4201-2100X5501101cj-z0-1100因檢驗(yàn)數(shù)020,說(shuō)明已求得最優(yōu)解：X* (9,4,1,0,0)8、某地區(qū)有A、B、C三個(gè)化肥廠，供應(yīng)本地甲、乙、丙、丁四個(gè)產(chǎn)糧區(qū)。各化肥廠可供應(yīng) 化肥的數(shù)量和各產(chǎn)糧區(qū)對(duì)化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價(jià)如表2-28所示。試制定個(gè)使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。運(yùn)價(jià)/ 產(chǎn)糧化肥廠甲乙丙丁各廠供應(yīng)量/萬(wàn)噸A158737A2491078A384293各區(qū)需要量/萬(wàn)噸6633解：設(shè)A、B、C三個(gè)化肥廠為Ai、A2、A3,甲、乙、丙、丁四個(gè)產(chǎn)糧區(qū)為Bi、B2、B3、B4；cij為由Ai運(yùn)化肥至Bj的運(yùn)價(jià)，單位是元/噸；xij為由Ai運(yùn)往B

6、j的化肥數(shù)量i=1,2,3;j=1,2,3,4單位是噸；z表示總運(yùn)費(fèi)，單位為元，依題意問(wèn)題的數(shù)學(xué)模型為:34minzi1 j 1cijxijX11X21X316X12X22X326X13X23X333s.tx14X24X343X11X12X13X147X21X22X23X248X31X32X33X347該題可以用單純形法或 matlab自帶工具箱命令:linprog求解。9、求解以下不平衡運(yùn)輸問(wèn)題各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價(jià)格q,框外右側(cè)的一列數(shù)為各發(fā)點(diǎn)的供應(yīng)量ai，框底下一行數(shù)是各收點(diǎn)的需求量bj：108015要求收點(diǎn)3的需求必須正好滿足75 20 5020101515要求收點(diǎn)1的需求必

7、須由發(fā)點(diǎn)4供應(yīng)解答略練習(xí)題三1min (t) t3 2t 1 t 0的近似最優(yōu)解，(t)的單谷區(qū)間為0,3，要求最后區(qū)間精度 0.5答：t=0.8115;最小值-0.0886.調(diào)用 golds.m 函數(shù)2、求無(wú)約束非線性規(guī)劃問(wèn)題的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點(diǎn)：2x-i2，丄8x2，丄2x3，那么由 f x0 得 x-i1 ,x20,x30XixX3再用充分條件進(jìn)行檢驗(yàn)：2 2 2 2 2 2f 2，厶f28，f cf cf牙 2，0，-0，f 0X1X2x3x1x-! x3X2X3200即2f080為正定矩陣得極小點(diǎn)為X*(1,0,0)T，最優(yōu)值為-1002解二：目標(biāo)函數(shù)改寫(xiě)成2

8、 2 2min f (Xi,X2X)= (Xi 1)4x? X3 1易知最優(yōu)解為1,0,0最優(yōu)值為-13、用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題。2 2 min f(X) x1 x2 2X 2x-|X2 x2其中X (X1,X2)T，給定初始點(diǎn)X0(0,0)T。1 4x1 2x21 2x1 2x2f(x)解一：目標(biāo)函數(shù)f (x)的梯度f(wàn)(x)(X1)f (x)(X2)f(X(0)1令搜索方向d1f (X(0)再?gòu)腦(0)出發(fā)，沿d方向作一維尋優(yōu)，令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為那么有X(0)故 f (x) f (X (0)d)2( )22(1()令 1( )220可得X(1) x(0)1d(1)求出X點(diǎn)

9、之后，與上類(lèi)似地,進(jìn)行第二次迭代:f(X)11 令 d(2)1f(X)令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為2，那么有x(1)d(2)1 1 11 1 1故f(x)f(X d )(1)(1) 2(1)22()1012 0可得 2- XX(1)2d(2)52(1)(1) (1)2 5 2 212()令1 1 1 0.815 11.20 2f(X(2)02此時(shí)所到達(dá)的精度f(wàn) (X )|0.28281此題最優(yōu)解X, f(X )1,251.5練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問(wèn)題：考察網(wǎng)絡(luò)圖4-6,設(shè)A為出發(fā)地，F(xiàn)為目的地，B,C, D，E分別為四個(gè)必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置，

10、線段旁的數(shù) 字表示鋪設(shè)這些管線所需的費(fèi)用。問(wèn)如何鋪設(shè)管道才能使總費(fèi)用最?。繄D4-1解：第五階段:E1 F 4;E2 F:3；第四階段:D1 E1 F7; D2 E2 F 5;D3E1 F 5;第三階段:C1 D1 E1F 12;C2D2 E2 F 10; C3 D2 E2第二階段:B1 C2 D2E2 F13; B2C3 D2 E2 F 15;第一階段:AB1 C2 -D2 E2-F 17;最優(yōu)解：AB1C2 D2 E2 F最優(yōu)值：17F 8； C4 D3 E1 F2、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃9；maxf(x) . X| , x2x3x1 x2 x327X1,X2,X30解：x-i 9,x

11、2 9, x3 9，最優(yōu)值為 9。3、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃2 2 max z 7x1 6x 5x2s.t x-i 2x210x-i 3x29x1, x20解：用順序算法階段：分成兩個(gè)階段，且階段1、2分別對(duì)應(yīng)Xi,X2。決策變量:Xi,X2狀態(tài)變量:Vi, Wj分別為第j階段第一、第二約束條件可供分配的右段數(shù)值。fl (Vi, Wi)。啊7 X0 x( W1min7 v； 6V| ,7 w 6w1x-imi nZw*2f2(v2,w2) max5 x22x2,w2 3x2)max5 x；由于 v210, w29，22min7( v2 2x2)6(v2 2x2),7( w2 3x2)6(

12、w2 3x2)* * 2 2f2 (v2, w2) f2 (10,9) maxmin33 x2 292x2 760,68 x2 396x2 621可解的X1 9.6, x； 0.2，最優(yōu)值為702.92。4、設(shè)四個(gè)城市之間的公路網(wǎng)如圖4-7。兩點(diǎn)連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。圖4- 2城市公路網(wǎng)解：城市1到城市4路線1-3-4 距離10；城市2到城市4路線2-4距離8;城市3到城市4路線3-4 距離4。5、某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售點(diǎn)每月可得到的利潤(rùn)如表 4-19所示。試問(wèn)在各地區(qū)

13、如何設(shè)置銷(xiāo)售點(diǎn)可使每月總利潤(rùn)最大。表4-1地銷(xiāo)售點(diǎn)區(qū)01234101625303220121721223010141617解：將問(wèn)題分為3個(gè)階段，k=1 , 2, 3;決策變量xk表示分配給第k個(gè)地區(qū)的銷(xiāo)售點(diǎn)數(shù)；狀態(tài)變量為Sk表示分配給第k個(gè)至第3個(gè)地區(qū)的銷(xiāo)售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：劭+1=孤乂丘，其中s=4;允許決策集合：DkSk= Xk|0S3S2X2, D3(s3) X3 1 0X3Ss狀態(tài)轉(zhuǎn)移方程為：Sk 1 Tk(Sk,Xk) Sk xk,k3,2,1該題是三階段決策過(guò)程，故可假想存在第四個(gè)階段，而 x4 0，于是動(dòng)態(tài)規(guī)劃的根本方程為:fk(Sk) XkmaxJseMk 咖f4() 0

14、k 3,f3(S3)max6x3X3 0,1, ,S3/5k 2,f2(S2)max 5x2X 0,1,邑4f3(S3)max 5x2X2 0,1,吟f3(S24X2)k 1,MG 頁(yè)ax戶(hù) f2(s2)max34 fzg 3xjx1 U,l，2,3計(jì)算最終結(jié)果為Xi 2,X2 1,X3 0，最大價(jià)值為13。9、設(shè)有A，B，C三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問(wèn)題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計(jì)結(jié) 果說(shuō)明，機(jī)器 A，B，C產(chǎn)生次品的概率分別為 Pa=30%, Pb=40%, Pc=20%,而產(chǎn)品必須經(jīng)過(guò)三部機(jī) 器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬(wàn)元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)

15、品的成品率指標(biāo)?，F(xiàn)提出如下四種改進(jìn)方案：方案1:不撥款，機(jī)器保持原狀；方案2:加裝監(jiān)視設(shè)備，每部機(jī)器需款 1萬(wàn)元；方案3:加裝設(shè)備，每部機(jī)器需款 2萬(wàn)元；方案4:同時(shí)加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款 3萬(wàn)元；采用各方案后，各部機(jī)器的次品率如表 4-21。表4- 3ABC不撥款30%40%20%撥款1萬(wàn)元20%30%10%撥款2萬(wàn)元10%20%10%撥款3萬(wàn)元5%10%6%問(wèn)如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺(tái)機(jī)器分配改造撥款，設(shè)撥款順序?yàn)?A, B, C,階段序號(hào)反向編號(hào)為k,即第一階段計(jì)算給 機(jī)器C撥款的效果。設(shè)永為第k階段剩余款，那么邊界條件為 s3=5；設(shè)x為第k階段的撥款

16、額；狀態(tài)轉(zhuǎn)移方程為 Sk-1=Sk-Xk；目標(biāo)函數(shù)為max R=(1-Pa)(1-Pb)(1-Pc)仍采用反向遞推第一階段：對(duì)機(jī)器C撥款的效果Rl(si，x0=d i(si ,xi)Ro(S0,X0)= d*si，xi)S10123X1*R1(S1, X1*)001121,2334353第二階段：對(duì)機(jī)器B, C撥款的效果由于機(jī)器A最多只需3萬(wàn)元，故s2 2 遞推公式：R2(S2，X2)=d2(s2，X2)只1&“)例：R2(3,2)=d2(3,2) R1(1,1)=(1-0.2)得第二階段最優(yōu)決策表S1X1*R1(S1, X1*)001121,2334353S20123X2*R2(S2, X2*)2232,34353第三階段：對(duì)機(jī)器A, B, C撥款的效果邊界條件：S3 = 5遞推公式：R3(s3,x3)=d3(s3,x3) R2