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

1、第五節(jié)第五節(jié) 動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支，它是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法大約產(chǎn)生于50年代1951年美國數(shù)學(xué)家貝爾曼(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ù)決策過程的演變是確定性的還是隨機(jī)性的，過

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

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

4、一個多階段決策問題。動態(tài)規(guī)劃就是解決這類問題的一個重要的數(shù)學(xué)方法。 如上圖所示的線路網(wǎng)絡(luò)，求 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ā)，對應(yīng)于B2點就有一個可供選擇的終點集合C1，C2，C3； 如果選擇由B2走至C2為第二階段的決策，則C2 就是第二階段的終點，同時又是第三階段的始點 同理遞推下去，可看到：各個階段的決策不同，調(diào)運(yùn)的路線就不同很明顯，當(dāng)某一階段的始點給定時，它直接影響著后面各階段的行進(jìn)路線和整個路線的長短，而后面各階段的路線的發(fā)展不受這點以前各階段路線的影響故此問題的要求是：在各個階段選取一個恰當(dāng)?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。 AEB2C2B1B3C1C3D1D24358101214181012945897

6、73411 如何解決這個問題呢? 可以采取窮舉法即把由A到E所有可能的每一條路線的距 離都算出來，然后互相比較找出最短者，相應(yīng)地得出了最短路線這樣，由A到E一共有3 X 3 X 2 X 118條不同的路線，比較這18條不同的路線的距離值，才找出最短路線。 顯然，這樣作計算是相當(dāng)繁的如果當(dāng)段數(shù)很多，各段的不同選擇也很多時，這種解法的計算將變得極其繁雜，甚至在電子計算機(jī)上計算都是不現(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)階段階段 把所給問題的過程，恰當(dāng)?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?？蛇_(dá)狀態(tài)集合可達(dá)狀態(tài)集合 某個階段的所有的狀態(tài)所構(gòu)成的集合，稱為可達(dá)狀態(tài)集合。例如，第三階段的所有狀態(tài)為c1,c2,c3，則第三階段的可達(dá)狀態(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)的影響換句活說，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的一個總結(jié)這個性質(zhì)稱為無后效性(即馬爾科夫性)前效性 相反，如果狀態(tài)僅僅描述過程的具體特征，并不滿足無后效性的要求。應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的規(guī)定方法，以達(dá)到能使它滿足無后效性的要求。才能成為動態(tài)規(guī)劃里所講的狀態(tài)。 例如，研究物體(把它看作一個質(zhì)點)受外力作用后其空間運(yùn)動的軌跡問題從描述軌跡這點著眼，可以只選坐標(biāo)位置(xk，yk)作為過程的狀態(tài)，但這樣不能滿足無后效性，因為即使知道了外力的大小和方向，仍

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

12、段當(dāng)狀態(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ī)劃的基本概念A(yù)EB2C2B1B3C1C3D1D2435810121418101294589773411K 子過程策略子過程策略 由過程的第k階段開始直到終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程(或稱為k子過程)全過程的一個策略全過程的一個策略 當(dāng)k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為p1,n(x1). 3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念3 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念允許策略集合允許策略集合 在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，

14、用P表示.從允許決策集合中就能找出達(dá)到最優(yōu)效果的策略，它被稱為最優(yōu)策略。 AEB2C2B1B3C1C3D1D24358101214181012945897734113 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念指標(biāo)函數(shù)指標(biāo)函數(shù) 使用不同的策略，其效果是不一樣的，把衡量過程效果的好壞的函數(shù)叫做指標(biāo)函數(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)指標(biāo)函數(shù)最優(yōu)指標(biāo)

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

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

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

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

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) 設(shè)uk(xk)為第K個階段所采取的決策變量，也就是分配給第K個戰(zhàn)場的導(dǎo)彈數(shù)量。 設(shè)g(uk(xk) ) 為分配給第K個戰(zhàn)場uk(xk)的導(dǎo)彈所產(chǎn)生的效益。 設(shè) f (x k) 為第K階段狀態(tài)為(x k時，第K階段到最后階段所得到的最優(yōu)效益。1）實際求解）實際求解012310371120481230579導(dǎo)彈數(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導(dǎo)彈數(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導(dǎo)彈數(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導(dǎo)彈數(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導(dǎo)彈數(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導(dǎo)彈數(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ī)劃的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都有廣泛的應(yīng)用，并且獲得了顯著的效果在企業(yè)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題等等，所以它是現(xiàn)代企業(yè)管理中的一種重要的決策方法許多問題用動態(tài)規(guī)劃的方法去處理，常比線性規(guī)劃或非線性規(guī)劃更有成效特別對于離散性的問題，由于解析數(shù)學(xué)無法施展其術(shù)，而動態(tài)規(guī)劃的方法就成為非常有用的工具應(yīng)指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法(如線性規(guī)劃是一種算法)因而，它不象線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進(jìn)行具體分析處理因此，讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解小 節(jié)