第六講動態(tài)規(guī)劃上

第六講動態(tài)規(guī)劃上第1頁，共47頁，2023年，2月20日，星期一第一節(jié)多階段決策過程的最優(yōu)化

美國數(shù)學(xué)家貝爾曼(R.Bellman)50年代執(zhí)教于普林斯頓和斯坦福大學(xué)，后進(jìn)入蘭德（Rand）研究所。1957年發(fā)表“DynamicProgramming”一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。

第2頁，共47頁，2023年，2月20日，星期一最短路問題給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總費(fèi)用最小）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第3頁，共47頁，2023年，2月20日，星期一2、每個(gè)階段都要進(jìn)行決策,目的是使整個(gè)過程的決策達(dá)到最優(yōu)效果。多階段決策問題：1、在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時(shí)間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段；第4頁，共47頁，2023年，2月20日，星期一12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策第5頁，共47頁，2023年，2月20日，星期一多階段決策問題的典型例子第6頁，共47頁，2023年，2月20日，星期一給定一個(gè)線路網(wǎng)絡(luò)圖，要從A地向F地鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距離最短?第7頁，共47頁，2023年，2月20日，星期一資源分配問題

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

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

0

0

0

0

1

3

5

4

2

7

10

6

3

9

11

11

4

12

11

12

5

13

11

12第8頁，共47頁，2023年，2月20日，星期一機(jī)器負(fù)荷分配問題

某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)

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

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

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

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

第9頁，共47頁，2023年，2月20日，星期一設(shè)備更新問題

企業(yè)在使用設(shè)備時(shí)都要考慮設(shè)備的更新問題，因?yàn)樵O(shè)備越陳舊所需的維修費(fèi)用越多，但購買新設(shè)備則要一次性支出較大的費(fèi)用?，F(xiàn)某企業(yè)要決定一臺設(shè)備未來8年的更新計(jì)劃，已預(yù)測了第j年購買設(shè)備的價(jià)格為Kj，設(shè)Gj為設(shè)備經(jīng)過j年后的殘值，Cj為設(shè)備連續(xù)使用j-1年后在第j年的維修費(fèi)(j＝1，2，…，8)，問應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最小。這是一個(gè)8階段決策問題，每年年初要作出決策，是繼續(xù)使用舊設(shè)備，還是購買新設(shè)備。第10頁，共47頁，2023年，2月20日，星期一第二節(jié)動態(tài)規(guī)劃的基本概念和基本原理

一、動態(tài)規(guī)劃的基本概念使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動態(tài)規(guī)劃模型，此時(shí)要用到以下概念：(1)階段；(2)狀態(tài)；(3)決策和策略；

(4)狀態(tài)轉(zhuǎn)移；(5)指標(biāo)函數(shù)。

第11頁，共47頁，2023年，2月20日，星期一要便于把問題的過程轉(zhuǎn)化為多階段決策的過程。

1.

階段、階段變量

把所給問題的過程，適當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便按次序去求每階段的解;

描述階段的變量稱為階段變量，常用k表示；

階段的劃分，一般是按時(shí)間和空間的自然特征（年、月、路段）來劃分；第12頁，共47頁，2023年，2月20日，星期一

例中，從A到F可以分成從A到B(B有兩種選擇B1,B2)，從B到C(C有四種選擇C1，C2，C3，C4)，從C到D(D有三種選擇D1，D2,D3)，從D到E(E有兩種選擇E1，E2)，再從E到F五個(gè)階段。k＝1，2，3，4，5。第13頁，共47頁，2023年，2月20日，星期一

狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合，用Sk表示。2.狀態(tài)、狀態(tài)變量

每個(gè)階段開始所處的自然狀態(tài)或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)。

描述過程狀態(tài)的變量稱為狀態(tài)變量，常用sk（一個(gè)數(shù)、一組數(shù)、一個(gè)向量）表示第k階段的狀態(tài)。第14頁，共47頁，2023年，2月20日，星期一

在例5中，第一階段狀態(tài)為A，第二階段則有二個(gè)狀態(tài)：Bl，B2。狀態(tài)變量s1的集合，后面各段的狀態(tài)集合分別是：

第15頁，共47頁，2023年，2月20日，星期一

動態(tài)規(guī)劃中的狀態(tài)應(yīng)具有如下性質(zhì)：當(dāng)某階段狀態(tài)給定以后，在這階段以后過程的發(fā)展不受這段以前各段狀態(tài)的影響。也就是說，當(dāng)前的狀態(tài)是過去歷史的一個(gè)完整總結(jié)，過程的過去歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展，這稱為無后效性。如果所選定的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃模型。

例5

中，當(dāng)某段的初始狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的鋪管路線只與該點(diǎn)有關(guān)，不受以前的鋪管路線影響，所以滿足狀態(tài)的無后效性。

第16頁，共47頁，2023年，2月20日，星期一

在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有決策變量是狀態(tài)變量的函數(shù)。3.

決策、決策變量

過程的某一階段、某個(gè)狀態(tài),可以做出不同的決定(選擇),決定下一階段的狀態(tài)，這種決定稱為決策。uk(sk)Dk(sk)

描述決策的變量，稱為決策變量。常用表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。第17頁，共47頁，2023年，2月20日，星期一在例5中，從第二階段的狀態(tài)B1出發(fā)，可選擇下一段的C1，C2，C3，即其允許決策集合為：

我們決定選擇C3，則可表為：

uk(sk)Dk(sk)第18頁，共47頁，2023年，2月20日，星期一

由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為pk,n(sk)，即

當(dāng)k=1時(shí)，此決策函數(shù)序列成為全過程的一個(gè)策略，簡稱策略，記為p1,n

(s1)即：4.

策略按順序排列的決策組成的集合；

可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用

表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。

由第k

n(終止?fàn)顟B(tài))為止的過程，稱為問題的后部子過程（k子過程）第19頁，共47頁，2023年，2月20日，星期一

費(fèi)用、成本、利潤、路長等。用

Vk,n

表示之。5.

指標(biāo)函數(shù)和最優(yōu)值函數(shù)

用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)；它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。

一個(gè)n段決策過程，從l到n叫作問題的原過程，對于任意一個(gè)給定的k(1≤k≤n)，從第k段到第n段的過程稱為原過程的一個(gè)后部子過程。表示在第k段，狀態(tài)為sk采用策略，后部子過程的指標(biāo)函數(shù)值。表示初始狀態(tài)為s1采用策略時(shí)原過程的指標(biāo)函數(shù)值，而

第20頁，共47頁，2023年，2月20日，星期一最優(yōu)指標(biāo)函數(shù)記為，它表示從第k段狀態(tài)sk采用最優(yōu)策略到過程終止時(shí)的最佳效益值。與間的關(guān)系為：

opt全稱optimum，表示最優(yōu)化，根據(jù)具體問題分別表為max或min。當(dāng)k＝1時(shí)，就是從初始狀態(tài)s1到全過程結(jié)束的整體最優(yōu)函數(shù)。

在例5中，指標(biāo)函數(shù)是距離。如第2階段，狀態(tài)為B1時(shí)，表示從B1到F的距離，而則表示從B1到F的最短距離。本問題的總目標(biāo)是求，即從A到終點(diǎn)F的最短距離。

第21頁，共47頁，2023年，2月20日，星期一二、動態(tài)規(guī)劃的基本思想與基本原理下面結(jié)合例5最短路線問題介紹動態(tài)規(guī)劃的基本思想。

第22頁，共47頁，2023年，2月20日，星期一

為了求出最短路線，一種簡單的方法，可以求出所有從A至F的可能鋪設(shè)的路長并加以比較。不難知道從A至F共有24條不同路徑，要求出最短路線需要做23次比較運(yùn)算，這種方法稱窮舉法。

當(dāng)問題的段數(shù)很多、各段的狀態(tài)也很多時(shí)，窮舉法的計(jì)算量會大大增加，甚至使得求優(yōu)成為不可能。下面介紹動態(tài)規(guī)劃方法。注意本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)F的最短路線，最后求得A點(diǎn)到F點(diǎn)的最短路線。

第23頁，共47頁，2023年，2月20日，星期一用表示由狀態(tài)sk點(diǎn)出發(fā)，采用決策uk到達(dá)下一階段sk+1點(diǎn)時(shí)的兩點(diǎn)距離。

第一步，從k＝5開始，狀態(tài)變量s5可取兩種狀態(tài)E1，E2，它們到F點(diǎn)的路長分別為4，3。

即：

第二步，k＝4，狀態(tài)變量s4可取三個(gè)值D1，D2，D3，這是經(jīng)過一個(gè)中途點(diǎn)到達(dá)終點(diǎn)F的兩級決策問題，從D1到F有兩條路線，需加以比較，取其中最短的，即：

第24頁，共47頁，2023年，2月20日，星期一由D1到終點(diǎn)F最短距離為7，其路徑為D1→E1→F。相應(yīng)決策為即D2到終點(diǎn)最短距離為5，其路徑為D2→E2→F。相應(yīng)決策為

即D3到終點(diǎn)最短距離為5，其路徑為D3→E1→F。相應(yīng)決策為

第25頁，共47頁，2023年，2月20日，星期一類似的，可算得：k=3時(shí)，有

k=2時(shí)，有

k=1時(shí)，則

第26頁，共47頁，2023年，2月20日，星期一所以最優(yōu)路線為：

即從A到F的最短距離為17。本段決策為

再按計(jì)算順序反推可得最優(yōu)決策序列即

第27頁，共47頁，2023年，2月20日，星期一這種遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程，(7.3b))式稱為邊界條件。從例5的計(jì)算過程中可以看出，在求解的各階段，都利用了第k段和第k+1段的如下關(guān)系：第28頁，共47頁，2023年，2月20日，星期一上述最短路線的計(jì)算過程也可用圖直觀表示出來，如圖7-2，每個(gè)結(jié)點(diǎn)上方的括號內(nèi)的數(shù)，表示該點(diǎn)到終點(diǎn)F的最短距離。連結(jié)各點(diǎn)到F點(diǎn)的線表示最短路徑。這種在圖上直接計(jì)算的方法叫標(biāo)號法。第29頁，共47頁，2023年，2月20日，星期一第三節(jié)動態(tài)規(guī)劃模型的建立與求解

一、動態(tài)規(guī)劃模型的建立

建立動態(tài)規(guī)劃的模型，就是分析問題并建立問題的動態(tài)規(guī)劃基本方程。

應(yīng)用動態(tài)規(guī)劃方法的關(guān)鍵在于:識別問題的多階段特征，將問題分解成為可用遞推關(guān)系式聯(lián)系起來的若干子問題，而正確建立基本遞推關(guān)系方程的關(guān)鍵又在于正確選擇狀態(tài)變量，保證各階段的狀態(tài)變量具有遞推的狀態(tài)轉(zhuǎn)移關(guān)系。第30頁，共47頁，2023年，2月20日，星期一

下面以資源分配問題為例介紹動態(tài)規(guī)劃的建模條件及解法。資源分配問題是動態(tài)規(guī)劃的典型應(yīng)用之一，資源可以是資金、原材料、設(shè)備、勞力等，資源分配就是將一定數(shù)量的一種或幾種資源恰當(dāng)?shù)胤峙浣o若干使用者，以獲取最大效益。

第31頁，共47頁，2023年，2月20日，星期一資源分配問題

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

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

0

0

0

0

1

3

5

4

2

7

10

6

3

9

11

11

4

12

11

12

5

13

11

12第32頁，共47頁，2023年，2月20日，星期一解：將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號為1、2、3廠。設(shè)sk=分配給第k個(gè)廠至第3個(gè)廠的設(shè)備臺數(shù)（k=1、2、3）

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

并有

第33頁，共47頁，2023年，2月20日，星期一第三階段:

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

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

第34頁，共47頁，2023年，2月20日，星期一

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－12125第35頁，共47頁，2023年，2月20日，星期一其中表示取3子過程上最優(yōu)指標(biāo)值時(shí)的決策，例如在表可知當(dāng)=4時(shí)，有有此時(shí)，即當(dāng)時(shí)，此時(shí)?。ò?臺設(shè)備分配給第3廠）是最優(yōu)決策，此時(shí)階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。第二階段：

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

第36頁，共47頁，2023年，2月20日，星期一因?yàn)樯鲜揭部蓪懗善鋽?shù)值計(jì)算如表所示。

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

212第37頁，共47頁，2023年，2月20日，星期一其中在的這一行里，當(dāng)時(shí)，這里從表10－5中可知，把1臺設(shè)備交給乙廠所得盈利數(shù)即可，知，這里從表10－6查即可知=11。同樣可知當(dāng)時(shí)，可知

;當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)，；由于，不可能分2廠5臺設(shè)備，故時(shí)，欄空著不填。從這些數(shù)值中取得最大即得，即有=16。在此行中我們在取最大值的上面加一橫以示區(qū)別，也可知這時(shí)的最優(yōu)決策為1或2。第38頁，共47頁，2023年，2月20日，星期一

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

然后按計(jì)算表格的順序推算，可知最優(yōu)分配方案有兩個(gè)：

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

2.由于，根據(jù)，查表可

0

1