第六章動(dòng)態(tài)規(guī)劃課件

第六章動(dòng)態(tài)規(guī)劃§1問題的提出§2基本概念、基本方程與最優(yōu)化原理§3動(dòng)態(tài)規(guī)劃的應(yīng)用1精選課件ppt§1問題的提出一、引例——最短路徑問題

下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最短路徑。BACBDBCDEC4123123123221647248386756110637512精選課件ppt§1問題的提出用窮舉法的計(jì)算量，非常大。討論：1、以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di、Ci、Bi、A到E的最短路徑問題。

第四階段：兩個(gè)始點(diǎn)D1和D2，終點(diǎn)只有一個(gè)；

表6-1分析得知：從D1和D2到E的最短路徑唯一。階段4本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)ED1D210*6106EE3精選課件ppt

第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2的最短路徑問題：

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

§1問題的提出階段3本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D14精選課件ppt第二階段：有4個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3的最短路徑問題：

表6-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。

§1問題的提出階段2本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(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=1212131412C2C3C3C35精選課件ppt

第一階段：只有1個(gè)始點(diǎn)A，終點(diǎn)有B1,B2,B3,B4。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

表6-4最后，可以得到：從A到E的最短路徑為A

B4

C3

D1

E§1問題的提出階段1本階段始點(diǎn)(狀態(tài))本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1412C26精選課件ppt

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

以上過程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1問題的提出7精選課件ppt§1問題的提出從引例的求解過程中可以得到以下啟示：（1）對(duì)一個(gè)問題是否用上述方法求解，其關(guān)鍵在與能否將問題轉(zhuǎn)化為相互聯(lián)系的多個(gè)階段的決策問題。（2）對(duì)問題的求解是從全局考慮解決局部（階段）的問題。（3）各階段選取的決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，整個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來，故有“動(dòng)態(tài)”含義。（4）決策過程是與階段發(fā)展過程逆向而行。8精選課件ppt§1問題的提出二、動(dòng)態(tài)規(guī)劃的含義及適用范圍1.動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是解決一類多階段決策問題的優(yōu)化方法，它是考察問題的一種途徑，而不是一種算法。

多階段決策問題：把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程，也稱為序貫決策過程。

2.適用范圍

如果一個(gè)問題可將其過程劃分為若干個(gè)相互聯(lián)系的階段問題，且它的每一階段都需要進(jìn)行決策，則這類問題均可用動(dòng)態(tài)規(guī)劃方法進(jìn)行求解。

9精選課件ppt一、基本概念

1.階段和階段變量用動(dòng)態(tài)規(guī)劃方法求解問題時(shí)，首先將問題的全過程適當(dāng)?shù)胤殖扇舾蓚€(gè)互相聯(lián)系的階段，以便能按一定的次序去求解。階段的劃分，一般根據(jù)時(shí)序和空間的自然特征來劃分。如引例可按照空間劃分為4個(gè)階段。

階段變量：描述階段的變量稱為階段變量。用k表示，引例中，k=1,2,3,4.

2.狀態(tài)和狀態(tài)變量sk

狀態(tài)就是階段的起始位置。它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

§2基本概念、基本方程與最優(yōu)化原理10精選課件ppt§2基本概念、基本方程與最優(yōu)化原理

狀態(tài)變量：描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個(gè)數(shù)、一組數(shù)或一向量（多維情形）來描述，常用sk第k階段的狀態(tài)變量。通常一個(gè)階段有若干個(gè)狀態(tài)。第k階段的狀態(tài)就是該階段所有始點(diǎn)的集合。3.決策與決策變量決策：在某階段對(duì)可供選擇狀態(tài)的決定（或選擇）。決策變量：描述決策的變量。常用xk(sk)表示第k階段處于狀態(tài)sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。4.策略與子策略

策略是一個(gè)決策序列的集合。由所有各階段的決策組成的決策函數(shù)序列稱為全過程策略，簡稱策略，記為：P1,n(s1)。

子策略：從第k個(gè)階段開始到最后階段的決策組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為：Pk,n(sk)

最優(yōu)策略：能夠達(dá)到總體最優(yōu)的策略。11精選課件ppt§2基本概念、基本方程與最優(yōu)化原理5.狀態(tài)轉(zhuǎn)移方程

它是確定過程由某一階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)的演變過程，用sk+1=Tk(sk,xk)表示。該方程描述了第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。因此又稱為狀態(tài)轉(zhuǎn)移函數(shù)。6.階段指標(biāo)函數(shù)rk(sk,xk)

從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)。7.最優(yōu)指標(biāo)函數(shù)fk(sk)表示從第k階段的狀態(tài)sk開始采用最優(yōu)子策略，到第n階段的終止時(shí)所得到的最優(yōu)指標(biāo)函數(shù)值。

12精選課件ppt二、基本方程最優(yōu)指標(biāo)的遞推方程（動(dòng)態(tài)規(guī)劃的基本方程）：

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

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

終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)=0?！?基本概念、基本方程與最優(yōu)化原理13精選課件ppt三、最優(yōu)化原理

作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的?！?基本概念、基本方程與最優(yōu)化原理14精選課件ppt§2基本概念、基本方程與最優(yōu)化原理四、動(dòng)態(tài)規(guī)劃求解過程

（1）將問題的過程劃分成恰當(dāng)?shù)碾A段；（2）正確選擇狀態(tài)變量sk，使它能夠恰當(dāng)?shù)孛枋鲞^程的演變；（3）確定決策變量xk；（4）正確寫出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)；（5）寫出最優(yōu)指標(biāo)的遞推方程：

fn+1(sn+1)=0終點(diǎn)條件15精選課件ppt一、資源分配問題

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

表8-5盈利工廠設(shè)備臺(tái)數(shù)甲廠乙廠丙廠000013542710639111141211125131112§3動(dòng)態(tài)規(guī)劃的應(yīng)用16精選課件ppt解：（1）劃分階段：將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號(hào)為1、2、3廠。

（2）確定狀態(tài)變量：設(shè)sk=分配給第k個(gè)廠至第3個(gè)廠的設(shè)備臺(tái)數(shù)（k=1、2、3）。

（3）確定決策變量：設(shè)xk=分配給第k個(gè)設(shè)備臺(tái)數(shù)。

（4）寫出狀態(tài)轉(zhuǎn)移方程。已知s1=5,并有§3動(dòng)態(tài)規(guī)劃的應(yīng)用17精選課件ppt第三階段:

表6－6

01234500－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－－12125§3動(dòng)態(tài)規(guī)劃的應(yīng)用18精選課件ppt第二階段：

表6－7

0123450－－－－－0010＋4

－－－－5120＋65＋4－－－10230＋115＋611＋0－－14240＋1211＋411＋0－161,250＋125＋1211＋611＋411＋0212§3動(dòng)態(tài)規(guī)劃的應(yīng)用19精選課件ppt

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

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

0123455

3＋169+1012+513+0210,2§3動(dòng)態(tài)規(guī)劃的應(yīng)用20精選課件ppt知，再由,求得，即分配給甲廠2臺(tái)，乙廠2臺(tái)，丙廠1臺(tái)。這兩種分配方案都能得到最高的總盈利21萬元。

§3動(dòng)態(tài)規(guī)劃的應(yīng)用21精選課件ppt二、背包問題

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

0

且為整數(shù)?！?動(dòng)態(tài)規(guī)劃的應(yīng)用22精選課件ppt下面用動(dòng)態(tài)規(guī)劃逆序解法求解它。設(shè)（1）階段變量k：第k次裝載第k種物品（k=1,2,…,n）（2）狀態(tài)變量sk：第k次裝載時(shí)背包還可以裝載的重量；（3）決策變量uk=xk：第k次裝載第k種物品的件數(shù)；（4）狀態(tài)轉(zhuǎn)移方程：sk+1=sk

wkxk；（5）最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價(jià)值；階段指標(biāo)：rk=ckxk；遞推方程：

fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk

wkxk)}；x

Dk(sk)終端條件：

fn+1(sn+1)=0。§3動(dòng)態(tài)規(guī)劃的應(yīng)用23精選課件ppt

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

咨詢項(xiàng)目類型待處理客戶數(shù)處理每個(gè)客戶所需工作日數(shù)處理每個(gè)客戶所獲利潤123443221347281120§3動(dòng)態(tài)規(guī)劃的應(yīng)用24精選課件ppt

解：用動(dòng)態(tài)規(guī)劃來求解此題。

（1）把此問題分成四個(gè)階段，第一階段我們決策將處理多少個(gè)第一種咨詢項(xiàng)目類型中的客戶，第二階段決策將處理多少個(gè)第二種咨詢項(xiàng)目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。

（2）設(shè)狀態(tài)變量

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

（3）設(shè)決策變量

=在第k種咨詢項(xiàng)目中處理客戶的數(shù)量（第k階3段的決策變量）。

（4）寫出狀態(tài)轉(zhuǎn)移方程已知＝10，并有

§3動(dòng)態(tài)規(guī)劃的應(yīng)用25精選課件ppt

并從與的定義可知

從第四階段開始計(jì)算：顯然將個(gè)工作日盡可能分配給第四類咨詢項(xiàng)目，即時(shí)，第四階段的指標(biāo)值為最大，其中，表示取不大于的最大整數(shù)，符號(hào)為取整符號(hào)，故有由于第四階段是最后的階段，故有§3動(dòng)態(tài)規(guī)劃的應(yīng)用26精選課件ppt

因?yàn)橹炼酁?0，其數(shù)值計(jì)算見表6－10。

表6－10

010－001－002－003－004－005－006－0070201802019020110011§3動(dòng)態(tài)規(guī)劃的應(yīng)用27精選課件ppt

第三階段：當(dāng)把個(gè)工作日分配給第四類和第三類咨詢項(xiàng)目時(shí)，則對(duì)每個(gè)值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標(biāo)函數(shù)值為

因?yàn)橐驗(yàn)橹炼酁?0，所以的取值可為0,1,2。其數(shù)值計(jì)算見表6－11。§3動(dòng)態(tài)規(guī)劃的應(yīng)用28精選課件ppt

表6－11

0120－－001－－002－－003－－0040＋0－11150＋0－11160＋0－111711+0－20080＋2011+022290＋2011+0222100＋2011+0222§3動(dòng)態(tài)規(guī)劃的應(yīng)用29精選課件ppt

第二階段：同樣以每個(gè)值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為：因?yàn)椋视幸驗(yàn)橹炼酁?0，所以的取值為0,1,2,3。其數(shù)值計(jì)算見表6－12。§3動(dòng)態(tài)規(guī)劃的應(yīng)用30精選課件ppt§3動(dòng)態(tài)規(guī)劃的應(yīng)用表6-1231精選課件ppt

第一階段：我們已知，又因?yàn)?，同樣?/p>

因?yàn)?故可取值為0,1,2,…,10。其數(shù)值計(jì)算見表6－13。表6－13§3動(dòng)態(tài)規(guī)劃的應(yīng)用32精選課件ppt從表6－13可知，從而得＝10－0＝10，在表6－12的的這一行可知，由，查表6－11的的這一行可知，最后由，查表6-10的的這一行得，綜上所述得最優(yōu)解為：此時(shí)最大盈利為28?，F(xiàn)在我們不妨假設(shè)該咨詢公司的工作計(jì)劃有所改變，只有8個(gè)工作日來處理這四類咨詢項(xiàng)目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開始重做這個(gè)問題，而只要在第一階段上把改成8，重新計(jì)算就可得到結(jié)果，如表6－14所示，這是動(dòng)態(tài)規(guī)劃的一個(gè)好處。

§3動(dòng)態(tài)規(guī)劃的應(yīng)用33精選課件ppt

表6－14

如上一樣可從表6－14,6－12,6－11,6－10得到兩組最優(yōu)解如下：

它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計(jì)算第一階段，而且要在第二、第三、第四階段的計(jì)算表上補(bǔ)上增加的工作日的新的信息，也可得到新的結(jié)果?！?動(dòng)態(tài)規(guī)劃的應(yīng)用34精選課件ppt

實(shí)際上，背包問題我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為W公斤，這N種物品中第i種物品的重量為，價(jià)值為，第i種物品的總數(shù)量的，我們可以設(shè)表示攜帶第i種物品的數(shù)量，則其數(shù)學(xué)模型為：S.T.且為整數(shù)。

我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果。§3動(dòng)態(tài)規(guī)劃的應(yīng)用35精選課件ppt三、生產(chǎn)與存貯問題例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購買，所以該公司可以預(yù)測未來幾個(gè)月的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)生產(chǎn)計(jì)劃，這四個(gè)月的需求如表6－15所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費(fèi)為4，除了調(diào)度費(fèi)用外，每月生產(chǎn)的頭兩臺(tái)各花費(fèi)為2，后兩臺(tái)花費(fèi)為1。最大生產(chǎn)能力每月為4臺(tái)，生產(chǎn)成本如表6－16所示。

表6－15

§3動(dòng)態(tài)規(guī)劃的應(yīng)用36精選課件ppt

表6－16

每臺(tái)變壓器在倉庫中由這個(gè)月存到下個(gè)月的儲(chǔ)存費(fèi)為1，倉庫的最大儲(chǔ)存能力為3臺(tái)，另外，知道在1月1日時(shí)倉庫里存有一臺(tái)變壓器，要求在4月30日倉庫的庫存量為零。試問該公司應(yīng)如何制定生產(chǎn)計(jì)劃，使得四個(gè)月的生產(chǎn)成本和儲(chǔ)存總費(fèi)用最少？解：（1）我們按月份來劃分階段，第i個(gè)月為第i階段：（i=1,2,3,4).（2）設(shè)為第k階段期初庫存量；k=1,2,3,4

§3動(dòng)態(tài)規(guī)劃的應(yīng)用37精選課件ppt

（3）為第k階段生產(chǎn)量；k=1,2,3,4為第k階段需求量；k=1,2,3,4，這已在表10-15中告訴我們。（4）寫出狀態(tài)轉(zhuǎn)移方程

因?yàn)橄聜€(gè)月的庫存量等于上個(gè)月的庫存量加上上個(gè)月的產(chǎn)量減去上個(gè)月的需求量，我們就得到了如下狀態(tài)轉(zhuǎn)移方程：因?yàn)椋视?/p>

因?yàn)?，故?/p>

§3動(dòng)態(tài)規(guī)劃的應(yīng)用38精選課件ppt

由于必須要滿足需求，則有

通過移項(xiàng)得到

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

以下我們從第四階段開始計(jì)算：從以上的狀態(tài)轉(zhuǎn)移方程可知這樣就有

§3動(dòng)態(tài)規(guī)劃的應(yīng)用39精選課件ppt

這里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與儲(chǔ)存費(fèi)，即為由于第四階段末要求庫存為零，即有，這樣可得對(duì)于每個(gè)的可行值，的值列于表6－17。

表6－17§3動(dòng)態(tài)規(guī)劃的應(yīng)用40精選課件ppt

表中當(dāng)時(shí)，可知第四階段要生產(chǎn)臺(tái)，從表6－16可知總成本為9，同樣可以算出當(dāng)為1,2,3時(shí)的情況，結(jié)果已列于表6－17中。第三階段：此時(shí)有：因?yàn)?/p>

以及

所以有例如，當(dāng)?shù)谌A段初庫存量時(shí)，生產(chǎn)量為2時(shí)，則