數(shù)學建模中的圖論方法.doc

數(shù)學建模中的圖論方法一、引言我們知道，數(shù)學建模競賽中有問題A和問題B。一般而言，問題A是連續(xù)系統(tǒng)中的問題，問題B是離散系統(tǒng)中的問題。由于我們在大學數(shù)學教育內容中，連續(xù)系統(tǒng)方面的知識的比例較大，而離散數(shù)學比例較小。因此很多人有這樣的感覺，A題入手快，而B題不好下手。另外，在有限元素的離散系統(tǒng)中，相應的數(shù)學模型又可以劃分為兩類，一類是存在有效算法的所謂P類問題，即多項式時間內可以解決的問題。但是這類問題在MCM中非常少見，事實上，由于競賽是開卷的，參考相關文獻，使用現(xiàn)成的算法解決一個P類問題，不能顯示參賽者的建模及解決實際問題能力之大小；還有一類所謂的NP問題，這種問題每一個都尚未建立有效的算法，也許真的就不可能有有效算法來解決。命題往往以這種NPC問題為數(shù)學背景，找一個具體的實際模型來考驗參賽者。這樣增加了建立數(shù)學模型的難度。但是這也并不是說無法求解。一般來說，由于問題是具體的實例，我們可以找到特殊的解法，或者可以給出一個近似解。圖論作為離散數(shù)學的一個重要分支，在工程技術、自然科學和經濟管理中的許多方面都能提供有力的數(shù)學模型來解決實際問題，所以吸引了很多研究人員去研究圖論中的方法和算法。應該說，我們對圖論中的經典例子或多或少還是有一些了解的，比如，哥尼斯堡七橋問題、中國郵遞員問題、四色定理等等。圖論方法已經成為數(shù)學模型中的重要方法。許多難題由于歸結為圖論問題被巧妙地解決。而且，從歷年的數(shù)學建模競賽看，出現(xiàn)圖論模型的頻率極大，比如：AMCM90B掃雪問題；AMCM91B尋找最優(yōu)Steiner樹；AMCM92B緊急修復系統(tǒng)的研制(最小生成樹)AMCM94B計算機傳輸數(shù)據(jù)的最小時間(邊染色問題)CMCM93B足球隊排名(特征向量法)CMCM94B鎖具裝箱問題(最大獨立頂點集、最小覆蓋等用來證明最優(yōu)性)CMCM98B災情巡視路線(最優(yōu)回路)等等。這里面都直接或是間接用到圖論方面的知識。要說明的是，這里圖論只是解決問題的一種方法，而不是唯一的方法。本文將從圖論的角度來說明如何將一個工程問題轉化為合理而且可求解的數(shù)學模型，著重介紹圖論中的典型算法。這里只是一些基礎、簡單的介紹，目的在于了解這方面的知識和應用，拓寬大家的思路，希望起到拋磚引玉的作用，要掌握更多還需要我們進一步的學習和實踐。二、基本概念和性質首先給出圖論中的一些基本概念。1一個圖G由一個頂點集V和一個邊的集E組成。E中每個元素e是連接頂點集 V中兩個頂點u和v的邊，稱e與u，v關聯(lián)。我們規(guī)定連接兩個頂點u、v至多有一條邊，且一條邊的兩個頂點不重合，這種圖稱為簡單圖。2頂點集為V，邊集為E的圖G通常記為G=（V，E）。圖G1=（V1，E1）稱為G的子圖，如果 V1V， E1E。3頂點v的度(或“次”)是指與v相關聯(lián)的邊的個數(shù)。圖G的度數(shù)之和為邊數(shù)的兩倍。4若圖G中任意兩個頂點u、v之間都存在連接它們的路，稱G為連通圖。5W=v0e1v1e2ekvk，其中eiE，vjV，ei與vi-1，vi關聯(lián)，稱W是圖G的一條道路。v0是起點，vk是終點；各邊相異的道路叫做行跡，各頂點相異的道路叫做軌道；起點和終點重合的道路為回路；起點和終點重合的軌道為圈；包含圖中每條邊的回路稱為Euler回路；含Euler回路的圖稱為Euler圖。6一個無圈的連通圖稱為樹。樹是最簡單而最重要的一類圖。樹有下列重要性質：性質：1)在樹中去掉任意一條邊，所得的圖是不連通的。2)在樹中任意兩個不相鄰的頂點u、v之間添加一條新的邊，所得的圖恰有一個圈。下述定理是樹的判斷定理：定理：若圖G具有下列性質中的兩條，則它是樹，且也具有第三條性質。(1)G是連通圖；(2)G沒有圈；(3)G的頂點數(shù)=G的邊數(shù)+1。7如果圖G=（V，E）的子圖Gt=（Vt，Et）是一個樹，且Vt=V，稱G t是G的生成樹。G連通的充要條件是G有生成樹。生成樹一般而言數(shù)量很大。8設對圖G=（V，E）的每一條邊e賦予一個實數(shù)W（e），稱為e的權，G稱為賦權圖(加權圖)。假設G是連通的賦權圖，要找G的連通子圖 G *=（V，E*），使得W（G*）=為最小。顯然G*應為G的一個生成樹。G的權最小的生成樹稱為 G的最小生成樹。三、算法介紹31 最短軌道問題背景：給定連接若干城市的鐵路網，尋求從指定城市v0到各城v去的最短道路。數(shù)學模型：圖G為一賦權圖，對任給的vV(G)，尋求軌道P(v0,v)，使得W(P(v0,v)=minW(P),P取自所有v0到v的軌道集合其中W(P)是軌道P上各邊權之和。這一問題可用迪克斯特拉(Dijkstra)算法解決?；舅枷耄簭钠瘘cv0開始，逐步尋找到達各點的最短路，在每一步都對頂點記錄一個數(shù)，稱之為該點的標號，它表示v0到該點的最短距離的上界，或就是v0到該點的最短距離。實際上每一步都通過把至少一個具有T標號的點變成P標號(即把一個不是最短距離標號的頂點變成是最短距離標號的頂點)，這樣最多經過|V(G)|-1步就可完成。步驟：記l(v)為v0到v的距離。(1) l(v0)=0，l(v) = ，(vv0)；S0=v0，i=0。(2) 對vSi，minl(v)，l(vi)+w(viv)代替l(v)；這樣找到點vi1使得l(v)取最小值，v(i1)(Si的余集)。令S(i1)Siv(i+1)。(3) i=|V(G)|-1時停止，否則，i+1，轉到(2)。實例：CMCM94A公路選址問題。32 求最小生成樹1克羅斯克爾(Kruskal)算法(1956年)，俗稱“避圈法”背景：筑路選線問題 欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為Cij。設計一個線路圖，使總造價最低。分析：選線問題的數(shù)學模型是在連通加權圖上求權最小的連通生成子圖。顯然，權最小的連通生成子圖是一個生成樹，即求取連通加權圖上的權最小的生成樹，這就歸結為最小生成樹問題。這個問題可由克羅斯克爾(Kruskal)算法解決。思路：從“邊”著手選最小生成樹。步驟：設G為由m個節(jié)點組成的連通賦權圖。(1) 先把G中所有的邊按權值大小由小到大重新排列，并取權最小的一條邊為樹T中的邊。即選e1E，使得w(e1)min。(2) 從剩下的邊中按(1)中的排列取下一條邊。若該邊與前面已取進T中的邊構成一個回路，則舍棄該邊，否則也把它取進T中。若e1，e2，ei已經選好，則從Ee1，e2，ei中選取ei1，使得Ge1，e2，ei，ei+1中無圈，且w(ei+1)=min。(3) 重復步驟(2)，直到T中有m1條邊為止。則T為G的最小生成樹。該算法的復雜度為O(eloge)，其中e是圖G中的邊數(shù)。2普萊姆(Prim)算法思路：從點入手來選邊步驟：(1) 在圖G中任取一個節(jié)點vi1，并放入T中。(2) 令SV(G)/V(T)，V(G)、V(T)分別是G、T的節(jié)點集。(3) 在所有連接V(T)節(jié)點與S節(jié)點的邊中，選出權值最小的邊(u0,v0)，即w(u0,v0)=minw(u,v)|uV(T), vS。(4) 將邊(u0,v0)放入T中。(5) 重復步驟(2)(4)，直到G中節(jié)點全部取完。該算法的復雜度為O(n2)，其中n為圖G的節(jié)點數(shù)。31975年管梅谷提出的“破圈法”33 Steiner生成樹實際背景：在已有網絡上選擇連通幾個城市的最廉價交通或通訊網。數(shù)學模型：從已知的加權連通圖上求取最小的樹狀子圖，使此樹包含指定的頂點子集。第一個的邊長為，第二個的邊長為1，總費用第二個更少。分析：與傳統(tǒng)的最小生成樹相比，這里可以引入若干“虛擬站”并構造一個新的Steiner樹，這樣可以降低由一組站生成的傳統(tǒng)的最小生成樹所需的費用(降低的費用大概為13.4%)。而且為構造一個有n個頂點的網絡的費用，最低的Steiner樹決不需要多于(n2)個虛設站。當然，有時最小Steiner生成樹與最小生成樹相同。尋求最小Steiner生成樹的算法有Melzak算法(1961年)，但是這是一個指數(shù)時間的算法，現(xiàn)在沒有多項式時間的算法，換句話說它是一個NP問題。而且，這里的要求是用直折線代替歐氏直線距離，因而不能利用直接的算法。所以在解決這樣的問題的時候，為減少運算的時間，理論上的分析是必要的：比如樹的長度的下界，Steiner樹的存在性，虛設站的位置等等。常用的算法還包括窮舉法、模擬退火法等。Melzak算法：其基礎是3點steiner樹，即3點Fermat問題的幾何作圖法。參考2，Page375。模擬退火法原理：模擬退火法(Simulated annealing, SA)是模擬熱力學中經典粒子系統(tǒng)的降溫過程，來求解極值問題。當孤立粒子系統(tǒng)的溫度以足夠慢的速度下降時，系統(tǒng)近似處于熱力學平衡狀態(tài)，最后系統(tǒng)將達到本身的最低能量狀態(tài)，即基態(tài)，這相當于能量函數(shù)的全局極小點。其步驟如下(也稱為Metropolis過程)：（1） 給定初始溫度T0，及初始點，計算該點的函數(shù)值f(x)。（2） 隨機產生擾動x，得到新點x=x+x，計算新點函數(shù)值f(x),及函數(shù)值差f=f(x)-f(x)。（3） 若f0，則接受新點，作為下一次模擬的初始點；（4） 若f0，則計算新點接受概率：，產生 0，1區(qū)間上均勻分布的偽隨機數(shù)r,r0,1，如果p(f)r，則接受新點作為下一次模擬的初始點；否則放棄新點，仍取原來的點作為下一次模擬的初始點。模擬退火法實例：1 MCM91B(通訊網絡中的極小生成樹)是一個求STEINER生成樹問題，參見工科數(shù)學專輯Page：7078。2、CMCM 97A題97年全國大學生數(shù)模競賽A題“零件的參數(shù)設計”，可以歸結為非線性規(guī)劃模型，由于目標函數(shù)很復雜，且又是一個多維函數(shù)，因此求解比較困難，為應用模擬退火法進行求解，將7個自變量的取值范圍進行離散化，取步長為0.0001，這樣，所有7個變量取值就組成了一個極為龐大的離散空間, 而這個問題變成組合優(yōu)化模型。這個問題算法的狀態(tài)調整規(guī)則是：每次從7個自變量中隨機選取1-4個，讓選取的自變量隨機移動，考慮選取的自變量在兩個方向移動組合，從中選取最佳的作為候選者，自變量移動的距離隨著溫度的降低而減少，為避免陷入局部極小，可以從多個隨機選取的初始值開始計算，算法的其它步驟同上。3、CMCM 98B題98年全國大學生數(shù)學建模競賽B題“水災巡視問題”，是一個推銷員問題，本題有53個點，所有可能性大約為exp(53),目前沒有好方法求出精確解，既然求不出精確解，我們使用模擬退火法求出一個較優(yōu)解，將所有結點編號為1到53，1到53的排列就是系統(tǒng)的結構，結構的變化規(guī)則是：從1到53的排列中隨機選取一個子排列，將其反轉或將其移至另一處，能量E自然是路徑總長度。具體算法描述如下：步1： 設定初始溫度T，給定一個初始的巡視路線。步2：步3 -8循環(huán)K次步3：步 4-7循環(huán)M次步4：隨機選擇路線的一段步5：隨機確定將選定的路線反轉或移動，即兩種調整方式：反轉、移動。步6：計算代價D，即調整前后的總路程的長度之差步7：按照如下規(guī)則確定是否做調整：如果D0，則按照EXP(-D/T)的概率進行調整步8：T*0.9-T，降溫34 Euler回路設G是一個圖，若存在這樣一條回路，使它經過圖中的每條邊且只經過一次又回到起始節(jié)點，就稱這樣的回路為Euler回路。背景：哥尼斯堡七橋問題定理：對連通圖G，下列條件是相互等價的：(1) G是Euler圖；(2) G的每個節(jié)點的度數(shù)都是偶數(shù)；(3) G的邊集可以分解為若干個回路的并。對有向圖，出度入度。算法：弗羅萊(Fleury)算法(1921)(1) 任給v0V(G)，Rv0(2) 設路Rv0e1v1e2v2eivi已選定，則從E(G)e1,e2,ei中選邊ei+1，且滿足：ei+1與vi相連；除非已無選擇，ei+1不要選E(Gi)E(G) e1,e2,ei 中的橋(注：橋，去掉之后圖不連通)(3) 重復(2)，直到不能再選為止實例：MCM90B鏟雪問題中單車道單車掃雪地圖是Euler圖的情形。說明：如果圖G不是Euler圖，也就是說不存在Euler回路，這時候求解就比較困難。求解前需要做一些處理，添加一個邊子集E1，E1GG1構成一個Euler圖，然后再尋找Euler回路。注意圖G不是Euler圖時，必有偶數(shù)個奇數(shù)度的節(jié)點，可以給這些節(jié)點兩兩配對，求兩點間的最短路，將這些最短路畫在一起構成附加邊子集E1。這里的困難在于：奇數(shù)度的節(jié)點較多時，配對方案也多。35 網絡中的最大流背景：把商品從生產地運往市場，交通網上每個路段能力給定的條件下，設計一個運輸方案，使得運輸最快。網絡：規(guī)定起點s、中間點和終點t的賦權圖。數(shù)學模型：有向圖G，每邊加權c(e)，稱c(e)為邊e之容量，設G為嚴格的有向圖，則稱這個有向的加權圖為一個網絡。映射f：E(G)R滿足(c1) 任給eE(G)，0f(e)c(e)；(c2) 任給vV(G)s,t，0；其中a(v)是以v為頭的邊集(流進)，b(v)是以v為尾的邊集(流出) ，即除起點和終點外，各節(jié)點流入量總和等于流出量總和。稱f(e)為流函數(shù)，稱F為流量。我們的目標是尋找一個流函數(shù)f，使其流量最大。1956年，福特(Ford)和福爾克遜(Fulkerson)提出了求最大流的算法。最大流最小割定理：流過網絡的最大流量等于最小割集的容量。2F算法：(1) 對每邊e，選f(e)0；(2) 標志頂s，其它頂未標志；(3) 選可“向前標志”或可“向后標志”的頂v。若無此種頂可選時，停止，現(xiàn)流函數(shù)即為最大流；若有此種頂可選時，則得到新的標志頂v及標志邊e。若vt，則轉(4)；否則轉(3)。(4) 設已得標志之軌為(此軌為無向的)se1v1e2v2ett，從t開始沿此軌逆行，令，若ei是前進邊，即在有向圖中eivi1vi(sv0，tvl)，則f(ei)f(ei)；若ei是后退邊，即在有向圖中eivivi1，則f(ei)f(ei)；(5) 轉(2)。向前和向后標志的含義如下：若euv，u已有標志，v沒有標志，且c(e)f(e)，則稱通過邊e可以向前標志頂點v，且規(guī)定(e)c(e)f(e)，得到標志邊e。若evu，u已有標志，v沒有標志，且f(e)0，則稱通過邊e可以向后標志頂v，規(guī)定(e)f(e)，且得到標志邊e。(e)的含義是邊e上可以增載的上界。說明：1 如果每邊之容量c(e)都是有理數(shù)，則2F算法在有限步之內可以求得最大流。2 容量有上下界的網絡，需要構造附加網絡。3.6 最小費用 最大流問題這是在上述討論的基礎上增加關于使費用最小的目標。解決的辦法是采用“對偶法原理”：1 先用上面討論的方法求出網絡的最大流量；2 然后在原始的網絡中福德算法找出從起點 vs 到終點 vt 的最短路線最短增廣鏈；3 在該增廣鏈上找出最大調整量，并調整流量得到一個可行流，則此可行流的費用最小。如果此時流量等于最大流量，那么它就是最小費用最大流；否則應繼續(xù)調整。應用：運輸問題，如CMCM2000B鋼管的采購和運輸問題。說明：1這里的介紹只是圖論中的一部分內容，更多的需要我們進一步學習。2算法都是描述性的，有些可以找到現(xiàn)成的程序，但是最好是自己實現(xiàn)。3這里的例子只是解決問題的一種方法，不是唯一的方法。4注意實際應用中直接利用所給算法解決問題的情況很少，通常只是解決問題的一部分，而且需要建立模型，把實際問題用圖論術語描述出來。所以要善于利用這里的工具。其它方面的應用，如工序問題，最大獨立集，最小覆蓋集，郵遞員問題，規(guī)劃審核技術，關鍵軌道方法，可靠通信網絡的構造問題，班級人員分配等等。37 工序問題統(tǒng)籌方法是組織生產計劃的方法，它用網絡圖表達生產和工程的進度，計算各項工序的有關時間參數(shù)。一項工程總是由許多相互獨立的工序組成的，各道工序之間有一定的先后次序。完成每道工序需要的時間（不妨設單位為小時）稱為工序的長度。因此我們可以用一個各條邊有方向的圖（稱為有向圖）表示各項工序之間的互相依賴關系。以一條有向變來表示一道工序，有向邊的權即為此工序的長度，有向邊的起點和終點分別表示相應工序的開工和完工，稱為事項，前接工序和完工事項即為后續(xù)工序和開工事項。實例：上海MCM91B四、網絡規(guī)劃的應用1最小生成樹網絡規(guī)劃例1例1求下圖的一個最小生成樹。解：首先取 G1=（V1，E1），V1=v0，E1=其次，一端屬于V1，一端不屬于V1的最短邊是v0v1，所以有 G2=（V2，E2），V2=v0，v1，E2=v0v1。現(xiàn)在，一端屬于V2，一端不屬于V2的最短邊是v1v3，所以有 G3=（V3，E3），V3=v0，v1，v3，E3=vov1，v1v3。類似做下去，最后得最小生成樹的邊為： v0v1，v1v3，v2v3，v2v5，v5v6，v4v6。 2存儲糧食模型網絡規(guī)劃例2 例2某鄉(xiāng)有七個村A1，A2，.，A7，需儲存糧食數(shù)量分別為 50，75，62，40，100，80，35噸。各村之間有公路連通，如圖?，F(xiàn)要選擇某村建立倉庫儲存所有糧食，問應選擇何處最好？解：圖上連結兩村的邊所注的數(shù)字表示該段公路的千米數(shù)。我們的目的是選擇倉庫的位置使運糧的噸千米數(shù)最小。首先比較 A1和A2兩處。在比較這兩個村莊時，因為倉庫無論建在 A1或A2，其他各村的糧食都要先運到 A2，所以我們可認為除 A1外各村的糧食都集中在 A2，共357噸?，F(xiàn)在事情很明顯，倉庫建在 A2時需把50噸糧食運3千米到 A2，建在 A1時需把357噸糧食運 3千米到A1，所以 A2較 A1好。以后我們不再考慮A1，因此可把 A1的糧食移到 A2以簡化問題。同理 A5也不必考慮，它的糧食可集中到 A4?？紤]其他五個村。我們猜想現(xiàn)在糧食數(shù)量大的村莊可能是個好主意。假定選擇 A4，我們考慮A6是否會更好：A2、 A7的糧食少運4千米，而A3、 A4的糧食多運4千米，可見A4較 A6好。同理可證A4比其他各村都好。因此倉庫應建在 A4。 3工作順序模型網絡規(guī)劃例3例3某工廠的改造工程由下列7道工序組成：A：拆遷；B：工程設計；C：土建工程設計，前接工序為 B；D：采購設備，前接工序為B；E：廠房土建，前接工序為A、C； F：設備安裝，前接工序為D、E；G：設備調試，前接工序為F。那么我們可用圖 3.4表示這個工程，其中S表示整個工程的開工， t表示完工。有時，為了表示工序之間的順序關系，需要引入虛工序。注意，用來表示工程進度的有向圖是不允許有回路的?，F(xiàn)在我們研究網絡圖的各種時間參數(shù)。 考慮圖3.5表示的網絡，我們把各事項（即圖的頂點）編號，一般要求每一工序的開工事項（即箭尾）的編號少于完工事項的編號（即箭頭）。每條有向邊旁所標數(shù)字為相應工序的長度。 某一工序A的最早開工時間t E (A)，表示該工序最早可在整個工程開工后t E (A)小時開工，這時間僅與該工序的開工事項有關，所以也可以說某一事項的最早時間 t E (k)，例如圖3.5中，事項4的最早時間是9（即工序1-4和 2-4都完成的時間）。因而有下列遞推公式 ik表示起點為i，終點為k的有向邊。整個工程完工事項的最早時間，就是全工程完工的最短時間，稱為總工期，記為 TE 。某一工序的最遲完工時間（或該工序完工事項的最遲時間） t E (k)，是在不誤總工期的條件下，該工序最遲應在整個工程開工后 t L (A)小時完成。因此 實際上，t E (k)就是由事項1到事項k的最長路的長度。t L (k)就是T E 減去k到n的最長路的長度。因而（2）的第二式也可寫成 工序ij的總時差定義為 即不誤總工期的條件下該工序的開工時間的機動時間，即可延遲開工的時間；而工序 ij的自由時差定義為 即在不誤下道工序最早開工時間的前提下，該工序開工時間的機動時間。從事項1到事項n的一條最長路稱為網絡圖的一條關鍵路，顯然在關鍵路上的每一事項 k滿足t L (k)=t E (k)，關鍵路上每一工序的總時差為 0，反之亦然。顯然，若關鍵路上工序能提前完成，整個工程才有可能提前完成；若關鍵路上工序未能按時完成，整個工程必然不能按期完成。求總工期和關鍵路的方法如下：首先對所有t E (i)置初始值零，然后利用公式（1）進行迭代，直到所有的 t E (i)不再改變，而自由時差為0的工序就是關鍵路上的工序。例如圖 3.5中網絡圖的總工期為28天，關鍵路為1-3-5-6-8。 4求網絡的最小費用最大流求網絡的最小費用最大流，弧旁的數(shù)字是容量(運費)。 一Ford和Fulkerson迭加算法. 基本思路：把各條弧上單位流量的費用看成某種長度,用求解最短路問題的方法確定一條自V1至Vn的最短路;在將這條最短路作為可擴充路,用求解最大流問題的方法將其上的流量增至最大可能值;而這條最短路上的流量增加后,其上各條弧的單位流量的費用要重新確定,如此多次迭代,最終得到最小費用最大流. 迭加算法： 設圖中雙線所示路徑為最短路徑，費用有向圖為W（fij） 1) 給定目標流量F或,給定最小費用的初始可行流fij=0 2) 若V(f)=F,停止,f為最小費用流;否則轉(3). 3) 構造fij 相應的新的費用有向圖W(fij),在W(fij)尋找Vs到Vt的最小費用有向路P(最短路),沿P增加流f的流量直到F,轉(2);若不存在從Vs到Vt的最小費用的有向路P,停止.f就是最小費用最大流. 在圖(a)中給出零流f, 在圖(b)中找到最小費用有向路,修改圖(a)中的可行流,=min4,3,5=3,得圖(c),再做出(c)的調整容量圖,再構造相應的新的最小費用有向路得圖(d), 修改圖(c)中的可行流, =min1,1,2,2=1,得圖(e),以此類推,一直得到圖(h),在圖(h)中以無最小費用有向路,停止,經計算: 圖(h)中 最小費用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38 圖(g)中 最大流=5 二圈算法： 具體解題步驟:1) 利用Ford和Fulkson標號算法找出流量為F(=最大流)的流f. 2) 構造f對應的調整容量的流網絡N(f). 3) 搜索N(f)中的負費用有向圖C(Floyd算法),若沒有則停止,否則轉(4). 4) 在C上找出最大的循環(huán)流,并加到N上去,同時修改N(F)中C的容量,轉(3). 利用Ford和Fulkson標號算法,得網絡的最大流F=5,見圖(a),由圖(a)構造相應的調整容量的流網絡(b),圖(b)中不存在負費用有向圖,故停止經計算: 圖(b)中 最小費用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38 圖(a)中 最大流為F=5參考文獻1 葉其孝編，大學生數(shù)學建模競賽輔導教材(2)，湖南教育出版社，1997。2 李尚志等，數(shù)學建模競賽教程，江蘇教育出版社，1996。3 葉其孝編，數(shù)學建模教育與國際數(shù)學建模競賽，工科數(shù)學雜志社，1994。4 王樹禾，圖論及其算法，中國科學技術大學出版社，1990。附錄一：Ford和Fulkerson迭加算法求網絡的最小費用最大流問題的C語言程序 /*Ford和Fulkerson迭加算法*/ #includestdio.h void main() int a,b,i,j,k,p,n,B1010,C1010,D1010,P101010; printf(please input n:n); scanf(%d,&n); printf(please input C%d%d,B%d%d:n,n,n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) scanf(%7d,%7d,&Cij,&Bij); /輸入各點(i,j)之間的容量Cij和運費Bij for(i=0;i=n;i+) for(j=0;j=n;j+) Dij=Bij; for(k=0;k=n;k+) Pijk=0; if(Dij100) /注：100表示Vi到Vj之間無可行路 Piji=1;Pijj=1; for(k=0;k=n;k+) for(i=0;i=n;i+) for(j=0;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; for(p=0;p=n;p+) Pijp=Pikp|Pkjp; /調用FLOYD算法 printf(D%d%d:n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) printf(%7d,Dij); printf(n); /由表D中的數(shù)值確定V0到V5的最短路 a=C13;b=B13*D05; printf(a=%d,b=%dn,a,b); B13=100; /將容量已滿的路改為不可行路 for(i=0;i=n;i+) for(j=0;j=n;j+) Dij=Bij; for(k=0;k=n;k+) Pijk=0; if(Dij100) Piji=1;Pijj=1; for(k=0;k=n;k+) for(i=0;i=n;i+) for(j=0;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; for(p=0;p=n;p+) Pijp=Pikp|Pkjp; /調用FLOYD算法 printf(D%d%d:n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) printf(%7d,Dij); printf(n); /由表D中的數(shù)值確定V0到V5的新最短路 a=a+C12;b=b+D05; printf(a=%d,b=%dn,a,b); B01=100;B12=100;B43=100; /將容量已滿的路改為不可行路 for(i=0;i=n;i+) for(j=0;j=n;j+) Dij=Bij; for(k=0;k=n;k+) Pijk=0; if(Dij100) Piji=1;Pijj=1; for(k=0;k=n;k+) for(i=0;i=n;i+) for(j=0;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; for(p=0;p=n;p+) Pijp=Pikp|Pkjp; /調用FLOYD算法 printf(D%d%d:n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) printf(%7d,Dij); printf(n); /由表D中的數(shù)值確定V0到V5的新最短路 a=a+C24-C43;b=b+D05; printf(a=%d,b=%dn,a,b); B24=100; /將容量已滿的路改為不可行路 for(i=0;i=n;i+) for(j=0;j=n;j+) Dij=Bij; for(k=0;k=n;k+) Pijk=0; if(Dij100) Piji=1;Pijj=1; for(k=0;k=n;k+) for(i=0;i=n;i+) for(j=0;j=n;j+) if(Dik+DkjDij) Dij=Dik+Dkj; for(p=0;p=n;p+) Pijp=Pikp|Pkjp; /調用FLOYD算法 printf(D%d%d:n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) printf(%7d,Dij); printf(n); /檢驗有無V0到V5的新最短路 運行結果: please input n: 5 please input C55,B55: 0,0 4,1 5,3 0,100 0,100 0,100 0,100 0,0 1,1 3,3 0,100 0,100 0,100 0,100 0,0 0,100 2,4 0,100 0,100 0,100 0,100 0,0 0,100 5,2 0,100 0,100 0,100 1,1 0,0 2,4 0,100 0,100 0,100 0,100 0,100 0,0 D55: 0 1 2 4 6 6 100 0 1 3 5 5 100 100 0 5 4 7 100 100 100 0 100 2 100 100 100 1 0 3 100 100 100 100 100 0 a=3,b=18 D55: 0 1 2 7 6 9 100 0 1 6 5 8 100 100 0 5 4 7 100 100 100 0 100 2 100 100 100 1 0 3 100 100 100 100 100 0 a=4,b=27 D55: 0 100 3 100 7 11 100 0 100 100 100 100 100 100 0 100 4 8 100 100 100 0 100 2 100 100 100 100 0 4 100 100 100 100 100 0 a=5,b=38 D55: 0 100 3 100 100 100 100 0 100 100 100 100 100 100 0 100 100 100 100 100 100 0 100 2 100 100 100 100 0 4 100 100 100 100 100 0 /注：100表示Vi到Vj之間無可行路附錄二：破圈法求網絡的最小費用最大流問題的C語言程序 /*圈算法*/ #includestdio.h int min(int x,int y) if(xy) return(x); else return(y); void main() int a=0,b=0,i,j,k,p,n,t,A1010,P1010,B1010,C1010,D1010; printf(please input n:n); scanf(%d,&n); printf(please input C%d%d,B%d%d:n,n,n,n,n); for(i=0;i=n;i+) for(j=0;j=n;j+) scanf(%7d,%7d,&Cij,