第10章動態(tài)規(guī)劃課件

第十章動態(tài)規(guī)劃§4-1引言及內(nèi)容框架§4-2基本概念、模型與最優(yōu)化原理§4-3動態(tài)規(guī)劃的應(yīng)用1第十章動態(tài)規(guī)劃§4-1引言及內(nèi)容框架1§4-1引言■動態(tài)規(guī)劃的研究對象■動態(tài)規(guī)劃問題的特點■靜態(tài)決策問題的動態(tài)處理2§4-1引言■動態(tài)規(guī)劃的研究對象2一、動態(tài)規(guī)劃的研究對象

——多階段的決策問題1多階段決策問題動態(tài)決策——將時間作為變量的決策問題稱為動態(tài)決策。其基本特點是多次決策。多階段決策問題是一類特殊形式的動態(tài)決策問題。是指這樣一類活動過程：系統(tǒng)的動態(tài)動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系又相互區(qū)別的階段，而且每個階段都進行決策，當(dāng)每個階段決策確定以后，就完全確定了一個過程確定的線路。3一、動態(tài)規(guī)劃的研究對象

多階段決策問題的典型例子※企業(yè)生產(chǎn)過程中，由于需求是隨著時間變化的因素，因此企業(yè)為了獲得全年最佳經(jīng)濟效益，就要在整個過程中進行逐月和逐季的根據(jù)庫存和需求決定生產(chǎn)計劃。※某種機器，可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷下生產(chǎn)時的產(chǎn)量多，但每生產(chǎn)一個階段的機器完好率低；低負(fù)荷下生產(chǎn)時的情況則相反?，F(xiàn)在需要安排該種機器在多個階段內(nèi)的生產(chǎn)，問應(yīng)如何決定各個階段中機器的使用，使這個計劃期內(nèi)的總產(chǎn)量最大？4多階段決策問題的典型例子※企業(yè)生產(chǎn)過程中，由于需求是隨著時※某臺設(shè)備。例如汽車，剛買來時故障低，耗油少，出車時間長，處理價值和經(jīng)濟效益高；隨著使用時間的增加則變?yōu)楣收隙?、耗油高、維修費用增加，經(jīng)濟效益差，使用時間越長，處理價值越低。另外每次更新都要付出更新費用。因此應(yīng)如何決定設(shè)備的使用年限，使總的效益最佳？※化工生產(chǎn)過程包括一系列的過程設(shè)備，如反映器、蒸餾塔、吸收器等，前一設(shè)備的輸出是后一設(shè)備的輸入。因此，應(yīng)如何控制生產(chǎn)過程中各個設(shè)備的輸出和輸入，使總產(chǎn)量最大？5※某臺設(shè)備。例如汽車，剛買來時故障低，耗油少，出車時間長，處什么是動態(tài)規(guī)劃？DP是OR中的一個分支，是解決多階段決策過程最優(yōu)化的一種方法或是一種分析多階段決策過程的數(shù)學(xué)方法。這種方法可根據(jù)人們所采取的措施，一步步地控制過程的發(fā)展，來實現(xiàn)預(yù)定的要求。這一運籌學(xué)分支最初有美國數(shù)學(xué)家BELLMAN等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的最優(yōu)化原理，并研究了許多實際問題而建立起來的。6什么是動態(tài)規(guī)劃？DP是OR中的一個分支，是解決多階段決策過程動態(tài)規(guī)劃的特點優(yōu)點①許多問題用動態(tài)規(guī)劃研究求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問題，解析數(shù)學(xué)無用武之地。而動態(tài)規(guī)劃成為得力工具；②某些情況下，用動態(tài)規(guī)劃處理不僅能定性描述分析，且可利用計算機給出求其數(shù)值解的方法。二、動態(tài)規(guī)劃問題的特點7動態(tài)規(guī)劃的特點優(yōu)點二、動態(tài)規(guī)劃問題的特點7缺點①沒有統(tǒng)一的處理方法，求解時要根據(jù)問題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此實踐經(jīng)驗及創(chuàng)造性思維將起重要的引導(dǎo)作用；②“維數(shù)障礙”，當(dāng)變量個數(shù)太多時，由于計算機內(nèi)存和速度的限制導(dǎo)致問題無法解決。有些問題由于涉及的函數(shù)沒有理想的性質(zhì)使問題只能用動態(tài)規(guī)劃描述，而不能用動態(tài)規(guī)劃方法求解。8缺點8不包含時間因素的決策問題稱為靜態(tài)決策問題，是一次性決策（如線性規(guī)劃）。但若能恰當(dāng)?shù)厝藶橐搿皶r段”概念，就可以把問題轉(zhuǎn)化成一個多階段決策問題，這樣就能用動態(tài)規(guī)劃處理了。拓寬了動態(tài)規(guī)劃的應(yīng)用范圍。這樣的例子是大量的，如最短線路問題，資源分配問題等等。三、靜態(tài)決策問題的動態(tài)處理9不包含時間因素的決策問題稱為靜態(tài)決策問題，是一次性決策（如線DP中描述多階段決策過程的基本概念主要有：●階段和階段變量●狀態(tài)和狀態(tài)變量●決策、決策變量和決策序列●狀態(tài)轉(zhuǎn)移方程●階段效應(yīng)和目標(biāo)函數(shù)§4-2基本概念、模型與最優(yōu)化原理10DP中描述多階段決策過程的基本概念主要有：§4-2基本概把所研究的多階段決策過程恰當(dāng)?shù)貏澐譃槿舾蓚€相互獨立又相互聯(lián)系的部分，每個部分稱為一個階段。事實上一個階段也就是需要作出一個決策的子問題部分。通常階段是按照過程進行的時間和空間上的先后順序劃分的。并用階段變量k表示。階段數(shù)等于多段決策過程中從開始到結(jié)束所需要作出決策的數(shù)目。劃分階段的目的是便于求解。1、階段和階段變量11把所研究的多階段決策過程恰當(dāng)?shù)貏澐譃槿舾蓚€相互獨立又相互聯(lián)系狀態(tài)是描述系統(tǒng)狀況所必須的信息。一般定義為某一階段的初始點、初始位置和初始情況。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息，階段k的狀態(tài)變量表示為sk。比如：在最短路問題中，狀態(tài)就是網(wǎng)絡(luò)中各個節(jié)點。2、狀態(tài)和狀態(tài)變量12狀態(tài)是描述系統(tǒng)狀況所必須的信息。一般定義為某一階段的初始點、

狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)可能集可以是一個離散取值的集合，也可以是一個連續(xù)的區(qū)間，視所給問題而定。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件。狀態(tài)可能集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，其中sk∈Sk13狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)決策就是決策者從本階段出發(fā)對下一階段狀態(tài)的選擇。多段決策過程的發(fā)展是用各個階段的狀態(tài)演變描述的。因此用狀態(tài)描述的過程具有無后效性，因此在進行階段決策時，只須根據(jù)當(dāng)前的狀態(tài)而無須考慮過去的歷史。在階段k如果給出了決策變量xk隨狀態(tài)變量sk變化的函數(shù)，稱為決策函數(shù)，表示為：xk(sk)。3、決策和決策變量和決策序列14決策就是決策者從本階段出發(fā)對下一階段狀態(tài)的選擇。3、決策和決決策變量的允許取值范圍，稱為允許決策集合。允許決策集合是決策變量的約束條件。xk的允許決策集合表示為Xk。xk

∈Xk，Xk要根據(jù)相應(yīng)的狀態(tài)可能集Sk并結(jié)合具體問題來確定。決策序列就叫策略，策略有全過程策略和子策略之分。全過程策略是整個問題n個段決策過程依次進行的n個階段決策構(gòu)成的序列，簡稱策略，表示為：{x1,x2,…,xn}15決策變量的允許取值范圍，稱為允許決策集合。允許決策集合是決策從階段k到階段n依次進行的階段決策構(gòu)成的決策序列稱為k-子策略。表示為：{xk,xk+1,…,xn}當(dāng)k=1時，k-子策略就是全過程策略。在n段決策過程中，各階段的狀態(tài)可能集合和決策允許集合決定了決策的允許范圍。特別，過程的初始狀態(tài)不同，決策和策略也就不同，即策略是初始狀態(tài)的函數(shù)。16從階段k到階段n依次進行的階段決策構(gòu)成的決策序列稱為狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。多階段過程的發(fā)展就是用階段狀態(tài)的演變來描述的。對具有無后效性的多階段決策過程，系統(tǒng)由從階段k到階段k+1的狀態(tài)轉(zhuǎn)移方程表示為：sk+1=Tk(sk,xk(sk))4、狀態(tài)轉(zhuǎn)移方程17狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。即階段的狀態(tài)完全由階段的狀態(tài)和決策確定，與系統(tǒng)過去的狀態(tài)s1,s2,…,sk-1及其決策x1(s1),x2(s2),…,xk-1(sk-1)無關(guān)。Tk(sk,xk)稱為變換函數(shù)或變換算子。變換函數(shù)可以分為確定型和隨機型兩種類型，據(jù)此形成確定型動態(tài)規(guī)劃和隨機型動態(tài)規(guī)劃。問：狀態(tài)轉(zhuǎn)移方程是否一定是數(shù)學(xué)意義上的方程？18即階段的狀態(tài)完全由階段的狀態(tài)和決策確定，與系統(tǒng)過去的狀態(tài)s1多階段決策過程中，在階段k狀態(tài)sk執(zhí)行決策xk，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也帶來對目標(biāo)函數(shù)的影響。階段效應(yīng)就是執(zhí)行階段決策時所帶來的目標(biāo)函數(shù)的增量。在具有無后效性的多階段決策過程中，階段效應(yīng)完全由階段k的狀態(tài)sk和決策xk決定，與階段以前的狀態(tài)和決策無關(guān)，表示為：Tk(sk,xk)5、階段效應(yīng)和目標(biāo)函數(shù)19多階段決策過程中，在階段k狀態(tài)sk執(zhí)行決策xk，不僅帶來系統(tǒng)多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是由各階段的階段效應(yīng)積累形成。適應(yīng)于動態(tài)規(guī)劃求解的問題的目標(biāo)，必須具有關(guān)于階段效應(yīng)的可分離形式、遞推性。20多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是由各階段的階段效應(yīng)積累形1、構(gòu)模條件一個大前提：恰當(dāng)?shù)膭澐謫栴}的階段，把問題化為多階段決策過程；四個條件：1）正確地選擇狀態(tài)變量能描述過程的演變特征；滿足無后效性可知性—各階段狀態(tài)變量的值直接和間接均為已知。2）能確定決策變量及各階段的允許決策集合：二、多階段決策過程的數(shù)學(xué)模型211、構(gòu)模條件二、多階段決策過程的數(shù)學(xué)模型213）能寫出狀態(tài)轉(zhuǎn)移方程；4）能根據(jù)題意列出階段效應(yīng)和目標(biāo)函數(shù)；在明確四個條件（或四個要素）的基礎(chǔ)上，寫出動態(tài)規(guī)劃基本方程。DP模型的數(shù)學(xué)表達一般形式：式中OPT指最優(yōu)化，根據(jù)問題要求取Max或Min223）能寫出狀態(tài)轉(zhuǎn)移方程；式中OPT指最優(yōu)化，根據(jù)問題要求取M問：動態(tài)規(guī)劃模型有那些部分組成？具體的DP模型包括：四個條件和一個方程（動態(tài)規(guī)劃基本方程）23問：動態(tài)規(guī)劃模型有那些部分組成？具體的DP模型包括：四個條件2、求解要求求出最優(yōu)策略或最優(yōu)線路求出最優(yōu)目標(biāo)函數(shù)值242、求解要求24三、最優(yōu)化原理最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言，下余的決策序列必須構(gòu)成最優(yōu)決策。25三、最優(yōu)化原理最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初§3動態(tài)規(guī)劃應(yīng)用例1最短路徑問題

下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC41231231232216472483867561106375126§3動態(tài)規(guī)劃應(yīng)用例1最短路徑問題BACBDBCDEC41討論：1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di、Ci、Bi、A到E的最短路徑問題。第四階段：兩個始點D1和D2，終點只有一個；

表10-1分析得知：從D1和D2到E的最短路徑唯一。階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D2106106EE27討論：第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2的最短路徑問題：

表10-2分析得知：如果經(jīng)過C1，則最短路為C1-D2-E；如果經(jīng)過C2，則最短路為C2-D2-E；如果經(jīng)過C3，則最短路為C3-D1-E。

階段3本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)D1D2C1C2C38+10=187+10=17

1+10=11

6+6=12

5+6=116+6=12121111D2D2D128第三階段：有三個始點C1，C2，C3，終點有D1，D2，對第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3的最短路徑問題：

表10-3

分析得知：如果經(jīng)過B1，則走B1-C2-D2-E；如果經(jīng)過B2，則走B2-C3-D1-E；如果經(jīng)過B3，則走B3-C3-D1-E；如果經(jīng)過B4，則走B4-C3-D1-E。

階段2本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=19

1+11=127+11=188+11=195+11=166+11=17

2+11=13

3+11=14

1+11=1212131412C2C3C3C329第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2第一階段：只有1個始點A，終點有B1,B2,B3,B4。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

表10-4最后，可以得到：從A到E的最短路徑為AB4C3D1E階段1本階段始點(狀態(tài))本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B430第一階段：只有1個始點A，終點有B1,B2,B3,B4。對

以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。

BACBDBCDEC4123123123321647248386751610601061211111213141412751231以上計算過程及結(jié)果，可用圖2表示，可以看到，以上資源分配問題(離散型)

例2.某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表10-5所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？

表10-5盈利工廠設(shè)備臺數(shù)甲廠乙廠丙廠00001354271063911114121112513111232資源分配問題(離散型)盈利解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)sk=分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。xk=分配給第k個廠設(shè)備臺數(shù)。已知s1=5,并有

從與的定義，可知

以下我們從第三階段開始計算。表格法33解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、

第三階段:顯然將臺設(shè)備都分配給第3工廠時，也就是時，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

由于第3階段是最后的階段，故有其中可取值為0,1,2,3,4,5。其數(shù)值計算見表10－6。

34第三階段:34表10－6

01234500－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－－12125§3動態(tài)規(guī)劃的應(yīng)用(1)35表10－6其中表示取3子過程上最優(yōu)指標(biāo)值時的決策，例如在表10-6中可知當(dāng)=4時，有有此時，即當(dāng)時，此時取（把4臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。第二階段：

當(dāng)把臺設(shè)備分配給第2工廠和第3工廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為

36其中表示取3子過程上最優(yōu)指標(biāo)值時的因為上式也可寫成其數(shù)值計算如表10－7所示。

表10－7

0123450－－－－－0010＋4

－－－－5120＋65＋4－－－10230＋115＋611＋0－－14240＋1211＋411＋0－161,250＋125＋1211＋611＋411＋021237因為上式也可寫成0其中在的這一行里，當(dāng)時，這里從表10－5中可知，把1臺設(shè)備交給乙廠所得盈利數(shù)即可，知，這里從表10－6查即可知=11。同樣可知當(dāng)時，可知;當(dāng)時，；當(dāng)時，；當(dāng)時，；由于，不可能分2廠5臺設(shè)備，故時，欄空著不填。從這些數(shù)值中取得最大即得，即有=16。在此行中我們在取最大值的上面加一橫以示區(qū)別，也可知這時的最優(yōu)決策為1或2。38其中在的這一行里，當(dāng)時，38

第一階段：把臺設(shè)備分配給第1，第2，第3廠時，最大盈利為其中可取值0,1,2,3,4,5.數(shù)值計算見表10－8

表10-8然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個：1.由于，根據(jù)，查表10－7可知，再由，求得。即分配給甲廠0臺，乙廠2臺，丙廠3臺。2.由于，根據(jù)，查表10－7可

0123455

3＋169+1012+513+0210,239第一階段：53＋16知，再由,求得，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到最高的總盈利21萬元。

40知，再由,求得，40解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)sk=分配給第k個廠至第1個廠的設(shè)備臺數(shù)（k=1、2、3）。xk=分配給第k個廠設(shè)備臺數(shù)。設(shè)s1=0,1,…,5并有

s2=0,1,…,5

s3=5

以下我們從第一階段開始計算。用解析法計算41解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、

第一階段:顯然將臺設(shè)備都分配給第1工廠時，也就是時，第1階段的指標(biāo)值（即第1廠的盈利）為最大，即

由于第3階段是最后的階段，故有其中x1可取值為0,1,2,3,4,5。

42第一階段:42第二階段：

當(dāng)把臺設(shè)備分配給第1工廠和第2工廠時，則對每個s2值，有一種最優(yōu)分配方案，使最大盈利,即最優(yōu)2階段子過程最優(yōu)指標(biāo)函數(shù)值為43第二階段：43444445454646第三階段：

當(dāng)把s3=5臺設(shè)備分配給第1工廠、第2工廠和第3工廠時，即最優(yōu)3階段子過程最優(yōu)指標(biāo)函數(shù)值為47第三階段：4748484949資源分配問題(連續(xù)型)將問題劃分為三個階段,設(shè)狀態(tài)變量為s1,s2,s3,并s3=10,取x1,x2,x3為各階段的決策變量,各階段的指標(biāo)函數(shù)按加法方式結(jié)合,令最優(yōu)函數(shù)fk(sk)表示第k階段結(jié)束狀態(tài)為sk,第1階段至第k階段的最大值.50資源分配問題(連續(xù)型)將問題劃分為三個階段,設(shè)狀態(tài)變量為s151515252第十章動態(tài)規(guī)劃§4-1引言及內(nèi)容框架§4-2基本概念、模型與最優(yōu)化原理§4-3動態(tài)規(guī)劃的應(yīng)用53第十章動態(tài)規(guī)劃§4-1引言及內(nèi)容框架1§4-1引言■動態(tài)規(guī)劃的研究對象■動態(tài)規(guī)劃問題的特點■靜態(tài)決策問題的動態(tài)處理54§4-1引言■動態(tài)規(guī)劃的研究對象2一、動態(tài)規(guī)劃的研究對象

——多階段的決策問題1多階段決策問題動態(tài)決策——將時間作為變量的決策問題稱為動態(tài)決策。其基本特點是多次決策。多階段決策問題是一類特殊形式的動態(tài)決策問題。是指這樣一類活動過程：系統(tǒng)的動態(tài)動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系又相互區(qū)別的階段，而且每個階段都進行決策，當(dāng)每個階段決策確定以后，就完全確定了一個過程確定的線路。55一、動態(tài)規(guī)劃的研究對象

多階段決策問題的典型例子※企業(yè)生產(chǎn)過程中，由于需求是隨著時間變化的因素，因此企業(yè)為了獲得全年最佳經(jīng)濟效益，就要在整個過程中進行逐月和逐季的根據(jù)庫存和需求決定生產(chǎn)計劃?！撤N機器，可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷下生產(chǎn)時的產(chǎn)量多，但每生產(chǎn)一個階段的機器完好率低；低負(fù)荷下生產(chǎn)時的情況則相反?，F(xiàn)在需要安排該種機器在多個階段內(nèi)的生產(chǎn)，問應(yīng)如何決定各個階段中機器的使用，使這個計劃期內(nèi)的總產(chǎn)量最大？56多階段決策問題的典型例子※企業(yè)生產(chǎn)過程中，由于需求是隨著時※某臺設(shè)備。例如汽車，剛買來時故障低，耗油少，出車時間長，處理價值和經(jīng)濟效益高；隨著使用時間的增加則變?yōu)楣收隙?、耗油高、維修費用增加，經(jīng)濟效益差，使用時間越長，處理價值越低。另外每次更新都要付出更新費用。因此應(yīng)如何決定設(shè)備的使用年限，使總的效益最佳？※化工生產(chǎn)過程包括一系列的過程設(shè)備，如反映器、蒸餾塔、吸收器等，前一設(shè)備的輸出是后一設(shè)備的輸入。因此，應(yīng)如何控制生產(chǎn)過程中各個設(shè)備的輸出和輸入，使總產(chǎn)量最大？57※某臺設(shè)備。例如汽車，剛買來時故障低，耗油少，出車時間長，處什么是動態(tài)規(guī)劃？DP是OR中的一個分支，是解決多階段決策過程最優(yōu)化的一種方法或是一種分析多階段決策過程的數(shù)學(xué)方法。這種方法可根據(jù)人們所采取的措施，一步步地控制過程的發(fā)展，來實現(xiàn)預(yù)定的要求。這一運籌學(xué)分支最初有美國數(shù)學(xué)家BELLMAN等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的最優(yōu)化原理，并研究了許多實際問題而建立起來的。58什么是動態(tài)規(guī)劃？DP是OR中的一個分支，是解決多階段決策過程動態(tài)規(guī)劃的特點優(yōu)點①許多問題用動態(tài)規(guī)劃研究求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問題，解析數(shù)學(xué)無用武之地。而動態(tài)規(guī)劃成為得力工具；②某些情況下，用動態(tài)規(guī)劃處理不僅能定性描述分析，且可利用計算機給出求其數(shù)值解的方法。二、動態(tài)規(guī)劃問題的特點59動態(tài)規(guī)劃的特點優(yōu)點二、動態(tài)規(guī)劃問題的特點7缺點①沒有統(tǒng)一的處理方法，求解時要根據(jù)問題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此實踐經(jīng)驗及創(chuàng)造性思維將起重要的引導(dǎo)作用；②“維數(shù)障礙”，當(dāng)變量個數(shù)太多時，由于計算機內(nèi)存和速度的限制導(dǎo)致問題無法解決。有些問題由于涉及的函數(shù)沒有理想的性質(zhì)使問題只能用動態(tài)規(guī)劃描述，而不能用動態(tài)規(guī)劃方法求解。60缺點8不包含時間因素的決策問題稱為靜態(tài)決策問題，是一次性決策（如線性規(guī)劃）。但若能恰當(dāng)?shù)厝藶橐搿皶r段”概念，就可以把問題轉(zhuǎn)化成一個多階段決策問題，這樣就能用動態(tài)規(guī)劃處理了。拓寬了動態(tài)規(guī)劃的應(yīng)用范圍。這樣的例子是大量的，如最短線路問題，資源分配問題等等。三、靜態(tài)決策問題的動態(tài)處理61不包含時間因素的決策問題稱為靜態(tài)決策問題，是一次性決策（如線DP中描述多階段決策過程的基本概念主要有：●階段和階段變量●狀態(tài)和狀態(tài)變量●決策、決策變量和決策序列●狀態(tài)轉(zhuǎn)移方程●階段效應(yīng)和目標(biāo)函數(shù)§4-2基本概念、模型與最優(yōu)化原理62DP中描述多階段決策過程的基本概念主要有：§4-2基本概把所研究的多階段決策過程恰當(dāng)?shù)貏澐譃槿舾蓚€相互獨立又相互聯(lián)系的部分，每個部分稱為一個階段。事實上一個階段也就是需要作出一個決策的子問題部分。通常階段是按照過程進行的時間和空間上的先后順序劃分的。并用階段變量k表示。階段數(shù)等于多段決策過程中從開始到結(jié)束所需要作出決策的數(shù)目。劃分階段的目的是便于求解。1、階段和階段變量63把所研究的多階段決策過程恰當(dāng)?shù)貏澐譃槿舾蓚€相互獨立又相互聯(lián)系狀態(tài)是描述系統(tǒng)狀況所必須的信息。一般定義為某一階段的初始點、初始位置和初始情況。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息，階段k的狀態(tài)變量表示為sk。比如：在最短路問題中，狀態(tài)就是網(wǎng)絡(luò)中各個節(jié)點。2、狀態(tài)和狀態(tài)變量64狀態(tài)是描述系統(tǒng)狀況所必須的信息。一般定義為某一階段的初始點、

狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)可能集可以是一個離散取值的集合，也可以是一個連續(xù)的區(qū)間，視所給問題而定。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件。狀態(tài)可能集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，其中sk∈Sk65狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)決策就是決策者從本階段出發(fā)對下一階段狀態(tài)的選擇。多段決策過程的發(fā)展是用各個階段的狀態(tài)演變描述的。因此用狀態(tài)描述的過程具有無后效性，因此在進行階段決策時，只須根據(jù)當(dāng)前的狀態(tài)而無須考慮過去的歷史。在階段k如果給出了決策變量xk隨狀態(tài)變量sk變化的函數(shù)，稱為決策函數(shù)，表示為：xk(sk)。3、決策和決策變量和決策序列66決策就是決策者從本階段出發(fā)對下一階段狀態(tài)的選擇。3、決策和決決策變量的允許取值范圍，稱為允許決策集合。允許決策集合是決策變量的約束條件。xk的允許決策集合表示為Xk。xk

∈Xk，Xk要根據(jù)相應(yīng)的狀態(tài)可能集Sk并結(jié)合具體問題來確定。決策序列就叫策略，策略有全過程策略和子策略之分。全過程策略是整個問題n個段決策過程依次進行的n個階段決策構(gòu)成的序列，簡稱策略，表示為：{x1,x2,…,xn}67決策變量的允許取值范圍，稱為允許決策集合。允許決策集合是決策從階段k到階段n依次進行的階段決策構(gòu)成的決策序列稱為k-子策略。表示為：{xk,xk+1,…,xn}當(dāng)k=1時，k-子策略就是全過程策略。在n段決策過程中，各階段的狀態(tài)可能集合和決策允許集合決定了決策的允許范圍。特別，過程的初始狀態(tài)不同，決策和策略也就不同，即策略是初始狀態(tài)的函數(shù)。68從階段k到階段n依次進行的階段決策構(gòu)成的決策序列稱為狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。多階段過程的發(fā)展就是用階段狀態(tài)的演變來描述的。對具有無后效性的多階段決策過程，系統(tǒng)由從階段k到階段k+1的狀態(tài)轉(zhuǎn)移方程表示為：sk+1=Tk(sk,xk(sk))4、狀態(tài)轉(zhuǎn)移方程69狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。即階段的狀態(tài)完全由階段的狀態(tài)和決策確定，與系統(tǒng)過去的狀態(tài)s1,s2,…,sk-1及其決策x1(s1),x2(s2),…,xk-1(sk-1)無關(guān)。Tk(sk,xk)稱為變換函數(shù)或變換算子。變換函數(shù)可以分為確定型和隨機型兩種類型，據(jù)此形成確定型動態(tài)規(guī)劃和隨機型動態(tài)規(guī)劃。問：狀態(tài)轉(zhuǎn)移方程是否一定是數(shù)學(xué)意義上的方程？70即階段的狀態(tài)完全由階段的狀態(tài)和決策確定，與系統(tǒng)過去的狀態(tài)s1多階段決策過程中，在階段k狀態(tài)sk執(zhí)行決策xk，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也帶來對目標(biāo)函數(shù)的影響。階段效應(yīng)就是執(zhí)行階段決策時所帶來的目標(biāo)函數(shù)的增量。在具有無后效性的多階段決策過程中，階段效應(yīng)完全由階段k的狀態(tài)sk和決策xk決定，與階段以前的狀態(tài)和決策無關(guān)，表示為：Tk(sk,xk)5、階段效應(yīng)和目標(biāo)函數(shù)71多階段決策過程中，在階段k狀態(tài)sk執(zhí)行決策xk，不僅帶來系統(tǒng)多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是由各階段的階段效應(yīng)積累形成。適應(yīng)于動態(tài)規(guī)劃求解的問題的目標(biāo)，必須具有關(guān)于階段效應(yīng)的可分離形式、遞推性。72多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是由各階段的階段效應(yīng)積累形1、構(gòu)模條件一個大前提：恰當(dāng)?shù)膭澐謫栴}的階段，把問題化為多階段決策過程；四個條件：1）正確地選擇狀態(tài)變量能描述過程的演變特征；滿足無后效性可知性—各階段狀態(tài)變量的值直接和間接均為已知。2）能確定決策變量及各階段的允許決策集合：二、多階段決策過程的數(shù)學(xué)模型731、構(gòu)模條件二、多階段決策過程的數(shù)學(xué)模型213）能寫出狀態(tài)轉(zhuǎn)移方程；4）能根據(jù)題意列出階段效應(yīng)和目標(biāo)函數(shù)；在明確四個條件（或四個要素）的基礎(chǔ)上，寫出動態(tài)規(guī)劃基本方程。DP模型的數(shù)學(xué)表達一般形式：式中OPT指最優(yōu)化，根據(jù)問題要求取Max或Min743）能寫出狀態(tài)轉(zhuǎn)移方程；式中OPT指最優(yōu)化，根據(jù)問題要求取M問：動態(tài)規(guī)劃模型有那些部分組成？具體的DP模型包括：四個條件和一個方程（動態(tài)規(guī)劃基本方程）75問：動態(tài)規(guī)劃模型有那些部分組成？具體的DP模型包括：四個條件2、求解要求求出最優(yōu)策略或最優(yōu)線路求出最優(yōu)目標(biāo)函數(shù)值762、求解要求24三、最優(yōu)化原理最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言，下余的決策序列必須構(gòu)成最優(yōu)決策。77三、最優(yōu)化原理最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初§3動態(tài)規(guī)劃應(yīng)用例1最短路徑問題

下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC41231231232216472483867561106375178§3動態(tài)規(guī)劃應(yīng)用例1最短路徑問題BACBDBCDEC41討論：1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di、Ci、Bi、A到E的最短路徑問題。第四階段：兩個始點D1和D2，終點只有一個；

表10-1分析得知：從D1和D2到E的最短路徑唯一。階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D2106106EE79討論：第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2的最短路徑問題：

表10-2分析得知：如果經(jīng)過C1，則最短路為C1-D2-E；如果經(jīng)過C2，則最短路為C2-D2-E；如果經(jīng)過C3，則最短路為C3-D1-E。

階段3本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)D1D2C1C2C38+10=187+10=17

1+10=11

6+6=12

5+6=116+6=12121111D2D2D180第三階段：有三個始點C1，C2，C3，終點有D1，D2，對第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3的最短路徑問題：

表10-3

分析得知：如果經(jīng)過B1，則走B1-C2-D2-E；如果經(jīng)過B2，則走B2-C3-D1-E；如果經(jīng)過B3，則走B3-C3-D1-E；如果經(jīng)過B4，則走B4-C3-D1-E。

階段2本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=19

1+11=127+11=188+11=195+11=166+11=17

2+11=13

3+11=14

1+11=1212131412C2C3C3C381第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2第一階段：只有1個始點A，終點有B1,B2,B3,B4。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

表10-4最后，可以得到：從A到E的最短路徑為AB4C3D1E階段1本階段始點(狀態(tài))本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B482第一階段：只有1個始點A，終點有B1,B2,B3,B4。對

以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。

BACBDBCDEC4123123123321647248386751610601061211111213141412751283以上計算過程及結(jié)果，可用圖2表示，可以看到，以上資源分配問題(離散型)

例2.某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表10-5所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？

表10-5盈利工廠設(shè)備臺數(shù)甲廠乙廠丙廠00001354271063911114121112513111284資源分配問題(離散型)盈利解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)sk=分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。xk=分配給第k個廠設(shè)備臺數(shù)。已知s1=5,并有

從與的定義，可知

以下我們從第三階段開始計算。表格法85解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、

第三階段:顯然將臺設(shè)備都分配給第3工廠時，也就是時，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

由于第3階段是最后的階段，故有其中可取值為0,1,2,3,4,5。其數(shù)值計算見表10－6。

86第三階段:34表10－6

01234500－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－－12125§3動態(tài)規(guī)劃的應(yīng)用(1)87表10－6其中表示取3子過程上最優(yōu)指標(biāo)值時的決策，例如在表10-6中可知當(dāng)=4時，有有此時，即當(dāng)時，此時?。ò?臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。第二階段：

當(dāng)把臺設(shè)備分配給第2工廠和第3工廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為

88其中表示取3子過程上最優(yōu)指標(biāo)值時的因為上式也可寫成其數(shù)值計算如表10－7所示。

表10－7

0123450－－－－－