第6章 網(wǎng)絡(luò)優(yōu)化(2009.08)

管理運(yùn)籌學(xué)汪賢裕

2009.081第6章網(wǎng)絡(luò)優(yōu)化§6.0基本概念§6.1歐拉回路和中國(guó)郵路問題§6.2最小樹問題§6.3最短路問題§6.4網(wǎng)絡(luò)上的最大流問題和最小割集§6.5最小費(fèi)用流§6.6運(yùn)輸問題2§6.0基本概念圖論（GraphTheory）是運(yùn)籌學(xué)的一個(gè)重要分支。圖

記為：G=（V,E）V=｛v1,，v2,，…vn,

｝——頂點(diǎn)集。表示系統(tǒng)中的元素。E=｛e1,，e2,，…,em

｝——邊集。表示系統(tǒng)中元素之間的關(guān)系。（1）無向邊——元素之間的一般關(guān)系；（2）有向邊——元素之間的因果關(guān)系。圖是研究離散系統(tǒng)中元素之間關(guān)系及對(duì)系統(tǒng)的影響。3一、圖的基本概念定義1一個(gè)圖是一個(gè)三元組，記為。其中V={vi}為有限非空集合，稱頂點(diǎn)集，其元素稱頂點(diǎn)

E={ej}為有限集合，稱為邊集，其元素稱為邊；

Ψ為EV×V的映射，即E中一個(gè)元素對(duì)應(yīng)V中兩個(gè)元素。例：右圖中V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5,e6}Ψ(e1)=v1v1,Ψ(e2)=v1v2,Ψ(e3)=v1v3,Ψ(e4)=v3v4,Ψ(e5)=v3v4,Ψ(e6)=v1v4。V1

○V2

○V5○○

v3○v4e2e1e4e6e3e54○二、無向圖與有向圖v1○V2○○v3a1a2a3a4○○○5三、圖的矩陣表示1、無向圖（1）、關(guān)聯(lián)矩陣（2）、鄰接矩陣（3）、權(quán)矩陣（簡(jiǎn)單圖）

wi,j為頂點(diǎn)vi和vj之間邊的權(quán)重。2、有向圖（略）6四、網(wǎng)絡(luò)對(duì)圖上的邊（or/and）頂點(diǎn)，賦以有實(shí)際意義的權(quán)重，則稱為網(wǎng)絡(luò)。網(wǎng)絡(luò)一般記為：N=（V,E,W）例1七橋問題例2運(yùn)輸網(wǎng)絡(luò)例3項(xiàng)目計(jì)劃例4電網(wǎng)絡(luò)例5生產(chǎn)安排……7例6.1七橋問題AB圖6.1aCD8圖6.1bACDB9§6.1歐拉回路和中國(guó)郵路問題。

（一筆畫問題）

1.鏈、簡(jiǎn)單鏈、初等鏈（路）鏈：圖G=(V,E)中，一個(gè)點(diǎn)與邊交替序列｛vi0ei1vi1ei2vi2……vik-1eikvik

｝且

eit=vit-1vit(t=1,2,…,k）,稱為一條連接vi0

和vik

的鏈，鏈長(zhǎng)為k。簡(jiǎn)單鏈（跡），鏈中只有重復(fù)的點(diǎn)而無重復(fù)的邊，稱為簡(jiǎn)單鏈。初等鏈（路），簡(jiǎn)單鏈中無重復(fù)的點(diǎn)，稱為初等鏈。若vi0=vik則稱鏈為閉鏈（或圈），否則稱開鏈。

102、定義：歐拉跡、歐拉回路、歐拉圖G是一個(gè)連通圖，若G中存在一條鏈，過每邊一次且僅一次，稱此鏈為歐拉跡。若G中存在一個(gè)圈，過每邊一次且僅一次，稱此圈為歐拉回路（歐拉圈）。若G具有歐拉回路，則稱G為歐拉圖。113、歐拉圖的判定定理6.1：無向連道圖G是歐拉圖，當(dāng)且僅當(dāng)中無奇點(diǎn)。推論：無向連道圖G有歐拉道路，當(dāng)且僅當(dāng)G中恰有兩個(gè)奇點(diǎn)。定理6.2：連通有向圖D是歐拉圖，當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的出次等于入次。12

4、尋找一條歐拉回路方法任意點(diǎn)出發(fā)，逐步構(gòu)造簡(jiǎn)單鍵，除非不得以不選擇“割邊”。13注：上面所說的方法在《圖論》稱為一種算法?！秷D論》中的算法分為好算法和壞算法。好算法是指計(jì)算的次數(shù)為頂點(diǎn)個(gè)數(shù)和邊的條組可用一個(gè)多項(xiàng)式來表示，否則稱為一個(gè)壞算法，又稱為NP問題。不要認(rèn)為只要有有限個(gè)點(diǎn)和有限條邊，就一定可以用窮舉法計(jì)算。設(shè)算法中一次加法或一次乘法表示一次算法運(yùn)算，若算法是n!次。(例如有n+1個(gè)頂點(diǎn)的完全圖中，一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的路有n!條不同的路。)

當(dāng)n=20時(shí),n!=20!=2.4329×1018.

若一臺(tái)計(jì)算機(jī)每秒中運(yùn)行10億次，即109次，則運(yùn)算時(shí)間為：14

5、中國(guó)郵路問題實(shí)際問題：郵遞員從郵局出發(fā)，走遍所有街道送信，再返回到出局。問如何安排送信線路，使所走的路最少？圖論問題：給定一個(gè)連道圖G，每邊有非負(fù)權(quán)，要找一個(gè)圈經(jīng)過每一條邊，且滿足圈的總權(quán)最小。

思路：對(duì)圖上加上一些邊,構(gòu)成，使得：（1）G’是一個(gè)歐拉圖，（2）E’的權(quán)和最小。管梅谷教授的方法：（1）每條邊最多重復(fù)一次。（2）G的每個(gè)初等圈中，重復(fù)邊的權(quán)和不超過圈權(quán)和的一半。（Edmods算法：《網(wǎng)絡(luò)算法與復(fù)雜性理論》，謝政、李建平，國(guó)防科技大學(xué)出版社）。15一、樹及其性質(zhì)。1.定義：連通且不含圈的無向圖稱為樹。一個(gè)無圈的圖稱為森林。森林的每一個(gè)分圖是樹。2.定理6.3：圖則下列命題等價(jià)。（1）T是一個(gè)樹。（2）T無圈，且m=n-1.（3）T連通，且m=n-1.（4）T無圈，但每加一新邊，即得唯一圈。（5）T連通，但每舍去一邊就不連通。（6）T中任意兩點(diǎn)有唯一初等鏈相連?！?.2最小樹問題16二、圖的生成樹1、定義：若圖G的生成子圖是一棵樹，則該樹稱為G的生成樹。

圖的生成樹是不唯一的。2、定理6.4：圖G有生成樹的充分必要件為G是連通圖。3、尋找生成樹方法：（1）生成法（避圈法）。（2）破圈法。17三、最小樹問題1、定義：連通圖G=(V,E),每條邊上有非負(fù)權(quán)w(e)>0。一棵生成樹所有樹枝上的權(quán)和，稱為這棵生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹（簡(jiǎn)稱最小樹）。2、算法（1）Kruskal算法（生成法、避圈法）①將各條邊按權(quán)增排序。

②

從最小權(quán)的邊開始依次向后選：每次選的邊與前面已選過的邊集不構(gòu)成圈。③選到n-1條邊停?？梢宰C明：Kruskal算法是一個(gè)好算法。18（2）破圈法①將各邊按權(quán)遞減排序。②從最大權(quán)的邊開始依次向后選：每次選的邊包含在某個(gè)圈中，該邊舍去，否則保留。③保留n-1條邊停。

例：219四、求最小生成樹的計(jì)算機(jī)軟件用WinQSB中的NET程序（NetworkModeling）

——MinimalSpanningTree20一、最短路問題的基本概念

1.鏈、簡(jiǎn)單鏈、初等鏈（路）鏈：圖G=(V,E)中，一個(gè)點(diǎn)與邊交替序列｛vi0ei1vi1ei2vi2……vik-1eikvik｝且

eit=vit-1vit(t=1,2,…,k）,稱為一條連接

vi0

和vik

的鏈，鏈長(zhǎng)為k。簡(jiǎn)單鏈（跡），鏈中只有重復(fù)的點(diǎn)而無重復(fù)的邊，稱為簡(jiǎn)單鏈。初等鏈（路），簡(jiǎn)單鏈中無重復(fù)的點(diǎn)，稱為初等鏈。

§6.3最短路問題21

2.路長(zhǎng)和最短路（1）.設(shè)G=（V,E）是連通圖，圖中各邊（vi,vj）有權(quán)wi,j=w（vi,vj

），設(shè)vs和vt是G中任意兩點(diǎn)，P是一條從vs到vt的路，則P的路長(zhǎng)定義為：（2）.求一設(shè)條路P*，使它是從vs到vt的所有路中總權(quán)和最小的路。則稱為從vs到vt的最短路。

w（P*）=Min｛w（P）｝22二、最短路的計(jì)算

1.線性規(guī)劃方法求v1到vm的最短路，等價(jià)于下面線性規(guī)劃：232.Dijkstra算法，（雙標(biāo)號(hào)法）前提：是連通圖，且每一條邊上的權(quán)為正數(shù)。作用：可求中對(duì)給定一點(diǎn)給到任意其它點(diǎn)的最短路。雙標(biāo)號(hào)意義：P(v)—永久標(biāo)號(hào)。T(v)—臨時(shí)標(biāo)號(hào)。算法中vi到vj的路長(zhǎng)記為li,j

，即前述的邊的權(quán)重wi,j

。若vi到vi無邊，則記li,j為無窮大。24算法步驟：（1）、給vs標(biāo)號(hào),其點(diǎn)。（2）、若vi點(diǎn)為剛得到P標(biāo)號(hào)的點(diǎn)，考慮與vi相鄰的點(diǎn)vj，且vj是T標(biāo)號(hào)。修正T(vj)標(biāo)號(hào)。（3）、比較所有T標(biāo)號(hào)點(diǎn)，取最小者點(diǎn)改成為P標(biāo)號(hào)，（相同則任取1個(gè)）。若全部點(diǎn)都為P標(biāo)號(hào)則停止。否則用vr代vi回(2)（該算法可適用有向圖）25三、求最短路的計(jì)算機(jī)軟件

1.用LINDO軟件計(jì)算上述線性規(guī)劃問題；

2.用WinQSB中的NET程序（NetworkModeling）

——ShortestPathProblem26例6.1：設(shè)備更新問題某企業(yè)使用一臺(tái)設(shè)備。每年年初，企業(yè)都要作出決定，是繼續(xù)使用舊的，付維修費(fèi)，或是購(gòu)買新的，付購(gòu)買費(fèi)。試制定一個(gè)5年的更新計(jì)劃，使總支出最少。購(gòu)買費(fèi)和維修費(fèi)計(jì)算表27圖論問題1、構(gòu)造一個(gè)有向圖G=(V,E)。

頂點(diǎn)vi表示第I年初時(shí)點(diǎn)(I=1,2,3,4,5,6),用v6表示第5年底。邊vi

vj

表示第i年初購(gòu)進(jìn)設(shè)備，一直用到第j年初（第j-1年底）。邊vi

vj

上的權(quán)表示，第i年初購(gòu)進(jìn)設(shè)備費(fèi)和一直使用到第j年初的全部費(fèi)用。（v1到v6的每一條路都是一個(gè)可行方案）。2228圖的中心例2：已知一個(gè)地區(qū)的交通網(wǎng)絡(luò)圖如下，其中點(diǎn)代表居民小區(qū)，邊代表公路，邊旁數(shù)為權(quán)代表公路的長(zhǎng)度。問該地區(qū)中心醫(yī)院應(yīng)建在那一個(gè)小區(qū)，可使醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路最近。20303029下面表中前7列組成最短路矩陣（對(duì)稱矩陣）各小區(qū)間最短路長(zhǎng)，和該區(qū)設(shè)衛(wèi)生院的最遠(yuǎn)路長(zhǎng)d（vi)。結(jié)論：醫(yī)院建在v6小區(qū)。30圖的重心例6.2若七個(gè)村鎮(zhèn)相互到達(dá)的距離矩陣以及各村鎮(zhèn)有居民人數(shù)如下表：（1）求7個(gè)村鎮(zhèn)的中心；（2）求7個(gè)村鎮(zhèn)的重心。距離di,j村鎮(zhèn)人數(shù)wiSABCDETS0245871340A2023651125B420143945C5310541030D864501520E753410635T13119105605031（1）7個(gè)村鎮(zhèn)的中心則7個(gè)村鎮(zhèn)的中心為E。距離di,j最大距離di,jSABCDETS0245871313A2023651111B42014399C5310541010D86450158E75341067（Min）T13119105601332（2）7個(gè)村鎮(zhèn)的重心則7個(gè)村鎮(zhèn)的重心為B。widi,j村鎮(zhèn)人數(shù)wiSABCDETS08016020032028052040A500507515012527525B1809004518013540545C1509030015012030030D1601208010002010020E24517510514035021035T65055045050025030005014351105875(Min)10601085980181033§6.4網(wǎng)絡(luò)上的最大流問題和最小割集一、一些基本概念v3v2v1v4vs（5,2）（4,3）（2,2）（7,5）（5,3）（3,3）（7,6）（4,1）（1,1）（2,2）圖

網(wǎng)絡(luò)及網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）每一個(gè)弧上的容量ci,j和流量fij例如:fs1=5,fs2=3,f13=2等等就是運(yùn)輸量vt341.運(yùn)輸網(wǎng)絡(luò)（容量網(wǎng)絡(luò)）N(V,A,C)定義

設(shè)一個(gè)賦權(quán)有向圖N=（V,A）,滿足：（1）僅有一個(gè)頂點(diǎn)vs,其入度為0。稱vs為發(fā)點(diǎn)（源）；僅有一個(gè)頂點(diǎn)vt,其出度為0。稱vt為收點(diǎn)（匯）。其他的點(diǎn)叫做中間點(diǎn)。（2）每一個(gè)?。╲i,vj）∈A上有一個(gè)非負(fù)正數(shù)cij

叫做弧的容量。我們把這樣的圖N，稱為容量網(wǎng)絡(luò)(簡(jiǎn)稱網(wǎng)絡(luò))，記做N=（V，A，C）。這里：C=｛cij｝352.網(wǎng)絡(luò)上的流（1）網(wǎng)絡(luò)N上的流，是指定義在弧集合A上的一個(gè)函數(shù)f={f(vi,vj)}={fij}。f(vi,vj)=fij叫做弧在(vi,vj)上的流量。（2）網(wǎng)絡(luò)上的一個(gè)流f叫做可行流，如果f滿足以下條件:

（A）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈A,有：0

fij

cij.

（B）平衡條件：對(duì)于中間點(diǎn)vi

，有：

∑fij=∑fji36（3）可行流的流量（流值）

val(f)=v(f)=∑fsj=∑fjt

即發(fā)點(diǎn)的總流量（或收點(diǎn)的總流量），叫做這個(gè)可行流的流量（流值）。若f=0則稱該流f為零流。因此可行流一定存在。（4）最大流給定一個(gè)容量網(wǎng)絡(luò)N(V,A,C)，流量最大的流稱為最大流f*。373.網(wǎng)絡(luò)上的最小割集（1）割集給定一個(gè)容量網(wǎng)絡(luò)D=（V，A，C）。設(shè)有S

V，滿足：發(fā)點(diǎn)vs∈S，收點(diǎn)vt∈,那么將弧集叫做是分離vs和vt的截集。這里。（2）割容量

c（3）最小割給定一個(gè)容量網(wǎng)絡(luò)D=（V，A，C）。割容量最小的割集稱為最小割。38

二.網(wǎng)絡(luò)中流與割集的關(guān)系

1.基本理論定理6.5

給定一個(gè)容量網(wǎng)絡(luò)D=（V，A，C）,f是D的任意可行流，是D的任意割集。有：

命題

若D有f-增廣路，則f不是D的最大流。

定理6.6

給定一個(gè)容量網(wǎng)絡(luò)D=（V，A，C），f*

是D的最大流，

是D的最小割，39相關(guān)說明給定一個(gè)容量網(wǎng)絡(luò)D=(V，A，C),f是D的任意可行流。*f在弧（vi,vj）上的飽合與不飽合若fi,j=ci,j，稱f在弧（vi,vj）上是飽合的；若fi,j<ci,j，稱f在?。╲i,vj）上是不飽合的。*設(shè)

μ是一條從vi到vj的路（鏈），若?。╲i,vj）∈μ

,?。╲i,vj）與μ

的方向一致，稱（vi,vj）為前向弧。前向弧的全體記為μ

+；

若弧（vi,vj）∈μ

,孤（vi,vj）與μ的方向相反，稱（vi,vj）為反向弧。反向弧的全體記為μ

－。40相關(guān)說明（續(xù)）※設(shè)

μ

是一條從vs到vt的路（鏈），若：稱Ω為一條f-增廣路

vsv1v2v3vt

(4,2)(2,1)(5,4)(4,1)(7,2)

圖6.30弧旁的數(shù)字為(ci,j

,fi,j,)41定理6.7

若D有f-增廣路，則f不是D的最大流。

證明：若G中有μ為一條f-增廣路。令：取現(xiàn)把f修訂為f’：

其它顯然，f’仍然是一可行流。但有：v(f’)=v(f)+

所以，f不是最大流。42

三、最大流的計(jì)算上面命題的證明是一個(gè)構(gòu)造性的證明。它放啟示了找最大流的計(jì)算方法：給定一個(gè)可行流f(i)(初始時(shí)：i=0)第一步是在網(wǎng)絡(luò)D中去尋找f(i)-增廣路。若不存在f(i)-增廣路，則f(i)就是網(wǎng)絡(luò)D的最大流；若找到f(i)-增廣路，則轉(zhuǎn)入第二步。第二步是按時(shí)命題中規(guī)定，將可行流f(i)修改為f(i+1)

，顯然f(i+1)的流量比f(i)的流量更大。然后又回到第一步。43

求最大流的標(biāo)號(hào)算法從網(wǎng)絡(luò)D中的一個(gè)可行流f出發(fā)（如果D中沒有f，可以令f是零流）第一階段標(biāo)號(hào)過程在標(biāo)號(hào)過程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)（分為已檢查和未檢查兩種）?；蛘呤俏礃?biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來確定增廣鏈上的調(diào)整量

。44

求最大流的標(biāo)號(hào)算法（續(xù)）（1）先給vs標(biāo)號(hào)（0，+∞）。（2）選擇一個(gè)已標(biāo)號(hào)點(diǎn)x,對(duì)所有未標(biāo)號(hào)的x的鄰接點(diǎn)y按下面規(guī)則處理：如果在?。▁,y）∈E,且fx,y<cx,y

那么給y標(biāo)號(hào)（+x,

y）.其中

y=min｛

x,fx,y－cx,y

｝.這時(shí)，y成為已標(biāo)號(hào)的點(diǎn)。b）如果在?。▂,x）∈E，fij>0,那么給y標(biāo)號(hào)（-x,

y）.

其中

y=min｛

x,fy,x

｝.這時(shí)，y成為已標(biāo)號(hào)的點(diǎn)。c)對(duì)不滿足a)和b)的x的相鄰接的點(diǎn)，則不給以標(biāo)號(hào)。（3）重復(fù)進(jìn)行（2），直到vt被標(biāo)號(hào)或不再有頂點(diǎn)可以標(biāo)號(hào)為止。a)若vt得到標(biāo)號(hào)，則可由標(biāo)號(hào)中的第一個(gè)逆向找出一條f-增廣路，并轉(zhuǎn)入第二階段；b)若vt未得到標(biāo)號(hào),且標(biāo)號(hào)過程已無法進(jìn)行,則f是最大流,計(jì)算結(jié)束。45求最大流的標(biāo)號(hào)算法（續(xù)）第二階段調(diào)整過程首先按照vt和其他的點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈μ

。例如，令vt的第一個(gè)標(biāo)號(hào)是+vk，則?。╲k,vt）在μ上。再看vk的第一個(gè)標(biāo)號(hào)，若是-vi，則弧(vk,vj)都在μ上。依次類推，直到vs為止。這時(shí)，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈μ

。

取調(diào)整量

=

vt

,即vt的第二個(gè)標(biāo)號(hào)，按命題中的公式對(duì)可行流進(jìn)行修改。46求最大流的標(biāo)號(hào)算法（續(xù)）（1）決定調(diào)解量

=

vt令u=v；（2）若u的標(biāo)號(hào)為（+v,

u),,則以fv,u+

代替fv,u。即(v

,u)∈μ+

若u的標(biāo)號(hào)為（-v,

u),,則以fu,v-

代替fu,v。即(u,v)∈μ-（3）令v代替u，返回到（2）；若v=v，則去掉所有的標(biāo)號(hào)，返回到第一階段,重新進(jìn)行標(biāo)號(hào)過程。47求最大流的標(biāo)號(hào)算法（續(xù)）例：V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)分別表示容量和流量Vt48四.最小割集計(jì)算給定一個(gè)容量網(wǎng)絡(luò)D=（V，A，C）,f是按上述算法得到的最大流。令S*為在計(jì)算的最后情況下所有得到標(biāo)號(hào)的頂點(diǎn)，而為所有未得到標(biāo)號(hào)的頂點(diǎn)。則(S*,)就是網(wǎng)絡(luò)的最小割。49五.求最大流f的線性規(guī)劃計(jì)算法50六、求最大流的計(jì)算機(jī)軟件

1.用LINDO軟件計(jì)算上述線性規(guī)劃問題；

2.用WinQSB中的NET程序（NetworkModeling）

——MaximalFlowProblem51七、非標(biāo)準(zhǔn)的運(yùn)輸網(wǎng)絡(luò)1.多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)；2.中間點(diǎn)賦有權(quán)；3.充許雙向通行；4.容量約束有上、下限；……52

§6.5最小費(fèi)用流一、網(wǎng)絡(luò)特征

1.G=(V,A)是一個(gè)有向圖，

2.每條邊(vi,vj)上有兩個(gè)權(quán)重：（1）ci,j表示該邊上單位時(shí)間的運(yùn)輸容量上限，（2）wi,j表示該邊上單位運(yùn)輸?shù)馁M(fèi)用，

3.每個(gè)頂點(diǎn)賦予權(quán)重bi

，表示該頂點(diǎn)vi的供給量(bi>0)，需求量(bi<0),純中轉(zhuǎn)點(diǎn)(bi=0)。53

二、最小費(fèi)用流問題

求滿足該網(wǎng)絡(luò)各頂點(diǎn)供需要求的單位時(shí)間的運(yùn)輸量f=｛fi，j｝計(jì)劃，且整個(gè)運(yùn)輸費(fèi)用最小。三、求解最小費(fèi)用流問題1.用圖論中求最短路和最大流的方法相結(jié)合。2.求解最小費(fèi)用流問題等價(jià)下面線性規(guī)劃問題。54四、最小費(fèi)用流的計(jì)算用LINDO軟件求解上面線性規(guī)劃。55§6.6運(yùn)輸問題一、網(wǎng)絡(luò)背景1.圖G=（V,E）；2.頂點(diǎn)集按足標(biāo)分為三部分：S,T,H.(1)有p個(gè)發(fā)點(diǎn)：S=｛1,2,…,p｝(2)有q個(gè)收點(diǎn)：T={n－q＋1,n－q＋2,…,n｝(3)有n－p－q個(gè)中間轉(zhuǎn)運(yùn)點(diǎn)：H=｛p＋1,p＋2,…,n－q｝顯然:|V|=|S|＋|T|＋|H|=p＋q＋(n－p－q)=n3.每條邊上有一個(gè)權(quán)重wi,j，wi,j表示該邊單位貨物的運(yùn)費(fèi)；各邊上的運(yùn)輸量無上限。56二、一般運(yùn)輸問題1.每個(gè)發(fā)點(diǎn)vi有供給量ai，>0，每個(gè)收點(diǎn)vi有需求量bi>0每個(gè)中間轉(zhuǎn)運(yùn)點(diǎn)vi供給和需求量都為零。2.每個(gè)發(fā)點(diǎn)和每個(gè)收點(diǎn)都可以作為中間轉(zhuǎn)運(yùn)點(diǎn)。3.求一個(gè)網(wǎng)絡(luò)上一的流f=｛fi,j｝，滿足供給和需求雙方要求，且總運(yùn)輸費(fèi)用最小。三、運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題可根據(jù)不同的背景和條件，等價(jià)于下面線性規(guī)劃模型。571.供需平衡情況，即：582.供給大于需求情況，即：593.供給小于需求的情況，即：60四、一般運(yùn)輸問題的計(jì)算1.用LINDO軟件求解上面線性規(guī)劃；2用WinQSB軟件中NET程序（NetworkModeling）——TransportationProblem

但該程序只能解中間轉(zhuǎn)運(yùn)點(diǎn)

|H|=n－p－q