運籌學教案動態(tài)規(guī)劃課件

運籌學教案動態(tài)規(guī)劃課件概述動態(tài)規(guī)劃為運籌學的一個分支，是用于求解多個階段決策過程的最優(yōu)化數學方法。理論基礎：美國數學家貝爾曼（RichardBellman)研究提出的最優(yōu)化原理（PrincipleofDecision)把多階段過程轉化為一系列單階段問題，逐個求解，創(chuàng)立一類求解多階段過程優(yōu)化問題的方法——動態(tài)規(guī)劃（DynamicProgramming)

動態(tài)規(guī)劃的應用領域經濟管理、工程技術、工農業(yè)生產及軍事部門。具體講：如最短路線，資源分配，庫存管理，生產調度，排序，裝載，市場營銷，設備維修與更新等方面。主要解決時序或空間序階段劃分的多階段問題。但對一些與時間甚至與空間都無關的靜態(tài)問題，在引入特殊序之后用動態(tài)規(guī)劃方法處理。多階段決策過程及實例多階段決策問題舉例從A地經B、C、D、E到F地鋪設管線，問，怎樣鋪設，可使管線最短？AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514若用窮舉法求解，計算量大，且容易遺漏某一路徑。本例可將其劃分為五個階段，用動態(tài)規(guī)劃原理求其最短路徑。思路：從A站出發(fā)應經過哪些站點到F站的總長度最短？若已作出從ABi中之一決策，之后的問題變?yōu)?，從各Bi站點經哪些站點到F點的總長度最短，仍為一多階段決策問題，與前一問題相似，解決方法也相似，只是少了一個階段，問題變小了，若后一問題解決了，則前一問題也解決了。

類似地，到了C站、D站、E站，都面臨同一問題，只是問題越來越小并易于解決。到了E站，從其各點到F的最短距離已易得，再逆推，可求出D站各點到F點的最短距離，逐次逆推，到最后可以求出A點到F點的最短距離。這就是動態(tài)規(guī)劃問題逆推算法。動態(tài)規(guī)劃問題其它例子，見P193機器負荷問題。動態(tài)規(guī)劃問題的基本概念以前述求最短路為例說明動態(tài)規(guī)劃問題中概念。階段與階段變量決策：處理問題時，從多個方案中作出的一某種選擇。

階段：為解決復雜問題而把一個過程劃分為若干個相互區(qū)別又相互聯系的部分。一般地，一個決策可從一個階段變到另一階段。階段的劃分依據：階段一般是根據，（1）時間（2）空間等自然特征來劃分。（3）也可以是其他人為方式。階段變量：描述階段的變量，一般用k表示。為離散變量，取值1，2….n分別表示1，2…n階段。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141階段2階段3階段4階段5階段狀態(tài)與狀態(tài)變量狀態(tài)：表示每個階段開始時所處的自然狀況或客觀條件，又稱為不可控因素，是階段的特征，通常一個階段有若干個狀態(tài)。如：前例，第一階段狀態(tài)為點A，第二階段的狀態(tài)有B1，B2，B3三個狀態(tài)。狀態(tài)變量：描述過程狀態(tài)的變量稱為，一般用xk表示第k個階段的狀態(tài)變量。狀態(tài)集：k階段所有可能狀態(tài)構成的集合。記為Sk，如S2={B1,B2,B3}狀態(tài)的無后效性：即當某階段的狀態(tài)一旦確定,則此后過程的演變不再受此前各狀態(tài)和決策的影響,或者說“未來與過去無關”。即由狀態(tài)xk出發(fā)的后部子過程可以看成一個以xk為初始狀態(tài)的獨立過程。注：階段的劃分與狀態(tài)的選擇要具有此性質，是動態(tài)規(guī)劃問題的特點。決策與決策變量決策：使在k階段，使狀態(tài)從xk

到xk+1

發(fā)生轉移的選擇。決策變量：描述決策的變量稱為決策變量，一般用uk表示第k個階段的決策變量。決策空間：即決策變量可能取值的集合，用Dk(xk)表示第k個階段xk狀態(tài)下的所有允許決策的集合。狀態(tài)轉移方程狀態(tài)轉移：系統由某一階段的一個狀態(tài)因相關決策而轉變到下一個階段的另一個狀態(tài)。與階段、狀態(tài)和決策有關，用下圖示意：

k階段決策輸入狀態(tài)輸出狀態(tài)稱為狀態(tài)轉移方程全過程與后部k子過程從k階段開始到終止狀態(tài)為止的過程稱為動態(tài)規(guī)劃問題的后部k子過程。如下圖所示：全過程：k=1時的子過程。k=1k=n

kk=2n

kk+1k=n,n-1,n-2…3,2,1策略與k子策略策略：設為k階段作出的決策，則稱其組成的決策序列為整個過程的一個全過程策略，簡稱為策略，記為p1,n(x1)?？晒┻x擇的所有全過程策略的集合構成允許策略集合，記為P1,n(x1)。最優(yōu)策略：使總體效果達到最優(yōu)的策略。記為k子策略:k部子過程對應決策形成的決策序列。記為pk,n(xk)=指標函數與最優(yōu)指標數階段指標函數：指對某一個階段的決策效果進行衡量其優(yōu)劣的一種數量指標。一般記為：vk(xk;uk)K指過程的指標函數：描述k子過程策略效果優(yōu)劣的數量函數，記為：Vk,n(xk;pk,n

)或Vk,n。由階段劃分與狀態(tài)選擇的無后效性知，k階段指標函數具有可分性，即可寫為：K=1時稱為全過程的指標函數。一般地，其可分性寫為最優(yōu)指標函數：指標函數的最優(yōu)值稱為最優(yōu)指標函數，記為即有：注:指標函數的含義是多樣的,如:距離、利潤、成本、產品產量、資源消耗等。最優(yōu)化原理“作為全過程的最優(yōu)策略具有這樣的性質：無論過去的狀態(tài)和決策如何，對于前面決策所形成的狀態(tài)（即該最優(yōu)策略上某一狀態(tài)）而言，余下的諸決策必須構成以此狀態(tài)為初始狀態(tài)的最優(yōu)策略。即：最優(yōu)策略的任一后部子策略都是最優(yōu)的。最優(yōu)化原理與動態(tài)規(guī)劃問題基本方程即，為最優(yōu)策略,對任意階段k(1<k<n),他的子策略對于為始點的后部k子過程而言，也必須是最優(yōu)的。注：最優(yōu)化原理只是最優(yōu)性定理的一個推論，即最優(yōu)策略的必要條件。即最優(yōu)性原理不是對任何決策過程普遍成立，它與基本方程不是無條件等價。動態(tài)規(guī)劃問題的基本方程利用動態(tài)規(guī)劃最優(yōu)性原理，可以把多階段決策問題求解看成是對若干個相互聯系的子問題逐個求解的反向遞推過程。求解的過程可用如下基本方程描述：k=1k=n

kk=2逆序計算fk(xk)表示第k階段初始狀態(tài)為xk時，k后部子過程的最優(yōu)準則函數

故逆序遞推法的基本方程為：順序遞推算法的基本方程：k=1k=n

kk=2順序計算此兩個基本方程描述多階段決策問題的求解方法，可以處理廣泛的實際優(yōu)化問題，而且可以得到各階段的一系列最優(yōu)解。但是要受到維數限制。順序遞推算法的基本方程：求解動態(tài)規(guī)劃問題的過程：（1）將問題過程劃分恰當階段，選擇階段變量k.。（2）正確選擇狀態(tài)變量xk.應注意：既能夠正確描過程的演變，又要滿足無后效性。（3）正確選擇決策變量uk，確定允許集合。（4）正確寫出狀態(tài)轉移方程xk+1=Tk(xk,uk)。（5）列出按階段可分的準則函數V1,n，要滿足幾個性質。（6）根據求解方向，給出邊界條件。（7）利用基本方程逆推求解。動態(tài)規(guī)劃的最優(yōu)性定理最優(yōu)性原理僅為策略最優(yōu)的必要條件，是最優(yōu)性定理的推論，為此下面介紹最優(yōu)性定理。設階段為n的多階段決策過程，決策變量k=1,2,…,n,允許策略是最優(yōu)策略的充要條件是:對任意1<k<n,當初始狀態(tài)為x1時,有： (4.3)式中,,即是由給定的初始狀態(tài)x1和子策略p1，k-1所確定的第k階段的狀態(tài).。例一：前述最短距離問題逆向標注法動態(tài)規(guī)劃應用舉例AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141階段2階段3階段4階段5階段首先求第五階段各點到F點的最短距離12AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141階段2階段3階段4階段5階段12逆推一個階段，用基本方程求第4階段和狀態(tài)點到F點的最短距離。如：f4(D1)=min{4+1,2+2}=4,即D1經E2到F為最短路徑。

同理可標注出其它各點到F點的最短距離與路徑。47751181491214最后得最優(yōu)解，最短距離為14，路徑為A-B2-C1-D1-E2-F動態(tài)規(guī)劃應用——資源分配問題

設有某種資源，數量為a，用于生產n種產品，若分配數量為uk用于生產第k種產品時，其收益為gk(uk)。問應當如何分配資源，才使生產n種產品總收益最大？此問題當gk(uk)為非線性函數時，為非線性規(guī)劃問題。此問題雖為靜態(tài)問題，但人為引進階段與狀態(tài)變量后，可用動態(tài)規(guī)劃模型求解。模型將把資料分配給一個或多個使用者的過程作為一個階段，此靜態(tài)規(guī)劃問題的決策變量為多階段決策變量，將累計的量或遞推過程中變化的量選擇為狀態(tài)變量。決變量策變量uk表示分配給第k種產品的原料數，狀態(tài)xk表示分配用于生產第k種產品至第n種產品的原料數，則有狀態(tài)轉移方程：而且階段指標函數為邊界條件為于是此靜態(tài)規(guī)劃問題轉變的動態(tài)規(guī)劃問題的基本方程為：其中fk(xk)

表示將手中資源xk分配生產第k種到第n種產品時的最大利潤。下邊以具體例子說明計算過程。

例：某公司現有4臺設備準備分配給該公司所屬的3家工廠.當分配臺uk設備給工廠k時，工廠k利用這些設備為公司創(chuàng)造的利潤（假設非負）為gk(uk).應當如何分配設備資源，使得公司總利潤最大？其利潤見下表：

工廠k設備數

1

2

301234046770256803578將此問題劃分為三個階段，1，2，3個工廠，其模型為前述模型中n=3,a=4基本方程為：從最后一個階段，即3階