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

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