《動態(tài)規(guī)劃模型》PPT課件

1、動態(tài)規(guī)劃模型,例1：最短線路問題,問題：現(xiàn)選擇一條從 到 的鋪管線路，使總距離最短,若用窮舉法要算23222148種不同線路，比較這48種結(jié)果即可得出，但當(dāng)段數(shù)增加，且各段選擇也增加時，窮舉法將變得非常龐大，以至利用計算機(jī)都十分困難,下面用動態(tài)規(guī)劃的方法計算,最短線路問題的特性,如果最短線路在第k站通過點 ，則這一線路在由 出發(fā)到達(dá)終點的那一部分線路，對于從 點到達(dá)終點的所有可能選擇的不同線路來說，必定也是距離最短的。（反正法,最短線路問題的這一特性啟示我們，從最后一段 開始，用從后向前逐步遞推的方法，求出各點到 的最短線路，最后求得從 到 的最短線路,k6時,設(shè) 表示由 到 的最短距離,設(shè)

2、表示由 到 的最短距離,顯然,k5時,如果 表示由 到 的最短距離,最短線路是,最短線路是,最短線路是,k4時,最短線路是,最短線路是,最短線路是,k3時,最短線路是,最短線路是,最短線路是,最短線路是,k2時,最短線路是,最短線路是,出發(fā)點只有,最短線路是,最短距離為18,說明,1)此例揭示了動態(tài)規(guī)劃的基本思想,2)動態(tài)規(guī)劃方法比窮舉法（48種）大大節(jié)省了計算量,3)計算結(jié)果不僅得到了 到 的最短線路和最短距離，而且得到了其它各點到 的最短線路和最短距離，這對于很多實際問題來說是很有用處的,動態(tài)規(guī)劃法求解的數(shù)學(xué)描述,討論動態(tài)規(guī)劃中最優(yōu)目標(biāo)函數(shù)的建立，一般有下列術(shù)語和步驟,階段,用動態(tài)規(guī)劃求解

3、多階段決策系統(tǒng)時，要根據(jù)具體情況，將系統(tǒng)適當(dāng)?shù)胤殖扇舾蓚€階段，以便分若干個階段求解，描述階段的變量稱為階段變量,上例分六個階段，是一個六階段的決策過程。例中由系統(tǒng)的最后階段向初始階段求最優(yōu)解的過程稱為動態(tài)規(guī)劃的逆推解法,狀態(tài),狀態(tài)表示系統(tǒng)在某一階段所處的位置或狀態(tài),上例中第一階段有一個狀態(tài),第二階段有兩個狀態(tài),過程的狀態(tài)可用狀態(tài)變量 來描述，某個階段所有可能狀態(tài)的全體可用狀態(tài)集合來描述,決策,某一階段的狀態(tài)確定之后，從該狀態(tài)演變到下一階段某一狀態(tài)所作的選擇稱為決策。描述決策的變量稱為決策變量,如上例中在第k階段用 表示處于 狀態(tài)時的決策變量,決策變量限制的范圍稱為允許決策集合,用 表示第k階段

4、從 出發(fā)的決策集合,策略,由每階段的決策 (i1,2,n)組成的決策函數(shù)序列稱為全過程策略或簡稱策略，用p表示,由系統(tǒng)的第k個階段開始到終點的決策過程稱為全過程的后部子過程，相應(yīng)的策略稱為后部子過程策略,用 表示k子過程策略,對于每一個實際的多階段決策過程，可供選擇的策略有一定的范圍限制，這個范圍稱為允許策略集合,允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略,狀態(tài)轉(zhuǎn)移,某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定,設(shè)第k個階段的狀態(tài)變量為 ，決策變量為 ，則第k+1個階段的狀態(tài) 用 表示從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱它為狀態(tài)轉(zhuǎn)移方程,階段效益,系統(tǒng)某階段的狀態(tài)一經(jīng)確定，

5、執(zhí)行某一決策所得的效益稱為階段效益，它是整個系統(tǒng)效益的一部分，是 階段狀態(tài)和 階段決策的函數(shù)， 記為,指標(biāo)函數(shù),指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益的數(shù)量表示，根據(jù)不同的實際問題，效益可以是利潤、距離、產(chǎn)量或資源的耗量等,指標(biāo)函數(shù)可以定義在全過程上，也可以定義在后部子過程上。指標(biāo)函數(shù)往往是各階段效益的某種和式，取最優(yōu)策略時的指標(biāo)函數(shù)稱為最優(yōu)策略指標(biāo),如上例中， 表示從 出發(fā)到終點 的最優(yōu)策略指標(biāo),上例中 顯然為零，稱它為邊值條件,而動態(tài)規(guī)劃的求解就是對kn,n-1,2,1逐級求出最優(yōu)策略指標(biāo)的過程,動態(tài)規(guī)劃的基本方程,例2：機(jī)器負(fù)荷分配問題,某種機(jī)器可以在高低兩種負(fù)荷下生產(chǎn)，年產(chǎn)量與年初投入

6、生產(chǎn)的機(jī)器數(shù)有關(guān)。在高負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中 為投入生產(chǎn)的機(jī)器數(shù)，年終的完好機(jī)器數(shù)為 ，稱系數(shù)0.7為機(jī)器完好率。在低負(fù)荷下生產(chǎn)時，年產(chǎn)量 ，式中 為投入生產(chǎn)的機(jī)器數(shù)，機(jī)器完好率為0.9，設(shè)開始時，完好的機(jī)器數(shù)為 臺，要求制定一個五年計劃，在每年開始時決定如何重新分配完好機(jī)器在兩種不同負(fù)荷下工作的數(shù)量，使五年的總產(chǎn)量最高,解：此問題與上例類似,設(shè)階段變量k表示年度,狀態(tài)變量 是第k年初擁有的完好機(jī)器數(shù)（也是第k-1年度末完好機(jī)器數(shù),決策變量 規(guī)定為第k年度中分配在高負(fù)荷下生產(chǎn)的機(jī)器數(shù),于是 是該年度分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù),k=2 k=3 k=4 k=5,記 表示第k年到第五年末的最高

7、總產(chǎn)量,k5時,這說明第5年初要把全部完好機(jī)器投入高負(fù)荷下生產(chǎn),k4時,k3時,k2時,k1時,由此知五年最高總產(chǎn)量為23700,再由上遞推知,高負(fù)荷生產(chǎn)的完好機(jī)器的最優(yōu)組合簡記,這表明在前兩年年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年年初全部完好機(jī)器投入高負(fù)荷生產(chǎn),第五年末的完好機(jī)器數(shù)為,0.7397278臺,在此例中，我們僅考慮最高產(chǎn)量，而未考慮五年計劃后的完好機(jī)器數(shù),問題1：若計劃為n個年度，怎樣決策,問題2：若要求在第5年末完好的機(jī)器數(shù)為500臺，如何決策使5年總產(chǎn)量最高,這類問題稱為固定終端問題,由上討論知,狀態(tài)轉(zhuǎn)移方程仍為,表示第k年初開始到第5年末的最高產(chǎn)量，稱為最優(yōu)值函數(shù)，其遞推關(guān)系為,k=1,2,3,4,5,其中 為第k段的效益值，即第k年的產(chǎn)量,表示第6年的產(chǎn)量不計算在總產(chǎn)量之內(nèi)，故為零,由假設(shè),又根據(jù)(1)得,一般地，當(dāng) 確定后，選擇 來確定 ，現(xiàn)在 已經(jīng)給定，故 已經(jīng)沒有選擇余地，它由 和 確定,于是,由(2)可知,最優(yōu)值,最優(yōu)值,類似地得到,這是五年最高產(chǎn)量,這表明，如果限定五