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

1、第七章 動態(tài)規(guī)劃1多階段決策過程最優(yōu)化問題舉例2基本概念、基本方程與最優(yōu)化原理3動態(tài)規(guī)劃的應(yīng)用(1)4動態(tài)規(guī)劃的應(yīng)用(2)第1頁，共28頁。11多階段決策過程最優(yōu)化問題舉例例1 最短路徑問題 下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC412312312322164724838675611063751第2頁，共28頁。2一、基本概念： 1、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。 2、狀態(tài)sk：能確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做

2、的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。 決策允許集合Dk(sk)：在狀態(tài)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)系。2基本概念、基本方程與最優(yōu)化原理第3頁，共28頁。3 6、階段指標(biāo)函數(shù)vk(sk, xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)。 過程指標(biāo)函數(shù)Vk,n(sk, xk, xk+1, xn)：從狀態(tài)sk出發(fā)，選擇決策xk, xk+1, , xn所產(chǎn)生的過程指標(biāo)。

3、動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)稱指標(biāo)具有可乘性。二、基本方程： 最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標(biāo)Vk,n的最優(yōu)值，即 2基本概念、基本方程與最優(yōu)化原理第4頁，共28頁。4 對于可加性指標(biāo)函數(shù)，上式可以寫為 上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為 以上式子

4、稱為動態(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。2基本概念、基本方程與最優(yōu)化原理第5頁，共28頁。5三、最優(yōu)化原理 作為整個過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。2基本概念、基本方程與最優(yōu)化原理第6頁，共28頁。6一、資源分配問題 例2. 某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造

5、的利潤如表所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？ 表10-5 盈利 工廠設(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 123 動態(tài)規(guī)劃的應(yīng)用(1)第7頁，共28頁。7二、背包問題 設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi公斤，每件價值ci元?，F(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。 這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i =1, 2, , n），背包中物品的總價值為z，則

6、 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且為整數(shù)。3 動態(tài)規(guī)劃的應(yīng)用(1)第8頁，共28頁。8 下面用動態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1, 2, , n）狀態(tài)變量sk：第k次裝載時背包還可以裝載的重量；決策變量uk = xk：第k次裝載第k種物品的件數(shù)；決策允許集合：Dk(sk) = xk | 0 xksk/wk，xk為整數(shù)；狀態(tài)轉(zhuǎn)移方程： sk+1 = sk wkxk；階段指標(biāo)： vk = ckxk；最優(yōu)過程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價值；遞推方程：

7、 fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 終端條件： fn+1(sn+1) = 0。3 動態(tài)規(guī)劃的應(yīng)用(1)第9頁，共28頁。9例3.某咨詢公司有10個工作日可以去處理四種類型的咨詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個客戶所需工作日數(shù)以及所獲得的利潤如表所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個工作日中獲利最大？ 咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤123443221347281

8、1203 動態(tài)規(guī)劃的應(yīng)用(1)第10頁，共28頁。10 實際上，背包問題我們也可以用整數(shù)規(guī)劃來求解，如果背包攜帶物品重量的限制為W公斤，這N種物品中第i種物品的重量為，價值為，第i種物品的總數(shù)量的，我們可以設(shè)表示攜帶第i種物品的數(shù)量，則其數(shù)學(xué)模型為：S.T. 且為整數(shù)。 我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果。3動態(tài)規(guī)劃的應(yīng)用(1) 第11頁，共28頁。11三、生產(chǎn)與存貯問題 例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購買，所以該公司可以預(yù)測未來幾個月的需求量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn)計劃，這四個月的需求如表1所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變

9、化。調(diào)試費為4，除了調(diào)度費用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺花費為1。最大生產(chǎn)能力每月為4臺，生產(chǎn)成本如表2所示。表13動態(tài)規(guī)劃的應(yīng)用(1) 第12頁，共28頁。12 表2每臺變壓器在倉庫中由這個月存到下個月的儲存費為1，倉庫的最大儲存能力為3臺，另外，知道在1月1日時倉庫里存有一臺變壓器，要求在4月30日倉庫的庫存量為零。試問該公司應(yīng)如何制定生產(chǎn)計劃，使得四個月的生產(chǎn)成本和儲存總費用最少？3動態(tài)規(guī)劃的應(yīng)用(1) 第13頁，共28頁。133動態(tài)規(guī)劃的應(yīng)用(1) 四、系統(tǒng)可靠性問題 例5.某科研項目組由三個小組用不同的手段順序研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三

10、個小組都失敗的可能性，現(xiàn)決定給三個小組中增派兩名高級科學(xué)家，到各小組后，各小組科研項目失敗概率如下表： 問如何分派科學(xué)家才能使三個小組都失敗的概率（即科研項目最終失敗的概率）最?。?高級科學(xué)家小組12300.400.600.8010.200.400.5020.150.200.30第14頁，共28頁。144動態(tài)規(guī)劃的應(yīng)用(2)一、連續(xù)確定性動態(tài)規(guī)劃 對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時，這種動態(tài)規(guī)劃問題就稱為連續(xù)確定性動態(tài)規(guī)劃問題。第15頁，共28頁。154動態(tài)規(guī)劃的應(yīng)用(2)機(jī)器負(fù)荷分配問題 例1 一種機(jī)器能在高低兩種不同的負(fù)荷狀態(tài)下工作。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)時，產(chǎn)量函數(shù)

11、為P1=8u1，其中u1為在高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為a=0.7，即到年底有70的機(jī)器保持完好。在低負(fù)荷下生產(chǎn)時，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為b=0.9。設(shè)開始生產(chǎn)時共有1000臺完好的機(jī)器，請問每年應(yīng)該如何把完好機(jī)器分配給高、低兩種負(fù)荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。第16頁，共28頁。164動態(tài)規(guī)劃的應(yīng)用(2)*解 建立動態(tài)規(guī)劃模型： 分為5個階段，每個階段為1年。設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機(jī)器數(shù)目；k=1,2,3,4,5。 決策變量xk表示第k階段中分配給高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目；k=1,2,3,4,5

12、。顯然sk-xk為分配給低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目。 狀態(tài)轉(zhuǎn)移方程為 sk+1=0.7xk+0.9(sk-xk) 階段指標(biāo) rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)指標(biāo)函數(shù) ，其中k=1,2,3,4,5。 f6(s6)=0。第17頁，共28頁。174動態(tài)規(guī)劃的應(yīng)用(2)*第5階段： 因為f5(s5)是x5的線性單調(diào)增函數(shù)，故有x5* =s5，于是有f5(s5)=8s5。第4階段： 第18頁，共28頁。184動態(tài)規(guī)劃的應(yīng)用(2)* 同樣的，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4 ，f4(s4)=13.6s4。 對前幾個階段依次類推，可得 f3(s3)=17.5s3， f2(

13、s2)=20.75s2， f1(s1)=23.72s1。 因為期初共有完好機(jī)器1000臺，故s1=1000。有f1(s1)=23.72s123720，即5年最大的產(chǎn)量為23720臺。得最優(yōu)解為 ， ， ， 。 這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷生產(chǎn)。第19頁，共28頁。194動態(tài)規(guī)劃的應(yīng)用(2)* 下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計算出每年年初完好的機(jī)器數(shù)目。已知s1=1000,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:第20頁，共28頁。204動態(tài)規(guī)劃的應(yīng)用(2) 上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點狀態(tài)s6沒

14、有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點自由的最優(yōu)策略。 如果終點附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結(jié)束時仍要保持500臺機(jī)器完好（而不是278臺），應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大？ 下面來分析： 根據(jù)終點條件有 可得第21頁，共28頁。214動態(tài)規(guī)劃的應(yīng)用(2)* 顯然，由于固定了終點的狀態(tài)，x5的取值受到了約束。因此有 類似的， 容易解得 ，f4(s4)=21.7s4-7500。第22頁，共28頁。224動態(tài)規(guī)劃的應(yīng)用(2)* 依次類推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-75

15、00 再采用順序方法遞推計算各年的狀態(tài)，有 s1=1000， 第23頁，共28頁。234動態(tài)規(guī)劃的應(yīng)用(2) 可見，為了使終點完好的機(jī)器數(shù)量增加到500臺，需要安排前四年中全部完好機(jī)器都要投入低負(fù)荷生產(chǎn)，且在第5年，也只能全部投入高負(fù)荷。 相應(yīng)的最優(yōu)指標(biāo)為 f1(s1)=29.4s1-750021900。 可以看到，因為增加了附加條件，總產(chǎn)量f1(s1)要比終點自由情況下的產(chǎn)量要低。第24頁，共28頁。24二、離散隨機(jī)性動態(tài)規(guī)劃 隨機(jī)型的動態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(tài)和決策，下一階段的到達(dá)狀態(tài)是具有確定概率分布的隨機(jī)變量，這個概率分布由本階段的狀態(tài)和決策完全確定。隨機(jī)型動態(tài)

16、規(guī)劃的基本結(jié)構(gòu)如下圖： 4動態(tài)規(guī)劃的應(yīng)用(2) sk狀態(tài) xk決策概率k階段的收益p1p2pN.k+1階段的狀態(tài)sk+1c1c2cN 1 2N第25頁，共28頁。254動態(tài)規(guī)劃的應(yīng)用(2) 圖中N表示第k+1階段可能的狀態(tài)數(shù)，p1、p2、pN為給定狀態(tài)sk和決策xk的前提下，可能達(dá)到下一個狀態(tài)的概率。ci為從k階段狀態(tài)sk轉(zhuǎn)移到k+1 階段狀態(tài)為i時的指標(biāo)函數(shù)值。 在隨機(jī)性的動態(tài)規(guī)劃問題中，由于下一階段到達(dá)的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)行優(yōu)化。第26頁，共28頁。26離散隨機(jī)性動態(tài)規(guī)劃 例2 某公司承擔(dān)一種新產(chǎn)品研制任務(wù)，合同要求三個月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗的技術(shù)人員估計，試制品合格的概率為0.4，每次試制一批的裝配費為200元，每件產(chǎn)品的制造成本為100元。每次試制的周期為1個月。問該如何安排試制，每次生產(chǎn)多少件，才能使得