運(yùn)籌學(xué)胡運(yùn)權(quán)第07章

1、|多階段決策過(guò)程的最優(yōu)化|動(dòng)態(tài)規(guī)劃的基本概念和基本原理|動(dòng)態(tài)規(guī)劃模型的建立與求解|動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用|馬氏決策規(guī)劃簡(jiǎn)介美國(guó)數(shù)學(xué)家貝爾曼（Richard. Bellman)創(chuàng)始時(shí)間上個(gè)世紀(jì)50年代創(chuàng)始人|是運(yùn)籌學(xué)的一個(gè)主要分支|是解決多階段決策過(guò)程的最優(yōu)化的一種方法多階段決策過(guò)程：資源分配問(wèn)題生產(chǎn)計(jì)劃與庫(kù)存問(wèn)題投資問(wèn)題裝載問(wèn)題排序問(wèn)題生產(chǎn)過(guò)程的最優(yōu)控制等多階段決策過(guò)程的最優(yōu)化的目標(biāo)：達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)主要用于解決：最優(yōu)路徑問(wèn)題動(dòng)態(tài)規(guī)劃模型分類離散確定型離散隨機(jī)型連續(xù)確定型連續(xù)隨機(jī)型多階段決策問(wèn)題(Multi-Stage decision process)狀態(tài) x1階段1T1決

2、策u1狀態(tài) x2決策u2階段2T2狀態(tài) x3.狀態(tài) xk決策uk階段kTk狀態(tài) xk+1.狀態(tài) xn決策un階段nTn狀態(tài) xn+11.多階段決策過(guò)程的最優(yōu)化 動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。然而它也可以處理與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題，只要在問(wèn)題中人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題。在本章中將介紹這種處理方法。2.多階段決策問(wèn)題舉例 屬于多階段決策類的問(wèn)題很多，例如： 1)1)工廠生產(chǎn)過(guò)程工廠生產(chǎn)過(guò)程：由于市場(chǎng)需求是一隨著時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，逐

3、月或者逐季度地根據(jù)庫(kù)存和需求情況決定生產(chǎn)計(jì)劃安排。|例1：某廠與用戶簽訂了如表所示的交貨合同，表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每月400件，該廠倉(cāng)庫(kù)的存貨能力為300件。已知每百件貨物的生產(chǎn)費(fèi)用為10000元。在進(jìn)行生產(chǎn)的月份，工廠還要支付經(jīng)常費(fèi)4000元。倉(cāng)庫(kù)保管費(fèi)為每百件貨物每月1000元。假設(shè)開(kāi)始時(shí)及6月底交貨后無(wú)存貨。月份123456交貨量（百件）125321 2) 2)設(shè)備更新問(wèn)題：設(shè)備更新問(wèn)題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買來(lái)時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價(jià)值也高，隨著使用年限的增加，就會(huì)逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益

4、差，并且，使用的年限越長(zhǎng)、處理價(jià)值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。例2：下表給出了某單位的預(yù)測(cè)數(shù)據(jù)，現(xiàn)決定考慮到1998年（n=5），試作5年內(nèi)的設(shè)備更新計(jì)劃產(chǎn)品年代機(jī)齡收入額維護(hù)費(fèi)新設(shè)備購(gòu)置費(fèi)舊設(shè)備折價(jià)199312345181616141488991050201510521994012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040 3)

5、3)連續(xù)生產(chǎn)過(guò)程的控制連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題問(wèn)題：一般化工生產(chǎn)過(guò)程中，常包含一系列完成生產(chǎn)過(guò)程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。 以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，因此在這類多階段決策問(wèn)題中，階段的劃分常取時(shí)間區(qū)段來(lái)表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)”的含義，所以把處理這類動(dòng)態(tài)問(wèn)題的方法稱為動(dòng)態(tài)規(guī)劃方法。 不過(guò)，實(shí)際中尚有許多不包含時(shí)間因素的一類“靜態(tài)”決策問(wèn)題，就其本質(zhì)而言是一次決策問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問(wèn)

6、題，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。 4 4）資源分配問(wèn)題：）資源分配問(wèn)題：便屬于這類靜態(tài)問(wèn)題。如：某工業(yè)部門或公司，擬對(duì)其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問(wèn)題原本要求一次確定出對(duì)各企業(yè)的資源分配量，它與時(shí)間因素?zé)o關(guān)，不屬動(dòng)態(tài)決策，但是，我們可以人為地規(guī)定一個(gè)資源分配的階段和順序，從而使其變成一個(gè)多階段決策問(wèn)題( (后面我們將后面我們將詳細(xì)討論這個(gè)問(wèn)題詳細(xì)討論這個(gè)問(wèn)題) )。|例3：某工廠生產(chǎn)A、B、C三種產(chǎn)品，都使用某種原材料，現(xiàn)有原材料4噸。江不同數(shù)量的這種原料分配給各種產(chǎn)品時(shí)產(chǎn)生的收益如表所示，試確定使總收益最大的分配法。ABC012301017200617

7、18081111 5 5）運(yùn)輸網(wǎng)絡(luò)問(wèn)題）運(yùn)輸網(wǎng)絡(luò)問(wèn)題：如圖7-1所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從A至F的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為5個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。|多階段決策過(guò)程的最優(yōu)化|動(dòng)態(tài)規(guī)劃的基本概念和基本原理|動(dòng)態(tài)規(guī)劃模型的建立與求解|動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用|馬氏決策規(guī)劃簡(jiǎn)介 一、動(dòng)態(tài)規(guī)劃的基本概念一、動(dòng)態(tài)規(guī)劃的基本概念 使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問(wèn)題，首先要將實(shí)際問(wèn)題寫成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對(duì)動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語(yǔ)進(jìn)一步加以說(shuō)明和定義：

8、 ( (一一) ) 階段和階段變量階段和階段變量 為了便于求解和表示決策及過(guò)程的發(fā)展順序，而把所給問(wèn)題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問(wèn)題，稱之為多段決策問(wèn)題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問(wèn)題，通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過(guò)程從開(kāi)始到結(jié)束所需作出決策的數(shù)目，圖71所示的最短路問(wèn)題就是一個(gè)四階段決策過(guò)程。 （二）狀態(tài)、狀態(tài)變量和可能狀態(tài)（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集集 1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)。反映狀態(tài)變化的量

9、叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過(guò)程進(jìn)行的先后，每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見(jiàn)，通常定義階段的狀態(tài)即指其初始狀態(tài)。 2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通常可能狀態(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問(wèn)題而定在圖71所示的最短路問(wèn)題中，第一階段狀態(tài)為A，狀態(tài)變量s1的狀態(tài)集合S1=A；第二

10、階段則有兩個(gè)狀態(tài)：B1 ,B2, 狀態(tài)變量s2的狀態(tài)集合S2=B1 ,B2 ；第三階段有四個(gè)狀態(tài):C1 ,C2 ,C3 ,C4狀態(tài)變量s3的狀態(tài)集合S3=C1 ,C2 ,C3 ,C4 ；第四階段則有三個(gè)狀態(tài)： D1 ,D ,D3 , 狀態(tài)變量s4的狀態(tài)集合S4=C1 ,C2 ,C3 ；第五階段則有兩個(gè)狀態(tài)E1 ,E2狀態(tài)變量s5的狀態(tài)集合S5=E1 ,E2, （三）決策、決策變量和允許決策集合（三）決策、決策變量和允許決策集合 所謂決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量和狀態(tài)變量一樣，

11、決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k= uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk) Uk(sk)允許決策集合實(shí)際是決策的約束條件。 （四）策略和允許策略集合（四）策略和允許策略集合 策略(Policy)也叫決策序列策略有全過(guò)程策略和k部子策略之分，全過(guò)程策略是指具有n個(gè)階段的全部過(guò)程，由依次進(jìn)行的n個(gè)階段決策 構(gòu) 成 的 決 策 序 列 ， 簡(jiǎn) 稱 策 略 ， 表 示 為p1,nu1,u2,un。從k階段到第n階段，依次進(jìn)行的

12、階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時(shí)的k部子策略就是全過(guò)程策略。 在實(shí)際問(wèn)題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。 （五）狀態(tài)轉(zhuǎn)移方程（五）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1 ，或者說(shuō)，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1，多階段決策過(guò)程的發(fā)展就是用階段狀態(tài)的

13、相繼演變來(lái)描述的。 對(duì)于具有無(wú)后效性的多階段決策過(guò)程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過(guò)去的狀態(tài)s1,s2, ,sk-1及其決策u1(s1), u2(s2)uk-1(sk-1)無(wú)關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：(7-1)(,(1kskukskTks 通常稱式(7-1)為多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程。有些問(wèn)題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。 ( (六六) ) 指標(biāo)函數(shù)指標(biāo)函數(shù) 用來(lái)衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過(guò)程或各子過(guò)程或各階段上的確定數(shù)

14、量函數(shù)。對(duì)不同問(wèn)題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。例如：圖71的指標(biāo)就是運(yùn)費(fèi)。 (1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為gk 。圖7-1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(A,B1)=4,即A到B1的距離為3。 (2)過(guò)程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。用Rk(sk,uk)表示第k子過(guò)程的指標(biāo)函數(shù)。如圖7-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時(shí)，從sk點(diǎn)到終點(diǎn)F的距離。由此可見(jiàn)，Rk(sk,uk)不僅跟當(dāng)前狀

15、態(tài)sk有關(guān)，還跟該子過(guò)程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴(yán)格說(shuō)來(lái)，應(yīng)表示為:)(,(kkkkspsR 不 過(guò) 實(shí) 際 應(yīng) 用 中 往 往 表 示 為Rk(sk,uk)或Rk(sk)。還跟第k子過(guò)程上各段指標(biāo)函數(shù)有關(guān)，過(guò)程指標(biāo)函數(shù)Rk(sk)通常是描述所實(shí)現(xiàn)的全過(guò)程或k后部子過(guò)程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)gk(sk,uk)累積形成的，適于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式對(duì)于部子過(guò)程的指標(biāo)函數(shù)可以表示為： 式中，表示某種運(yùn)算，可以是加、減、乘、除、開(kāi)方等。 (7-2),()1,1(1),(),1,1,(,

16、nunsngkukskgkukskgnunskukskuksnkRnkR 多階段決策問(wèn)題中，常見(jiàn)的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即: (7-3) 有些問(wèn)題，如系統(tǒng)可靠性問(wèn)題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如： (7-4) 總之，具體問(wèn)題的目標(biāo)函數(shù)表達(dá)形式需要視具體問(wèn)題而定。nkiiuisigkR),(nkiiiikusgR),( ( (七七) ) 最優(yōu)解最優(yōu)解 用fk(sk)表示第k子過(guò)程指標(biāo)函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱fk(sk)為第k子過(guò)程上的最優(yōu)指標(biāo)函數(shù)；nkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()(式中“OPT”表示最優(yōu)化，視具

17、體問(wèn)題取max或min。)(,(kkkkspsR 最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個(gè)全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過(guò)程中的任意狀態(tài)而言，無(wú)論其過(guò)去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過(guò)程最優(yōu)策略為：)(),(,),(),()(221111nnkksususususp 則對(duì)上述策略中所隱含的任一狀態(tài)而言，第k子過(guò)程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過(guò)程最優(yōu)策略p1*中，即為)(,),(),()(11nnkkkkkksusususp 二二. .動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題的特點(diǎn)動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題的特點(diǎn) 通常多階段決策

18、過(guò)程的發(fā)展是通過(guò)狀態(tài)的一系列變換來(lái)實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過(guò)去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問(wèn)題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問(wèn)題，即具有“無(wú)后效性”的多階段決策過(guò)程。所謂無(wú)后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無(wú)關(guān)。 例例4 4：為了說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖7-1所示為例討論的求最短路問(wèn)題的方法。 第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對(duì)它

19、們一一進(jìn)行比較，求出最優(yōu)方案。這里從A到F的路程可以分為5個(gè)階段。第一段的走法有兩種，第二段的走法有三種，第三四段的走法 各 兩 種 ， 第 五 段 走 法 一 種 ， 因 此 共 有2322124條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線。 顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算 第二種方法即所謂“局部最優(yōu)路徑”法，是說(shuō)某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是AB1C1D1E1F，全程長(zhǎng)度是18；顯然，這種方法

20、的結(jié)果常是錯(cuò)誤的 第三種方法是動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃方法尋求該最短路問(wèn)題的基本思想是，首先將問(wèn)題劃分為5個(gè)階段，每次的選擇總是綜合后繼過(guò)程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過(guò)程，動(dòng)態(tài)規(guī)劃方法總是從過(guò)程的最后階段開(kāi)始考慮，然后逆著實(shí)際過(guò)程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。 具體說(shuō)，此問(wèn)題先從F開(kāi)始，因?yàn)镕是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第5階段上所有可能狀態(tài)E1，E2的最優(yōu)后續(xù)過(guò)程。因?yàn)閺腅1 ,E2到F的路線是唯一的，所以E1，E2的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到F，它們的最短距離分別是4和3

21、。 接著考慮階段4上可能的狀態(tài)D1，D2，D3 到F的最優(yōu)決策和最優(yōu)后繼過(guò)程在狀態(tài)D1上，到E1是3，到E2是5，綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到E1,最優(yōu)后繼過(guò)程是D1E1F ，最短距離是7。同理，狀態(tài)D2的最優(yōu)決策是至E2 ；D3的最優(yōu)決策是到E1。 同樣，當(dāng)階段4上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段3上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如C1的最優(yōu)決策是到D1,最優(yōu)路線是C1D1E1F ，最短距離是12依此類推，最后可以得到從初始狀態(tài)A的最 優(yōu) 決 策 是 到F最 優(yōu) 路 線 是AB1C2D2E2 F ，全程的最短距離是17。圖71中粗實(shí)線表示各點(diǎn)到的最

22、優(yōu)路線，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。的距離到表示從的最短距離到表示從令ykykkkvvgFvf,53246minmin73543minmin303404022,211,2222, 111, 1110,2210, 11EEDEEDDEEDEEDDFEEFEEFfgfgffgfgffgffgff85453minmin105574minmin125875minmin53341minmin33, 322, 3322,211,2222, 111, 1122, 311, 33DDCDDCCDDCDDCCDDCDDCCEEDEEDDfgfgffgfgffgfgffgfgf17155134

23、min22,11,min159787108min34,223,212,2min21386103122min33, 122, 111, 1min195458min33,422,4min4BfBAgBfBAgAfCfCBgCfCBgCfCBgBfCfCBgCfCBgCfCBgBfDfDCgDfDCgCf 綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問(wèn)題分解為一系列同類型的更易求解的子問(wèn)題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過(guò)程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問(wèn)題中所有可能狀態(tài)的最優(yōu)決

24、策與最優(yōu)路線值，然后再順序地求出整個(gè)問(wèn)題的最優(yōu)策略和最優(yōu)路線。計(jì)算過(guò)程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。|多階段決策過(guò)程的最優(yōu)化|動(dòng)態(tài)規(guī)劃的基本概念和基本原理|動(dòng)態(tài)規(guī)劃模型的建立與求解|動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用|馬氏決策規(guī)劃簡(jiǎn)介 1應(yīng)將實(shí)際問(wèn)題恰當(dāng)?shù)胤指畛蒼個(gè)子問(wèn)題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。2正確地定義狀態(tài)變量sk，使它既能正確地描述過(guò)程的狀態(tài)，又能滿足無(wú)后效性動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說(shuō)的狀態(tài)的概念是有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變

25、量必須具備以下三個(gè)特征： (1)要能夠正確地描述受控過(guò)程的變化特征。(2)要滿足無(wú)后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定，那么在該階段以后，過(guò)程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃的模型。(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測(cè)算得到。一般在動(dòng)態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進(jìn)行累計(jì)的量。此外，在與靜態(tài)規(guī)劃模型的對(duì)應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗(yàn)，線性與非線性規(guī)劃中約束條件的個(gè)數(shù)，相當(dāng)于動(dòng)態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。3正確地定義決策變量及各階段的允許決策集合Uk

26、(sk)，根據(jù)經(jīng)驗(yàn)，一般將問(wèn)題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。4. 能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+ 1的 值 也 就 完 全 確 定 ， 即 有sk+1=Tk(sk ,uk)5根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)： (1)可分性，即對(duì)于所有k后部子過(guò)程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策uk ,uk+1,un,就是說(shuō)它是定

27、義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)。 (2)要滿足遞推關(guān)系，即 (3)函數(shù) 對(duì)其變?cè)猂k+1來(lái)說(shuō)要嚴(yán)格單調(diào)。),(,111nkkkkkssRus),(,),(111111,nkkkkknkkkknkssRussususR6寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程 例如常見(jiàn)的指標(biāo)函數(shù)是取各段指標(biāo)和的形式 其中 表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成 ：nkiiiikkusgsR),()(),(),(111nkkkkkkssRusgR),(iiiusg例5 （資源分配問(wèn)題）某公司有資金10萬(wàn)元，擬投資于3個(gè)項(xiàng)目，已知對(duì)第i個(gè)項(xiàng)目投資xi萬(wàn)元，收益為g i (xi)，問(wèn)應(yīng)如何分配資金可

28、使總收益最大？其中，解：階段k=1,2, 3決策變量uk：第k個(gè)項(xiàng)目的投資額狀態(tài)變量sk：在第k階段時(shí)可以用于投資 第k到第3個(gè)項(xiàng)目的資金數(shù)指標(biāo)函數(shù)Vk,n3kiiiug：第k階段可分配的資金數(shù)為sk時(shí)，第k至第3個(gè)項(xiàng)目的最大總收益狀態(tài)轉(zhuǎn)移方程：sk+1 = sk -uk0|kkkksuuUkksf最優(yōu)值函數(shù) af1求邊界條件：044sf資源分配問(wèn)題的動(dòng)態(tài)規(guī)劃基本方程： 01 , 2 , 3max44110sfksfugsfkkkksukkkk建立遞推公式：kksu 0maxkksfk=3,2,1kkug11kksf：在第k階段分配的資金數(shù)為sk時(shí)，第k至第3個(gè)項(xiàng)目的最大總收益kksf最優(yōu)值函

29、數(shù)順序解法(前向動(dòng)態(tài)規(guī)劃方法)動(dòng)態(tài)規(guī)劃的求解有兩種基本方法：逆序解法(后向動(dòng)態(tài)規(guī)劃方法)順序解法的尋優(yōu)方向與過(guò)程的行進(jìn)方向相同，計(jì)算時(shí)從第一段開(kāi)始逐段向后遞推，計(jì)算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過(guò)程的最優(yōu)結(jié)果。順序解法與逆序解法本質(zhì)上并無(wú)區(qū)別，一般地說(shuō)，當(dāng)初始狀態(tài)給定時(shí)可用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)可用順序解法。|兩種解法區(qū)別1.狀態(tài)轉(zhuǎn)移方式不同 2.指標(biāo)函數(shù)的定義不同逆序：順序：sk+1=Tk(sk ,uk)sk=Tk(sk+1,uk)3.基本方程形式不同當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式，逆序解法順序解法解法離散型連續(xù)型：分段窮舉法：解析方法或線性規(guī)劃方法沒(méi)有固定的方法

30、具體模型具體分析要求：經(jīng)驗(yàn) 、技巧、靈活難！連續(xù)變量的離散化解法高維問(wèn)題的降維法及疏密格子點(diǎn)法|用逆序解法解例52323x03322max)(33sxsfsk=3時(shí)k=2時(shí))(*29max)(9max)(2222x0332x0222222xsxsfxsfss令2222222)(*29)x,(shxsx由0) 1(*)(*49dxdh2222xs解得）是極小點(diǎn)（因?yàn)?449222222dxhdsx222s極大值只可能在0,s2端點(diǎn)取得，f2(0)=f2(s2)=9s2222sk=1時(shí)23221x0112)(4max)(11ssfxsfs2*22222*222222222x),()0(2/90 x

31、),()0(2/92/9)()0(ssffssffsssff此時(shí)，時(shí)，此時(shí)，時(shí)，當(dāng)時(shí)，解得當(dāng)同理可求出x1=s1-1是極小點(diǎn)20010010, 011）（時(shí)，兩個(gè)端點(diǎn)，比較fx0401010*1111xfx）（時(shí)，)2/9(102*112sxss再由狀態(tài)轉(zhuǎn)移方程順推101003*3*223*2sxxssx，所以最優(yōu)投資方案為全部資金投于第三個(gè)項(xiàng)目，可得最大收益200萬(wàn)元。|多階段決策過(guò)程的最優(yōu)化|動(dòng)態(tài)規(guī)劃的基本概念和基本原理|動(dòng)態(tài)規(guī)劃模型的建立與求解|動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用|馬氏決策規(guī)劃簡(jiǎn)介 學(xué)習(xí)方法建議： 第一步 先看問(wèn)題，充分理解問(wèn)題的條件、情況及求解目標(biāo)。 第二步 結(jié)合前面講到的理論

32、和解題過(guò)程，考慮如何著手進(jìn)行求解該問(wèn)題的工作。分析針對(duì)該動(dòng)態(tài)規(guī)劃問(wèn)題的“四大要素、一個(gè)方程”這一步在開(kāi)始時(shí)會(huì)感到困難，但是一定要下決心去思考，在思考過(guò)程中深入理解前文講到的概念和理論。 第三步 動(dòng)手把求解思路整理出來(lái)，或者說(shuō)，把該問(wèn)題作為習(xí)題獨(dú)立的來(lái)做。 第四步 把自己的求解放到一邊，看書(shū)中的求解方法，要充分理解教材中的論述。 第五步 對(duì)照自己的求解，分析成敗。 1.動(dòng)態(tài)規(guī)劃的四大要素 狀態(tài)變量及其可能集合x(chóng)kXk 決策變量及其允許集合ukUk 狀態(tài)轉(zhuǎn)移方程xk+1=Tk (xk,uk) 階段效應(yīng)rk (xk,uk) 2. 動(dòng)態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 (邊界條件) fk(x

33、k) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,160則 max z=c1x1+c2x2+cnxn. w1x1+w2x2+wnxnW x1,x2,xn為正整數(shù)(i=1,2,n)1 .階段k：第k次裝載第k種物品（k=1,2,n）2.狀態(tài)變量sk+1：在第k次開(kāi)始時(shí)，背包中允許裝入前k種物品的重量；3.決策變量xk：第k次裝載第k種物品的件數(shù)；采用動(dòng)態(tài)規(guī)劃順序解法建模求解s.t4. 決策允許集合：Dk(xk)=dk|0dksk+1/wk,dk為整數(shù)；5. 狀態(tài)轉(zhuǎn)移方程：sk=sk+1-wkxk6. 階段指標(biāo)：vk=ckxk7. 遞推方程 fk(sk)=ma

34、xckxk+fk-1(sk) =maxckxk+fk-1(sk+1-wkxk)8. 終端條件：f0(s1)=0例6:對(duì)于一個(gè)具體問(wèn)題c1=4，c2=5，c3=6；w1=3，w2=4，w3=5；以及W=10用動(dòng)態(tài)規(guī)劃求解 f0(s1)=04max)(4302121xxfsx 對(duì)于k=1332221110001212888444000f1(s2)109876543210s2*1x)4(50max)(23124/3232xsfxsxxf對(duì)于k=21021011000013121098554000f2(s3)101312109121098985854544000c2+f2210210210101010

35、100000 x2109876543210s3*2x13012, 56 ,13max0(5),126),10max5-106max)10(22232321033）（）（，fffxfxfx對(duì)于k=3, 0 x, 1x, 2x*3*2*1最大值為1366庫(kù)存問(wèn)題例8 某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)如表7-7，又每月生產(chǎn)j單位產(chǎn)品費(fèi)用為： C(j)= 0(j=0) 3+j(j=1,2,，6)(千元) 每月庫(kù)存j單位產(chǎn)品的費(fèi)用為E(j)=0.5j(千元)，該廠最大庫(kù)存容量為3單位，每月最大生產(chǎn)能力為6單位，計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零。試制定四個(gè)月的生產(chǎn)計(jì)劃，在滿足用戶需求條件

36、下總費(fèi)用最小。假設(shè)第i+1個(gè)月的庫(kù)存量是第i個(gè)月可銷售量與該月用戶需求量之差；而第i個(gè)月的可銷售量是本月初庫(kù)存量與產(chǎn)量之和。階段k狀態(tài)變量sk決策變量uk狀態(tài)轉(zhuǎn)移方程階段指標(biāo)終端條件月份，k=1,2,3,4；第k個(gè)月初（發(fā)貨以前）的庫(kù)存量；第k個(gè)月的生產(chǎn)量；sk+1=sk+uk-gk；gk(sk ,dk)=ckuk；f8(s8)=0,x8=0；最優(yōu)指標(biāo)函數(shù)fk(sk)fk(xk)=mingk(sk ,uk)+fk+1(sk+1) =minckuk+fk+1(sk-gk+uk)125 . 58 ; 5u67 ; 4u5 . 66 ; 3u75 ; 2umin)2(0*5 . 0)3(min)0(

37、f3333343523ufusu整數(shù))()()(min)(f3334335233guSfsEuCssu整數(shù)遞推方程對(duì)于u3 max(0,2-s3)u3min(6,5-s3,6-s3),其中s3的取值范圍為0,1,2,3當(dāng)s3=0時(shí)2)0(u*3對(duì)于K=3u*3(s3)f3( s3)C+E+f4u3(s3)00128811.5121211.5812.51211.581312.51211.513.51312.5122103210432154323210s3對(duì)于K=2u*2(s2)f2( s2)C+E+f3u2(s2) 3 4 513.5 15 15.5 1614.51713.5161517.517

38、16.515.51817.5171618.5182104321543265433 2 10s2315.50u*1(s1)f1( s1)C+f2u1(s1)221.52221.52154320s121對(duì)于K=1得出最佳生產(chǎn)計(jì)劃為，第一個(gè)月生產(chǎn)2單位，第二個(gè)月生產(chǎn)5單位，第三個(gè)月不生產(chǎn)，第四個(gè)月生產(chǎn)4個(gè)單位?？偨Y(jié)此類生產(chǎn)存貯問(wèn)題的基本方程為：0)()()()(min)(f111knnkkkkkkuksfguSfsEuCsk1,.,1,nnk若最大庫(kù)存量為q,每月最大生產(chǎn)能力為p.則狀態(tài)集合為：)(,minks011nkjkjjjgpgq允許決策集合為：,minku), 0(maxnkjksqkgk

39、sjgpkskg73采購(gòu)與銷售問(wèn)題例9某商店在未來(lái)的四個(gè)月里，準(zhǔn)備利用商店的一個(gè)倉(cāng)庫(kù)來(lái)專門經(jīng)銷某種商品，倉(cāng)庫(kù)最大容量為這種商品1000單位。假定商店每月只能賣出倉(cāng)庫(kù)現(xiàn)有的貨物。當(dāng)商店在某月購(gòu)貨時(shí)，下月初才能到貨。預(yù)測(cè)該商店未來(lái)四個(gè)月的買賣價(jià)格如 下表，假定商店在1月開(kāi)始經(jīng)銷時(shí)，倉(cāng)庫(kù)貯有該商品500單位，試問(wèn)，如何制定這四個(gè)月的訂購(gòu)與銷售計(jì)劃，使獲利最大（不計(jì)庫(kù)存費(fèi)）。 1 10 12 2 8 9 3 11 13 4 15 17月份（k）購(gòu)買單價(jià) （ck）銷售單價(jià) （pk）解： k=1，2，3，4狀態(tài)變量skxk第k月賣出的貨物數(shù)量yk第k月訂購(gòu)的貨物數(shù)量狀態(tài)轉(zhuǎn)移方程：sk+1 = sk + y

40、k -xk pk xk+fk+1（sk+1），求f1（500）-ck yk0 xk sk 0yk 1000-(sk -xk )已知：倉(cāng)庫(kù)最大容量為1000單位。商店每月只賣出倉(cāng)庫(kù) 現(xiàn)有的貨物。當(dāng)商店在某月購(gòu)貨時(shí)，下月初才能到 貨。 1月開(kāi)始經(jīng)銷 時(shí)，倉(cāng)庫(kù)貯有該商品500單位，如何制定四個(gè)月的訂 購(gòu)與銷售計(jì)劃，使獲利最大（不計(jì)庫(kù)存費(fèi)）。第k月的購(gòu)買單價(jià)ck，銷售單價(jià)pk，fk（sk）=第k月初庫(kù)存為時(shí)sk ， 從第k月到第4月末所獲得的最大利潤(rùn) =max ,0 xk sk ,0yk 1000-(sk -xk )（ sk + yk xk）決策變量：s1=500 ,0sk1000 k=2，3，4第k

41、個(gè)月的庫(kù)存量（含上月的定貨）基本方程：f5（s5）=0求f1（500）fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)k=4，3，2，1f4（s4）=maxp4 x4 0 x4 s4 -c4 y40y4 1000-(s4 x4 )=p4 s4=17 s4x*4= s4y*4= 0當(dāng)k=4時(shí)當(dāng)k=3時(shí)f3（s3）=maxp3 x3 0 x3 s3 -c3 y30y3 1000-(s3 x3 )+f4 （s3+y3-x3)=max13 x3 0 x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s

42、3+y3-x3),0s41000 ,0s31000 當(dāng)k=3時(shí)f3（s3）=max13 x3 0 x3 s3 -11 y30y3 1000-(s3 x3 )+17 （s3+y3-x3)=max-4 x3 0 x3 s3 +6 y30y3 1000-(s3 x3 )+17 s3求maxZ=-4 x3+6 y3 +17s30 x3 s3 0y3 1000-(s3 x3 )取Z=-4 x3+6 y3 +17s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3,0s31000 x*3= s3y*3=100 0=6000+13s3x3 + x1

43、=s3 - x3 +y3 + x2= 1000-s3 maxZ=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2-4 6 0 0Z- 17s3 x1 1 0 1 0s3x2-1 1 0 11000-s3x3 y3 x1 x22 0 0 -6Z-6000-11s3 x1 1 0 1 0s3y3-1 1 0 11000-s3x3 y3 x1 x20 0 -2 -6Z-6000-13s3 x3 1 0 1 0s3y3 0 1 1 11000 x*3= s3y*3=100 0最優(yōu)值 Z=6000+13s3x3 s3 - x3 +y3 1000-s3 x3, y30

44、求maxZ=-4 x3+6 y3 +17s3標(biāo)準(zhǔn)型：最優(yōu)解：fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)f3（s3）=x*3= s3，y*3=100 06000+13s3當(dāng)k=2時(shí)f2（s2）=maxp2 x2 0 x2 s2 -c2 y20y2 1000-(s2 x2 )+f3 （s2+y2-x2),0s21000 =max9 x2 0 x2 s2 -8 y20y2 1000-(s2 x2 )+6000+13 （s2+y2-x2)=max-4 x2 0 x2 s2 +5 y20y2 1000-(s2 x2 )+13 s2+6000 x*2= 0=11000+8s2，y*2=1000-s2fk（sk）= max pk xk 0 xk sk -ck yk0yk 1000-(sk -xk )+fk+1 （sk+yk-xk)當(dāng)k=1時(shí)f1（s1）=maxp1 x1 0 x1 s1 -c1 y10y1 1000-(s1 x1 )+f2 （s1+y1-x1),s1=500 x*1= 500=17000，y*1=0f2（s2）=x*2= 011000+8s2，