第二講動態(tài)規(guī)劃

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

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

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

4、因此，為了取得全年時間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計(jì)劃安排。定生產(chǎn)計(jì)劃安排。9 例例1：某廠與用戶簽訂了如表所示的交貨合同，：某廠與用戶簽訂了如表所示的交貨合同，表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每表中數(shù)字為月底的交貨量。該廠的生產(chǎn)能力為每月月400件，該廠倉庫的存貨能力為件，該廠倉庫的存貨能力為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元。倉庫保元。倉庫保管費(fèi)為每百件貨物每月管費(fèi)為每百件貨物每月1000元。假設(shè)開始時及元。假設(shè)開始時及6月底交貨后無存貨。月底交貨后無存貨。月份123456交貨量（百件）125321102)2)設(shè)備更新問題設(shè)備更新問題：一般企業(yè)用于生產(chǎn)活動的設(shè)備，一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，剛買來時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價值也高，隨著使用年限的增加，就會逐漸處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用減少，

6、加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)因此就需要綜舊的買新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。好。例例2 2：下表給出了某單位的預(yù)測數(shù)據(jù)，現(xiàn)決定考慮到：下表給出了某單位的預(yù)測數(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è)備購置費(fèi)舊設(shè)備折價1993123451816161414889910502015105219

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

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

9、質(zhì)而言是一次決策決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。劃方法加以解決。14 4 4）資源分配問題資源分配問題：便屬于這類靜態(tài)問題。如：某工業(yè)部門或公司，擬對其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素?zé)o關(guān)，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題( (后面我們將詳細(xì)討論這個問題后面我們

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

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

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

13、可以作出不同的決定，從而確定下一階段的狀態(tài)從而確定下一階段的狀態(tài)，這種決定稱為這種決定稱為決策決策。描述決策的變量，稱為描述決策的變量，稱為決策變量決策變量。決策變量是狀態(tài)變量的函數(shù)。可。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。用一個數(shù)、一組數(shù)或一向量（多維情形）來描述。在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為在實(shí)際問題中決策變量的取值往往在某一范圍之內(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)過去的歷史狀態(tài)和決策有關(guān)。而且

14、還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過程、多階段決策過程可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)的；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)的；21),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過個狀態(tài)到另一個狀態(tài)的演變過程。如果第程。如果第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能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即即具有無后效性具有無后效性的多階段決策過程。的多階段決策過程。22),(),(),(122231112kkkkusTsusTsusTs 動態(tài)規(guī)劃中能動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程的形式方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性

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

17、法。23 5、策略：、策略：是一個按順序排列的決策組成的集合。在實(shí)際問題中，可供選擇的是一個按順序排列的決策組成的集合。在實(shí)際問題中，可供選擇的策略有一定的范圍，稱為策略有一定的范圍，稱為允許策略集合允許策略集合。從允許策略集合中找出達(dá)。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為到最優(yōu)效果的策略稱為最優(yōu)策略最優(yōu)策略。 6、狀態(tài)轉(zhuǎn)移方程：、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。移規(guī)律。 7、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，為用來衡量所實(shí)現(xiàn)過程優(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ù)。在不同的問題中，指標(biāo)函數(shù)的含。在不同的問題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。動態(tài)規(guī)劃模型的指標(biāo)函數(shù)應(yī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解多階段決策過程問題，求出解多階段決策過程問題，求出 最優(yōu)策略最優(yōu)策略，即最優(yōu)，即最優(yōu)決策序列決策序列 susvoptsfnkknkkkuunk1, f1(s1) 最優(yōu)軌線最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的即執(zhí)行最優(yōu)策略時的狀態(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、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)摹討B(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程

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

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

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

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

24、程演變的特點(diǎn)中尋找。3、確定決策變量及允許決策集合、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。策變量的取值范圍，即確定允許決策集合。294、確定狀態(tài)轉(zhuǎn)移方程、確定狀態(tài)轉(zhuǎn)移方程根據(jù)根據(jù)k 階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出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ù)，建立動態(tài)規(guī)劃基本方程、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(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)值，最后寫出動階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。態(tài)規(guī)劃基本方程。以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧

26、。 2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路徑問題求從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 用動態(tài)規(guī)劃方法求最短路46 先從先從F F開始，因?yàn)殚_始，因?yàn)镕 F是終點(diǎn)。再無后繼過程，故可以是終點(diǎn)。再無后繼過程，故可以接著考慮第接著考慮第5 5階段上所有可能狀態(tài)階段上所有可能狀態(tài)E E1 1，E E2 2的最優(yōu)

34、后續(xù)的最優(yōu)后續(xù)過程。因?yàn)閺倪^程。因?yàn)閺腅 E1 1 ,E,E2 2到到F F的路線是唯一的，所以的路線是唯一的，所以E E1 1，E E2 2的最優(yōu)決策和最優(yōu)后繼過程就是到的最優(yōu)決策和最優(yōu)后繼過程就是到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)后繼過程在狀態(tài)最優(yōu)決策和最優(yōu)后繼過程在狀態(tài)D D1 1上，到上，到E E1 1是是3 3，到到E E2 2是是5 5，綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決，綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決策是到策是到E E1 1, ,最優(yōu)后繼過程是最優(yōu)后繼過程是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)后繼過程都已求得后，便可以開始考慮階段后繼過程都已求得后，便可以開始考慮階段3 3上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如程，如C C1 1的最優(yōu)決策是到的最優(yōu)決策是到D D1 1, ,最優(yōu)路線是最優(yōu)路線是C C1 1D D1 1