運籌學-圖與網(wǎng)絡模型以及最小費用最大流ppt課件

.,Chapter11圖與網(wǎng)絡分析(GraphTheoryandNetworkAnalysis),圖與網(wǎng)絡的基本概念與模型最短路問題最小生成樹問題最大流問題最小費用最大流問題,本章主要內容：,.,圖與網(wǎng)絡的基本概念與模型,長,江,漢,江,武昌,漢口,漢陽,您能從武漢理工大學出發(fā)走過每座橋且只走一次然后回到學校嗎?,.,近代圖論的歷史可追溯到18世紀的七橋問題穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。,圖與網(wǎng)絡的基本概念與模型,Knigsberg橋對應的圖,.,圖與網(wǎng)絡的基本概念與模型,圖論中圖是由點和邊構成，可以反映一些對象之間的關系。一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的。,圖的定義(P230)若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為點和邊的集合，記作：,其中:V點集E邊集,圖G區(qū)別于幾何學中的圖。這里只關心圖中有多少個點以及哪些點之間有連線。,.,圖與網(wǎng)絡的基本概念與模型,可見圖論中的圖與幾何圖、工程圖是不一樣的。,例如：在一個人群中，對相互認識這個關系我們可以用圖來表示。,.,6,1圖與網(wǎng)絡的基本概念,如果我們把上面例子中的“相互認識”關系改為“認識”的關系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個反映這七人“認識”關系的圖。相互認識用兩條反向的弧表示。,.,圖與網(wǎng)絡的基本概念與模型,定義:圖中的點用v表示，邊用e表示。對每條邊可用它所連接的點表示，記作：e1=v1,v1;e2=v1,v2;,端點,關聯(lián)邊,相鄰,若有邊e可表示為e=vi,vj，稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關聯(lián)邊。若點vi、vj與同一條邊關聯(lián)，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。,.,圖與網(wǎng)絡的基本概念與模型,環(huán),多重邊,簡單圖,如果邊e的兩個端點相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個點之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。,.,圖與網(wǎng)絡的基本概念與模型,鏈，圈，連通圖(P231),圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意Vi-1,Vi和vi+1均相鄰稱為鏈。用表示：,起點與終點重合的鏈稱作圈。如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。,.,圖與網(wǎng)絡的基本概念與模型,網(wǎng)絡（賦權圖）(P232),設圖G（V，E），對G的每一條邊(vi,vj)相應賦予數(shù)量指標wij，wij稱為邊(vi,vj)的權,賦予權的圖G稱為網(wǎng)絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。端點無序的賦權圖稱為無向網(wǎng)絡，端點有序的賦權圖稱為有向網(wǎng)絡。,.,11,圖與網(wǎng)絡的基本概念與模型,主要概念(p231-p232)無向圖：由點和邊構成的圖，記作G=（V，E）。有向圖：由點和弧構成的圖，記作D=（V，A）。連通圖：對無向圖G，若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖。回路：若路的第一個點和最后一個點相同，則該路為回路。賦權圖：對一個無向圖G的每一條邊(vi,vj)，相應地有一個數(shù)wij，則稱圖G為賦權圖，wij稱為邊(vi,vj)上的權。網(wǎng)絡：在賦權的有向圖D中指定一點，稱為發(fā)點，指定另一點稱為收點，其它點稱為中間點，并把D中的每一條弧的賦權數(shù)稱為弧的容量，D就稱為網(wǎng)絡。,.,最短路問題,如何用最短的線路將三部電話連起來？此問題可抽象為設ABC為等邊三角形，連接三頂點的路線（稱為網(wǎng)絡）。這種網(wǎng)絡有許多個，其中最短路線者顯然是二邊之和（如ABAC）。,A,B,C,.,最短路問題,A,B,C,P,但若增加一個周轉站（新點P），連接4點的新網(wǎng)絡的最短路線為PAPBPC。最短新路徑之長N比原來只連三點的最短路徑O要短。這樣得到的網(wǎng)絡不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。,.,最短路問題,問題描述：要求：就是從給定的網(wǎng)絡圖中找出一點到各點或任意兩點之間距離最短的一條路.有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應用。,.,最短路問題,例渡河游戲一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。,.,最短路問題,定義：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）點Vi表示河岸的狀態(tài)3）邊ek表示由狀態(tài)vi經(jīng)一次渡河到狀態(tài)vj4）權邊ek上的權定為1,我們可以得到下面的加權有向圖：,.,最短路問題,狀態(tài)說明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戲轉化為在下面的二部圖中求從v1到u1的最短路問題。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,.,最短路問題,求最短路有兩種算法:,狄克斯屈拉(Dijkstra)（雙標號）算法逐次逼近算法,最短路問題：對一個賦權的有向圖D中的指定的兩個點Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權數(shù)的總和被稱為從Vs到Vt的距離。,.,最短路問題,狄克斯屈拉(Dijkstra)標號算法的基本思路：若序列vs,v1.vn-1,vn是從vs到vt間的最短路，則序列vs,v1.vn-1必為從vs到vn-1的最短路。,假定v1v2v3v4是v1v4的最短路，則v1v2v3一定是v1v3的最短路，v2v3v4也一定是v2v4的最短路。,.,最短路問題,最短路的Dijkstra算法(雙標號法）的步驟：1.給出點V1以標號(0,s)2.找出已標號的點的集合I，沒標號的點的集合J以及弧的集合3.如果上述弧的集合是空集，則計算結束。如果vt已標號（lt,kt），則vs到vt的距離為lt，而從vs到vt的最短路徑，則可以從kt反向追蹤到起點vs而得到。如果vt未標號，則可以斷言不存在從vs到vt的有向路。如果上述的弧的集合不是空集，則轉下一步。4.對上述弧的集合中的每一條弧，計算sij=li+cij。在所有的sij中，找到其值為最小的弧。不妨設此弧為（Vc,Vd），則給此弧的終點以雙標號（scd,c）,返回步驟2。,.,最短路問題,(P233)例1求下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6各點的標號圖如下：,.,最短路問題,(P234)例2電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數(shù)表示兩地間公路的長度（單位：公里）。解：這是一個求無向圖的最短路的問題?？梢园褵o向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可。,.,最短路問題,（0,s）V1（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3)v2,(22,6)V7（乙地）,V5(14,3),V6(16,5),V3(10,1),V4(18,5),.,最短路問題,例3設備更新問題。某公司使用一臺設備，在每年年初，公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。請設計一個五年之內的更新設備的計劃，使得五年內購置費用和維修費用總的支付費用最小。已知：設備每年年初的價格表設備維修費如下表,.,最短路問題,例3的解：將問題轉化為最短路問題，如下圖：用vi表示“第i年年初購進一臺新設備”,?。╲i,vj）表示第i年年初購進的設備一直使用到第j年年初。把所有弧的權數(shù)計算如下表：,.,最短路問題,(繼上頁)把權數(shù)賦到圖中，再用Dijkstra算法求最短路。最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1v3v6和v1v4v6,.,最短路問題,課堂練習：1.用Dijkstra算法求下圖從v1到v6的最短距離及路線。,v3,v5,4,v1到v6的最短路為：,.,最短路問題,2.求從v1到v8的最短路徑,.,最短路問題,v1到v8的最短路徑為v1v4v7v5v8，最短距離為10,.,最短路問題,3.求下圖中v1點到另外任意一點的最短路徑,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,.,最短路問題,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,.,最短路問題,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,.,最短路問題,算法適用條件：Dijkstra算法只適用于全部權為非負情況，如果某邊上權為負的，算法失效。此時可采用逐次逼近算法。,例6.7如右圖所示中按dijkstra算法可得P(v1)=5為從vsv1的最短路長顯然是錯誤的，從vsv2v1路長只有3。,v2,vs,v1,5,-5,8,.,最小生成樹問題,樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。,例6.2乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。,運動員,.,最小生成樹問題,例某企業(yè)的組織機構圖也可用樹圖表示。,.,樹與圖的最小樹,樹：無圈的連通圖即為樹,性質1：任何樹中必存在次為1的點。(一個點Vi的相關聯(lián)邊的數(shù)目稱為點Vi的次)性質2：n個頂點的樹必有n-1條邊。性質3：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。,.,37,最小生成樹問題,樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。,圖11-11中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹，(c)因為不連通所以也不是樹。,.,最小生成樹問題,圖的最小部分樹(支撐樹),如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。,G1,G2,.,最小生成樹問題,.,最小生成樹問題,.,最小生成樹問題,.,最小生成樹問題,.,最小生成樹問題,.,44,最小生成樹問題,給了一個無向圖G=(V,E)，我們保留G的所有點，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖11-12中，(c)就是(a)的生成樹。最小生成樹問題就是指在一個賦權的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權數(shù)之和為最小。,(a),(b),(c),.,最小生成樹問題,求樹的方法：破圈法和避圈法,破圈法,.,最小生成樹問題,部分樹,.,最小生成樹問題,避圈法,.,最小生成樹問題,賦權圖中求最小樹的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最長邊，直到無圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,邊數(shù)n-1=5,.,最小生成樹問題,得到最小樹：,MinC(T)=15,.,最小生成樹問題,避圈法:去掉G中所有邊，得到n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通(即:n-1條邊)。,.,最小生成樹問題,v1,v2,v3,v4,v5,v6,4,3,5,2,1,MinC(T)=15,.,最小生成樹問題,練習：應用破圈法求最小樹,.,最小生成樹問題,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,.,最小生成樹問題,練習：應用避圈法求最小樹,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,.,最小生成樹問題,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,.,最小生成樹問題,課堂練習：,MinC(T)=12,MinC(T)=15,答案：,.,最小生成樹問題,3,4,1,2,2,3,2,3,2,4,2,MinC(T)=12,MinC(T)=18,.,74,最小生成樹問題,例5、某大學準備對其所屬的7個學院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡的可能聯(lián)通的途徑如下圖，圖中v1,v7表示7個學院辦公室，請設計一個網(wǎng)絡能聯(lián)通7個學院辦公室，并使總的線路長度為最短。,解：此問題實際上是求圖11-14的最小生成樹，這在例4中已經(jīng)求得，也即按照圖11-13的(f)設計，可使此網(wǎng)絡的總的線路長度為最短，為19百米?！肮芾磉\籌學軟件”有專門的子程序可以解決最小生成樹問題。,.,網(wǎng)絡的最大流,如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡最大流問題。,.,網(wǎng)絡的最大流,基本概念：1.容量網(wǎng)絡：隊網(wǎng)絡上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡中通常規(guī)定一個發(fā)點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網(wǎng)絡中其他點稱為中間點。,s,t,4,8,4,4,1,2,2,6,7,9,.,網(wǎng)絡的最大流,2.網(wǎng)絡的最大流是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。,3.流與可行流流是指加在網(wǎng)絡各條弧上的實際流量，對加在弧(vi,vj)上的負載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。,容量限制條件。容量網(wǎng)絡上所有的弧滿足：0fijcij中間點平衡條件。,若以v(f)表示網(wǎng)絡中從st的流量，則有：,.,網(wǎng)絡的最大流,結論：任何網(wǎng)絡上一定存在可行流。（零流即是可行流）,網(wǎng)絡最大流問題：指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。,.,79,網(wǎng)絡的最大流,一、最大流的數(shù)學模型例6某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡系統(tǒng)從采地v1向銷地v7運送石油，問每小時能運送多少加侖石油？,v5,.,80,網(wǎng)絡的最大流,我們可以為此例題建立線性規(guī)劃數(shù)學模型：設弧(vi,vj)上流量為fij，網(wǎng)絡上的總的流量為F，則有：,.,81,網(wǎng)絡的最大流,在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示了網(wǎng)絡中的流量必須滿足守恒條件，發(fā)點的流出量必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應小于等于弧(vi,vj)的容量cij，并大于等于零，即0fijcij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡流fij稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學軟件”，馬上得到以下的結果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最優(yōu)值（最大流量）=10。,.,82,網(wǎng)絡的最大流,二、最大流問題網(wǎng)絡圖論的解法對網(wǎng)絡上弧的容量的表示作改進。為省去弧的方向，如下圖:(a)和(b)、(c)和(d)的意義相同。用以上方法對例6的圖的容量標號作改進，得下圖,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,.,83,網(wǎng)絡的最大流,求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡的流量pf。（3）在這條路上，減少每一條弧的順流容量pf，同時增加這些弧的逆流容量pf，返回步驟（1）。用此方法對例6求解：第一次迭代：選擇路為v1v4v7?；。╲4,v7）的順流容量為2，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：,.,84,網(wǎng)絡的最大流,第二次迭代：選擇路為v1v2v5v7?；。╲2,v5）的順流容量為3，決定了pf=3，改進的網(wǎng)絡流量圖如下圖：第三次迭代：選擇路為v1v4v6v7。?。╲4,v6）的順流容量為1，決定了pf=1，改進的網(wǎng)絡流量圖如下圖：,.,85,網(wǎng)絡的最大流,第四次迭代：選擇路為v1v4v3v6v7?；。╲3,v6）的順流容量為2，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：第五次迭代：選擇路為v1v2v3v5v7?；。╲2,v3）的順流容量為2，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：,.,86,網(wǎng)絡的最大流,經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。最大流量圖如下圖：,“管理運籌學軟件”中還有專門的子程序用于解決最大流問題。,.,87,最小費用最大流問題,最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡，對每一條?。╲i,vj），除了給出容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流F，并使得總運送費用最小。一、最小費用最大流的數(shù)學模型例7由于輸油管道的長短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，還有不同的單位流量的費用bij，cij的單位為萬加侖/小時，bij的單位為百元/萬加侖。如圖。從采地v1向銷地v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流量和最小費用。,.,88,最小費用最大流問題,這個最小費用最大流問題也是一個線性規(guī)劃的問題。解：我們用線性規(guī)劃來求解此題，可以分兩步走。第一步，先求出此網(wǎng)絡圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運籌學軟件已經(jīng)獲得結果。第二步，在最大流量F的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下：仍然設?。╲i,vj）上的流量為fij，這時已知中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)顯然是求其流量的最小費用fij.bij。由此得到線性規(guī)劃模型如下：,.,89,最小費用最大流問題,.,90,最小費用最大流問題,用管理運籌學軟件，可求得如下結果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費用)=145。對照前面例6的結果，可對最小費用最大流的概念有一個深刻的理解。如果我們把例7的問題改為：每小時運送6萬加侖的石油從采地v1到銷地v7最小費用是多少？應怎樣運送？這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧(vi,vj)賦權以容量cij及單位費用bij的網(wǎng)絡中，求一個給定值f的流量的最小費用，這個給定值f的流量應小于等于最大流量F，否則無解。求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費用流的線性規(guī)劃的模型了。,.