《【安全課件】動態(tài)規(guī)劃》由會員分享，可在線閱讀，更多相關《【安全課件】動態(tài)規(guī)劃（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第五節(jié)第五節(jié) 動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃是運籌學的一個分支，它是解決多階段決策過程最優(yōu)化的一種數(shù)學方法大約產(chǎn)生于50年代1951年美國數(shù)學家貝爾曼(RBellman)等人，根據(jù)一類多階段 決策問題的特點，把多階段決策問題變換為一系列互相聯(lián)系單階段問題，然后逐個加以解決。與此同時，他提出了解決這類問題的“最優(yōu)性原理”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法動態(tài)規(guī)劃他的名著“動態(tài)規(guī)劃”于1957年出版，該書是動態(tài)規(guī)劃的第一本著作 動態(tài)規(guī)劃模型的分類，根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)的變量；過程分為離散決策過程和連續(xù)決策過程根據(jù)決策過程的演變是確定性的還是隨機性的，過

2、程又可分為確定性決策過程和隨機性決策過程組合起來就有離散確定性、離散隨機性、連續(xù)確定性、連續(xù)隨機性四種決策過程模型本部分主要研究離散決策過程，介紹動態(tài)規(guī)劃的基本概念、理論和方法，并通過幾個典型的問題來說明它的應用，這些都是整個動態(tài)規(guī)劃的基本內(nèi)容 離散決策過程連續(xù)決策過程根據(jù)多階段決策過程的時間參量根據(jù)決策過程的演變確定性決策過程隨機性決策過程離散確定性決策過程離散確定性決策過程連續(xù)確定性決策過程連續(xù)隨機性決策過程 引例有一批軍用物資需要從 A 地調(diào)運到E地，如下圖所示，請求出一條從 A 到 E 的一條線路，使總的運輸距離最短。圖中線條上的數(shù)字為距離。AEB2C2B1B3C1C3D1D24358

3、101214181012945897734111 多階段決策過程及實例多階段決策過程及實例B 地C 地D 地E 地A 地 在生產(chǎn)和科學實驗中，有一類活動的過程，由于它的特殊性，可將過程分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，才能使整個過程達到最好的活動效果因此，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響到以后的決策。AEB2C2B1B3C1C3D1D2435810121418101294589773411 如果一個問題的過程可以化分為若干個互相聯(lián)系的階段，而且每個階段都需要作出決策，而且當每個階段的決策都確定之后，整個問題也就確定了，那么，這個問題就叫做

4、一個多階段決策問題。動態(tài)規(guī)劃就是解決這類問題的一個重要的數(shù)學方法。 如上圖所示的線路網(wǎng)絡，求 A 到 E 點的最短路線問題是動態(tài)規(guī)劃中一個較為直觀的典型例子現(xiàn)通過討論它的解法，來說明動態(tài)規(guī)劃方法的基本思想，并闡述它的基本概念。AEB2C2B1B3C1C3D1D2435810121418101294589773411 如上圖可知，從A點到E點可以分為4個階段從A到B為第一階段，從B到C為第二階段從D到E為第四階段 在第一階段，A為起點，終點有B1，B2，B3三個，因而這時走的路線有三個選擇， 分別是走B1，B2，B3。 如果選擇走B2的決策，則B2就是第 一階段在我們決策之下的結(jié)果它既是第一階段

5、路線的終點，又是第二階段路線的始點。 在第二階段，再從B2點出發(fā)，對應于B2點就有一個可供選擇的終點集合C1，C2，C3； 如果選擇由B2走至C2為第二階段的決策，則C2 就是第二階段的終點，同時又是第三階段的始點 同理遞推下去，可看到：各個階段的決策不同，調(diào)運的路線就不同很明顯，當某一階段的始點給定時，它直接影響著后面各階段的行進路線和整個路線的長短，而后面各階段的路線的發(fā)展不受這點以前各階段路線的影響故此問題的要求是：在各個階段選取一個恰當?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。 AEB2C2B1B3C1C3D1D24358101214181012945897

6、73411 如何解決這個問題呢? 可以采取窮舉法即把由A到E所有可能的每一條路線的距 離都算出來，然后互相比較找出最短者，相應地得出了最短路線這樣，由A到E一共有3 X 3 X 2 X 118條不同的路線，比較這18條不同的路線的距離值，才找出最短路線。 顯然，這樣作計算是相當繁的如果當段數(shù)很多，各段的不同選擇也很多時，這種解法的計算將變得極其繁雜，甚至在電子計算機上計算都是不現(xiàn)實的AEB2C2B1B3C1C3D1D2435810121418101294589773411AEB2C2B1B3C1C3D1D243581012141810129458977341112043514141617192

7、 用動態(tài)規(guī)劃的方法來求解以上最短路問題用動態(tài)規(guī)劃的方法來求解以上最短路問題B 地C 地D 地E 地A 地（1） 順序解法求解得到的結(jié)果內(nèi)容豐富（2） 逆序解法AEB2C2B1B3C1C3D1D24358101214181012945897734110B 地C 地D 地E 地A 地3471110151819193 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念(1)階段階段 把所給問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解 階段的劃分，一般是根據(jù)時間和空間的 自然特征來劃分。 描述階段的變量稱為階段變量，常用 k 表示如例1可分為4個階段來求解，k1、2、3、4。AEB2C2B1

8、B3C1C3D1D2435810121418101294589773411(2)狀態(tài)狀態(tài) 狀態(tài)表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，又稱不可控因素在例1中，狀態(tài)就是某階段的出發(fā)位置它既是該階段某支路的起點，又是前一階段某支路的終點通常一個階段有若于個狀態(tài)，第一階段有一個狀態(tài)就是點A，第二階段有兩個狀態(tài)，即點集合B1，B2， 第k階段的狀態(tài)就是第k是階段所有始點的集合 .AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念 描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個數(shù)、一組數(shù)或一個向量(

9、多維情形)來描述常用 xk 表示第受階段的狀態(tài)變量如在例1中第三階段有 3 個狀態(tài)，則狀態(tài)變量 x3 可取3個值，即x3=c1,c2,c3?？蛇_狀態(tài)集合可達狀態(tài)集合 某個階段的所有的狀態(tài)所構成的集合，稱為可達狀態(tài)集合。例如，第三階段的所有狀態(tài)為c1,c2,c3，則第三階段的可達狀態(tài)集合成為點集合 c1,c2,c3 。記為x3= c1,c2,c3 。AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念狀態(tài)的基本特性狀態(tài)的基本特性無后效性（否則就不能成為動態(tài)規(guī)劃里所講的狀態(tài)）AEB2C2B1B3C1C3D1D243581

10、0121418101294589773411 如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響換句活說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展，當前的狀態(tài)是以往歷史的一個總結(jié)這個性質(zhì)稱為無后效性(即馬爾科夫性)前效性 相反，如果狀態(tài)僅僅描述過程的具體特征，并不滿足無后效性的要求。應適當?shù)馗淖儬顟B(tài)的規(guī)定方法，以達到能使它滿足無后效性的要求。才能成為動態(tài)規(guī)劃里所講的狀態(tài)。 例如，研究物體(把它看作一個質(zhì)點)受外力作用后其空間運動的軌跡問題從描述軌跡這點著眼，可以只選坐標位置(xk，yk)作為過程的狀態(tài)，但這樣不能滿足無后效性，因為即使知道了外力的大小和方向，仍

11、無法確定物體受力后的運動方向和軌跡。 不具有后效性的例子不具有后效性的例子 但是如果把位置(xk，yk)和速度(vxk，vvk)都作為過程的狀態(tài)變量，就可以確定物體運動下一步的方向和軌跡，實現(xiàn)無后效性的要求(3)決策決策 決策表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念決策變量決策變量 uk ( xk ) 描述決策的變量，稱為決策變量它可用一個數(shù)、一組數(shù)或一個向量來描述uk ( xk ) 表示第 k 階

12、段當狀態(tài)處于xk 時的決策變量它是狀態(tài)變量的函數(shù) AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念允許決策允許決策集合集合Dk(xk)在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策允許決策集合AEB2C2B1B3C1C3D1D2435810121418101294589773411Dk(xk) 表示第 k 階段從狀態(tài)xk 出發(fā)的允許決策集合，顯然有 uk(xk) Dk(xk) 從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合是D2(B1)C1，C2，C3，如果選取的點為C2，則C2是

13、狀態(tài)Bl在決策u2(B1) 作用下的一個新的狀態(tài)，記作u2(B1) C2 3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念AEB2C2B1B3C1C3D1D2435810121418101294589773411K 子過程策略子過程策略 由過程的第k階段開始直到終止狀態(tài)為止的過程，稱為問題的后部子過程(或稱為k子過程)全過程的一個策略全過程的一個策略 當k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為p1,n(x1). 3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念允許策略集合允許策略集合 在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，

14、用P表示.從允許決策集合中就能找出達到最優(yōu)效果的策略，它被稱為最優(yōu)策略。 AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念指標函數(shù)指標函數(shù) 使用不同的策略，其效果是不一樣的，把衡量過程效果的好壞的函數(shù)叫做指標函數(shù)。Vkn=Vkn(xk,uk,xk+1, uk +1, xk+1) (k=1,2, ,n)V是value的縮寫AEB2C2B1B3C1C3D1D2435810121418101294589773411在這個函數(shù)里面，各個狀態(tài)的取值是變化的不定的。3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念最優(yōu)指標函數(shù)最優(yōu)指標

15、函數(shù) 對于不同的狀態(tài)xk,指標函數(shù)Vkn有不同的最優(yōu)值，這個最優(yōu)值可以表示為xk的函數(shù)，稱為最優(yōu)指標函數(shù)，記為f k ( x k )AEB2C2B1B3C1C3D1D2435810121418101294589773411 例如 f 2 ( B 2 )表示從第二階段中的B2狀態(tài)到終點E的最短距離。 例如 f 4 ( D 1 )表示從第四階段中的D 1 狀態(tài)到終點E的最短距離。012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場1戰(zhàn)場2戰(zhàn)場3 將問題分為三個階段，第三階段給戰(zhàn)場3分配導彈，第二階段給戰(zhàn)場2和戰(zhàn)場3分配導彈。第一階段給戰(zhàn)場1、2、3分配導彈第三階段給戰(zhàn)場3分配導彈第二階段給

16、戰(zhàn)場2和戰(zhàn)場3分配導彈第一階段給戰(zhàn)場1、2、3分配導彈4 動態(tài)規(guī)劃解動態(tài)規(guī)劃解決問題的決問題的 一般一般 步驟步驟(1)首先確定階段變量 K . K=1,2,3.(2)確定各階段的狀態(tài) xk戰(zhàn)場2戰(zhàn)場3012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場1(1)首先確定階段變量 K . K=1,2,3.(2)確定各階段的狀態(tài) xk(3)確定各階段允許狀態(tài)集合 .X3可以取值多少呢？X3表示分配給第三階段（也就是第3戰(zhàn)場）的導彈數(shù)量。 x2表示分配給第二階段（也就是第2、3戰(zhàn)場）的導彈數(shù)量。 X1表示分配給第一階段（也就是第1、2、.3戰(zhàn)場）的導彈數(shù)量。 X3=0,1,2,3要滿足無后效

17、性，x3,x2,x1(4)確定決策變量.決策變量uk(xk)表示的是當?shù)贙階段所處的狀態(tài)為xk時所作的決策。(4)確定決策變量.(5)確定狀態(tài)轉(zhuǎn)移關系.4 動態(tài)規(guī)劃解決問題的動態(tài)規(guī)劃解決問題的 一般一般 步驟步驟略過012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1(1)首先確定階段變量 K . (2)首先各階段的狀態(tài) xk(3)確定各階段允許狀態(tài)集合 .(4)確定決策變量uk(xk).(5)確定狀態(tài)轉(zhuǎn)移關系.x3X3=0,1,2,3u3(X3)X2X2=0,1,2,3u2(X2)x2-u2(x2)=x3012310371120481230579導彈數(shù)戰(zhàn)場效益(1)首先

18、確定階段變量 K . (2)首先各階段的狀態(tài) xk(3)確定各階段允許狀態(tài)集合 .(4)確定決策變量uk(xk).(5)確定狀態(tài)轉(zhuǎn)移關系.戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X2X1X1=0,1,2,3u1(X1)x1-u1(x1)=x2012310371120481230579導彈數(shù)戰(zhàn)場效益(1)首先確定階段變量 K . (2)首先各階段的狀態(tài) xk(3)確定各階段允許狀態(tài)集合 .(4)確定決策變量uk(xk).(5)確定狀態(tài)轉(zhuǎn)移關系.戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X2X1X1=0,1,2,3u1(X1)x1-u1(x1)=x2xk+1 = xk-uk(xk)X4=0 012310371120481230579導

19、彈數(shù)戰(zhàn)場效益戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3u2(X2) 設uk(xk)為第K個階段所采取的決策變量，也就是分配給第K個戰(zhàn)場的導彈數(shù)量。 設g(uk(xk) ) 為分配給第K個戰(zhàn)場uk(xk)的導彈所產(chǎn)生的效益。 設 f (x k) 為第K階段狀態(tài)為(x k時，第K階段到最后階段所得到的最優(yōu)效益。1）實際求解）實際求解012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1

20、x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3f2(0)=g(u2(0) )+ f3(0)=0f2(1)=g(u2(0) )+ f3(1)=5g(u2(1) )+ f3(0)=4max=5f2(2)=g(u2(0) )+ f3(2)=7g(u2(1) )+ f3(1)=9g(u2(2) )+ f3(0)=8=9maxf2(3)=g(u2(0) )+ f3(3)=9g(u2(1) )+ f3(2)=11g(u2(2) )+

21、f3(1)=13g(u2(3) )+ f3(0)=12max=13u2(X2)012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9xk+1 = xk-uk(xk) x2X2=0,1,2,3f2(0)=g(u2(0) )+ f3(0)=0f2(1)=g(u2(0) )+ f3(1)=5g(u2(1) )+ f3(0)=4max=5f2(2)=g(u2(0) )+ f3(2)=7g(u2(1) )+ f3(1)=9g

22、(u2(2) )+ f3(0)=8=9maxf2(3)=g(u2(0) )+ f3(3)=9g(u2(1) )+ f3(2)=11g(u2(2) )+ f3(1)=13g(u2(3) )+ f3(0)=12max=13u2(X2)012310371120481230579導彈數(shù)戰(zhàn)場效益戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3u3(X3)u3(0)=0u3(1)=1f3(0)=0u3(1)=1f3(1)=5u3(2)=2f3(2)=7u3(3)=3f3(3)=9x2X2=0,1,2,3xk+1 = xk-uk(xk) f2(0)=g(u2(0) )+ f3(0)= 0f2(1)=g(u2(0)

23、 )+ f3(1)=5f2(2)=g(u2(1) )+ f3(1)=9f2(3)=g(u2(2) )+ f3(1)=13=5u2(0)f2(0)= 0決策是、u3(0)f2(1)= 5u2(0)決策是、u3(1)f2(2)= 9u2(1)決策是、u3(1)f2(3)= 13u2(2)決策是、u3(1)u2(X2)012310371120481230579導彈數(shù)戰(zhàn)場效益xk+1 = xk-uk(xk) 戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0決策是、u3(0)f2(1)= 5u2(0)決策是、u3(1)f2(2)= 9u2(1)決策是、u3(1

24、)f2(3)= 13u2(2)決策是、u3(1)x1X1=0,1,2,3用不用再求f1(0)， f1 (1)， f1 (2)了？f1(3)=g(u1(0) )+ f2 (3)= 13g(u1(1) )+ f2 (2)= 12g(u1(2) )+ f2 (1)= 12g(u1(3) )+ f2 (0)= 11max= 13012310371120481230579導彈數(shù)戰(zhàn)場效益xk+1 = xk-uk(xk) 戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0決策是、u3(0)f2(1)= 5u2(0)決策是、u3(1)f2(2)= 9u2(1)決策是、

25、u3(1)f2(3)= 9u2(2)決策是、u3(1)x1X1=0,1,2,3f1(3)=g(u1(0) )+ f2 (3)= 13g(u1(1) )+ f2 (2)= 12g(u1(2) )+ f2 (1)= 12g(u1(3) )+ f2 (0)= 11max= 13012310371120481230579導彈數(shù)戰(zhàn)場效益xk+1 = xk-uk(xk) 戰(zhàn)場2戰(zhàn)場3戰(zhàn)場1x3X3=0,1,2,3x2X2=0,1,2,3f2(0)u2(0)= 0決策是、u3(0)f2(1)= 5u2(0)決策是、u3(1)f2(2)= 9u2(1)決策是、u3(1)f2(3)= 9u2(2)決策是、u3(

26、1)x1X1=0,1,2,3f1(3)=g(u1(0) )+ f2 (3)= 13f1(3)= 13u1(0)決策是、u2(2)、u3(1) 動態(tài)規(guī)劃的方法，在工程技術、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都有廣泛的應用，并且獲得了顯著的效果在企業(yè)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設備更新問題、生產(chǎn)過程最優(yōu)控制問題等等，所以它是現(xiàn)代企業(yè)管理中的一種重要的決策方法許多問題用動態(tài)規(guī)劃的方法去處理，常比線性規(guī)劃或非線性規(guī)劃更有成效特別對于離散性的問題，由于解析數(shù)學無法施展其術，而動態(tài)規(guī)劃的方法就成為非常有用的工具應指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法(如線性規(guī)劃是一種算法)因而，它不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理因此，讀者在學習時，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解小 節(jié)