第八章動態規劃
動態規劃模型和求解方法
(1)階段．
(2)狀態．描述過程在第k階段狀態的變數，稱為狀態變數，用sk表示． sk取值的全體記作sk，稱作第k階段的狀態集合．
狀態的定義在動態規劃中往往是最重要的概念．它必須具備3個特性：
①描述性．各階段狀態的演變能描述決策過程．
②無後效性．如果第k階段的狀態給定，則在這階段以後過程的發展不受這階段以前各個階段狀態的影響．也就是說，過程未來的發展，只與過程的現在狀態有關，而與過程的過去狀態無關．
③可知性．各階段狀態變數的取值，直接或間接是可知的，也就是說，第k階段的狀態集合sk是給定的．
(3)決策．當第k階段的狀態sk給定後，從該狀態演變為第k+1階段狀態時所作的選擇稱為決策．
描述決策的變數稱為決策變數，用xk(sk)表示，簡記為xk．
xk(sk)取值的全體記為dk(sk)，稱為第k階段的決策集合，sk取值不同，相應的決策集合也可能不同．
(4)策略． 稱為策略．
(5)狀態轉移方程．第k+1階段的狀態sk+l與第k階段的狀態sk、決策xk之間有函式關係
sk+l =tk (sk，xk)，
並稱其為狀態轉移方程．
(6)權函式．在第k階段，當狀態取定sk、決策取定xk時，該階段所實現的效益指標(例如距離、時耗、利潤、成本等)稱為權函式，
(7)指標函式．若第k階段的狀態為sk，當採用了最優子策略後，從階段k到階段n可獲得的效益，稱為指標函式，記為fk (sk)．實現fk (sk) 值的xk記為x*k．
(8)遞迴方程．稱下列方程為遞迴方程：
fn+1 (sn+1) =0或1，
fk(sk)=，k=n，n一1，…，1．
其中，符號opt視問題性質可取面min或max，同時，當符號⊙取加法運算時，取fn+1 (sn+1) =0；當符號⊙取乘法運算時，取 fn+1 (sn+1) =1．
由於用遞迴方程和狀態轉移方程求解動態規劃的過程，是由第n階段向前遞迴至第1階段，故這種方法稱為逆序解法．
綜上所述，如果乙個問題能用動態規劃方法求解，那麼，我們可以按下列步驟建立動態規劃的數學模型：
①劃分階段，並正確地定義各階段狀態變數使之具有描述性、無後效性和可知性3個特性，同時確定狀態集合；
②定義決策變數，確定決策集合：
③確定權函式；
④建立狀態轉移方程；
⑤確定指標函式；
⑥建立遞迴方程．
由狀態轉移方程和遞迴方程，用逆序解法對動態規劃模型求解，在求得，f1(s1)和x*1後，則按順序追蹤方法尋找最優策略。
例8-2(投資問題)現有資金5百萬元，可對3個專案進行投資，投資額均為整數（單位為百萬元）．假設2# 專案的投資不得超過3百萬元，1#和3#專案的投資均不得超過4百萬元，3#專案至少要投資1百萬元．投資5年後每個專案預計可獲得的收益由下表給出。問如何投資可獲得最大的收益．
解：本問題是乙個靜態問題，但可以把它轉化成動態問題：將這個投資問題分成3個階段，在第k階段要對專案k#進行投資決策．令
sk——對k#，…，3#專案允許的投資額；
xk——對k#專案的投資額；
w(sk，xk)——對k#專案投資xk後的收益：
w(sk，xk)= wk（xk）；
tk (sk，xk)——sk+l= sk - xk；
fk(sk)——當第k至第3專案允許的投資額為sk時所能獲得的最大收益．
為了獲得最大收益，必須將5百萬元資金全部用於投資．故假想有第4階段存在時
必有s4= 0．對於本問題，有下列遞迴方程：
第一步 k=3
第二步 k=2
第三步 k=1
s1=5 s2=4 s3=2
x1*=1 x2*=2 x3*=2
f1(5)=21
（最優分配問題）有乙個儀表公司打算向它的3個營業區設立6家銷售店。每個營業區至少設一家，所獲利潤如表。問設立的6家銷售店數應如何分配，可使總利潤最大？
解：sk——對k#,…,3#營業區允許設立的銷售店數
xk——對k#營業區設立的銷售店數
wk (sk,xk)——對k#營業區設立xk銷售店後的利潤：wk (sk,,xk)= wk (xk)
tk (sk, xk)——sk +1= sk - xk
fk (sk)——當第k至第3個營業區允許設立的銷售店數為sk時所能獲得的最大利潤
遞迴方程：
f4(s4)=0
fk (sk)=max ｛wk (xk)+ fk+1(sk+1)｝, k=3,2,1
xk∈dk(sk)
第一步：k=3時，有方程
f4 (s4)=0
f3(s3)= max ｛w3(x3)+ f4(s4) ｝
x3∈d3(s3)
s3=s2—x2
第二步：k=2,有方程
f2(s2)= max ｛w2(x2)+ f3(s3) ｝
x2∈d2(s2)
s3=s2—x2
-第三步：k=1,有方程
f1(s1)= max ｛w1(x1)+ f2(s2) ｝
x1∈d1(s1)
s2=s1—x1
s1=6 → s2=3 → s3=2
x1*=3 x2*=1 x3*=2
分別a1、a2、a3營業區設立3家、1家、2家銷售店，最大利潤為770
例8-7(可靠性問題)某種儀表由3種不同的元件串聯而成，任乙個元件的故障將造成整台儀表的故障．每種元件又都有3種規格，設k#元件j#規格的可靠性為rkj，所需費用為ckj．生產每台儀表的費用限額e為10．試問如何選用各種元件的規格，使得儀表的可靠性最大?
我們把這個問題分成3個階段．在第k階段要確定k#元件的規格．
下面我們用逆序解法求解．
sk——儀表上配備k #，…， 3# 元件時允許使用的費用；
s3——儀表上配備 3# 元件時允許使用的費用；
s2——儀表上配備2 #, 3# 元件時允許使用的費用；
s1——儀表上配備1 #，2 #， 3# 元件時允許使用的費用；
xk——k#元件所選用的規格；
wk(sk，xk)——k#元件採用規格xk# 時的可靠性：
wk(sk，xk)=rkxk；
tk (sk，xk)——sk+l= sk - ckxk；
fk(sk)——在費用限額為sk的條件下，k #，…， 3#元件串聯時相應部分可獲得的最大可靠性．
遞迴方程為：
f4(s4)=1
fk(sk)=，
k=3，2，，1。
第一步，k=3，
將上表簡化：
第二步，k=2，f(s2)的計算過程如表所示．
2019數塔動態規劃
數塔time limit 1000ms memory limit 32768k total submit 116 accepted 60 description 在講述dp演算法的時候，乙個經典的例子就是數塔問題，它是這樣描述的 有如下所示的數塔，要求從頂層走到底層，若每一步只能走到相鄰的結點，則經...
動態規劃練習
任務 請寫乙個程式 在文字檔案tan.in中讀入路程的總長度 旅館的數目和對旅館的描述 找出兩個旅行的方案 乙個最便宜的方案 就是付出的宿費最少的方案 如果有多個方案，選擇在旅館中度夜的次數最少的方案 乙個最短的方案 就是在旅館中度夜的次數最少的方案 如果有多個方案，選擇花費最少的方案 把結果，就是...
動態規劃講稿
第四章動態規劃 第一節動態規劃原理 一 基本概念 1 引例 例4 1 最短路程問題。某地區需要由發電廠至使用者端架設一條高壓輸電線路，途中經過三個城鎮 每個城鎮又各需建設乙個變電站。城鎮和各有二個站址可供選擇，城鎮有三個站址可供選擇，相互間地理位置如圖4 1所示，圖中各線段旁資料表示該段路徑相對長度...