1、1第十章第十章 動態(tài)規(guī)劃應用舉例動態(tài)規(guī)劃應用舉例2 第一節(jié)第一節(jié) 一維資源分配問題一維資源分配問題一、一、一維資源分配問題基本模型及求解方法一維資源分配問題基本模型及求解方法1. 1. 模型模型 設有某種原料，總數(shù)量為設有某種原料，總數(shù)量為a，用于生產，用于生產n中產品。若分配數(shù)中產品。若分配數(shù)量量xi用于生產第用于生產第i 種產品，其收益為種產品，其收益為gi(xi)。問應如何分配，才能。問應如何分配，才能使生產使生產n種產品的總收入最大？種產品的總收入最大？此問題可寫成靜態(tài)規(guī)劃問題：此問題可寫成靜態(tài)規(guī)劃問題：nixaxxxtsxgxgxgMaxZinnn, 2 , 10.)()()(212

2、211 3 在應用動態(tài)規(guī)劃處理這類在應用動態(tài)規(guī)劃處理這類“靜態(tài)規(guī)劃靜態(tài)規(guī)劃”問題時，通常以把問題時，通常以把資源分配給一個或幾個使用者的過程作為一個階段，把問題中資源分配給一個或幾個使用者的過程作為一個階段，把問題中的變量的變量xi作為決策變量，將累計的量或隨遞推過程變化的量選作為決策變量，將累計的量或隨遞推過程變化的量選為狀態(tài)變量。為狀態(tài)變量。 當當gi(xi)都是線性函數(shù)時，它是一個線性規(guī)劃問題；當都是線性函數(shù)時，它是一個線性規(guī)劃問題；當gi(xi)不是線性函數(shù)時，它是一個非線性規(guī)劃問題。但當不是線性函數(shù)時，它是一個非線性規(guī)劃問題。但當n較大時，較大時，具體求解是比較麻煩的。然而，由于這類

3、問題的特殊結構，可具體求解是比較麻煩的。然而，由于這類問題的特殊結構，可以將它看成一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關系以將它看成一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關系來解。來解。42. 求解方法求解方法 設狀態(tài)變量設狀態(tài)變量sk表示分配用于生產第表示分配用于生產第k種產品至第種產品至第n產品的產品的原料數(shù)量。則原料數(shù)量。則s1 =a，可用逆推法求解。，可用逆推法求解。 設決策變量設決策變量uk表示分配給生產第表示分配給生產第k種產品的原料數(shù)量，種產品的原料數(shù)量，即即: uk = xk狀態(tài)轉移方程：狀態(tài)轉移方程：kkkkkxsuss 1允許決策集合：允許決策集合：0|)(kkkkk

4、ksxuusD 把該分配問題看成是對資源總量的消耗過程。把該分配問題看成是對資源總量的消耗過程。5 令最優(yōu)值函數(shù)令最優(yōu)值函數(shù)fk(sk)表示以數(shù)量為表示以數(shù)量為sk的原料分配給第的原料分配給第k種產品種產品至第至第n種產品所得到的最大總收入。遞推關系式為：種產品所得到的最大總收入。遞推關系式為：0)(1 , 1,)()(max)(1110 nnkkkkksxkksfnnkxsfxgsfkk利用這個遞推關系式進行逐段計算，最后求得最大總收入為利用這個遞推關系式進行逐段計算，最后求得最大總收入為f1(a)6例例1 某公司有某公司有9個推銷員在全國三個不同市場推銷貨個推銷員在全國三個不同市場推銷貨物

5、，這三個市場里推銷人員數(shù)與收益的關系如下表，物，這三個市場里推銷人員數(shù)與收益的關系如下表，試作出使總收益最大的分配方案試作出使總收益最大的分配方案。 31,11)(max)(321iixxxxdsf解：設分配人員的順序為市場解：設分配人員的順序為市場1, 2, 3，已知已知 s1=9，用逆推法。，用逆推法。 設設 sk 為第為第k階段尚未分配的人員數(shù)，階段尚未分配的人員數(shù)， xk 為第為第k階段分配的推階段分配的推銷人員數(shù)。則銷人員數(shù)。則狀態(tài)轉移方程為狀態(tài)轉移方程為 sk1=sk xk 目標函數(shù)為目標函數(shù)為 推推銷銷員員市市場場012345678912032475766718290100 11

6、02405060718293104 115 125 13535061728497109 120 131 140 150二、離散的二、離散的一維資源分配問題一維資源分配問題7第三階段：給第三市場分配第三階段：給第三市場分配 s3 有有09種可能，第三階段最優(yōu)決策表如下種可能，第三階段最優(yōu)決策表如下： x3 s3 0 1 2 3 4 5 6 7 8 9 x3* f3* 0 50 0 50 1 50 61 1 61 2 50 61 72 2 72 3 50 61 72 84 3 84 4 50 61 72 84 97 4 97 5 50 61 72 84 97 109 5 109 6 50 61 7

7、2 84 97 109 120 6 120 7 50 61 72 84 97 109 120 131 7 131 8 50 61 72 84 97 109 120 131 140 8 140 9 50 61 72 84 97 109 120 131 140 150 9 150 8第二階段：給第二市場分配第二階段：給第二市場分配 s2 有有09種可能，第二階段最優(yōu)決策表如下種可能，第二階段最優(yōu)決策表如下： x2 s2 0 1 2 3 4 5 6 7 8 9 x2* f2* 0 90 0 90 1 101 100 0 101 2 112 111 110 0 112 3 124 122 121 12

8、1 0 124 4 137 134 132 132 132 0 137 5 149 147 144 143 143 143 0 149 6 160 159 157 155 154 154 154 0 160 7 171 170 169 168 166 165 165 165 0 171 8 180 181 180 180 179 177 176 176 175 1 181 9 190 190 191 191 191 190 188 187 186 185 2,3,4 191 s3 9 8 7 6 5 4 3 2 1 0 s3 0 1 2 3 4 5 6 7 8 9 x3* 0 1 2 3 4

9、5 6 7 8 9 f3* 50 61 72 84 97 109 120 131 140 150 狀態(tài)轉移方程：狀態(tài)轉移方程： s3=s2 x29 第一階段：給第一市場分配第一階段：給第一市場分配 由邊界條件由邊界條件 s1=9，第一階段最優(yōu)決策表如下，第一階段最優(yōu)決策表如下： x1 s1 0 1 2 3 4 5 6 7 8 9 x1* f1* 9 211 213 218 217 215 208 206 202 201 200 2 218 s20123456789x2*0000000012,3,4f2*90 101 112 124 137 149 160 171 181191得決策過程：得決策

10、過程：x1*=2, x2*=0, x3*=7, f1*=218即即 市場市場1 分配分配 2人，市場人，市場2 不分配不分配 ，市場，市場3 分配分配 7人，人，最大收益為最大收益為218萬元。萬元。狀態(tài)轉移方程：狀態(tài)轉移方程： s2=s1 x110三、連續(xù)的三、連續(xù)的一維資源分配問題一維資源分配問題1. 問題的提出問題的提出 在資源分配問題中，還有一類要考慮資源回收利用問題，這里在資源分配問題中，還有一類要考慮資源回收利用問題，這里決策變量為連續(xù)值，故稱為資源連續(xù)分配問題。這類問題一般描決策變量為連續(xù)值，故稱為資源連續(xù)分配問題。這類問題一般描述如下：述如下： 設有數(shù)量為設有數(shù)量為s1的某種資

11、源，可投入的某種資源，可投入A和和B兩種生產。兩種生產。 第一年若以數(shù)量第一年若以數(shù)量u1投入生產投入生產A，剩下的，剩下的量量s1-u1就投入生產就投入生產B，則可得收入為則可得收入為g(u1)+h(s1-u1)，其中，其中g(u1)和和h(u1)為已知函數(shù)，且為已知函數(shù)，且g(0)= h(0)=0 。 這種資源在投入生產這種資源在投入生產A、B后，年終還可回收再投入生產。設后，年終還可回收再投入生產。設年回收率分別為年回收率分別為0a1和和0b1，則在第一年生產后，回收的資源，則在第一年生產后，回收的資源量合計量合計為為s2=au1+b(s1-u1)。 第二年再將資源數(shù)量第二年再將資源數(shù)量

12、s2按按u2和和s2-u2分別投入分別投入A、B兩種生產，如兩種生產，如此繼續(xù)此繼續(xù)n年，試問：應當如何決定每年投入年，試問：應當如何決定每年投入A生產的資源量生產的資源量u1，u2，un，才能使總收入最大？，才能使總收入最大？ 112. 基本模型基本模型nisuusbaususbaususbausushugushugMaxZiinnnnnnn, 2 , 10)()()()()()()(122231112111 3. 求解方法求解方法設狀態(tài)變量設狀態(tài)變量sk表示第表示第k階段可投入階段可投入A和和B兩種生產的資源量；兩種生產的資源量；決策變量決策變量uk表示第表示第k階段可投入階段可投入A生產

13、的資源量，則生產的資源量，則sk uk為可投為可投入入B生產的資源量。生產的資源量。已知已知 s1，可用逆推法求解。，可用逆推法求解。 12狀態(tài)轉移方程：狀態(tài)轉移方程：)(1kkkkusbaus 令最優(yōu)值函數(shù)令最優(yōu)值函數(shù)fk(sk)表示以數(shù)量為表示以數(shù)量為sk的資源量分配給第的資源量分配給第k階段至第階段至第n階段所得到的最大總收入。階段所得到的最大總收入。遞推關系式為：遞推關系式為：1 ,2,1,0)()()()(max)(1110 nnksfusbaufushugsfnnkkkkkkksukkkk最后求得最大總收入為最后求得最大總收入為f1(s1)。13例例2 機器負荷分配問題機器負荷分配

14、問題(書書P253)解解：設狀態(tài)變量設狀態(tài)變量sk表示第表示第k年度初擁有的完好機器數(shù)量，同時表年度初擁有的完好機器數(shù)量，同時表示第示第k1年度末擁有的完好機器數(shù)量。年度末擁有的完好機器數(shù)量。設決策變量設決策變量uk表示第表示第k年度中分配高負荷下生產的機器數(shù)年度中分配高負荷下生產的機器數(shù)量，則量，則sk uk為該年度中分配低負荷下生產的機器數(shù)量。為該年度中分配低負荷下生產的機器數(shù)量。狀態(tài)轉移方程：狀態(tài)轉移方程：)( 9 . 07 . 0)(1kkkkkkkusuusbaus 允許決策集合：允許決策集合：0|)(kkkkkksxuusD 141 ,2,50)()(9.07.0)(58max)(

15、661)( ksfusufususfkkkkkkksDukkkkk 515, 1),(kkkkusvV令最優(yōu)值函數(shù)令最優(yōu)值函數(shù)fk(sk)表示以資源量表示以資源量sk出發(fā)，從第出發(fā)，從第k年開始至第年開始至第5年結年結束時，生產的產品最大值。遞推關系式為：束時，生產的產品最大值。遞推關系式為：設設vk(sk , uk)為第為第k年度的產量，則年度的產量，則vk 8 uk 5(sk uk)故指標函數(shù)為：故指標函數(shù)為：15當當k=5時，有時，有53max)(58max)(9.07.0)(58max)(55055505556555055555555suusuusufususfsususu 求得最大解

16、：求得最大解：5555*58)(,ssfsu 相應的，有相應的，有4444*46 .13)(,ssfsu 3333*35 .17)(,ssfsu 222*28 .20)(, 0ssfu 111*17 .23)(, 0ssfu 因因10001 s，故最高產量為，故最高產量為23700)(11 sf（臺）（臺）補充作業(yè)補充作業(yè)14 若計劃期結束時完好的機器臺數(shù)為若計劃期結束時完好的機器臺數(shù)為500臺，應臺，應如何安排生產使產量最大？如何安排生產使產量最大？16 第二節(jié)第二節(jié) 生產與存貯問題生產與存貯問題一、一、生產計劃問題生產計劃問題1. 問題的提出問題的提出 設某公司要制定一設某公司要制定一項項

17、n個階段的生產計劃。已知初始庫存?zhèn)€階段的生產計劃。已知初始庫存為零，每階段該產品的生產量有上限的限制；每階段社會對為零，每階段該產品的生產量有上限的限制；每階段社會對該產品的需求量是已知的，在該產品的需求量是已知的，在n階段末庫存為零。問該公司階段末庫存為零。問該公司如何制定每個階段的生產計劃，使產品總成本最低。如何制定每個階段的生產計劃，使產品總成本最低。設設dk為第為第k階段對產品的需求量，階段對產品的需求量，xk為第為第k階段該產品的階段該產品的生產量，生產量，sk1為為k階段末的產品庫存量。則有階段末的產品庫存量。則有 sk1 sk xk dk由此可見，過程演化方向由由此可見，過程演化

18、方向由s1至至 sn1 。2. 基本模型基本模型17 設設ck(xk)表示第表示第k階段生產量階段生產量xk的成本費用，它包括生產準備的成本費用，它包括生產準備成本成本K和產品成本和產品成本axk(a是單位產品成本是單位產品成本)兩項費用兩項費用 ，hk(sk )為第為第k階段開始時有產品庫存量階段開始時有產品庫存量sk 所需的存貯費用。故所需的存貯費用。故k階段的成本階段的成本費用為費用為ck(xk) hk(sk)。m表示每階段最多能生產該產品的上限數(shù)表示每階段最多能生產該產品的上限數(shù)量。量。因而，上述問題的模型為因而，上述問題的模型為nkxnkmxnkdxssstsshxcMinGkkkj

19、jjknnkkkkk,2 , 1,2 , 101,2 , 1)(0,0.)()(11111 為為整整數(shù)數(shù)18nnkdxsskkkk, 1, 2 , 11 根據動態(tài)規(guī)劃求解規(guī)則，采用逆推法，遞推關系式：根據動態(tài)規(guī)劃求解規(guī)則，采用逆推法，遞推關系式：1 ,1,)()()(min)(1121 nnksfshxcsfkkkkkkxkkkkk 邊界條件為：邊界條件為：0)(11 nnsf用動態(tài)規(guī)劃方法求解如下：用動態(tài)規(guī)劃方法求解如下：由于過程演化方向由由于過程演化方向由s1至至 sn1 ，則其狀態(tài)轉移方程：，則其狀態(tài)轉移方程：問題的關鍵是確定問題的關鍵是確定 sk 和和 xk 的取值范圍。的取值范圍。

20、從邊界條件出發(fā)，利用這個遞推關系式進行計算，對每個從邊界條件出發(fā)，利用這個遞推關系式進行計算，對每個k計計算算fk(sk) 的值，最后求得的值，最后求得f1(0)即為所求最小總費用。即為所求最小總費用。19xk 的取值范圍的取值范圍：sk 的取值范圍的取值范圍：下限為：下限為0；上限為；上限為)0,min(1 knkjjdmdmdk 1 表示表示k1階段生產時的最大庫存量，如果不生產則階段生產時的最大庫存量，如果不生產則庫存量更小。這是由生產與存貯問題的特性決定的，即庫存量更小。這是由生產與存貯問題的特性決定的，即k1階段進行生產的條件是該階段初的庫存一定為零，而一旦進階段進行生產的條件是該階

21、段初的庫存一定為零，而一旦進行生產則盡可能按最大生產能力生產。行生產則盡可能按最大生產能力生產。:1k 下下限限0)1( kxkkkkkkksdxdxss 0)2(1由由), 0max(1kkksd 20:2k 上上限限mxk )1(kkkkkkkkkkkdssxsdsdxss 111max)2(達達最最大大時時不不變變的的情情況況下下，當當、在在知知：由由)max,min(12kkkkdssm 21例例3 某工廠生產某種產品的月生產能力為某工廠生產某種產品的月生產能力為6件，已知今后四個月的件，已知今后四個月的每批產品的固定成本和單位產品成本分別為每批產品的固定成本和單位產品成本分別為3千元

22、、千元、1千元。如果本千元。如果本月產量超過銷售量時，可以存儲起來備以后各月銷售，一件產品的月產量超過銷售量時，可以存儲起來備以后各月銷售，一件產品的月存儲費為月存儲費為0.5千元，試安排月生產計劃并做到：千元，試安排月生產計劃并做到： 1、保證滿足每月的銷售量，并規(guī)定計劃期初和期末庫存為零；、保證滿足每月的銷售量，并規(guī)定計劃期初和期末庫存為零； 2、在生產能力允許范圍內，安排每月生產量計劃使產品總成本、在生產能力允許范圍內，安排每月生產量計劃使產品總成本(即生產費用加存儲費即生產費用加存儲費)最低。最低。3. 實例實例(P263 例例3)月份月份階段階段k月銷售量月銷售量dk月初庫存月初庫存

23、sk月末庫存月末庫存sk+1112s1 0s2223s2s3332s3s4444s4s5 022設設xk為第為第k階段生產量，則有階段生產量，則有k階段生產成本：階段生產成本： 6601300)(kkkkkkxxxxxck階段存貯成本：階段存貯成本： kkkssh5 . 0)( 則則k階段總成本：階段總成本： )()(kkkkshxc 4 , 3 , 2 , 11 kdxsskkkk狀態(tài)轉移方程：狀態(tài)轉移方程：采用逆推法，遞推關系式：采用逆推法，遞推關系式：1 ,2,3,4)()()(min)(1121 ksfshxcsfkkkkkkxkkkkk 邊界條件為：邊界條件為：0)(55 sf23k

24、=4 4)26 , 4min(),min(344 dmdjjs4的上限：的上限： 所以，所以， s4 0,4。x4的取值范圍：的取值范圍： )4 , 0max(), 0max(44414ssd )4 , 6min()max,min(444524sdssm 44044 xs當當33144 xs當當22244 xs當當11344 xs當當00444 xs當當24)4()()(min)(44544444424414 xsfshxcsfx x4s401234x4*f4(s4)07.047.016.536.526.026.035.515.542.002.025k=3 3)36 , 6min(),min(

25、243 dmdjjs3的上限：的上限： 所以，所以， s3 0,3。x3的取值范圍：的取值范圍： )2 , 0max(), 0max(33313ssd )6 , 6min()max,min(333423sdssm 62033 xs當當51133 xs當當40233 xs當當30333 xs當當26)2()()(min)(33433333323313 xsfshxcsfx x3s30123456x3*f3(s3)012.012.513.013.511.0611.0111.512.012.513.010.5510.528.011.512.012.510.008.038.011.512.09.508

26、.027k=2 4)26 , 9min(),min(142 dmdjjs2的上限：的上限： 所以，所以， s2 0,4。x2的取值范圍：的取值范圍： )3 , 0max(), 0max(22212ssd )6 , 6min()max,min(222322sdssm 63022 xs當當52122 xs當當41222 xs當當30322 xs當當20422 xs當當28)3()()(min)(22322222222212 xsfshxcsfx x2s20123456x2*f2(s2)017.017.516.017.0516.0116.517.015.516.5415.5216.016.515.0

27、16.0315.5312.516.014.515.5012.5412.514.015.0012.529k=1 s10 x1的取值范圍：的取值范圍： )2 , 0max(), 0max(11111ssd )6 , 6min()max,min(111221sdssm 62021 xs)2()()(min)(11211111121111 xsfshxcsfx x1s123456x1*f1(s1)021.021.522.020.521.5520.5逆計算過程反推得：逆計算過程反推得：x1* =5, x2* =0 , x3* =6, x4* =0這類庫存問題的特征：這類庫存問題的特征：si xi =03

28、0二、二、不確定性采購問題不確定性采購問題例例4 (P269 例例6) 某工廠生產上需要在近五周內采購一批原料，某工廠生產上需要在近五周內采購一批原料，而估計在未來五周內價格有波動，其浮動價格和概率已測得如而估計在未來五周內價格有波動，其浮動價格和概率已測得如下表。試求在哪一周以什么價格購入，使其價格的數(shù)學期望值下表。試求在哪一周以什么價格購入，使其價格的數(shù)學期望值最小，并求出期望值。最小，并求出期望值。解解: 這里價格是一個隨機變量，是按某種已知的概率分這里價格是一個隨機變量，是按某種已知的概率分布取值的。按采購期限布取值的。按采購期限5周分為周分為5個階段，將每周的價格個階段，將每周的價格

29、看作該階段的狀態(tài)。看作該階段的狀態(tài)。31yk為狀態(tài)變量，表示第為狀態(tài)變量，表示第k周的實際價格。周的實際價格。xk為決策變量，當為決策變量，當xk1表示表示第第k周采購，當周采購，當xk0，不采購。，不采購。ykE表示第表示第k周決定等待，而在以后采取最優(yōu)決策時采購價格的周決定等待，而在以后采取最優(yōu)決策時采購價格的期望值。期望值。 fk(yk)表示第表示第k周實際價格為周實際價格為yk時，從第時，從第k周到第周到第5周最優(yōu)決策的周最優(yōu)決策的期望值。期望值。 逆序遞推關系為：逆序遞推關系為：kEkkkkkkkkkkkkkEkkkkEkkkyyfxyyfxfffyEfykSSyyyfSyyyyf )(0)(1)700(4 . 0)600(3 . 0)500(3 . 0)(5 , 2 , 1700,600,500)(,min)(1111155555（不采購）（不采購）（采購）（采購）(1)32從最后一周，向前遞推：從最后一周，向前遞推：k=5時，因時，因700)700(,600)600(,500)500(,)(55555555 fffSyyyf即在第五周，若所需的原料尚未買入，無論價格多少，都必須采購。即在第五周，若所需的原料尚未買入，無論價格多少