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

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

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

3、純形法求解以下線性規(guī)劃問題：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因檢驗數(shù)020，故

4、確定X2為換入非基變量，以X2的系數(shù)列的正分量對應去除常數(shù)列，最小比值 所在行對應的基變量X4作為換出的基變量。Cj1-11000Cb基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-zj20-1100因檢驗數(shù)03Q,說明已求得最優(yōu)解：X*(0,8/ 3,1/3,0,0,11/ 3)，去除添加的松弛變量，原問題的最優(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因檢驗數(shù)020,說明已求得最優(yōu)解：X* (9,4,1,0,0)8、某地區(qū)有A、B、C三個化肥廠，供應本地甲、乙、丙、丁四個產糧區(qū)。各化肥廠可供應 化肥的數(shù)量和各產糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定個使總運費最少的化肥調撥方案。運價/ 產糧化肥廠甲乙丙丁各廠供應量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設A、B、C三個化肥廠為Ai、A2、A3,甲、乙、丙、丁四個產糧區(qū)為Bi、B2、B3、B4；cij為由Ai運化肥至Bj的運價，單位是元/噸；xij為由Ai運往B

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

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

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

9、之后，與上類似地,進行第二次迭代:f(X)11 令 d(2)1f(X)令步長變量為，最優(yōu)步長為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此時所到達的精度f (X )|0.28281此題最優(yōu)解X, f(X )1,251.5練習題四1、石油輸送管道鋪設最優(yōu)方案的選擇問題：考察網(wǎng)絡圖4-6,設A為出發(fā)地，F(xiàn)為目的地，B,C, D，E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設的位置，

10、線段旁的數(shù) 字表示鋪設這些管線所需的費用。問如何鋪設管道才能使總費用最?。繄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、用動態(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、用動態(tài)規(guī)劃方法求解非線性規(guī)劃2 2 max z 7x1 6x 5x2s.t x-i 2x210x-i 3x29x1, x20解：用順序算法階段：分成兩個階段，且階段1、2分別對應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、設四個城市之間的公路網(wǎng)如圖4-7。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應的最短距離。圖4- 2城市公路網(wǎng)解：城市1到城市4路線1-3-4 距離10；城市2到城市4路線2-4距離8;城市3到城市4路線3-4 距離4。5、某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表 4-19所示。試問在各地區(qū)

13、如何設置銷售點可使每月總利潤最大。表4-1地銷售點區(qū)01234101625303220121721223010141617解：將問題分為3個階段，k=1 , 2, 3;決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為Sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉移方程：劭+1=孤乂丘，其中s=4;允許決策集合：DkSk= Xk|0S3S2X2, D3(s3) X3 1 0X3Ss狀態(tài)轉移方程為：Sk 1 Tk(Sk,Xk) Sk xk,k3,2,1該題是三階段決策過程，故可假想存在第四個階段，而 x4 0，于是動態(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 頁ax戶 f2(s2)max34 fzg 3xjx1 U,l，2,3計算最終結果為Xi 2,X2 1,X3 0，最大價值為13。9、設有A，B，C三部機器串聯(lián)生產某種產品，由于工藝技術問題，產品常出現(xiàn)次品。統(tǒng)計結 果說明，機器 A，B，C產生次品的概率分別為 Pa=30%, Pb=40%, Pc=20%,而產品必須經過三部機 器順序加工才能完成。為了降低產品的次品率，決定撥款5萬元進行技術改造，以便最大限度地提高產

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

16、額；狀態(tài)轉移方程為 Sk-1=Sk-Xk；目標函數(shù)為max R=(1-Pa)(1-Pb)(1-Pc)仍采用反向遞推第一階段：對機器C撥款的效果Rl(si，x0=d i(si ,xi)Ro(S0,X0)= d*si，xi)S10123X1*R1(S1, X1*)001121,2334353第二階段：對機器B, C撥款的效果由于機器A最多只需3萬元，故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第三階段：對機器A, B, C撥款的效果邊界條件：S3 = 5遞推公式：R3(s3,x3)=d3(s3,x3) R2