《運籌學動態(tài)規(guī)劃》 (2)ppt課件

1、.1.1動態(tài)規(guī)劃問題和根本概念動態(tài)規(guī)劃問題和根本概念.2 .2 動態(tài)規(guī)劃的根本原理動態(tài)規(guī)劃的根本原理.3 .3 動態(tài)規(guī)劃的運用動態(tài)規(guī)劃的運用 多階段決策是指這樣一類特殊的活動過程, 它們可以按時間順序分解成假設干相互聯(lián)絡的階段, 每個階段都要作出決策, 全部過程的決策是一個決策序列, 所以多階段決策問題又稱為序貫決策問題。多階段決策的目的多階段決策的目的是要到達整個活動過程的總體效果最優(yōu), 所以多階段決策又叫做過程最優(yōu)化。所謂動態(tài)規(guī)劃，動態(tài)規(guī)劃， 就是處理多階段決策和過程最優(yōu)化問題的一就是處理多階段決策和過程最優(yōu)化問題的一種規(guī)劃方法。種規(guī)劃方法。 例.1 最短路問題 設A地的某一企業(yè)要把一批貨

2、物由A地運到E城銷售, 其間要經(jīng)過八個城市,各城市間的交通道路及間隔如以下圖所示, 問應選擇什么道路才干使總的間隔最短? .1 .1 動態(tài)規(guī)劃問題和根本概念動態(tài)規(guī)劃問題和根本概念例中，道路圖(共18條道路,3321=18)枚舉法：例中，道路圖(共18條道路,3321=18)為處理這個最短途徑問題，首先給出幾個定義。1 1、階段、階段(stage) 將所給問題的過程，按時間或空間特征分解成假設干相互聯(lián)絡的段落，以便按次序求解就構成了階段 ,階段變量常用字母 K 來表示。如例 .1有四個階段，K 就等于 1,2,3,4。第一階段共有 3 條道路即(A,B1), (A,B2)和(A,B3),第二階段

3、有 9 條道路，第 3 階段有 6 條道路,第 4 階段有 2 條道路。12342 2、 形狀形狀 ( state)各階段開場時的出發(fā)點稱作形狀。 描畫各階段形狀的變量，稱作形狀變量，用sk 表示。 在例.1 中，第一階段的形狀為 A，第二階段的形狀為城市 B1，B2和B3。 所以形狀變量 S1 的集合 S1=A,S2 的集合是 S2=B1,B2,B3,依次有 S3=C1,C2,C3, S4=D1,D2。1234 3 3、 決策決策Decision ) Decision ) 當各階段的形狀確定以后，就可以做出不同的決議或選擇，從而確定下一階段的形狀，這種決議就是決策，表示決策的變量稱為決策變量

4、。常用kXks表示第 K 階段當形狀為ks時的決策變量， 在例.1中第二階段如決議從B1出發(fā)，即S2=B1，可選擇走C1或C2，C3 ，假設我們選擇，從C2走，那么此時的決策變量可表示x2(B1)=C2。12344 4、戰(zhàn)略、戰(zhàn)略 PolicyPolicy 在各階段決策確定以后，整個問題的決策序列就構成了一個戰(zhàn)略在各階段決策確定以后，整個問題的決策序列就構成了一個戰(zhàn)略, ,用用P1n(s1)P1n(s1)表示。表示。 如對于例.1總共可有18個戰(zhàn)略，但最優(yōu)戰(zhàn)略只需一個。12345 5、目的函數(shù)、目的函數(shù) 用于衡量所選定戰(zhàn)略優(yōu)劣的數(shù)量目的稱作目的函數(shù)。一個用于衡量所選定戰(zhàn)略優(yōu)劣的數(shù)量目的稱作目的

5、函數(shù)。一個n n階階段的決策過程，從段的決策過程，從1 1到到n n 叫作問題的原過程。叫作問題的原過程。 目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函數(shù)，最優(yōu)目的函數(shù)記為目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函數(shù)，最優(yōu)目的函數(shù)記為fk(sk)fk(sk)，它表示從第，它表示從第K K階段的形狀階段的形狀SkSk出發(fā)采用的最優(yōu)戰(zhàn)略。出發(fā)采用的最優(yōu)戰(zhàn)略。 當當K=1K=1時時, f1(s1 ), f1(s1 )就是從初始形狀就是從初始形狀S1S1到全過程終了的整體最到全過程終了的整體最優(yōu)目的函數(shù)。優(yōu)目的函數(shù)。 , 在例.1中，目的函數(shù)就是間隔。如在第2階段，形狀為B2時，f2 (B2)那么表示從B2到E的最短間隔。本問

6、題的總目的是求f 1(A), 即從A到E的最短間隔。12346 6、 形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程在動態(tài)規(guī)劃中，本階段的形狀往往是上階段決策的結果。所以假設給定了第 K 階段的形狀ks和該階段的決策kx(ks)，那么第 K+1 段的形狀1+ks由于 K 階段決策的完成也就完全確定了 ,它們之間的關系可用如下公式表示： 1+kskTks，kx其中，kT表示從形狀ks出發(fā)經(jīng)過kx向下一階段的轉(zhuǎn)移(Transfer)，換言之，即1+ks是從形狀ks出發(fā)經(jīng)過決策kx轉(zhuǎn)移的結果。由于上式表示了由 K 段到第 K+1 段的形狀轉(zhuǎn)移規(guī)律，所以就稱為形狀轉(zhuǎn)移方程。在例 .1中,形狀轉(zhuǎn)移方程即1+kskx。 為了求

7、出例.1的最短道路,一個簡單的方法是,可以求出一切從A到E的能夠走法的路長并加以比較。不難知道,從A到E共有18條不同的道路,每條道路有四個階段,要做3次加法,要求出最短道路需做54次加法運算和17次比較運算,這叫做窮舉法。 當問題的段數(shù)很多,各段的形狀也很多時,這種方法的計算量會大大添加,甚至使得尋優(yōu)成為不能夠。 下面運用動態(tài)規(guī)劃方法求解例.1。運用逆序遞推方法求解,即由最后一段到第一段逐漸求出各點到終點的最短道路,最后求出A點到E點的最短道路。 運用逆序遞推方法的益處是可以一直盯住目的,不致脫離最終目的。 例.1是一個四階段決策問題,普通可分為四步：1234第一步第一步,從從K=4開場開場

8、 1234S1S2S3S4逆序法求解最短路問題形狀變量S4可取兩種形狀D1, D2,它們到E點的間隔分別為4和3,這也就是由D1和D2到終點E 的最短間隔， 即 f4(D1)=4, f4(D2)=3.第二步第二步 ,K=3形狀變量 S3 可取 3 個值即 C1,C2 和 C3。為方便運用，規(guī)定用d(sk，sk+1)表示由形狀sk出發(fā)，到達下一階段sk+1時的兩點間隔。 3f1Cmin+)(),()(),(24211411DfDCdDfDCd=min+3543=7這闡明,由1c到 E 的最短間隔為 7,其途徑為以1C1DE,相應的決策為*3x1C=1D1234S1S2S3S4+)(),()(),

9、(24221412DfDCdDfDCd 3f2Cmin=min+3246=5即從 C2 到 E的最短間隔為 5,其途徑為2C2DE,相應的決策為*3x2C=2D1234S1S2S3S4即從 C3 到 E的最短間隔為 5,其途徑為 C3D1E,相應的決策為*3x3C=1D。 3f3Cmin+)(),()(),(24231413DfDCdDfDCd=min+3341=51234S1S2S3S4第三步第三步, K=2, K=2由于第 3 段各點 C1,C2,C3 到終點 E 的最短間隔 f3(C1),f3(C2), f3(C3),知,所以要求城市 B1 到 E 的最短間隔,只需以它們?yōu)楦?分別加上

10、B1 到達 C1,C2,C3 的一段間隔,加以比較取其最短者即可。即 B1 到終點 E 的最短間隔為 9,其途徑為 B1C2D2E,本段的相應決策為*2x1B=2C )(12Bf=min+)(),()(),()(),(333123211311CfCBdCfCBdCfCBd=min+555476=91234S1S2S3S4同理有: )(22Bf=min+)(),()(),()(),(333223221312CfCBdCfCBdCfCBd=min+565778=11 即*2x2B3CB2C3 D1 E1234S1S2S3S4+ )(32Bf=min+)(),()(),()(),(333323231

11、313CfCBdCfCBdCfCBd=min+595877=13 即*2x3B2C1234S1S2S3S4B3C2 D2 E第四步第四步, K=1, 只需一個形狀點 A,那么 )(1Af=min+)(),()(),()(),(333232121BfBAdBfBAdBfBAd=min+13511998=171234S1S2S3S4從城市 A 到城市 E 的最短間隔為 17。把各段的最優(yōu)決策按計算順序反推,即得到最優(yōu)決策序列,即*1xA1B,*2 x1B=2C,*3 x2C2D，*4x2DE，所以最短道路為:AB1C2D2E.1234 圖例.1各點到終點的最短途徑根據(jù)例 .1, 動態(tài)規(guī)劃的根本思想

12、可總結如下：一、 將多階段決策過程劃分階段,恰當?shù)剡x取形狀變量,決策變量和定義最優(yōu)目的函數(shù),從而把問題化成一族同類型的子問題，然后逐個求解。二、 求解時從邊境開場， 沿過程行進方向，逐段遞推尋優(yōu)。在每一個子問題求解時,都要利用它前邊已求出的子問題的最優(yōu)結果,最后一個子問題的最優(yōu)解,就是整個問題的最優(yōu)解。三、 動態(tài)規(guī)劃方法是既把當前一段與未來各段分開,又把當前效益和未來效益結合起來思索的一種最優(yōu)化方法,因此,每段的最優(yōu)決策的選取都是從全局思索的,它與該段的最優(yōu)選擇是不同的。在例.1的求解過程中 , 各段的計算都利用了第K 段和第 K+1 段的如下關系：kfksminkdks，sk+1 )(11+

13、kksf (k=4,3,2,1) (1)(55sf 0 (2)這種遞推關系稱為動態(tài)規(guī)劃的根本方程動態(tài)規(guī)劃的根本方程,(2)式稱邊境條件,容易算出,運用動態(tài)規(guī)劃方法解例 .1 只進展了 17 次加法運算,11 次比較運算，就獲得了最優(yōu)解,比窮舉法的計算量明顯地要少,而且隨著問題段數(shù)的添加和變量程度的提高,計算量將呈指數(shù)規(guī)律減少。其次,動態(tài)規(guī)劃的計算結果不僅得到了 A 到 E 的最短道路,而且得到了恣意一點到 E 點的最優(yōu)道路。這可由圖 .2 來描畫(用彩色線表示最優(yōu)道路,各點上的數(shù)字表最短間隔).2.1 最優(yōu)化原理最優(yōu)化原理 動態(tài)規(guī)劃方法是由美國數(shù)學家貝爾曼(R.Bellman)等人于本世紀 5

14、0 年 代提出的。他們針對多階段決策問題的特點,提出理處理這類問題的 最優(yōu) 化原理 ,并勝利地處理了消費管理、工程技術許多方面的實踐問題。最優(yōu)化 原理可以表述為：“一個過程的最優(yōu)戰(zhàn)略具有這樣的性質(zhì) , 即無論初始形狀 和初始決策如何,對于先前決策所構成的形狀而言,其以后的一切決策必構成 最優(yōu)戰(zhàn)略。 簡言之：最優(yōu)戰(zhàn)略的任一子戰(zhàn)略都是最優(yōu)的。 假設把最優(yōu)化原理用數(shù)學言語描畫,就得到了動態(tài)規(guī)劃的根本方程： kfks opt)(),(11+kkkkksfxsd (k=n,n-1,1) 1+kf1+ks0 其中,opt 可依題意取max或min7.2.2 動態(tài)規(guī)劃求解的根本步驟 求解動態(tài)規(guī)劃 , 就是分

15、析問題并建立問題的動態(tài)規(guī)劃根本方程。勝利地運用動態(tài)規(guī)劃方法的關鍵 ;在于識別問題的多階段特征 ,將問題 分解成可用遞推關系式聯(lián)絡起來的假設干子問題 ,或者說是要正確地建立具 體問題的根本方程。而正確地建立關于遞推關系根本方程的關鍵，又 在于正確地選擇形狀變量保證各階段的形狀變量具有遞推的形狀轉(zhuǎn)移關系。 1+ks),(kkkxsT。 這是建立動態(tài)規(guī)劃模型的兩個要點。 1234S1S2S3S4例P184 某公司有資金萬元，擬投資于個工程，其收益分別為2111222333()4, ()9, ()2gxxgxxgxx可建立以下模型：2123123123max z=4x92 x10 x ,0 xxxxx

16、x+7.2.2 動態(tài)規(guī)劃求解的根本步驟 2. 形狀變量ks：表示第 K 段可用于剩余的 n-k+1 個工程的資金數(shù), 顯然有1s=10, 4s=0。 3. 決策變量kx： 即應分配第 K 個工程上的投資額。 1.階段：K=1，2，4. 形狀轉(zhuǎn)移方程：kkkxss-+1 5. 最優(yōu)目的函數(shù)kfks：表示當可投資金數(shù)為ks時,投資于剩余的 n-k+1個工程的最大收益。 6. 根本方程為： +0)()()(max)(1111nnkkkkkksfsfxgsf k=3,2,1 (逆序解法)投資問題: 設總投資額為 A萬元, 擬投資于n個工程上，知對第i 個工程投 資ix萬元,收益函數(shù)為)(iixg,問應

17、如何分配資金才可以使總收益最大 ? 這是一個與時間無明顯關系的靜態(tài)最優(yōu)化問題 ,可先列出其靜態(tài)模型為： 為了運用動態(tài)規(guī)劃方法求解, 我們可以人為地賦予它“時段的概 念。方法是將投資工程排序, 假想對各個投資工程有先后順序。 首先考 慮對項目 1 的投資, 然后思索對工程 2 的投資, 依次最后思索第 n 項 投資.這樣就把原問題轉(zhuǎn)化為 n 階段的決策過程。接下來的問題，便是如 何選擇正確的形狀變量,并使各后部子過程間具有遞推關系。 Max Vniiixg1)( s.t. Axnii1 0ix (i=1,2,n) 2. 形狀變量ks：表示第 K 段可用于剩余的 n-k+1 個工程的資金數(shù), 顯然

18、有1s=A, 1+ns=0。 3. 決策變量kx： 即應分配第 K 個工程上的投資額。 1.階段：K=1，2，n4. 形狀轉(zhuǎn)移方程：kkkxss-+1 5. 最優(yōu)目的函數(shù)kfks：表示當可投資金數(shù)為ks時,投資于剩余的 n-k+1個工程的最大收益。 6. 根本方程為： +0)()()(max)(1111nnkkkkkksfsfxgsf k=n,n-1,2,1 假設運用逆序遞推尋優(yōu), 那么)(1s1f就是所求的最大收益。 7.2.3 動態(tài)規(guī)劃求解時的幾種常用算法離散變量的分段窮舉法如最短路問題的解法, 離散型資源分配問題等延續(xù)變量的解法根據(jù)方程的詳細情況靈敏選取求解方法a.逆序解法b.順序解法如

19、延續(xù)型資源分配問題等例用動態(tài)規(guī)劃方法求解以下問題2123123123max z=4x92 x10 x ,0 xxxxxx+解：采用逆序解法順序解法的根本方程為： +0)()()(max)(144k+1kkkkksfsfxgsf k=3,2,1當3時，有333333440()m a x ()()xsfsgxfs+33230max 2xsx可以看到,當 時, f3(s3)獲得極大值*33xs332233330()max22xsfsxs當時，有222222330()max ()()xsfsgxfs+222223302230m ax 9()m ax 92)xsxsxfsxs+2222220m ax 9

20、2() xsxsx+-2222222 (,)92()h sxxsx+-記 求其極值點:22222294 ()(1)09 4d hsxd xxs+-這是一個極小點, 為什么?所以,極大值只能夠在0,s2的端點獲得, 那么有2222222()2 ()9fssfss或當1時，有111111220()max ()()xsfsgxfs+111220max4()xsxfs+分兩種情況: 討論!當 x1=0時, f1(10)=200, 到達最大值.再由形狀轉(zhuǎn)移方程順推,可求出: x2=0 x3=10例用動態(tài)規(guī)劃方法求解以下問題2123123123max z=4x92 x10 x ,0 xxxxxx+解：采用

21、順序解法順序解法的根本方程為： +0)()()(max)(1kkkkkksfsfxgsf k=3,2,1當時，有121211010()max ()()xsfsgxfs+12102m a x 44xsxs12*xs當時，有232322120()max ()()xsfsgxfs+23232120220m a x 9() m a x 94) xsxsxfsxs+23232320230m a x 94 () m a x 54) xsxsxsxxs+-+39 s*23xs當3時，有343433230()max ()()xsfsgxfs+34342323023430m a x 2() m a x 29 (

22、) xsxsxfsxsx+-2343h(s,x)=2x9()sx+-記33490dhxdx-求導，得934x解得223 40d hdx此點僅為極小點極大值應在0，s4=0，10的端點獲得當x3=0時，f3 (10)=90當x3=10時，f3 (10)=200*3 10 x再由形狀轉(zhuǎn)移方程逆推： *332*232*1100 x000sxssxx-逆序解法的過程見書 P.3.1 資源分配問題 例 某企業(yè)共有設備 5 臺,擬分給三個工廠,各工廠利用這些設備 為企業(yè)可提供的盈利 kk(x )g各不一樣 ( 見表.4) ,問應如何分配這四臺 設備才干使企業(yè)獲得的盈利最大? 表 .4 有關資料 單位：萬元

23、 設備分配數(shù) )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲廠乙廠丙廠 Max z3iiixg1)( s.t. 5xnii1 0ix (i=1,2,n) 分析: 可建立如下模型解： 1.將問題按工廠分為三個階段，k=1,2,3 2.設 xk分配給第k個工廠的設備臺數(shù)。S1S2S3S4甲廠x1乙廠x2丙廠x33.形狀轉(zhuǎn)移方程：Sk+1=Sk - xk知 s1=5 s2=s1-x1 s3=s2-x2 4.目的函數(shù)為: fk(sk)=maxgk(xk)+fk+1(sk+1) k=3,2,1 f4(

24、s4)=0 設備分配數(shù) )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲廠乙廠丙廠當 K=3時形狀變量3s的取值范圍為3s0，1，2，3，4 ,53x的取值范圍也是3D0，1，2，3，4, 5 ,33sx 0)(44sf,K=3時的結果如下表: x3s3f3(s3)=g3(x3)+ f4(s4)f3(s3)x30123450123455.列表計算：046111212012345046111212當K=2時223xss-322ssx- X2s2f2(s2)=g2(x2)+f3(s3)f2(s2)

25、x20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+00051102142 161,2212形狀變量的取值范圍為 s2=0,1,2,3,4,5,x2的取值范圍也是2D0，1，2，3，4, 5 ,當k=1時，s1=5, x1的可取值為0,1,2,3,4,5計算結果如下： x1s1f1(s1)=g1(x1)+f2(s2)f1(s1)x10123455最優(yōu)分配方案有兩個：x1=0, x2=2, x3=30+213+167+14 9+10 12+5 13+0210，2x1

26、=2, x2=2, x3=1例 7.5 一運輸商擬用一 10 噸載分量的大卡車裝載 3 種貨物, 資料如下表,問應如何組織裝載,可使總價值最大? 解： 設裝載第三種貨物的件數(shù)為ix，那么有： Max z=41x+52x+63x s.t. 31x+42x+53x10 0 xi 且為整數(shù) 貨物編號1 2 3單位分量噸單位價值(百元)3 4 54 5 67.3.2背包問題背包問題是動態(tài)規(guī)劃的典型問題。一維背包問題的典型提法是：一位游覽者能接受的背包最大分量是 b 千克，現(xiàn)有 n 種物品供他選擇裝入背包，第 i 種物品單件分量為ia千克，其價值(或重要性參數(shù))為 ci，總價值是攜帶數(shù)量ix的函數(shù)即ii

27、xc，問游覽者應如何選擇所攜帶物品的件數(shù)以使總價值最大? 模型可表述為：niiixcz1max s.t. bxaniii1 0ix 且為整數(shù)i=1,2,n段。用動態(tài)規(guī)劃方法來求解1. 階段 k：即需求裝入的 n 種物品的次序,每段裝入一種,共 n2. 形狀變量ks：即在第 k 段開場時,允許裝入前 k 種物品的總重量，顯然有1s=b 3. 決策變量kx：即裝入第 K 種物品的件數(shù)4. 形狀轉(zhuǎn)移方程：kkkkxass-+1允許的決策集合是：kkkkkkasxxsD0|)(且為整數(shù) 5. 目的函數(shù)是:)+nkSn+1fsfxcsfk+1kkkkk,.,2, 10)(max)(n+11當K=3時，S

28、3=0，1，2，10 ， f3(S3)=max6x3+0 x3s36x3+0f3(s3)x301201234567891000000666661200000666661200000111112 x2s25x2+ f3(S3)f2(s2)x2012012345678910當K=2時，S2=0，1，2，10， f2(S2)=max6x2+ f3(S3)000000+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111100001000211當K=1時，S1=10, f1(S1)=max4x1+ f2(S2) x1s14x1+

29、 f2(S2)f1(s1)x1S2012310最優(yōu)解為： X1*=2, X2*=1, X3*=0 Z*=130+114+68+512+013247.3.3 消費與存儲問題 例 7.6 某廠消費的一種產(chǎn)品，以后四個月的訂單如下表：月份1234訂貨量bk)3324合同規(guī)定在各月底前交貨，消費每批產(chǎn)品的固定本錢為3千元，每批消費的產(chǎn)品件數(shù)不限。每件產(chǎn)品的可變本錢為1千元，每批產(chǎn)品的最大消費才干為5件。產(chǎn)品每件每月的存儲費為500元。又知1月初有庫存產(chǎn)品1件，4月底不再留下產(chǎn)品。試在滿足需求的前提下，如何組織消費才干使總的本錢最低。解：1.設階段變量為K,那么每月為一個階段,K=1,2,3,40 xk

30、5,4. 形狀轉(zhuǎn)移方程由下式確定： 1+ks kkkbxs-+ 其中 ,kd表示第 K 階段的產(chǎn)品總本錢，即 ),(kkkxsd+)0(0.5sk)50(3kkxxxk+0.5sk2.每月初的產(chǎn)品庫存量作為形狀變量，由知條件顯然有S1=1，S5=03.決策變量是每月的產(chǎn)品消費量，由知條件知： 5. 建立根本方程即本錢最小化)(),(min)(11+kkkkkUkksfxsdsfkk=4,3,2,10)(55sf當K=4時，S4的最小能夠值為0，即4月初沒有存貨。S4的最大能夠值=5313 3 2，4=4即 S4=0，1，2，3，4。 K=4s4本階段費用s5f5(s5)d+ f5(s5)f4(s4)x4消費費用存儲費d(s4,x4)043+4070077133+30.56.5006