第三節(jié) 動態(tài)規(guī)劃問題的一些例子

1、精品課程運籌學 3.1 最短路徑問題最短路徑問題 3.2 投資分配問題投資分配問題 3.3 背包問題背包問題 3.4 排序問題排序問題 精品課程運籌學 例一、從例一、從a 地到地到d 地要鋪設一條煤氣管道地要鋪設一條煤氣管道,其中需經過其中需經過 兩級中間站，兩點之間的連線上的數字表示距離，如兩級中間站，兩點之間的連線上的數字表示距離，如 圖所示。問應該選擇什么路線，使總距離最短？圖所示。問應該選擇什么路線，使總距離最短？ a b1 b2 c1 c2 c3 d 2 4 3 3 3 3 2 1 1 1 4 3.1 最短路徑問題最短路徑問題 精品課程運籌學 解：整個計算過程分三個階段，從最后一個階

2、段開始。解：整個計算過程分三個階段，從最后一個階段開始。 第一階段（第一階段（c d）：）： c 有三條路線到終點有三條路線到終點d 。 a b1 b2 c1 c2 c3 d 2 4 3 3 3 3 2 1 1 1 4 d c1 c2 c3 顯然有顯然有 f1 (c1 ) = 1 ； f1(c2 ) = 3 ； f1 (c3 ) = 4 精品課程運籌學 d( b1,c1 ) + f1 (c1 ) 3+1 f2 ( b1 ) = min d( b1,c2 ) + f1 (c2 ) = min 3+3 d( b1,c3 ) + f1 (c3 ) 1+4 4 = min 6 = 4 5 第二階段（第

3、二階段（b c）：）： b 到到c 有六條路線。有六條路線。 a b1 b2 c1 c2 c3 d 2 4 3 3 3 3 2 1 1 1 4 d c1 c2 c3 b1 b2 (最短路線為最短路線為b1c1 d) 精品課程運籌學 d( b2,c1 ) + f1 (c1 ) 2+1 f2 ( b2 ) = min d( b2,c2 ) + f1 (c2 ) = min 3+3 d( b2,c3 ) + f1 (c3 ) 1+4 3 = min 6 = 3 5 a b1 b2 c1 c2 c3 d 2 4 3 3 3 3 2 1 1 1 4 d c1 c2 c3 b1 b2 (最短路線為最短路線

4、為b2c1 d) 精品課程運籌學 第三階段（第三階段（ a b ）：）： a 到到b 有二條路線有二條路線。 f3(a)1 = d(a, b1 ) f2 ( b1 ) 246 f3 (a)2 = d(a, b2 ) f2 ( b2 ) 437 f3 (a) = min = min6,7=6 d(a, b1 ) f2 ( b1 ) d(a, b2 ) f2 ( b2 ) (最短路線為最短路線為ab1c1 d) a b1 b2 c1 c2 c3 d 2 4 3 3 3 3 2 1 1 1 4 d c1 c2 c3 b1 b2 a 精品課程運籌學 a b1 b2 c1 c2 c3 d 2 4 3 3

5、 3 3 2 1 1 1 4 d c1 c2 c3 b1 b2 a 最短路線為最短路線為 ab1c1 d 路長為路長為 6 精品課程運籌學 練習練習1： a b1 b2 c1 c2 c3 c4 d1 d2 d3 e1 e2 e3 f1 f2 g 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最優(yōu)路線為：最優(yōu)路線為：a b1 c2 d1 e2 f2 g 路長路長18 求從求從a到到g的最短路徑的最短路徑 3 精品課程運籌學 k=5k=5，出發(fā)點，出發(fā)點e1e1、e2e2、e3e3 7 35 43 min , , min 262

6、1 5 16115 fffed fffedu5(e1)=f1 e1 f1 g 5 32 45 min , , min 26225 16125 2 5 fffed fffed f e a b1 b2 c1 c2 c3 c4 d1 d2 d3 e1 e2 e3 f1 f2 g 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 )(15ef u5(e2)=f2 e2 f2 g 9 36 46 min , , min 26235 16135 3 5 fffed fffed f e u5(e3)=f2 e3 f2 g k=6k=6,f

7、1 g f f6 6(f1)=4(f1)=4 f f2 2 g ,f ,f6 6(f2)=3(f2)=3 精品課程運籌學 k=4，f4(d1)=7 u4(d1)=e2 f4(d2)=6 u4(d2)=e2 f4(d3)=8 u4(d3)=e2 k=2, f2(b1)=13 u2(b1)=c2 f2(b2)=16 u2(b2)=c3 f3(c1)=13 u3(c1)=d1 f3(c2)=10 u3(c2)=d1 f3(c3)=9 u3(c3)=d1 f3(c4)=12 u3(c4)=d3 k=3, = min f1(a)= min d1(a,b1)+ f2(b1) d1(a,b2)+ f2(b2

8、) 5+13 3+16 =18 k=1, u1(a)=b1u2(b1)=c2u3(c2)=d1u4(d1)=e2 精品課程運籌學 u1(a)=b1u2(b1)=c2u3(c2)=d1u4(d1)=e2 u5(e1)=f1 e1 f1 g u5(e2)=f2 e2 f2 g u5(e3)=f2 e3 f2 g 7 5 9 u5(e2)=f2 u6(f2)=g 最優(yōu)策略最優(yōu)策略 a b1 b2 c1 c2 c3 c4 d1 d2 d3 e1 e2 e3 f1 f2 g 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 精品課程運

9、籌學 求從求從a到到e的最短路徑的最短路徑 路線為路線為ab2c1 d1 e ，最短路徑為最短路徑為1919 a b2 b1 b3 c1 c3 d1 d2 e c2 5 2 14 112 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 練習練習2： 1 精品課程運籌學 現有數量為現有數量為a（萬元）的資金，計劃分配給（萬元）的資金，計劃分配給n 個工廠個工廠, 用于擴大再生產。用于擴大再生產。 假設：假設：xi 為分配給第為分配給第i 個工廠的資金數量（萬元）個工廠的資金數量（萬元） ； gi(xi)為第為第i 個工廠得到資金后提供的利潤值（萬元）。個工廠得到資金后提供

10、的利潤值（萬元）。 問題是如何確定各工廠的資金數，使得總的利潤為問題是如何確定各工廠的資金數，使得總的利潤為 最大。最大。 nix ax xgz i n i i n i ii .2.1 0 )(max 1 1 據此，有下式：據此，有下式： 3.2 投資分配問題投資分配問題 精品課程運籌學 令：令：fk(x) = 以數量為以數量為x 的資金分配給前的資金分配給前k 個工廠，所個工廠，所 得到的最大利潤值。得到的最大利潤值。 用動態(tài)規(guī)劃求解，就是求用動態(tài)規(guī)劃求解，就是求 fn(a) 的問題。的問題。 當當 k=1 時，時， f1(x) = g1(x) （因為只給一個工廠）（因為只給一個工廠） 當當

11、1kn 時，其遞推關系如下：時，其遞推關系如下： 設：設：y 為分給第為分給第k 個工廠的資金（其中個工廠的資金（其中 0y x ），此時），此時 還剩還剩 x y（萬元）的資金需要分配給前（萬元）的資金需要分配給前 k-1 個工廠個工廠,如如 果采取最優(yōu)策略，則得到的最大利潤為果采取最優(yōu)策略，則得到的最大利潤為fk 1(x y) ,因此因此 總的利潤為：總的利潤為： gk(y) fk 1(x y) 精品課程運籌學 nk yxfygxf kk xy k .3.2 )()(max)( 1 0 其其中中 如果如果a 是以萬元為資金分配單位，則式中的是以萬元為資金分配單位，則式中的y 只取只取 非負

12、整數非負整數0，1，2，x。上式可變?yōu)椋?。上式可變?yōu)椋?)()(max)( 1 ,2,1 ,0 yxfygxf kk xy k 所以，根據動態(tài)規(guī)劃的最優(yōu)化原理，有下式：所以，根據動態(tài)規(guī)劃的最優(yōu)化原理，有下式： 精品課程運籌學 例題：例題： 設國家撥給設國家撥給60萬元投資，供四個工廠擴建使用，每萬元投資，供四個工廠擴建使用，每 個工廠擴建后的利潤與投資額的大小有關，投資后的個工廠擴建后的利潤與投資額的大小有關，投資后的 利潤函數如下表所示。利潤函數如下表所示。 投資投資 利潤利潤 0102030405060 g1(x)0205065808585 g2(x)0204050556065 g3(x)

13、0256085100110115 g4(x)0254050606570 解：依據題意，是要求解：依據題意，是要求 f4(60) 。 精品課程運籌學 按順序解法計算。按順序解法計算。 第一階段：求第一階段：求 f1(x)。顯然有。顯然有 f1(x) g1(x)，得到下表，得到下表 投資投資 利潤利潤 0102030405060 f1(x) g1(x)0205065808585 最優(yōu)策略最優(yōu)策略0102030405060 第二階段：求第二階段：求 f2(x)。此時需考慮第一、第二個工廠如。此時需考慮第一、第二個工廠如 何進行投資分配，以取得最大的總利潤。何進行投資分配，以取得最大的總利潤。 )60

14、()(max)60( 12 60,10,0 2 yfygf y 精品課程運籌學 120 065 2060 5055 6550 8040 8520 850 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0( max 12 12 12 12 12 12 12 fg fg fg fg fg fg fg 最優(yōu)策略為（最優(yōu)策略為（40，20），此時最大利潤為），此時最大利潤為120萬元。萬元。 同理可求得其它同理可求得其它 f2(x) 的值。的值。 精品課程運籌學 105 )0()50( )10()40( )20()30( )

15、30()20( )40()10( )50()0( )50()(max)50( 12 12 12 12 12 12 12 50,10,0 2 fg fg fg fg fg fg yfygf y 最優(yōu)策略為（最優(yōu)策略為（30，20），此時最大利潤為），此時最大利潤為105萬元。萬元。 精品課程運籌學 90 )40()(max)40( 12 40,10,0 2 yfygf y 最優(yōu)策略為（最優(yōu)策略為（20，20），此時最大利潤為），此時最大利潤為90萬元。萬元。 70 )30()(max)30( 12 30,20,10,0 2 yfygf y 最優(yōu)策略為（最優(yōu)策略為（20，10），此時最大利潤為），

16、此時最大利潤為70萬元。萬元。 精品課程運籌學 50 )20()(max)20( 12 20,10,0 2 yfygf y 20 )10()(max)10( 12 ,10,0 2 yfygf y 最優(yōu)策略為（最優(yōu)策略為（10，0）或（）或（ 0 ， 10 ） ，此時最大利潤，此時最大利潤 為為20萬元。萬元。 f2(0) 0。最優(yōu)策略為（最優(yōu)策略為（0，0），最大利潤為），最大利潤為0萬元。萬元。 得到下表得到下表 最優(yōu)策略為（最優(yōu)策略為（20，0），此時最大利潤為），此時最大利潤為50萬元。萬元。 精品課程運籌學 投資投資 利潤利潤 0102030405060 f2(x)0205070901

17、05120 最優(yōu)策略最優(yōu)策略(0,0)(10,0) (0,10) (20,0)(20,10)(20,20)(30,20) (40,20) 第三階段：求第三階段：求 f3(x)。此時需考慮第一、第二及第三個。此時需考慮第一、第二及第三個 工廠如何進行投資分配，以取得最大的總利潤。工廠如何進行投資分配，以取得最大的總利潤。 )60()(max)60( 23 60,10,0 3 yfygf y 精品課程運籌學 155 0115 20110 50100 7085 9060 10525 1200 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()1

18、0( )60()0( max 23 23 23 23 23 23 23 fg fg fg fg fg fg fg 最優(yōu)策略為（最優(yōu)策略為（20，10，30），最大利潤為），最大利潤為155萬元。萬元。 同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表 精品課程運籌學 投資投資 利潤利潤 0102030405060 f3(x)0256085110135155 最優(yōu)最優(yōu) 策略策略 (0,0,0)(0,0,10)(0,0,20)(0,0,30) (20,0,20)(20,0,30)(20,10,30) 第四階段：求第四階段：求 f4(60)。即問題的最優(yōu)策略。即問題的最優(yōu)策略。

19、 )60()(max)60( 34 60,10,0 4 yfygf y 精品課程運籌學 160 070 2565 6060 8550 11040 13525 1550 max )0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0( max 34 34 34 34 34 34 34 fg fg fg fg fg fg fg 最優(yōu)策略為（最優(yōu)策略為（20，0，30，10），最大利潤為），最大利潤為160萬元。萬元。 精品課程運籌學 練習：練習： 求投資分配問題得最優(yōu)策略，其中求投資分配問題得最優(yōu)策略，其中a50 萬元，其余萬元，其余

20、 資料如表所示。資料如表所示。 投資投資 利潤利潤 01020304050 g1(x)02140528085 g2(x)015365073100 g3(x)02560656870 精品課程運籌學 例：某公司打算在例：某公司打算在3個不同的地區(qū)設置個不同的地區(qū)設置4個銷售點，個銷售點， 根據市場部門估計，在不同地區(qū)設置不同數量的銷根據市場部門估計，在不同地區(qū)設置不同數量的銷 售點每月可得到的利潤如表所示。試問在各地區(qū)如售點每月可得到的利潤如表所示。試問在各地區(qū)如 何設置銷售點可使每月總利潤最大。何設置銷售點可使每月總利潤最大。 地地 區(qū)區(qū) 銷售點銷售點 01234 1 2 3 0 0 0 16

21、12 10 25 17 14 30 21 16 32 22 17 x1=2，x2=1，x3=1，f3(4)=47 精品課程運籌學 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其可攜帶物品重量的限度為a 公公 斤，設有斤，設有n 種物品可供他選擇裝入包中。已知每種物品種物品可供他選擇裝入包中。已知每種物品 的重量及使用價值（作用），問此人應如何選擇攜帶的重量及使用價值（作用），問此人應如何選擇攜帶 的物品（各幾件），使所起作用（使用價值）最大？的物品（各幾件），使所起作用（使用價值）最大？ 物品物品 1 2 j n 重量（公斤重量（公斤/ /件）件） a1 a2 aj an 每件

22、使用價值每件使用價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、這就是背包問題。類似的還有工廠里的下料問題、 運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題 等。等。 3.3 背包問題背包問題 精品課程運籌學 設設xj 為第為第j 種物品的裝件數（非負整數）則問題的數學種物品的裝件數（非負整數）則問題的數學 模型如下：模型如下： ). 2 . 1(0 max 1 njx axa xcz j n ij jj n j jj 且且為為整整數數 用動態(tài)規(guī)劃方法求解，令用動態(tài)規(guī)劃方法求解，令 fx(y) = 總重量不超過總重量不超過

23、 y 公斤，包中只裝有前公斤，包中只裝有前k 種物品種物品 時的最大使用價值。時的最大使用價值。 其中其中y 0， k 1,2, , n 。所以問題就是求所以問題就是求 fn(a) 精品課程運籌學 其遞推關系式為：其遞推關系式為： nk xayfxcyf kkkkk a y x k k k 2 )(max)( 1 0 其其中中 當當 k=1 時，有：時，有： 的的最最大大整整數數表表示示不不超超過過其其中中 11 1 1 1 11 , )( a y a y a y x a y cyf 精品課程運籌學 例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解 且且為為整整數數0, 5523 12

24、58max 321 321 321 xxx xxx xxxz 物品物品 1 2 3 重量（公斤）重量（公斤） 3 2 5 使用價值使用價值 8 5 12 解：解：a5 ，問題是求，問題是求 f3(5) )55(12max)5( 323 5 0 3 3 3 3 xfxf x a x 整整數數 精品課程運籌學 )1()0( 22 323 10 323 5 5 0 323 5 0 3 33 3 3 3 3 3 3 )0(12),5(0max )55(12max )55(12max )55(12max)5( xx x x x x a x ff xfx xfx xfxf ， 整整數數 整整數數 精品課程

25、運籌學 5 5 )( 2)1()0( 111 212 2, 10 212 2 5 0 212 5 0 2 222 2 2 2 2 2 2 )1(10),3(5),5(0max )25(max )25(max )25(5max)5( xxx x x x x a x fff xfx xfx xfxf ， 整數整數 整數整數 精品課程運籌學 )0()0(0max )20(max )20(max )20(5max)0( 1 )0( 1 212 0 212 2 0 0 212 0 0 2 2 2 2 2 2 2 2 ff xfx xfx xfxf x x x x x a x 5 5 整數整數 整數整數

26、精品課程運籌學 )0(0 3 0 8)0( )0(0 3 1 8)1( )1(8 3 3 8)3( )1(8 3 5 8)5( 1111 1111 1111 1111 xxcf xxcf xxcf xxcf ) 1, 1(1310, 85, 8max ) 1 (10),3(5),5(0max)5( 21 2)1()0( 1112 222 xx ffff xxx )( 精品課程運籌學 )0, 0(0)0()0(0max)0( 211 )0( 12 2 xxfff x )0,1,1(13 012,130max )0(12),5(0max)5( 321 )1()0( 223 33 xxx fff x

27、x 所以，最優(yōu)解為所以，最優(yōu)解為 x（1 . 1 . 0），），最優(yōu)值為最優(yōu)值為 z = 13。 精品課程運籌學 練習練習1：某廠生產三種產品，各種產品重量與利：某廠生產三種產品，各種產品重量與利 潤的關系如表所示?，F將此三種產品運往市場出售，潤的關系如表所示。現將此三種產品運往市場出售， 運輸能力總重量不超過運輸能力總重量不超過 6 噸，問如何安排運輸，使噸，問如何安排運輸，使 總利潤最大？總利潤最大？ 種類種類 1 2 3 重量（噸重量（噸/ /公斤）公斤） 2 3 4 單件利潤（元）單件利潤（元） 80 130 180 最優(yōu)方案：最優(yōu)方案：x1 = =（0.2.00.2.0）x2 = =

28、（1.0.11.0.1）z=260=260 精品課程運籌學 練習練習2：求下列問題的最優(yōu)解：求下列問題的最優(yōu)解 且且為為整整數數0, 10543 654max 321 321 321 xxx xxx xxxz x=(2. 1. 0) 最優(yōu)值為最優(yōu)值為 z = 13 精品課程運籌學 排序問題指排序問題指n 種零件經過不同設備加工是的順序問題。種零件經過不同設備加工是的順序問題。 其目的是使加工周期為最短。其目的是使加工周期為最短。 1、n 1 排序問題排序問題 即即n 種零件經過種零件經過1 種設備進行加工，如何安排？種設備進行加工，如何安排？ 14682023 交貨日期（交貨日期（d） 451

29、73 加工時間（加工時間（t） 零件代號零件代號 2 j 1 j 3 j 4 j 5 j 例一、例一、 3.4 排序問題排序問題 精品課程運籌學 （1）平均通過設備的時間最小）平均通過設備的時間最小 按零件加工時間非負次序排列順序，其時間最小。（即按零件加工時間非負次序排列順序，其時間最小。（即 將加工時間由小到大排列即可）將加工時間由小到大排列即可） 1 j 2 j 3 j 4 j 5 j零件加工順序零件加工順序 工序時間工序時間 13457 實際通過時間實際通過時間1481320 交貨時間交貨時間82314620 平均通過時間平均通過時間2 .9)1481320( 5 1 x 精品課程運籌學 延遲時間延遲時間 = 13 6 = 7 （2）按時交貨排列順序）按時交貨排列順序 1 j 2 j 3 j 4 j5 j零件加工順序零件加工順序 工序時間工序時間 13457 實際通過時間實際通過時間56101720 交貨時間交貨時間82314620 平均通過時間平均通過時間6 .11)56101720( 5 1 x 延遲時間延遲時間 = 0 精品課程運