動態(tài)規(guī)劃匯總課件

*動態(tài)規(guī)劃DP一、概述二、DP的基本原理(最優(yōu)化原理)與方法三、DP基本概念及方程四、動態(tài)規(guī)劃的數(shù)學(xué)模型和求解方法*動態(tài)規(guī)劃DP一、概述*動態(tài)規(guī)劃DP一、概述(一)什么是DPDP:解決多階段決策的一種方法多階段決策過程:根據(jù)問題的空間或時間特性將過程分為若干階段,而在每一階段中都需作出決策,并且一個階段的決策將影響下階段的狀態(tài)。所有階段決策構(gòu)成一個決策序列，稱為策略，每個策略對應(yīng)一個效果。所選擇的策略應(yīng)使整個過程獲得最優(yōu)效果。DP是按照上述思路尋求問題最優(yōu)解的工具。*動態(tài)規(guī)劃DP一、概述*

動態(tài)系統(tǒng):當(dāng)所解決多階段決策過程優(yōu)化問題處于一個含時間變量或與時間變量有關(guān)的系統(tǒng)中,且系統(tǒng)現(xiàn)在的狀態(tài)與過去與未來的狀態(tài)有關(guān)時,這個系統(tǒng)稱為動態(tài)系統(tǒng).

如以灌溉或發(fā)電為主要目標(biāo)的水庫調(diào)度問題就是一個多階段決策過程。一年可以按時間分成若干階段。每個階段，以水庫蓄水量或水位為狀態(tài)變量，以放水量為決策變量，把灌溉效益或發(fā)電量最大為目標(biāo)函數(shù)。在滿足約束條件下確定各時段放水量，即組成一個決策序列。如果所選定的各時段放水量能使全年灌溉或發(fā)電效益最大，這就是一個最優(yōu)策略，即最優(yōu)調(diào)度方案。由于各階段決策與時間進(jìn)程有關(guān)，故為DP。*動態(tài)系統(tǒng):當(dāng)所解決多階段決策過程優(yōu)化問題處于一個含*(二)DP適用范圍DP不僅能解決與時間有關(guān)的優(yōu)化問題，而且也能解決與時間無關(guān)的靜態(tài)問題。例如，資源分配、投資分配、最優(yōu)線路、結(jié)構(gòu)優(yōu)化問題等。只要能把問題分成多個階段或步驟進(jìn)行決策，就可用DP尋求最優(yōu)解。廣義:工農(nóng)業(yè)生產(chǎn),資源開發(fā)管理,經(jīng)濟(jì)社會,環(huán)境水利等系統(tǒng)狹義:①變量連續(xù)或離散,可微或不可微.②LP,NLP③變量是確定性或隨機(jī)性④單變量或多變量(三)DP優(yōu)缺點優(yōu):①可以把一個n維優(yōu)化問題變?yōu)閚個一維問題求解②能找出全局最優(yōu)③適用難度較大的復(fù)雜問題④簡單易懂缺:①存在”維數(shù)災(zāi)”②計算程序通用性差.

*(二)DP適用范圍*二、DP的基本原理(最優(yōu)化原理)與方法基本原理:一個決策過程的最優(yōu)策略具備這樣的性質(zhì),即形成的狀態(tài)并作為初始狀態(tài)的過程而言,余下的諸決策必須構(gòu)成最優(yōu)策略.12tt+1n-1n最優(yōu)余留期例:AB1B2C1C2D1D2E456645132443(14,B2)(9,C1)(6,D1)(3,E)(11,C1)(5,D1)(4,E)①窮舉法:2×2×2=8條路徑,最優(yōu)策略:AB2C1D1E,min為14②標(biāo)號法*二、DP的基本原理(最優(yōu)化原理)與方法12t*③公式法di(·)—第i階段的費用Fi(·)—i~n階段的總最小費用i=4D→Ef4(D1)=4f4(D2)=3i=3

f3(C1)=min[d3(C1,D1)+f4(D1),d3(C1,D2)+f4(D2)]=min[1+4,3+3]=5(C1,D1,E)f3(C2)=min[d3(C2,D1)+f4(D1),d3(C2,D2)+f4(D2)]=min[2+4,4+3]=6(C2,D1,E)i=2f2(B1)=min[d2(B1,C1)+f3(C1),d2(B1,C2)+f3(C2)]=min[6+5,6+6]=11(B1,C1,D1E)f2(B2)=min[d2(B2,C1)+f3(C1),d2(B2,C2)+f3(C2)]=min[4+5,5+6]=9(B2,C1,D1E)i=1f1(A)=min[d1(A,B1)+f2(B1),d1(A,B2)+f2(B2)]=min[4+11,5+9]=14(A,B2,C1,D1E)最優(yōu)路線AB2C1D1E*③公式法*三、DP基本概念及方程(一)概念1.多階段決策過程是把整個過程按時間或空間分成若干階段,各階段首尾相連,但不重復(fù),閉合.2.多階段過程具有性質(zhì):當(dāng)前階段以前的各階段的決策和狀態(tài),對后面各階段的決策,相當(dāng)于一個初始條件,并不影響后面過程的最優(yōu)策略.3.DP對多階段最優(yōu)決策過程是一個有效方法,可大大減少計算工作量.4.DP法豐富了計算結(jié)果.5.DP一般采用”逆序決策過程”*三、DP基本概念及方程*(二)DP的要素意義1.階段:指研究對象在發(fā)展中所處的時段或空間中所處的部位,常用階段變量k描述.2.狀態(tài):系統(tǒng)在某階段中,過程演變的各種可能發(fā)生情況或所處狀態(tài).Sk為第k階段的狀態(tài)變量。如上例S2={B1,B2}

狀態(tài)無后效性：過程的過去歷史只通過面臨階段的狀態(tài)去影響未來的發(fā)展，而與未來過程無直接聯(lián)系。*(二)DP的要素意義*3.決策:某階段給定,從該階段狀態(tài)演變到下一階段某狀態(tài)應(yīng)做的決定(選擇),描述決策的變量稱決策變量。Uk(sk)為第k階段狀態(tài)處于變量Sk時的決策變量，是Sk的函數(shù)。U2(B1)=c14.策略:第k階段開始到終止?fàn)顟B(tài)為止的過程，每段決策按順序排列組成的決策函數(shù)序列{Uk(sk),Uk+1(sk+1)…,Un(sn)}記為Pk,n(Sk)*3.決策:某階段給定,從該階段狀態(tài)演變到下一階段某狀態(tài)應(yīng)做*5.狀態(tài)轉(zhuǎn)移方程:由一個狀態(tài)到另一個狀態(tài)的演變過程。SK+1=TK(Sk,uk)

狀態(tài)轉(zhuǎn)移規(guī)律，狀態(tài)轉(zhuǎn)移方程

TK狀態(tài)轉(zhuǎn)移函數(shù)。上例SK+1=Uk(sk)，Vt+1=Vt+Qt-qt6.指標(biāo)函數(shù)和最優(yōu)值函數(shù):指標(biāo)函數(shù):各階段效益vk總和

Vk,n=Vk,n(SK,uk,Sk+1,uk+1,…Sn+1),k=1,2,…nVk,n應(yīng)具有可分離性,并滿足遞推關(guān)系:

Vk,n(Sk,uk,Sk+1,uk+1,…Sn+1)=Vk(Sk,uk)+VK+1,n(SK+1,uk+1…Sn+1)]最優(yōu)值函數(shù):指標(biāo)函數(shù)的最優(yōu)值，記為fk(sk).表示從第k階段的狀態(tài)SK開始到第n階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略得到的指標(biāo)函數(shù)值。

fk(sk)=optVk,n(SK,uk,Sk+1,…Sn+1)

*5.狀態(tài)轉(zhuǎn)移方程:由一個狀態(tài)到另一個狀態(tài)的演變過程。SK+*綜上，多階段決策過程具有如下性質(zhì)：（1）在多階段決策過程中，任一階段都是以若干狀態(tài)來表征，其中任一狀態(tài)的變化，都將使該階段決策發(fā)生變化。（2）在每一階段，都可對每個狀態(tài)選擇一種決策，決策的結(jié)果就是狀態(tài)的轉(zhuǎn)移。（3）階段n+1的狀態(tài)sn+1是由階段的狀態(tài)和決策所決定，而與以前的各階段狀態(tài)無關(guān)。這表明，多階段決策過程存在著馬爾可夫單鏈性質(zhì)，這是無后效性的重要特性。（4）過程的決策序列可能有多個，但只有使目標(biāo)函數(shù)獲得最優(yōu)值的策略才是要選擇的最優(yōu)策略。*綜上，多階段決策過程具有如下性質(zhì)：*

設(shè)多階段決策過程如下圖，階段變量、狀態(tài)變量、決策變量分別用k、s和u表示。系統(tǒng)的實際運動方向為1----n，階段的編碼次序與實際運動方向一致，即1----N，遞推計算時采用的系統(tǒng)狀態(tài)轉(zhuǎn)移方向也與實際運動方向一致sn---sn+1（三）DP的基本方程(遞推方程)*設(shè)多階段決策過程如下圖，階段變量、狀態(tài)變量、決策變量*2….kk+1….nn+1123…N-1N時刻階段Vk(sk,uk)Fk+1(sk+1)Fk(sk)狀態(tài)s1s2….sk

…..

snsn+1uk系統(tǒng)實際運動方向逆序遞推*2….k*根據(jù)Bellman最優(yōu)原理:Vk,n=Vk(sk,uk)+VK+1,,n[sk+1,…,sn+1]，若用pk,n(sk)表示k~n階段的策略,則:Vk,n(sk,pk,n)=vk(sk,uk)+Vk+1[sk+1,pk+1,n]

當(dāng)最優(yōu)策略記為p*k,n(sk)，則最優(yōu)函數(shù)值fk(sk)DP遞推方程為:**上式的推導(dǎo)中，階段變量按順序編碼，且階段號碼與階段初編號一致，系統(tǒng)狀態(tài)轉(zhuǎn)移方向也與實際運動方向一致，而遞推計算次序與實際運動方向相反，即由系統(tǒng)實際的終端向始端遞推，故稱這種計算為逆序遞推，又稱向后計算法。許多問題可以令系統(tǒng)狀態(tài)轉(zhuǎn)移方向與系統(tǒng)實際運動方向相反，系統(tǒng)實際的始端變?yōu)橛嬎阌玫慕K端，遞推計算要從這個終端開始，這樣遞推計算次序與實際運行方向一致，稱這順序遞推，又叫向前計算法。下圖為順序遞推示意圖。設(shè)階段變量按順序編碼，且階段號碼與階段末編號一致，用上述同樣方法可推導(dǎo)出順序遞推的遞推方程。*上式的推導(dǎo)中，階段變量按順序編碼，且階段號碼與階段初編號一*01….K-1k….N-1N12k…N-1N時刻階段Vk(sk,uk)Fk-1(sk-1)Fk(sk)狀態(tài)s0s1….sk

…..

Sn-1snuk系統(tǒng)實際運動方向順序遞推*01….K-1*

由最優(yōu)化原理和遞推方程可以看出DP具有如下基本性質(zhì)：(1)DP的基本內(nèi)容，實際上是把原問題分成許多相互聯(lián)系的子問題，而每個子問題是一個比原問題簡單得多的優(yōu)化問題，且在每一個子問題的求解中，均利用它的一個后部子問題（余留過程）的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個子問題所得的最優(yōu)解，即為原問題的最優(yōu)解。DP就是將一個決策序列問題轉(zhuǎn)化為多個階段求單階段決策問題；每一個單階段決策問題可看成原問題的一個子問題?，F(xiàn)以一個簡單情況為例說明，如果原問題劃分為N個階段，并且每個階段只有一個決策變量，則DP就將一個N維決策的原問題轉(zhuǎn)化成只有一維決策的N個子問題。*由最優(yōu)化原理和遞推方程可以看出DP具有如下基本性*(2)從遞推方程中看出，在任一階段n選用一個決策后，它有兩方面的影響：其一，它直接影響面臨階段的費用；其二，它也影響其后子過程的初始狀態(tài)，因而影響到后邊各階段的最小總費用。全過程最優(yōu)策略的選擇是根據(jù)兩者統(tǒng)一考慮的結(jié)果確定的。所以，在多階段決策過程中，DP是既把面臨階段與未來階段分開，又把當(dāng)前費用和未來費用結(jié)合起來考慮的一種最優(yōu)化方法。*(2)從遞推方程中看出，在任一階段n選用一個決策后，它有兩*(3)由于用DP求解問題只需考慮相鄰兩個階段，就使得DP的計算量遠(yuǎn)遠(yuǎn)小于枚舉法的計算量。對于一個N階段問題，如果始端狀態(tài)只有一個，其他各階段狀態(tài)點數(shù)有T個，每個狀態(tài)下有T個決策，則枚舉法需計算TN個方案，而DP只需計算T+(N-1)T2個方案。(4)對系統(tǒng)方程、目標(biāo)函數(shù)、約束條件的函數(shù)性質(zhì)無嚴(yán)格要求，線性、非線性均可，甚至用表格表示某些變量之間關(guān)系，都可用DP求解，它也不要求決策空間為凸的，故DP是一種相當(dāng)靈活的方法。*(3)由于用DP求解問題只需考慮相鄰兩個階段，就使得DP的*（四）動態(tài)規(guī)劃的數(shù)學(xué)模型和求解方法1、DP的數(shù)學(xué)模型

DP的數(shù)學(xué)模型一般由系統(tǒng)方程、目標(biāo)函數(shù)、約束條件的邊界條件等幾部分組成。在建立模型時，首先將研究的問題根據(jù)其時間或空間特點劃分階段，形成多階段決策過程，并相應(yīng)地選取階段變量、狀態(tài)變量和決策變量。*（四）動態(tài)規(guī)劃的數(shù)學(xué)模型和求解方法1、DP的數(shù)學(xué)模型*（一）系統(tǒng)方程系統(tǒng)方程即上面所說的狀態(tài)轉(zhuǎn)移方程，它是包括階段變量、狀態(tài)變量和決策變量三種變量的一組關(guān)系式。對于具有一個狀態(tài)變量、一個決策變量的一維多階段決策過程，系統(tǒng)方程可寫成

n=1,2,…,N

式中，——階段n的狀態(tài)變量；

——階段n的決策變量；

——狀態(tài)轉(zhuǎn)移函數(shù)。

*（一）系統(tǒng)方程*

例如，例5—1中的系統(tǒng)方程為單一水庫優(yōu)化調(diào)度問題的系統(tǒng)方程為式中，——n時段和n+1時段初水庫蓄水量；

——n時段內(nèi)水庫來水量、放水量和蒸發(fā)滲漏損失量。對于具有m維狀態(tài)向量、q維決策向量的系統(tǒng)方程可寫成*例如，例5—1中的系統(tǒng)方程為*

﹕*﹕*

這可以4個水庫聯(lián)合運行為例加以說明。4個水庫具有4個狀態(tài)變量，故為四維（m=4）問題。由于每一個水庫時段末的狀態(tài)不僅和它自己時段初的狀態(tài)、本時段的決策有關(guān)，而且和所有其他3個水庫時段初狀態(tài)的本時段決策有關(guān)。（二）目標(biāo)函數(shù)

DP和其他數(shù)學(xué)規(guī)劃方法一樣，其數(shù)學(xué)模型同樣要包括目標(biāo)函數(shù)。目標(biāo)函數(shù)的最優(yōu)準(zhǔn)則可以是效益最大化，也可以是費用最小化或其他指標(biāo)。目標(biāo)函數(shù)值決定于系統(tǒng)中的狀態(tài)變量和決策變量，設(shè)以F表示目標(biāo)函數(shù)，**

則

式中，L——每一階段的費用（或效益）；

F——系統(tǒng)總費用（或總效益）。若為最小化目標(biāo)函數(shù)，則寫作

**（三）約束條件對狀態(tài)變量和決策變量的約束可以根據(jù)實際限制條件給出。第n階段的狀態(tài)向量的約束于集合，記為

(5-22)

式中，——第n階段的可行狀態(tài)集合。在第n階段狀態(tài)時所采用的決策向量約束于集合，記為

(5-23)

式中，——在第n階段狀態(tài)的可行決策集合。*（三）約束條件*（四）邊界條件指初始條件

或終末狀態(tài)

式中，——已知常數(shù)。凡問題的初始狀態(tài)已知，則稱為初值問題；而終末狀態(tài)已知的問題則稱終值問題；如初始和終末狀態(tài)均已知，則稱邊值問題。

DP就是要在系統(tǒng)方程、約束條件、邊界條件約束下，尋求目標(biāo)函數(shù)最優(yōu)值和相應(yīng)的最優(yōu)決策序列。*（四）邊界條件*2DP的求解方法求解DP數(shù)學(xué)模型，主要是反復(fù)使用遞推方程進(jìn)行擇優(yōu)計算，并由給定的初始狀態(tài)開始反演，以確定最優(yōu)策略。若實際問題中的階段變量、狀態(tài)變量和決策變量是離散的，就按原離散值計算；若這些變量是連續(xù)的，則可在其可行域內(nèi)離散為有限個數(shù)值。設(shè)階段變量離散為；任一階段的狀態(tài)離散為個點，記為,;狀態(tài)上的決策離散為個值，記為,。*2DP的求解方法*（一）由最后階段開始逐階段進(jìn)行遞推計算在每個階段，對每一個離散狀態(tài),都要使用所有的可行決策。對任何一個指定的離散狀態(tài)，都須進(jìn)行下列工作，以便選定最優(yōu)決策。

1.由給定的和，求得相應(yīng)的。

2.由該和,用系統(tǒng)方程計算，并求出由該狀態(tài)開始的余留過程的最小總費用。*（一）由最后階段開始逐階段進(jìn)行遞推計算*

應(yīng)當(dāng)指出，若在給定的離散狀態(tài)點上，則可以由階段計算結(jié)果直接查到；若不在離散狀態(tài)點上，則須進(jìn)行內(nèi)插。

3.由遞推方程計算使用時的余留過程總費用，。當(dāng)個決策都使用之后，將所有的進(jìn)行比較，取其中最小者為該指定狀態(tài)開始的余留過程的最小總費用，其相應(yīng)的為最優(yōu)決策。

*應(yīng)當(dāng)指出，若在給定的離散狀態(tài)點上，則*

將記入計算機(jī)內(nèi)存，供階段計算使用；同時存貯，供決策反演時使用。至此，便結(jié)束這個離散化狀態(tài)的計算。一個指定的算完后，接著依次進(jìn)行其他離散狀態(tài)點的計算。所有的都算完之后，階段計算結(jié)束，隨即轉(zhuǎn)入階段計算。**（二）由即定的初始狀態(tài)開始進(jìn)行決策反演，追尋最優(yōu)策略

當(dāng)遞推計算至第1階段后，由給定的初始狀態(tài)開始，按系統(tǒng)方程和各狀態(tài)下的最優(yōu)決策進(jìn)行反演，直到最后階段，從而得到最優(yōu)策略、最優(yōu)軌跡和相應(yīng)的最優(yōu)目標(biāo)函數(shù)值。若初始狀態(tài)非唯一，則將推算的幾個不同的初始狀態(tài)的最小總費用進(jìn)行比較，取其中最小者為最優(yōu)目標(biāo)函數(shù)值；并由它對應(yīng)的初始狀態(tài)開始反演求得最優(yōu)策略和最優(yōu)軌跡。一般講來，當(dāng)初始狀態(tài)已知時，逆序遞推較方便；當(dāng)終末狀已知時，順序遞推較方便*（二）由即定的初始狀態(tài)開始進(jìn)行決策反演，追尋最優(yōu)策略*

開始

輸入資料階段計算；并放入內(nèi)存狀態(tài)決策由系統(tǒng)方程計算下一階段狀態(tài)計算由階段優(yōu)化結(jié)果求得存貯和由初始狀態(tài)開始反演，追蹤最優(yōu)策略輸入最優(yōu)解

結(jié)束

*開始輸入資料階段計算*DP和靜態(tài)規(guī)劃的關(guān)系及DP求解方法一,關(guān)系一般對LP,NLP問題可人為引入”時間”因素,用DP求狀態(tài)轉(zhuǎn)移方程:Sk+1=Tk(Sk,xk)V1n=v1(S1,x1)*v2(S2,x2)*…vn(Sn,xn)*表示”+”或”ⅹ”DP方法

LP靜態(tài)數(shù)學(xué)規(guī)劃NLP靜態(tài)

DP與時間有關(guān),多階段階段數(shù)n固定:公式法,列表法,標(biāo)號法階段數(shù)n不固定:函數(shù)迭代法,策略迭代法*DP和靜態(tài)規(guī)劃的關(guān)系及DP求解方法一,關(guān)系*例:Maxz=x1.x22.x3x1+x2+x3=c(c>0)xi≥0,i=1,2,3解:按變量個數(shù)劃分為三個階段i=1,2,3設(shè)狀態(tài)變量為:sk(S1,S2,S3,S4)，代表第k個變量及以后變量之和，記S1=C，S4=0決策:x1,x2,x3狀態(tài)轉(zhuǎn)移:Sk+1=Sk-Xk,S4=S3-X3=0,∴S3=X3S3=S2-x2,,S2=S1-x1S1=C階段效益:v1=x1v2=x22v3=x3F4(S4)=1*例:Maxz=x1.x22.x3F4(S4)=1*決策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3遞推:*決策域:0≤x1≤S1=C,0≤x2≤S2,x3=S3*例:MaxZ=x1·x22·x3x1+x2+x3=C(C>0)xi≥0,i=1,2,3*例:MaxZ=x1·x22·x3*****例:MaxF=4x12-x22+2x32+123x1+2x2+x3≤9xi≥0,i=1,2,3解:分三個階段,設(shè)狀態(tài)變量S0,S1,S2,S3≤9

決策變量:x1,x2,x3順推解法:設(shè)S0=0,3x1=S1,S1+2x2=S2,S2+x3=S3≤9則:0≤x1≤1/3S1,0≤x2≤1/2S2,0≤x3≤S3階段效益:v1=4x12

v2=-x22v3=2x32+12F0(S0)=0*例:MaxF=4x12-x22+2x32+12F0(*****2.列表法思路:首先把各階段的狀態(tài)變量Sk按計算精度ΔS離散為0,ΔS,2ΔS,…(m-1)ΔS,S0共有m+1個分點.先后用表格型式在離散點上求解遞推方程,得最優(yōu)策略.例:MaxF=x1+(x2-3)2+(4-x3)3

x1+x2+x3≤8xi≥0,i=1,2,3ε=1(精度)解:分三個階段,設(shè)S0=0,狀態(tài)空間為8是連續(xù)的

S1=S0+x1,S2=S1+x2,S3=S2+x3Sk=Tk(Sk-1,xk)階段效益:v1=x1

v2=(x2-3)2v3=(4-x3)3把各Sk按ΔS=1離散順推計算:

*2.列表法*第一階段:設(shè)S1=x1F1(S1)=Max{v1(S1,x1)}=Max{x1}第二階段:S2=S1+x2

S2={0…8}f2(S2)=Max{v2(S2,x2)+f1(S1)}S1

012345678f1(S1)

012345678X1*012345678

*第一階段:設(shè)S1=x1S1*41014916250123456784101491625521251017632361176347854596510711

s1f2x2v2f10012345678*4101*f2(S2)s2v3x3f327810182764012345678361710910173673371811101118373819121112193920131213402114134122154223438901234567258

*f2(S2)s2v3x3f3278*把各階段最優(yōu)值匯總:Sf1x1f2x2f3x30009073011100740221107503312076044130770551407806615079077167或080088258890*把各階段最優(yōu)值匯總:Sf1*S2=S3-x3,S1=S2-x2當(dāng)S0=8時，x1*=0,x2*=8,x3*=0,F=89當(dāng)S0=7時,x1*=0,或7,x2*=7或0,x3*=0F=80當(dāng)S0=6時,x1*=6x2*=0x3*=0F=79F(0,7,0)=x1+(x2-3)2+(4-x3)2=80F(7,0,0)=80結(jié)論：1）當(dāng)問題的變量是離散時，所求解是精確的

2）當(dāng)變量是連續(xù)的，可安精度要求得近似最優(yōu)解。

3）DP離散方法，不用求導(dǎo)，計算簡便，易于編程。*S2=S3-x3,S1=S2-x2*7.4二維及多維DPn維DP：狀態(tài)變量n個，決策變量n個例：兩個水庫可供總水量分別為Z，Y聯(lián)合向n個用水戶供水，第i個用戶從Z，Y取水xi,yi,得收益ri(xi,yi)求水資源系統(tǒng)最優(yōu)分配方案？解：設(shè)水庫A，B可用水量離散，用狀態(tài)變量qi,Qi表示，則有DP遞推方程：狀態(tài)轉(zhuǎn)移方程：qi+1=qi-xi0≤xi≤qi≤ZQi+1=QI-yi0≤yi≤Qi≤Y可用DP格點法求解

*7.4二維及多維DP*7.5隨機(jī)DP簡介1.分類：①各階段是相互獨立的，且有各自的概率分布②各階段是有相關(guān)關(guān)系的，如存在馬爾柯夫2.（MarkovChain）關(guān)系獨立（有預(yù)報）相關(guān)（無預(yù)報）例：某室外工程，施