運(yùn)籌學(xué)教案動(dòng)態(tài)規(guī)劃課件

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

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

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

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

到xk+1

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

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

kk=2n

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

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

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

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

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

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

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

表示將手中資源xk分配生產(chǎn)第k種到第n種產(chǎn)品時(shí)的最大利潤(rùn)。下邊以具體例子說明計(jì)算過程。

例：某公司現(xiàn)有4臺(tái)設(shè)備準(zhǔn)備分配給該公司所屬的3家工廠.當(dāng)分配臺(tái)uk設(shè)備給工廠k時(shí)，工廠k利用這些設(shè)備為公司創(chuàng)造的利潤(rùn)（假設(shè)非負(fù)）為gk(uk).應(yīng)當(dāng)如何分配設(shè)備資源，使得公司總利潤(rùn)最大？其利潤(rùn)見下表：

工廠k設(shè)備數(shù)

1

2

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