第7章圖論pptppt課件

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

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

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

4、與y為網(wǎng)絡(luò)的發(fā)點(diǎn)集與收點(diǎn)集，x的頂點(diǎn)稱作發(fā)點(diǎn)或源，y的頂點(diǎn)稱作收點(diǎn)或匯，其余為中間點(diǎn)集。10.網(wǎng)絡(luò) 中，若函數(shù) 滿足(1) 任給 ，(2) 任給 ， ，其中 是 以為終點(diǎn)的邊集， 是以 為起點(diǎn)的邊集，稱 為網(wǎng)絡(luò)的一個(gè)流流， 為邊的流量流量。),(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é)點(diǎn)和邊加以編號(hào)（定序），以確定與矩陣元素的對(duì)應(yīng)關(guān)系。 1.鄰接矩陣鄰接矩陣 設(shè) 是一簡(jiǎn)單有向圖，結(jié)點(diǎn)集為 。構(gòu)造矩陣 其中 則稱a為有向圖g的鄰接矩陣鄰接矩陣。 這個(gè)定義也適用于無(wú)向圖，只須把其中的有向表示換成無(wú)向表示就行了。 對(duì)于賦權(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è) 是一個(gè)無(wú)環(huán)的有向圖， 。構(gòu)造矩陣 ，其中 稱m是g的關(guān)聯(lián)矩陣。 設(shè) 是無(wú)環(huán)的無(wú)向圖， 。構(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è)指定城市為圖的一個(gè)頂點(diǎn) ，其余任一城市為圖的一個(gè)頂點(diǎn) ，連接任意兩城市的公路為圖的邊 ， 為邊之長(zhǎng)，即在加權(quán)圖中求 兩點(diǎn)之間的路徑 ，使該路徑上的邊權(quán)之和最小，即 解決這一問題可以用迪克斯特拉（dijkstra）算法， 0-1規(guī)劃法、動(dòng)態(tài)規(guī)劃法求解。本節(jié)主要介紹0-1規(guī)劃法。 0uve ewvu,),(0vupp )()()(minpeewpw 設(shè)1為起點(diǎn)， n為終點(diǎn)。引入 表示：若弧(i,j)在最短路上, ；否則， 。z為目標(biāo)函數(shù)上各弧的路程之和。起點(diǎn)1必定有一條弧出發(fā),所以， 終點(diǎn)n必定有一條弧到達(dá),所以 。 其它點(diǎn)有兩種情況

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

9、24314313132解：本題要求城市a到城市 d的最短路線設(shè)計(jì)方案，城市間路長(zhǎng)作為邊上的權(quán)，問題就轉(zhuǎn)化為兩點(diǎ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軟件計(jì)算結(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即最短路是, 最短路長(zhǎng)為6個(gè)單位。dcba117.3.2最小生成樹最小生成樹 欲修筑連接n個(gè)城市的鐵路，已知i城與j城之間的鐵路造價(jià)為cij。設(shè)計(jì)一個(gè)線路圖，使修筑鐵路的總造價(jià)最低。 設(shè)計(jì)要求鐵路將n個(gè)城市連通，不要求任意兩城直達(dá)，但總造價(jià)最低。將城市看作點(diǎn)，城市之間欲修的鐵路看作邊，而城市間的鐵路造價(jià)作權(quán)，則構(gòu)成一個(gè)賦權(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è) 表示點(diǎn)i到點(diǎn)j的權(quán)，當(dāng)兩個(gè)節(jié)點(diǎn)沒有線路相通時(shí)， 。設(shè)0-1變量,當(dāng) ,表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊在樹中;當(dāng) ,表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊不在樹中。 目標(biāo)函數(shù): 約束條件：（1）假設(shè)根節(jié)點(diǎn)為 ，根節(jié)點(diǎn)只有出去的線路，且出去的線路不少于1條，但沒有進(jìn)來(lái)的線路,有 ；（2）其它節(jié)點(diǎn)（除根節(jié)點(diǎn)外）必須有且只有一條線路進(jìn)來(lái)，即 。 僅僅上述條件還不夠，因?yàn)橐豢脴涫沁B通且不能有圈的。引入變量 ，其中 ，為避免形成圈，約束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個(gè)城市（標(biāo)記為1）和9個(gè)鄉(xiāng)鎮(zhèn)（標(biāo)記為2-10）組成，該地區(qū)不久將用上天然氣，其中城市1含有井源?，F(xiàn)要設(shè)計(jì)一供氣系統(tǒng)，使得從城市1到每個(gè)鄉(xiāng)鎮(zhèn)（2-10）都有一條管道相通，并且鋪設(shè)的管子的量盡可能的少。下表給出了城鎮(zhèn)之間的距離。101111116816814915157108181571017317121271197

14、22141811817159221716121412958-2 3 4 5 6 7 8 9 101 23456789解：本題要求設(shè)計(jì)一條管道使得城市1到每個(gè)鄉(xiāng)鎮(zhèn)（2-10）都相通，但總長(zhǎng)最短。將城市、鄉(xiāng)鎮(zhèn)看作點(diǎn)，之間連線看作邊，之間距離作邊權(quán)，構(gòu)成一個(gè)賦權(quán)連通圖。求使各點(diǎn)相互連通，總長(zhǎng)最短的連線，即權(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)來(lái)保證所選的邊不構(gòu)成圈。計(jì)算結(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個(gè)城鎮(zhèn)的最小距離為60公里。7.3.3 遍遍 歷歷 一、中國(guó)郵路問題一、中國(guó)郵路問題 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，他必須經(jīng)過所負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計(jì)一條投遞路線，使得他行程最短。這個(gè)問題稱為中國(guó)郵路問題。定義定義 設(shè)g=(v,e)是連通無(wú)向圖（1）經(jīng)過g的每邊正好一次的回路稱為歐拉回路歐拉回路。（2）存在歐拉回路的圖稱為歐拉圖歐拉圖。（3）經(jīng)過g的每邊正好一次的道路稱為歐拉道路歐拉道路。 左圖中 是一條歐拉道路，但無(wú)歐拉回路，所以不是歐拉圖。右圖存在歐拉回路 ，所以是歐拉圖。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不含奇次頂點(diǎn)。 將投遞區(qū)的街道用邊表示，街道的長(zhǎng)度用邊權(quán)表示，郵局街道交叉口用點(diǎn)表示，則一個(gè)投遞區(qū)構(gòu)成一個(gè)賦權(quán)連通無(wú)向圖中國(guó)郵遞員問題轉(zhuǎn)化為：在一個(gè)非負(fù)賦權(quán)連通圖中，尋求一個(gè)權(quán)最小的回路這樣的回路稱為最佳回路。對(duì)于歐拉圖，可由fleury算法求出圖的一個(gè)歐拉回路即是最佳回路。 對(duì)于無(wú)向加權(quán)連通圖，設(shè) 為從 i到 j 經(jīng)過的次數(shù)，則得如下數(shù)學(xué)模型ijxjivvijijxwminevvnxevvxx

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

21、7v8 定義定義在加權(quán)圖g=(v,e)中，（）權(quán)最小的哈密爾頓圈稱為最佳最佳h圈圈。（）經(jīng)過每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最佳推銷員回路最佳推銷員回路。 一般說來(lái)，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈。 定理定理在加權(quán)圖g=(v,e)中，若對(duì)任意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)造一個(gè)以v為頂點(diǎn)集的完備圖g=(v,e)，e的每條邊(x,y)的權(quán)等于頂點(diǎ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圈至今仍無(wú)有效算法。我們常采用近似算法，如二邊逐次修正法，或建立數(shù)學(xué)模型用軟件求解。設(shè)當(dāng)從 到 時(shí)， ，否則， ， ，則得如下模型ivjv1ijx0ijxji jinjniuunnxuunjixjinjxijnixtsxwjiijjiijniijnjijninjijij, 2, 2 , 1, 0, 1, 1, 1 , 0, 1, 1, 1, 1. .min1111、例例5 某公司計(jì)劃在某地區(qū)作廣告宣傳，各城鎮(zhèn)之間的距離如表,推銷員從城市1出發(fā)

23、，經(jīng)過各個(gè)鄉(xiāng)鎮(zhèn)，再回到城市1，為節(jié)約開支，公司希望推銷員走過這10 個(gè)城鎮(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是用來(lái)保證所選的邊除第1點(diǎn)外不構(gòu)成圈。lingo軟件計(jì)算結(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 個(gè)

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

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

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軟件的計(jì)算結(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ò)最大流的限制下，求輸油管道輸送最大流的最小費(fèi)用，編寫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軟件的計(jì)算結(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因此，最大流的最小費(fèi)用是205單位。7.4驅(qū)動(dòng)問題建模求解7.4.1 問題分析問題分析 題中給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線。從若干可能的安排或方案中尋求最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化問題。 將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)

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

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

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

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