1、12 多階段決策過(guò)程的最優(yōu)化多階段決策過(guò)程的最優(yōu)化 動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃的基本概念和基本原理 動(dòng)態(tài)規(guī)劃模型的建立與求解動(dòng)態(tài)規(guī)劃模型的建立與求解3美國(guó)數(shù)學(xué)家貝爾曼美國(guó)數(shù)學(xué)家貝爾曼(Richard. Bellman)創(chuàng)始時(shí)間創(chuàng)始時(shí)間上個(gè)世紀(jì)上個(gè)世紀(jì)50年代年代創(chuàng)始人創(chuàng)始人4 是運(yùn)籌學(xué)的一個(gè)主要分支是運(yùn)籌學(xué)的一個(gè)主要分支 是解決是解決多階段決策過(guò)程多階段決策過(guò)程的最優(yōu)化的一種方法多的最優(yōu)化的一種方法多階段決策過(guò)程：階段決策過(guò)程：資源分配問(wèn)題資源分配問(wèn)題生產(chǎn)計(jì)劃與庫(kù)存問(wèn)題生產(chǎn)計(jì)劃與庫(kù)存問(wèn)題投資問(wèn)題投資問(wèn)題裝載問(wèn)題裝載問(wèn)題排序問(wèn)題排序問(wèn)題生產(chǎn)過(guò)程的最優(yōu)控制等生產(chǎn)過(guò)程的最優(yōu)控制等多階段決策

2、過(guò)程的多階段決策過(guò)程的最優(yōu)化的目標(biāo)最優(yōu)化的目標(biāo)：達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)主要用于解決：主要用于解決：最優(yōu)路徑問(wèn)題最優(yōu)路徑問(wèn)題5動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃模型分類模型分類離散確定型離散確定型離散隨機(jī)型離散隨機(jī)型連續(xù)確定型連續(xù)確定型連續(xù)隨機(jī)型連續(xù)隨機(jī)型6多階段決策問(wèn)題(Multi-Stage decision process)狀態(tài) x1階段1T1決策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+17 動(dòng)態(tài)規(guī)劃方法與動(dòng)態(tài)規(guī)劃方法與“時(shí)間時(shí)間”關(guān)系很密關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的

3、切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)動(dòng)態(tài)”的意思。然而它也可以處理與時(shí)間無(wú)關(guān)的的意思。然而它也可以處理與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題，只要在問(wèn)題中人為地引入靜態(tài)問(wèn)題，只要在問(wèn)題中人為地引入“時(shí)時(shí)段段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題。在本章中將介紹這種處理方法。決策問(wèn)題。在本章中將介紹這種處理方法。82.多階段決策問(wèn)題舉例多階段決策問(wèn)題舉例 屬于多階段決策類的問(wèn)題很多，例如屬于多階段決策類的問(wèn)題很多，例如 1)1)工廠生產(chǎn)過(guò)程工廠生產(chǎn)過(guò)程：由于市場(chǎng)需求是一隨著：由于市場(chǎng)需求是一隨著時(shí)間而變化的因素，

4、因此，為了取得全年時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，逐月或者逐季度地根據(jù)庫(kù)存和需求情況決逐月或者逐季度地根據(jù)庫(kù)存和需求情況決定生產(chǎn)計(jì)劃安排。定生產(chǎn)計(jì)劃安排。9 例例1：某廠與用戶簽訂了如表所示的交貨合同，：某廠與用戶簽訂了如表所示的交貨合同，表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每月月400件，該廠倉(cāng)庫(kù)的存貨能力為件，該廠倉(cāng)庫(kù)的存貨能力為300件。已知件。已知每百件貨物的生產(chǎn)費(fèi)用為每百件貨物的生產(chǎn)費(fèi)用為10000元。在進(jìn)行生產(chǎn)元。在進(jìn)行生產(chǎn)的月份，工廠還要支付經(jīng)常費(fèi)的月份，

5、工廠還要支付經(jīng)常費(fèi)4000元。倉(cāng)庫(kù)保元。倉(cāng)庫(kù)保管費(fèi)為每百件貨物每月管費(fèi)為每百件貨物每月1000元。假設(shè)開(kāi)始時(shí)及元。假設(shè)開(kāi)始時(shí)及6月底交貨后無(wú)存貨。月底交貨后無(wú)存貨。月份123456交貨量（百件）125321102)2)設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買來(lái)時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，剛買來(lái)時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價(jià)值也高，隨著使用年限的增加，就會(huì)逐漸處理價(jià)值也高，隨著使用年限的增加，就會(huì)逐漸變?yōu)楣收隙啵S修費(fèi)用增加，可正常使用的工時(shí)變?yōu)楣收隙啵S修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用減少，

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

7、94012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040123)3)連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題：一般化工生產(chǎn)過(guò)程中，常包含一一般化工生產(chǎn)過(guò)程中，常包含一系列完成生產(chǎn)過(guò)程的設(shè)備，前一系列完成生產(chǎn)過(guò)程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出，

8、以使程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。總產(chǎn)量最大。13 以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，因此在這類多階段決策問(wèn)題中，階段的劃分常取因此在這類多階段決策問(wèn)題中，階段的劃分常取時(shí)間區(qū)段來(lái)表示，并且各個(gè)階段上的決策往往也時(shí)間區(qū)段來(lái)表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)動(dòng)態(tài)”的含的含義，所以把處理這類動(dòng)態(tài)問(wèn)題的方法稱為動(dòng)態(tài)規(guī)義，所以把處理這類動(dòng)態(tài)問(wèn)題的方法稱為動(dòng)態(tài)規(guī)劃方法。劃方法。 不過(guò)，實(shí)際中尚有許多不包含時(shí)間因素的一不過(guò)，實(shí)際中尚有許多不包含時(shí)間因素的一類類“靜態(tài)靜態(tài)”決策問(wèn)題，就其本

9、質(zhì)而言是一次決策決策問(wèn)題，就其本質(zhì)而言是一次決策問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)入階段的概念當(dāng)作多階段決策問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。劃方法加以解決。14 4 4）資源分配問(wèn)題資源分配問(wèn)題：便屬于這類靜態(tài)問(wèn)題。如：某工業(yè)部門(mén)或公司，擬對(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)題后面我們

10、將詳細(xì)討論這個(gè)問(wèn)題) )。15 例3：某工廠生產(chǎn)A、B、C三種產(chǎn)品，都使用某種原材料，現(xiàn)有原材料4噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時(shí)產(chǎn)生的收益如表所示，試確定使總收益最大的分配法。ABC0123010172006171808111116 5 5）運(yùn)輸網(wǎng)絡(luò)問(wèn)題運(yùn)輸網(wǎng)絡(luò)問(wèn)題：如圖如圖7-17-1所示的運(yùn)輸網(wǎng)絡(luò)，所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線上的數(shù)字表示兩地距離點(diǎn)間連線上的數(shù)字表示兩地距離( (也可是運(yùn)也可是運(yùn)費(fèi)、時(shí)間等費(fèi)、時(shí)間等) )，要求從，要求從A A至至F F的最短路線。的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分但是

11、，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為為5 5個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。1718 多階段決策過(guò)程的最優(yōu)化多階段決策過(guò)程的最優(yōu)化 動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃的基本概念和基本原理 動(dòng)態(tài)規(guī)劃模型的建立與求解動(dòng)態(tài)規(guī)劃模型的建立與求解191、階段：、階段：p把一個(gè)問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的把一個(gè)問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段階段，以便于按，以便于按一定的次序去求解。一定的次序去求解。p描述階段的變量稱為描述階段的變量稱為階段變量階段變量。階段的劃分，一般是根據(jù)時(shí)間和空。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于

12、問(wèn)題轉(zhuǎn)化為多階段決策。間的自然特征來(lái)進(jìn)行的，但要便于問(wèn)題轉(zhuǎn)化為多階段決策。2、狀態(tài)：、狀態(tài)：表示每個(gè)階段開(kāi)始所處的表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件自然狀況或客觀條件。通常一個(gè)階段有若。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過(guò)程狀態(tài)的變量稱為干個(gè)狀態(tài)，描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量狀態(tài)變量。年、年、月、月、路段路段一個(gè)數(shù)、一個(gè)數(shù)、一組數(shù)、一組數(shù)、一個(gè)向量一個(gè)向量 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合狀態(tài)允許集合。203、決策：、決策：表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，

13、可以作出不同的決定，從而確定下一階段的狀態(tài)從而確定下一階段的狀態(tài)，這種決定稱為這種決定稱為決策決策。描述決策的變量，稱為描述決策的變量，稱為決策變量決策變量。決策變量是狀態(tài)變量的函數(shù)。可。決策變量是狀態(tài)變量的函數(shù)。可用一個(gè)數(shù)、一組數(shù)或一向量（多維情形）來(lái)描述。用一個(gè)數(shù)、一組數(shù)或一向量（多維情形）來(lái)描述。在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允允許決策集合許決策集合。系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān)。而且

14、還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過(guò)程、多階段決策過(guò)程可以在各個(gè)階段進(jìn)行決策，去控制過(guò)程發(fā)展的多段過(guò)程；可以在各個(gè)階段進(jìn)行決策，去控制過(guò)程發(fā)展的多段過(guò)程；其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的；其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的；21),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。如果第程。如果第k階段狀態(tài)變量階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)的值、該階段的決策變量一經(jīng)確定，第確定，第k+1階段狀態(tài)變

15、量階段狀態(tài)變量sk+1的值也就確定。的值也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程，能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程，即即具有無(wú)后效性具有無(wú)后效性的多階段決策過(guò)程。的多階段決策過(guò)程。22),(),(),(122231112kkkkusTsusTsusTs 動(dòng)態(tài)規(guī)劃中能動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程的形式方程的形式。狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下?tīng)顟B(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下無(wú)后效性

16、無(wú)后效性(馬爾可夫性馬爾可夫性)如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；階段以前各段狀態(tài)的影響；過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展；構(gòu)造過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展；構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無(wú)后效性的要求；動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無(wú)后效性的要求；狀態(tài)變量要滿足無(wú)后效性的要求；狀態(tài)變量要滿足無(wú)后效性的要求；如果狀態(tài)變量不能滿足無(wú)后效如果狀態(tài)變量不能滿足無(wú)后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方

17、法。23 5、策略：、策略：是一個(gè)按順序排列的決策組成的集合。在實(shí)際問(wèn)題中，可供選擇的是一個(gè)按順序排列的決策組成的集合。在實(shí)際問(wèn)題中，可供選擇的策略有一定的范圍，稱為策略有一定的范圍，稱為允許策略集合允許策略集合。從允許策略集合中找出達(dá)。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為到最優(yōu)效果的策略稱為最優(yōu)策略最優(yōu)策略。 6、狀態(tài)轉(zhuǎn)移方程：、狀態(tài)轉(zhuǎn)移方程：是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程，描述了狀態(tài)轉(zhuǎn)是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。移規(guī)律。 7、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，為用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一

18、種數(shù)量指標(biāo)，為指標(biāo)函數(shù)指標(biāo)函數(shù)。指標(biāo)函。指標(biāo)函數(shù)的最優(yōu)值，稱為數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)最優(yōu)值函數(shù)。在不同的問(wèn)題中，指標(biāo)函數(shù)的含。在不同的問(wèn)題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源消耗等。義是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源消耗等。動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)應(yīng)具有動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)應(yīng)具有可分離性可分離性，并滿足，并滿足遞推遞推關(guān)系。關(guān)系。24),(,111,1nkknkkkksusVus指標(biāo)函數(shù)指標(biāo)函數(shù): 指標(biāo)函數(shù)形式指標(biāo)函數(shù)形式: 和、和、積積),(111,nkkkknksususV可遞推可遞推),()(1,susVoptsfnkknkkkuunk 效益

19、效益最優(yōu)函數(shù)最優(yōu)函數(shù): 25,*2*1nuuu,*2*1nsss解多階段決策過(guò)程問(wèn)題，求出解多階段決策過(guò)程問(wèn)題，求出 最優(yōu)策略最優(yōu)策略，即最優(yōu)，即最優(yōu)決策序列決策序列 susvoptsfnkknkkkuunk1, f1(s1) 最優(yōu)軌線最優(yōu)軌線，即執(zhí)行最優(yōu)策略時(shí)的即執(zhí)行最優(yōu)策略時(shí)的狀態(tài)序列狀態(tài)序列 最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值),(*1*1*,1*,1nnnnususVV從從 k 到終點(diǎn)最優(yōu)策略到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值子策略的最優(yōu)目標(biāo)函數(shù)值261、動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)摹?dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡(jiǎn)稱基本方程

20、）。邊界條件（簡(jiǎn)稱基本方程）。要做到這一點(diǎn)，就必須將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階要做到這一點(diǎn)，就必須將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類型的子問(wèn)題，然后逐個(gè)求解。而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類型的子問(wèn)題，然后逐個(gè)求解。即從邊界條件開(kāi)始，逐段遞推尋優(yōu)，在每一個(gè)子問(wèn)題的求解即從邊界條件開(kāi)始，逐段遞推尋優(yōu)，在每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解

21、。后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。272、在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)一、在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)一段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的一般是不同的. 最優(yōu)化原理：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去最優(yōu)化原理：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，

22、余下的的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。決策序列必然構(gòu)成最優(yōu)子策略。”也就是說(shuō)，一個(gè)最優(yōu)策略的子策也就是說(shuō)，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。略也是最優(yōu)的。 3、在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段、在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。逐段變換得到，從而確定了最優(yōu)路線。28建立動(dòng)態(tài)規(guī)劃模型的步驟建立動(dòng)態(tài)規(guī)劃模型的步驟 1、劃分階段、劃分階段劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解

23、多階段決策問(wèn)題的第一步，在確劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過(guò)程劃分為若干定多階段特性后，按時(shí)間或空間先后順序，將過(guò)程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)題要人為地賦予相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)題要人為地賦予“時(shí)間時(shí)間”概念，概念，以便劃分階段。以便劃分階段。2、正確選擇狀態(tài)變量、正確選擇狀態(tài)變量選擇變量既要能確切描述過(guò)程演變又要滿足無(wú)后效性，而且各選擇變量既要能確切描述過(guò)程演變又要滿足無(wú)后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找。過(guò)

24、程演變的特點(diǎn)中尋找。3、確定決策變量及允許決策集合、確定決策變量及允許決策集合通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量，同時(shí)要給出決通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。策變量的取值范圍，即確定允許決策集合。294、確定狀態(tài)轉(zhuǎn)移方程、確定狀態(tài)轉(zhuǎn)移方程根據(jù)根據(jù)k 階段狀態(tài)變量和決策變量，寫(xiě)出階段狀態(tài)變量和決策變量，寫(xiě)出k+1階段狀態(tài)變量，狀階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程 階段指標(biāo)函數(shù)是指第階段

25、指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫(xiě)出動(dòng)階段末所獲得收益的最優(yōu)值，最后寫(xiě)出動(dòng)態(tài)規(guī)劃基本方程。態(tài)規(guī)劃基本方程。以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問(wèn)題具體分析，只有通過(guò)不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。問(wèn)題具體分析，只有通過(guò)不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧

26、。 2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路徑問(wèn)題求從A到E的最短路徑2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f522425112141061

27、04131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最優(yōu)決策2511214106104131112396581052C1C3D1A

28、B1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最優(yōu)

29、決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1

30、)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最優(yōu)決策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最優(yōu)決策2511

31、214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21

32、狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D12511214106104131112396581052C1C3D1AB1B3B2D2EC2

33、f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E從A到E的最短路徑為19，路線為AB 2C1 D1 E 45 用動(dòng)態(tài)規(guī)劃方法求最短路46 先從先從F F開(kāi)始，因?yàn)殚_(kāi)始，因?yàn)镕 F是終點(diǎn)。再無(wú)后繼過(guò)程，故可以是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第接著考慮第5 5階段上所有可能狀態(tài)階段上所有可能狀態(tài)E E1 1，E E2 2的最優(yōu)

34、后續(xù)的最優(yōu)后續(xù)過(guò)程。因?yàn)閺倪^(guò)程。因?yàn)閺腅 E1 1 ,E,E2 2到到F F的路線是唯一的，所以的路線是唯一的，所以E E1 1，E E2 2的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到F F，它們的最，它們的最短距離分別是短距離分別是4 4和和3 3。 接著考慮階段接著考慮階段4 4上可能的狀態(tài)上可能的狀態(tài)D D1 1，D D2 2，D D3 3 到到F F的的最優(yōu)決策和最優(yōu)后繼過(guò)程在狀態(tài)最優(yōu)決策和最優(yōu)后繼過(guò)程在狀態(tài)D D1 1上，到上，到E E1 1是是3 3，到到E E2 2是是5 5，綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決，綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到策是到E

35、E1 1, ,最優(yōu)后繼過(guò)程是最優(yōu)后繼過(guò)程是D D1 1EE1 1FF ，最短距離是，最短距離是7 7。同理，狀態(tài)。同理，狀態(tài)D D2 2的最優(yōu)決策是至的最優(yōu)決策是至E E2 2 ；D D3 3的最優(yōu)決的最優(yōu)決策是到策是到E E1 1。47 同樣，當(dāng)階段同樣，當(dāng)階段4 4上所有可能狀態(tài)的最優(yōu)上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段3 3上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如程，如C C1 1的最優(yōu)決策是到的最優(yōu)決策是到D D1 1, ,最優(yōu)路線是最優(yōu)路線是C C1 1D D1 1E E1 1F F ，最短距離是，最短距離是1212依此類推，最依此類推，最后可以得到從初始狀態(tài)后可以得到從初始狀態(tài)A A的最優(yōu)決策是到的最優(yōu)決策是到F F最最優(yōu)路線是優(yōu)路線是A AB B1 1C C2 2D D2 2E E2 2 F F ，全程的最短，全程的最短距離是距離是1717。圖。圖7 71