《動(dòng) 態(tài) 規(guī) 劃PPT課件》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《動(dòng) 態(tài) 規(guī) 劃PPT課件（75頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、路問(wèn)題的動(dòng)態(tài)規(guī)劃最優(yōu)化原理 假設(shè)一條最短路線(xiàn)經(jīng)過(guò)狀態(tài)xk，那么，這條路線(xiàn)上從xk到終點(diǎn)的一段，是從xk出發(fā)到終點(diǎn)的所有路線(xiàn)中最短的。第4頁(yè)/共75頁(yè)5逆序法（回溯法） 從后向前逐步求出各點(diǎn)到終點(diǎn)的最佳路線(xiàn)，最后得到由起點(diǎn)到終點(diǎn)的最短路線(xiàn)。0)(1, 2, 1),(min)(NfNijfcifijj最短路問(wèn)題的動(dòng)態(tài)規(guī)劃模型，歸納為下述遞推公式：第5頁(yè)/共75頁(yè)643, 143,243, 34()02.3( 1)()1 01( 2)()303( 3)()404D CD CD CfDkf CrfDf CrfDf CrfD 1.從最后一段開(kāi)始,k=4第6頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)81,212,24.1( 1)2 4( ) minmin6( 2)4 3B AB Akrf BfArf B最短路徑：AB1C1D最短距離：6第8頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)12圖論與網(wǎng)絡(luò)模型第12頁(yè)/共75頁(yè)13定義有序二元組G= (V,E )稱(chēng)為一個(gè)圖.圖的定義圖的定義第13頁(yè)/共75頁(yè)14定義定義若將圖 G 的每一條邊 e 都對(duì)應(yīng)一個(gè)實(shí)數(shù) w(e)，稱(chēng) w(e)為邊的權(quán)權(quán)，并稱(chēng)圖 G 為賦賦權(quán)權(quán)圖圖.第14頁(yè)/共75頁(yè)15第15頁(yè)/共75頁(yè)16第16頁(yè)/共75頁(yè)17頂點(diǎn)的度頂點(diǎn)的度4)(4vd5)(3)(2)(444vdvdvd第17頁(yè)/共75頁(yè)18例 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。第18頁(yè)/共75頁(yè)19子圖子圖(3)設(shè) E1E,且 E1,以 E1為邊

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

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

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

11、，現(xiàn)需要求從頂點(diǎn)1到頂點(diǎn)n 的最短路。,10.ijijijxxx 設(shè)決策變量為當(dāng)，說(shuō)明弧(i,j)位于頂點(diǎn)1至頂點(diǎn)n的路上，否則( , )11( , )(, )11(1, )min;. .0,1, ;1;0,( , )ijiji jEnnijjijji jEj iEnjjjEijw xs txxinxxi jE 第34頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)37選擇菜單命令選擇菜單命令“l(fā)ingo|solutionl

14、ingo|solution”，出現(xiàn)對(duì)話(huà)，出現(xiàn)對(duì)話(huà)框框第37頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)39設(shè)備更新問(wèn)題第39頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)42無(wú)向圖的最短路問(wèn)題 例 求下圖u1到u8的最短路 解：對(duì)于無(wú)向圖，從點(diǎn)u1到ui和點(diǎn)ui到u8 的邊都看成有向弧，其

17、它各邊均看成有不同方向的雙弧。第42頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)46最大流問(wèn)題的數(shù)學(xué)表達(dá)式：假定圖有n個(gè)頂點(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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)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頁(yè)/共75頁(yè)52最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題ijijij

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

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

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

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