最優(yōu)化習題1-7.pdfVIP

最優(yōu)化方法部分課后習題解答 習題一習題一 1.1.一直優(yōu)化問題的數(shù)學模型為：一直優(yōu)化問題的數(shù)學模型為： 22 12 112 212 31 42 min( )(3)(4) 5 ( )0 2 ( )50 . . ( )0 ( )0 f xxx g xxx gxxx st gxx gxx =+ = = + = = 試用圖解法求出：試用圖解法求出： （1 1）無約束最優(yōu)點，并求出最優(yōu)值。無約束最優(yōu)點，并求出最優(yōu)值。 （2 2）約束最優(yōu)點，并求出其最優(yōu)值。約束最優(yōu)點，并求出其最優(yōu)值。 （3 3）如果加一個等式約束如果加一個等式約束，其約束最優(yōu)解是什么？，其約束最優(yōu)解是什么？ 12 ( )0h xxx= 解：（1）在無約束條件下，的可行域在整個平面上，不難看出，當=（3，4）( )f x 12 0xx * x 時，取最小值，即，最優(yōu)點為=（3，4）：且最優(yōu)值為：=0( )f x * x * ()f x （2）在約束條件下，的可行域為圖中陰影部分所示，此時，求該問題的最優(yōu)點就是( )f x 在約束集合即可行域中找一點，使其落在半徑最小的同心圓上，顯然，從圖示中可 12 ( ,)x x 以看出，當時，所在的圓的半徑最小。 * 15 5 (, ) 44 x=( )f x 其中：點為和的交點，令求解得到： 1( ) g x 2( ) gx 112 212 5 ( )0 2 ( )50 g xxx gxxx = = += 1 2 15 4 5 4 x x = = 即最優(yōu)點為：最優(yōu)值為：= * 15 5 (, ) 44 x= * ()f x 65 8 （3）.若增加一個等式約束，則由圖可知，可行域為空集，即此時最優(yōu)解不存在。 2.2.一個矩形無蓋油箱的外部總面積限定為一個矩形無蓋油箱的外部總面積限定為 S S， 怎樣設(shè)計可使油箱的容量最大？試列出這個， 怎樣設(shè)計可使油箱的容量最大？試列出這個優(yōu)優(yōu) 化問題的數(shù)學模型，并回答這屬于幾維的優(yōu)化問題化問題的數(shù)學模型，并回答這屬于幾維的優(yōu)化問題. . 解：列出這個優(yōu)化問題的數(shù)學模型為： 該優(yōu)化問題屬于三維的優(yōu)化問題。 123 122313 1 2 3 max( ) 22 0 . . 0 0 f xx x x x xx xx xS x st x x = + 3 2 31 /3,/3,/12 182 3 sss xsyszsv = 習題二習題二 3. 3. 3. 3.計算一般二次函數(shù)計算一般二次函數(shù)的梯度。的梯度。 1 ( ) 2 TT f xX AXb Xc=+ 解：設(shè)：則： 1212 (),( ,.) ,( ,.) TT ijn nnn Aabb bbXx xx = ，將它對變量球偏導(dǎo)數(shù)得： 111 1 ( ) 2 nnn ijijii iji f xa x xb xc = =+ (1,2,. ) i x in= = 1 2 3 ( ) ( ) ( ) ( ) f x x f x f x x f x x = 111 11 222 11 11 11 22 11 22 11 22 nn jjii ji nn jjii ji nn njjinin ji a xa xb a xa xb a xa xb = = = + + + 1 1 1 1 1 22 11 2 3 1 1 11 22 n n jj ii j i n n jjii ji n n ini njj i j a x a x b a xa x b b a xa x = = = = = + = 1 () 2 T AXA Xb+ 5. 5. 5. 5.求下列函數(shù)的梯度和求下列函數(shù)的梯度和 HesseHesseHesseHesse矩陣矩陣 （1）解： 222 12313 ( )234f xxxxx x=+ 2 2 0 -4 ( )0 4 0 4 0 6 f x = （2）解： 1 2 2 12 ( )3 x x f xx xe=+ 1 21 21 2 1 21 21 2 2 22122 2 21211 6+ ( ) 6+ 6 + x xx xx x x xx xx x x exex x e f x xex x exx e + = + 6. 6. 6. 6.判斷下列函數(shù)是凸函數(shù)，凹函數(shù)，還是既不凸也不凹函數(shù)：判斷下列函數(shù)是凸函數(shù)，凹函數(shù)，還是既不凸也不凹函數(shù)： （1） 22 121212 ( ,)23f x xxxx x= + 解：不是半正定，即非凸，然后判斷-，經(jīng)驗證：不是半 2 ( )f x( )f x( )f x 2( ( )f x 正定，由此可知：非凸非凹。( )f x （2） 22 1211221 ( ,)24356f x xxx xxx=+ 解：半正定，故為凸函數(shù)。 2 ( )f x( )f x （3） 222 12312312 ( ,)234f x x xxxxx x=+ 解：不是半正定，即非凸，然后判斷-，經(jīng)驗證：不是半 2 ( )f x( )f x( )f x 2( ( )f x 正定，由此可知：非凸非凹。( )f x 7. 7. 7. 7.設(shè)約束優(yōu)化問題的數(shù)學模型為：設(shè)約束優(yōu)化問題的數(shù)學模型為： 22 1122 112 22 21212 min( )4410 ( )20 . . ( )220 f xxxxx g xxx st gxxxxx =+ =+ = + 試用試用 K-TK-TK-TK-T 條件判別點條件判別點是否為最優(yōu)點。是否為最優(yōu)點。1,1 T x= 解：對于點，=0，點滿足約束條件，故點是可行解。1,1 T x= 1( ) g x 2( ) 0gxX 且是起作用約束，,，由條件下的 1( ) g x 1I= 2 ( ) 2 f x = 1 1 ( ) 1 g x = ( )0 i g x K-T 條件得：，得到，點滿足 K-T 條( )( )0,0 iii i I f xg x = 1 2=1,1 T x= 件。又因正定，故為嚴格凸函數(shù)，該最優(yōu)化問題是凸規(guī)劃問題，由 2 ( )f x( )f x 是 K-T 點，所以也是該問題的全局最優(yōu)點。 * 1,1 T x= * 1,1 T x= 8. 8. 8. 8.設(shè)約束優(yōu)化問題：設(shè)約束優(yōu)化問題： 22 12 11 22 2 312 min( )(2) ( )0 . .( )0 ( )10 f xxx g xx stgxx gxxx =+ = = = + 它的當前迭代點為它的當前迭代點為，試用，試用 K-T 條件判定它是不是約束最優(yōu)解。條件判定它是不是約束最優(yōu)解。1,0 T k x= 解：對于點，點是可行點，1,0 T k x= 123 ()10,()0,()0 kkk g xgxgx= =1,0 T k x= 且起作用的約束條件是，,， 23 ( ),( )gx gx2,3I= k 2 () 0 f x = 2k 0 g () 1 x = ，由約束條件為時的 K-T 條件得，應(yīng)有： 3k 2 g () 1 x = ( )0 i g x 解得：，所以為 K-T 點。( )( )0,0 iii i I f xg x += 2 3 1 1 = = 1,0 T k x= 現(xiàn)判斷該問題是否為凸規(guī)劃問題，因正定，故為凸函數(shù)，為 2 ( )f x( )f x 12 ( ),( )g x gx 線性函數(shù)，亦為凸函數(shù)，半正定，所以為凸函數(shù)，所以該優(yōu)化問題為凸 2 3 g ( )x 3 g ( )x 規(guī)劃問題，即點是該問題的約束最優(yōu)解。1,0 T k x= 習題三習題三 1. 1. 1. 1.對于下列線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定出最優(yōu)解。對于下列線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定出最優(yōu)解。 （1 1 1 1） 123 1234 1235 16 max( )32 12369 84210 . . 30 0,(1,2.6) j f xxxx xxxx xxxx st xx xj =+ += += = = 解：令 123456 12 3 6 3 0 0 8 1 -4 0 2 0 ( ,) 3 0 0 0 0 -1 AP P P P P P = （1） 基解不是基可行解， 1 167 (0,0,0,0) 36 x= （2） 基解不是基可行解， 2 (0,10,0,7,0,0)x= （3） 基解是基可行解，且， 3 (0,3,0,0,3.5,0)x=( )3f x= （4） 基解不是基可行解， 4 721 ( , 4,0,0,0,) 44 x= （5） 基解不是基可行解， 5 5 (0,0,8,0,0) 2 x= （6） 基解是基可行解，且， 6 3 (0,0,0,16,0) 2 x=( )3f x= （7） 基解不是基可行解， 7 1 (1,0,0,0,3) 2 x= （8） 基解是基可行解，且， 8 (0,0,0,3,5,0)x=( )0f x= （9） 基解不是基可行解。 9 515 ( ,0,0, 2,0,) 44 x= （10） 基解是基可行解，且。 10 39 ( ,0,0,0,4, ) 44 x= 9 ( ) 4 f x= （11） 基解不是基可行解。 11 167 (0,0,0,0) 36 x= （12） 基解不是基可行解。 12 (0,10,0, 7,0,0)x= （13） 基解是基可行解，且。 13 7 (0,3,0,0,0) 2 x=( )3f x= （14） 基解不是基可行解。 14 5 (0,0,8,0,0) 2 x= （15） 基解是基可行解，且。 15 3 (0,0,0,8,0) 2 x=( )3f x= （16） 基解是基可行解，且。 16 (0,0,0,3,5,0)x=( )3f x= 2. 2. 2. 2.用單純形法求解下列線性規(guī)劃問題：用單純形法求解下列線性規(guī)劃問題： （1 1 1 1） 12 12 12 12 max( )105 349 . . 528 ,0 f xxx xx stxx x x =+ + + 解：將現(xiàn)行規(guī)劃問題化為標準形式如下： 1234 123 124 1234 min( )10500 349 . . 528 ,0 f xxxxx xxx stxxx x x x x = + += += 作初始單純形表，并按單純形表步驟進行迭代，如下： 此時，均為正，目標函數(shù)已不能再減小，于是得到最優(yōu)解為： j * 3 (1,0,0) 2 x= 目標函數(shù)值為： * ()17.5f x= 3. 3. 3. 3.分別用單純形法中的大分別用單純形法中的大 MMMM 法和兩階段法求解下列線性規(guī)劃問題：法和兩階段法求解下列線性規(guī)劃問題： B C B Xb-10 1 x -5 2 x 0 3 x 0 4 x i 0 3 x 934103 0 4 x 852011.6 0-10-500 0 3 x 4.202.81-0.61.5 -10 1 x 1.610.400.24 160-102 -5 2 x 1.501 5 14 3 14 -10 1 x 110 1 7 2 7 17.500 5 14 25 14 （1） 1234 1234 1234 1234 min( )5236 2347 . . 223 ,0 f xxxxx xxxx stxxxx x x x x =+ += += 解：（1 1 1 1）大大 MMMM 法法：把原問題化為標準形式，并加入人工變量如下： 123456 12345 12346 123456 min( )5236 2347 . . 223 ,0 f xxxxxMxMx xxxxx stxxxxx x x x x x x =+ += += 作初始單純形表，并按單純形表步驟進行迭代，如下： 因為 M 是一個很大的正數(shù)，此時均為正， j 所以，得到最優(yōu)解：，最優(yōu)值為 * (0,0,1,1,)Tx= * ()3f x= （2 2 2 2）兩階段法兩階段法 B C B Xb5 1 x -2 2 x 3 3 x -6 4 x -6 4 x -6 4 x i M 5 x 71234101.75 M 6 x 32112011.5 -10M5-3M-2-3M 3-4M -6-6M00 M 5 x 1-30101-21 -6 4 x 1.510.50.5100.53 9-M11+3M16-M003M+3 3 3 x 1-30101-2 -6 4 x 12.50.501-0.51.5 329100M-6 M+15 首先，構(gòu)造一個僅含人工變量的新的線性規(guī)劃如下： 123456 12345 12346 123456 min ( )0000 2347 . . 223 ,0 g xxxxxxx xxxxx stxxxxx x x x x x x =+ += += 按單純形法迭代如下： 最優(yōu)解為：，最優(yōu)值： * (0,0,1,1,0,0)x=( )0g x= 因人工變量，則原問題的基可行解為:,進入第二階段計算 56 0xx= * (0,0,1,1,)Tx= 如下表所示： 由上表可知，檢驗數(shù)均大于等于 0，所以得到最優(yōu)解： * (0,0,1,1,)Tx= 最優(yōu)值為。 * ()3f x= 4. 4. 4. 4.某糖果廠用原料某糖果廠用原料 A A A A，B B B B，C C C C 加工成三中不同牌號的糖果，甲，乙，丙，已知各種牌號加工成三中不同牌號的糖果，甲，乙，丙，已知各種牌號糖糖 果中果中 A,B,CA,B,CA,B,CA,B,C 含量，原料成本，各種原料的每月限用量，三中牌號糖果的單位加工費及含量，原料成本，各種原料的每月限用量，三中牌號糖果的單位加工費及售售 B C B Xb0 1 x 0 2 x 0 3 x 0 4 x 1 4 x 1 4 x i 1 5 x71234101.75 1 6 x32112011.5 -10-3-3-4-600 1 5 x1-30101-21 0 4 x1.510.50.5100.53 -140-1003 0 3 x1-30101-2 0 4 x12.50.501-0.51.5 B C B Xb5 1 x -2 2 x 3 3 x -6 4 x 3 3 x1-3010 -6 4 x12.50.501 329100 價如下表所示，問該廠每月應(yīng)生產(chǎn)這三種牌號糖果各多少千克，使該廠獲利最大？試價如下表所示，問該廠每月應(yīng)生產(chǎn)這三種牌號糖果各多少千克，使該廠獲利最大？試建建 立這個問題的線性規(guī)劃數(shù)學模型。立這個問題的線性規(guī)劃數(shù)學模型。 解：設(shè)表示甲、乙、丙中分別含 A、B、C 的含量，構(gòu)造此問題的,0,1,2,3 iii x y zi= 數(shù)學規(guī)劃模型如下： 123123123 111 222 333 123 123 123 123 12 max( )0.91.41.90.450.951.450.50.450.95 2000 2500 1200 0.40.60.60 . . 0.850.150.150 0.20.20.80 0.60.60.40 0.50.5 f xxxxyyyzzz xyz xyz xyz xxx styyy xxx yyy zz =+ + + + + + + 3 0.50 ,0,1,2,3 iii z x y zi = 5. 5. 5. 5.求解下列線性規(guī)劃問題的對偶問題求解下列線性規(guī)劃問題的對偶問題 （1） 123 123 123 123 123 min( )224 2352 373 . . 465 ,0 f xxxx xxx xxx st xxx x x x =+ + + + （2） 123 123 123 123 123 max( )563 225 53 . . 4738 ,0,0 f xxxx xxx xxx st xxx xxx =+ += + + 無約束 甲乙丙 原料成本 （元/千克） 每月限用量 （千克） A 60 % 15 % 2.002000 B1.502500 C 20 % 60 % 50 % 1.001200 加工費0.500.400.30 售價3.402.852.25 解：（1）由表 3.7 可得該問題的對偶問題為： 123 123 123 123 123 max( )235 232 342 . . 5764 0,0 g yyyy yyy yyy st yyy yyy =+ + + + （2）該問題的對偶問題為： 123 123 123 123 123 min( )538 345 2576 . . 233 ,0,0 g yyyy yyy yyy st yyy yyy =+ += + + 無約束 6用對偶單純形法求解下列線性規(guī)劃問題： （1） 123 13 23 123 min( )41218 33 . . 225 ,0 f xxxx xx stxx x x x =+ + + 解：（1）首先，將“”約束條件兩邊反號，再加入松弛變量，得： 12345 134 235 12345 min( )412180 33 . .225 ,0 f xxxxxx xxx stxxx x x x x x =+ += += 建立初始單純形表如下圖所示，所有。0 j 則對應(yīng)對偶問題解是可行的，則繼續(xù)迭代： 計算，所以為換出變量，確定為換入變量。min3, 55= 5 xmin 6,96= 2 x 繼續(xù)迭代，得到如下單純形表： B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 4 x-3-10-310 0 5 x-50-2-201 4121800 。 43 min33,min 4 22xx= =換出， 換入 此時，所有，故原問題的最優(yōu)解為,最優(yōu)值為：0 j * 3 0,1 2 T x= * ()36f x= 其對偶問題得到最優(yōu)解為：，最優(yōu)值為：。 * 2,6Tx= * ()36f x= 7. 7. 7. 7.已知線性規(guī)劃問題已知線性規(guī)劃問題 123 123 12 123 min( )2 6 . .24 ,0 f xxxx xxx stxx x x x =+ + + 先用單純形法求出最優(yōu)解，再分別就下列情況進行分析：先用單純形法求出最優(yōu)解，再分別就下列情況進行分析： （1 1 1 1） 目標函數(shù)中變量目標函數(shù)中變量的系數(shù)分別在什么范圍內(nèi)變化，問題的最優(yōu)解不變；的系數(shù)分別在什么范圍內(nèi)變化，問題的最優(yōu)解不變； 123 ,x x x （2 2 2 2） 兩個約束條件的右端分別在什么范圍內(nèi)變化，問題的最優(yōu)解不變。兩個約束條件的右端分別在什么范圍內(nèi)變化，問題的最優(yōu)解不變。 解：將該規(guī)劃問題化為標準型，引入松弛變量 45 ,x x 12345 1234 125 12345 min( )200, 6 . .24 ,0 f xxxxxx xxxx stxxx x x x x x =+ += += B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 4 x-3-10-310 0 2 x-2.50110-0.5 40600 B C B Xb4 1 x 12 2 x 18 3 x 0 4 x 0 5 x 0 3 x1 1 3 01 1 3 0 0 2 x1.5 1 3 10 1 3 -0.5 20026 用單純形法求解，如下表： 由上表可知，所有的檢驗數(shù)均大于等于零，得最優(yōu)解:,所以原問題的 * (0,2,0,4,0)Tx= 最優(yōu)解為：，最優(yōu)值 * (0,2,0,)Tx= * ()2f x= （1）。 123132 xxxxxx變量 ， ， 中， ， 為非基變量， 為基變量 3311 ,), 2222 1100,), ccccc ccccc = =+ = =+ 111111 333333 由，當時，所以，當此時最優(yōu)解不變。 由，當時，所以，當此時最優(yōu)解不變。 ，最優(yōu)解不變。() 2 3,1c 綜上， 1 ,) 4,00,), 2 ccc+ + 123 當，此時最優(yōu)解不變。 （2）的變化范圍 1 b 1111 1 410.5410 200.520000 bb B bBb +=+=+ 得到：，最優(yōu)解保持不變。 1111 4042bbbb+ ，則 的變化范圍是 11 2 22 00410.540.50 200.520.50 B bBb bb +=+=+ 得到：，最優(yōu)解保持不變。 22 48bb ，則 的變化范圍是0,12 習題四習題四 B C B Xb2 1 x -1 2 x 1 3 x 0 4 x 0 5 x i 0 4 x1111106 0 5 x1.5-120012 2-1100 0 4 x41.5011-0.5 -1 2 x2-0.51000.5 1.50100.5 3. 3. 3. 3.用用 Newton 法求解法求解 3 ( )21ttt=+ 用第用第 1 題求得的區(qū)間，按精度題求得的區(qū)間，按精度計算。計算。0.01= 解： 0100111010 ( )(0)1,1, ( )0,0,( )( )2ttthttthh=+=因為，則 2112212 1( )22,22, ( )( )K=20,=0b=3tthttt=+=，反向，因為所以， 則搜索區(qū)間為?。簍0,3 2 ( )32,( )6,(0)20,(3)250ttt= ， 000 15 5 1,( )1,( )6,t110.01 66 6 ttt= =所以，繼續(xù)迭代 0 5 =t 6 t= ， 0 000 0 ( )491149 ,0.01,0.8165 ( )606060 t tttttt t = 則令，則 。 * 0 0.00050.01,0.817,()0.088tt=繼續(xù)迭代，因為 1122 1.832608, ( )0.306764,1.111392, ( )0.987592tttt= = = = ， ，因為，所以新的搜索區(qū)間為-1.832608，0.056： 12 ,tt繼續(xù)迭代 12 ( )( )tt ， 1122 1.111292, ( )0.987592,0.665448, ( )0.888075tttt= = = = ， ，所以新的搜索區(qū)間為-1.832608，-0.665448 ： 12 ,tt繼續(xù) 12 ( )( )tt ， 1122 1.386753, ( )0.854402,1.111392, ( )0.987592tttt= = = = ，因為，所以新的搜索區(qū)間為-1.386753，-0.665448 12 ,tt繼續(xù) 12 ( )( )tt ， 2211 0.940987, ( )0.996518,1.111392, ( )0.987592tttt= = = = ， ，所以新的搜索區(qū)間為-1.111392，-0.665448 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 1122 0.940987, ( )0.996518,0.835799, ( )0.973038tttt= = = = ， ，所以新的搜索區(qū)間為-1.111392，-0.835799 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 2211 0.940987, ( )0.996518,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索區(qū)間為-1.111392，-0.940987 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 1122 1.046295, ( )0.997857,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索區(qū)間為-1.046295，-0.940987 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 2211 0.981215, ( )0.999647,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索區(qū)間為-1.046295，-0.981215 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 1122 1.021434, ( )0.999540,1.006115, ( )0.999962tttt= = = = ， ，所以新的搜索區(qū)間為-1.021434，-0.981215 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 2211 0.996579, ( )0.999987,1.006115, ( )0.999962tttt= = = = ，所以新的搜索區(qū)間為-1.006115，-0.981215 ： 12 ,tt繼續(xù) 12 ( )( )tt因為 ， 1122 0.996579, ( )0.999987,0.990727, ( )0.999914tttt= = = = ， ，所以新的搜索區(qū)間為-1.006115，-0.990727 ： 12 ,tt繼續(xù) 12 ( )( )tt繼續(xù) 12 ( )( )tt繼續(xù) 12 ( )( )tt因為 2211 0.998830, ( )0.999998505,1.000237, ( )1.00000016tttt= = = = ， ，新的搜索區(qū)間為-1.002472，-0.998830 12 ,tt繼續(xù) 12 ( )( )tt， ，所以，新的搜索區(qū)間為0.5227，1， 0 ( )0.1588( )0.063tt= = = ， ，新的搜索區(qū)間為：0.6232，1， 0 ( )0.2032( )0.2029tt= = = 、解： 矩陣 22 9883.89760.07348 0.48089 0.0030.150.06913 ()0.124872 00 ( )0 00 T f xg xxf x = = = 同理繼續(xù)迭代，最后至，此時最優(yōu)解， 2. 2. 2. 2.用用 NewtonNewtonNewtonNewton 法求解法求解 22 1212120 min( )60 10400.01. T f xxxxxx xx=+=-，初始點，0 ， 解： 1221 1 1 100 11 * ( )( ) 102, 42 21 21 33 ( )( ) 1212 33 21 010 33 ( )()8,6 0124 33 ( )0,0 ,( )00.01 8,6 ,()8 T T T T g xf xxxxx G xG x xxG xg x f xf x xf x = + + = = = = =最優(yōu)解為 3. 3. 3. 3.用修正用修正 NewtonNewtonNewtonNewton 法求解法求解 22 12120 min( )412100.01. T f xxxxxx=+=（） （）+10，初始點，0 ， 解： 12 ( )( )89,43Tg xf xxx= =+ 0 1000 0 9 8 3 4 t xxt p t =+ = ， 1 1 0 80 8 ( )( ) 041 0 4 G xG x = = ， 0 ()93 T g x=， 則，令 1 00 1 0 99 3 8 ( )(), 318 4 0 4 T pG xg x = = 0 1000 0 9 8 3 4 t xxt p t =+ = 2 1 9999 ()161( ) 168 f xtttf x=+ = 時，最小 111 * 9 3 , ()0,0 ,()00.01 8 4 9 3157 , ,() 8 416 TT T xf xf x xf x = = = = ， 4. 4. 4. 4.用共軛梯度法求解用共軛梯度法求解 22 120 min410.01. T xxx+=（），取初始點，1 ， 解： 令， 22 1112 ( )4,( )2 ,8 T f xxxf xxx=+= 00 ()2,8 T pf x= = 1000000 12 12 ,1 8 18 T xxt pttt =+=+= 令， 22 00 min(12 )4(1 8 ) min ( )ttt+= 則 00 ( )5206800.130969 d ttt dt = 11 0.738062, 0.047752()1.476124, 0.382016 TT xf x=， 則 2 1 0 2 0 ()2.324878 0.034189 68 () f x f x = 1100 ()pf xp= +新搜索方向為 1.47612421.544502 0.034189 0.38201680.108504 =+= 211111 0.738062 1.544502 , 0.0477520.108504 T xxt ptt=+=+因此有 1111 ()00.477127 d f xt pt dt +=由 2111 0.7380621.544502 0.4771270.00,0.007 0.0477520.108504 T xxt p =+=+= 因而得下一迭代點 ， 2 ()00.01f x=停止迭代 * 0,0 ,()0 T xf x= 5. 5. 5. 5.用共軛梯度法求解用共軛梯度法求解 22 1212 min( )20.01.f xxxx x=+=-，自定初始點， 解：，取初始點， 1221 ( )4,2 T f xxxxx= 0 0,1 T x= 00 ()1, 2Tpf x= = 1000000 01 ,12 12 T xxt pttt =+=+= 令 22 0000 min2(12 )(1 2 )min ( )ttttt+= 則 00 ( )16500.125 d ttt dt = 11 0.3125, 0.375()0.875,0.4375 TT xf x=， 2 1 0 2 0 ()0.95703125 0.191406 5 () f x f x = 1100 ()pf xp= +新搜索方向為 0.87510.683594 0.191406 0.437520.82012 =+= = 2111 xxt p=+因而得下一迭代點 11 0.31250.683594 ,0.3750.820312 T tt ， 1111 ()00.456927 d f xt pt dt +=由 則停止迭代 222 0.000,0.000()0,0 ,()00.01 TT xf xf x=， 則=，綜上所述，原問題的最優(yōu)解，最優(yōu)值為 * x 2 0,0Tx= * 0,0Tx= * ()0f x= 6. 6. 6. 6.用用 DFPDFPDFPDFP 法求解法求解 22 120 min( )45680.01. T f xxxx=+=（） （），初始點，9 ， 6、解：取 012 80 ,( )840,212 02 T HIAg xxx = 00 8,19,24,6 TT xg= 第一步迭代得： 11 4.86154,8.21538,1.10768,4.43076 TT xg= 用 DFP 法第二次迭代： 010 3.13846, 0.78462Tsxx= 010 25.10768, 1.56924Tygg= 則， 0 00000 10 00000 TT TT s sH y y H HH syy H y =+ 因： 00 80.03071, T sy= 00000 632.85811 TT y H yyy= ， 0 0 9.849932.46250 2.462500.61563 T s s = 0 0 9.849932.46250 2.462500.61563 T s s = 1 100.123080.030770.996110.062260.126970.03149 010.030770.007700.062260.003900.031491.0038 H =+= 則搜索方向 111 0.28017,4.48248TpH g= = 從出發(fā)沿進行直線搜索，即： 1 x 1 p 111 4.861540.28017 ,8.215384.48248 T xxtptt=+=+ 由，得 11 ()0 d f xtp dt +=0.48674t= 所以，由于，所以是極小 211 5.000,6.000Txxtp=+ 2 ()0,0Tg x= 2 5,6Tx= 點。 習題六習題六 1. 1. 1. 1.用外點罰函數(shù)法求解：用外點罰函數(shù)法求解： 12 2 112 21 min( ) ( )0 . . ( )0 f xxx g xxx st gxx =+ = + = 解：利用外點罰函數(shù)法構(gòu)造增廣目標函數(shù)，如下： 222 12121 12 ()() ( , ) () xxxxxxD F x xxxD + = + 對于的情況：xD 由得： 12 0,0 FF xx = 2 111 ( ), 2224(1) x = + 當時， +()( )0,0x 即：，且()0,0x=()0f x= 2. 2. 2. 2.用外點罰函數(shù)法求解：用外點罰函數(shù)法求解： 22 12 min( )f xxx=+ . .st 1 ( )10g xx= 解：構(gòu)造增廣目標函數(shù)： 222 121 22 12 (1)() ( , ) () xxxxD F x xxxD + = + 對于的情況：xD 由得： 12 0,0 FF xx = 11 2 22 (1)0 20 xx x = = 推出：( ),0 1 x = + 當時，。 +()( )1,0x 即：且。()1,0x=()1f x= 4. 4. 4. 4.用內(nèi)點罰函數(shù)法求解：用內(nèi)點罰函數(shù)法求解： 3 12 11 22 1 min( )(1) 3 ( )10 . . ( )0 f xxx g xx st gxx =+ = = 解：利用內(nèi)點罰函數(shù)法構(gòu)造如下增廣目標函數(shù)： 3 12 12 111 ( ,)(1)() 31 kk F x rxxr xx =+ 由得： 1 2 0 0 F x F x = = *( )( 1,) kkk x xrr=+ 當時，0 k r + *( )(1,0) k x x =， * x(1,0) * 8 () 3 f x= 5. 5. 5. 5.用內(nèi)點罰函數(shù)法求解：用內(nèi)點罰函數(shù)法求解： 3 12 1 2 1 min(1) 3 10 . . 0 xx x st x + 解法同上。 習題七習題七 1. 1. 1. 1.用動態(tài)規(guī)劃求解：用動態(tài)規(guī)劃求解： 2 123 123 max 4 . . 0(1,2,3) i Ex x x xxx st xi = + = 解：將原問題表示為： 2 123 maxEu u u= 123 4 . . 0(1,2,3) i uuu st ui + = 由此，確定狀態(tài)變量為：， 決策變量為： 123 ,x x x 123 ,u u u 狀態(tài)轉(zhuǎn)移方程：。 11; xu= 221; xux=+ 332 4xux=+ 用動態(tài)規(guī)劃的思想順推，如下： 第一步，1:k= 。 11 * 111111 () , max ux f xuxux = =且 第二步，2:k= 22 22 22 22211 0 2122 0 222 0 ()() () (). max max max ux ux ux fxuf x uf xu uxu = = = 2222222 22* 222222 1 () 2 111 ()max0, 0 442 uuxuuux fxxxux = = 令： ()=，由()=0，得： ，且 第三步，3:k= 33 33 33 2 33322 0 2 3233 0 22 333 0 ()() () 1 () . 4 max max max ux ux ux fxufx ufxu uxu = = = 22 3333333 44* 333333 4 333 11 () 42 111 ()max0, 0 64642 1 4()44 64 uuxuuux fxxxux xfx = = = 同理，令： ()=，由()=0，得： ，且 將代入上述表達式，逆序遞推求出： 33 ()4fx= * 33 * 22 * 11 * * 42 21 11. (1,1,2)()4 (1,1,2)()4. xu xu xu uf u xf x = = = = = ,， ,， , 新問題的最優(yōu)解為：，且 原問題的最優(yōu)解為：，且 2. 2. 2. 2.設(shè)有設(shè)有 5 5 5 5 個城市，編號從個城市，編號從 1 1 1 1 到到 5 5 5 5，記第，記第 個城市與第個城市與第個城市的距離為個城市的距離為，記：，記：ij ij d ， 5 5 0652 2 60 0.5 5 7 ()5 0.5 0 1 5 251 0 3 2753 0 ij Dd = 試分別用函數(shù)迭代法和策略迭代法求出各城市到第試分別用函數(shù)迭代法和策略迭代法求出各城市到第 5 5 5 5 個城市的最短距離。個城市的最短距離。 解：法一，函數(shù)迭代法： 15 11111 21 05 21 21 2 1( )(1,2,3,4,5) (1)2,(2)7,(3)5,(4)3,(5)0. 2( )( ) (1)min02,67,55,23,20(1), (2)min62,07,0.55,53,70(2), (3)min52,0.57