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

第八章動態(tài)規(guī)劃(Dynamicprogramming)動態(tài)規(guī)劃的基本思想最短路徑問題離散確定性問題的動態(tài)規(guī)劃解法一般數(shù)學(xué)規(guī)劃模型的動態(tài)規(guī)劃解法第八章動態(tài)規(guī)劃動態(tài)規(guī)劃的基本思想最短路徑問

動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。

需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；每個階段都要進(jìn)行決策,目的是使整個過程的決策達(dá)到最優(yōu)效果。動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進(jìn)行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：是動態(tài)決策問題的一種特殊形式；在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。

2.機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策多階段決策問題的典型例子：2.機(jī)器負(fù)荷分配問題：某種

這時，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終完好的機(jī)器就為au,0<a<1。

在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為

h=h(u2)

假定開始生產(chǎn)時完好的機(jī)器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。

相應(yīng)的機(jī)器年完好率b,0<b<1。

這時，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u2511214106104131112396581052C1C3D1AB1B3B2D2EC23、最短路徑問題:一個線路網(wǎng)絡(luò)圖，從A到E要修建一條石油管道，必須在B、C、D處設(shè)立加壓站。各邊上的數(shù)為長度，現(xiàn)需要找一條路使總長度最短求從A到E的最短路徑2511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B22511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C12511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D12511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E從A到E的最短路徑為19，路線為A→B2→C1→D1→E2511214106104131112396581052C1

（一）、基本概念1、階段：把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量。年、月、路段一個數(shù)、一組數(shù)、一個向量狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。一、動態(tài)規(guī)劃的基本思想（一）、基本概念2、狀態(tài)：表示每個階段開始所處的自然狀況或3、決策：表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過程可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；3、決策：表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變?nèi)绻麪顟B(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?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ù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，為指標(biāo)函數(shù)。指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。5、策略：是一個按順序排列的決策組成的集合。在實際問題中小結(jié):方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量k﹑狀態(tài)變量sk﹑決策變量uk;指標(biāo):

動態(tài)規(guī)劃本質(zhì)上是多階段決策過程;

效益指標(biāo)函數(shù)形式:

和、積無后效性可遞推小結(jié):方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量k﹑狀態(tài)變量sk解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列

最優(yōu)目標(biāo)函數(shù)值從k到終點最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值解多階段決策過程問題，求出最優(yōu)策略，即最優(yōu)決策序列1、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。（二）、動態(tài)規(guī)劃的基本思想（二）、動態(tài)規(guī)劃的基本思想2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來一段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.

最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個最優(yōu)策略的子策略也是最優(yōu)的。3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段（三）、建立動態(tài)規(guī)劃模型的步驟1、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。2、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。3、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。（三）、建立動態(tài)規(guī)劃模型的步驟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ù)具體問題具體分析，只有通過不斷實踐總結(jié)，才能較好掌握建模方法與技巧。4、確定狀態(tài)轉(zhuǎn)移方程以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型二離散確定性動態(tài)規(guī)劃模型的求解例：設(shè)國家撥給60萬元投資，供四個工廠擴(kuò)建使用，每個工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)。二離散確定性動態(tài)規(guī)劃模型的求解投資01按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進(jìn)行投資分配，以取得最大的總利潤。按順序解法計算。投資0最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)的值。最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求最優(yōu)策略為（30，20），此時最大利潤為105萬元。最優(yōu)策略為（30，20），此時最大利潤為105萬元。最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)＝0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。最優(yōu)策略為（10，0）或（0，10），此時最大利潤

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮第一、第二及第三個工廠如何進(jìn)行投資分配，以取得最大的總利潤。投資010203040最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)的值。得到下表最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可

投資利潤0102030405060f3(x)0256085110135155最優(yōu)策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四階段：求f4(60)。即問題的最優(yōu)策略。投資0102030405060f3(x)02560最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。三、一般數(shù)學(xué)規(guī)劃模型的動態(tài)規(guī)劃解法這里所說的一般數(shù)學(xué)規(guī)劃模型包括線性規(guī)劃、