運(yùn)籌學(xué)課程07-動態(tài)規(guī)劃.ppt

1、動態(tài)規(guī)劃,Dynamic Programming,不要過河拆橋 追求全局最優(yōu), 多階段決策過程的最優(yōu)化 動態(tài)規(guī)劃的基本概念和基本原理 動態(tài)規(guī)劃方法的基本步驟 動態(tài)規(guī)劃方法應(yīng)用舉例,本章內(nèi)容,一、多階段決策過程的最優(yōu)化,示例1（工廠生產(chǎn)安排）： 某種機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷生產(chǎn)條件下機(jī)器完好率為0.7，即如果年初有u臺完好機(jī)器投入生產(chǎn)，則年末完好的機(jī)器數(shù)量為0.7u臺。系數(shù)0.7稱為完好率。年初投入高負(fù)荷運(yùn)行的u臺機(jī)器的年產(chǎn)量為8u噸。系數(shù)8稱為單臺產(chǎn)量。低負(fù)荷運(yùn)行時，機(jī)器完好率為0.9，單臺產(chǎn)量為5噸。設(shè)開始時有1000臺完好機(jī)器，要制訂五年計(jì)劃，每年年初將完好的機(jī)器一部分分配到

2、高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。,設(shè)有數(shù)量為y的某種資源，將它分別投入兩種生產(chǎn)方式A和B，已知收益函數(shù)分別是g(x)和h(x)，x為資源投入量。設(shè)這種資源用于生產(chǎn)后還可以回收一部分用于生產(chǎn)，A、B的回收率分別為a和b（ 0a1，0b1 ）， 問：對總數(shù)量為y的資源進(jìn)行n個階段的生產(chǎn)，應(yīng)如何分配每個階段投入A、B的資源數(shù)量，才能使總收益最大？,推廣：多階段資源分配問題,示例2（設(shè)備更新問題）：,一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價(jià)值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時減少，加工質(zhì)量下降，

3、經(jīng)濟(jì)效益差，并且，使用的年限越長、處理價(jià)值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。,一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。,示例3 （連續(xù)生產(chǎn)過程的控制問題）：,示例4、最短路徑問題,給定一個交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總費(fèi)用最?。?。,1,2,3,4,5,6,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,

4、F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,示例5（生產(chǎn)與存儲問題）： 某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今后四個月市場需求預(yù)測及每月生產(chǎn)j個單位產(chǎn)品的費(fèi)用如下： 每月庫存i個單位產(chǎn)品的費(fèi)用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計(jì)劃開始和計(jì)劃期末庫存量都是零，試制定四個月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下，使總費(fèi)用最小。,每個月視為一個階段，,每個階段都須決定生產(chǎn)幾個、庫存幾個,上一個階段的決策直接影響下一個階段的決策,由于航天飛機(jī)的運(yùn)動的環(huán)境是不斷變化的，因此就

5、要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問題）。,示例6（航天飛機(jī)飛行控制問題）：,10,所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。 每個階段的決策均確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達(dá)到最優(yōu)。 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。,1,2,n,狀態(tài),

6、決策,狀態(tài),決策,狀態(tài),狀態(tài),決策,不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。,某些線性規(guī)劃、非線性規(guī)劃等靜態(tài)規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決。,DP是上個世紀(jì)五十年代貝爾曼(B.E.Bellman)為代表 的研究成果，屬于現(xiàn)代控制理論的一部分。其最優(yōu)化原理， 可歸結(jié)為一個遞推公式。,注意：動態(tài)規(guī)劃是求解某類多階段決策問題的一種方法，是考察問題的一種途徑，不是一種算法。必須對具體問題進(jìn)行具體分析，運(yùn)用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。,動態(tài)規(guī)劃思想示例

7、：,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從 A到E的最短路徑問題。,第四階段：兩個始點(diǎn) 和 ，終點(diǎn)只有一個；,分析得知：從 和 到E的最短路徑唯一。,第三階段：有三個始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對始點(diǎn) 和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2 的最短路 徑問題： 分析得知：如果經(jīng)過C1，則最短路為C1-D2-E； 如果經(jīng)過C2，則最短路為C2-D2-E； 如

8、果經(jīng)過C3，則最短路為C3-D1-E。,第二階段：有4個始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3 的最短路徑問題： 分析得知：如果經(jīng)過B1，則走B1-C2-D2-E； 如果經(jīng)過B2，則走B2-C3-D1-E； 如果經(jīng)過B3，則走B3-C3-D1-E； 如果經(jīng)過B4，則走B4-C3-D1-E。,第一階段：只有1個始點(diǎn)A，終點(diǎn)有B1,B2,B3,B4 。對始點(diǎn)和終 點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題： 最后，可以得到：從A到E的最短路徑為A B4 C3 D1 E,以上計(jì)算過程及結(jié)果，可用

9、下圖表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點(diǎn)到E的最短路徑。 以上過程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,二、動態(tài)規(guī)劃的基本概念和基本原理,基本概念 1、階段： 把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。 描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要

10、便于問題轉(zhuǎn)化為多階段決策。,2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量。,一個數(shù)一組數(shù)一個向量,狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。,3、決策：表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。,描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。 在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。,系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決

11、策有關(guān)。,4、多階段決策過程,可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；,其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)的；,圖示如下：,狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。,其狀態(tài)轉(zhuǎn)移方程如下（一般形式）,能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。,如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。,動態(tài)規(guī)劃中能 處理的狀態(tài)轉(zhuǎn)移 方程的形式。,狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下,無后效性(馬

12、爾可夫性),如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；,過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；,狀態(tài)變量要滿足無后效性的要求；,5、策略：是一個按順序排列的決策組成的集合。在實(shí)際問題中，可供選擇的策略有一定的范圍，稱為允許策略集合。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。,6、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。,7、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，為指標(biāo)函數(shù)。指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)

13、量或資源消耗等。 動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。,小結(jié):,指標(biāo)函數(shù)形式:,和、,積,無后效性,可遞推,原過程的一個后部子過程：,原過程的一個后部子過程的策略：,對于任意給定的k（1 kn），從第k段到第n段的過程稱為原過程的一個后部子過程,最優(yōu)策略,解多階段決策過程問題，求出,f1(s1),從 k 到終點(diǎn)最優(yōu)策略 子策略的最優(yōu)目標(biāo)函數(shù)值,問題分成4個階段：,k=1，2，3，4,線路：,線路：,k=1：,k=3：,階段,狀態(tài),第一階段的狀態(tài)：,第二階段的狀態(tài)：,sk,s4,Sk =sk,S3 =s3,=5，6，7,注：n個階段的決策過程有個n+1狀態(tài)變量,sn+1表示s

14、n演變的結(jié)果,S5 =10,決策,決策,可取值為：5，6，7,=5，6，7,允許決策集合,策略,最短路問題：,策略,= 行進(jìn)方案,如 ,允許策略集合,最優(yōu)策略：使整個問題達(dá)到最優(yōu)效果的策略,策略： ,最優(yōu)策略=最短的行進(jìn)路線,策略, , , ,最短路問題：,原過程的一個策略：, ,后部子過程的策略, ,后部子過程的策略,后部子過程的策略,or ,每月庫存i個單位產(chǎn)品的費(fèi)用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計(jì)劃開始和計(jì)劃期末庫存量都是零，試制定四個月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下，使總費(fèi)用最小。,k=1，2，3，4,階段,第k階段的狀態(tài)變量sk

15、,S1=0，,S2=0,1,2,3，,S3=0,1,2,3，,S4=0,1,2,3,=第k個月月初的庫存量,（生產(chǎn)與存儲問題）某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今四個月市場需求預(yù)測如下表，又每月生產(chǎn)j個單位產(chǎn)品的費(fèi)用為,=2,3,4,5,=2,3,4,5,=0,1,2,3,=3,一個策略=一個生產(chǎn)方案,2，5，0，4,2，3，2，4,費(fèi)用：21（千元）,費(fèi)用：23（千元）,最優(yōu)策略：,使總費(fèi)用最小的生產(chǎn)方案,最優(yōu)化原理（基本原理） 作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的當(dāng)前狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。”也就是說，一個最優(yōu)策略的子策略

16、也是最優(yōu)的。,對最短路問題：,最短路問題的基本方程：,k=4,3,2,1,從最后一階段開始，用由后向前的方法，求出各點(diǎn)到終點(diǎn)的 最短路線，最后，求得由起點(diǎn)到終點(diǎn)的最短路線。,對于生產(chǎn)與存儲問題：某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今四個月市場需求預(yù)測如下表，又每月生產(chǎn)j個單位產(chǎn)品費(fèi)用為 每月庫存i個單位產(chǎn)品的費(fèi)用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計(jì)劃開始和計(jì)劃期末庫存量都是零，試制定四個月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下，使總費(fèi)用最小。,階段k=1，2，3，4,狀態(tài)變量 =第k個月月初的庫存量,狀態(tài)轉(zhuǎn)移方程：,當(dāng)k=4時，,u4(s4)對應(yīng)的總費(fèi)用=

17、生產(chǎn)費(fèi)+庫存費(fèi),庫存費(fèi)E(i)=0.5i，,最大庫存容量為3個單位，,最大生產(chǎn)能力為6個單位，,計(jì)劃開始和計(jì)劃期末庫存量為零,0,1,2,3,4,7,4,3,6.5,3,2,6,2,1,5.5,1,當(dāng)k=3時，,庫存費(fèi)E(i)=0.5i，,最大庫存容量為3個單位，,最大生產(chǎn)能力為6個單位，,計(jì)劃開始和計(jì)劃期末庫存量為零,0,1,2,3,0,1,2,3,0,u3(3)對應(yīng)的總費(fèi)用=生產(chǎn)費(fèi)+庫存費(fèi),庫存費(fèi)E(i)=0.5i，,最大庫存容量為3個單位，,最大生產(chǎn)能力為6個單位，,計(jì)劃開始和計(jì)劃期末庫存量為零,0,2 3 4 5,12,12 .5,13,13.5,12,2,1,1 2 3 4,11.5

18、,12,12.5,13,11.5,1,2,0 1 2 3,8 11.5 12 12.5,8,0,3,0 1 2,8,8,0,11.5,12,0,1,2,3,4,7,4,3,6.5,3,2,6,2,1,5.5,1,當(dāng)k=2時，,u2(s2)對應(yīng)的總費(fèi)用=生產(chǎn)費(fèi)+庫存費(fèi),0,2 3 4 5,12,12 .5,13,13.5,12,2,1,1 2 3 4,11.5,12,12.5,13,11.5,1,2,0 1 2 3,8 11.5 12 12.5,8,0,3,0 1 2,8 11.5 12,8,0,k=3,當(dāng)k=2時，,0,1,2,3,3 4 5 6,18,18.5,16,17,16,5,2 3

19、4 5,17.5 18 15.5 16.5,1 2 3 4,17,0 1 2 3,13.5 17 14.5 15.5,15.5,4,15,3,13.5,0,17.5,15,16,當(dāng)k=1時，,u1(0)對應(yīng)的總費(fèi)用=生產(chǎn)費(fèi),k=2,0,1,2,3,3 4 5 6,18,18.5,16,17,16,5,2 3 4 5,17.5 18 15.5 16.5,1 2 3 4,17 17.5 15 16,0 1 2 3,13.5 17 14.5 15.5,15.5,4,15,3,13.5,0,當(dāng)k=1時，,0,2 3 4 5,22 21.5,21,2,21,21.5,生產(chǎn)存儲問題的基本方程：,最短路問題

20、的基本方程：,k=4,3,2,1,三、動態(tài)規(guī)劃方法建模基本要求與步驟,建模要素：,1)階段數(shù) k,2)狀態(tài)變量 sk,3)決策變量 uk（ sk ）,4)指標(biāo)函數(shù) Vk,n,狀態(tài)轉(zhuǎn)移方程,5)最優(yōu)值函數(shù) fk(sk),DP建?；疽螅?1）所研究的問題必須能夠分成幾個相互聯(lián)系的階段，而且在每一個階段都具有需要進(jìn)行決策的問題。,2）在每一階段都必須有若干個與該階段相關(guān)的狀態(tài)，建模時總是從與決策有關(guān)的條件中，或是從問題的約束條件中去選擇狀態(tài)變量。,一般情況下，狀態(tài)是所研究系統(tǒng)在該階段可能處于的情況或條件,3) 具有明確的指標(biāo)函數(shù)，且階段指標(biāo)值可以計(jì)算,4) 能正確列出最優(yōu)值函數(shù)的遞推公式和邊界條

21、件,（b）能通過現(xiàn)階段的決策，使當(dāng)前狀態(tài)轉(zhuǎn)移成下一階段的狀態(tài)（反映過程的演變性）,即 能夠給出狀態(tài)轉(zhuǎn)移方程,（c）狀態(tài)的無后效性,狀態(tài)的選取必須注意以下幾個要點(diǎn)：,（a）在所研究問題的各階段，都能直接或間接確定狀態(tài)變量的取值（可知性）,建立DP模型的步驟 1、劃分階段 劃分階段是運(yùn)用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。 2、正確選擇狀態(tài)變量 選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找。

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

23、建模方法與技巧。,四、動態(tài)規(guī)劃方法應(yīng)用舉例,動態(tài)規(guī)劃常用基本方程：,從A 地到D 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,1、最短路徑問題,解：整個計(jì)算過程分三個階段，從最后一個階段開始。,第一階段（C D）： C 有三條路線到終點(diǎn)D 。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4,

24、d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5,第二階段（B C）： B 到C 有六條路線。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路線為B1C1 D),d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1

25、 (C3 ) 1+4 3 = min 6 = 3 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路線為B2C1 D),第三階段（ A B ）： A 到B 有二條路線。,f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437, f3 (A) = min = min6,7=6,d(A, B1 ) f2 ( B1 ) d(A, B2 ) f2 ( B2 ),(最短路線為AB1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,

26、3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,最短路線為 AB1C1 D 路長為 6,2、資源分配問題,某公司有資金a萬元，擬投資于n個項(xiàng)目，已知對第i個項(xiàng)目投資xi萬元，收益為g i (xi)，問應(yīng)如何分配資金可使總收益最大？,解：階段k=1,2, ,n,狀態(tài)變量sk,決策變量uk,：第k個項(xiàng)目的投資額,：在第k階段時可以用于投資 第k到第n個項(xiàng)目的資金數(shù),狀態(tài)轉(zhuǎn)移方程：,sk+1 = sk -uk,指標(biāo)函數(shù)Vk,n,第k至第n個項(xiàng)目的最大總收益,最優(yōu)值函數(shù)

27、,邊界條件：,k=n,n-1, ,2,1,資源分配問題的動態(tài)規(guī)劃基本方程：,建立遞推公式：,投資額,收益,工廠,某有色金屬公司擬撥出50萬元對所屬三家冶煉廠進(jìn)行技術(shù)改造，若以十萬元為最少分割單位，各廠收益與投資的關(guān)系如下表：,問：對三個工廠如何分配， 才能使總收益達(dá)到最大？,狀態(tài)變量 sk：,階段 k=1，2，3,決策變量 uk：,給工廠k的投資額,在第k階段時可供工 廠k到工廠3分配的 資金數(shù),狀態(tài)轉(zhuǎn)移方程：,sk+1 = sk -uk,g k (uk)=給工廠k投資 uk （十萬元）的收益,指標(biāo)函數(shù) Vk,n,資源分配問題示例,fk（ sk ）,投資工廠k至工廠3所得的最大總收益,求f1（

28、 5 ）,=在工廠k，可供分配的資金數(shù)為sk時，,基本方程：,k=3,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,投資額,收益,工廠,k=2,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9.5,4,5,投資額,收益,工廠,sk+1 = sk -uk,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,k=1,sk+1 = sk -uk,投資額,收益,工廠,5,16,0 1 2 3 4 5,12,1,17,最大總收益：,最優(yōu)策略：,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9

29、.5,4,5,系統(tǒng)由n個部件串聯(lián)組成，每一個部件上裝有備用件，部件i(i=1,2, ,n)上裝有xi個備用元件時，正常工作的概率為pi （ xi ）。設(shè)裝一個i部件的設(shè)備元件費(fèi)用為ci ，重量wi為，要求總費(fèi)用不超過C，總重量不超過W，問如何選擇各個部件的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大？,3、復(fù)合系統(tǒng)工作可靠性問題,設(shè)A-整個系統(tǒng)正常工作，Ai部件i正常工作,滿足：,非線性規(guī)劃問題,解： n個部件=n個階段,決策變量uk =,部件k上所裝的備用元件數(shù)xk,狀態(tài)變量：,sk,=第k個到第n個部件可使用的總費(fèi)用,yk,=第k個到第n個部件容許的總重量,狀態(tài)轉(zhuǎn)移方程：,指標(biāo)函數(shù)Vk,n,最優(yōu)

30、指標(biāo)函數(shù)fk(sk， yk ）=,在部件k，可使用 的總費(fèi)用為 sk，總重量為 yk 時，從部件k 到部件n的系統(tǒng)工作可靠性的最大值,復(fù)合系統(tǒng)工作可靠性的動態(tài)規(guī)劃基本方程為：,與問題無關(guān),有一個徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？,這就是背包問題。類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。,4、背包問題,設(shè)xj 為第j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：,用動態(tài)規(guī)劃方法求解，令 fx(y) = 總重

31、量不超過 y 公斤，包中只裝有前k 種物品時的最大使用價(jià)值。 其中y 0， k 1,2, , n 。所以問題就是求 fn(a),其遞推關(guān)系式為：,當(dāng) k=1 時，有：,求下面背包問題的最優(yōu)解,解：a5 ，問題是求 f3(5),所以，最優(yōu)解為 X（1 . 1 . 0），最優(yōu)值為 Z = 13。,一種機(jī)器能在高低兩種不同的負(fù)荷狀態(tài)下工作。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)時，產(chǎn)量函數(shù)為P1=8u1，其中u1為在高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為a=0.7，即到年底有70的機(jī)器保持完好。在低負(fù)荷下生產(chǎn)時，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為b=0.9。設(shè)開始生產(chǎn)時共有10

32、00臺完好的機(jī)器，請問每年應(yīng)該如何把完好機(jī)器分配給高、低兩種負(fù)荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。,5、機(jī)器負(fù)荷分配問題,解 建立動態(tài)規(guī)劃模型： 分為5個階段，每個階段為1年。設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機(jī)器數(shù)目；k=1,2,3,4,5。 決策變量xk表示第k階段中分配給高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目；k=1,2,3,4,5。顯然sk-xk為分配給低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目。 狀態(tài)轉(zhuǎn)移方程為 階段指標(biāo) rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)指標(biāo)函數(shù) 其中k=1,2,3,4,5。 f6(s6)=0。,第5階段： 因?yàn)閒5(s5)是x5的線性單調(diào)增函數(shù)，故有x5* =

33、s5， 于是有f5(s5)=8s5。 第4階段：,同樣地，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4 ， f4(s4)=13.6s4。 對前幾個階段依次類推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因?yàn)槠诔豕灿型旰脵C(jī)器1000臺，故s1=1000。有f1(s1)=23.72s1 23720，即5年最大的產(chǎn)量為23720臺。得最優(yōu)解為 ， ， ， 。 這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷生產(chǎn)， 后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷生產(chǎn)。,下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目。已

34、知s1=1000,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:,上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點(diǎn)狀態(tài)s6沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自由的最優(yōu)策略。 如果終點(diǎn)附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結(jié)束時仍要保持500臺機(jī)器完好（而不是278臺），應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大？ 下面來分析： 根據(jù)終點(diǎn)條件有 可得,顯然，由于固定了終點(diǎn)的狀態(tài)，x5的取值受到了 約束。因此有 類似， 容易解得 ，f4(s4)=21.7s4-7500。,依次類推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1

35、)=29.4s1-7500 再采用順序方法遞推計(jì)算各年的狀態(tài)，有 s1=1000，,可見，為了使終點(diǎn)完好的機(jī)器數(shù)量增加到500臺，需要安排前四年中全部完好機(jī)器都要投入低負(fù)荷生產(chǎn)，且在第5年，也只能全部投入高負(fù)荷。 相應(yīng)的最優(yōu)指標(biāo)為 f1(s1)=29.4s1-750021900。 可以看到，因?yàn)樵黾恿烁郊訔l件，總產(chǎn)量f1(s1)要比終點(diǎn)自由情況下的產(chǎn)量要低。,一臺設(shè)備的價(jià)格為P，運(yùn)行壽命為n年，每年的維修費(fèi)用是設(shè)備役齡的函數(shù)，記為C(t)，新設(shè)備的役齡為t=0。舊設(shè)備出售的價(jià)格是設(shè)備役齡的函數(shù)，記為S(t)。在n年末，役齡為t的設(shè)備殘值為R(t)?，F(xiàn)有一臺役齡為T的設(shè)備，在使用過程中，使用者每

36、年都面臨“繼續(xù)使用”或“更新”的策略，,7、設(shè)備更新問題,設(shè)具體數(shù)據(jù)如下：,97,由以上計(jì)算可知，本問題有兩個決策，它們對應(yīng)的最小費(fèi)用都是115。,這兩個決策是,例（季節(jié)工問題）某工廠的生產(chǎn)任務(wù)隨季節(jié)波動，為降低成本宜用季節(jié)臨時工，但熟練的生產(chǎn)工人臨時難以聘到，培訓(xùn)新手費(fèi)用又高，各季節(jié)工人需用量如下表所示，每季節(jié)超過需用量聘用，每人浪費(fèi)2000元，聘用或解聘費(fèi)為200元乘上兩個季節(jié)聘用人數(shù)之差的平方，問廠長一年中應(yīng)如何聘用工人可使總花費(fèi)最小？（假定工資按實(shí)際工作時間計(jì)算，則聘用人數(shù)可為分?jǐn)?shù)）,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,方案1：,255 220 240 200 255,總費(fèi)用：,+200352,200552,+200202,+200402,=1249000,方案2：,255 245 245 245 255,總費(fèi)用：,+200102,200102,+200025,+20005,+200045,=190000,解：,階段1,，狀態(tài)變量sk第k-1季度聘用人數(shù),決策變量uk第k季度聘用人數(shù),狀態(tài)轉(zhuǎn)移方程：,sk+1 = uk,fk（sk）=第k-1季度聘用人數(shù)為sk人時，第k季度到 第4季度的最小總費(fèi)用,220s2255,gkuk255,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,2,3,4