運籌學第八章動態(tài)規(guī)劃.ppt

1、第八章動態(tài)規(guī)劃，導論，動態(tài)規(guī)劃是解決多階段決策過程優(yōu)化的一種方法。這種方法是由美國數(shù)學家貝爾曼在20世紀50年代初提出的。并成功地解決了生產(chǎn)管理和工程技術中的許多問題，從而建立了運籌學的一個新分支，即動態(tài)規(guī)劃。貝爾曼在1957年出版了動態(tài)規(guī)劃，這是動態(tài)規(guī)劃領域的第一本書。動態(tài)規(guī)劃與其他規(guī)劃方法的區(qū)別在于，動態(tài)規(guī)劃是解決某一類問題(多階段決策問題)的方法，是研究問題的一種方式，而不是具體的算法。因此，與線性規(guī)劃不同，它沒有標準的數(shù)學表達式和一套明確定義的(算法)規(guī)則，但必須分析和管理具體問題。因此，在學習動態(tài)規(guī)劃時，不僅要正確理解基本概念和方法，還要在積累一定經(jīng)驗的基礎上，用豐富的想象力建立模型

2、，用創(chuàng)造性的技巧解決問題。提綱，1個動態(tài)規(guī)劃的例子，2個動態(tài)規(guī)劃的基本概念，3個動態(tài)規(guī)劃的基本思想和原則，4個逆序解和順序解，學習目標：1闡明什么是多階段決策問題，并特別注意如何將沒有明顯時間背景的問題轉(zhuǎn)化為多階段決策問題。P156例1動態(tài)規(guī)劃，P156例2機器負荷分配問題(時間階段問題)有某種機器設備用來完成兩種工作A和B.如果k開始時完整機器的數(shù)量是xk，如果uk的數(shù)量用于A，剩余的(xkuk)用于工作B，則該年的預期收入是g(uk) h(xkuk)。G(uk)和h(xkuk)是已知函數(shù)，g(0)=h(0)=0。此外，機器和設備在使用中會損壞。當機器用于工作A時，一年后可繼續(xù)使用的完好機器

3、數(shù)量占年初投入的70%；如果在作業(yè)B中使用，一年后可以繼續(xù)使用的完整機器數(shù)量占年初輸入的90%。明年年初，可繼續(xù)用于A和B的設備數(shù)量為xk 1=0.7uk 0.9(xk uk)。讓第一年年初的完好機器總數(shù)為1000臺，并詢問連續(xù)五年每年A和B的機器數(shù)量如何分配，以使五年的總收入最大化。1動態(tài)規(guī)劃的例子，相應的問題稱為多階段決策問題。這是一個多階段的決策過程。這個過程可以分為幾個相互關聯(lián)的階段，每個階段都需要做出一個決定，從而在整個過程中形成一個決定。第一年，u1，x2=0.7u10.9 (x1-u1)，U2，x3=0.7u20.9 (x2-U2)，u3，第四年，u4，x5=0.7u4 0.9(

4、x4-u4)，u5，P156例1最短路線問題(空間從A到E有很多路線可供選擇，且各點之間的距離如圖所示。問旅行者選擇哪條路線，這樣從A到E的總距離是最短的。1，2，3，4，決策1，決策2，決策3，決策4可以看作是一個四階段決策問題。從以上兩個例子中，我們可以知道，所謂的多階段決策問題就是指這樣一個決策問題：這個過程可以分為相互關聯(lián)的階段，每個階段對應一組備選決策，而每個決策的選擇取決于當前的狀態(tài)并影響未來的整體結果。當每個階段的決策被選定時，它就構成了一個決策序列，稱為策略，它對應于某個效果。多階段決策問題是尋找最佳策略。多階段決策過程的特點1。每個階段的決策都是相互關聯(lián)的。多階段決策過程優(yōu)化

5、的目的是實現(xiàn)整個活動過程的最佳整體效果，而不是某一階段的最佳“局部”效果。因此，每個階段的決策選擇不是任意的。前一個決策的選擇決定了當前的狀態(tài)，從而影響到?jīng)Q策后下一階段的狀態(tài)和決策，從而影響整體效果。因此，在每個階段做出決策時，決策者不僅要考慮這一階段的最佳方案，還要考慮對最終目標的影響，從而做出總體上最佳的決策。動態(tài)規(guī)劃是滿足這一要求的優(yōu)化方法。2.每個階段的決策通常與“時間”相關。動態(tài)規(guī)劃方法與“時間”密切相關。隨著時間進程的發(fā)展，每個階段的決策都是決定的，從而產(chǎn)生一個決策序列，這就是“動態(tài)”的含義。但是，一些與時間無關的靜態(tài)問題，只要人為地將“時間”因素引入到問題中，也可以被視為多階段決

6、策問題，可以用動態(tài)規(guī)劃方法來處理。學習目標：1 .準確、熟練掌握動態(tài)規(guī)劃的基本概念，尤其是狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移規(guī)律、指標函數(shù)和基本方程。2.動態(tài)規(guī)劃的基本概念是，為了解決和表達決策和過程的發(fā)展順序，把給定的問題分成幾個相互關聯(lián)的不同的子問題，稱為多階段決策問題階段。階段是需要做出決定的子問題。通常，根據(jù)決策的時間或空間順序來劃分階段。描述一個階段的變量稱為階段變量，通常記錄為k，k=1，2和n。例如，解可以根據(jù)空間分為四個階段，k=1，2，3，4。(1)階段、狀態(tài)：每個階段開始時的客觀條件。描述每個階段狀態(tài)的變量稱為狀態(tài)變量，而xk通常用來表示第k階段的狀態(tài)。(2)狀態(tài)。在示例1中，狀

7、態(tài)是某個階段的起始位置。根據(jù)狀態(tài)變量的值是連續(xù)的還是離散的，動態(tài)規(guī)劃問題可以分為離散型和連續(xù)型。動態(tài)規(guī)劃中的狀態(tài)應滿足無后效性(Markov屬性):所謂無后效性是指系統(tǒng)達到某一狀態(tài)之前的過程決策不會影響到該狀態(tài)之后的決策。它是指系統(tǒng)從某一階段到未來的發(fā)展，它只由這一階段的狀態(tài)及其未來的決策所決定，而與系統(tǒng)以前的狀態(tài)和決策(歷史)無關。該過程的過去歷史只能通過當前狀態(tài)影響其未來發(fā)展。在示例1中，當在某個階段的狀態(tài)中選擇了某個點時，該點之后的路線僅與該點相關，并且不受該點之前的路線的影響，因此該狀態(tài)沒有后效。狀態(tài)集：狀態(tài)變量xk的值集稱為狀態(tài)集，它實際上是一個關于狀態(tài)的約束條件。通常，Sk用來表示

8、狀態(tài)集xkSk。第一階段S1=a；第二階段有三個國家B1，B2和B3，所以S2=B1，B2和B3。(3)決策，當過程在某一階段處于某一狀態(tài)時，可以作出不同的決策來確定下一階段的狀態(tài)，這叫做決策。描述決策的變量稱為決策變量，當狀態(tài)為xk時，uk(xk)通常用于表示k階段的決策變量，xk是狀態(tài)變量的函數(shù)。在示例1中，從第二階段的狀態(tài)B1，可以選擇下一階段的C1、C2和C3。如果我們決定選擇C1，它可以表示為u2(B1)=C1。B1，C1，C2，C3，決策集：當狀態(tài)為xk時，決策變量uk(xk)的值范數(shù)稱為決策集，通常用Dk(xk)表示。在示例1中，從第二階段的狀態(tài)B1，可以選擇下一階段的C1、C2

9、和C3。也就是說，D2(B1)=C1、C2和C3；B1、C1、C2、C3，決策集實際上是決策的約束條件，uk(xk) Dk(xk)?？偨Y階段k、狀態(tài)xk、狀態(tài)集Sk、決策集uk(xk)和決策集Dk(xk)。(4)狀態(tài)轉(zhuǎn)移定律(方程):從某個狀態(tài)值xk開始，當確定了決策變量uk(xk)的值時，也就確定了下一階段狀態(tài)變量xk 1的值。描述從xk到xk 1轉(zhuǎn)變的定律稱為狀態(tài)轉(zhuǎn)變定律(方程式)。從第二階段的狀態(tài)B1開始，如果我們明確選擇C2(即確認下一階段的狀態(tài))。在上面的例子中，u2(B1)=C2的狀態(tài)轉(zhuǎn)移定律是：xk 1=uk(xk)。一般來說，下一階段狀態(tài)變量xk 1的值是前一階段的某個狀態(tài)變量

10、xk和前一階段的決策變量uk(xk)的函數(shù)，表示為xk 1=Tk(xk，uk(xk)，(5)策略：由N個決策階段組成的決策序列依次構成一個策略，由P1U1 (x1)、U2 (x2)和UN (xn)表示。在本例中，p14u1 (a)=B1，U2 (B1)=C2，u3 (C2)=D1，U4 (D1)=e代表策略之一，其總距離為2 5 6 3=16。策略集：在實際問題中，由于每個階段都有許多可供選擇的決策，它們的不同組合構成了許多可供選擇的決策序列(策略)，由它們組成的集合稱為策略集，被記錄為P1n。從策略集合來看，效果最好的策略稱為最優(yōu)策略。子策略：從K階段到N階段，由依次做出的階段決策組成的決策

11、序列稱為K子策略，表示為PKN=英國(XK)、英國1 (XK 1)、聯(lián)合國(XN)，例如，從第三階段C2狀態(tài)開始的子策略可以表示為P34=U3 (C2)，它是在整個過程或子過程或階段中定義的一個確定的數(shù)量函數(shù)。對于不同的問題，指標函數(shù)可以是成本、成本、產(chǎn)值、利潤、產(chǎn)量、消耗、距離、時間、效用等。階段指數(shù)函數(shù)、過程指數(shù)函數(shù)、階段指數(shù)函數(shù)：是指在K階段從狀態(tài)xk進行決策uk時產(chǎn)生的收益，用vk(xk，uk)表示。在示例1中，索引函數(shù)是距離。例如，v2(B1，C2)表示從B1開始，采用從判定點到C2的兩點之間的距離，即v2(B1，C2)=5。過程指數(shù)函數(shù)：是指在第K階段從某個狀態(tài)xk取子策略pkn時

12、所獲得的收益，在例1中記錄為Vkn(xk，uk，xk 1，uk 1，xn)，如V34 (C2，U3 (C2)=D1，D1，U4 (D1)=E，E)。過程指數(shù)函數(shù)Vkn通常是描述整個過程或后K子過程的優(yōu)劣的量化指標，它是由階段指數(shù)函數(shù)vk(1)累加而成的(1)可分性：適用于動態(tài)規(guī)劃求解問題的過程指標函數(shù)(即目標函數(shù))必須具有關于階段指標的可分形式，即后子過程的指標函數(shù)可以表示為：vkn (xk，uk，xk1，uk 1，xn)=vk (xk，uk) vk1 (xk1，uk 1) VN在多階段決策問題中，一種常見的目標函數(shù)形式是每個階段的效果之和，即對于某些問題， 例如系統(tǒng)可靠性，目標函數(shù)是每個階段

13、的效果的產(chǎn)物，例如，簡而言之，特定問題的目標函數(shù)的表達形式需要依賴于特定問題。 (2)遞歸：過程指標函數(shù)Vkn應滿足遞歸關系，即遞歸，VKN (xk，uk，xk1，uk 1，xn)，kxk，uk，v (k 1) n (xk1，uk 1，xn)，vk (xk，uk) vk1 Uk)，V(k 1)n(xk 1，uk 1，xn)，最優(yōu)指標函數(shù)：它表示當kth階段的狀態(tài)為xk至終止時，采用最優(yōu)策略pkn*的最優(yōu)收益值寫為fk(xk)。Fk (xk)=vkn (xk，pkn *)=optvkn (xk，pkn)，例如1，f3(C2)=3 4=7。其中opt可以根據(jù)具體情況采用最大值或最小值。，C2，動態(tài)

14、規(guī)劃的目標是什么？最優(yōu)解：最優(yōu)策略p1n最優(yōu)值：最優(yōu)指標f1(A)，多階段決策問題的數(shù)學模型綜上所述，一類適用于動態(tài)規(guī)劃方法的多階段決策問題的數(shù)學模型是如下形式： f1=opt V1n(x1，p1n)最優(yōu)指標函數(shù)xk 1=Tk(xk，Uk(xk)狀態(tài)轉(zhuǎn)移方程ukDk決策變量xkSk狀態(tài)變量k=1，2，n，階段變量，St，上述數(shù)學模型表明，對于給定的多得到一個(或多個)最優(yōu)策略或最優(yōu)決策序列u1、u2、un，它不僅滿足左表達式給出的所有約束，而且使左表達式所示的目標函數(shù)得到極值。summary :index function form : sum，product，no aftereffect，r

15、ecursion，fk (xk)=vkn (xk，pkn *)=optvkn (xk，pkn)，vkn (xk，uk，xk1，uk 1，xn)，kxk，Xn)，解決多階段決策過程的問題，找出，u1*、u2*、un*、x1*、x2*、xn*、1。劃分階段，2。正確選擇狀態(tài)變量，3。確定決策變量和允許的決策集，4。確定狀態(tài)轉(zhuǎn)移方程，5。確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立靜態(tài)問題應人工給出“時間”的概念，以便劃分階段。在建立動態(tài)規(guī)劃模型的步驟中，狀態(tài)變量的選擇不僅要準確描述過程的演化，而且要滿足無后效的要求，并且每個階段的狀態(tài)變量的值都是可以確定的。通常選擇待解決問題的關鍵變量作為決策變量，并給出決策變量的取值范圍，即確定允許的決策集。根據(jù)k階段狀態(tài)變量和決策變量，編寫了k-1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應該具有遞歸關系。階段指數(shù)函數(shù)指的是第k階段的收入，最優(yōu)指數(shù)函數(shù)指的是從第k階段到第n階段結束所獲得的收入的最優(yōu)值。最后，寫出了動態(tài)規(guī)劃的基本方程。以上五個步驟是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型不同于線性規(guī)劃模型，在