數(shù)學(xué)建模優(yōu)化理論與方法PPT課件

1、（1）由決策變量構(gòu)成，反映決策的目標(biāo)是線性函數(shù)。（2）一組由決策變量的線性等式或不等式構(gòu)成約束 條件。（3）對決策變量取值范圍加以限制的非負(fù)約束。1.1 線性規(guī)劃模型的特征線性規(guī)劃模型的特征 例1：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤、所消耗的材料、工時(shí)及每天的材料限額和工時(shí)限額，如表1.1所示。試問如何安排生產(chǎn)，使每天所得的利潤為最大？第1頁/共178頁表表1.11.1甲乙限額材料2324工時(shí)3226利潤(元/件)43 設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為 x1 , x2 則該問題可描述為由如下數(shù)學(xué)模型：0,26232432 .34max 21212121xxxxxxtsxxZ第2頁/共178

2、頁1.2 線性規(guī)劃問題的標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)型 如下形式的線性規(guī)劃模型被稱作標(biāo)準(zhǔn)型:),2, 1( 0 ),2, 1( .max11njxmibxatsxcZjnjijijnjjj也可用矩陣形式描述: 0 bAX .maxXtsCXZA:資源消耗系數(shù)矩陣b: 資源限量向量C:價(jià)格向量X:決策變量向量第3頁/共178頁同時(shí)我們對標(biāo)準(zhǔn)型作如下假定:. 1 , 0 , 0 )2(. , ,)( ) 1 (即可乘以個(gè)約束方程兩邊同時(shí)則可對第若有沒有多余方程彼此獨(dú)立即標(biāo)準(zhǔn)型中的約束方程ibbnmAranki 一般的線性規(guī)劃問題通過變換可化成標(biāo)準(zhǔn)型 , 變換方式可以歸結(jié)為:. ) max( ) max

3、() min( :, ) 1 (即可這樣我們只要討論問題可以通過以下方式得到如果目標(biāo)函數(shù)是極小化第4頁/共178頁. 0 , 0 , ) 3()0( , .)0( , . , )2(kkkkkkzyzyxxba其中則可令無非負(fù)性限制如果變量該松弛變量右端某松弛變量不等式左端則如果約束條件為該松弛變量右端某松弛變量不等式左端則如果約束條件為變量來得到我們可以通過引進(jìn)松弛如果約束方程為不等式第5頁/共178頁1.3 線性規(guī)劃問題解的概念線性規(guī)劃問題解的概念 對于線性規(guī)劃問題)3.1( ),2, 1( 0 )2.1( ),2, 1( .)1.1( max11njxmibxatsxcZjnjijijn

4、jjj. ) 1 . 1 ( : . ),( ) 3 . 1 ( ) 2 . 1 ( : 21的可行解稱為最優(yōu)解滿足最優(yōu)解稱為可行解的解和滿足約束條件可行解TxxX第6頁/共178頁題的一個(gè)基。是線性規(guī)劃問則稱階非奇異子矩陣中的一個(gè)是矩陣如果基：設(shè) , )0|(| , )( BBmmABmAranknm個(gè)非基向量。有中共，之外各列即為非基向量中除矩陣，中的列向量稱為基向量基向量與非基向量：基 mnABAB基變量。為基變量；否則稱為非稱對應(yīng)的變量基向量基變量與非基變量：與 jjxP第7頁/共178頁稱為基解。的解，求出的滿足為基解：令所有非基變量 )2 . 1 ( 0 )3 . 1 ( mnC

5、基解的數(shù)目解的數(shù)目基可行為可行基。顯然，對應(yīng)基可行解的基，稱的基解稱為基可行解。足基可行解與可行基：滿優(yōu)基。為最對應(yīng)基本最優(yōu)解的基稱優(yōu)解，的基可行解稱為基本最滿足基本最優(yōu)解與最優(yōu)基： ) 1 . 1 ( 可行解基解基可行解第8頁/共178頁1.4 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法 下面結(jié)合例1的求解來說明圖解法步驟。0,26232432 .34max 21212121xxxxxxtsxxZ例1第一步：在直角坐標(biāo)系中分別作出各種約束條件，求出可行域（圖中陰影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)第9頁/共178頁為則稱

6、點(diǎn)連線上的一切任意兩點(diǎn)中的一個(gè)點(diǎn)集，若維歐氏空間是設(shè)定義，先介紹兩個(gè)概念。為介紹基本定理的需要 , ) 10( )1 ( )(, 1 . 1)2()1()2()1()2()1(KKXXXXXKXXEnKn第二步：作出一條目標(biāo)函數(shù)等值線，并確定 Z 值增大的方向。第三步：沿 Z 值增大方向移動(dòng)，當(dāng)移至 Q2(6,4) 點(diǎn)時(shí)，Z 值為最大，Z*=36 .1.5 基本定理基本定理. 凸集第10頁/共178頁., 1 . 1域必為凸集則其可行空可行域若線性規(guī)劃問題存在非定理的一個(gè)為則稱的線性組合表示為點(diǎn)若不能用兩個(gè)不同的是凸集，設(shè)定義 , ) 10( )1 ( , ; 2 . 1)2()1()2()1

7、(KXKXXXKXKXKXK. 極點(diǎn)., 2 . 1可行域的極點(diǎn)上達(dá)到數(shù)最優(yōu)值一定可以在其則其目標(biāo)函域有界若線性規(guī)劃問題的可行定理. 3 . 1的極點(diǎn)對應(yīng)于可行域解線性規(guī)劃問題的基可行定理X 從理論上來講,采用“枚舉法”找出所有基可行解,并第11頁/共178頁1.6 求解求解線性規(guī)劃問題的單純形方法線性規(guī)劃問題的單純形方法 一一比較,一定會(huì)找到最優(yōu)解。但當(dāng) m, n 較大時(shí),這種方法是不經(jīng)濟(jì)和不可取的。 下面介紹求解線性規(guī)劃問題的有效方法單純形方法。單純形法的實(shí)質(zhì)是從一個(gè)基可行解向另一個(gè)基可行解（極點(diǎn)到極點(diǎn)）的迭代方法。 以下通過例1的求解過程說明單純形方法的基本步驟。0,26232432 .

8、34max 21212121xxxxxxtsxxZ例1：第12頁/共178頁第一步：引進(jìn)松馳變量 x3 , x4 將原問題化為標(biāo)準(zhǔn)型。0,26 2324 32 . 0034max 43214213214321xxxxxxxxxxtsxxxxZ標(biāo)準(zhǔn)型第二步：找出初始可行基，建立初始單純形表。 見下表1.2。第13頁/共178頁 cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1Z0 -4 -3 0 0 表 1.2bBbIPPB10430 ),( 則本例中，初始可行基第三步：最優(yōu)性檢驗(yàn)。 可能有下面三種情況：的檢驗(yàn)數(shù)檢驗(yàn)各非基變量 , j

9、jxij第14頁/共178頁行換基迭代。四步，進(jìn)不是最優(yōu)基，須轉(zhuǎn)入第則基分量，所對應(yīng)的列向量有正若有某個(gè)負(fù)檢驗(yàn)數(shù)，停止計(jì)算。函數(shù)無上界，即無界解標(biāo)則該線性規(guī)劃問題的目（部分量它所對應(yīng)的列向量的全若有某，停止計(jì)算?？尚薪饧礊榛咀顑?yōu)解為最優(yōu)基，相應(yīng)的基則基若所有的 B 0 ) 3( , 0), , 0 )2( , 0 ) 1 (21jmssssjaaaB第15頁/共178頁量。所在的列變?yōu)閱挝涣邢蚣窗鸦兞窟M(jìn)行初等行變換，為主元，在單純形表中以為主元。為出基變量，其中確定元按最小比值原則求出主確定換出變量取確定換入變量 )3( ,0|min : )2(. 0 , 0|min : ) 1 (srs

10、rsrrsrisisiirjsxaaxabaabxnjjsx第四步：換基迭代。第16頁/共178頁的單純形表。，得到新的可行基和新?lián)Q為中的同時(shí)將 srBxxX有無界解，計(jì)算終止。出至獲得最優(yōu)解，或判斷重復(fù)第三、第四步，直 所在行的交叉處所在列和換出基變量，并以為確定，為換入變量。所以，因?yàn)閬碚f，對于表針對例 326326,2240|min 13, 4|min: 2 . 1 1 414121xxxaabxjsisisiii第17頁/共178頁元素為主元進(jìn)行迭代。 cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3Z0 -4

11、-3 0 0 04x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3413Z104/3 0 -1/3 0 4/3表1.3ijj第18頁/共178頁同理，確定 x2 換入，x3 換出，繼續(xù)迭代得表 1.3 cj 4 3 0 0 CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5Z36 0 0 1/5 6/5 表 1.3 表中最后一行的所有檢驗(yàn)數(shù)都已是正數(shù)或零，從而得到基本最優(yōu)解 X*=(6,4,0,0)T, Z*=36 。由于 x3 , x4 是引進(jìn)的松弛變量，因此原問題的最優(yōu)解為 x1=6, x2=4, 最優(yōu)值 Z*=

12、36 。ji第19頁/共178頁例2 一奶制品加工廠用牛奶生產(chǎn) A1 , A2 兩種奶制品，1 桶牛奶可以在設(shè)備甲上用 12 小時(shí)加工成 3 公斤 A1,或者在設(shè)備乙上用 8 小時(shí)加工成 4 公斤 A2。根據(jù)市場需求，生產(chǎn)的 A1 , A2 全部能售出，且每公斤 A1 獲利 24 元，每公斤 A2 獲利 16 元?，F(xiàn)在加工廠每天能得到 50 桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為 480 小時(shí)，并且設(shè)備甲每天至多能加工 100 公斤 A1 , 設(shè)備乙的加工能力沒有限制。試為該廠制定一個(gè) 我們無意過深涉及線性規(guī)劃的具體計(jì)算方法，而著重介紹的是如何建立若干實(shí)際的線性規(guī)劃模型，如何使用現(xiàn)成的數(shù)學(xué)軟

13、件進(jìn)行求解，以及如何對結(jié)果進(jìn)行深入的分析。 下面以奶制品加工生產(chǎn)計(jì)劃為例，進(jìn)行詳細(xì)的討論。第20頁/共178頁生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下 3 個(gè)附加問題： 若用 35 元可買到 1 桶牛奶，買嗎？若買，每天最多 買多少? 若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人 的工資最多是每小時(shí)幾元? 由于市場需求的變化，A1 的獲利增加到 30元/公斤， 應(yīng)否改變生產(chǎn)計(jì)劃？第21頁/共178頁1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時(shí)間480小時(shí) 至多加工100公斤A1 每天：分析x1 桶牛奶生產(chǎn) A1 x2 桶牛奶生產(chǎn)

14、A2 獲利 243x1 獲利 164 x2 決策變量決策變量 0, 1003 480812 50 .6472 211212121xxxxxxxtsxxzMax數(shù)學(xué)模型原料供應(yīng) 勞動(dòng)時(shí)間 加工能力 非負(fù)約束 第22頁/共178頁解法1：圖解法。 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約束條件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMaxZ=0Z=2400Z=3360c從圖中可以看出，在 B(20,30) 點(diǎn)得到最優(yōu)解。解法2：軟件實(shí)現(xiàn)。求解線性規(guī)劃有不少現(xiàn)成的數(shù)學(xué)軟

15、件，比如用 LINDO 軟件就可以很方便地實(shí)現(xiàn)。在 LINDO6.1版本下打開一個(gè)新文件，像書寫模型一樣。直接輸入：第23頁/共178頁max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end注：LINDO中已規(guī)定所有決策變量均為非負(fù)，故變量非負(fù)的條件不必輸入。輸入文件中第1行為目標(biāo)函數(shù)，2),3),4)是為了標(biāo)示各約束條件，便于從輸出結(jié)果中查找相應(yīng)信息；程序最后以end 結(jié)束。 將文件存儲(chǔ)并命名后，選擇菜單 “Solve” 并對提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即可得到如下輸出：第24頁/共178頁

16、OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元。 原料無剩余時(shí)間無剩余加工能力剩余40三種資源“資源” 剩余為零的約束為緊約束（有效約束） 第25

17、頁/共178頁結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量 原料增加1單位, 利潤增長48 時(shí)間增加1單位, 利潤增長2 加工能力增長不

18、影響利潤影子價(jià)格 35元可買到1桶牛奶，要買嗎？35 0 ,并將各個(gè)約束條件加到目標(biāo)函數(shù)上，得一新函數(shù)如下：1( ,)( ) ( ) (4.12)ljjP X Mf XMg X 可以看出，當(dāng) 時(shí)，有 ；當(dāng) 時(shí)，由于M 很大，將使 很大，從而使XR( ,)( )P X Mf XXR1 ( )ljjMg X( ,)P X M第121頁/共178頁很大，這就相當(dāng)于對非可行點(diǎn)的“懲罰”。而且，X 點(diǎn)離可行域越遠(yuǎn)懲罰越嚴(yán)厲?？梢韵胍?，當(dāng) M 變得足夠大時(shí)，相應(yīng)于這樣的 M 值，(4.12) 的無約束極小點(diǎn) X(M) , 就會(huì)和原來的約束問題的極小點(diǎn)足夠接近。而當(dāng) 時(shí)，它就成為原約束問題的極小點(diǎn)。 懲罰函

19、數(shù)（4.12）也可改寫成另外的形式：XR21( ,)( ) min(0, ( ) (4.13)ljjP X Mf XMg X 或者：)14. 4( )()()(),(12ljjjjXguXgMXfMXP第122頁/共178頁 是階越函數(shù)：)(Xgujj0)( 1 0)( 0 )(XgXgXgujjjj當(dāng)當(dāng) 假定對某一罰因子，例如說 M1 , , 就加大罰因子的值。隨著罰因子數(shù)值的增加，懲罰函數(shù)中的懲罰項(xiàng)所起的作用隨之增大，minP(X,M) 的解 X(M) 離可行域 R 的“距離”就會(huì)越來越近，當(dāng)RMX)(1kMMM210趨于無窮大時(shí)，點(diǎn)列 X(Mk) 就從可行域 R 的外部趨于原非線性規(guī)劃問

20、題的極小點(diǎn)。第123頁/共178頁和不等式約束問題類似，對于等式約束問題，即：miXhXfi, 2 , 1 0)()(min采用以下形式的罰函數(shù)：miiXhMXfMXP12)()(),( 對于既包含等式約束又包含不等式約束的一般非線性規(guī)劃問題(4.1),其罰函數(shù)為)15. 4( )(, 0min()()(),(1212ljjmiiXgMXhMXfMXP或)16. 4( (X)()()()(),(1212jjljjmiiguXgMXhMXfMXP第124頁/共178頁罰函數(shù)法的迭代步驟如下：（1）取第一個(gè)罰因子 M1 0 (例如M1 =1），允許誤差 ，并令 k :=1 。（2）求下述無約束極值

21、問題的最優(yōu)解：其中P(X,Mk) 可取式（4.15)或(4.16)的形式。設(shè)其極小點(diǎn)為 X(k) 。（3）若存在某一個(gè) ，有或存在某一個(gè) ,有則取 Mk+1Mk ( 例如 Mk+1=cMk , c=10 )，并令 k:=k+1 。然后，0),(minkMXP) 1 ( ljj) 1 ( mii)()(kjXg | )(|)(kiXh第125頁/共178頁轉(zhuǎn)回第(2)步。否則，停止迭代，得所要的點(diǎn) X(k) 。障礙函數(shù)法( (內(nèi)點(diǎn)法） 罰函數(shù)法的一個(gè)重要特點(diǎn)，就是函數(shù) P(X,M) 可在整個(gè) En 空間內(nèi)進(jìn)行優(yōu)化，可以任意選擇初始點(diǎn)，這給計(jì)算帶來了很大方便。但由于迭代過程常常是在可行域外進(jìn)行，因

22、而不能以中間結(jié)果直接作為近似解使用。 如果要求每次的近似解都是可行解，以便觀察目標(biāo)函數(shù)值的改善情況；或者，如果目標(biāo)函數(shù)在可行域外的性質(zhì)比較復(fù)雜，甚至沒有定義，這時(shí)就無法使用上面所述的罰函數(shù)法了。 障礙函數(shù)法與罰函數(shù)法不同，它要求迭代過程始終在可行 第126頁/共178頁域內(nèi)部進(jìn)行。 考慮非線性規(guī)劃（4.3），當(dāng) X 點(diǎn)從可行域 R 內(nèi)部趨于其邊界時(shí)，至少有某一個(gè)約束函數(shù) 趨于零。從而，下述倒數(shù)函數(shù)和對數(shù)函數(shù)都將無限增大。如果把式 (4.17) 或 (4.18) 加到非線性規(guī)劃 (4.3)的目標(biāo)函數(shù)上，就能構(gòu)成新的目標(biāo)函數(shù)障礙函數(shù)。)1 ( )(ljXgj)17. 4( )(11ljjXg)18

23、. 4( )(lg(1ljjXg第127頁/共178頁或)19. 4( )(1)() 1 XgrXf(X,rPljjkk)20. 4( )(lg()() 1 XgrXf(X,rPljjkk 如果從某一點(diǎn) 出發(fā)，求下列無約束極小化問題)21. 4( ),(min0kRXrXP0)0(RX 則隨著障礙因子 的逐漸減小，即障礙項(xiàng)所起的作用也越來越小，因而，求出的問題（4.21）的kr021krrr第128頁/共178頁解 就會(huì)逐步逼近原約束問題 (4.3) 的極小解。)(krX障礙函數(shù)法的迭代步驟如下：（1）取第一個(gè)障礙因子 ，允許誤差 ，并令 k:=1 。（2）構(gòu)造障礙函數(shù)，可采取 (4.19)

24、或 (4.20) 。（3）對障礙函數(shù)進(jìn)行無約束極小化，設(shè)所得解為 。（4）檢查是否滿足收斂準(zhǔn)則：) 0 ( 011rr如00)(RXkljkjkXgr1)()(1或ljkjkXgr1)(|)(lg(|如果滿足此準(zhǔn)則，則以 X(k) 為原約束問題的近似極小解，停第129頁/共178頁止迭代；否則，取 rk+1 rk ，令 k:=k+1 , 轉(zhuǎn)回第（3）步繼續(xù)進(jìn)行迭代。第130頁/共178頁五五. . 動(dòng)態(tài)規(guī)動(dòng)態(tài)規(guī)劃劃 動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。該方法是由美國數(shù)學(xué)家貝爾曼等人在 20 世紀(jì) 50 年代初提出的。他們針對多階段決策問題的特點(diǎn)，提出了解決這類問題的最優(yōu)化原理，并

25、成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問題。 多階段決策問題的特點(diǎn)是整個(gè)決策過程可以分為好幾個(gè)彼此有聯(lián)系的階段，而每一個(gè)階段都有多于一個(gè)的小方案需要選擇確定，決策者需要在可供選擇的小方案中選出其中的一個(gè)最優(yōu)方案，使其效果在預(yù)定的目標(biāo)下達(dá)到最好。第131頁/共178頁A5BDFCE11121067一個(gè)簡單的多級(jí)決策：有某旅行者從 A 地出發(fā)到 F 地，可以選擇兩條路線，一是途經(jīng) B 地，D 地到 F ;另一是途經(jīng) C 地，E 地到 F (如圖),每段路程所需的費(fèi)用在圖中標(biāo)出。這個(gè)問題是以總旅費(fèi)達(dá)到最小作為目標(biāo)，顯然應(yīng)選擇：A C E F。 整個(gè)規(guī)劃的目標(biāo)是使得最終結(jié)果達(dá)到最優(yōu)，這就意味著

26、，某一段作出的決策，就這個(gè)階段來說，并不一定是一個(gè)最優(yōu)的選擇，甚至要作出某些犧牲（如上例第一段）。但是第132頁/共178頁由于各階段的相互影響，到最后卻會(huì)得到一個(gè)最優(yōu)的結(jié)果。相反，在這一階段選擇了一個(gè)最優(yōu)的決策，并不等于最后得到最優(yōu)結(jié)果，這就是動(dòng)態(tài)規(guī)劃的特點(diǎn)。 使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型，此時(shí)要用到以下概念：（1）階段；（2）狀態(tài)；（3）決策和策略；（4）狀態(tài)轉(zhuǎn)移；（5）指標(biāo)函數(shù)。 下面我們結(jié)合以下例題說明這些概念。例 5.1 最短路線問題。 如圖所示，給定一個(gè)線路網(wǎng)絡(luò)圖，要從 A 地向 F 地鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇第

27、133頁/共178頁什么線路，可使總距離最短？ A468335425B1B2E2FD1E1C1C2C3C4D3D2737835448431265（1）階段。 將所給問題的過程，按時(shí)間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解。 （2）狀態(tài)。 各階段開始時(shí)的客觀條件叫狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，sk 表示第 k 階段的狀態(tài)變量 ，sk 的取值集合稱為狀態(tài)集合，用 Sk 表示。第134頁/共178頁在例5.1中，各階段的狀態(tài)集合分別是： 當(dāng)某段的初始狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的鋪管路線只與該點(diǎn)有關(guān)，不受以前鋪管路線的影響，這叫狀態(tài)變量的“無后效性”，如果所選的狀

28、態(tài)變量不具備“無后效性”就不能用來構(gòu)造動(dòng)態(tài)規(guī)劃模型。, , , 2153214432132121EESDDDSCCCCSBBSAS（3）決策和策略。 當(dāng)各段的狀態(tài)取定以后，就可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。表示決策的變量，稱為決策變量，常用 uk(sk) 表示第 k 階段當(dāng)狀態(tài)為 sk 時(shí)的決第135頁/共178頁策變量，Dk(sk) 表示第 k 階段從狀態(tài) sk 出發(fā)的允許決策集合。 在例5.1中，有 D2(B1)=C1, C2, C3 如我們決定選擇 C3，則可表為： u2(B1)=C3 各段決策確定后，整個(gè)問題的決策序列就構(gòu)成一個(gè)策略，用 p1,n u1(s

29、1),u2(s2),un(sn)表示，P1,n 表示允許決策的集合，使整個(gè)問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。(4)狀態(tài)轉(zhuǎn)移方程。 動(dòng)態(tài)規(guī)劃中，如果給定了第 k 階段的狀態(tài) sk 和本階段決策 uk(sk) 則第 k+1 段的狀態(tài) sk+1 也就完全確定，它們的關(guān)第136頁/共178頁系可用下列狀態(tài)轉(zhuǎn)移方程表示： sk+1=Tk(sk,uk)例5.1中，狀態(tài)轉(zhuǎn)移方程為： sk+1=uk(sk)（5）指標(biāo)函數(shù)。 用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)。它分 為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)兩種。階段指標(biāo)函數(shù)是指第 k段，從狀態(tài) sk 出發(fā)，采取決策 uk 時(shí)的效益，用 d (sk,uk) 表示

30、。一個(gè) n 段的決策過程，從 1 到 n 叫做問題的原過程，對任意給定的 ,從第 k 段到第 n 段的過程稱為原過程的一個(gè)后部子過程。V1,n(s1,p1,n) 表示初始狀態(tài)為 (1)kkn第137頁/共178頁s1 采用策略 p1,n 時(shí)，后部子過程的指標(biāo)函數(shù)值，而Vk,n(sk,pk,n)表示在第 k 段，狀態(tài)為 sk 采用策略 pk,n時(shí) ，后部子過程的指標(biāo)函數(shù)值。最優(yōu)指標(biāo)函數(shù)記為 fk(sk) ,它表示從第 k 段狀態(tài) sk 采用最優(yōu)策略 到過程終止時(shí)的最佳效益值。即：當(dāng) k1 時(shí)， 就是從初始狀態(tài) 到全過程結(jié)束的整體最優(yōu)函數(shù)。 下面用動(dòng)態(tài)規(guī)劃方法求解例5.1 。本方法是從過程的最后一

31、段開始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn) F 的最短路線。*,k np,*,()(,)(,)k nk nkkk nkk nk nkk npPfsVspopt Vsp11( )f s1s第138頁/共178頁第一步：從 k=5 開始，狀態(tài)變量 s5 可取兩種狀態(tài) E1, E2, 它們到 F 點(diǎn)的路長分別為 4，3 。即：第二步：k=4，狀態(tài)變量可取三個(gè)值D1, D2, D3, 從 D1 到 F 有兩條路線，需要加以比較，取其中最短的，即：這說明 D1 到 F 最短距離為 7 , 其路徑為 D1 E1 F 。相應(yīng)決策 。5152()4 ()3fEfE735 43 min)(),( )()

32、,( min)(2521151114EfEDdEfEDdDf11*4)(EDu532 46 min)(),( )(),( min)(2522151224EfEDdEfEDdDf第139頁/共178頁即 D2 到 F 最短距離為 5 , 其路徑為 D2 E2 F 。相應(yīng)決策為 。即 D3 到 F 最短距離為 5 , 其路徑為 D3 E1 F 。相應(yīng)決策為 。類似地，可算得：*4()22uDE533 41 min)(),( )(),( min)(2523151334EfEDdEfEDdDf13*4)(EDu34*34323*33322*32311*313)( 9)( )( 8)( )( 10)(

33、)( 12)( 3DCuCfDCuCfDCuCfDCuCfk時(shí)，有第140頁/共178頁FEDCBAFEuEDuDCuCBuBAuuBAuFABfBAdBfBAdAfCBuBfCBuBfkk22212*522*422*321*21*11*1222121132*22221*212 )( ,)( ,)( ,)( ,)(: , . )( 17 17155 134 min)(),( )(),( min)( A 1k)( 15)( )( 13)( 2所以最優(yōu)路線為：即最優(yōu)決策序列在按計(jì)算順序反推可得。本段決策為的最短距離為到即從，則只有一個(gè)狀態(tài)點(diǎn)時(shí)，時(shí)，有第141頁/共178頁。轉(zhuǎn)移關(guān)系有遞推的狀態(tài)證各

34、階段的狀態(tài)變量具正確選擇狀態(tài)變量，保的關(guān)鍵又在于建立基本遞推關(guān)系方程的若干子問題，而正確系式聯(lián)系起來題分解成為可用遞推關(guān)題的多階段特征，將問，在于識(shí)別問用動(dòng)態(tài)規(guī)劃方法的關(guān)鍵劃基本方程。成功地應(yīng)的動(dòng)態(tài)規(guī)是分析問題并建立問題建立動(dòng)態(tài)規(guī)劃模型，就規(guī)劃的基本方程。這種遞推關(guān)系稱為動(dòng)態(tài)段的如下關(guān)系：段和第第利用了，在求解的各階段，都的計(jì)算過程中可以看出從例 ),( 0)(1 , 2 , 3 , 4 , 5 )(),(min)( 1 1 . 516611kkkkkkkkkukkusTssfksfusdsfkkk第142頁/共178頁全渡河那？人怎樣才能安掌握在商人們手中。商是如何乘船渡河的大權(quán)殺人越貨。但

35、從的人數(shù)比商人多，就在河的任一岸，一旦隨。隨從們密約，二人，由他們自己劃行河，一只小船只能容納從乘船渡）三名商人各帶一個(gè)隨（商人們怎樣安全過河例成最優(yōu)策略”。其以后的所有決策應(yīng)構(gòu)的狀態(tài)而言，對于先前決策所形成始狀態(tài)及初始決策如何質(zhì)：即無論初最優(yōu)策略具有這樣的性表述為：“一個(gè)過程的理，它可曼等人提出的最優(yōu)化原動(dòng)態(tài)規(guī)劃方法基于貝爾 2 . 5 第143頁/共178頁 3名商人 3名隨從問題分析問題分析: 安全渡河問題可以視為一個(gè)多步?jīng)Q策過程。每一步，即船由此岸到彼岸或從彼岸駛回此岸，都要對船上的人員（商人、隨從各幾人）作出決策，在保證安全的前提下（兩岸的隨從數(shù)都河小船(至多2人)不比商人數(shù)多），在

36、有限步內(nèi)全部人員過河。用狀態(tài)變量表示某一岸的人員狀況，決策變量表示船上的人員狀況，于是可以找出狀態(tài)隨決策變化的規(guī)律。第144頁/共178頁模型構(gòu)成模型構(gòu)成xk第k次渡河前此岸的商人數(shù)yk第k次渡河前此岸的隨從數(shù)xk, yk=0,1,2,3; k=1,2, sk=(xk , yk)過程的狀態(tài)（向量）S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2S 允許狀態(tài)集合uk第k次渡船上的商人數(shù)vk第k次渡船上的隨從數(shù)dk=(uk , vk)決策D=(u , v) u+v=1, 2 允許決策集合uk, vk=0,1,2; k=1,2, sk+1=sk dk

37、 +(-1)k狀態(tài)轉(zhuǎn)移律求dk D(k=1,2, n), 使sk S, 并按轉(zhuǎn)移律由 s1=(3,3)到達(dá) sn+1=(0,0).多步?jīng)Q策多步?jīng)Q策問題問題第145頁/共178頁模型求解模型求解xy3322110 窮舉法 編程上機(jī) 圖解法圖解法狀態(tài)s=(x,y) 16個(gè)格點(diǎn) 10個(gè) 點(diǎn)允許決策 移動(dòng)1或2格; k奇,左下移; k偶,右上移.s1sn+1d1, ，d11給出安全渡河方案 同學(xué)們還可以進(jìn)一步考慮 4 名商人各帶一隨從的情況（小船同前）。d1d11允許狀態(tài)S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2第146頁/共178頁), 1(m

38、iAi), 1(njXjj1 , 101njjj：評(píng)價(jià)對象（可替代且非劣的方案）：評(píng)價(jià)指標(biāo)（準(zhǔn)則、項(xiàng)目）：評(píng)價(jià)指標(biāo)權(quán)重，1、關(guān)聯(lián)矩陣法綜合評(píng)價(jià)方法第147頁/共178頁 n21Vi X1 X2 Xn mjjjmjjjnjjjVVVVVV22111XjjVijAi?ijVij = ?逐對比較法、古林法 A1A2AmV11 V12 V1nV21 V22 V2nVm1 Vm2 Vmn . . .第148頁/共178頁評(píng)價(jià)指標(biāo)Xj替代方案Ai期望利潤（萬元）產(chǎn)品成品率（%）市場占有率（%）投資費(fèi)用（萬元）產(chǎn)品外觀自行設(shè)計(jì)（A1）6509530110美 觀國外引進(jìn)（A2）7309735180比較美觀改

39、建（A3）520922550美 觀 方案預(yù)期結(jié)果例表第149頁/共178頁評(píng)價(jià)指標(biāo)得分序號(hào)累計(jì)得分權(quán)重12345678910期望利潤（X1）1111 40.4產(chǎn)品成品率（X2）0 111 30.3市場占有率（X3） 0 0 01 10.1投資費(fèi)用（X4） 0 0 1 120.2產(chǎn)品外觀（X5） 0 0 0000.0 逐對比較法例表 第150頁/共178頁評(píng)價(jià)尺度(得分)評(píng)價(jià)指標(biāo)54321期望利潤（萬元）800以上701-800601-700501-600500以下產(chǎn) 品 成 品 率（%）97以上96-9791-9586-9085以下市 場 占 有 率（%）40以上35-3930-3425-29

40、25以下投資費(fèi)用（萬元）20以下21-8081-120121-160160以上產(chǎn)品外觀非常美觀美觀比較美觀一般不美觀 評(píng)價(jià)尺度例表 第151頁/共178頁VijAij 期望利潤產(chǎn)品成品率市場占有率投資費(fèi)用產(chǎn)品外觀Vi0.40.30.10.20.0自行設(shè)計(jì)(A1)333343.0國外引進(jìn)(A2)444133.4改建(A3)232442.7Xj 關(guān)聯(lián)矩陣表（逐對比較法）第152頁/共178頁j341/2序號(hào)評(píng)價(jià)指標(biāo)RjKj1期望利潤180.5802產(chǎn)品成品率60.1943市場占有率20.0654投資費(fèi)用40.1295產(chǎn)品外觀10.032合計(jì)311.0003Rj Kj Wj 基準(zhǔn)化 歸一化 古林法求

41、j 例表第153頁/共178頁序號(hào)（j）評(píng)價(jià)指標(biāo)替代方案RijKijVij1期望利潤A10.8901.2500.342A21.4041.4040.384A31.0000.2742產(chǎn)品成品率A10.9791.0320.334A21.0541.0540.342A31.0000.324 古林法求Vij例表第154頁/共178頁3市場占有率A10.8571.2000.333A21.4001.4000.389A31.0000.2784投資費(fèi)用A11.6360.4550.263A20.2870.2870.160A31.0000.5775產(chǎn)品外觀A11.3331.0000.364A20.7500.7500.

42、272A31.0000.364 古林法求Vij例表（續(xù)）第155頁/共178頁VijAij期望利潤產(chǎn)品成品率市場占有率投資費(fèi)用產(chǎn)品外觀Vi0.5800.1940.0650.1290.032A10.3420.3840.2740.3340.3420.3240.3330.3890.2780.2630.1600.5770.3640.2720.3640.3300.3340.326A2A3Xj 關(guān)聯(lián)矩陣?yán)恚ü帕址ǎ┑?56頁/共178頁Analytic Hierarchy ProcessAHP（美國運(yùn)籌學(xué)家、匹茲堡大學(xué)教授）投資效果好（T）風(fēng)險(xiǎn)程度（I1）資金利潤率（I2）轉(zhuǎn)產(chǎn)難易程度（I3）產(chǎn)品1（P

43、1）產(chǎn)品2（P2）產(chǎn)品3（P3）（目的層）（準(zhǔn)則層）（方案層）三、層次分析（AHP）法第157頁/共178頁判斷矩陣標(biāo)度定義 標(biāo)度含義1兩個(gè)要素相比，具有同樣重要性3兩個(gè)要素相比，前者比后者稍微重要5兩個(gè)要素相比，前者比后者明顯重要7兩個(gè)要素相比，前者比后者強(qiáng)烈重要9兩個(gè)要素相比，前者比后者極端重要2，4，6，8上述相鄰判斷的中間值倒數(shù)兩個(gè)要素相比，后者比前者的重要性標(biāo)度 AHP方法的基本工具判斷矩陣第158頁/共178頁TI1I2I3WiWioI111/320.8740.230I23152.4660.648I31/21/510.4640.122(3.804) 注 Wi的求取采用方根法（求根法

44、或稱幾何平均值法） I1P1P2P3WiWioP111/31/50.4060.105P2311/31.0000.258P35312.4660.637 判斷矩陣及其分析處理舉例第159頁/共178頁I2P1P2P3WiWioP11272.4100.592P21/2151.3570.333P31/71/510.3060.075I3P1P2P3WiWioP111/31/70.3620.081P2311/50.8430.188P37513.2710.731 判斷矩陣及其分析處理舉例（續(xù)）第160頁/共178頁 求綜合重要度（加權(quán)和） T I1 I2 I3 綜合綜合 重要度重要度 權(quán)重權(quán)重 0.230

45、0.648 0.122（加權(quán)和）（加權(quán)和） P1 0.105 0.592 0.149 0.426 P2 0.258 0.333 0.066 0.283 P3 0.637 0.075 0.785 0.291第161頁/共178頁（1）分析評(píng)價(jià)系統(tǒng)中各基本要素之間的關(guān)系，建立系統(tǒng)的遞階層次結(jié)構(gòu)（分解法）；（2）對同一層次的各要素關(guān)于上一層次中某一準(zhǔn)則的重要性進(jìn)行兩兩比較，構(gòu)造判斷矩陣（專家調(diào)查法）；（3）由判斷矩陣計(jì)算被比較要素對于該準(zhǔn)則的相對權(quán)重（方根法）；（4）計(jì)算各層要素相對于系統(tǒng)目的（總目標(biāo)）的合成（總）權(quán)重，并據(jù)此對方案等排序（加權(quán)和法）。AHP方法步驟第162頁/共178頁 課程： 教

46、師： 班級(jí)： 評(píng)價(jià)項(xiàng)目（權(quán)重）好（100）較好(85)一般（70）較差（55）1.教學(xué)計(jì)劃及教學(xué)內(nèi)容安排（0.10）9 0.3614 0.562 0.080 0.002.教材及參考資料狀況(0.10)3 0.1214 0.567 0.281 0.043.教師教學(xué)態(tài)度及責(zé)任心(0.15)5 0.2015 0.605 0.200 0.004.教師講解能力（0.10）1 0.0410 0.4011 0.443 0.12評(píng)價(jià)結(jié)果(票數(shù)/隸屬度) ) 評(píng)價(jià)等級(jí)四、模糊綜合評(píng)判法（1）第163頁/共178頁5.課堂教學(xué)形式的多樣化程度（0.10）2 0.0811 0.4412 0.480 0.006.理論

47、聯(lián)系實(shí)際程度及教學(xué)案例使用情況（0.10）5 0.2014 0.566 0.240 0.007.輔助教學(xué)環(huán)節(jié)及考核情況(0.10)4 0.166 0.2413 0.522 0.088.教學(xué)改革與創(chuàng)新情況(0.10)3 0.128 0.3212 0.482 0.089.從本課程學(xué)習(xí)中所獲得的收益程度（0.15）5 0.2012 0.486 0.242 0.08綜合評(píng)價(jià)結(jié)果綜合隸屬度 0.168 0.470 0.318 0.044綜合得分81.43四、模糊綜合評(píng)判法（2）第164頁/共178頁49)(ijrR91)(iwW41)(jdDTDS 隸屬度 rij 指多個(gè)評(píng)價(jià)主體對某個(gè)評(píng)價(jià)對象在第i個(gè)項(xiàng)

48、目下作出第j等級(jí)評(píng)定的可能性程度。 若記：隸屬度矩陣為 評(píng)價(jià)項(xiàng)目權(quán)重向量為 評(píng)價(jià)等級(jí)分值向量為 則有：綜合隸屬度向量 S=WR綜合得分 四、模糊綜合評(píng)判法（3）第165頁/共178頁 動(dòng)態(tài)規(guī)劃模型常被用來求解經(jīng)濟(jì)管理中的貨物存儲(chǔ)、動(dòng)態(tài)規(guī)劃模型常被用來求解經(jīng)濟(jì)管理中的貨物存儲(chǔ)、設(shè)備更新、資源分配、任務(wù)均衡、水庫調(diào)度、系統(tǒng)可靠性設(shè)備更新、資源分配、任務(wù)均衡、水庫調(diào)度、系統(tǒng)可靠性等問題，在離散系統(tǒng)最優(yōu)控制中也有廣泛應(yīng)用。等問題，在離散系統(tǒng)最優(yōu)控制中也有廣泛應(yīng)用。動(dòng)態(tài)規(guī)劃模型的主要缺點(diǎn)是：動(dòng)態(tài)規(guī)劃模型的主要缺點(diǎn)是：1.1. 沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有萬能的構(gòu)造模型的沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有萬能的構(gòu)造

49、模型的 方法，方法，需要對每類問題具體分析。在定義狀態(tài)變量、建立狀態(tài)轉(zhuǎn)需要對每類問題具體分析。在定義狀態(tài)變量、建立狀態(tài)轉(zhuǎn)移率等方面，需要靈活技巧，這就帶來了應(yīng)用上的局限性。移率等方面，需要靈活技巧，這就帶來了應(yīng)用上的局限性。2.2. 用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)。由于狀態(tài)個(gè)數(shù)隨維數(shù)呈指用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)。由于狀態(tài)個(gè)數(shù)隨維數(shù)呈指數(shù)增長，對高維問題求解十分困難。數(shù)增長，對高維問題求解十分困難。第166頁/共178頁六六. . 最優(yōu)控制理論最優(yōu)控制理論 最優(yōu)控制理論是從20世紀(jì)50年代末60年代初發(fā)展起來的現(xiàn)代控制理論的一個(gè)重要分支。它最初研究的對象是由導(dǎo)彈、航天、航空、航海中的制導(dǎo)、導(dǎo)航和控

50、制中所總結(jié)出來的一類按某個(gè)性能指標(biāo)取最優(yōu)（極小或極大）的控制問題。其核心問題是如何為被控制系統(tǒng)選擇一個(gè)控制策略，使得被控制系統(tǒng)本身獲得優(yōu)良的技術(shù)品質(zhì)和滿意的經(jīng)濟(jì)效益。今天，最優(yōu)控制理論的研究，無論在深度和廣度上都有了較大的發(fā)展，諸如分布參數(shù)系統(tǒng)的最優(yōu)控制、隨機(jī)系統(tǒng)的最優(yōu)控制、大系統(tǒng)的最優(yōu)控制、微分對策等許多方面都是當(dāng)前極其活躍的科學(xué)研究領(lǐng)域。6.1 6.1 控制工程中的幾個(gè)實(shí)際問題 為了更好地說明最優(yōu)控制問題，我們給出幾個(gè)工程控制中的實(shí)例。第167頁/共178頁例6.1 （升降機(jī)的最快升降問題）一個(gè)內(nèi)部帶控制器的物體 M ，其質(zhì)量為 1 。常重力加速度 g 垂直向下作用到M 的質(zhì)心上，控制器可提供一個(gè)作用于 M 使其垂直上升或下降的加速度 。設(shè) 和 分別表示 t0 時(shí)刻質(zhì)心距地面的垂直距離和垂直運(yùn)動(dòng)速度。我們的問題是如何選擇 ，使 M 從初始時(shí)刻 t0 的初態(tài) 最快地到達(dá)終端時(shí)刻 tf 的末態(tài) (到