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

運籌學(xué)趙明霞山西大學(xué)經(jīng)濟與管理學(xué)院運籌學(xué)趙明霞2023/1/22第七章動態(tài)規(guī)劃多階段決策過程最優(yōu)化問題基本概念、基本原理動態(tài)規(guī)劃建模與求解動態(tài)規(guī)劃的應(yīng)用2022/12/182第七章動態(tài)規(guī)劃多階段決策過程最優(yōu)化2023/1/23第一節(jié)多階段決策過程最優(yōu)化問題舉例例1最短路徑問題下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC4123123123221647248386756110637512022/12/183第一節(jié)多階段決策過程最優(yōu)化問題舉例例2023/1/24用窮舉法的計算量:如果從A到E的站點有k個，除A、E之外每站有3個位置則總共有3k-1×2條路徑；計算各路徑長度總共要進行(k+1)3k-1×2次加法以及3k-1×2-1次比較。隨著k的值增加時，需要進行的加法和比較的次數(shù)將迅速增加；例如當(dāng)k=20時，加法次數(shù)為4.2550833966227×1015

次，比較1.3726075472977×1014

次。若用1億次/秒的計算機計算需要約508天。2022/12/184用窮舉法的計算量:2023/1/25逆序解法順序解法第二節(jié)基本概念、基本方程與最優(yōu)化原理2022/12/185逆序解法第二節(jié)基本概念、基本方程與最2023/1/261、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。

2、狀態(tài)sk：每個階段開始時所處的自然狀態(tài)或客觀條件。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)∈D

k(sk)。

4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。

5、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。6、指標(biāo)函數(shù)rk(sk,uk)：衡量策略優(yōu)劣的數(shù)量指標(biāo)；最優(yōu)指標(biāo)函數(shù)fk(sk)，f1(s1)。一、逆序解法2022/12/1861、階段k：表示決策順序的離散2023/1/27

對于可加性指標(biāo)函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為

以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。

終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)=0。基本方程2022/12/187對于可加性指標(biāo)函數(shù)，上式2023/1/28最優(yōu)化原理作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。2022/12/188最優(yōu)化原理2023/1/29二、順序解法狀態(tài)轉(zhuǎn)移方程sk=Tk(sk+1,xk)最優(yōu)指標(biāo)函數(shù)fk(sk+1)，

fn(sn+1)基本方程2022/12/189二、順序解法狀態(tài)轉(zhuǎn)移方程sk=T2023/1/210一、基本步驟1．應(yīng)將實際問題恰當(dāng)?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，必須具備以下三個特征：

(1)要能夠正確地描述受控過程的變化特征。

(2)要滿足無后效性。即如果在某個階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響。

(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。第三節(jié)動態(tài)規(guī)劃建模與求解2022/12/1810一、基本步驟1．應(yīng)將實際問題恰當(dāng)?shù)胤?023/1/2113．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量。4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。5．正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)。6．寫出動態(tài)規(guī)劃函數(shù)基本方程2022/12/18113．正確地定義決策變量及各階段的允許2023/1/212例1：

1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di

、Ci、Bi、A到E的最短路徑問題。第四階段：兩個始點D1和D2，終點只有一個；

分析得知：從D1和D2到E的最短路徑唯一。

階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D210*6106EE二、離散變量----分段窮舉算法2022/12/1812例1：2023/1/213

第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2

的最短路徑問題：分析得知：如果經(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=171+10=116+6=125+6=116+6=12121111D2D2D12022/12/1813第三階段：有三個始點C1，C2，C2023/1/214第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3

的最短路徑問題：分析得知：如果經(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=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C32022/12/1814第二階段：有4個始點B1,B2,B32023/1/215第一階段：只有1個始點A，終點有B1,B2,B3,B4

。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

最后，可以得到：從A到E的最短路徑為AB4C3D1E

階段1本階段始點(狀態(tài))

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B42022/12/1815第一階段：只有1個始點A，終點有B12023/1/216

以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。以上過程，僅用了22次加法，計算效率遠高于窮舉法。BACBDBCDEC412312312332164724838675161060106121111121314141275122022/12/1816以上計算過程及結(jié)果，可用2023/1/217教材例2三、連續(xù)變量2022/12/1817教材例2三、連續(xù)變量2023/1/218最短路徑問題（例1）資源分配問題（投資問題）背包問題生產(chǎn)經(jīng)營問題系統(tǒng)可靠性問題設(shè)備更新問題機器負荷分配問題貨郎擔(dān)問題第四節(jié)動態(tài)規(guī)劃的應(yīng)用2022/12/1818最短路徑問題（例1）第四節(jié)動態(tài)規(guī)2023/1/219

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

工廠盈利設(shè)備臺數(shù)

甲廠

乙廠

丙廠000013542710639111141211125131112資源分配問題2022/12/1819

例3.某公司擬將某種2023/1/220解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)

sk=分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。

xk=分配給第k個廠設(shè)備臺數(shù)。已知s1=5,

并有

從sk

與xk

的定義，可知

以下我們從第三階段開始計算。2022/12/1820解：將問題按工廠分為三個階段，甲、乙2023/1/221

第三階段:

顯然將s3(s3=0,1,2,3,4,5)臺設(shè)備都分配給第3工廠時，也就是s3=x3時，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

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

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－121252022/12/182200－2023/1/223

其中x*3表示取3子過程上最優(yōu)指標(biāo)值f3(s3)時的x3決策，例如在表中可知當(dāng)s3=4時，有r3(4,4)=12,有f3(4)=12此時x*3=4，即當(dāng)s3=4時，此時取x3=4

（把4臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。2022/12/1823其中x*3表示取3子2023/1/224第二階段：當(dāng)把s2=0,1,2,3,4,5臺設(shè)備分配給第2工廠和第3工廠時，則對每個s2值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為因為s3=s2-x2上式也可寫成2022/12/1824第二階段：因為s3=s2-x2上式也2023/1/225

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

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

0

1

2

3

4

5

5

3＋169+1012+513+0210,22022/12/1826第一階段：52023/1/227然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個：

1.由于x*1=0，根據(jù)s2=s1-x*1=5，查表10－7可知x*2=2，再由s3=s2-x*2=3，求得x*3=s3=3。即分配給甲廠0臺，乙廠2臺，丙廠3臺。

2.由于x*1=2，根據(jù)s2=s1-x*1=3，查表10－7可知x*2=2，再由s3=s2-x*2=1,求得x*3=s3=1，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到最高的總盈利21萬元。2022/12/1827然后按計算表格的順序推算，可知最優(yōu)分2023/1/228

設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi公斤，每件價值ci元。現(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i=1,2,…,n），背包中物品的總價值為z，則

maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且為整數(shù)。背包問題2022/12/1828設(shè)有n種物品，每一種2023/1/229

下面用動態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量sk：第k次裝載時背包還可以裝載的重量；決策變量xk：第k次裝載第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skwkxk；階段指標(biāo)：rk=ckxk；最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價值；遞推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(skwkxk)}；

xDk(sk)終端條件：fn+1(sn+1)=0。2022/12/1829下面用動態(tài)規(guī)劃逆序解2023/1/230

例4.某咨詢公司有10個工作日可以去處理四種類型的咨詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個客戶所需工作日數(shù)以及所獲得的利潤如表所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個工作日中獲利最大？

咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤

1

2

3

4

4

3

2

2

1

3

4

7

2

8

11

202022/12/1830例4.某咨詢公司有10個工作日2023/1/231

解：用動態(tài)規(guī)劃來求解此題。我們把此問題分成四個階段：第一階段我們決策將處理多少個第一種咨詢項目類型中的客戶，第二階段決策將處理多少個第二種咨詢項目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們設(shè)

sk＝分配給第k種咨詢項目到第四種咨詢項目的所有客戶的總工作日（第k階段的狀態(tài)變量）。

xk=在第k種咨詢項目中處理客戶的數(shù)量（第k階段的決策變量）。已知s1＝10并有2022/12/1831解：用動態(tài)規(guī)劃來求解此題。2023/1/232從第四階段開始計算：顯然將s4個工作日s4=(0,1,2……,10)盡可能分配給第四類咨詢項目，即x4=[s4/7]時，第四階段的指標(biāo)值為最大，其中[s4/7]表示取不大于[s4/7]的最大整數(shù)，符號[]為取整符號，故有由于第四階段是最后的階段，故有2022/12/1832從第四階段開始計算：2023/1/233因為s4至多為10，其數(shù)值計算見表

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

20

12022/12/1833因為s4至多為10，其數(shù)值計算見表2023/1/234第三階段：當(dāng)把s3=(0,1,2……,10)個工作日分配給第四類和第三類咨詢項目時，則對每個s3值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標(biāo)函數(shù)值為

因為因為s3

至多為10，所以x3的取值可為0,1,2。其數(shù)值計算見表10－11。2022/12/1834第三階段：2023/1/235

012

0－－

0

01

－－

0

02－－

0

03－－

0

04

0＋0－

1115

0＋0－

1116

0＋0－

1117

11+0－2008

0＋20

11+0

2229

0＋20

11+0

22210

0＋20

11+0

2222022/12/183502023/1/236第二階段：同樣以每個s2值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為：因為，故有因為s2至多為10，所以x2的取值為0,1,2,3。2022/12/1836第二階段：2023/1/2372022/12/18372023/1/238

第一階段：我們已知，又因為，同樣有

因為,故可取值為0,1,2,…,10。2022/12/1838第一階段：2023/1/239可知f1(10)=28，x*1=0從而得s2=s1-x*1＝10－0＝10s2=10的這一行可知x*2=1，由s3=s2-3x*1＝7s3=7的這一行可知x*3=0，最后由s4=s3-x*3＝7s4=7這一行得x*4=1綜上所述得最優(yōu)解為：x*1=0,x*2=1，x*3=0，x*4=1,最大盈利為28。現(xiàn)在我們不妨假設(shè)該咨詢公司的工作計劃有所改變，只有8個工作日來處理這四類咨詢項目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開始重做這個問題，而只要在第一階段上把s1改成8，重新計算就可得到結(jié)果，這是動態(tài)規(guī)劃的一個好處。2022/12/1839可知f1(10)=28，x*1=0從2023/1/240

得到兩組最優(yōu)解如下：

它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計算第一階段，而且要在第二、第三、第四階段的計算表上補上增加的工作日的新的信息，也可得到新的結(jié)果。2022/12/18402023/1/241

例5.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購買，所以該公司可以預(yù)測未來幾個月的需求量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn)計劃，這四個月的需求如表所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費為4，除了調(diào)度費用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺花費為1。最大生產(chǎn)能力每月為4臺。生產(chǎn)與存貯問題2022/12/1841例5.某公司為主要電力公2023/1/242每臺變壓器在倉庫中由這個月存到下個月的儲存費為1，倉庫的最大儲存能力為3臺，另外，知道在1月1日時倉庫里存有一臺變壓器，要求在4月30日倉庫的庫存量為零。試問該公司應(yīng)如何制定生產(chǎn)計劃，使得四個月的生產(chǎn)成本和儲存總費用最少？2022/12/1842每臺變壓器在倉庫中由這個月存到下2023/1/243解：我們按月份來劃分階段，第i個月為第i階段：（i=1,2,3,4).

設(shè)為第k階段期初庫存量；k=1,2,3,4

為第k階段生產(chǎn)量；k=1,2,3,4為第k階段需求量；k=1,2,3,4，這已在表10-15中告訴我們。因為下個月的庫存量等于上個月的庫存量加上上個月的產(chǎn)量減去上個月的需求量，我們就得到了如下狀態(tài)轉(zhuǎn)移方程：因為，故有

因為，故有2022/12/1843解：我們按月份來劃分階段，第i個月為2023/1/244由于必須要滿足需求，則有

通過移項得到

另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力（4臺），也不大于第k階段至第四階段的需求之和與第k階段期初庫存量之差，否則第k階段的生產(chǎn)量就要超過從第k階段至第四階段的總需求，故有

以下我們從第四階段開始計算：從以上的狀態(tài)轉(zhuǎn)移方程可知這樣就有2022/12/1844由于必須要滿足需求，則有2023/1/245

這里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與儲存費，即為由于第四階段末要求庫存為零，即有，這樣可得對于每個的可行值，的值列于表2022/12/1845這里的階段指標(biāo)2023/1/246表中當(dāng)時，可知第四階段要生產(chǎn)臺，從表可知總成本為9，同樣可以算出當(dāng)為1,2,3時的情況，結(jié)果已列于表中。第三階段：此時有：因為以及所以有例如，當(dāng)?shù)谌A段初庫存量時，生產(chǎn)量為2時，則所以生產(chǎn)成本為8，第三階段末庫存為2時，儲存費為，而2022/12/1846表中當(dāng)時，可知第四階段要生2023/1/247可知，這樣可知，填入表中的欄內(nèi)，其他結(jié)果如表：第二階段：因為所以有2022/12/1847可知，這樣可知，2023/1/248

計算結(jié)果如表所示。

表

2022/12/1848計算結(jié)果如表所示。2023/1/249第一階段：因為故有

計算結(jié)果見表。

2022/12/1849第一階段：2023/1/250利用遞推關(guān)系可以得到兩組最優(yōu)解：這時有最低總成本29。2022/12/1850利用遞推關(guān)系可以得到兩組最優(yōu)解：2023/1/251教材例82022/12/1851教材例82023/1/252

例6.某科研項目組由三個小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個小組都失敗的可能性，現(xiàn)決定給三個小組中增派兩名高級科學(xué)家，到各小組后，各小組科研項目失敗概率如下表：問如何分派科學(xué)家才能使三個小組都失敗的概率（即科研項目最終失敗的概率）最?。扛呒壙茖W(xué)家小組12300.400.600.8010.200.400.5020.150.200.30系統(tǒng)可靠性問題2022/12/1852例6.某科2023/1/253

解：用逆序算法。設(shè)階段：每個研究小組為一個階段，且階段123小組1232022/12/1853解：用逆序算法。設(shè)階段122023/1/254計算當(dāng)n=3時，當(dāng)n=2時，s3f3*(s3)x3*00．80010．50120．302

x2s2f2(s2,x2)=P2(x2)·f3*(s2-x2)f2*(s2)x2*01200．480．48010．300．320．30020．180．200．160．1622022/12/1854計算2023/1/255

當(dāng)n=1時，最優(yōu)解為x1*=1，x2*=0，x3*=1；科研項目最終失敗的概率為0.060。x1s1f1(s1,x1)=P1(x1)·f2*(s1-x1)f2*(s2)x2*01220．0640．0600．0720．06012022/12/1855當(dāng)n=1時，2023/1/256教材例9設(shè)備更新問題2022/12/1856教材例9設(shè)備更新問題2023/1/257順序解法2022/12/1857順序解法2023/1/258習(xí)題7.27.37.47.87.142022/12/1858習(xí)題7.2運籌學(xué)趙明霞山西大學(xué)經(jīng)濟與管理學(xué)院運籌學(xué)趙明霞2023/1/260第七章動態(tài)規(guī)劃多階段決策過程最優(yōu)化問題基本概念、基本原理動態(tài)規(guī)劃建模與求解動態(tài)規(guī)劃的應(yīng)用2022/12/182第七章動態(tài)規(guī)劃多階段決策過程最優(yōu)化2023/1/261第一節(jié)多階段決策過程最優(yōu)化問題舉例例1最短路徑問題下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC4123123123221647248386756110637512022/12/183第一節(jié)多階段決策過程最優(yōu)化問題舉例例2023/1/262用窮舉法的計算量:如果從A到E的站點有k個，除A、E之外每站有3個位置則總共有3k-1×2條路徑；計算各路徑長度總共要進行(k+1)3k-1×2次加法以及3k-1×2-1次比較。隨著k的值增加時，需要進行的加法和比較的次數(shù)將迅速增加；例如當(dāng)k=20時，加法次數(shù)為4.2550833966227×1015

次，比較1.3726075472977×1014

次。若用1億次/秒的計算機計算需要約508天。2022/12/184用窮舉法的計算量:2023/1/263逆序解法順序解法第二節(jié)基本概念、基本方程與最優(yōu)化原理2022/12/185逆序解法第二節(jié)基本概念、基本方程與最2023/1/2641、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。

2、狀態(tài)sk：每個階段開始時所處的自然狀態(tài)或客觀條件。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)∈D

k(sk)。

4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。

5、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。6、指標(biāo)函數(shù)rk(sk,uk)：衡量策略優(yōu)劣的數(shù)量指標(biāo)；最優(yōu)指標(biāo)函數(shù)fk(sk)，f1(s1)。一、逆序解法2022/12/1861、階段k：表示決策順序的離散2023/1/265

對于可加性指標(biāo)函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為

以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。

終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)=0。基本方程2022/12/187對于可加性指標(biāo)函數(shù)，上式2023/1/266最優(yōu)化原理作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。2022/12/188最優(yōu)化原理2023/1/267二、順序解法狀態(tài)轉(zhuǎn)移方程sk=Tk(sk+1,xk)最優(yōu)指標(biāo)函數(shù)fk(sk+1)，

fn(sn+1)基本方程2022/12/189二、順序解法狀態(tài)轉(zhuǎn)移方程sk=T2023/1/268一、基本步驟1．應(yīng)將實際問題恰當(dāng)?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，必須具備以下三個特征：

(1)要能夠正確地描述受控過程的變化特征。

(2)要滿足無后效性。即如果在某個階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響。

(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。第三節(jié)動態(tài)規(guī)劃建模與求解2022/12/1810一、基本步驟1．應(yīng)將實際問題恰當(dāng)?shù)胤?023/1/2693．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量。4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。5．正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)。6．寫出動態(tài)規(guī)劃函數(shù)基本方程2022/12/18113．正確地定義決策變量及各階段的允許2023/1/270例1：

1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di

、Ci、Bi、A到E的最短路徑問題。第四階段：兩個始點D1和D2，終點只有一個；

分析得知：從D1和D2到E的最短路徑唯一。

階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D210*6106EE二、離散變量----分段窮舉算法2022/12/1812例1：2023/1/271

第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2

的最短路徑問題：分析得知：如果經(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=171+10=116+6=125+6=116+6=12121111D2D2D12022/12/1813第三階段：有三個始點C1，C2，C2023/1/272第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3

的最短路徑問題：分析得知：如果經(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=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C32022/12/1814第二階段：有4個始點B1,B2,B32023/1/273第一階段：只有1個始點A，終點有B1,B2,B3,B4

。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

最后，可以得到：從A到E的最短路徑為AB4C3D1E

階段1本階段始點(狀態(tài))

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B42022/12/1815第一階段：只有1個始點A，終點有B12023/1/274

以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。以上過程，僅用了22次加法，計算效率遠高于窮舉法。BACBDBCDEC412312312332164724838675161060106121111121314141275122022/12/1816以上計算過程及結(jié)果，可用2023/1/275教材例2三、連續(xù)變量2022/12/1817教材例2三、連續(xù)變量2023/1/276最短路徑問題（例1）資源分配問題（投資問題）背包問題生產(chǎn)經(jīng)營問題系統(tǒng)可靠性問題設(shè)備更新問題機器負荷分配問題貨郎擔(dān)問題第四節(jié)動態(tài)規(guī)劃的應(yīng)用2022/12/1818最短路徑問題（例1）第四節(jié)動態(tài)規(guī)2023/1/277

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

工廠盈利設(shè)備臺數(shù)

甲廠

乙廠

丙廠000013542710639111141211125131112資源分配問題2022/12/1819

例3.某公司擬將某種2023/1/278解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)

sk=分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。

xk=分配給第k個廠設(shè)備臺數(shù)。已知s1=5,

并有

從sk

與xk

的定義，可知

以下我們從第三階段開始計算。2022/12/1820解：將問題按工廠分為三個階段，甲、乙2023/1/279

第三階段:

顯然將s3(s3=0,1,2,3,4,5)臺設(shè)備都分配給第3工廠時，也就是s3=x3時，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

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

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－121252022/12/182200－2023/1/281

其中x*3表示取3子過程上最優(yōu)指標(biāo)值f3(s3)時的x3決策，例如在表中可知當(dāng)s3=4時，有r3(4,4)=12,有f3(4)=12此時x*3=4，即當(dāng)s3=4時，此時取x3=4

（把4臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。2022/12/1823其中x*3表示取3子2023/1/282第二階段：當(dāng)把s2=0,1,2,3,4,5臺設(shè)備分配給第2工廠和第3工廠時，則對每個s2值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為因為s3=s2-x2上式也可寫成2022/12/1824第二階段：因為s3=s2-x2上式也2023/1/283

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

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

0

1

2

3

4

5

5

3＋169+1012+513+0210,22022/12/1826第一階段：52023/1/285然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個：

1.由于x*1=0，根據(jù)s2=s1-x*1=5，查表10－7可知x*2=2，再由s3=s2-x*2=3，求得x*3=s3=3。即分配給甲廠0臺，乙廠2臺，丙廠3臺。

2.由于x*1=2，根據(jù)s2=s1-x*1=3，查表10－7可知x*2=2，再由s3=s2-x*2=1,求得x*3=s3=1，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到最高的總盈利21萬元。2022/12/1827然后按計算表格的順序推算，可知最優(yōu)分2023/1/286

設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi公斤，每件價值ci元?，F(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i=1,2,…,n），背包中物品的總價值為z，則

maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且為整數(shù)。背包問題2022/12/1828設(shè)有n種物品，每一種2023/1/287

下面用動態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量sk：第k次裝載時背包還可以裝載的重量；決策變量xk：第k次裝載第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skwkxk；階段指標(biāo)：rk=ckxk；最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價值；遞推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(skwkxk)}；

xDk(sk)終端條件：fn+1(sn+1)=0。2022/12/1829下面用動態(tài)規(guī)劃逆序解2023/1/288

例4.某咨詢公司有10個工作日可以去處理四種類型的咨詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個客戶所需工作日數(shù)以及所獲得的利潤如表所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個工作日中獲利最大？

咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤

1

2

3

4

4

3

2

2

1

3

4

7

2

8

11

202022/12/1830例4.某咨詢公司有10個工作日2023/1/289

解：用動態(tài)規(guī)劃來求解此題。我們把此問題分成四個階段：第一階段我們決策將處理多少個第一種咨詢項目類型中的客戶，第二階段決策將處理多少個第二種咨詢項目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們設(shè)

sk＝分配給第k種咨詢項目到第四種咨詢項目的所有客戶的總工作日（第k階段的狀態(tài)變量）。

xk=在第k種咨詢項目中處理客戶的數(shù)量（第k階段的決策變量）。已知s1＝10并有2022/12/1831解：用動態(tài)規(guī)劃來求解此題。2023/1/290從第四階段開始計算：顯然將s4個工作日s4=(0,1,2……,10)盡可能分配給第四類咨詢項目，即x4=[s4/7]時，第四階段的指標(biāo)值為最大，其中[s4/7]表示取不大于[s4/7]的最大整數(shù)，符號[]為取整符號，故有由于第四階段是最后的階段，故有2022/12/1832從第四階段開始計算：2023/1/291因為s4至多為10，其數(shù)值計算見表

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

20

12022/12/1833因為s4至多為10，其數(shù)值計算見表2023/1/292第三階段：當(dāng)把s3=(0,1,2……,10)個工作日分配給第四類和第三類咨詢項目時，則對每個s3值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標(biāo)函數(shù)值為

因為因為s3

至多為10，所以x3的取值可為0,1,2。其數(shù)值計算見表10－11。2022/12/1834第三階段：2023/1/293

012

0－－

0

01

－－

0

02－－

0

03－－

0

04

0＋0－

1115

0＋0－

1116

0＋0－

1117

11+0－2008

0＋20

11+0

2229

0＋20

11+0

22210

0＋20

11+0

2222022/12/183502023/1/294第二階段：同樣以每個s2值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為：因為，故有因為s2至多為10，所以x2的取值為0,1,2,3。2022/12/1836第二階段：2023/1/2952022/12/18372023/1/296

第一階段：我們已知，又因為，同樣有

因為,故可取值為0,1,2,…,10。2022/12/1838第一階段：2023/1/297可知f1(10)=28，x*1=0從而得s2=s1-x*1＝10－0＝10s2=10的這一行可知x*2=1，由s3=s2-3x*1＝7s3=7的這一行可知x*3=0，最后由s4=s3-x*3＝7s4=7這一行得x*4=1綜上所述得最優(yōu)解為：x*1=0,x*2=1，x*3=0，x*4=1,最大盈利為28?，F(xiàn)在我們不妨假設(shè)該咨詢公司的工作計劃有所改變，只有8個工作日來處理這四類咨詢項目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開始重做這個問題，而只要在第一階段上把s1改成8，重新計算就可得到結(jié)果，這是動態(tài)規(guī)劃的一個好處。2022/12/1839可知f1(10)=28，x*1=0從2023/1/298

得到兩組最優(yōu)解如下：

它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計算第一階段，而且要在第二、第三、第四階段的計算表上補上增加的工作日的新的信息，也可得到新的結(jié)果。2022/12/18402023