數(shù)學(xué)規(guī)劃的理論與方法

1、 數(shù)學(xué)規(guī)劃的理論與方法數(shù)學(xué)規(guī)劃的理論與方法 1. 線性規(guī)劃理論與方法線性規(guī)劃理論與方法 2. 目標(biāo)規(guī)劃的理論與方法目標(biāo)規(guī)劃的理論與方法 3. 整數(shù)規(guī)劃的理論與方法整數(shù)規(guī)劃的理論與方法 4. 非線性規(guī)劃的理論與方法非線性規(guī)劃的理論與方法 5. 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 6. 最優(yōu)控制理論最優(yōu)控制理論 y 一一. .線性規(guī)劃的理論與方法線性規(guī)劃的理論與方法 線性規(guī)劃是指目標(biāo)函數(shù)是由線性函數(shù)給出，約 束條件由線性等式或者不等式給出的優(yōu)化問題。 最早提出線性規(guī)劃問題并進(jìn)行專門研究的學(xué) 者康托洛維奇。 康托洛維奇在20世紀(jì)30年代就提出了求解線 性規(guī)劃問題的“解乘數(shù)法”。 自從1947年美國學(xué)者丹青格提出求解線

2、性 規(guī)劃問題的一般方法單純形方法 后，才使線 性規(guī)劃的理論和方法日臻成熟。 （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.11.1 甲乙限額 材料2324 工時(shí)3226 利潤(元/件)43 設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為 x1 , x2 則該 問題可描述為由如下數(shù)學(xué)模型： 0,

3、2623 2432 . 34max 21 21 21 21 xx xx xx ts xxz 1.2 線性規(guī)劃問題的標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)型 如下形式的線性規(guī)劃模型被稱作標(biāo)準(zhǔn)型: ),2, 1( 0 ),2, 1( . max 1 1 njx mibxa ts xcz j n j ijij n j jj 也可用矩陣形式描述: 0 bax . max x ts cxz a:資源消耗系數(shù)矩陣 b: 資源限量向量 c:價(jià)格向量 x:決策變量向量 同時(shí)我們對標(biāo)準(zhǔn)型作如下假定: . 1 , 0 , 0 )2( . , ,)( ) 1 ( 即可乘以 個(gè)約束方程兩邊同時(shí)則可對第若有 沒有多余方程 彼此獨(dú)立即

4、標(biāo)準(zhǔn)型中的約束方程 ibb nmarank i 一般的線性規(guī)劃問題通過變換可化成標(biāo)準(zhǔn)型 , 變 換方式可以歸結(jié)為: . ) max( ) max() min( :, ) 1 ( 即可這樣我們只要討論問題 可以通過以下方式得到如果目標(biāo)函數(shù)是極小化 . 0 , 0 , ) 3( )0( , . )0( , . . , )2( kk kkkk zy zyxx b a 其中 則可令無非負(fù)性限制如果變量 該松弛變量右端某松弛變量不等式左端 則如果約束條件為 該松弛變量右端某松弛變量不等式左端 則如果約束條件為 變量來得到 我們可以通過引進(jìn)松弛如果約束方程為不等式 1.3 線性規(guī)劃問題解的概念線性規(guī)劃問題

5、解的概念 對于線性規(guī)劃問題 )3.1( ),2, 1( 0 )2.1( ),2, 1( . )1.1( max 1 1 njx mibxa ts xcz j n j ijij n j jj . ) 1 . 1 ( : . ),( ) 3 . 1 ( ) 2 . 1 ( : 21 的可行解稱為最優(yōu)解滿足最優(yōu)解 稱為可行解 的解和滿足約束條件可行解 t xxx 題的一個(gè)基。 是線性規(guī)劃問則稱階非奇異子矩陣 中的一個(gè)是矩陣如果基：設(shè) , )0|(| , )( bb mmabmarank nm 個(gè)非基向量。有 中共，之外各列即為非基向量中除矩陣 ，中的列向量稱為基向量基向量與非基向量：基 mn aba

6、 b 基變量。為基變量；否則稱為非 稱對應(yīng)的變量基向量基變量與非基變量：與 jj xp 稱為基解。 的解，求出的滿足為基解：令所有非基變量 )2 . 1 ( 0 )3 . 1 ( m n c 基解的數(shù)目解的數(shù)目 基可行為可行基。顯然，對應(yīng)基可行解的基，稱 的基解稱為基可行解。足基可行解與可行基：滿 優(yōu)基。 為最對應(yīng)基本最優(yōu)解的基稱 優(yōu)解，的基可行解稱為基本最 滿足基本最優(yōu)解與最優(yōu)基： ) 1 . 1 ( 可行解 基 解 基可行解 1.4 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法 下面結(jié)合例1的求解來說明圖解法步驟。 0, 2623 2432 . 34max 21 21 21 21 xx xx

7、xx ts xxz例1 第一步：在直角坐標(biāo)系中分 別作出各種約束條件，求出 可行域（圖中陰影部分）。 x2 q2(6,4) x1 3x1+2x2=26 2x1+3x2=24 z oq1(26/3,0) q3(6,4) 為則稱點(diǎn) 連線上的一切任意兩點(diǎn) 中的一個(gè)點(diǎn)集，若維歐氏空間是設(shè)定義 ，先介紹兩個(gè)概念。為介紹基本定理的需要 , ) 10( )1 ( )(, 1 . 1 )2()1( )2()1()2()1( kkxxx xxkxx enk n 第二步：作出一條目標(biāo)函數(shù)等值線，并確定 z 值增 大的方向。 第三步：沿 z 值增大方向移動(dòng)，當(dāng)移至 q2(6,4) 點(diǎn) 時(shí)，z 值為最大，z*=36

8、. 1.5 基本定理基本定理 . 凸集 . , 1 . 1 域必為凸集 則其可行空可行域若線性規(guī)劃問題存在非定理 的一個(gè)為則稱 的線性組合表示為點(diǎn) 若不能用兩個(gè)不同的是凸集，設(shè)定義 , ) 10( )1 ( , ; 2 . 1 )2( )1()2()1( kxkx xxkxkx kxk . 極點(diǎn) . , 2 . 1 可行域的極點(diǎn)上達(dá)到數(shù)最優(yōu)值一定可以在其 則其目標(biāo)函域有界若線性規(guī)劃問題的可行定理 . 3 . 1 的極點(diǎn) 對應(yīng)于可行域解線性規(guī)劃問題的基可行定理x 從理論上來講,采用“枚舉法”找出所有基可行解, 并 1.6 求解求解線性規(guī)劃問題的單純形方法線性規(guī)劃問題的單純形方法 一一比較,一定會(huì)

9、找到最優(yōu)解。但當(dāng) m, n 較大時(shí),這 種方法是不經(jīng)濟(jì)和不可取的。 下面介紹求解線性規(guī)劃問題的有效方法單純 形方法。單純形法的實(shí)質(zhì)是從一個(gè)基可行解向另一個(gè) 基可行解（極點(diǎn)到極點(diǎn)）的迭代方法。 以下通過例1的求解過程說明單純形方法的基本 步驟。 0, 2623 2432 . 34max 21 21 21 21 xx xx xx ts xxz 例1： 第一步：第一步：引進(jìn)松馳變量 x3 , x4 將原問題化為標(biāo)準(zhǔn)型。 0, 26 23 24 32 . 0034max 4321 421 321 4321 xxxx xxx xxx ts xxxxz 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 第二步：第二步：找出初始可行基，建立初

10、始單純形表。 見下表1.2。 cj 4 3 0 0 cbxbb x1 x2 x3 x4 0 0 x3 x4 24 26 2 3 1 0 3 2 0 1 z0 -4 -3 0 0 表 1.2 bbbippb 1 0430 ),( 則本例中，初始可行基 第三步：第三步：最優(yōu)性檢驗(yàn)。 可能有下面三種情況： 的檢驗(yàn)數(shù)檢驗(yàn)各非基變量 , jj x i j 行換基迭代。 四步，進(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

11、 0 ) 3( , 0), , 0 )2( , 0 ) 1 ( 21 j msss s j aaa b 量。所在的列變?yōu)閱挝涣邢蚣窗鸦兞?進(jìn)行初等行變換，為主元，在單純形表中以 為主元。為出基變量，其中確定 元按最小比值原則求出主確定換出變量 取 確定換入變量 )3( ,0|min : )2( . 0 , 0|min : ) 1 ( s rs rsr rs r is is i i r j s x a ax a b a a b x njjs x 第四步：第四步：換基迭代。 的單純形表。 ，得到新的可行基和新?lián)Q為中的同時(shí)將 srb xxx 有無界解，計(jì)算終止。 出至獲得最優(yōu)解，或判斷重復(fù)第三、第

12、四步，直 所在行的交叉處所在列和換出基變量，并以 為確定， 為換入變量。所以 ，因?yàn)閬碚f，對于表針對例 3 26 3 26 , 2 24 0|min 13, 4|min : 2 . 1 1 41 4 121 xx xa a b xjs is is i i i 元素為主元進(jìn)行迭代。 cj 4 3 0 0 cbxbb x1 x2 x3 x4 0 0 x3 x4 24 26 2 3 1 0 3 2 0 1 12 26/3 z0 -4 -3 0 0 0 4 x3 x1 20/3 26/3 0 5/3 1 -2/3 1 2/3 0 1/3 4 13 z104/3 0 -1/3 0 4/3 表1.3 i

13、j j 同理，確定 x2 換入，x3 換出，繼續(xù)迭代得表 1.3 cj 4 3 0 0 cbxbb x1 x2 x3 x4 3 4 x2 x1 4 6 0 1 3/5 -2/5 1 0 -2/5 3/5 z36 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*=36 。 j i 例2 一奶制品加工廠用牛奶生產(chǎn) a1 , a2 兩種奶制品，1 桶牛 奶可以在設(shè)備甲上用 12 小時(shí)加工成 3 公斤 a1,或

14、者在設(shè)備 乙上用 8 小時(shí)加工成 4 公斤 a2。根據(jù)市場需求，生產(chǎn)的 a1 , a2 全部能售出，且每公斤 a1 獲利 24 元，每公斤 a2 獲利 16 元。現(xiàn)在加工廠每天能得到 50 桶牛奶的供應(yīng)，每天正式工人 總的勞動(dòng)時(shí)間為 480 小時(shí)，并且設(shè)備甲每天至多能加工 100 公斤 a1 , 設(shè)備乙的加工能力沒有限制。試為該廠制定一個(gè) 我們無意過深涉及線性規(guī)劃的具體計(jì)算方法，而著重介 紹的是如何建立若干實(shí)際的線性規(guī)劃模型，如何使用現(xiàn)成的 數(shù)學(xué)軟件進(jìn)行求解，以及如何對結(jié)果進(jìn)行深入的分析。 下面以奶制品加工生產(chǎn)計(jì)劃為例，進(jìn)行詳細(xì)的討論。 生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下 3 個(gè)附加問

15、題： 若用 35 元可買到 1 桶牛奶，買嗎？若買，每天最多 買多少? 若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人 的工資最多是每小時(shí)幾元? 由于市場需求的變化，a1 的獲利增加到 30元/公斤， 應(yīng)否改變生產(chǎn)計(jì)劃？ 1桶 牛奶 3公斤a1 12小時(shí) 8小時(shí) 4公斤a2 或 獲利24元/公斤 獲利16元/公斤 50桶牛奶 時(shí)間480小時(shí) 至多加工100公斤a1 每天： 分析 x1 桶牛奶生產(chǎn) a1 x2 桶牛奶生產(chǎn) a2 獲利 243x1 獲利 164 x2 決策變量決策變量 0, 1003 480812 50 . 6472 21 1 21 21 21 xx x xx xx ts xxzm

16、ax 數(shù)學(xué)模型 原料供應(yīng)原料供應(yīng) 勞動(dòng)時(shí)間勞動(dòng)時(shí)間 加工能力加工能力 非負(fù)約束非負(fù)約束 解法1：圖解法。 x1 x2 0 a b c d l1 l2 l3 l4 l5 50 21 xx 480812 21 xx 1003 1 x 0, 21 xx 約約 束束 條條 件件 50: 211 xxl 480812: 212 xxl 1003: 13 xl 0:, 0: 2514 xlxl 21 6472xxzmax z=0 z=2400 z=3360 c 從圖中可以看出，在 b(20,30) 點(diǎn)得到最優(yōu)解。 解法2：軟件實(shí)現(xiàn)。求解線性規(guī)劃有不少現(xiàn)成的數(shù)學(xué)軟件，比 如用 lindo 軟件就可以很方便地

17、實(shí)現(xiàn)。在 lindo6.1版本下打 開一個(gè)新文件，像書寫模型一樣。直接輸入： max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end 注：lindo中已規(guī)定所有決策變量均為 非負(fù)，故變量非負(fù)的條件不必輸入。輸 入文件中第1行為目標(biāo)函數(shù)，2),3),4) 是為了標(biāo)示各約束條件，便于從輸出結(jié) 果中查找相應(yīng)信息；程序最后以end 結(jié) 束。 將文件存儲(chǔ)并命名后，選擇菜單 “solve” 并對提示 “ do range(sensitivity)analysis? ”回答“是”，即 可得到如下輸出： objective function value 1)

18、 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 20桶牛奶生產(chǎn)桶牛奶生產(chǎn)a1, 30桶生產(chǎn)桶生產(chǎn)a2，利潤，利潤3360元。元。 原料無剩余原料無剩余 時(shí)間無剩余時(shí)間無剩余 加工能力剩余加工能力剩余40 三三 種種 資資 源源 “資源資源” 剩余剩余

19、為零的約束為為零的約束為 緊約束（有效緊約束（有效 約束）約束） 結(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)解下最優(yōu)解下“資源資源”增加增加 1單位時(shí)單位時(shí)“效益效益”的

20、增的增 量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時(shí)間增加時(shí)間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤 影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 0 ,并將各個(gè)約束條件加到 目標(biāo)函數(shù)上，得一新函數(shù)如下： 1 ( ,)( ) ( ) (4.12) l j j p x mf xmg x 可以看出，當(dāng) 時(shí)，有 ；當(dāng) 時(shí)，由于m 很大，將使 很大，從而使 xr( ,)( )p x mf xxr 1 ( ) l j j mg x ( ,)p x m 很大，這就相當(dāng)于對非可行點(diǎn)的“懲罰”。而且，x 點(diǎn)離可行 域

21、 越遠(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)。 懲罰函數(shù)（4.12）也可改寫成另外的形式： xr 2 1 ( ,)( ) min(0, ( ) (4.13) l j j p x mf xmg x 或者： )14. 4( )()()(),( 1 2 l j jjj xguxgmxfmxp 是階越函數(shù)： )(xgu jj 0)( 1 0)( 0 )( xg xg xgu j j jj 當(dāng) 當(dāng) 假定對某一罰因子，例如說 m1 , , 就加大罰因 子的

22、值。隨著罰因子數(shù)值的增加，懲罰函數(shù)中的懲罰項(xiàng)所起 的作用隨之增大，minp(x,m) 的解 x(m) 離可行域 r 的“距離” 就會(huì)越來越近，當(dāng) rmx)( 1 k mmm 21 0 趨于無窮大時(shí)，點(diǎn)列 x(mk) 就從可行域 r 的外部趨于原非 線性規(guī)劃問題的極小點(diǎn)。 和不等式約束問題類似，對于等式約束問題，即： mixh xf i , 2 , 1 0)( )(min 采用以下形式的罰函數(shù)： m i i xhmxfmxp 1 2 )()(),( 對于既包含等式約束又包含不等式約束的一般非線性規(guī) 劃問題(4.1),其罰函數(shù)為 )15. 4( )(, 0min()()(),( 1 2 1 2 l

23、 j j m i i xgmxhmxfmxp 或 )16. 4( (x)()()()(),( 1 2 1 2 jj l j j m i i guxgmxhmxfmxp 罰函數(shù)法的迭代步驟如下： （1）取第一個(gè)罰因子 m1 0 (例如m1 =1），允許誤差 ， 并令 k :=1 。 （2）求下述無約束極值問題的最優(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 ),(min k mxp ) 1 ( ljj

24、) 1 ( mii )( )(k j xg | )(| )(k i xh 轉(zhuǎn)回第(2)步。 否則，停止迭代，得所要的點(diǎn) x(k) 。 4.6.2 4.6.2 障礙函數(shù)法障礙函數(shù)法( (內(nèi)點(diǎn)法）內(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)行，因而不能以中 間結(jié)果直接作為近似解使用。 如果要求每次的近似解都是可行解，以便觀察目標(biāo)函數(shù)值 的改善情況；或者，如果目標(biāo)函數(shù)在可行域外的性質(zhì)比較復(fù)雜， 甚至沒有定義，這時(shí)就無法使用上面所述的罰函數(shù)法了。 障礙函數(shù)法與罰函數(shù)法不同，它要求

25、迭代過程始終在可行 域內(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 ( )(ljxg j )17. 4( )( 1 1 l j j xg )18. 4( )(lg( 1 l j j xg 或 )19. 4( )( 1 )() 1 xg rxf(x,rp l j j kk )20. 4( )(lg()() 1 xgrxf(x,rp l j jkk 如果從某一點(diǎn) 出

26、發(fā)，求下列無約束極小化問題 )21. 4( ),(min 0 k rx rxp 0 )0( rx 則隨著障礙因子 的逐漸減小，即 障礙項(xiàng)所起的作用也越來越小，因而，求出的問題（4.21）的 k r 0 21 k rrr 解 就會(huì)逐步逼近原約束問題 (4.3) 的極小解。)( k rx 障礙函數(shù)法的迭代步驟如下： （1）取第一個(gè)障礙因子 ，允許誤差 ， 并令 k:=1 。 （2）構(gòu)造障礙函數(shù)，可采取 (4.19) 或 (4.20) 。 （3）對障礙函數(shù)進(jìn)行無約束極小化，設(shè)所得解為 。 （4）檢查是否滿足收斂準(zhǔn)則： ) 0 ( 0 11 rr如 0 0 )( rx k l j k j k xg r

27、 1 )( )( 1 或 l j k jk xgr 1 )( |)(lg(| 如果滿足此準(zhǔn)則，則以 x(k) 為原約束問題的近似極小解，停 止迭代；否則，取 rk+1 rk ，令 k:=k+1 , 轉(zhuǎn)回第（3）步繼續(xù)進(jìn) 行迭代。 五五. . 動(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)化原理，并成功地解 決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問題。 多階段決策問題的特點(diǎn)是整個(gè)決策過程可以分為 好幾個(gè)彼此有聯(lián)系的階段，而每一個(gè)階段都有多于一 個(gè)的小

28、方案需要選擇確定，決策者需要在可供選擇的 小方案中選出其中的一個(gè)最優(yōu)方案，使其效果在預(yù)定 的目標(biāo)下達(dá)到最好。 a 5 b d f ce 11 12 10 6 7 一個(gè)簡單的多級決策：有某 旅行者從 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)，這就意味 著，某一段作出的決策，就這個(gè)階段來說，并不一定是一個(gè) 最優(yōu)的選擇，甚至要作出某些犧牲（如上例第一段）。但是 由于各階段的相互影響

29、，到最后卻會(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)選擇 什么線路，可使總距離最短？ a 4 6 8 3 3 5 4 2 5 b1 b2e2 f d1 e1 c1 c2 c3 c4 d3

30、d2 7 3 7 8 3 5 4 4 8 4 3 1 2 6 5 （1）階段。 將所給問題的過 程，按時(shí)間或空間特 征分解成若干互相聯(lián) 系的階段，以便按次 序去求每階段的解。 （2）狀態(tài)。 各階段開始時(shí)的客觀條件叫狀態(tài)。描述各階段狀態(tài)的變量 稱為狀態(tài)變量，sk 表示第 k 階段的狀態(tài)變量 ，sk 的取值集合 稱為狀態(tài)集合，用 sk 表示。 在例5.1中，各階段的狀態(tài)集合分別是： 當(dāng)某段的初始狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的鋪管 路線只與該點(diǎn)有關(guān)，不受以前鋪管路線的影響，這叫狀態(tài)變量 的“無后效性”，如果所選的狀態(tài)變量不具備“無后效性”就 不能 用來構(gòu)造動(dòng)態(tài)規(guī)劃模型。 , , , , 2153

31、214 432132121 eesddds ccccsbbsas （3）決策和策略。 當(dāng)各段的狀態(tài)取定以后，就可以作出不同的決定，從而確 定下一階段的狀態(tài)，這種決定稱為決策。表示決策的變量，稱 為決策變量，常用 uk(sk) 表示第 k 階段當(dāng)狀態(tài)為 sk 時(shí)的決 策變量，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(s1),u2(s2),un(sn)表示，p1,n 表示允許決策的 集合，使整個(gè)問

32、題達(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) 系可用下列狀態(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) 表示。一個(gè) n 段的決策過程，從 1 到 n 叫做問題的原過 程，對任意給定的 ,從第 k

33、 段到第 n 段的過程 稱為原過程的一個(gè)后部子過程。v1,n(s1,p1,n) 表示初始狀態(tài)為 (1)kkn 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 。本方法是從過程的最后 一段開始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn) f 的最短路線。 * ,k n p ,

34、 * , ()(,)(,) k nk n kkk nkk nk nkk n pp fsvspopt vsp 11 ( )f s 1 s 第一步：從 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 ()3fefe 7 35 43 min )(),( )(),( min)( 2521 1511 14 efedd ef

35、edd df 11 * 4 )(edu 5 32 46 min )(),( )(),( min)( 2522 1512 24 efedd efedd df 即 d2 到 f 最短距離為 5 , 其路徑為 d2 e2 f 。相應(yīng)決策為 。 即 d3 到 f 最短距離為 5 , 其路徑為 d3 e1 f 。相應(yīng)決策為 。 類似地，可算得： * 4( ) 22 ude 5 33 41 min )(),( )(),( min)( 2523 1513 34 efedd efedd df 13 * 4 )(edu 34 * 343 23 * 333 22 * 323 11 * 313 )( 9)( )(

36、8)( )( 10)( )( 12)( 3 dcucf dcucf dcucf dcucfk 時(shí)，有 fedcba feuedudcucbubau u baufa bfbad bfbad af cbubf cbubfk k 2221 2 * 522 * 422 * 321 * 21 * 1 1 * 1 222 121 1 32 * 222 21 * 212 )( ,)( ,)( ,)( ,)( : , . )( 17 17 155 134 min )(),( )(),( min)( a 1k )( 15)( )( 13)( 2 所以最優(yōu)路線為： 即最優(yōu)決策序列在按計(jì)算順序反推可得 。本段決策為

37、的最短距離為到即從 ，則只有一個(gè)狀態(tài)點(diǎn)時(shí)， 時(shí)，有 。轉(zhuǎn)移關(guān)系 有遞推的狀態(tài)證各階段的狀態(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 . 5 1 66 11 kkkk kkkkk u kk usts sf k

38、sfusdsf kk k 全渡河那？ 人怎樣才能安掌握在商人們手中。商是如何乘船渡河的大權(quán) 殺人越貨。但從的人數(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 3名商人名商人 3名隨從名隨從 問題分析問題分析: 安全渡河問題可以安全渡河問題可以 視為一個(gè)多步?jīng)Q策過程。視為一個(gè)多步?jīng)Q策過程。 每一步，即

39、船由每一步，即船由此岸到此岸到 彼岸或從彼岸駛回此岸，彼岸或從彼岸駛回此岸， 都要對都要對船上的人員（商船上的人員（商 人、隨從各幾人）作出人、隨從各幾人）作出 決策，在保證安全的前決策，在保證安全的前 提下（兩岸的隨從數(shù)都提下（兩岸的隨從數(shù)都 河河 小船小船(至多至多2人人) 不比商人數(shù)多），在有限步內(nèi)全部人員過河。用狀態(tài)變不比商人數(shù)多），在有限步內(nèi)全部人員過河。用狀態(tài)變 量表示某一岸的人員狀況，決策變量表示船上的人員狀量表示某一岸的人員狀況，決策變量表示船上的人員狀 況，于是可以找出狀態(tài)隨決策變化的規(guī)律。況，于是可以找出狀態(tài)隨決策變化的規(guī)律。 模型構(gòu)成模型構(gòu)成 xk第第k次渡河前此岸的商人

40、數(shù)次渡河前此岸的商人數(shù) yk第第k次渡河前此岸的隨從數(shù)次渡河前此岸的隨從數(shù) xk, yk=0,1,2,3; k=1,2, sk=(xk , yk)過程的狀態(tài)（向量）過程的狀態(tài)（向量） s=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2 s 允許狀態(tài)集合允許狀態(tài)集合 uk第第k次渡船上的商人數(shù)次渡船上的商人數(shù) vk第第k次渡船上的隨從數(shù)次渡船上的隨從數(shù) dk=(uk , vk)決策決策d=(u , v) u+v=1, 2 允許允許決策決策集合集合 uk, vk=0,1,2; k=1,2, sk+1=sk dk +(-1)k狀態(tài)轉(zhuǎn)移律狀態(tài)轉(zhuǎn)移律 求求

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

42、11 允許狀態(tài)允許狀態(tài) s=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2 ), 1(mia i ), 1(njx j j 1 , 10 1 n j jj ：評價(jià)對象（可替代且非劣的方案）評價(jià)對象（可替代且非劣的方案） ：評價(jià)指標(biāo)（準(zhǔn)則、項(xiàng)目）：評價(jià)指標(biāo)（準(zhǔn)則、項(xiàng)目） ：評價(jià)指標(biāo)權(quán)重，評價(jià)指標(biāo)權(quán)重， 1、關(guān)聯(lián)矩陣法、關(guān)聯(lián)矩陣法 綜合評價(jià)方法綜合評價(jià)方法 n 21 vi x1 x2 xn mj j jm j jj n j jj vv vv vv 22 1 11 xj j vij ai ? ij vij = ? 逐對比較法、古林法逐對比較法、古林法

43、a1 a2 am v11 v12 v1n v21 v22 v2n vm1 vm2 vmn . . . 評價(jià)指標(biāo)評價(jià)指標(biāo)xj 替代方案替代方案ai 期望利期望利 潤（萬潤（萬 元）元） 產(chǎn)品成品產(chǎn)品成品 率（率（%） 市場占有市場占有 率（率（%） 投資費(fèi)用投資費(fèi)用 （萬元）（萬元） 產(chǎn)品外觀產(chǎn)品外觀 自行設(shè)計(jì)自行設(shè)計(jì) （a1） 6509530110美美 觀觀 國外引進(jìn)國外引進(jìn) （a2） 7309735180比較美觀比較美觀 改改 建（建（a3）520922550美美 觀觀 方案預(yù)期結(jié)果例表方案預(yù)期結(jié)果例表 評價(jià)指標(biāo)評價(jià)指標(biāo) 得分序號(hào)得分序號(hào) 累計(jì)得累計(jì)得 分分 權(quán)重權(quán)重 1234567891

44、0 期望利潤期望利潤 （x1） 1111 40.4 產(chǎn)品成品產(chǎn)品成品 率（率（x2） 0 111 30.3 市場占有市場占有 率（率（x3） 0 0 01 10.1 投資費(fèi)用投資費(fèi)用 （x4） 0 0 1 120.2 產(chǎn)品外觀產(chǎn)品外觀 （x5） 0 0 0000.0 逐對比較法例表逐對比較法例表 評價(jià)尺度評價(jià)尺度(得分得分) 評價(jià)指標(biāo)評價(jià)指標(biāo) 54321 期望利潤（萬期望利潤（萬 元）元） 800以上以上701-800601-700501-600500以下以下 產(chǎn) 品 成 品 率產(chǎn) 品 成 品 率 （%） 97以上以上96-9791-9586-9085以下以下 市 場 占 有 率市 場 占 有

45、 率 （%） 40以上以上35-3930-3425-2925以下以下 投資費(fèi)用（萬投資費(fèi)用（萬 元）元） 20以下以下21-8081-120121-160160以上以上 產(chǎn)品外觀產(chǎn)品外觀 非常美觀非常美觀美觀美觀比較美觀比較美觀一般一般不美觀不美觀 評價(jià)尺度例表評價(jià)尺度例表 vij ai j 期望期望 利潤利潤 產(chǎn)品成產(chǎn)品成 品率品率 市場占市場占 有率有率 投資投資 費(fèi)用費(fèi)用 產(chǎn)品產(chǎn)品 外觀外觀 vi 0.40.30.10.20.0 自行設(shè)自行設(shè) 計(jì)計(jì)(a1) 333343.0 國外引國外引 進(jìn)進(jìn)(a2) 444133.4 改建改建(a3)232442.7 xj 關(guān)聯(lián)矩陣表（逐對比較法）關(guān)聯(lián)

46、矩陣表（逐對比較法） j 3 4 1/2 序號(hào)序號(hào)評價(jià)指標(biāo)評價(jià)指標(biāo)rjkj 1期望利潤期望利潤180.580 2產(chǎn)品成品率產(chǎn)品成品率60.194 3市場占有率市場占有率20.065 4投資費(fèi)用投資費(fèi)用40.129 5產(chǎn)品外觀產(chǎn)品外觀10.032 合計(jì)合計(jì)311.000 3 rj kj wj 基準(zhǔn)化基準(zhǔn)化 歸一化歸一化 古林法求古林法求j 例表例表 序號(hào)（序號(hào)（j）評價(jià)指標(biāo)評價(jià)指標(biāo)替代方案替代方案rijkijvij 1期望利潤期望利潤 a10.8901.2500.342 a21.4041.4040.384 a31.0000.274 2 產(chǎn)品成品產(chǎn)品成品 率率 a10.9791.0320.334

47、a21.0541.0540.342 a31.0000.324 古林法求古林法求vij例表例表 3 市場占市場占 有率有率 a10.8571.2000.333 a21.4001.4000.389 a31.0000.278 4 投資費(fèi)投資費(fèi) 用用 a11.6360.4550.263 a20.2870.2870.160 a31.0000.577 5 產(chǎn)品外產(chǎn)品外 觀觀 a11.3331.0000.364 a20.7500.7500.272 a31.0000.364 古林法求古林法求vij例表（續(xù)）例表（續(xù)） vij ai j 期望利期望利 潤潤 產(chǎn)品成品產(chǎn)品成品 率率 市場占有市場占有 率率 投資費(fèi)

48、投資費(fèi) 用用 產(chǎn)品外產(chǎn)品外 觀觀 vi 0.5800.1940.0650.1290.032 a1 0.342 0.384 0.274 0.334 0.342 0.324 0.333 0.389 0.278 0.263 0.160 0.577 0.364 0.272 0.364 0.330 0.334 0.326 a2 a3 xj 關(guān)聯(lián)矩陣?yán)恚ü帕址ǎ╆P(guān)聯(lián)矩陣?yán)恚ü帕址ǎ?analytic hierarchy processahp （美國運(yùn)籌學(xué)家、匹茲堡大學(xué)教授（美國運(yùn)籌學(xué)家、匹茲堡大學(xué)教授t.l.saaty,1977） 投資效果好（投資效果好（t） 風(fēng)險(xiǎn)程度（風(fēng)險(xiǎn)程度（i1）資金利潤率（資

49、金利潤率（i2）轉(zhuǎn)產(chǎn)難易程度（轉(zhuǎn)產(chǎn)難易程度（i3） 產(chǎn)品產(chǎn)品1（p1）產(chǎn)品產(chǎn)品2（p2）產(chǎn)品產(chǎn)品3（p3） （目的層）（目的層） （準(zhǔn)則層）（準(zhǔn)則層） （方案層）（方案層） 三、層次分析（三、層次分析（ahp）法）法 判斷矩陣標(biāo)度定義判斷矩陣標(biāo)度定義 標(biāo)度標(biāo)度含義含義 1 兩個(gè)要素相比，具有同樣重要性兩個(gè)要素相比，具有同樣重要性 3 兩個(gè)要素相比，前者比后者稍微重要兩個(gè)要素相比，前者比后者稍微重要 5 兩個(gè)要素相比，前者比后者明顯重要兩個(gè)要素相比，前者比后者明顯重要 7 兩個(gè)要素相比，前者比后者強(qiáng)烈重要兩個(gè)要素相比，前者比后者強(qiáng)烈重要 9 兩個(gè)要素相比，前者比后者極端重要兩個(gè)要素相比，前者比后

50、者極端重要 2，4，6，8 上述相鄰判斷的中間值上述相鄰判斷的中間值 倒數(shù)倒數(shù) 兩個(gè)要素相比，后者比前者的重要性標(biāo)度兩個(gè)要素相比，后者比前者的重要性標(biāo)度 ahp方法的基本工具方法的基本工具判斷矩陣判斷矩陣 ti1i2i3wiwio i111/320.8740.230 i23152.4660.648 i31/21/510.4640.122 (3.804) 注注 wi的求取采用方根法（求根法或稱幾何平均值法）的求取采用方根法（求根法或稱幾何平均值法） i1p1p2p3wiwio p1 11/31/50.4060.105 p2 311/31.0000.258 p3 5312.4660.637 判斷矩

51、陣及其分析處理舉例判斷矩陣及其分析處理舉例 i2p1p2p3wiwio p11272.4100.592 p21/2151.3570.333 p31/71/510.3060.075 i3p1p2p3wiwio p111/31/70.3620.081 p2311/50.8430.188 p37513.2710.731 判斷矩陣及其分析處理舉例（續(xù)）判斷矩陣及其分析處理舉例（續(xù)） 求綜合重要度（加權(quán)和）求綜合重要度（加權(quán)和） t i1 i2 i3 綜合綜合 重要度重要度 權(quán)重權(quán)重 0.230 0.648 0.122 （加權(quán)和）（加權(quán)和） p1 0.105 0.592 0.149 0.426 p2 0

52、.258 0.333 0.066 0.283 p3 0.637 0.075 0.785 0.291 （1）分析評價(jià)系統(tǒng)中各基本要素之間的關(guān)系，建立）分析評價(jià)系統(tǒng)中各基本要素之間的關(guān)系，建立 系統(tǒng)的遞階層次結(jié)構(gòu)（分解法）；系統(tǒng)的遞階層次結(jié)構(gòu)（分解法）； （2）對同一層次的各要素關(guān)于上一層次中某一準(zhǔn)則）對同一層次的各要素關(guān)于上一層次中某一準(zhǔn)則 的重要性進(jìn)行兩兩比較，構(gòu)造判斷矩陣（專家調(diào)查的重要性進(jìn)行兩兩比較，構(gòu)造判斷矩陣（專家調(diào)查 法）；法）； （3）由判斷矩陣計(jì)算被比較要素對于該準(zhǔn)則的相對）由判斷矩陣計(jì)算被比較要素對于該準(zhǔn)則的相對 權(quán)重（方根法）；權(quán)重（方根法）； （4）計(jì)算各層要素相對于系統(tǒng)目

53、的（總目標(biāo)）的合）計(jì)算各層要素相對于系統(tǒng)目的（總目標(biāo)）的合 成（總）權(quán)重，并據(jù)此對方案等排序（加權(quán)和法）。成（總）權(quán)重，并據(jù)此對方案等排序（加權(quán)和法）。 ahp方法步驟方法步驟 課程：課程： 教師：教師： 班級：班級： 評價(jià)項(xiàng)目（權(quán)重）評價(jià)項(xiàng)目（權(quán)重） 好好 （100） 較好較好 (85) 一般一般 （70） 較差較差 （55） 1.教學(xué)計(jì)劃及教學(xué)內(nèi)容安排（教學(xué)計(jì)劃及教學(xué)內(nèi)容安排（0.10）9 0.36 14 0.56 2 0.08 0 0.00 2.教材及參考資料狀況教材及參考資料狀況(0.10)3 0.12 14 0.56 7 0.28 1 0.04 3.教師教學(xué)態(tài)度及責(zé)任心教師教學(xué)態(tài)度及

54、責(zé)任心(0.15)5 0.20 15 0.60 5 0.20 0 0.00 4.教師講解能力（教師講解能力（0.10）1 0.04 10 0.40 11 0.44 3 0.12 評價(jià)結(jié)果評價(jià)結(jié)果(票數(shù)票數(shù)/隸屬度隸屬度) ) 評價(jià)等級評價(jià)等級 四、模糊綜合評判法（四、模糊綜合評判法（1） 5.課堂教學(xué)形式的多樣化程度（課堂教學(xué)形式的多樣化程度（0.10）2 0.08 11 0.44 12 0.48 0 0.00 6.理論聯(lián)系實(shí)際程度及教學(xué)案例使用情理論聯(lián)系實(shí)際程度及教學(xué)案例使用情 況（況（0.10） 5 0.20 14 0.56 6 0.24 0 0.00 7.輔助教學(xué)環(huán)節(jié)及考核情況輔助教學(xué)環(huán)

55、節(jié)及考核情況(0.10)4 0.16 6 0.24 13 0.52 2 0.08 8.教學(xué)改革與創(chuàng)新情況教學(xué)改革與創(chuàng)新情況(0.10)3 0.12 8 0.32 12 0.48 2 0.08 9.從本課程學(xué)習(xí)中所獲得的收益程度從本課程學(xué)習(xí)中所獲得的收益程度 （0.15） 5 0.20 12 0.48 6 0.24 2 0.08 綜合評價(jià)結(jié)果綜合評價(jià)結(jié)果 綜合隸屬度綜合隸屬度 0.168 0.470 0.318 0.044 綜合得分綜合得分81.43 四、模糊綜合評判法（四、模糊綜合評判法（2） 49 )( ij rr 91 )( i ww 41 )( j dd t ds 隸屬度隸屬度 rij

56、指多個(gè)評價(jià)主體對某個(gè)評價(jià)對象指多個(gè)評價(jià)主體對某個(gè)評價(jià)對象 在第在第i個(gè)項(xiàng)目下作出第個(gè)項(xiàng)目下作出第j等級評定的可能性程度。等級評定的可能性程度。 若記：隸屬度矩陣為若記：隸屬度矩陣為 評價(jià)項(xiàng)目權(quán)重向量為評價(jià)項(xiàng)目權(quán)重向量為 評價(jià)等級分值向量為評價(jià)等級分值向量為 則有：綜合隸屬度向量則有：綜合隸屬度向量 s=wr 綜合得分綜合得分 四、模糊綜合評判法（四、模糊綜合評判法（3） 動(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)控制中也

57、有廣泛應(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)造模型的 方法，方法， 需要對每類問題具體分析。在定義狀態(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ù)增長，對高維問題求解十分困

58、難。 六六. . 最優(yōu)控制理論最優(yōu)控制理論 最優(yōu)控制理論是從20世紀(jì)50年代末60年代初發(fā)展起來的現(xiàn) 代控制理論的一個(gè)重要分支。它最初研究的對象是由導(dǎo)彈、航 天、航空、航海中的制導(dǎo)、導(dǎo)航和控制中所總結(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í)際問題控制工程中的幾個(gè)實(shí)際問題 為了更好地說明最優(yōu)控制問題，我們給出幾個(gè)工程控制中 的實(shí)例。 例6.1 （升降機(jī)的最快升降問題）一個(gè)內(nèi)部帶控制器的物體 m ， 其質(zhì)量為 1 。常重力加速度 g 垂直向下作用到m 的質(zhì)心上，控