第五章§1圖論于18世紀。第一篇圖論是數學家歐拉于1736年的“哥尼1哥尼斯堡七橋問圖與網絡是運籌學（OperationsResearch）中的一個經典和重要的分支，所研究的我們首先通過一些例子來了解網絡優化問題。1最短路問題（SPP－shortestpathproblem）2例 例 梅谷教授1960年首先，所以國際上稱之為中國郵遞員問題。例 例 種意義下的最優安排或方案，數學上把這種問題稱為最優化或優化（opn）問為網絡（network。與圖和網絡相關的最優化問題就是網絡最優化或稱網絡優化（netwokoptimization）問題。所以上面例子中介紹的問題都是網絡優化問題。由于多絡流（networkflows）或網絡流規劃等。§2一個無向圖(undirectedgraph)G是由一個非空有限集合V(G和V(G中某些元素的無序對集合E(G)構成的二元組，記為GV(GE(G))。其中V(G){v1v2L,vn}稱為圖G的頂點集（vertexset）或節點集（nodeset，V(G中vi(i1,2,Ln稱為該圖的一個頂點（vertex）或節點（node）；E(Ge1e2Lem稱為圖G的邊集（edgesetE(G中的每一個元素ek(即V(G)vivj的無序對ekvivjekvivjv被稱為該圖的一條從vi到vj的邊（edge

(k1,2,L,m)當邊ekvivj時，稱vivj為邊ek的端點，并稱vj與vi相鄰（adjacent；邊ek稱（incident圖G中相鄰。network一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖G的頂點數用符號|V|(G表示，邊數用|E|或(G當的圖只有一個時，總是用G來表示這個圖。從而在圖論符號中我們常略去字母G，例如，分別用VE,和代替V(GE(G),(G)和(G。端點重合為一點的邊稱為環(loop)一個圖稱為簡單圖 graph)，如果它既沒有環也沒有兩條邊連接同一對頂點定義一個有向圖（directedgraphdigraph）G是由一個非空有限集合V和V中A構成的二元組，記為GVA。其中Vv1v2Lvn稱為圖G的頂點集或節點集，Vvi(i1,2,L,n)稱為該圖的一個頂點set，某兩個元素vivj的有序對)記為akvivj或akvivj(k1,2,Ln，被稱為該圖的一條從vi到vj的弧（arc當弧akvivj時，稱vi為ak的尾（tailvj為ak的頭（head，并稱弧ak為vi的出弧（outgoingarc，為vj的入弧（ingarc。樣的有向圖稱為G的一個定向圖。的完全圖記為Kn。若V(GXUYXIY，|X||Y|0（這里|X|表示X中的元素個數XY中亦然，則稱G為二分圖(bipartitegraph)H叫做圖G的子圖（subgraph），記作HGV(HV(G)E(HE(GH是G的子圖，則GH的母圖G的支撐子圖（spanningsubgraph，又成生成子圖）是指滿足V(HV(G的子圖H。設vV(G，G中與v關聯的邊數（每個環算作兩條邊）稱為v的度(degree)，記作d(v)。若d(v)是奇數，稱v是奇頂點(oddpoint)d(v)是偶數，稱v是偶頂點(evend(v)表示法、鄰接表表示法和星形表示法。在下面數據結構的中，我們首先假設G(V,A是一個簡單有向圖，|V|n,|A|m，并假設V中的頂點用自然數1,2,Ln表示或，A中的弧用自然數1,2,L,m表示或。對于有多重邊或無向網絡的情況，GVAC是一個nn的01C(cij)nn{0,1}nncij

(i,j)(i,j)2例 00

00同樣，對于網絡中的權，也可以用類似鄰接矩陣的nn矩陣表示。只是此時一條B(bik)nm{1,0,1}nm

jV,k(i,j)jV,k(j,i)1；如果一個節點是一條弧的終點，則關聯矩陣中對應的元素為1；如果一個節點與一條弧不關聯，則關聯矩陣中對應的元素為0。對于簡單圖，關聯矩陣每列只含有兩個非零元（一個1，一個1。可以看出，這種表示法也非常簡單、直接。但是，在關聯矩陣的所有nm個元素中，只有2m個為非零元。如果網絡比較稀疏，這種表示法也會浪費大量的空間。但由于87所示的圖，如果關聯矩陣中每列對應弧的順序為(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關聯矩00

0010010000001000010001100000101弧表表示法將圖以弧表（arclist）的形式在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序對。弧表表示法直接列出所有弧的起點和終點，共需2m個存應地用額外的單元表示。例如，例7所示的圖，假設弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)8，9，6，4，0，3，6711123445523423534權89640367鄰接表表示法將圖以鄰接表（adjacencylists）的形式在計算機中。所謂圖的組表示。例如，例7所示的圖，鄰接表表示為1個數據域表示弧的另一個端點（弧的頭(1,3)9對于有向圖G(V,A，一般用A(i)表示節點i的鄰接表，即節點i的所有出弧構也就是說，在該數組中首先存放從節點1出發的所有弧，然后接著存放從節點2出發的所有孤，依此類推，最后存放從節點n出發的所有孤。對每條弧，要依次存放其起點、（forwardstar）（1,2（l,3（2,4（3,2（4,3（4,5，（5,3）和（5,4）8，9，6，4，0，3，67。此時該網絡圖可以用前向星形表示法表示為表2和表3。表2節點對應的出弧的起始地址數節點號123456 弧56781123445523423534權89640367[point(i),point(i1)point(i)point(i1)，則節點i后有序存放，并增加一個數組（point）記錄每個節點出發的弧的起始。有入弧。為了能夠快速檢索每個節點的所有入孤，可以采用反向星形（reversestar）表后存放進入節點n的所有孤。對每條弧，仍然依次存放其起點、終點、權的數值等有關個節點的入孤的起始地址（即弧的。例如，例7所示的圖，可以用反向星形表示法表示為表4和表5。表4節點對應的入弧的起始地址數節點號1234561 弧6782233344531權763當于一種緊湊的雙向星形表示法，如表6所示。6兩種表示法中的弧的對應關 12345678 trace(41257836①星形表示法和鄰接表表示法在實際算法實現中都是經常采用的。星形表示法的優點是占用的空間較少，并且對那些不提供指針類型的語言（如FORTRAN語言量較大（需要花費O(m的計算時間。有關“計算時間”的觀念是網絡優化中需要（即多重弧）時，顯然此時鄰接矩陣表示0和1，而不含有1，因為此時不區分邊的起點和終點。又如，在鄰接表和星形表示Wv0e1v1e2Lekvk，其中eiE(G，1ik，vjV(G，0jk，eivi1vi關聯，稱W是圖G的一條道路(walk)，k為路長，頂點v0和vk分別稱為W的起點和終點，而v1,v2,L,vk1稱為它的頂點。若道路W的邊互不相同，則W稱為跡(trail)。若道路W的頂點互不相同，則W稱若圖G的兩個頂點uv間存在道路，則稱u和v連通(connected)。uv間的最短軌的長叫做uv間的距離。記作d(uv。若圖G的任二頂點均連通，則稱G2；圖C是一個圈的充要條件是C2G的子圖的權是指子圖的各邊的權和。問題就是求賦權圖G中指定的兩個頂點u0v0間的具最小權的軌。這條軌叫做u0v0間的最短路，它的權叫做u0v0間的距離，亦記作d(u0,v0)。求最短路已有成算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0從近到遠為順序，依次求得u0到G的各頂點的最短路和距離，直至v0（或直至G令l(u00，對vu0，令l(v)S0u0i0對每個vSi（SiVSimin{l(v),l(u)代替l(v)。計算min{l(v)}，把達到這個最小值的一個頂點記為ui1，令Si1SiU{ui1}(iii).若i|V|1，停止；若i|V|1，用i1代替i，轉(ii)算法結束時，從u0v的距v的最后一次的標號l(v)給出。在vSi之前的標號l(v)TvSi時的標號l(v)P標號。算法就是不斷修改各頂TPP標號所由來的邊在圖上標明，則算法結束時，u0至各項點的最短路也在圖上標示出來了。9某公司在六個城市c1c2L,c6中有，從ci到cj的直接航程票價記在

0用矩陣ann（n為頂點個數存放各邊權的鄰接矩陣，行向量pbindex1index2dP標號信息、標號頂點順序、標號頂點索引、最短通路的值。其中分0pb(i)0

；index2i)存放始點到第i點最短通路中第id(i)存放由始點到第iwhilesum(pb)<length(a)tb=find(pb==0);d,index1,ww(vivj vivj 其決策變量為xij，當xij1，說明弧vivj位于頂點1至頂點n的；否則xij0。其n

n

is.t.xijxji i E

i1,viv

v xij0或10在圖3中，用點表示城市，現A,B1B2C1C2C3D7個城市。點與到城市D鋪設一條天然氣管道，請設計出最小價格管道鋪設方案。37個城市間的連線roads(cities,cities)/AB1,AB2,B1C1,B1C2,B1C3,B2C1,B2C2,B2C3,C1D,C2D,C3D/:w,x;w=2433123113@for(cities(i)|i#ne#1#and#i#ne#n:11（無向圖的最短路問題）求圖4中v1到v11的最分析例10處理的問題屬于有向圖的最短路問題，本例是處理無向圖的最短路問寫LINGO程序。4無向圖的最短@for(roads(i,j):w(i,j)=@if(w(i,j)#eq#0,1000,w(i,j)));n=@size(cities);!城市的個數;@for(cities(i)|i#ne#1#andi#ne#!從頂點1離開后，再不能回到該頂點。復執行n1次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。這種算法的時間復雜度為O(n3)。第二種解決這一問題的方法是由FloydRW算法，稱之為Floyd算法。 a1n aA0

2n M an

annaii0aijaij

i1,2,L,n,wij是i,ji,j1,2,LnFloyd算法的基本思想是：遞推產生一個矩陣序列A0A1L,Ak,L,An，其中Ak(i,j)vivjk的最短路徑長ki,jk1,2,Ln。最后，當knAn即是各頂點之間的最短通路值。例12用Floyd算法求解例9。矩陣path用來存放每對頂點之間最短路徑上所經過的頂點的序號。Floyd程序如n=6;a=zeros(n);a(4,5)=10;a(4,6)=25;a(5,6)=55;a=a+a'M=max(max(a))*n^2M為充分大的正實數fork=1:nfori=1:nifa,我們使用LINGO9.0編寫的FLOYD th;!path標志最短路徑上走過的頂點;@format(w(i,j),'10.0f')),@newline(1)); 連通的無圈圖叫做樹，記之為T。若圖G滿足V(G)V(TE(T)E(G則稱T是G的生成樹。圖G連通的充分必要條件為G有生成樹。通圖的生成樹的個數很多，用(G)表示G的生成樹的個數，則有公式公式(Caylay)

)nn2公式(G(Ge(Ge其中Ge表示從G上刪除邊eGe表示把e的長度收縮為零得到的圖。定理 （i）G是樹當且僅當G中任二頂點之間有且僅有一條軌道G是樹當且僅當G無圈，且1G是樹當且僅當G連通，且1G是樹當且僅當G連通，且eE(GGeG是樹當且僅當GeE(GGen個城市的鐵路，已知ij城之間的鐵路造價為Cij，設計一個線prim算法構造最小生成樹P和Q,P用于存放G的最小生成樹中的頂點，集合Q存放的最小生成樹令集P的初值P{v1}（假設構造最小生成樹v1出發，集合Q的初值為Q。primpPvVP的邊中，選取具有最pv，將v加入P中，將pv加入集合Q中，如PV時，最小生成樹構造完畢，這時集合Q中包含了最小生成樹（i）P{v1}，Q（ii）whileP~pvpPvVPPQQ5最小生成樹問a=zeros(7);a(1,2)=50;a(2,4)=65; Kruskal算法構造最小生成樹科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法如下:(i)選e1E(G)w(e1min。若e1e2Lei已選好，則從E(G){e1e2Lei中選取ei1，使①G[{e1e2Leiei1中無②w(ei1min直到e1號中較大序號u改記為此邊的另一序號v，同時把后面邊中所有序號為u的改記為v。此方法的幾何意義是：將序號u的這個頂點收縮到v頂點，u頂點不復存在。后面繼續程序如下：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)<loopifindex(1,flag)~=index(2,flag) 定義ME(G，eiejMei與ej無公共端點（ij）MG中的一個對集；MM中相配；M中的端點稱為M許配；GM許配時，M稱為完美對集；G中已無使|M'||M稱此軌為M的交錯軌，交錯軌的起止頂點都未被許配時，此交錯軌稱為可增廣軌。MM內的邊從對集中刪除，則被許配的頂點數增加2，對集中的“對兒”增加一個。定理 M是圖G中的最大對集當且僅當G中無M可增廣軌定理 G為二分圖，X與Y是頂點集的劃分，G中存在把X中頂點皆許配SX，則|N(S||S|N(SS中頂點的鄰集。1：若G是k次（k0)2分圖，則G所謂k次正則圖，即每頂點皆k度的圖。定理 每個姑娘都結識k(k1)位小伙子，每個小伙子都結識k位姑娘，則每分派問題：x1x2L,xn去做ny1,y2L,yn，每人適合做其這個問題的數學模型是：G是二分圖，頂點集劃分為V(GXUYX{x1Lxn}，Y{y1L,yn}，當且僅當xi適合做工作yj時xiyjE(G解決這個問題可以利用1965年埃德門茲(Edmonds)匈牙利算法。從GM許配的一頂點uSu}TN(STyN(STyM許配的yzMSSU{zTTU{y}，轉（iii；P(u,yM(ME(PU(E(P)M，轉（ii。這個問題的數學模型是：在分派問題的模型中，圖G的每邊加了 定義若l:V(G)R，滿足xX,yYlxlywxy，則稱l是二分圖G的可行頂點標Elxy|xyE(Glxlywxy)}，El為邊集的G的生成子圖為相等子圖，記作Gl。l(x)maxw(l(y)

xXyY定理 Gl的完美對集即為G的權最大的完美對集Kuhn-Munkres算法選定初始可行頂點標號l，確定Gl，在GlMM許配的頂點uSu}，T。 若 （iv； (S)T lmin{l(x)l(y)w(xS,l(v)l(v)l,vT 其llGlGlG (S)T中一頂點y若y已被M許配且yzM則SSU{z}GliiiM(ME(P))U(E(P)M)（iilNG(S是GlSl 定義經過G的每條邊的跡叫做GEulerEulerEuler直觀地講，Euler圖就是從一頂點出發每邊恰通過一次能回到出發點的那種圖，即定理 （i）G是Euler圖的充分必要條件是G連通且每頂點皆偶次d（ii）G是Euler圖的充分必要條件是G連通且Gi

Ci是圈，E(CiIE(Cj(ijGEuler跡的充要條件是G定義包含GHamilton(哈密頓)Hamilton直觀地講，Hamilton圖就是從一頂點出發每頂點恰通過一次能回到出發點的那種Fleury1o.v0V(G，令W0v02o.假設跡WvevLevE{e,Le 01 i 邊ei1ei1和vi相關聯（ii）除非沒有別的邊可選擇，否則ei1不是GiG{e1Lei}的割邊(cutedge)。 設G是連通賦權圖。（i）求V0v|vV(Gd(v1(mod2)}對每對頂點uvV0，求d(uv)（d(uv是u與vFloyd算法構造完全賦權圖K|V0|，以V0為頂點集，以d(uv)為邊uv的權00M中邊的端點之間的在G在（vi）中得的圖GEuler回路即為中國郵遞員問題的解。kPP的數學模型如下：G(VEv0V(G，求G的回路C1L,Ck（i）v0V(Ci)，i1,2,L,kmaxw(e)mini1ikeE(CikUE(Ci)i旅行商（TSP）問Hamilton圈C，然后適當修改C以得到具有較小權的另一個Hamilton圈。修改的方法叫做改良圈算法。設初始圈Cv1v2Lvnv1。對于1i1jnHamilton圈Cijv1v2Lvivjvj1vj2Lvi1vj1vj2Lvnv1它是由C中刪去邊vivi1vjvj1，添加邊vivjvi1vj1而得到的。若w(vivj)w(vi1vj1w(vivi1w(vjvj1，則以Cij代替C，Cij叫做C的改iKruskal算法加以說明。假設C是G中的最優圈。則對于vCv是在GvHamilton軌，因而也是Gv的生成樹。由此推知：若TGv中的最優樹，同時e和f是和v關聯的兩條邊，并使得w(ew(fw(Tw(ew(fw(C的一個上界。間的航線距離如表7。7六城市間的距LMNTLMNTfunctionmainglobalaa(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<long%修改圈function[circle,long]=modifycircle(c1,L);globalawhileifc1(m+1:n)=c1(n:-fori=1:L-1設城市的個數為ndij是兩個城市ijxij01（1表示走過城市i到城市j的路，0表示沒有選擇走這條路。則有mindijin xij1i1,2,Ln每個點只有一條邊出去nxij1j1,2,Ln（每個點只有一條邊進去xij|s|1，2|s|n1，s{1,2,L,i,xij{0,1}i,j1,2,Lnij。其中|s|表示集合s中元素個數。例16已知SV地區各城鎮之間距離見表8，某公司計劃在SV地區做宣傳，從城市1出發，經過各個城鎮，再回到城市1。為節約開支，公司希望走過這10個城鎮的總距離最少。8城鎮之間的距 58678689解編寫LINGOCITY/1..10/:U;!U(I)=sequenceno.ofcity;LINK(CITY,CITY):DIST,!ThedistanceX;!X(I,J)=1ifweuselinkI, !Distancematrix,itneednotbesymmetric;DIST=0 !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));!Fortheandlaststopwe@FOR(CITY(K)|K#GT#U(K)<=N-1-(N-2)*X(1,U(K)>=1+(N-2)*X(K,1)); 定義在以VA為弧集的有向圖GVA（i）LAR為孤上的權函數，弧(i,jAL(i,jlij(i,j的容量下界（lowerbound；（ii）U:AR為弧上的權函數，弧(i,jA對應的權U(i,j記為uij(i,j)的容量上界，或直接稱為容量（capacity；（iii）DVR為頂點上的權函數，節點iVD(idi，稱為頂點i的供需量（supply／demand；NVAL,UD由于我們只V,A為有限集合的情況，所以對于弧上的權函數L,U和頂點上的權函數D，可以直接用所有孤上對應的權和頂點上的權組成的有限維向量表示，因此在流網絡中，弧(i,j)的容量下界lij和容量上界uij表示的物理意義分別是：通過點發送到網絡外部的“物質”數量（di0時。下面我們給出嚴格定義。定義NVAL,UD，其上的一個流（flow）fNAR的一個函數，即對每條弧(i,j)fij（稱為弧(i,j的流量果流ffijj:(i,j

fjidij:(j,i

lijfijuij (i,j)A flownetwork可見，當di0時，表示有di個單位的流量從網絡外部流入該頂點，因此頂點i稱（source時，表示有|di|個單位的流量從該頂點流失到網絡外部（或說被該頂點吸收點i稱為需求點（demandnode）或匯（sink，有時也形象地稱為終止點或收點等；當di0時，頂點i稱為轉運點（transshipmentnode）或平衡點、中間點等。此外，根據di

L0（即所有孤(i,jlij0），并將L0時的流網絡簡記為N(V,A,UD。此時，相應的容量約束（2）為0fijuij (i,jA定義NVA,UDffij (i,j)Af為零流，否則為非零流。如果某條弧(i,j)上的流量等于其容量（fijuij稱該弧為飽和弧（saturatedarc）；如果某條弧(ij上的流量小于其容量（fijuij，arc。而其它節點為轉運點。如果網絡中存在可行流f，此時稱流f的流量（或流值，flowvalue）為ds（根據（3），它自然也等于dt，通常記為v或v(f)，即vvfdsdt般記為Nst,VA,U)。最大流問題（umflowproblem）就是在N(s,t,V,A,U)中找到流值最大的可行流（即最大流。會看到，最大流問題maxs.t.fijf

ii j:(i,j j:(j,i is,0fijuij (i,j)A 定義A的任何子方陣的行列式的值都等于0，1或1A是全幺模的(totallyunimodularTU，又譯為全單位模的)，或稱A是全幺模矩陣。實際問題往往是多源多匯網絡，為了計算的規格化，可將多源多匯網絡G化成單源單匯網絡G'。設X是GY是G的匯，具體轉化方法如下：在原圖Gxy，令為新圖G中之單源和單匯，則G中所有頂點V成為G'之中間頂點集。 的弧把x連接到X中的每個頂點 的弧把Y中的每個頂點連接到yG和Gf是Gff'(a)ff

若a(x,v)若av所定義的函數fGvfvf的流，這里f(vv的流量，f(v表示流入v的流量（在G中G中的流在G的弧集上的限制就是G中Nst,VA,USVsStVS，則稱(SSSVS(SSSSC(S,S)為割(SS

(i,j)AiS,

定理 f是最大流，(S,S)是容量最小的割的充要條件vf)C(SSN(st,VA,U中，對于軌(sv2Lvn1t（此軌為無向的vivi1A，則稱它為前向弧；若vi1viA，則稱它為后向弧Ns到tP上，若對所有的前向弧(ijfijuij，對所有的后向弧(i,j)恒有fij0Ps到t的關于f的可增廣軌。令uijfij 當（i,j fij

當（i,j)且保持為正，也不影響其它弧的流量。總之，網絡中f可增廣軌的存在是有意義的，因為這意味著f不是最大流。標號法是由Ford和Fulkerson在1957年。用標號法尋求網絡中最大流的基給發點標號為(s,)①若(xyAfxyuxy時，令ymin{uxyfxy,xy標號為(xyxfyuxyy②yxAf

0，令

min{fyx,xy標號為(xy不斷地重復步驟（ii）直到收點t被標號，或不再有頂點可以標號為止。當t（Bs到t的可增廣軌，算法結束，令ut若u的標號為(vtfvufvut；若u的標號為(vtfuvfuvt若us，把全部標號去掉，并回到標號過程（A。否則，令uv，并回到增流過程（ii。(pred(j),可以增廣的最大流量maxf(j)。 1 若maxft0 jV的標號，即令maxfj)0))STEP3LIST且maxft0，繼續下一步；否則：（3a）如果t已經有標號（即maxf(t)0，則找到了一條增廣路，沿該增廣路對x進行增廣（增廣的流量為maxf(t)，增廣路可以根據pred回溯方便地得到STEP1。（3b）如果t沒有標號（LIST=且maxft0對非飽和前向弧(i,j)，若節點j沒有標號（即pred(j)0，對j進行標號，即令maxfjmin{maxf(i),uijxij}pred(j)i，并將j加入LIST中。)maxf(j)min{maxf(i),xij}，pred(j)i例17 用Ford-Fulkerson算法計算如圖6網絡中的最大流每條弧上的兩個數字分6最大流問解編寫程序如下：whilemaxf(n)>0while(~isempty(list))&(maxf(n)==0)ifwhilev2~=1if例18s的石油通過管道運送到城市t，中間有4個中轉站v1v2和v4，城市與中轉站的連接以及管道的容量如圖7所示，求從城市s到城市t的最圖7最大流問arcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,f;c=87952596n=@size(nodes)頂點的個數;@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)頂點的個數;@for(nodes(i)|i#ne#1#and#i#ne#n:的費用問題，在許多實際問題中，費用的因素很重要。例如，在問題中，人們總是希望在完成任務的同時，尋求一個使總的費用最小的方案。這就是下面要在網絡N(s,t,V,A,U)中，設cij是定義在A上的非負函數，它表示通過弧(i,j)單位流的費用。所謂最小費用流問題就是從發點到收點怎樣以最小費用輸送一已知量為v(f)的總流量。mincij(i,j fijj:(i,j

fjidij:(j0fijuij (i,j)Av(f i其中divf),i is,顯然，如果vf最大流vfmaxvfvfmax（8最小費用最大流問arcs(nodes,nodes)/s1,s3,12,13,23,2t,34,42,4t/:c,u,f;d=14000014;!最大流為c=28251634u=87952596d=140000-14;c=0;u=0;在1961年。其主要步驟如下求出從發點到收點的最小費用通路(s,t)對該通路(s,t)f min(i,j)(s,t并讓通的所有邊的容量相應減少f。這時，對于通的飽和邊，其單位流費用相應改為。(s,t上所有邊(i,j的反向邊(j,iujif，cji部流量等于v(f)為止（或者再也找不到從s到t的最小費用道路。求最短路的函數floydpath。globalMnumglobalMnumfork=1:numfori=1:numforif

ifw(1,num)==M

while~isempty(m)if

%最小費用最大流函數function%第一個參數：容量矩陣；第二個參數：費%前兩個參數必須在不通%第三個參數：指定容量值（可以不寫，表示求最小費用最大流%返回值flow為可行流矩陣,val為最小費用值globalMifnargin<3whileallflow<flowvaluepath=floydpath(w);%調用floydpath函數ifisempty(path) ,（criticalpathmethodCPM）是網絡分析的重要組成部分，它廣泛地用于系統分析和項杜邦公司為了協調企業不同業務部門的系統規劃，提出了關鍵路。1958年，PERTCPM既有著相同的目標應用，又有很多相同的術語，這兩種方法已合并為法，在國外稱為PERT/CPM，在國內稱為統籌方法（schedulingmethod。例20 某項目工程由11項作業組成（分別用代號A,B,L,J,K表示其計劃完成時間及作業間相互關系如表9所示，求完成該項目的最短時間。9作業流程數A5—B,B,B,EF,GB—C—D4BE4AFC,示事件，A,B表示作業。由這種方法畫出的網絡圖稱為計劃網絡圖。9計劃網絡圖的基本畫事件j的最早時間用tE(j)表示，它表明以它為始點的各工作最早可能開始的時設事件為1,2,L,n，tE(1)t(j)max{t(i)t(i, t 其中tE(ijt(ij是作業(i,j所需的工時。tE(n)總最早完工 事件i的最遲時間用tL(i)表示，它表明在不影響任務總工期條件下，以它為始點tL(n)總工期（或tEt(i)min{t(j)t(i, 其中tLj是與事件i一個工作(i,j的最早可能開工時間用tES(i,j有緊前工作全部完工后才能開始。工作(ij的最早可能完工時間用tEF(ij表示。它

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

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

1020的計劃xnx1。設tij是作業(i,j的計劃時間，因此，對于事件i與事件j有不等式xjximinxn xjxitij，(i,j)A，i,jVxi0，iV用LINGO求解例20。解編寫LINGOoperate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 10天；等等。每個作業只要按規定的時間開工，整個項目的最短工期為51天。sijsijxjxitij，(i,jA，這樣就可以得到作業的最遲yi表示事件i的最遲開工時間。當最早開工時間與最遲開工時間相同時，operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=5 34 c=07004004500006003005000500400;sijsij0時，說明還有剩余時間，對sijs781，作業（7，8）（J）的開工時間可以推遲1，6（（1，4（（4，6（所以，作業（1，4（C）5天。1210作業數作業(i,作業(i,5HI4J4KF11帶有關鍵路線的計劃網絡n

tij(i,jn

i xijxji i(i,j

(j

xij01(i,j例 operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 d=1000000-23（關鍵路線與計劃網絡的優化）20中所列的工程要求在49天內完成。20中可縮短工期的所有作業和縮短一天工期額外增加的費用。現在的問題11工程作業數作 計劃完(i,j)時間（天最短完作 (i,j)最短完8H8I43JKxi是事件itij是作業(ijmij是完成作業(ij的最yij是作業(ijcij是作業(i,j縮短一天增加的費用，因此xjxitijyij且0yijtij總目標是使額外增加的費用最小，即目標函數為mincij(i,j xjxiyijtij，(i,j)A，i,jVxnx1d0yijtijmij，(i,j)A，i,j

(i,joperate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=58834 c=07004004500006003005000500400;作業(1,3)(B）壓縮1天的工期，作業(6,8)(K)1天工期，這樣可以在49例24（續例23）用LINGO求解例23，并求出相應的關鍵路徑、各作業的xizi表示事件寫出相應的LINGO程序如下：operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,7t=5101144 m=58834 c=07004004500006003005000500400;12作業數作業(i,作業(i,59HI4J4KF12優化后的關鍵路線估計值：最樂觀值的估計值（a，最悲觀的估計值（b）和最可能的估計值（m設tij是完成作業(i,j)的實際時間（是一隨量通常用下面的方法計算相應

)aij4mij6(bijaij)

var(tij)

設TT (i,j)TE(T) E(tij (i,j)S2var(T) (ij)關鍵路

var(tij dTP{Td} 1@psn(x)是LINGO提供的標準正態分布函數，1

x@psn(x)(x)x

et2/2 25205213作業數(i,(i,ambamb35789H8I246J345KF8operate(events,events)/12,13,14,25,34,35,46,557,58,67,68,78/:a,m,b,et,dt,x;a=388208;m=59d=100404000-3252025 后可以生產這種主管道的鋼廠有S1,S2,LS7。圖中粗線表示鐵路，單細線表示公表示火車站，每段鐵路、公路和管道旁的數字表示里程(單位km)。一個鋼廠如果承擔制造這種，至少需要生產500個單位。鋼廠Si在指定期限1單位的鐵路運價見表15。i1234567 里程里程請制定一個主管道的訂購和計劃，使總費用最小（給出總費用)絡，請就這種更一般的情形給出一種解決辦法，并對圖15按（1）的要求給出模型和結果。

記第i個鋼廠的最大供應量為si，從第i個鋼廠到鋪設節點j的訂購和費用為cij；用lj表示管道第j段需要鋪設的量。xij是從鋼廠i運到節點j的量，yj是從節點j向左鋪設的量，zj是從節點j向右鋪設的量。SiAj的最小購運費cij中），費用（Si經鐵路、公路至各點Aji1,2,L,7,j1,2,L,15AjAj1j1,2,L,14)的運費。用cij的計算構造鐵路距離賦權圖G1(VE1W1,其

（j1,2,L,15）V{S,L,S,A,L,A,B,L,B}，各頂點的見圖14；W(w1 ij,11

i,j

（d1表示i，j兩點之間的鐵路路的最小費用c1。其中，路徑值無窮大時的費用也為無窮大。②計算公路任意兩點間的最小構造公路距離賦權圖G2VE2,W2,其中V同上，W2(w2

3939d2ijw2 (d2表示i，j兩點之間的公i,j計算，計算出公路任意兩點間的最小費用 費

ij。路徑值為無窮大時的費 構造鐵路公路的混合賦權完全圖G(V,E,W)，W(c~ ，其~minc1c2 16最小運費計算結

ij（j1,2,L,152任意兩點間的最 費用加上出廠售價,得到單位從任一個（i1,2,L,7）到Aj（j1,2,L,15） 和運送最小費用cij運量約束：xij對izjyj；yj1zjAjAj1段的長度lj由Aj向AjAj1段鋪設管道的總路程為1Ly由Aj向AjAj1段鋪設管道的總路程為1Lz

yj(yj1)/2zj(zj1)27min7

0.1152

j(z

1)

yj(y

s.t.xij0U[500,si

i 7xijzjyj7yj1zjlxij0,zj0,yjy10,z15Lingo

jji1,2,L7,j

使用計算機求解上述數學規劃時需要對約束條（20）進行處理我們引進

500fi xijsifi，i!nodes表示節點集合

!c1(i,j)表示節點i到j鐵路的最小運價（萬元）,c2(i,j)表示節點i到j公路的費用鄰接矩陣，c(i,j)表示節點ij的最小運價，path標志最短路徑上走過的頂點;link(nodes,nodes):w,c1,c2,c,path1,path;need/A1..A15/:b,y,zy表示每一點往左鋪的量，z表示往右鋪的量;linkf(supply,need):cf,X;S=8008001000200020002000P=160155 path1=0;path=0;w=0; 以下是格式化輸出計算的中間結果和最終結果@text(MiddleCost.txt)=@writefor(supply(i):@writefor(need(j):@format(cf(i,j),'6.1f')),@newline(1));@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)#eq#0,20000,w(i,j))); !無鐵路連接，元素為充分!以下就是最短路計算公式（Floyd-Warshall算法）;@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:C1=60); !輸入公路距離鄰接矩陣的下三角元素));!@for(link(i,j)|i#ne#j:c2(i,j)=@if(c2(i,j)#eq#0,10000,c2(i,j))); @for(link:C=@if(C1#le#C2,C1,C2)); C1C2矩陣對應元素取最小;@for(link(i,j)|ile7and#j#ge#8and#j#le22:cf(i,j-7)=c(i,j提取下面二次規劃模型需要的7×15矩陣;!約束@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(j));y(1)=0;z(15)=0;@for(need:@gin(y));7 mincijxij

(y2y

i1 j1