動 態(tài) 規(guī) 劃PPT課件
《動 態(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點出發(fā),點出發(fā),經(jīng)過經(jīng)過B B、C C等處,最后到達(dá)等處,最后到達(dá)D D點。從點。從A A到到D D有很多路有很多路線可以選擇,各點之間的距離如下圖中所示,線可以選擇,各點之間的距離如下圖中所示,問該公司應(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)每一階段的起點位置決策由一個狀態(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ā)到終點的最優(yōu)效益第3頁/共75頁4最短
3、路問題的動態(tài)規(guī)劃最優(yōu)化原理 假設(shè)一條最短路線經(jīng)過狀態(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圖論與網(wǎng)絡(luò)模型第12頁/共75頁13定義有序二元組G= (V,E )稱為一個圖.圖的定義圖的定義第13頁/共75頁14定義定義若將圖 G 的每一條邊 e 都對應(yīng)一個實數(shù) w(e),稱 w(e)為邊的權(quán)權(quán),并稱圖 G 為賦賦權(quán)權(quán)圖圖.第14頁/共75頁15第15頁/共75頁16第16頁/共75頁17頂點的度頂點的度4)(4vd5)(3)(2)(444vdvdvd第17頁/共75頁18例 在一次聚會中,認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù)。第18頁/共75頁19子圖子圖(3)設(shè) E1E,且 E1,以 E1為邊
8、集,E1的端點集為頂點集的圖 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)與若的終點是若的起點是若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è)備購買價格及維修費用見表。現(xiàn)設(shè)該公司在第一年開始時新購入一套設(shè)備,問今后5年的設(shè)備更新方案如何,才能使得總費用最???年12345價格1111121213使用年限0-11-22-33-44-5維修費用5681118第27頁/共75頁28 結(jié)點i表示第i年購買一套設(shè)備,結(jié)點6為虛設(shè)的結(jié)點第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算法做兩點改變。第32頁/共75頁33 1、計算T( j)=minT( j), P(k)+bkj時,不僅對未著色點進(jìn)行,對著色點也要進(jìn)行。已著色標(biāo)號也可以減小。 2、僅在所有頂點都已著色,而且下一步不能使任一頂點的標(biāo)號減小時,算法才終止。第33頁/共75頁34最短路問題的數(shù)學(xué)表達(dá)式:假定圖有n個頂點
11、,現(xiàn)需要求從頂點1到頂點n 的最短路。,10.ijijijxxx 設(shè)決策變量為當(dāng),說明弧(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”,出現(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的最短路 解:對于無向圖,從點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最大流問題的數(shù)學(xué)表達(dá)式:假定圖有n個頂點,現(xiàn)需要求從
20、頂點1到頂點n 的最大流量。.ijf 代表弧從i點到j(luò)點的流量( , )( , )(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 設(shè) 為弧(i,j)上的流量,c 為弧(i,j)上的單位運費,弧(i,j)上的容量, 是節(jié)點 處的凈流量.最小費用最大流問題的數(shù)學(xué)表達(dá)式:( , )( , )( , )( , )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個數(shù)字是網(wǎng)絡(luò)的個數(shù)字是網(wǎng)絡(luò)的
26、容量,第容量,第2 2個數(shù)字是個數(shù)字是網(wǎng)絡(luò)的單位運費網(wǎng)絡(luò)的單位運費. .求求流量流量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). 如果有向圖中任何一個頂點都可由某一頂點到達(dá),則該頂點稱為圖的根(root). 如果有向圖G有根,且它的基礎(chǔ)圖是樹,則稱G為有向樹.第57頁/共75頁58生成樹 定義:若F是包
30、含G的全部頂點的子圖,它又是樹,則稱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的每個頂點的路稱為Hamilton路, 包含圖G的每個頂點的圈成為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頁
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 6.煤礦安全生產(chǎn)科普知識競賽題含答案
- 2.煤礦爆破工技能鑒定試題含答案
- 3.爆破工培訓(xùn)考試試題含答案
- 2.煤礦安全監(jiān)察人員模擬考試題庫試卷含答案
- 3.金屬非金屬礦山安全管理人員(地下礦山)安全生產(chǎn)模擬考試題庫試卷含答案
- 4.煤礦特種作業(yè)人員井下電鉗工模擬考試題庫試卷含答案
- 1 煤礦安全生產(chǎn)及管理知識測試題庫及答案
- 2 各種煤礦安全考試試題含答案
- 1 煤礦安全檢查考試題
- 1 井下放炮員練習(xí)題含答案
- 2煤礦安全監(jiān)測工種技術(shù)比武題庫含解析
- 1 礦山應(yīng)急救援安全知識競賽試題
- 1 礦井泵工考試練習(xí)題含答案
- 2煤礦爆破工考試復(fù)習(xí)題含答案
- 1 各種煤礦安全考試試題含答案