運籌學(xué)動態(tài)規(guī)劃ppt課件

1、第八章 動態(tài)規(guī)劃多階段決策過程：是指這樣一類決策過程，它可以按時間分為假設(shè)干階段稱為時段，每一個階段都需求做出決策，以便在過程的最終階段得到最優(yōu)結(jié)局。動態(tài)規(guī)劃的一個重要特點是利用所謂的“最優(yōu)化原理，將問題用函數(shù)方程來表示即遞推方程，然后利用方程遞推地進展計算、求解。1一、最短道路問題最短道路問題：是指給定始點和終點，并且知由始點到終點的各種能夠的途徑，需求找出由始點到終點的最短道路。這里的最短道路可以是通常意義下的間隔，也可以是運輸?shù)臅r間或運輸費用等等。2例由A到D地要鋪設(shè)一條煤氣管道。其中須經(jīng)過兩級中間站，第一級中間站分別為B1和B2，第二級中間站分別為C1、C2、C3。兩站之間有連線的就表

2、示可鋪設(shè)管道，沒有連線的就表示不能鋪設(shè)管道。連線中間的數(shù)字表示兩點間鋪設(shè)管道的長度，試確定一條由A點到D點的鋪設(shè)管道的最短道路。AB2B1C3C2C1D212331343413符號和概念A(yù)B2B1C3C2C1D21233134341n：表示由當(dāng)前的形狀到終點之間的階段數(shù)。：表示由當(dāng)前的形狀到終點之間的階段數(shù)。如由如由A點到點到D點點n=3；由；由B2到到D點點n=2等等。等等。n=3n=2n=14符號和概念A(yù)B2B1C3C2C1D21233134341s：表示當(dāng)前所處的位置，稱為形狀變量。：表示當(dāng)前所處的位置，稱為形狀變量。如如s可以是可以是A、B1、B2、C1、C2等等。等等。5符號和概念A(yù)

3、B2B1C3C2C1D21233134341Xn(s)：稱為決策變量，它表示由階段數(shù)為：稱為決策變量，它表示由階段數(shù)為n的某個形狀的某個形狀s演化到下一個階段的某個形狀，演化到下一個階段的某個形狀，決策者做出的一種選擇。決策者做出的一種選擇。如，如，X2(B1)表示已處于表示已處于B1形狀，還有形狀，還有2個階段就到達個階段就到達D點了，此時決策者可選擇的地點了，此時決策者可選擇的地點；點；X2(B1)可取可取C1,C2或或C3。6符號和概念A(yù)B2B1C3C2C1D21233134341fn(s)：表示由階段數(shù)為：表示由階段數(shù)為n的某個形狀的某個形狀s至終點的最短間隔。至終點的最短間隔。例如，

4、例如，f2(B1)表示由階段數(shù)為表示由階段數(shù)為2的形狀的形狀B1沿最優(yōu)道路到達終點的間隔，即沿最優(yōu)道路到達終點的間隔，即B1到到D點的最點的最短間隔。短間隔。顯然本例就是要求顯然本例就是要求f3(A)及及f3(A)所確定的最短道路。所確定的最短道路。7符號和概念A(yù)B2B1C3C2C1D21233134341d(s，Xn(s)：表示當(dāng)前處于形狀：表示當(dāng)前處于形狀s時，選取決策變量時，選取決策變量Xn(s)后，由點后，由點s到點到點Xn(s)的間隔。的間隔。例如，例如，d(B1，C3)=1，d(C2，D)=3 8分析要求出f3(A)的值及相應(yīng)的戰(zhàn)略從起點A開場分析 AB2B1C3C2C1D2123

5、31343419當(dāng)處于形狀A(yù)時，有幾種可供選擇的道路 AB2B1C3C2C1D2123313434110當(dāng)處于形狀A(yù)時，有兩種可供選擇的道路AB1：闡明由A點所選擇的下一點是B1由B1形狀到終點D的最短間隔為f2(B1)假設(shè)選此條道路，那么由A出發(fā)到達終點的最短間隔可表示為 d(A,B1)+ f2(B1)AB2：闡明由A點所選擇的下一點是B2由B2形狀到終點D的最短間隔為f2(B2)假設(shè)選此條道路，那么由A出發(fā)到達終點的最短間隔可表示為 d(A,B2)+ f2(B2)11綜合思索兩種情況可知，由形狀A(yù)出發(fā)，到終點D的最優(yōu)道路應(yīng)是上述兩種最短間隔中的最小值，即 可見，要計算f3(A)就得先計算f

6、2(B1)和f2(B2)。 2221213,minBfBAdBfBAdAf12由B1、B2點出發(fā)分別有幾種可供選擇的道路？ AB2B1C3C2C1D2123313434113由B1點出發(fā)有三種可供選擇的道路 B1C1最短間隔為 d(B1,C1)+ f1(C1)B1C2最短間隔為 d(B1,C2)+ f1(C2)B1C3最短間隔為 d(B1,C3)+ f1(C3)14綜合思索三種情況可知，由形狀B1出發(fā)，到終點D的最優(yōu)道路應(yīng)是上述三種最短間隔中的最小值，即可見，要計算f2(B1)就得先計算和f1(C1)、f1(C2)、f1(C3)。 31312121111112,minCfCBdCfCBdCfC

7、BdBf15由B2點出發(fā)有三種可供選擇的道路 B2C1最短間隔為 d(B2,C1)+ f1(C1)B2C2最短間隔為 d(B2,C2)+ f1(C2)B2C3最短間隔為 d(B2,C3)+ f1(C3)16綜合思索三種情況可知，由形狀B2出發(fā)，到終點D的最優(yōu)道路應(yīng)是上述三種最短間隔中的最小值，即可見，要計算f2(B2)就得先計算和f1(C1)、f1(C2)、f1(C3)。 31322122111222,minCfCBdCfCBdCfCBdBf17由于由形狀C1、C2、C3出發(fā)到達終點D只需經(jīng)過一個階段，所以 DCdCfDCdCfDCdCf,33122111118由以上分析可以看出，計算f3(A

8、)的過程實踐是一個倒推的過程，即由最后的階段向前逐級進展計算。AB2B1C3C2C1D2123313434119當(dāng)n=1時 DCDCdCfDCDCdCfDCDCdCf3331222111114,3,1,相應(yīng)的最短路線為相應(yīng)的最短路線為相應(yīng)的最短路線為20圖示AB2B1C3C2C1D2123313434121當(dāng)n=2時 DCBCfCBdCfCBdCfCBdBf11313121211111124564413313,min相應(yīng)的最短路線為DCBCfCBdCfCBdCfCBdBf12313221221112223563413312,min相應(yīng)的最短路線為22圖示AB2B1C3C2C1D21233134

9、34123當(dāng)n=3時 DCBABfBAdBfBAdAf1122212136763442min,min相應(yīng)的最短路線為24圖示AB2B1C3C2C1D21233134341所以，鋪設(shè)管道的最短道路應(yīng)是AB1C1D。 25總結(jié)對于最短道路問題，普通地有如下的遞推關(guān)系式： 這個遞推公式是根據(jù)最優(yōu)化原理得到的 為終點狀態(tài)其中： E,2,min11Esdsfnsxfsxsdsfnnnn26最優(yōu)化原理最優(yōu)化原理一個過程的最優(yōu)戰(zhàn)略具有這樣的性質(zhì)，即無論其初始形狀和初始決策如何，其今后諸決策對第一個決策所構(gòu)成的形狀作為初始形狀和過程而言，必需構(gòu)成最優(yōu)戰(zhàn)略。 27二、動態(tài)規(guī)劃的運用281、“背包問題/最優(yōu)裝載問

10、題假設(shè)有一個徒步游覽者，它所能接受的游覽背包的總分量式A公斤，今有n種游覽物品供它選擇裝入背包中，知，aj：第j種物品的單位分量公斤cj：第j種物品的單位運用價值闡明給該游覽者所帶來的益處的一種數(shù)量目的我們的問題是：如何確定這n種物品的數(shù)量x1、x2、xn，使得該游覽者的背包分量不超越A公斤，而且對游覽者來說總的運用價值最大？ 29例假設(shè)有以下“背包問題 總分量不超越5物品編號 123單位重量aj325每件使用價值量cj8512物品件數(shù)xjx1x2x330數(shù)學(xué)模型3 , 2 , 105523. .1258max321321jxxxxtsxxxfj且全為整數(shù)，31思緒分析給待裝物品編號：1、2、

11、n分n步裝載物品。為與階段數(shù)同一，假設(shè)從編號為n的物品開場倒序裝載。即先裝第n號物品，再裝n-1號物品，最后裝1號物品。如本例，先裝3號物品，再裝2號物品，最后裝1號物品。32思緒分析當(dāng)裝n號物品時，假設(shè)決議裝xn件， xn 應(yīng)滿足以下條件 xn為決策變量、A為總分量限制nnnnnA, 0,Aaxxxa整數(shù)33遞推公式n種物品的最大價值量= 第n種物品的價值量 + 剩余n-1種物品的最大價值量即： ymax1nnnnfxcyf34形狀變量確實定“背包只需一個約束條件：分量限制。裝載階段不同，“背包剩余的分量限制會發(fā)生變化。因此可確定“分量限制為形狀變量。公式可寫成 n2時nn1nnn,aAxn

12、AmaxAnnxafxcf且為整數(shù)35當(dāng)n=1時 1111,01111maxaycxcyfxyxa為整數(shù)36求解例題用遞推關(guān)系式計算：我們的問題是求f3(5) 012,5max5512max5512max5max5221 ,0323,55032333233,503333333ffxfxxfxxafxcfxxxxax為整數(shù)為整數(shù)37可見要計算f3(5),要先計算f2(5)、f2(0) 110,35,5max255max255max5max51112, 1 ,0213,25021222122,502222222fffxfxxfxxafxcfxxxxax為整數(shù)為整數(shù) 002f38可見，要計算f2(5

13、)、f2(0) ，要先計算f1(5)、f1(3)、 f1(1)、f1(0) 1583585511111axacf 1383383311111axacf 0103181111111axacf 0003080011111axacf39將f1值代入f2中，得到 )0, 0(000) 1, 1(,1310138max010858max52112212xxffxx，f40將f2值代入f3中，得到“背包問題的最優(yōu)解為 X1=1, X2=1, X3=0, 最優(yōu)值為13。 0, 1, 113012,13max53213xxxf412、投資分配問題/資源分配問題資源分配問題：設(shè)有某種資源如電力、煤炭等，可用于資

14、源分配問題：設(shè)有某種資源如電力、煤炭等，可用于n種消費，假設(shè)資源的總數(shù)種消費，假設(shè)資源的總數(shù)量為量為A，用于第，用于第j種消費的資源數(shù)量為種消費的資源數(shù)量為xj時，可以得到收益時，可以得到收益gj(xj),j=1,2,n，問：對資，問：對資源源A應(yīng)如何進展分配，使得總的收益最大？應(yīng)如何進展分配，使得總的收益最大？投資分配問題：設(shè)有總數(shù)為投資分配問題：設(shè)有總數(shù)為A的資金，要分配給的資金，要分配給n個工程或工廠、部門等，用于擴個工程或工廠、部門等，用于擴展再消費或其他建立，假設(shè)展再消費或其他建立，假設(shè)xj：表示分配給第：表示分配給第j個工程的資金數(shù)；個工程的資金數(shù)；gj(xj):表示第表示第j個個

15、工程得到數(shù)量為工程得到數(shù)量為xj的資金后，所提供的利潤值；問：如何確定各工程的資金數(shù)，使得的資金后，所提供的利潤值；問：如何確定各工程的資金數(shù)，使得總的投資利潤最大？總的投資利潤最大？ 42分析無妨假設(shè)，分n個階段思索分配給n個工程的資金，由于每個階段的決策不僅影響到該工程得到的資金多少，同時也會影響到今后其他工程所能夠得到的資金數(shù)資金總數(shù)A已確定，所以可以用動態(tài)規(guī)劃方法來求解，令：fk(x):數(shù)量為x的資金分配給前k個工程所得到的最大利潤值；xk：分配給第k個工程的資金數(shù)，滿足條件：0 xkx顯然，我們的目的是求fn(A) 43分析當(dāng)n=1時，f1(x)表示將數(shù)量為x的資金分配給一個工程的最

16、大利潤，由于只需一個工程，所以f1(x)=g1(x)當(dāng)n=k2時，gk(xk)表示分配給第k個工程資金數(shù)為xk時的利潤值；(x-xk)表示分配給前k個工程資金數(shù)為x，那么分配給前k-1個工程的資金數(shù)為x-xk；fk-1(x-xk)表示以數(shù)量為x-xk的資金分配給k-1個工程所得到的最大利潤值。 kkkkxxkxxfxgxfk10max44例：股東投資30萬元給三個工廠進展工廠擴建，每個工廠擴建后的利潤與投資額的大小有關(guān)，投資后的利潤值如下表：問：應(yīng)如何分配這30萬元使得這四個工廠擴建后總利潤最大？ 投資x利潤0102030g1(x)0205065g2(x)0204050g3(x)0256075

17、45解 03010202010300max30max302323232330,20,10,0323333fgfgfgfgxfxgfx要計算f3(30)， 要先計算f2(30)，f2(20)，f2(10)，f2(0)46 03010202010300max30max301212121230,20,10,0212222fgfgfgfgxfxgfx )0()20()10(10200max20max2012121220,10,0212222fgfgfgxfxgfx47 010100max10max10121210, 0212222fgfgxfxgfx 002f要計算f2(30)，f2(20)，f2(1

18、0)，f2(0)， 要先計算f1(30)，f1(20)，f1(10)，f1(0) 48將以上結(jié)果代入前面各式 0002010105020206530301111111111gfgfgfgxgf49 20,107005020405020650max03010202010300max30max30121212121230,20,10,0212222xxfgfgfgfgxfxgfx50 20, 0500402020500max)0()20()10(10200max20max201212121220,10,0212222xxfgfgfgxfxgfx51 0,1010, 020020200max0101

19、00max10max101212121210, 0212222xxxxfgfgxfxgfx或 0, 0, 00122xxf52 0,10,2010, 0,208007520605025700max03010202010300max30max303231232323232330,20,10,0323333xxxxxxfgfgfgfgxfxgfx或得最優(yōu)解為 最優(yōu)值為80 533、多階段消費安排問題 /多階段配置問題設(shè)有某種原料，其數(shù)量為A噸，用于消費兩種不同類型的產(chǎn)品，記為類型、類型，知投入該原料進展消費后，還可以回收部分原料用于下一階段的再消費，假設(shè)g1(a)：投入數(shù)量為a的原料，消費型產(chǎn)品的

20、收益值；g2(a) ：投入數(shù)量為a的原料，消費型產(chǎn)品的收益值； r1(a)：消費型產(chǎn)品的回收率0r11；r2(a)：消費型產(chǎn)品的回收率0r21我們的目的是，對于總數(shù)為A的原料進展n個階段消費，每個階段應(yīng)如何分配原料用于消費型產(chǎn)品及型產(chǎn)品，使得經(jīng)過n個階段消費之后總收益最大？ 54分析由于問題本身就是多階段的，所以可以用動態(tài)規(guī)劃方法求解，令：fk(a)：初始原料數(shù)量為a，進展k個階段的消費，采取最優(yōu)分配戰(zhàn)略所獲得的最大收益；x：進展k個階段的消費時，在消費的第一個階段用于消費型產(chǎn)品的原料數(shù)量0 xa。在進展某階段消費時，當(dāng)前階段的收益為 xagxg2155分析該階段消費之后，總的回收原料的數(shù)量為

21、 它是在以后將要進展的k-1個階段消費的形狀變量的值，這些原料用于k-1個階段消費，采取最優(yōu)分配戰(zhàn)略所獲得的最大收益為)(21xarxrxrrarfxarxrfkk212121156分析根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理，當(dāng)2kn時，有 當(dāng)k=1時即只進展一個階段消費，有 顯然，我們的目的是計算fn(A) xarxrfxagxgxfkaxk211210max xagxgafax2101max57例在多階段消費安排問題中，設(shè)收益函數(shù)分別為回收率分別為消費階段數(shù)為n=3，現(xiàn)有原料為A=100噸。 xxgxxg5 . 06 . 0214 . 01 . 021rr58解：先整理一些算式 xaxaxxarxrxa

22、xaxxagxg3 . 04 . 0)(4 . 01 . 0)(1 . 05 . 0)(5 . 06 . 0212159當(dāng)k=1時 對于一個階段消費問題，最大收益為0.6a，最正確消費安排是：全部原料用于消費型產(chǎn)品； )(6 .01 .05 .0maxmax02101axaxaxagxgafaxax60當(dāng)k=2時 可知，當(dāng)進展兩個階段消費時，最大收益為0.74a最正確消費安排是：全部原料用于消費型產(chǎn)品； )0(74. 008. 074. 0max3 . 04 . 06 . 01 . 05 . 0maxmax002112102xaxaxaxaxarxrfxagxgafaxaxax61當(dāng)k=3時

23、可知，當(dāng)進展三個階段消費時，最大收益為0.796a最正確消費安排是：全部原料用于消費型產(chǎn)品； )0(796.0122.0796.0max3 .04 .074.01 .05 .0maxmax002122103xaxaxaxaxarxrfxagxgafaxaxax62將知數(shù)據(jù)代入上式得 即投入100噸原料進展三階段消費時，可獲得的最大收益為79.6萬元。此時，最正確消費安排是：第一階段k=3全部原料用于消費型產(chǎn)品；第二階段k=2全部原料用于消費型產(chǎn)品；第三階段k=1全部原料用于消費型產(chǎn)品； 萬元）(6 .79100796. 01003f63第一階段：把全部原料100噸投入型產(chǎn)品消費 收益=0.5*

24、100=50萬元，回收=0.4*100=40噸第二階段：把全部原料40噸投入型產(chǎn)品消費 收益=0.5*40=20萬元，回收=0.4*40=16噸第三階段：把全部原料16噸投入型產(chǎn)品消費 收益=0.6*16=9.6萬元，回收=0.1*16=1.6噸 三個階段總收益為：50+20+9.6=79.6萬元 每個階段消費安排644、多階段存儲問題 把一年或一段時間分為n個周期也稱階段，知倉庫的最大容量為w，第i個周期的需求量為ri，單位產(chǎn)品的購進費為ai，單位產(chǎn)品的周期保管費為bi。問：各個周期應(yīng)訂多少貨，才可以既滿足需求，又使n個周期總存儲費最小。假設(shè)：1、各個周期的訂貨在該周期末才干存儲，而各周期的

25、需求應(yīng)在該周期初給予滿足，而且不允許缺貨。2、第一個周期的初始存儲量z1為知，第n個周期的期末存儲量zn+1也為知。3、期初存儲量不低于本期需求量。 65例某個居民區(qū)每年四個季度對煤的需求量、該區(qū)煤場各個季度購進煤的單價和存儲煤的保管費用都列于下表。知煤場的最大容量為9百噸，每年年底都要求有8百噸煤的存儲，如今問，煤場應(yīng)如何安排各個季度的進煤量，才最合理。假設(shè)：1、各個周期的訂貨在該周期末才干存儲，而各周期的需求應(yīng)在該周期初給予滿足，而且不允許缺貨。2、第一個周期的初始存儲量z1為知，第n個周期的期末存儲量zn+1也為知。3、期初存儲量不低于本期需求量。單位第一季度第二季度第三季度第四季度需求

26、量 ri每百噸購買價 ai每百噸保管費 bi百噸千元千元840.5520.7530.763.50.666分析存儲問題的周期數(shù)n為一定數(shù)，故定購費在一年內(nèi)也是一個常數(shù)；又由于不允許短缺，所以可以不思索定購費與短缺費。這樣，總存儲費就等于購進費與保管費之和。設(shè)第i個周期的初始存儲量為zi，訂貨量為qii1,2,n，由假設(shè)知，有如下關(guān)系式成立： ) 3(0, 0)2(), 2 , 1() 1 (1iiiiiiiiqznirzwzrzq67分析令fk(z)=初始存儲量為z，還有k個周期，采取最優(yōu)戰(zhàn)略時的最低總存儲費。顯然，我們的目的是求fn(z1)。假設(shè)設(shè)第i個周期的初始存儲量為z，進貨量為q，由公式

27、12可知 1iirrzqw68分析再結(jié)合公式3知令得當(dāng)i=n時，有 即 1, 2 , 1,max1nizrroqzrwiiizrroezrwliiiii1,max,1, 2 , 1,nieqlii1nnzrzqzrzqnn169分析由“最優(yōu)化原理可得遞推公式： nklqerzqfzbqazfzrzqzbqazfknknknkknknknnnn, 2minmin1111111170解這是一個四階段的存儲問題，且z1=z5=8，w=9，由遞推公式，得其中 4 , 3 , 2minmin55515545441klqerzqfzbqazfzrzqzbqazfkkkkkkk4 , 3 , 29, 0max5565