廣東工業(yè)大學 管理運籌學第10章動態(tài)規(guī)劃

1、第1、10章動態(tài)編程，1多級決策流程優(yōu)化問題的實例2基本概念、基本方程和優(yōu)化原理3動態(tài)編程的應用(1)4動態(tài)編程的應用(2)、2、實例1多級資源分配問題，將數(shù)量為x的特定資源投入到兩種生產(chǎn)方法a和b中：將數(shù)量y投入到生產(chǎn)方法a中，剩下的投入到生產(chǎn)方法b中，收入g其中g(y)和h(y)是已知函數(shù)，g(0)=h(0)=0；另外，假設您可以用y和x-y分別投入兩種生產(chǎn)方法a，b可以用a和b的回收率回收再生產(chǎn)。尋找步驟n后的最大總收入。1多階段決策流程優(yōu)化問題實例，3，實例1繼續(xù)(1)，分別以y和x-y的形式投入生產(chǎn)方法a和b，在步驟1中投入生產(chǎn)后回收的資源合計為x1=ay b(x-y)，x1投入生產(chǎn)

2、方法a和b，則收入g(y1) h(x1)因此，問題是，通過獲取y，y1，y2，yn-1，g(y)h(x-y)g(y1)h(x1-y1)g(yn-1)h(xn-)滿足條件x1=ayb(x-y)x2=ay1b(x1-y1)xn-1=ayn-2b(xn-2-yn-2)yi和Xi不是負值求從a到e的最短路徑。b，c，b，d，d，e，c，k值增加時，所需的添加和比較次數(shù)會快速增加。例如，當k=20時，加法比較為4.2550833962771015次，1.3726007547297717114次。計算1億次/秒需要大約508天。7，1多級決策過程優(yōu)化問題的示例，討論：1，a到e的最短路徑問題可以轉換為具有

3、4個特性但大小較小的子問題，分別是Di，Ci，Bi，a到e的最短路徑問題。步驟4:兩個起點D1和D2，只有一個終點；表10-1分析發(fā)現(xiàn)D1和D2到e的最短路徑是唯一的。步驟、8和3:有三個起點：C1、C2、C3、D1和D2，分別分析和討論C1、C2和C3中D1和D2的最短路徑問題。表10-2分析結果：通過C1時，最短路的是C1-D2-e；如果通過C2，則段落為C2-D2-e。通過C3時，最短路徑為C3-D1-E。1多階段決策流程優(yōu)化問題實例，第9，2階段：4個起點B1、B2、B3、B4，終點C1、C2、C3。分析和討論起點和終點，分別從B1、B2、B3、B4到C1、C2和C3的最短路徑問題：表

4、10-3分析結果：經(jīng)過B1后的B1-C2-D2-e；B2-C3-D1-e(如果通過B2)；通過B3時為B3-C3-D1-e；通過B4后，移至B4-C3-D1-E。1多級決策過程優(yōu)化問題的示例，第10，1步：只有一個起點a，結尾有B1、B2、B3和B4。分析和討論從a到B1、B2、B3、B4的最短路徑問題：表10-4中的最后，從a到e的最短路徑是AB4C3D1E，1多級決策過程優(yōu)化問題的示例，11，以上計算過程和結果如圖2所示，上述方法不僅可以獲得從a到d的最短路徑，還可以獲得從圖中任意點到e的最短路徑只用了22次加法，計算效率遠高于宮法。b，c，b，d，d，e，c，對于每個階段k的每個狀態(tài)，如

5、果在決策集Qk(xk)、Qk(xk)中選擇決策qkQk(xk)，則狀態(tài)xk將轉換為新狀態(tài)xk 1=Tk(xk，Qk)，并獲得利潤Rk(xk，Qk)。我們的目標是從每一階段的決策集中選擇決策，以最大限度地提高每一階段的總利潤。這種多階段問題稱為動態(tài)編程。2基本概念，基本方程和優(yōu)化原理，13，多階段決策過程，動態(tài)規(guī)劃的分類：離散決策離散概率連續(xù)決策連續(xù)概率類型，決策1，決策2，決策n，14，狀態(tài)可以是數(shù)量或文字，數(shù)量狀態(tài)可以是連續(xù)的或不連續(xù)的。3，決定xk:從一個狀態(tài)切換到下一個狀態(tài)時所做的選擇。決定是該狀態(tài)的函數(shù)，以xk(sk)表示。決策允許集Dk(sk):狀態(tài)sk中決策的完全允許。4，poli

6、cy Pk，n(sk):從步驟k開始到最后n步的決策序列，稱為k子策略。P1，n(s1)是整體過程策略。5，狀態(tài)轉移方程sk 1=Tk(sk，xk):狀態(tài)及其狀態(tài)的決策和下一狀態(tài)之間的函數(shù)關系。2基本概念，基本方程和優(yōu)化原理，17，6，階段索引函數(shù)vk(sk，xk):從狀態(tài)sk開始，選擇從決策xk生成的階段k指標。流程指標函數(shù)Vk，n(sk，xk，xk 1，xn):選擇從狀態(tài)sk開始由決策xk，xk 1，xn生成的流程指標。動態(tài)編程需要過程指標的可分離性。也就是說，vk，n (sk，xk，xk 1，xn)=vk (sk，xk) vk1 (sk 1，xk 1，xn)是指標相加或vk，n()最佳指

7、數(shù)函數(shù)fk(sk):從狀態(tài)sk開始，所有策略Pk，n，流程指標Vk，n的最佳值為2基本概念，基本方程和優(yōu)化原理，18，可加指數(shù)函數(shù)的常識是自下而上的“opt”是“max”或“min”對于乘法指數(shù)函數(shù)，常識是動態(tài)編程最佳指標的遞歸方程，通過編寫上述表達式，是動態(tài)編程的基本方程。端子條件：為了使上述遞歸方程具有遞歸起點，必須設置最佳指標的端子條件，通常在最后狀態(tài)n 1下的最佳指數(shù)fn 1(sn 1)=0。2基本概念，基本方程和優(yōu)化原理，19，特別是f1(s1)，是從初始狀態(tài)s1到整個過程結束的整體最優(yōu)函數(shù)。最短路徑問題的步長指標函數(shù)是兩點之間的距離。后子程序pk，n的指數(shù)函數(shù)Vk，n(sk，pk，

8、n)是k步長從點sk到端點的距離，fk(sk)是到端點的最短距離。最短路徑問題是該定線需要f1(A)。，20，動態(tài)編程的基本思路，離散決策動態(tài)編程解決，最短路徑問題，逆序方法：(10)，(4)，(3)，(7)，(5)，(5)，(5) k=4s 4=D1、D2、D3、x * 4 (D1)=E1、x * 4 (D2)=E2、x * 4 (D3)=E1、23 k=1 S1=a，x * 1 (a)=B1，26，x * 3 (C4)=D3，k=2 S2=B1，B2，x * 2 (B1) x * 4 (D2)=E2，x * 4 (D3)=E1，29，k=5 S5=E1，e2f 5 (E1)=d (E1，F(xiàn)

9、) x * 1(A)=b1x * 2(B1)=c2x * 3(C2)=d2x * 4(D2)=e2x * 5(E2)=f，F(xiàn)1 從邊界條件開始逐步遞歸優(yōu)化，在解決每個子問題時，使用前面確定的子問題的最佳結果，最后一個子問題的最佳解決方案，即整個問題的最佳解決方案(3)段的最佳決定選擇，通常與段的最佳選擇不同，整體考慮，動態(tài)編程方法的基本思路，32，動態(tài)編程方法：(1)逆序法，(2)順序法Fk(sk 1)是從起點a到階段k狀態(tài)sk 1的最短距離k=0f0(a)=0k=1 f1(B1)=4x * 1(B1)=af1(B2)=5x * 1 k=3 F3(D1)=11x * 3(D1)=C1/C2 F

10、3(D2)=12x * 3(D2)=c2f3 F3(D3)=11x * * 在此最佳策略中，無論特定狀態(tài)的先前狀態(tài)和決定如何，該狀態(tài)的所有后續(xù)決定都必須構成最佳子策略。也就是說最佳策略的任意球子策略都是最佳的。37，順序法，逆序適用的條件：(1)給出初始狀態(tài)，逆序法(2)可以使用退出狀態(tài)，順序法(3)可以使用初始狀態(tài)和退出狀態(tài)，可以使用，劃分38，1，建模(1)階段sk 1=Tk(sk，xk)sk=Tk(sk 1，Xk)(3)指數(shù)函數(shù)fk(sk):步驟k，從sk到端點的最佳收益值fk(sk 1):從開始到步驟k 1的狀態(tài)計劃將5臺設備分配給公司所屬的a、b、c三家工廠。各工廠取得該設備后，可預

11、測的利潤如表10-5所示，問如何將這5個設備分配給這3個工廠，以最大限度地提高所造成的總利潤。表10-5，3動態(tài)編程應用程序(1)，41，解決：將問題按工廠分為3個階段，a，b，c三個工廠分別編號為1，2，3個工廠。Sk=設置從第一個工廠到第三個工廠的指定設備表數(shù)(k=1、2、3)。Xk=分配給第k個設備數(shù)。已知S1=5和具有和的定義。在此，從第三步開始計算。步驟3(1)、42、3步驟：將設備分配給3工廠時，步驟3的指標值(工廠3的收益)最大。也就是說，所需的值為0，1，2，3，4，5，因為第三階段是最后一個階段。數(shù)值計算見表106。3動態(tài)編程的應用(1)，43，表106，3動態(tài)編程的應用(1

12、)，44。其中表示采取3個子流程的最佳指標值時的決定。例如，如表10-6所示，=4，此時(將4臺設備分配給第三工廠)是最佳決定，此時步驟指標值(利潤)為12，最佳3子流程最佳指標值也為12。步驟2:將設備分配給2工廠和3工廠時，每個值的最佳分配方案是最大收益，即最佳2子流程最佳指數(shù)函數(shù)值，3動態(tài)編程的應用(1)，45。這是因為可以計算值，例如表107。表107，3動態(tài)編程應用程序(1)，46，這里，如表105所示，將一臺設備移交給b工廠是有利的?？梢栽诒?06中確認=11 .也可以知道當時；那時；那時；那時；2由于工廠不能劃分5臺設備，所以車廂是空的，沒有裝滿。獲取這些值中最大的值。范例=16

13、。在這一行，我們在最大的值上加水平來表示差異。也可以看出，此時最好的決定是1或2。3動態(tài)編程的應用(1)，47，步驟1:1，2，3將設備分配給工廠時，最大收益是優(yōu)選值0，1，2，3，4，5。值計算參照表108中的表10-8，然后按計算表的順序計算。1.據(jù)了解，調(diào)查表107是已知的，然后得到的。被分配到0家工廠，2家b工廠，3家c工廠。2.根據(jù)，表107分配給，3動態(tài)編程應用程序(1)，48，知道，因為它得到了，即，2個a工廠，2個b工廠，1個c工廠。兩種分配方案都能獲得最高總利潤21萬元。3動態(tài)編程應用(1)，49，2，背包問題各有無限數(shù)量的n個項目。我的I項是每件重量wi公斤，每件價值ci元?，F(xiàn)