數(shù)學(xué)建模算法與應(yīng)用多媒體電子課件-5第五章圖網(wǎng)絡(luò)

第五 §1圖論于18世紀(jì)。第一篇圖論是數(shù)學(xué)家歐拉于1736年的“哥尼斯堡的七座橋”。1847年，克?；舴驗榱私o出電網(wǎng)絡(luò)方程而引進了“樹”的概念。1857年，凱萊在計數(shù)烷CnH2n2的同分異構(gòu)物時，也發(fā)現(xiàn)了“樹”1859年提出“周游世界”游戲，用圖論的術(shù)語，就是如何找出通圖中的生成圈、近幾十年1問題成為從任一點出發(fā)一筆畫出七條線再回到起點。歐拉了一般一筆畫的結(jié)構(gòu)特圖與網(wǎng)絡(luò)是運籌學(xué)（OperationsResearch）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通、計算機科學(xué)與、通訊與網(wǎng)絡(luò)技術(shù)等1最短路問題（SPP－shortestpathproblem）一名貨柜車奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)交錯，因此有多種行車路線，這名應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運2-3指派問題（assignment一家公司經(jīng)理準(zhǔn)備安排N名員工去完成N項任務(wù)，每人一項。由于各員工的特點4中國郵遞員問題（CPP－chinesepostman梅谷教授1960年首先，所以國際上稱之為中國郵遞員問題。5旅行商問題（TSP－travelingsalesman例6問題（transportation某種原材料有M個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往N個使用這些原材料的工廠。假定M個產(chǎn)地的產(chǎn)量和N家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排方案可以使總成本最低？（netwokoptimization）問題。所以上面例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。由于多絡(luò)流（networkflows）或網(wǎng)絡(luò)流規(guī)劃等?！?2.1一個無向圖(undirectedgraph)G是由一個非空有限集合V(G)和V(G)中某些元素E(G)G(V(GE(G))V(Gv1v2,Lvn}稱為圖G的頂點集（vertexset）或節(jié)點集（nodeset），V(G)vi(i1,2,L,n)（vertex）（nodeE(Ge1e2,Lem}稱為圖G的邊集（edgeset），E(G)中的每一個元素ek(即V(G)vi,vj的無序?qū)?記為ek(vi,vj)或ekvivjvjvi(k1,2,L,m)，被稱為該圖的一條從vi到vj的邊（edge）。當(dāng)邊ekvivj時，稱vivj為邊ek的端點，并稱vj與vi相鄰（adjacent）；邊ek稱為與頂點vi,vj關(guān)聯(lián)（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖G邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡(luò)（undirectednetwork）。我們對圖和-一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖G的頂點數(shù)用符號|V|G)表示，邊數(shù)用|E|G)G來表示這個圖。從而在圖論符號中我們常略去字母G，例如，分別用V,E,代替V(G),E(G),(G)(G)。定

一個有向圖（directedgraphdigraph）G是由一個非空有限集合V和V某些元素的有序?qū)螦構(gòu)成的二元組，記為GVA)。其中Vv1v2,Lvn}稱為圖G的頂點集或節(jié)點集，V中的每一個元素vi(i1,2,L,n)稱為該圖的一個頂點或節(jié)點；Aa1a2,Lam}稱為圖G的弧集（arcset），A中的每一個元素ak(即V中某兩個元素vi,vj的有序?qū)?記為ak(vi,vj)或akvivj(k1,2,L,n)，被稱為該圖的一條從vi到vj的弧（arc）當(dāng)弧akvivj時，稱vi為ak的尾（tail），vj為ak的頭（head），并稱弧ak為vi的出?。╫utgoingarc），為vj的入弧（ ingarc）。對應(yīng)于每個有向圖D，可以在相同頂點集上作一個圖G，使得對于DG有一條有相同端點的邊與之相對應(yīng)。這個圖稱為D的基礎(chǔ)圖。反之，給定任意圖G，樣的有向圖稱為G每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(completegraph)。n個頂點的完全圖記為Kn。若V(GXUY，XIY，|X||Y|0（這里|X|表示集合X中的元素個數(shù)），X中無相鄰頂點對，Y中亦然，則稱G為二分圖(bipartitegraph)；特別地，若 X Y，則 E(G)，則稱G為完全二分圖，記成K|X|,|Y|圖HG（subgraph），記作HG，如果VH)V(G)EHE(G)。若H是G的子圖，則G稱為HG的支撐子圖（spanningsubgraph，又成生成子圖）是指滿足VHV(G)的子圖H。設(shè) V(G)，G中與v關(guān)聯(lián)的邊數(shù)（每個環(huán)算作兩條邊）稱為v的度(degree)，作d(v)。若d(v)是奇數(shù)，稱v是奇頂點(oddpoint)；d(v)是偶數(shù)，稱v是偶頂點(evenv(ii)-算法，首先須有法（即數(shù)據(jù)結(jié)構(gòu)）在計算機上來描述圖與網(wǎng)絡(luò)。一般來說，5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、GVA)是一個簡單有向圖，|V|n|A|m，并假設(shè)V中的頂點用自然數(shù)1,2,L表示或編號，A中的弧用自然數(shù)1,2,Lm表示或編號。對于有多重邊或無向網(wǎng)絡(luò)的情鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式在計算機中。G(V,A)的cij陣是如下定義的：C是一個nn的 1矩陣，C(cij)nn{0,1}nn0,(i,j)102個為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費大量的空間，從而增加了在網(wǎng)絡(luò)02072 0100 010011同樣，對于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的nn矩陣表示。只是此時一條1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式在計算機中．GVA)的關(guān)聯(lián)矩陣B是如下定義的：B是一個nmB(bik) {1,0,1}nm-bik1,jV,k(j, jV,k(i, 0,其它1；如果一個節(jié)點是一條弧的終點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為0。對于簡單圖，關(guān)聯(lián)矩陣每列只含有兩個非零元（一個1，一 1）nm個元素中，只有2m個為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法也會浪費大量的空間。但由于 0000110001011010

1每條弧有一個權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對應(yīng)的權(quán)在增加的弧所對應(yīng)的權(quán)在增加的行中?；”肀硎痉▽D以弧表（arclist）的形式在計算機中。所謂圖的弧表，也就

2m

7所示的圖，假設(shè)弧(4,3)，(4,5)，(5,3)和(5,4)8，9，6，4，0，3，67表14552534權(quán)80367照這樣的順序的。鄰接表表示法將圖以鄰接表（adjacencylists）的形式在計算機中。所謂圖的組表示。例如，例7所示的圖，鄰接表表示為-5維指針數(shù)組，每一維（上面表示法中的每一行）11個節(jié)點的鄰接表（1個節(jié)點的所有出弧）1個數(shù)據(jù)域表示弧的另一個端點（弧的頭），后面的數(shù)據(jù)域表示對應(yīng)弧上的權(quán)。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2）），“8”表示對應(yīng)弧(1,2)上的權(quán)為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應(yīng)弧（1，3）上的權(quán)955出發(fā)的弧有(5,3)、(5,4)67對于有向圖GVA)，一般用A(i)表示節(jié)點i的鄰接表，即節(jié)點i的所有出弧構(gòu)A(1){2,3}，A(5)3,4}星形（12n形（forwardstar）表示法。7所示的圖中，仍然假設(shè)?。?,3）和（5,4）8，9，6，4，0，3，67。此時該網(wǎng)絡(luò)圖可以用前向星形表示法表示為表2和表3。節(jié)點號123節(jié)點號123456起始地址 記錄弧信息的數(shù)267845523534權(quán)40367在數(shù)組point1（即n1），且一定有point(1)1point(n1)m1。對于節(jié)點i[point(i),point(i 1]如果point(ipoint(i1)，則節(jié)點i-似，記錄弧信息的數(shù)組”實際上相當(dāng)于有序存放的“弧表”。只是向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組（point）記錄每個節(jié)點出發(fā)的弧的起始編號。所有入弧。為了能夠快速檢索每個節(jié)點的所有入孤，可以采用反向星形（reversestar）12的所有弧，依此類推，最后存放進入節(jié)點n的所有孤。對每條弧，仍然依次存放其起點、終點、權(quán)的數(shù)值等有每個節(jié)點的入孤的起始地址（即弧的編號）7所示的圖，可以用反向星形表示法表示為表4和表5。4節(jié)點號 起始地址 表6782445524權(quán)906763前向星形表示法的基礎(chǔ)上，加上上面介紹的rpoint數(shù)組和如下的trace數(shù)組即可。這相當(dāng)于一種緊湊的雙向星形表示法，如表6所示。6反向法中弧編 正向法中弧編號trace( ①用的空較，并且那不提供針型的語（如N語言等）（如C語言等（(）。有關(guān)（即多重?。r，顯然此時鄰接矩陣表示③上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計算機中只鄰接矩陣的一半01，而不含有1，因為此時不區(qū)分邊的起點和終點。又如，在鄰接表和星形表示法中，每條邊會被兩次，而且反向星形表示顯然是沒有必要的，等等?！癢v0e1v1e2Lekvk，其中 E(G)，1ik，v V(G)，0jk，ei-vi1vi關(guān)聯(lián)，稱W是圖G的一條道路(walk)，k為路長，頂點v0和vk分別稱為W的起點和終點，而v1,v2,L,vk1稱為它的內(nèi)部頂點。若道路W的邊互不相同，則W稱為跡(trail)。若道路W的頂點互不相同，則W若圖G的兩個頂點u,v間存在道路，則稱u和v連通(connected)。uv的長叫做uv間的距離。記作d(uv)。若圖G的任二頂點均連通，則稱G是連通圖。圖P是一條軌的充要條件是P圖C是一個圈的充要條件是C2問題如下：給出了接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，以各城鎮(zhèn)為圖G的頂點，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數(shù)w(e)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G中指定的兩個頂點u0,v0間的具最小權(quán)的軌。這條軌叫做u0v0間的最短路，它的權(quán)叫做u0v0間的距離，亦記作d(u0,v0)。求最短路已有成算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0近到遠為順序，依次求得u0到G的各頂點的最短路和距離，直至v0（或直至G的所有(i)令l(u0)0，對vu0，令l(v) ，S0{u0}，i0(ii)對每個 S（SV\S），l(ii)對每個 S（SV\S）， min{l(v),l(u)uvSSi1SiU{ui1}(iii).若i|V 1，停止；若i|V 1，用i1代替i，轉(zhuǎn)(ii)算法結(jié)束時，從u0到各頂點v的距離由v的最后一次的標(biāo)號l(v)給出。在v進入之前的標(biāo)號l(v)T標(biāo)號，v進入Si時的標(biāo)號l(v)P標(biāo)號。算法就是不斷修改各頂點的T標(biāo)號，直至獲得標(biāo)號。若在算法運行過程中，將每一頂點獲得P標(biāo)號所由來的邊在圖上標(biāo)明，則算法結(jié)束時，u0例9某公司在六個城市c1,c2,L,c6中 ，從ci到cj的直接航程票價記下述矩陣的(i,j)位置上 表示無直接航路），請幫助該公司設(shè)計一張城市c1到其-50015200 40254020 10 15010 20100 25用矩陣ann（n為頂點個數(shù)）存放各邊權(quán)的鄰接矩陣，行向量pb、index1、index2d分別用來存放P量1當(dāng)?shù)趇；0當(dāng)?shù)趇index2(i)存放始點到第i點最短通路中第id(i)存放由始點到第i求第一個城市到其它城市的最短路徑的程序如下whilesum(pb)<length(a)d,index1,function%sb—起點的標(biāo)號db—輸出：mydistance—最短路的距離mypath—最短路的路徑n=size(a,1);visited(1:n)=0;distance(1:ninf-distance(sb)=0;parent(1:n)=0;fori=1:n-1id1=find(visited==1)查找已經(jīng)標(biāo)號的點temp(id1)=inf;%已標(biāo)號點的距離換成無窮[t,u]=min(temp);%找標(biāo)號值最小的頂點visited(u)=1;%標(biāo)記已經(jīng)標(biāo)號的頂點id2=find(visited==0)查找未標(biāo)號的頂點forv=id2ifa(u,v)+distance(u)<distance(v)distance(vdistance(ua(uv)修改標(biāo)號值parent(v)=u;

mypath=ifparent(db~0如果存在路!t=db;mypath=[db];whilet~=sbp=parent(t);mypath=[pmypath];t=p;mydistance=distance(db);wij假設(shè)有向圖有n1到頂點n的最短路。設(shè)Wwijnnw(vivj),viv 決策變量為xij，當(dāng)xij1，說明弧vivj位于頂點1至頂點n ；否則xij0。 j1 j1xji1,i wij vv xij0或103中，用點表示城市，現(xiàn)有A,B1B2C1C2,C3D7到城市D-37LINGOroads(cities,cities)/AB1,AB2,B1C1,B1C2,B1C3,B2C1,B2C2,B2C3,C1D,C2D,C3D/:w,x;w=2433123113n=@size(cities)城市的個數(shù);@for(cities(i)|i#ne#1#and#i#ne#n:@sum(roads(i,j)|i@sum(roads(i,j)|j#eq#n:x(i,j))=1;11（無向圖的最短路問題）4中v1到v11分析10寫LINGO程序。4LINGO-@for(roads(i,j):w(i,j)=@if(w(i,j)#eq#0,1000,w(i,j)));n=@size(cities);!城市的個數(shù);@for(cities(i)|i#ne#1#andi#ne#@sum(cities(j):x(j,1))=0不能回到頂點從頂點1離開后，再不能回到該頂點。1→2→5→6→3→7→10→9→1113法 法每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復(fù)執(zhí)行n 3 LM

Man

La1nLa2nLannaiiaijaij

i1,2,L,nijwij是ij之間邊的長度，i,j1,2,Ln對于無向圖，A0是對稱矩陣，aijajiFloyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列A0A1,LAk,LAnAk(ij)表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點序號不大于k的最短路徑長-Ak(i,j)min(Ak1(i,j),Ak1(i,k)Ak1(k,k是迭代次數(shù)，ij,k1,2,L,n最后，當(dāng)kn時，An即是各頂點之間的最短通路值。例12用Floyd算法求解例9。n=6;a=zeros(n);a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a+a'M=max(max(a))*n^2M為充分大的正實數(shù)fork=1:nfori=1:nforj=1:nifa,link(nodes,nodes):w,path!path標(biāo)志最短路徑上走過的頂點;@format(w(i,j),'10.0f')),@newline(1));@format(path(i,j),'10.0f')),@newline(1));@for(link(i,j)|i#ne#j:w(i,j)=@if(w(i,j)#eq#0,10000,w(i,j)));-path(i,j)=@if(w(i,j)#gt#tm,k,path(i,j));w(i,j)=tm)));sbdbFloydfunction%輸入：a—鄰接矩陣(aij)ijsb—起點的標(biāo)號；db—%輸出：dist—最短路的距離；mypath—最短路的路徑n=size(a,1);path=zeros(n);forforifpath(i,j)=j;%ji

forforforif

mypath=sb;t=sb;whilet~=db ((K)。 連通的無圈圖叫做樹，記之為T。若圖G滿足V(GV(T)，E(TE(G)則稱T是G的生成樹。圖G連通的充分必要條件為G有生成樹。通圖的生成樹的個數(shù)很多，用(G)表示G的生成樹的個數(shù)，則有公式公 n公式(G) e)(Ge)其中G e表示從G上刪除邊e，Ge表示把e的長度收縮為零得到的圖。1（i）G是樹當(dāng)且僅當(dāng)G-G是樹當(dāng)且僅當(dāng)G無圈，且 1G是樹當(dāng)且僅當(dāng)G連通，且 1G是樹當(dāng)且僅當(dāng)G連通，且 E(G)， e不連通G是樹當(dāng)且僅當(dāng)G無圈，eE(G)，Ge欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為Cij，設(shè)計一個線prim設(shè)置兩個集合P和Q,其中P用于存放G的最小生成樹中的頂點，集合Q存放的最小生成樹中的邊。令集合P的初值為Pv1}（假設(shè)構(gòu)造最小生成樹時，從頂點出發(fā)），集合Q的初值為Q。prim算法的思想是，從所有p P，v P的邊中，選取具有最小權(quán)值的邊pv，將頂點v加入集合P中，將邊pv加入集合Q中，如此不斷重復(fù)，直到PV時，最小生成樹構(gòu)造完畢，這時集合Q中包含了最小生成樹prim（i）P{v1}，Q（ii）whileP~找最小邊pv，其中 P, PPQQ{圖513prim5我們用result3n的第一、二、三行分別表示生成樹邊的起點、終點、權(quán)集合。a(1,2)=50;a(2,4)=65;a(4,5)=50;a(4,6)=30;a(4,7)=42;-whilelength(result)~=length(a)-1 Kruskal科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法如下選 E(G)，使得w(e1)min若e1,e2,L,ei已選好，則從E {e1,e2,L,ei}中選取ei1，使G[{e1e2,Leiei1}]w(ei1min直到選得e114Kruskal3我們用index2n號中較大序號u改記為此邊的另一序號v，同時把后面邊中所有序號為u的改記為v。此方法的幾何意義是：將序號u的這個頂點收縮到v頂點，u頂點不復(fù)存在。后面繼續(xù)a(1,2)=50;a(1,3)=60;a(2,4)=65;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;whilelength(result)<loopifv1~=v2- 定義若ME(G)，ei,e M，ei與ej無公共端點（ij），則稱M為G中的一個對集；M中的一條邊的兩個端點叫做在對集M中相配；M被M許配；G中每個頂點皆被M許配時，M稱為完美對集；G中已無使|M'||M|的對集M'，則M稱為最大對集；若G中有一軌，其邊交替地在對集M內(nèi)外出現(xiàn)，則稱此軌為M的交錯軌，交錯軌的起止頂點都未被許配時，此交錯軌稱為可增廣軌。若把可增廣軌上在M外的邊納入對集，把M2，對集中的“對兒”1957年，貝爾熱(Berge)定理 M是圖G中的最大對集當(dāng)且僅當(dāng)G中無M可增廣軌1935年，霍爾(Hall)3G為二分圖，X與Y是頂點集的劃分，G中存在把X中頂點皆許配的對集的充要條件是，SX，則|N(S||S|，其中N(S)是S1：若G是k次（k0)2分圖，則G有完美對集。所謂k次正則圖，即每頂點皆k度的圖。4每個姑娘都結(jié)識k(k1)位小伙子，每個小伙子都結(jié)識k人員分派問題：工作人員x1x2,Lxn去做n件工作y1y2,Lyn，每人適合做其GV(G)XUYX{x1,L,xn}，Y{y1,L,yn}，當(dāng)且僅當(dāng)xi適合做工作yj時，xiy E(G)，G解決這個問題可以利用1965年埃德門茲(Edmonds)匈牙利算法。從G中任意取定一個初始對集M若M把X中的頂點皆許配，停止，M即完美對集；否則取X中未被M許配的一頂點u，記S{u}，T。若N(S)T，停止，無完美對集；否則取 N(S T若y是被M許配的，設(shè)yz M，SSU{z}，TTU{y}，轉(zhuǎn)（iii）；否則，取可增廣軌P(u,y)，令M(M E(P))U(E(P) M)，轉(zhuǎn)（ii）。Gw(xiyj)0，表示xi干yj工作的效益，求 圖G上的權(quán)最大的完美對集。-定義若映射l:V(G)R，滿足 X, Yl(x)l(y)w(xy)，則稱l是二分圖GEl{xy|xy E(Glxlywxy)}，稱以El為邊集的G的生成子圖為相等子圖，記作Gl。l(x)maxw(xyyl(y)

XY定理 Gl的完美對集即為G的權(quán)最大的完美對集Kuhn-Munkres選定初始可行頂點標(biāo)號l，確定Gl，在Gl中選取一個對集M若X中頂點皆被M許配，停止，M即G的權(quán)最大的完美對集；否則，取中未被M許配的頂點u，令Su}，T若NGl(ST，轉(zhuǎn)（iv）；若NGl(S)TxS,l l, l(v),ll，GlGl（iv）選NGl(S T中一頂點y，若y已被M許配，且 M，則SSU{z}TTUy}，轉(zhuǎn)（iii）；否則，取Gl中一個M可增廣軌P(uy)M( E(P))U(E( M)其中NGl(S)是Gl中S EulerHamilton定

經(jīng)過G的每條邊的跡叫做GEulerEulerEuler回路或EulerEuler直觀地講，Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即6（i）GEuler圖的充分必要條件是G（ii）GEulerGG

i

i，CiE(Ci)IE(Cj)(ij)GEuler跡的充要條件是G定義包含GHamilton(哈密頓)Hamilton-l(v)l(v)l, TUHamilton圈或HHamiltonHamilton直觀地講，Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種6.2EulerFleury1921年，F(xiàn)leuryEulerFleury V(G)，令W0v02o.假設(shè)跡Wiv0e1v1Leivi已經(jīng)選定，那么按下述方法從E {e1,L,ei}中選取邊ei1：ei1和vi除非沒有別的邊可選擇，否則ei1不是GiG {e1,L,ei}的割邊(cutedge)。

2步不能再執(zhí)行時，算法停止。EulerFleuryEuler回路，此回路即為Euler圖，1973年，EdmondsJohnson給出下面的解法：設(shè)G是連通賦權(quán)圖。（i）求V0{v| V(G),d(v)1(mod2)}對每對頂點u,v V0，求d(u,v)（d(u,v)是u與v的距離，可用Floyd算法構(gòu)造完全賦權(quán)圖K|V0|，以V0為頂點集，以d(uv)為邊uv求K|V0|中權(quán)之和最小的完美對集M求M中邊的端點之間的在G在（vi）中得的圖G'Euler回路即為中國郵遞員問題的解。郵局有k(k2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時間最早？我們把這一問題記成kPP。kPPG(V,E)是連通圖， V(G)，求G的回路C1,L,Ck，使（i） V(Ci)，i1,2,L,k-

1i（ii（ii）i

E(C)Ew(e)mineE(CiHamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行Hamilton圈C，然后適當(dāng)修改C以得到具有較小權(quán)的另一個Hamilton圈。修改的方法叫做改良圈算法。設(shè)初始圈Cv1v2Lvnv1。對于1i1jnHamilton圈Cijv1v2Lvivjvj1vj2Lvi1vj1vj2Lvnv1C中刪去邊vivi1和vjvj1，添加邊vivj和vi1vj1w(vivjw(vi1vj1w(vivi1)w(vjvj1)，則以Cij代替C，Cij叫做CKruskal算法加以說明。假設(shè)C是G則對于任何頂點v，C v是在G v中的Hamilton軌，因而也是G v的生成樹。由此推知：若T是G v中的最優(yōu)樹，同時e和f是和v關(guān)聯(lián)的兩條邊，并使得w(ewf)盡可能小，則w(Tw(ew(f)將是w(C)

L15

離T

functionmainglobala-a(3,4)=36;a(3,5)=68;a(3,6)=68;a(5,6)=13;a=a+a';L=size(a,1);c1=[51:46];c2=[561:4];%改變初始圈，該算法的最后一個頂點不動iflong2<longfunction[circle,long]=modifycircle(c1,L);globalawhileform=1:L-3forn=m+2:L-iffori=1:L-1設(shè)城市的個數(shù)為n，dij是兩個城市i與j之間的距離，xij01（1表示走過城市i到城市xj的路，0表示沒有選擇走這條路）。則有 dijxijxij

jn

ij1，i1,2,Ln，（每個點只有一條邊出去ij1，j1,2,Ln，（每個點只有一條邊進去i,j

|s 1，2|s| 1，s{1,2,L,-

{0,1}，ij1,2,Ln，ij。其中|s|表示集合s中元素個數(shù)。LINGO例16已知SV地區(qū)各城鎮(zhèn)之間距離見表8，某公司計劃在SV地區(qū)做宣傳從城市1出發(fā)，經(jīng)過各個城鎮(zhèn)，再回到城市1。為節(jié)約開支，公司希望走過這10個城鎮(zhèn)的總距離最少。8 8解LINGOCITY/1..10/:U;!U(I)=sequenceno.ofcity;LINK(CITY,CITY):DIST,!ThedistanceX;!X(I,J)=1ifweuselinkI,DATA:!Distancematrix,itneednotbesymmetric;DIST=0859120 90860116110222217 !Themodel:Ref.Desrochers&Laporte,ORLetters,Feb.91;N=@SIZE(MIN=@SUM(LINK:DIST*X);@FOR(CITY(K):!Itmustbe@SUM(CITY(I)|I#NE#K:X(I,K))=!Itmustbe@SUM(CITY(J)|J#NE#K:X(K,J))=!Weakformofthesubtourbreaking!Thesearenotverypowerfulforlargeproblems;@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,!MaketheX's0/1;@FOR(LINK:@BIN(X));!Forthefirstandlaststopweknow...;@FOR(CITY(K)|K#GT#1:U(K)<=N-1-(N-2)*X(1,U(K)>=1+(N-2)*X(K,1)); V為節(jié)點集，A為弧集的有向圖GVA)L:AR為孤上的權(quán)函數(shù)，弧(i, A對應(yīng)的權(quán)L(i,j)記為lij，稱為(ij)的容量下界（lower（ii）U:AR為弧上的權(quán)函數(shù)，弧(i, A對應(yīng)的權(quán)U(i,j)記為uij，稱為(ij)的容量上界，或直接稱為容量（iii）D:VR為頂點上的權(quán)函數(shù)，節(jié)點i V對應(yīng)的權(quán)D(i)記為di，稱為頂點i的供需量（supply／demand）；NVAL,UD)由于我們只討論V,A為有限集合的情況，所以對于弧上的權(quán)函數(shù)L,U和頂點上的權(quán)函數(shù)D，可以直接用所有孤上對應(yīng)的權(quán)和頂點上的權(quán)組成的有限維向量表示，因此L,U,D有時直接稱為權(quán)向量，或簡稱權(quán)。由于給定有向圖G(V,A)后，我們總是可在流網(wǎng)絡(luò)中，弧(i,j)的容量下界lij和容量上界uij表示的物理意義分別是：通過該弧發(fā)送某種“物質(zhì)”時，必須發(fā)送的最小數(shù)量為lij，而發(fā)送的最大數(shù)量為uij。頂點i 對應(yīng)的供需量di則表示該頂點從網(wǎng)絡(luò)外部獲得的“物質(zhì)”數(shù)量（di0時），或從該頂點發(fā)送到網(wǎng)絡(luò)外部的“物質(zhì)”數(shù)量（di0時）定義對于流網(wǎng)絡(luò)NVAL,UD)，其上的一個流（flow）f是指從N集A到R的一個函數(shù)，即對每條弧(ij)賦予一個實數(shù)fij（稱為弧(ij)的流量）。如果流f滿足j:(i,j)

j:(j,i)

jidi V lijfijuij (i, A 則稱f為可行流（feasibleflow）。至少存在一個可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasible可見，當(dāng)di0時，表示有di個單位的流量從網(wǎng)絡(luò)外部流入該頂點，因此頂點i-為供應(yīng)點（supplynode）或源（source），有時也形象地稱為起始點或發(fā)點等；當(dāng)di0時，表示有|di|個單位的流量從該頂點流失到網(wǎng)絡(luò)外部（或說被該頂點吸收），因此頂點i稱為需求點（demandnode）或匯（sink），有時也形象地稱為終止點或收點等；當(dāng)di0時，頂點i稱為轉(zhuǎn)運點（transshipmentnode）或平衡點、中間點等。此外，根據(jù)dii

0一般來說，我們總是可以把L0的流網(wǎng)絡(luò)轉(zhuǎn)化為L0的流網(wǎng)絡(luò)進行研究。所以，除非特別說明，以后我們總是假設(shè)L0（即所有孤(i,j)的容量下界lij0），并將L0時的流網(wǎng)絡(luò)簡記為N(V,A,U,D)。此時，相應(yīng)的容量約束（2）為0fijuij (i, A定義在流網(wǎng)絡(luò)NVA,UD)中，對于流ffij (i, A則稱f為零流，否則為非零流。如果某條弧(i,j)上的流量等于其容量（fijuij），則稱該弧為飽和?。╯aturatedarc）；如果某條弧(i,j)上的流量小于其容量（fijuij），則稱該弧為非飽和?。蝗绻硹l弧(ij)0（fij0），則稱該弧為空?。╲oid 網(wǎng)絡(luò)N(V,A,U,D)：節(jié)點s為網(wǎng)絡(luò)中唯一的源點，t為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流f，此時稱流f的流量（或流值，flowvalue）為ds（根據(jù)（3），它自然也等于 dt），通常記為v或v(f)，即vvf)ds dt對這種單源單匯的網(wǎng)絡(luò)，如果我們并不給定ds和dt（即流量不給定），則網(wǎng)絡(luò)一般記為N(s,t,V,A,U)。最大流問題（ umflowproblem）就是在N(s,t,V,A,U)中找到流值最大的可行流（即最大流）。 max j:(i,j)

j(j,i)

0,is,0fijuij (i, A 定義如果一個矩陣A的任何子方陣的行列式的值都等于0，1或 1，則稱A是全幺模的(totallyunimodularTU，又譯為全單位模的)，或稱A是全幺模矩陣。7（整流定理）

-fjiv,i最大流問題是一個特殊的線性規(guī)劃問題。會看到利用圖的特點，解決這個問單源和單匯網(wǎng)G化成單源單匯網(wǎng)絡(luò)G'。設(shè)X是G的源，Y是G的匯，具體轉(zhuǎn)化方法如下：在原圖G中增加兩個新的頂點x和y，令為新圖G'中之單源和單匯，則G中所有頂點V成為G'之中間頂點集。x連接到X若,若G和G'中的流以一個簡單的方式相互對應(yīng)。若f是Gf(a),若a是Gf'G'中使得vfvf)的流，這里f(v)vf(v),若a(v,f(v)表示流入v的流量（在G中）。反之，G'中的流在G的弧集上的限制就是G中設(shè)N(s,t,V,A,U)，SV，s S，tV S，則稱(S,S)為網(wǎng)絡(luò)的一個割，其中SV S，(S,S)為尾在S，頭在S的弧集，稱C(S,S)為割(SS)

(i,j)AiS,j

定理 f是最大流，(S,S)是容量最小的割的充要條件vfC(SS)在網(wǎng)絡(luò)Nst,V,A,U)中，對于軌(sv2,L,vn1t)（此軌為無向的）vivi A，則稱fij,向?。蝗魐i 在網(wǎng)絡(luò)N中，從s到t的軌P上，若對所有的前向弧(ij)都有fijuij，對所有的后向弧(i,j)恒有fij0，則稱這條軌P為從s到t的關(guān)于f的可增廣軌。令 fij,當(dāng)（ij)，當(dāng)（i,j)為后向min{ij則在這條可增廣軌上每條前向弧的流都可以增加一個量，而相應(yīng)的后向弧的流可減，這樣就可使得網(wǎng)絡(luò)的流量獲得增加，同時可以使每條弧的流量不超過它的容量，而且保持為正，也不影響其它弧的流量?？傊W(wǎng)絡(luò)中f可增廣軌的存在是有意義的，因為這意味著f不是最大流。-標(biāo)號法是由Ford和Fulkerson在1957年。用標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基.i）可s

則給頂y標(biāo)號x,y)，若fxyuxy，則不給頂點y標(biāo)號若頂點x已經(jīng)標(biāo)號，則對x的所有未標(biāo)號的鄰接頂點yy Afyx0yminfyx,x}，則給y標(biāo)號x,y)，①若(x, A，且fxyuxy時，令ymin{u fxy,x}fyx0，則不給y不斷地重復(fù)步驟（ii）直到收點t被標(biāo)號，或不再有頂點可以標(biāo)號為止。當(dāng)被標(biāo)號時，表明存在一條從s到t的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若t標(biāo)號，且不存在其它可以標(biāo)號的頂點時，表明不存在從s到t的可增廣軌，算法結(jié)束，（i）令utfuvf t（iii）若us，把全部標(biāo)號去掉，并回到標(biāo)號過程（A）。否則，令uv，并回求網(wǎng)絡(luò)Nst,VA,U)中的最大流x對每個節(jié)點j(pred(j),max該節(jié)點在可能的增廣路中的前一個節(jié)點pred(j)，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量maxf(j)。1）

置初始可行流x（如零流）；對節(jié)點t標(biāo)號，即令maxft=任意正值（若maxf(t)0，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。取消所有節(jié)點j V的標(biāo)號，即令maxf(j)0，pred(j0LIST={s}，對節(jié)點s標(biāo)號，即令maxf(s LIST且maxft0，繼續(xù)下一步；否則：（3a）如果t標(biāo)號（即maxft0），則找到了一條增廣路，沿該增廣路對流x進行增廣（增廣的流量為maxf(t)，增廣路可以根據(jù)pred回溯方便地得到），轉(zhuǎn)STEP1。-（3b）如果t沒有標(biāo)號（LIST=且maxft0）STEP4LIST中移走一個節(jié)點i；尋找從節(jié)點i出發(fā)的所有可能的增廣?。海?a）對非飽和前向弧(i,j)，若節(jié)點j沒有標(biāo)號（即pred(j)0），對j進行標(biāo)號，即令maxf(j)min{maxf(i),uij xij}，pred(ji，并將j加入LIST中。（4b）對非空后向弧ji)，若節(jié)點j沒有標(biāo)號（即pred(j0），對jmaxf(j)min{maxf(i),xij}，pred(j) i并將jLIST17Ford-Fulkerson6網(wǎng)絡(luò)中的最大流，每條弧上的兩個數(shù)字分圖6解編寫程序如下：whilemaxf(n)>0while(~isempty(list))&(maxf(n)==0)label1=find(u(flag,:)-f(flag,:));ifv2=n;v1=pred(v2);whilev2~=1-

ifv2=v1;v1=pred(v2);例18現(xiàn)需要將城市s的石油通過管道運送到城市t，中間有4個中轉(zhuǎn)站v1v2和v4，城市與中轉(zhuǎn)站的連接以及管道的容量如圖7所示，求從城市s到城市t圖7解使用最大流的數(shù)學(xué)規(guī)劃表達式，編寫LINGOarcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,f;c=87952596n=@size(nodes)頂點的個數(shù);@for(nodes(i)|i#ne#1#and#i#ne#n:@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@sum(arcs(i,j)|j#eq#n:f(i,j))=flow;-n=@size(nodes)頂點的個數(shù);@for(nodes(i)|i#ne#1#and#i#ne#n:的費用問題，在許多實際問題中，費用的因素很重要。例如，在問題中，人們總是希望在完成任務(wù)的同時，尋求一個使總的費用最小的方案。這就是下面要 網(wǎng)絡(luò)N(s,t,V,A,U)中，設(shè)cij是定義在A上的非負函數(shù)，它表示通過(ij)單位流的費用。所謂最小費用流問題就是從發(fā)點到收點怎樣以最小費用輸送一已知量為v(f)的總流量。最s.t.ffdi問題可以用如下的線性規(guī)劃問題描述 cij(i,j) j:(i,j) j:(j, 其中d v(f),i0fijuij (i, Av(f),i0,is,顯然，如果vf最大流vfmax)vfvfmax)例19（最小費用最大流問題）（續(xù)例18）由于輸油管道的長短不一或地質(zhì)等原因， 管道輸送最大流的最小費用。圖8所示是帶有運費的網(wǎng)絡(luò)，其中第1個數(shù)字是網(wǎng)絡(luò)的容28-解LINGOarcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,u,f;d=14000014!最大流為c=28251634u=87952596205210類似地，可以利用賦權(quán)鄰接矩陣編程求得最小費用最大流。LINGOd=140000-14;c=0;u=0;求最小費用流的法—迭代Busacker在1961 {st)st)(i,j)(s,t并讓 的所有邊的容量相應(yīng)減少f。這時，對于 -相應(yīng)改 s,t)上所有邊(i,j)的反向邊ji)ujif，cji 部流量等于v(f)為止（或者再也找不到從s到t的最小費用道路）。mincostmaxflowFloyd算法求最短路的函數(shù)floydpath。19具體程序如下（下面的全部程序放在一個文件中functionmainexample19globalMnumfunctionpath=floydpath(w);globalMnumforforforif

ifw(1,num)==M

while~isempty(m)if-

function%返回值flow為可行流矩陣,val為最小費用值globalMifnargin<3whileallflow<flowvaluepath=floydpath(w);%調(diào)用floydpath函數(shù)ifisempty(path) 計劃評審方法（programevaluationandreviewtechnique,PERT）和關(guān)鍵路（criticalpathmethod,CPM）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛地用于系統(tǒng)分析和項2050年代提出并發(fā)展起來的，1956年，杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃，提出了關(guān)鍵路。1958年，部在研制“北極星”計劃時，由于的研制系統(tǒng)過于龐大、復(fù)雜，PERTCPM既有著相同的目標(biāo)應(yīng)用，又有很多相同的術(shù)語，這兩種方法已合并為法，在國外稱為PERT/CPM，在國內(nèi)稱為統(tǒng)籌方法（schedulingmethod）。例

11項作業(yè)組成（分別用代號AB,LJK表示），99作 計劃完成時間（天

緊前作 作

計劃完成時間（天

A5—A5—B—C—D4BE4AFC,GB,HB,IB,JF,G,KF,-例20就是計劃評審方法或關(guān)鍵路需要解決的問題

9所示，1，2，3表示事件，A,B表示作業(yè)。由這種方法畫出的網(wǎng)絡(luò)圖稱為計劃網(wǎng)絡(luò)圖。920 事件j的最早時間用tEj)表示，它表明以它為始點的各工作最早可能開始的時設(shè)事件編號為1,2,LntE(1)Ei其中tE(i)是與事件j相鄰的各緊前事件的最早時間，t(ij)是作業(yè)(ij)所需的工時。tE(n)總最早完工 事件i的最遲時間用tL(i)表示，它表明在不影響任務(wù)總工期條件下，以它為始點-t(j)max{t(i)t(i,為 tL(n總工期（或tELj

其中tLj)是與事件iES的最早可能開工時間與工作的最早可能完工時一個作(ij)的最早可能開工時間用tES(ij)表示。任何一件工作都必須在其所有緊前工作全部完工后才能開始。工作(i,j)的最早可能完工時間用tEF(i,j)表示。它t(1,j)tES(i,j)max{tES(k,i)t(k,ktEF(i,j)tES(i,j)t(i,

這組公式也是遞推公式。即所有從總開工事件出發(fā)的工作(1,j)，其最早可能開工時間為零；任一工作(ij)的最早開工時間要由它的所有緊前工作(ki)的最早開工時間決定；工作(i,j)的最早完工時間顯然等于其最早開工時間與工時之和。工作的最遲必須開工時間與工作的最遲必須完工時一個工作(ij)的最遲開工時間用tLS(ij)表示。它表示工作(ij)在不影響整個任工作(ij)的最遲必須完工時間用tLF(ij)表示。它表示工作(ij)按最遲時間開t(i,n)總完工期（或t(i, tLS(i,j)min{tLS(j,k t(i,ktLF(i,j)tLS(i,j)t(i,

總完工事件n的工作(in)，其最遲完工時間必須等于預(yù)定總工期或等于這個工作的最早可能完工時間。任一工作(ij)的最遲必須開工時間由它的所有緊后工作jk)的最遲開工時間確定。而工作(i,j)的最遲完工時間顯然等于本工作的最遲開工時間與工時由于任一個事件i（除去始點事件和終點事件）（9（0）6）8）(i,的最早可能開工時間tES(ij)就等于事件i的最早時間tE(i)。工作(ij)的最遲必須完工時間等于事件j的最遲時間。-在不影響任務(wù)總工期的條件下，某工作(ij)可以延遲其開工時間的最大幅度，叫做該工作的總時差，用R(i,j)表示。其計算公式為：R(i,j)tLF(i, tEF(i, 即工作(ij)的總時差等于它的最遲完工時間與最早完工時間的差。顯然R(ij)也等于開工時間的最大幅度，用r(i,j)表示。其計算公式為：r(i,j)tES(j,k tEF(i,

2020101020設(shè)xi是事件i的開始時間，1為最初事件，n為最終事件。希望總的工期最短，即極小化 x1。設(shè)tij是作業(yè)(i,j)的計劃時間，因此，對于事件i與事件j有不等xjximin xjxitij，(i, A，i, xi0，i其中V是所有的事件集合，A用LINGO軟件求解例20。解LINGO程序如下：operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7-t=5101144 計算結(jié)果給出了各個項目的開工時間，如x10，則作業(yè)A,B,C的開工時間均是0天；x25，作業(yè)E5天；x310，則作業(yè)D的開工時間是第10天；等等。每個作業(yè)只要按規(guī)定的時間開工，整個項目的最短工期為51天。LINGOii對應(yīng)弧上的松弛變量sij，且sijxj tij，(i,j) A，這樣就可以得到作業(yè)的最遲開工時間，記yi表示事件i的最遲開工時間。當(dāng)最早開工時間與最遲開工時間相同時，LINGOoperate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=58834 c=07004004500006003005000500400;最遲開工時間的分析需要用到松弛變量sij，當(dāng)sij0-應(yīng)作業(yè)的工期可以推遲sij。例如，s781，作業(yè)（7，8）（J）36。再如s462，作業(yè)（4，6）（F）2天開始，s143，作業(yè)（1，4）（C）可以推遲3天開始，但由于作業(yè)（4，6）（F）已能夠推遲2天，所以，作業(yè)（1，4）（C）最多可推遲5天。12(i,計劃完成時間（天作業(yè) 計劃完成時間（天5HCI4J4KF111→3→圖

設(shè)xij0-1變量，當(dāng)作業(yè)(ij)10 (ij)

ij

j(i,j) (j,i)

i例

xij0或1，(i, 20 -

LINGO 1xji1,i i1,operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 d=1000000-511→3→5→6→823（關(guān)鍵路線與計劃網(wǎng)絡(luò)的優(yōu)化）2049天內(nèi)完成。20中可縮短工期的所有作業(yè)和縮短一天工期額外增加的費用。現(xiàn)在的問題11作 計劃完 最短完成縮短1天增加作 計劃完 最短完成縮短1天增(ij)時間（天）時間（天）費用（元）(ij)時間（天）時間（天）（元8H8IE43JK23所涉及的問題就是計劃網(wǎng)絡(luò)的優(yōu)化問題，這時需要壓縮關(guān)鍵路徑來減少最短設(shè)xi是事件i的開始時間，tij是作業(yè)(ij)的計劃時間，mij是完成作業(yè)(ij)的最短時間，yij是作業(yè)(i,j)可能減少的時間，cij是作業(yè)(i,j)縮短一天增加的費用，因此有x xi yij且0yij 設(shè)d是要求完成的天數(shù)，1為最初事件，n為最終事件，所以有 x1d。而問題總目標(biāo)是使額外增加的費用最小，即目標(biāo)函數(shù)為 cijyij。由此得到相應(yīng)的數(shù)(i,j) (i,j)

xj xiyijtij，(i,j) A，i,j x1d-0yij mij，(i, A，i, LINGO23operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=58834 c=07004004500006003005000500400;作業(yè)(1,3)(B)）1天的工期，作業(yè)(6,8)(K)149天完工，需要多花費1200元。24（23）LINGO23，并求出相應(yīng)的關(guān)鍵路徑、各作業(yè)的解為了得到作業(yè)的最早開工時間，仍在目標(biāo)函數(shù)中加 i

，記zi表示事件寫出相應(yīng)的LINGO程序如下：operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=58834 c=07004004500006003005000500400;-12(i,實際完成時間（天作業(yè) 實際完成時間（天59HCI4JE4KF125-1012完成作業(yè)期望事件的概20中，每項作業(yè)完成的時間均看成固定的，但在實際應(yīng)用中，每一工作的完估計值：最樂觀值的估計值（a），最悲觀的估計值（b）和最可能的估計值（m）。設(shè)tij是完成作業(yè)(i,j)的實際時間（是一隨 aij4mijE(tij)

6var(tij)

aij)設(shè)TT (i,j)

由中心極限定理，可以假設(shè)T-TE(T) E(tij(i,j)S2var(T) var(tij(ij)設(shè)規(guī)定的工期為d

d

@psn(x)LINGO@psn(x)(x)

2520估計時間（天估計時間（天(i,amb(i,amb35789H8I246J345KF8LINGOoperate(events,events)/12,13,14,25,34,35,46,557,58,67,68,78/:a,m,b,et,dt,x;a=388320 m=591144 3252025d=1000000--P{Td} et/513.165262.4%9556.2 要鋪設(shè)一條A1A2LA15的輸送天然氣的主管道,如圖14所示。經(jīng)篩選 的鋼廠有S1,S2,LS7。圖中粗線表示鐵路，單細線表示公 數(shù)字表示里程(單位km)圖為方便計，1km為方便計，1km稱為1。3少需要生45005位。鋼廠6Si7內(nèi)能生產(chǎn) i31單 的鐵路運價見表15表15單位里程-里程1000km以上每增加1至100km運價增加5萬元。公路費用為1單位每公里0.1萬元（不足整公里部分按整公里計算）。可由鐵路、公路運往鋪設(shè)地點（不只是運到點A1,A2,L,A15，而是管道全線）。請制定一個主管道的訂購 請就（1）的模型分析：哪個鋼廠的銷價的變化對購運計劃和總費用影響15（1）的要求給出模型和結(jié)

圖記第i個鋼廠的最大供應(yīng)量為si，從第i個鋼廠到鋪設(shè)節(jié)點j的訂購和費用為cij；用lj表示管道第j段需要鋪設(shè)的量。xij是從鋼廠i運到節(jié)點j的量，yj是從節(jié)點j向左鋪設(shè)的 量，zj是從節(jié)點j向右鋪設(shè)的 根據(jù)題中所給數(shù)據(jù)，我們可以先計算出從供應(yīng)點Si到需求點Aj的最小購運費（即出廠售價與費用之和），再根據(jù)cij求解總費用，總費用應(yīng)包括：訂購費用（包含在cij中）（由各廠SiAj，i1,2,L,7j1,2,L,15），鋪設(shè)管道AjAj1j1,2,L,14)- 及從Si（i1,2,L,7）運送到Aj（j1,2,L,15）的最小購運費用cij的計算：w

（dijij兩點之間的鐵路路程。VS1,LS7A1,LA15B1,LB17}14；W1wij13939 的最小費用cij。其中，路徑值無窮大時的費用也為無窮大 2 2 2 2 393用 來計算由于鐵路運費不是連續(xù)的，故不能直接用Floyd算法來計算最小 構(gòu)造公路距離賦權(quán)圖G (V,E,W),其中V同上，W (wij) 2 2 2 2 393用 來計算Floyd最 1②計算公路任意兩點間的最小費

dij表示i，j兩點之間的公路路程2計算）”，計算出公路任意兩點間的最小費用cij。路徑值為無窮大時的費用也為wij2 ij之間沒有公路直接相依據(jù)題中“公路費用為1單位每公里0.1萬元（不足整公里部分按整公2③計算任意兩點間的最小費由于可以用路、公路交叉運送，所以任意相鄰兩點間的最小費用為鐵路、公路兩者最小費用的最小值。GV,E,W)，W(c~ij)3939c~ijmincij1cij2)對圖GFloyd算法，就可以計算出Si（i1,2,L,7）到Aj（j1,2,L,15）的最小運送費用cij(單位：萬元)見表16。16最小運費計算結(jié)果2,S（i1,2,L,7）到Aj（j1,2,L,15） 和運送最小費用cij-運量約束：xij對i求和等于zj加yj；yj1與zj之和等于AjAj1段的長度ljAj向AjAj1段鋪設(shè)管道的總路程為1Lyjyjyj1)2；Aj向AjAj1段鋪設(shè)管道的總路程為1Lzjzj(zj1)/2。

7i1j

0.12

i j7zjyjiyj1zjlxij0,zj0,yjy10,z15ji1,2,L7,jLingo使用計算機求解上述數(shù)學(xué)規(guī)劃時，需要對約束條件（20）進行處理。我們引進 1,鋼廠i生0廠i不生j

Lingo127.8632億。Lingo!nodes表示節(jié)點集合nodes/S1,S2,S3,S4,S5,S6,S7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,!c1(i,j)表示節(jié)點i到j(luò)鐵路的最小運價（萬元）,c2(i,j)表示節(jié)點i到j(luò)公路的-cijxij (zj(zj1)yj(yjx0U[500,sxfi500fi xijsifi，i用鄰接矩陣，c(i,j)ij的最小運價，path標(biāo)志最短路徑上走過的頂點;link(nodes,nodes):w,c1,c2,c,path1,path;need/A1..A15/:b,y,z;y表示每一點往左鋪的量，z表示往右鋪的量;linkf(supply,need):cf,X;S=8008001000200020002000P=160155155160155150160;path1=0;path=0;w=0;!以下是格式化輸出計算的中間結(jié)果和最終結(jié)果;@text(MiddleCost.txt)=@writefor(supply(i):@writefor(need(j):@format(cf(i,j),'6.1f')),@newline(1));@text(FinalResult.txt)=@writefor(need:@format(y,'5.0f'));@text(FinalResult.txt)=@writefor(need:@format(z,'5.0f'));@for(link(i,j):w(i,j)=w(i,j)+w(j,i));!輸入鐵路距離鄰接矩陣的下三角元素;@for(link(i,j)|i#ne#j:w(i,j)=@if(w(i,j#eq0,20000,w(i,j)));!無鐵路連接，元素為充分!以下就是最短路計算公式（Floyd-Warshall算法）;path1(i,j)=@if(w(i,j)#gt#!wC1的計算公式;@for(link|w#eq#0:C1=0);@for(link|w#gt#0#and#w#le#300:C1=20);@for(link|w#gt#300#and#w#le#350:C1=23);@for(link|w#gt#350#and#w#le#400:C1=26);@for(link|w#gt#400#and#w#le#450:C1=29);@for(link|w#gt#450#and#w#le#500:C1=32);@for(link|w#gt#500#and#w#le#600:C1=37);@for(link|w#gt#600#and#w#le#700:C1=44);@for(link|w#gt#700#and#w#le#800:C1=50);@for(link|w#gt#800#and#w#le#900:C1=55);@for(link|w#gt#900#and#w#le#1000:-@for(link|w#gt#1000:C1=60+5*@floor(w/100-10)+@if(@mod(w,100)#eq#0,0,5)@for(link(i,jc2(i,jc2(i,j)+c2(j,i)輸入公路距離鄰接矩陣的下三角元素@for(link(i,j):c2(i,j)=0.1*c2(i,j));!距離轉(zhuǎn)化成費用@for(link(i,j)|i#ne#j:c2(i,j)@if(c2(i,j)#eq#0,10000,c2(i,j)無公路連接，元素為充分@for(link:C C1C2矩陣對應(yīng)元素取最小path(i,j)=@if(C(i,j)#gt#@for(link(i,j)|i#le#7and#j#ge#8#andj#le#22:cf(i,j-7)=c(i,j)提取下面二次規(guī)劃模型需要的7×15矩陣;!約束@for(supply(i):[con1]@sum(need(j):x(i,j))<=@for(supply(i):[con2]@sum(need(j):x(i,j))>=@for(need(j):[con3]@sum(supply(i):x(i,j))=y(j)+z(j));@for(need(j)|j#NE#15:[con4]z(j)+y(j+1)=b(