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

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

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

3、路問題的動態(tài)規(guī)劃最優(yōu)化原理 假設(shè)一條最短路線經(jīng)過狀態(tài)xk，那么，這條路線上從xk到終點(diǎn)的一段，是從xk出發(fā)到終點(diǎn)的所有路線中最短的。第4頁/共75頁5逆序法（回溯法） 從后向前逐步求出各點(diǎn)到終點(diǎn)的最佳路線，最后得到由起點(diǎn)到終點(diǎn)的最短路線。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圖論與網(wǎng)絡(luò)模型第12頁/共75頁13定義有序二元組G= (V,E )稱為一個圖.圖的定義圖的定義第13頁/共75頁14定義定義若將圖 G 的每一條邊 e 都對應(yīng)一個實(shí)數(shù) w(e)，稱 w(e)為邊的權(quán)權(quán)，并稱圖 G 為賦賦權(quán)權(quán)圖圖.第14頁/共75頁15第15頁/共75頁16第16頁/共75頁17頂點(diǎn)的度頂點(diǎn)的度4)(4vd5)(3)(2)(444vdvdvd第17頁/共75頁18例 在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù)。第18頁/共75頁19子圖子圖(3)設(shè) E1E,且 E1,以 E1為邊

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

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

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

11、，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)n 的最短路。,10.ijijijxxx 設(shè)決策變量為當(dāng)，說明弧(i,j)位于頂點(diǎn)1至頂點(diǎn)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”，出現(xiàn)對話，出現(xiàn)對話框框第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設(shè)備更新問題第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的最短路 解：對于無向圖，從點(diǎn)u1到ui和點(diǎn)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最大流問題的數(shù)學(xué)表達(dá)式：假定圖有n個頂點(diǎn)，現(xiàn)需要求從

20、頂點(diǎn)1到頂點(diǎn)n 的最大流量。.ijf 代表弧從i點(diǎn)到j(luò)點(diǎn)的流量( , )( , )(1, )min;. .0,1, ;,();,( , )fijjij Vj Vi jEj iEsjfj VjEijijVs txxinxVsfci jE 表示起點(diǎn) 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最小費(fèi)用最大流問題最小費(fèi)用最大流問題ijijij

25、ifudi 設(shè) 為弧(i,j)上的流量，c 為弧(i,j)上的單位運(yùn)費(fèi)，弧(i,j)上的容量， 是節(jié)點(diǎn) 處的凈流量.最小費(fèi)用最大流問題的數(shù)學(xué)表達(dá)式：( , )( , )( , )( , )min;. .0,;,( , )ijiji jEijjij Vj Vi jEj iEsjfj Vs jEijijc fs tffifVsfui jE起點(diǎn)，終點(diǎn) 為起點(diǎn) 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個數(shù)字是網(wǎng)絡(luò)的個數(shù)字是網(wǎng)絡(luò)的

26、容量，第容量，第2 2個數(shù)字是個數(shù)字是網(wǎng)絡(luò)的單位運(yùn)費(fèi)網(wǎng)絡(luò)的單位運(yùn)費(fèi). .求求流量流量F F為為1010的最小費(fèi)的最小費(fèi)用用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最小費(fèi)用：最小費(fèi)用：4848第56頁/共75頁57最優(yōu)連線問題（最小生成樹） 定義：如果無向圖是連通的，且不包含有圈，則稱該圖為樹(tree). 如果有向圖中任何一個頂點(diǎn)都可由某一頂點(diǎn)到達(dá)，則該頂點(diǎn)稱為圖的根(root). 如果有向圖G有根，且它的基礎(chǔ)圖是樹，則稱G為有向樹.第57頁/共75頁58生成樹 定義：若F是包

30、含G的全部頂點(diǎn)的子圖，它又是樹，則稱F為生成樹或支撐樹. 定理：如果無向圖是連通的、有限的，則在G中存在生成樹. 定義：在一個賦權(quán)圖中，稱具有最小權(quán)和的生成樹為最優(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)是滿足的盡可能小的權(quán)； 3、當(dāng)2不能繼續(xù)執(zhí)行時停止.第59頁/共75頁60第60頁/共75頁61最小生成樹的數(shù)學(xué)表達(dá)式：( , )1min;. .1;1,1

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