【正文】 階段特性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐譃闈M足遞推關(guān)系的若干階段，對(duì)非時(shí)序的靜態(tài)問(wèn)題要人為地賦予“時(shí)段”概念。 ???????????)3,2,1(010..294m a x3212321ixxxxtsxxxzi（一）動(dòng)態(tài)規(guī)劃模型的建立 ??????2212 5xuss 例 5 某公司有資金 10萬(wàn)元．若投資于項(xiàng)目 i(i＝ 1， 2， 3＞的投資額為xi時(shí)，其收益分別為 g1(x1)＝ 4x1， g2(x2)＝ 9x2， g3(x3)＝ 2x32，問(wèn)應(yīng)如何分配投資數(shù)額才能使總收益最大 ? K=1 K=2 第 k段時(shí) 所以，建立動(dòng)態(tài)規(guī)劃模型： 階段 k：本例中取 1， 2， 3 狀態(tài)變量 sk：第 k段可以投資于第 k項(xiàng)到第 3個(gè)項(xiàng)目的資金數(shù) 決策變量 xk：決定給第 k個(gè)項(xiàng)目投資的資金數(shù)。 也可以人為地賦予時(shí)段概念，把問(wèn)題轉(zhuǎn)化為一個(gè) 3段決策過(guò)程。資源分配問(wèn)題是動(dòng)態(tài)規(guī)劃的典型應(yīng)用之一，資源可以是資金、原材料、設(shè)備、勞力等，資源分配就是將一定數(shù)量的一種或幾種資源恰當(dāng)?shù)胤峙浣o若干使用者，以獲取最大效益。 0)(1,...,1,)](),([)(1111)(??????????nnkkkkksDukksfnnksfusvoptsfkkk三、動(dòng)態(tài)規(guī)劃模型的建立與求解 （一）動(dòng)態(tài)規(guī)劃模型的建立 （二）逆序解法與順序解法 （三）基本方程分段求解時(shí)的幾種常用算法 （一）動(dòng)態(tài)規(guī)劃模型的建立 建立動(dòng)態(tài)規(guī)劃的模型關(guān)鍵，在于識(shí)別問(wèn)題的多階段持征，將問(wèn)題分解成為可用 遞推關(guān)系式 聯(lián)系起來(lái)的若干子問(wèn)題，或者說(shuō)正確地建立具體問(wèn)題的基本方程。 (3)動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。 (2)求解時(shí)從邊界條件開(kāi)始，逆 (或順 )過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。 其次，動(dòng)態(tài)規(guī)劃的計(jì)算結(jié)果不僅得到了從起始點(diǎn)到最終點(diǎn)的最短路線，而且得到了中間段任一點(diǎn)到最終點(diǎn)的最短路線 。 這種在圖上直接計(jì)算的方法稱為標(biāo)號(hào)法。 動(dòng)態(tài)規(guī)劃的基本思想 第一步： k=5 狀態(tài) s5： E1， E2 (4) (3) f5(E1)＝ 4 f5(E2)＝ 3 第二步： k=4 狀態(tài)： D1 D2 D3 u4*(D1)=E1 u4*(D2)=E2 u4*(D3)=E1 (4) (3) (7) (5) (5) (4) (3) (5) (5) (7) 第三步： k=3 狀態(tài)： C1 C2 C3 C4 u3*(C1)=D1 u3*(C2)=D2 u3*(C3)=D2 f3(C1)＝ 12 f3(C2)＝ 10 f3(C3)＝ 8 u3*(C4)=D3 f3(C4)＝ 9 (12) (10) (8) (9) (4) (3) (7) (5) (5) (12) (10) (8) (9) 第四步： k=2 狀態(tài)： B1 B2 u2*(B1)=C2 u2*(B2)=C3 f2(B1)＝ 13 f2(B2)＝ 15 (13) (15) (4) (3) (7) (5) (5) (12) (10) (8) (9) (13) (15) 第五步： k=1 狀態(tài)： A u1*(A)=B1 f1(A)＝ 17 (17) 即從 A到 F的最短距離為 17。共有多少條路徑，依次計(jì)算并比較。 最優(yōu)指標(biāo)函數(shù)記為 fk(sk)表示從第 k段狀態(tài) sk采用最優(yōu)策略到過(guò)程終止時(shí)的最佳效益值。 V1,n(s1,p1,n) 表示初始狀態(tài)為 s1采用策略 p1,n時(shí)原過(guò)程的指標(biāo)函數(shù)值 。 階段指標(biāo)函數(shù) 是指第 k段，從狀態(tài) sk出發(fā)，采取決策 uk時(shí)的效益，用 d(sk,uk)表示。 第 k段的狀態(tài) sk，本階段決策為 uk(sk)，則第 k+1段的狀態(tài) sk+1也就完全確定，它們的關(guān)系可用公式表示： sk+1=Tk(sk,uk) sk+1= uk(sk) 指標(biāo)函數(shù)： 用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。 對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定范圍，稱為允許策略集合，記作 P1,n，使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。 允許決策集合： 決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合。 一階段： S1＝ {A} 二階段： S2＝ {B1,B2,B3} 三階段： S3＝ {C1,C2,C3} 四階段： S4＝ {D1,D2} 決策： 當(dāng)各段的狀態(tài)取定以后，就可以作出不同的決策（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。 動(dòng)態(tài)規(guī)劃中的狀態(tài)應(yīng)具有如下性質(zhì) ：當(dāng)某階段狀態(tài)給定以后，在這階段以后過(guò)程的發(fā)展不受這段以前各段狀態(tài)的影響。 狀態(tài)： 各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)。(4)狀態(tài)轉(zhuǎn)移 。(2)狀態(tài) 。 A B1 B2 B3 C1 C2 C3 D1 D2 E 3 6 7 7 6 9 5 2 3 8 3 5 4 3 6 9 4 3 二、動(dòng)態(tài)規(guī)劃的基本概念和基本原理 階段： 將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母 k表示階段變量。因此可以把整個(gè)路程分為 A， B(包括 B1， B2， B3)， C(包括 C1，C2， C3)和 D(包括 Dl， D2)四個(gè)階段。 解： 在問(wèn)題中，從 A到 B1， B2， B3中的哪一個(gè)點(diǎn)要作出一項(xiàng)決策，從 B1， B2，B3中的某點(diǎn)到 C1， C2， C3中的哪一個(gè)點(diǎn)又要作出一項(xiàng)決策等。 幾個(gè)例子 例 (最短路程問(wèn)題 )假定從 A地到 E地要鋪設(shè)一條管道，其中要經(jīng)過(guò)若干個(gè)中間點(diǎn) (如圖 )。同時(shí)，各種貨物的總重量不能超過(guò) 10噸。 假定這艘貨船的總載重量是 10噸，現(xiàn)在要確定這四種貨物應(yīng)各裝幾箱才能使裝載貨物的總價(jià)值達(dá)到最大。 幾個(gè)例子 例 (貨船裝運(yùn)問(wèn)題 )有四種貨物準(zhǔn)備裝到一艘貨船上。同時(shí)，這三個(gè)廠的總投資不能超過(guò) 7萬(wàn)元。各個(gè)廠的投資方案及擴(kuò)建后預(yù)期可獲得的利潤(rùn)如表所示 (單位：萬(wàn)元 )。 幾個(gè)例子 幾個(gè)例子 例 (基建投資問(wèn)題 )一家公司有三個(gè)工廠，每個(gè)廠都需要進(jìn)行擴(kuò)建。 例 3 設(shè)備更新問(wèn)題 企業(yè)在使用設(shè)備時(shí)都要考慮設(shè)備的更新問(wèn)題，因?yàn)樵O(shè)備越陳舊所需的維修費(fèi)用越多，但購(gòu)買(mǎi)新設(shè)備則要一次性支出較大的費(fèi)用；現(xiàn)某企業(yè)要決定一臺(tái)設(shè)備未來(lái) 8年的更新計(jì)劃，已預(yù)測(cè)了第 j年購(gòu)買(mǎi)設(shè)備的價(jià)格為 Kj，設(shè) Gj為設(shè)備經(jīng)過(guò) j年后的殘值，Cj為設(shè)備連續(xù)使用 j1年后在第 j年的維修費(fèi) (j＝ 1， 2， … ， 8)，問(wèn)應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最小。 例 2 投資決策問(wèn)題 某公司現(xiàn)有資金 Q萬(wàn)元，在今后 5年內(nèi)考慮給 A， B， C， D 4個(gè)項(xiàng)目投資，這些項(xiàng)目投資的回收期限、回報(bào)率均不相同，問(wèn)該公司應(yīng)如何確定這些項(xiàng)目每年的投資額，使到第 5年末擁有資金的本利總額最大。要求確定一個(gè)逐月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最小。 例 1 生產(chǎn)與存貯問(wèn)題 某工廠每月需供應(yīng)市場(chǎng)一定數(shù)量的產(chǎn)品，并將所余產(chǎn)品存入倉(cāng)庫(kù)。 動(dòng)態(tài)的含義： 動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。 其中離散確定型是最基本的，本章主要針對(duì)這種類型的問(wèn)題，介紹動(dòng)態(tài)規(guī)劃的基本思想、原理和方法，這些對(duì)其它類型的問(wèn)題也適用。 按決策過(guò)程演變的性質(zhì)分為： ? 確定型動(dòng)態(tài)決策問(wèn)題。 動(dòng)態(tài)決策問(wèn)題分類： 按數(shù)據(jù)給出的形式分為： ? 離散型動(dòng)態(tài)決策問(wèn)題?？捎糜诮鉀Q最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃與庫(kù)存、投資、裝載、排序等問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。 動(dòng)態(tài)規(guī)劃 (.– Dynamic Program)： 動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。第七章 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)決策問(wèn)題： 決策過(guò)程具有階段性和時(shí)序性 (與時(shí)間有關(guān) )的決策問(wèn)題。即決策過(guò)程可劃分為明顯的階段。 廣泛應(yīng)用于工業(yè)技術(shù)、生產(chǎn)管理、企業(yè)管理、經(jīng)濟(jì)、軍事等領(lǐng)域。 動(dòng)態(tài)規(guī)劃 (.)的起源： 1951年 ,(美 )數(shù)學(xué)家 最優(yōu)化原理，從而建立動(dòng)態(tài)規(guī)劃，名著《 動(dòng)態(tài)規(guī)劃 》 于 1957年出版。 ? 連續(xù)型動(dòng)態(tài)決策問(wèn)題。 ? 隨機(jī)型動(dòng)態(tài)決策問(wèn)題。 第七章 動(dòng)態(tài)規(guī)劃 一、多階段決策過(guò)程的最優(yōu)化 二、基本概念和基本原理 三、動(dòng)態(tài)規(guī)劃模型的建立與求解 四、動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 一、多階段決策過(guò)程的最優(yōu)化 多階段決策過(guò)程： 多階段決策過(guò)程，本意是指這樣一類特殊的活動(dòng)過(guò)程，它們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，稱為“時(shí)段”，在每一個(gè)時(shí)段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題屬序貫決策問(wèn)題。 多階段決策過(guò)程最優(yōu)化的目標(biāo)： 達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)。一般某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉(cāng)庫(kù)會(huì)增加庫(kù)存費(fèi)用。 顯然，可以把每個(gè)月作為一個(gè)階段，全年分為 12個(gè)階段逐次決策。 這是一個(gè) 5階段決策問(wèn)題。 這是一個(gè) 8階段決策問(wèn)題，每年年初要作出決策，是繼續(xù)使用舊設(shè)備，還是購(gòu)買(mǎi)新設(shè)備。公司用于擴(kuò)建的資金總共為 7萬(wàn)元。 現(xiàn)在公司要確定時(shí)各廠投資多少才能使公司的總利潤(rùn)達(dá)到最大？ 解： 在這個(gè)問(wèn)題中