《動 態(tài) 規(guī) 劃PPT課件》由會員分享，可在線閱讀，更多相關《動 態(tài) 規(guī) 劃PPT課件（75頁珍藏版）》請在裝配圖網上搜索。

1、1動態(tài)規(guī)劃模型 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。多階段決策問題，是指一個問題可以分為若干個階段，每一階段需要作出決策，而一個階段的決策，常常會影響下一個階段的決策。要在各個階段決定一個最優(yōu)決策，使整個系統達到最佳的效果。第1頁/共75頁2 設某一個公司要鋪設管道，從下圖中的設某一個公司要鋪設管道，從下圖中的A A點出發(fā)，點出發(fā)，經過經過B B、C C等處，最后到達等處，最后到達D D點。從點。從A A到到D D有很多路有很多路線可以選擇，各點之間的距離如下圖中所示，線可以選擇，各點之間的距離如下圖中所示，問該公司應該選擇哪一條路線，使從問該公司應該選擇哪一條路線，使從A A到到D

2、 D的總的總的鋪設管道距離最短。的鋪設管道距離最短。A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1例1 最短路線問題第2頁/共75頁3先引入幾個概念狀態(tài)每一階段的起點位置決策由一個狀態(tài)變到另一個狀態(tài)的選擇xk第K階段的狀態(tài)，稱為狀態(tài)變量uk(xk) 從xk 出發(fā)所作出的決策，稱為決策變量狀態(tài)轉移方程xxk+1k+1=T=Tk k(x(xk k,u,uk k(x(xk k)d(x(xk k,x,xk+1k+1)從狀態(tài)x xk k出發(fā)，轉移到狀態(tài)x xk+1k+1的效益f(x(xk k)從狀態(tài)x xk k出發(fā)到終點的最優(yōu)效益第3頁/共75頁4最短

3、路問題的動態(tài)規(guī)劃最優(yōu)化原理 假設一條最短路線經過狀態(tài)xk，那么，這條路線上從xk到終點的一段，是從xk出發(fā)到終點的所有路線中最短的。第4頁/共75頁5逆序法（回溯法） 從后向前逐步求出各點到終點的最佳路線，最后得到由起點到終點的最短路線。0)(1, 2, 1),(min)(NfNijfcifijj最短路問題的動態(tài)規(guī)劃模型，歸納為下述遞推公式：第5頁/共75頁643, 143,243, 34()02.3( 1)()1 01( 2)()303( 3)()404D CD CD CfDkf CrfDf CrfDf CrfD 1.從最后一段開始,k=4第6頁/共75頁71, 131, 2321, 332

4、, 132, 2322, 333.2( 1)3 1( 1)min( 2)min 3 34( 3)1 4( 1)2 1( 2)min( 2)min 3 33( 3)1 4B CB CB CB CB CB Ckrf CfBrf Crf Crf CfBrf Crf C第7頁/共75頁81,212,24.1( 1)2 4( ) minmin6( 2)4 3B AB Akrf BfArf B最短路徑：AB1C1D最短距離：6第8頁/共75頁9A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1Model:sets:cities/a,b1,b2,c1,c2,c

5、3,d/:f;roads(cities,cities)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:d;Endsets第9頁/共75頁10data:d=2 4 3 3 1 2 3 1 1 3 4;f= , , , , , ,0;enddatan=size(cities);for(cities(i)|i#lt#n: f(i)=min(roads(i,j): f(j)+d(i,j););end第10頁/共75頁11 Feasible solution found at iteration: 0 Variable Val

6、ue N 7.000000 F( A) 6.000000 F( B1) 4.000000 F( B2) 3.000000 F( C1) 1.000000 F( C2) 3.000000 F( C3) 4.000000 F( D) 0.000000 D( A, B1) 2.000000 D( A, B2) 4.000000 D( B1, C1) 3.000000 D( B1, C2) 3.000000 D( B1, C3) 1.000000 D( B2, C1) 2.000000 D( B2, C2) 3.000000 D( B2, C3) 1.000000 D( C1, D) 1.000000

7、 D( C2, D) 3.000000 D( C3, D) 4.000000第11頁/共75頁12圖論與網絡模型第12頁/共75頁13定義有序二元組G= (V,E )稱為一個圖.圖的定義圖的定義第13頁/共75頁14定義定義若將圖 G 的每一條邊 e 都對應一個實數 w(e)，稱 w(e)為邊的權權，并稱圖 G 為賦賦權權圖圖.第14頁/共75頁15第15頁/共75頁16第16頁/共75頁17頂點的度頂點的度4)(4vd5)(3)(2)(444vdvdvd第17頁/共75頁18例 在一次聚會中，認識奇數個人的人數一定是偶數。第18頁/共75頁19子圖子圖(3)設 E1E,且 E1,以 E1為邊

8、集,E1的端點集為頂點集的圖 G 的子圖,稱為 G 的由由 E1導導出出的的子子圖圖,記為 GE1. GGv1,v4,v5Ge1,e2,e3第19頁/共75頁20關聯矩陣關聯矩陣對無向圖，其關聯矩陣)(ijm，其中：不關聯與若相關聯與若jijiijevevm01對有向圖，其關聯矩陣)(ijm，其中：不關聯與若的終點是若的起點是若jijijiijevevevm011注：假設圖為簡單圖第20頁/共75頁21鄰接矩陣鄰接矩陣注：假設圖為簡單圖A=432143210111101011011010vvvvvvvv第21頁/共75頁22對有向賦權圖，其鄰接矩陣)(ijaA，其中：EvvjiwEvvwaji

9、ijjiijij),(0,),(若若為其權且若無向賦權圖的鄰接矩陣可類似定義A=4321432105375083802720vvvvvvvv第22頁/共75頁23第23頁/共75頁24第24頁/共75頁25第25頁/共75頁26步驟：第26頁/共75頁27例（設備更新問題）設某公司需使用某種設備一套，設備購買價格及維修費用見表。現設該公司在第一年開始時新購入一套設備，問今后5年的設備更新方案如何，才能使得總費用最??？年12345價格1111121213使用年限0-11-22-33-44-5維修費用5681118第27頁/共75頁28 結點i表示第i年購買一套設備，結點6為虛設的結點第28頁/共

10、75頁29第29頁/共75頁30第30頁/共75頁31第31頁/共75頁32Ford算法 動態(tài)規(guī)劃法與Dijkstra算法，都假定弧的長度是非負的，但在某些問題中，有時會出現長度為負值的情況，可采用Ford算法。 稱臨時標號為未著色標號，永久性標號為著色標號。所以Ford算法，只要對Dijkstra算法做兩點改變。第32頁/共75頁33 1、計算T( j)=minT( j), P(k)+bkj時，不僅對未著色點進行，對著色點也要進行。已著色標號也可以減小。 2、僅在所有頂點都已著色，而且下一步不能使任一頂點的標號減小時，算法才終止。第33頁/共75頁34最短路問題的數學表達式：假定圖有n個頂點

11、，現需要求從頂點1到頂點n 的最短路。,10.ijijijxxx 設決策變量為當，說明弧(i,j)位于頂點1至頂點n的路上，否則( , )11( , )(, )11(1, )min;. .0,1, ;1;0,( , )ijiji jEnnijjijji jEj iEnjjjEijw xs txxinxxi jE 第34頁/共75頁35例例A AB1B1B2C1C2C3D2 22 24 44 43 33 33 33 31 11 11 1Model:Model:Sets:Sets:Cities/a,b1,b2,c1,c2,c3,d/;Cities/a,b1,b2,c1,c2,c3,d/;Roads

12、(cities,cities)/a,b1 a,b2Roads(cities,cities)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:w,x; c1,d c2,d c3,d/:w,x;endsetsendsets第35頁/共75頁36data:data:w=2 4 3 3 1 2 3 1 1 3 4;w=2 4 3 3 1 2 3 1 1 3 4;EnddataEnddatan=size(cities);n=size(cities);min=

13、sum(roads:wmin=sum(roads:w* *x);x);for(cities(i)|i#ne#1 #and# i#ne#n:for(cities(i)|i#ne#1 #and# i#ne#n: sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i); sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);sum(roads(i,j)|i#eq#1:x(i,j)=1;sum(roads(i,j)|i#eq#1:x(i,j)=1;endend第36頁/共75頁37選擇菜單命令選擇菜單命令“l(fā)ingo|solutionl

14、ingo|solution”，出現對話，出現對話框框第37頁/共75頁38 Global optimal solution found at iteration: 3 Objective value: 6.000000 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000最短距離：最短距離：6 A-B1-C1-D6 A-B1-C1-D第38頁/共75頁39設備更新問題第39頁/共75頁40model:sets:cities/

15、1.6/;roads(cities,cities)|&1 #lt# &2: c, x;endsetsdata:c=12 22 30 41 59 16 22 30 41 17 23 31 17 23 18;enddatan=size(cities);min=sum(roads: c*x);for(cities(i)|i #ne# 1 #and# i#ne#n: sum(roads(i,j):x(i,j)=sum(roads(j,i): x(j,i);sum(roads(i,j)|i #eq# 1: x(i,j)=1;end第40頁/共75頁41 Variable Value Reduced Co

16、st X( 1, 3) 1.000000 0.000000 X( 3, 6) 1.000000 0.000000 Global optimal solution found at iteration: 0 Objective value: 53.00000 Variable Value Reduced Cost N 6.000000 0.000000 C( 1, 2) 12.00000 0.000000 C( 1, 3) 22.00000 0.000000 第41頁/共75頁42無向圖的最短路問題 例 求下圖u1到u8的最短路 解：對于無向圖，從點u1到ui和點ui到u8 的邊都看成有向弧，其

17、它各邊均看成有不同方向的雙弧。第42頁/共75頁43model:sets:cities/1.8/;roads(cities,cities): p,w,x;endsetsdata:p=0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0;第43頁/共75頁44w=0 2 1 8 0 0 0 0 2 0 0 6 1 0 0 0 1 0 0 7 0 0 9 0 8 6 7 0 5 1 2 0 0 1

18、0 5 0 3 0 9 0 0 0 1 3 0 4 6 0 0 0 2 0 4 0 3 0 0 0 0 9 6 3 0;enddatan=size(cities);min=sum(roads: w*x);for(cities(i)|i #ne# 1 #and# i#ne#n: sum(cities(j):p(i,j)*x(i,j)=sum(cities(j): p(j,i)*x(j,i);sum(roads(i,j)|i #eq# 1: p(i,j)*x(i,j)=1;end第44頁/共75頁45 Variable Value Reduced Cost X( 1, 2) 1.000000 0.

19、000000 X( 2, 5) 1.000000 0.000000 X( 5, 8) 1.000000 0.000000 Global optimal solution found at iteration: 10 Objective value: 12.00000 Variable Value Reduced Cost N 8.000000 0.000000 P( 1, 1) 0.000000 0.000000 P( 1, 2) 1.000000 0.000000 P( 1, 3) 1.000000 0.000000 第45頁/共75頁46最大流問題的數學表達式：假定圖有n個頂點，現需要求從

20、頂點1到頂點n 的最大流量。.ijf 代表弧從i點到j點的流量( , )( , )(1, )min;. .0,1, ;,();,( , )fijjij Vj Vi jEj iEsjfj VjEijijVs txxinxVsfci jE 表示起點 0第46頁/共75頁47例例Model:Model:Sets:Sets:nodes/v1,v2,v3,v4,v5,v6/;nodes/v1,v2,v3,v4,v5,v6/;arcs(nodes,nodes):p,c,f;arcs(nodes,nodes):p,c,f;endsetsendsetsv1v1v2v2v3v4v5v68 82 27 71010

21、9 99 95 55 56 6第47頁/共75頁48data:data:p=0 1 1 0 0 0 p=0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0; 0 0 0 0 0 0;第48頁/共75頁49C=0 8 7 0 0 0 C=0 8 7 0 0 0 0 0 5 9 0 0 0 0 5 9 0 0 0 0 0 0 9 0 0 0 0 0 9 0 0 0 2 0 0 5 0 0 2 0 0 5 0 0

22、0 6 0 10 0 0 0 6 0 10 0 0 0 0 0 0; 0 0 0 0 0 0;enddataenddatan=size(nodes)n=size(nodes)max=flow;max=flow;第49頁/共75頁50for(nodes(i)|i#ne#1 #and# i#ne#n:for(nodes(i)|i#ne#1 #and# i#ne#n: sum(arcs(i,j):p(i,j) sum(arcs(i,j):p(i,j)* *f(i,j)=f(i,j)= sum(arcs(j,i):p(j,i) sum(arcs(j,i):p(j,i)* *f(j,i);f(j,i);

23、sum(arcs(i,j)|i#eq#1:p(i,j)sum(arcs(i,j)|i#eq#1:p(i,j)* *f(i,j)=flow;f(i,j)=flow;for(arcs:bnd(0,f,c);for(arcs:bnd(0,f,c);endend第50頁/共75頁51 Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost F( V1, V2) 7.000000 0.000000 F( V1, V3) 7.000000 0.000000 F(

24、V2, V3) 2.000000 0.000000 F( V2, V4) 5.000000 0.000000 F( V3, V5) 9.000000 -1.000000 F( V4, V6) 5.000000 -1.000000 F( V5, V6) 9.000000 0.000000v1v1v2v2v3v4v5v6(8,7)(8,7)(2,0)(2,0)(7,7)(7,7)(10,9)(10,9)(9,9)(9,9)(9,5)(9,5)(5,5)(5,5)(5,2)(5,2)(6,0)(6,0)最大流量：最大流量：1414第51頁/共75頁52最小費用最大流問題最小費用最大流問題ijijij

25、ifudi 設 為弧(i,j)上的流量，c 為弧(i,j)上的單位運費，弧(i,j)上的容量， 是節(jié)點 處的凈流量.最小費用最大流問題的數學表達式：( , )( , )( , )( , )min;. .0,;,( , )ijiji jEijjij Vj Vi jEj iEsjfj Vs jEijijc fs tffifVsfui jE起點，終點 為起點 0第52頁/共75頁53v1v1v2v2v3vsvt(8,1)(8,1)(2,6)(2,6)(7,1)(7,1)(10,4)(10,4)(10,3)(10,3)(4,2)(4,2)(5,2)(5,2)例例 第第1 1個數字是網絡的個數字是網絡的

26、容量，第容量，第2 2個數字是個數字是網絡的單位運費網絡的單位運費. .求求流量流量F F為為1010的最小費的最小費用用Model:Model:Sets:Sets:nodes/vs,v1,v2,v3,vt/nodes/vs,v1,v2,v3,vt/：d;d;arcs(nodes,nodes)/vs,v1 vs,v2 v1,v3 v1,vtarcs(nodes,nodes)/vs,v1 vs,v2 v1,v3 v1,vt v2,v1 v2,v3 v3,vt/:c,u,f; v2,v1 v2,v3 v3,vt/:c,u,f;endsetsendsets第53頁/共75頁54data:data:d

27、=10 0 0 0 -10;d=10 0 0 0 -10;C=4 1 6 1 2 3 2;C=4 1 6 1 2 3 2;u=10 8 2 7 5 10 4;u=10 8 2 7 5 10 4;enddataenddatan=size(nodes);n=size(nodes);min=sum(arcs:cmin=sum(arcs:c* *f);f);第54頁/共75頁55for(nodes(i)|i#ne#1 #and# i#ne#n:for(nodes(i)|i#ne#1 #and# i#ne#n: sum(arcs(i,j):f(i,j)= sum(arcs(i,j):f(i,j)= su

28、m(arcs(j,i):f(j,i); sum(arcs(j,i):f(j,i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:bnd(0,f,u);for(arcs:bnd(0,f,u);endend第55頁/共75頁56 Global optimal solution found at iteration: 6 Objective value: 48.00000 Variable Value Reduced Cost F( VS, V1) 2.000000 0.000000 F( VS,

29、 V2) 8.000000 0.000000 F( V1, VT) 7.000000 -1.000000 F( V2, V1) 5.000000 -1.000000 F( V2, V3) 3.000000 0.000000 F( V3, VT) 3.000000 0.000000最小費用：最小費用：4848第56頁/共75頁57最優(yōu)連線問題（最小生成樹） 定義：如果無向圖是連通的，且不包含有圈，則稱該圖為樹(tree). 如果有向圖中任何一個頂點都可由某一頂點到達，則該頂點稱為圖的根(root). 如果有向圖G有根，且它的基礎圖是樹，則稱G為有向樹.第57頁/共75頁58生成樹 定義：若F是包

30、含G的全部頂點的子圖，它又是樹，則稱F為生成樹或支撐樹. 定理：如果無向圖是連通的、有限的，則在G中存在生成樹. 定義：在一個賦權圖中，稱具有最小權和的生成樹為最優(yōu)生成樹或最小生成樹.第58頁/共75頁59求最小生成樹的算法: 避圈法(Kruskal算法) 1、選擇邊e1,使得w(e1)盡可能小； 2、若已選定邊e1 e2 ei,則從E e1 e2 ei中選取邊e(i+1),使得 Ge1 e2 ei e(i+1)為無圈圖； w(e(i+1)是滿足的盡可能小的權； 3、當2不能繼續(xù)執(zhí)行時停止.第59頁/共75頁60第60頁/共75頁61最小生成樹的數學表達式：( , )1min;. .1;1,1

31、;()ijiji jAjj Vjij Vd xs txxi 各邊不構成圈第61頁/共75頁62例 假設某電話公司計劃在六個村莊架設電話線，各村莊之間的距離如圖所示。試求出使電話線總長度最小的架線方案。 第62頁/共75頁63第63頁/共75頁64第64頁/共75頁65第65頁/共75頁66第66頁/共75頁67第67頁/共75頁68第68頁/共75頁69第69頁/共75頁70旅行商問題(貨郎擔問題) 定義：包含圖G的每個頂點的路稱為Hamilton路， 包含圖G的每個頂點的圈成為Hamilton圈. 一個圖若包含Hamilton圈，則稱這個圖為Hamilton圖. 旅行商問題就是求最小距離的Hamilton圈第70頁/共75頁71第71頁/共75頁72第72頁/共75頁73第73頁/共75頁74旅行商問題的數學表達式niunjixnjinxnuunixnjxtsxcziijijjinjijniijnjijiijij, 3, 2, 0, 2, 1, 1, 02, 1, 2, 1, 1, 2, 1, 1. .min111,第74頁/共75頁75感謝您的觀看！第75頁/共75頁