廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃

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

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

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

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

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

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

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

8、n)是k步長(zhǎng)從點(diǎn)sk到端點(diǎn)的距離，fk(sk)是到端點(diǎn)的最短距離。最短路徑問(wèn)題是該定線(xiàn)需要f1(A)。，20，動(dòng)態(tài)編程的基本思路，離散決策動(dòng)態(tài)編程解決，最短路徑問(wèn)題，逆序方法：(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 從邊界條件開(kāi)始逐步遞歸優(yōu)化，在解決每個(gè)子問(wèn)題時(shí)，使用前面確定的子問(wèn)題的最佳結(jié)果，最后一個(gè)子問(wèn)題的最佳解決方案，即整個(gè)問(wèn)題的最佳解決方案(3)段的最佳決定選擇，通常與段的最佳選擇不同，整體考慮，動(dòng)態(tài)編程方法的基本思路，32，動(dòng)態(tài)編程方法：(1)逆序法，(2)順序法Fk(sk 1)是從起點(diǎn)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 * * 在此最佳策略中，無(wú)論特定狀態(tài)的先前狀態(tài)和決定如何，該狀態(tài)的所有后續(xù)決定都必須構(gòu)成最佳子策略。也就是說(shuō)最佳策略的任意球子策略都是最佳的。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到端點(diǎn)的最佳收益值fk(sk 1):從開(kāi)始到步驟k 1的狀態(tài)計(jì)劃將5臺(tái)設(shè)備分配給公司所屬的a、b、c三家工廠(chǎng)。各工廠(chǎng)取得該設(shè)備后，可預(yù)

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

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

13、。在這一行，我們?cè)谧畲蟮闹瞪霞铀絹?lái)表示差異。也可以看出，此時(shí)最好的決定是1或2。3動(dòng)態(tài)編程的應(yīng)用(1)，47，步驟1:1，2，3將設(shè)備分配給工廠(chǎng)時(shí)，最大收益是優(yōu)選值0，1，2，3，4，5。值計(jì)算參照表108中的表10-8，然后按計(jì)算表的順序計(jì)算。1.據(jù)了解，調(diào)查表107是已知的，然后得到的。被分配到0家工廠(chǎng)，2家b工廠(chǎng)，3家c工廠(chǎng)。2.根據(jù)，表107分配給，3動(dòng)態(tài)編程應(yīng)用程序(1)，48，知道，因?yàn)樗玫搅耍矗?個(gè)a工廠(chǎng)，2個(gè)b工廠(chǎng)，1個(gè)c工廠(chǎng)。兩種分配方案都能獲得最高總利潤(rùn)21萬(wàn)元。3動(dòng)態(tài)編程應(yīng)用(1)，49，2，背包問(wèn)題各有無(wú)限數(shù)量的n個(gè)項(xiàng)目。我的I項(xiàng)是每件重量wi公斤，每件價(jià)值ci元。現(xiàn)