第7章圖論pptppt課件

1、第第7章章 圖圖 論論 7.1 問題驅(qū)動：最佳災(zāi)情巡視路線 根據(jù)最新天氣預(yù)報，某縣將要遭遇特大暴雨，為預(yù)防洪澇災(zāi)情發(fā)生，提前做好預(yù)防工作，縣政府決定抽調(diào)各職能部門相關(guān)人員組成三個工作組到各鄉(xiāng)鎮(zhèn)、村進(jìn)行巡視。假設(shè)你是縣政府秘書，請設(shè)計最佳巡視路線。1.圖論基本知識2.圖論與網(wǎng)絡(luò)模型（1）最短路問題（2）最小生成樹（3）遍歷（4）網(wǎng)絡(luò)流問題7.2 圖論基本知識7.2.1 起源起源 哥尼斯堡是東普魯士的一座城市，第二次世界大戰(zhàn)后劃歸蘇聯(lián)，也就是現(xiàn)在的加里寧格勒。 普萊格爾河流經(jīng)此城市，河中有兩個孤島，有七座橋?qū)蓫u及島與河岸相連，如圖所示。當(dāng)時那里的居民熱衷于這樣一個問題：從一個點出發(fā)，能否通過每座

2、橋一次且僅一次，最后回到原來的出發(fā)點？7.2.2 圖論中的一些基本概念圖論中的一些基本概念 1.有序三元組 稱為一個圖圖。其中（1） 是有窮非空集，稱為頂點集，其中的元素叫圖g的頂點頂點。 （2） 稱為邊集，其中的元素叫圖g的邊邊。（3） 是從邊集到頂點集中的有序或無序的元素偶對的集合的映射，稱為關(guān)聯(lián)函數(shù)關(guān)聯(lián)函數(shù)。,evg,21nvvvv,21neeee2.邊有方向的圖，稱為有向圖有向圖，邊無方向的圖稱為無向圖無向圖。連接兩個頂點至多有一條邊，且一條邊的兩個頂點不重合的圖稱為簡單圖簡單圖。（a）（b）（c）（d）3.圖 、 ，若 、 ，則稱圖 是 的子圖。如圖中的（b）即為圖（a）的子圖。),

3、(evg ),(111evg 1vv 1ee 1gg（a）（b）通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路徑4521141vevevpvv6.任意兩個頂點之間都有邊相連的簡單圖，稱為完備圖完備圖。7.如果圖 的子圖 是一棵樹，且 ，則稱 是 的生成樹生成樹。8.設(shè)對圖 的每一條邊 賦予一個實數(shù) ，稱為邊的權(quán)，則稱 為賦權(quán)圖賦權(quán)圖(或加權(quán)圖或加權(quán)圖)。連通的賦權(quán)圖的權(quán)和最小的生成樹稱為的最小生成樹最小生成樹9.有向圖 中，每邊加權(quán) ，則稱這個賦權(quán)的有向圖為一個網(wǎng)絡(luò)網(wǎng)絡(luò)，記作 , 其中c為容量函數(shù)，c(e)稱為邊e的容量，容量，x

4、與y為網(wǎng)絡(luò)的發(fā)點集與收點集，x的頂點稱作發(fā)點或源，y的頂點稱作收點或匯，其余為中間點集。10.網(wǎng)絡(luò) 中，若函數(shù) 滿足(1) 任給 ，(2) 任給 ， ，其中 是 以為終點的邊集， 是以 為起點的邊集，稱 為網(wǎng)絡(luò)的一個流流， 為邊的流量流量。),(evg tttevg,vvttgg),(evg e ew),(evg ecyxcevn,yxcevn,ref:ee ecef0匯源, vv0)()()()(vnevneefef vnv vnvf ef（2，1）（5，4）（3，0）（2，2）（1，1）（4，4）（1，0）（5，2）（4，3）7.2.3 圖的矩陣表示圖的矩陣表示 圖的矩陣表示常用的有兩種形

5、式：鄰接矩陣和關(guān)聯(lián)矩陣。鄰接矩陣常用于研究圖的各種道路的問題，關(guān)聯(lián)矩陣常用于研究子圖的問題。由于矩陣的行列有固定的順序，因此在用矩陣表示圖之前，須將圖的結(jié)點和邊加以編號（定序），以確定與矩陣元素的對應(yīng)關(guān)系。 1.鄰接矩陣鄰接矩陣 設(shè) 是一簡單有向圖，結(jié)點集為 。構(gòu)造矩陣 其中 則稱a為有向圖g的鄰接矩陣鄰接矩陣。 這個定義也適用于無向圖，只須把其中的有向表示換成無向表示就行了。 對于賦權(quán)圖，其鄰接矩陣記作 ，其中：),(evg nvvvv,21nnijaa)(, 0, 1evvevvajijiij當(dāng)當(dāng))(ijaaevvjiwevvwajiijjiijij),(0,),(若若為其權(quán)且若2.關(guān)聯(lián)矩

6、陣關(guān)聯(lián)矩陣 設(shè) 是一個無環(huán)的有向圖， 。構(gòu)造矩陣 ，其中 稱m是g的關(guān)聯(lián)矩陣。 設(shè) 是無環(huán)的無向圖， 。構(gòu)造矩陣 ，其中 ,稱m為g的關(guān)聯(lián)矩陣。),(evg mneeeevvvv,2121nnijmm，ve，vemijijij其它的入邊是當(dāng)?shù)某鲞吺钱?dāng)01, 1),(evg mneeeevvvv,2121mnijmm)(，evmjiij其它關(guān)聯(lián)與若, 0, 1例例1 圖的鄰接矩陣是4321432105375083802720vvvvvvvv例例2 圖的關(guān)聯(lián)矩陣如下43215432110110011000101110001vvvveeeee7.3 圖論與網(wǎng)絡(luò)模型7.3.1最短路問題最短路問題 假設(shè)

7、給定連接若干城市的公路網(wǎng)，尋求從指定城市到各城去的最短路線。 設(shè)指定城市為圖的一個頂點 ，其余任一城市為圖的一個頂點 ，連接任意兩城市的公路為圖的邊 ， 為邊之長，即在加權(quán)圖中求 兩點之間的路徑 ，使該路徑上的邊權(quán)之和最小，即 解決這一問題可以用迪克斯特拉（dijkstra）算法， 0-1規(guī)劃法、動態(tài)規(guī)劃法求解。本節(jié)主要介紹0-1規(guī)劃法。 0uve ewvu,),(0vupp )()()(minpeewpw 設(shè)1為起點， n為終點。引入 表示：若弧(i,j)在最短路上, ；否則， 。z為目標(biāo)函數(shù)上各弧的路程之和。起點1必定有一條弧出發(fā),所以， 終點n必定有一條弧到達(dá),所以 。 其它點有兩種情況

8、：(1)點i不在最短路上，即無進(jìn)線弧，也無出線弧。滿足： ，且 (2)點i在最短路上，即有進(jìn)線弧，也有出線弧。滿足： ，且 改寫上述兩個等式為：01njijx01njjix11njijx11njjix0,11iinjjinjijxxx1 , 01 ,11. .min111111,ijnjjinjijnjjnnjjnjiijijxnixxxxtsxwz1 , 0ijx1ijx0ijx121njjx111njjnx例例3 在圖中，點表示城市，現(xiàn)有7個城市，點與點之間的連線表示城市間有道路相連，連線旁的數(shù)字表示道路的長度。某人計劃從城市a到城市 d去，請設(shè)計出路程最短的路線。ab1b2c1c2c3d

9、24314313132解：本題要求城市a到城市 d的最短路線設(shè)計方案，城市間路長作為邊上的權(quán)，問題就轉(zhuǎn)化為兩點間的最短路問題，編寫lingo程序求解如下： model: sets:city/a, b1, b2, c1, c2, c3, d/; road(city, city)/ a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/: w, x; endsets data: w = 2 4 3 3 1 2 3 1 1 3 4; enddata n=size(city); min=sum(road: w*x); for(city

10、(i) | i #ne# 1 #and# i #ne# n: sum(road(i,j): x(i,j) = sum(road(j,i): x(j,i); sum(road(i,j)|i #eq# 1 : x(i,j)=1; endlingo軟件計算結(jié)果如下global optimal solution found at iteration: 0 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.00

11、0000 0.000000即最短路是, 最短路長為6個單位。dcba117.3.2最小生成樹最小生成樹 欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為cij。設(shè)計一個線路圖，使修筑鐵路的總造價最低。 設(shè)計要求鐵路將n個城市連通，不要求任意兩城直達(dá)，但總造價最低。將城市看作點，城市之間欲修的鐵路看作邊，而城市間的鐵路造價作權(quán)，則構(gòu)成一個賦權(quán)連通圖，該問題就是在賦權(quán)連通圖中求權(quán)值最小的連通子圖，即邊權(quán)之和最小的生成樹。數(shù)學(xué)模型 。 解決這類構(gòu)造最小生成樹問題的算法有kruskal算法、prim算法、破圈法、整數(shù)規(guī)劃法。本節(jié)主要介紹整數(shù)規(guī)劃法。)()()(minteewtw整數(shù)規(guī)劃法整數(shù)規(guī)

12、劃法 假設(shè) 表示點i到點j的權(quán)，當(dāng)兩個節(jié)點沒有線路相通時， 。設(shè)0-1變量,當(dāng) ,表示從節(jié)點i到節(jié)點j的邊在樹中;當(dāng) ,表示從節(jié)點i到節(jié)點j的邊不在樹中。 目標(biāo)函數(shù): 約束條件：（1）假設(shè)根節(jié)點為 ，根節(jié)點只有出去的線路，且出去的線路不少于1條，但沒有進(jìn)來的線路,有 ；（2）其它節(jié)點（除根節(jié)點外）必須有且只有一條線路進(jìn)來，即 。 僅僅上述條件還不夠，因為一棵樹是連通且不能有圈的。引入變量 ，其中 ，為避免形成圈，約束ijwijw1ijx0ijxnjiijijxwz1,min1v0, 12121njjnjjxxjinjxniij,.,3 ,2, 11ujinjnuuj, 2, 11 , 01nj

13、nkxnxnxuujkkjkjkj2 ,1 ,312綜上，求最小生成樹模型njnkxnxnxuujinjnuujinjxxtsxwzjkkjkjkjjniijnjjnjiijij2 ,1 ,312, 2, 11 , 0,.,3 , 2, 11. .min11211,例例4 某地區(qū)共有1個城市（標(biāo)記為1）和9個鄉(xiāng)鎮(zhèn)（標(biāo)記為2-10）組成，該地區(qū)不久將用上天然氣，其中城市1含有井源?，F(xiàn)要設(shè)計一供氣系統(tǒng)，使得從城市1到每個鄉(xiāng)鎮(zhèn)（2-10）都有一條管道相通，并且鋪設(shè)的管子的量盡可能的少。下表給出了城鎮(zhèn)之間的距離。101111116816814915157108181571017317121271197

14、22141811817159221716121412958-2 3 4 5 6 7 8 9 101 23456789解：本題要求設(shè)計一條管道使得城市1到每個鄉(xiāng)鎮(zhèn)（2-10）都相通，但總長最短。將城市、鄉(xiāng)鎮(zhèn)看作點，之間連線看作邊，之間距離作邊權(quán)，構(gòu)成一個賦權(quán)連通圖。求使各點相互連通，總長最短的連線，即權(quán)和最小的生成樹。 編寫lingo程序求解如下：model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11

15、18 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddata n=size(city); min=sum(link: distance*x);for(link : bin(x); for(city(k) |k #g

16、t# 1 : sum(city(i)| i #ne# k: x(i,k)=1; for(city(j)| j #gt# 1 #and# j #ne# k: u(j) = u(k) + x(k,j) - (n-2)*(1-x(k,j) + (n-3)*x(j,k); ); sum(city(j)| j #gt# 1: x(1,j)=1; for(city(k) |k #gt# 1 :u(k)=n-1-(n-2)*x(1,k); ); end在上述程序中，利用變量(u)來保證所選的邊不構(gòu)成圈。計算結(jié)果如下：global optimal solution found at iteration: 34

17、objective value: 60.00000 variable value reduced cost x( 1, 2) 1.000000 8.000000 x( 1, 3) 1.000000 5.000000 x( 3, 4) 1.000000 7.000000 x( 3, 7) 1.000000 7.000000 x( 4, 5) 1.000000 3.000000 x( 5, 8) 1.000000 6.000000 x( 7, 9) 1.000000 6.000000 x( 9, 6) 1.000000 8.000000 x( 9, 10) 1.000000 10.00000連接這

18、10個城鎮(zhèn)的最小距離為60公里。7.3.3 遍遍 歷歷 一、中國郵路問題一、中國郵路問題 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，他必須經(jīng)過所負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計一條投遞路線，使得他行程最短。這個問題稱為中國郵路問題。定義定義 設(shè)g=(v,e)是連通無向圖（1）經(jīng)過g的每邊正好一次的回路稱為歐拉回路歐拉回路。（2）存在歐拉回路的圖稱為歐拉圖歐拉圖。（3）經(jīng)過g的每邊正好一次的道路稱為歐拉道路歐拉道路。 左圖中 是一條歐拉道路，但無歐拉回路，所以不是歐拉圖。右圖存在歐拉回路 ，所以是歐拉圖。e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e651 1

19、 2 2 31 4 4 3 3v ev e v e v e v e v1 1 2 2 3 5 1 44 3 3 6 1v ev e v e v e v e v e v定理定理 連通圖g是歐拉圖當(dāng)且僅當(dāng)g不含奇次頂點。 將投遞區(qū)的街道用邊表示，街道的長度用邊權(quán)表示，郵局街道交叉口用點表示，則一個投遞區(qū)構(gòu)成一個賦權(quán)連通無向圖中國郵遞員問題轉(zhuǎn)化為：在一個非負(fù)賦權(quán)連通圖中，尋求一個權(quán)最小的回路這樣的回路稱為最佳回路。對于歐拉圖，可由fleury算法求出圖的一個歐拉回路即是最佳回路。 對于無向加權(quán)連通圖，設(shè) 為從 i到 j 經(jīng)過的次數(shù)，則得如下數(shù)學(xué)模型ijxjivvijijxwminevvnxevvxx

20、vvxxjiijjijiijvvivvkiijjiik, 1,二、推銷員問題二、推銷員問題 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，如何為他設(shè)計一條旅行路線，使其從駐地出發(fā)，經(jīng)過每個城市至少一次，最后返回出發(fā)地的總行程最小？這個問題稱為推銷員問題。 若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時間、費用），于是推銷員問題就轉(zhuǎn)化為在加權(quán)圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題。 定義 設(shè)g=(v,e)是連通無向圖（1）經(jīng)過g的每個頂點正好一次的圈，稱為g的哈密爾頓圈哈密爾頓圈或h圈。（2）含h圈的圖稱為哈密爾頓圖哈密爾頓圖或h圖。v1v2v5v3v4圖7-20v10v9v6v

21、7v8 定義定義在加權(quán)圖g=(v,e)中，（）權(quán)最小的哈密爾頓圈稱為最佳最佳h圈圈。（）經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最佳推銷員回路最佳推銷員回路。 一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈。 定理定理在加權(quán)圖g=(v,e)中，若對任意x,y,z v，zx,zy,都有w(x,y) w(x,z)+w(z,y) ，則圖g的最佳h圈也是最佳推銷員回路。 最佳推銷員回路問題可轉(zhuǎn)化為最佳h圈問題方法是由給定的圖g=(v,e)構(gòu)造一個以v為頂點集的完備圖g=(v,e)，e的每條邊(x,y)的權(quán)等于頂點x與y在圖中最短路的權(quán)。即：w(x,y)=mi

22、ndg(x,y) 定理定理加權(quán)圖g的最佳推銷員回路的權(quán)與g的最佳h圈的權(quán)相同。 加權(quán)圖中求最佳推銷員回路問題就轉(zhuǎn)化為再完備加權(quán)圖中尋求最佳h圈問題，而求h圈至今仍無有效算法。我們常采用近似算法，如二邊逐次修正法，或建立數(shù)學(xué)模型用軟件求解。設(shè)當(dāng)從 到 時， ，否則， ， ，則得如下模型ivjv1ijx0ijxji jinjniuunnxuunjixjinjxijnixtsxwjiijjiijniijnjijninjijij, 2, 2 , 1, 0, 1, 1, 1 , 0, 1, 1, 1, 1. .min1111、例例5 某公司計劃在某地區(qū)作廣告宣傳，各城鎮(zhèn)之間的距離如表,推銷員從城市1出發(fā)

23、，經(jīng)過各個鄉(xiāng)鎮(zhèn)，再回到城市1，為節(jié)約開支，公司希望推銷員走過這10 個城鎮(zhèn)的總距離最少。 10111111681681491515710818157101731712127119722141811817159221716121412958-2 3 4 5 6 7 8 9 101 23456789解：本題是最佳推銷員問題，編寫lingo程序如下model: sets: city/1.10/:u; link(city, city): distance, x; endsets data: distance = 0 8 5 9 12 14 12 16 17 22 8 0 9 15 16 8 11 18

24、 14 22 5 9 0 7 9 11 7 12 12 17 9 15 7 0 3 17 10 7 15 15 12 16 9 3 0 8 10 6 15 15 14 8 11 17 8 0 9 14 8 16 12 11 7 10 10 9 0 8 6 11 16 18 12 7 6 14 8 0 11 11 17 14 12 15 15 8 6 11 0 10 22 22 17 15 15 16 11 11 10 0; enddatan=size(city); min=sum(link: distance*x); for(link : bin(x); for(city(k) :sum(ci

25、ty(i)| i#ne# k: x(i,k)=1; sum(city(j)| j #ne# k: x(k,j)=1;); for(city(i): for(city(j) | j #gt# 1 #and#i #ne# j : u(i)-u(j)+n*x(i,j)=n-1);); for(city(i):u(i)=n-1);for(link : bin(x); end變量u是用來保證所選的邊除第1點外不構(gòu)成圈。lingo軟件計算結(jié)果如下：global optimal solution found at iteration: 90objective value: 73.00000 variable

26、 value reduced cost x( 1, 2) 1.000000 8.000000 x( 2, 6) 1.000000 8.000000 x( 3, 1) 1.000000 5.000000 x( 4, 3) 1.000000 7.000000 x( 5, 4) 1.000000 3.000000 x( 6, 9) 1.000000 8.000000 x( 7, 10) 1.000000 11.00000 x( 8, 5) 1.000000 6.000000 x( 9, 7) 1.000000 6.000000 x( 10, 8) 1.000000 11.00000旅行商經(jīng)過10 個

27、城鎮(zhèn)的最短距離為73公里，次序1345810796217.3.4 網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題 現(xiàn)實生活中存在很多網(wǎng)絡(luò)，鐵路網(wǎng)、通信網(wǎng)、運輸網(wǎng)等。把商品從生產(chǎn)地運往市場，交通網(wǎng)上每個路段能力給定的條件下，設(shè)計一個運輸方案，使得運輸最快。 在單源單匯具有容量上限的網(wǎng)絡(luò)中求從源到匯的流量最大的流。求網(wǎng)絡(luò)最大流中有ford-fulkerson算法，但是網(wǎng)絡(luò)最大流也是一個線性規(guī)劃問題。其數(shù)學(xué)模型如下：其中1發(fā)點，表示收點。最小費用最大流問題數(shù)學(xué)模型 nijifikfcjiftsnfvjvkij, 1, ),(),(),(0. ., 1max的最大流到為網(wǎng)絡(luò)頂點nnfnijifikfcjiftsnjnifczv

28、jvkijejiijij1, 1, 1, ),(),(),(0. ., 1,min,例例6 現(xiàn)需要將城市s的石油通過管道運送到城市t，中間有4個中轉(zhuǎn)站v1v2v3v4 , 城市與中轉(zhuǎn)站的連接，由于輸油管道的長短不一或地質(zhì)等原因，使每條管道上運輸費用也不相同，因此，除考慮輸油管道的最大流外，還需要考慮輸油管道輸送最大流的最小費用，如圖示是帶有運費的網(wǎng)絡(luò)，其中第1個數(shù)字是網(wǎng)絡(luò)的容量，第2個數(shù)字是網(wǎng)絡(luò)的單位運費。stv1v2v3v4(8,2)(7,8)(9,3)(9,2)(2,1)(5,5)(5,6)(10,7)(6,4)解： 本例所提出的問題就是最小費用最大流問題，即考慮網(wǎng)絡(luò)在最大流情況下的最小費

29、用，先求網(wǎng)絡(luò)最大流，編寫lingo程序如下：model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f; endsets data: c = 8 7 5 9 9 2 5 6 10; enddatamax = f(s,t);for(links (i,j) :f(i,j)=c(i,j);for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j);endlingo軟件的計算結(jié)果如下:global optimal s

30、olution found at iteration: 6 objective value: 14.00000 variable value reduced cost flow 14.00000 0.000000 f( s, 1) 7.000000 0.000000 f( s, 2) 7.000000 0.000000 f( 1, 2) 2.000000 0.000000 f( 1, 3) 5.000000 0.000000 f( 2, 4) 9.000000 -1.000000 f( 3, 2) 0.000000 0.000000 f( 3, t) 5.000000 -1.000000 f(

31、 4, 3) 0.000000 1.000000 f( 4, t) 9.000000 0.000000在網(wǎng)絡(luò)最大流的限制下，求輸油管道輸送最大流的最小費用，編寫lingo程序如下：model: sets: nodes/s,1,2,3,4,t/; links(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, u, f; endsets data: c= 8 7 5 9 9 2 5 6 10; u= 2 8 5 2 3 1 6 4 7; enddata f(s,t)=14; min=sum(links:u*f); for(links(i

32、,j):f(i,j)=c(i,j);for(nodes(i):sum(links(j,i):f(j,i)=sum(links(i,j):f(i,j);endlingo軟件的計算結(jié)果如下:global optimal solution found at iteration: 3 objective value: 205.0000 variable value reduced cost f( s, 1) 8.000000 -1.000000 f( s, 2) 6.000000 0.000000 f( 1, 2) 1.000000 0.000000 f( 1, 3) 7.000000 0.00000

33、0 f( 2, 4) 9.000000 0.000000 f( 3, 2) 2.000000 -2.000000 f( 3, t) 5.000000 -7.000000 f( 4, t) 9.000000 0.000000因此，最大流的最小費用是205單位。7.4驅(qū)動問題建模求解7.4.1 問題分析問題分析 題中給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線。從若干可能的安排或方案中尋求最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化問題。 將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對應(yīng)頂點間的邊，各條公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)

34、，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為推銷員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點o出發(fā)，行遍所有頂點至少一次再回到點o，使得總權(quán)（路程或時間）最小。本題即推銷員問題的延伸多推銷員員問題。7.4.2 假假 設(shè)設(shè) 1汽車在路上的速度總是一定，不會出現(xiàn)拋錨等現(xiàn)象； 2巡視當(dāng)中，在每個鄉(xiāng)鎮(zhèn)、村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間； 3每個小組的汽車行駛速度完全一樣； 4分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路，除公共路外。 5村鎮(zhèn)被巡視一次后，再次經(jīng)過時不會停留。 7.4.3模模 型型 的的 建建 立立 與與 求求 解解 將公路網(wǎng)圖中，每個鄉(xiāng)（鎮(zhèn)）或村看作圖中

35、的一個節(jié)點，各鄉(xiāng)（鎮(zhèn)）、村之間的公路看作圖中對應(yīng)節(jié)點間的邊，各條公路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點o出發(fā)，行遍所有頂點至少一次再回到o點，使得總程最小，此即最佳推銷員回路問題。 在加權(quán)圖g中求最佳推銷員回路問題是np完全問題，我們采用一種近似算法求出該問題的一個近似最優(yōu)解，來代替最優(yōu)解，算法如下： 1.用圖論軟件求出g中任意兩個頂點間的最短路，構(gòu)造出完備圖 ， ， ； 2.輸入圖的一個初始h圈； 3.隨機(jī)搜索出中若干個h圈； 4.對第2、3步所得的每個h圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳h圈； 5.在第4

36、步求出的所有h圈中，找出權(quán)最小的一個，此即要找的最佳h圈的近似解。 由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3步分別用兩種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果。),(evgeyx ,yxmindyxg,具體求解如下： 此問題是多個推銷員的最佳推銷員回路問題，即在加權(quán)圖g中求頂點集v的劃分 ，將g分成n個生成子圖 ，使得（1）頂點 i=1，2，3n（2）（3） ，其中 為 的導(dǎo)出子圖中的最佳推銷員回路， 為 的權(quán)，i，j=1，2，3n（4）定義 稱為分組的實際均衡度。 為最大容許均衡度。nvvv,.,21 nvgvgvg,.,21ivogvvnii1iijijicmaxccma

37、x,icivicicmincnii1iijijicmaxccmax,0 從o點出發(fā)去其它點，要使路程較小應(yīng)盡量走o點到該點的最短路。故用圖論軟件包求出o點到其余頂點的最短路，這些最短路構(gòu)成一棵樹，將從o點出發(fā)的樹枝稱為干枝，見下圖，從圖中可以看出，從o點出發(fā)到其它點共有6條干枝，它們的名稱分別為，。根據(jù)實際工作的經(jīng)驗及上述分析，在分組時應(yīng)遵從以下準(zhǔn)則：一、盡量使同一干枝上及其分枝上的點分在同一組；二、應(yīng)將相鄰的干枝上的點分在同一組；三、盡量將長的干枝與短的干枝分在同一組。根據(jù)上述分組準(zhǔn)則，我們找到兩種分組形式如下：分組一：（，），（，），（，）分組二：（，），（，），（，）顯然分組一的方法極不均衡，故考慮