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

1、數(shù)學(xué)建模中的圖論方法一、引言我們知道，數(shù)學(xué)建模競(jìng)賽中有問(wèn)題A和問(wèn)題B。一般而言，問(wèn)題A是連續(xù)系統(tǒng)中的問(wèn)題，問(wèn)題B是離散系統(tǒng)中的問(wèn)題。由于我們?cè)诖髮W(xué)數(shù)學(xué)教育內(nèi)容中，連續(xù)系統(tǒng)方面的知識(shí)的比例較大，而離散數(shù)學(xué)比例較小。因此很多人有這樣的感覺(jué)，A題入手快，而B(niǎo)題不好下手。另外，在有限元素的離散系統(tǒng)中，相應(yīng)的數(shù)學(xué)模型又可以劃分為兩類，一類是存在有效算法的所謂P類問(wèn)題，即多項(xiàng)式時(shí)間內(nèi)可以解決的問(wèn)題。但是這類問(wèn)題在MCM中非常少見(jiàn)，事實(shí)上，由于競(jìng)賽是開(kāi)卷的，參考相關(guān)文獻(xiàn)，使用現(xiàn)成的算法解決一個(gè)P類問(wèn)題，不能顯示參賽者的建模及解決實(shí)際問(wèn)題能力之大??；還有一類所謂的NP問(wèn)題，這種問(wèn)題每一個(gè)都尚未建立有效的算法，

2、也許真的就不可能有有效算法來(lái)解決。命題往往以這種NPC問(wèn)題為數(shù)學(xué)背景，找一個(gè)具體的實(shí)際模型來(lái)考驗(yàn)參賽者。這樣增加了建立數(shù)學(xué)模型的難度。但是這也并不是說(shuō)無(wú)法求解。一般來(lái)說(shuō)，由于問(wèn)題是具體的實(shí)例，我們可以找到特殊的解法，或者可以給出一個(gè)近似解。圖論作為離散數(shù)學(xué)的一個(gè)重要分支，在工程技術(shù)、自然科學(xué)和經(jīng)濟(jì)管理中的許多方面都能提供有力的數(shù)學(xué)模型來(lái)解決實(shí)際問(wèn)題，所以吸引了很多研究人員去研究圖論中的方法和算法。應(yīng)該說(shuō)，我們對(duì)圖論中的經(jīng)典例子或多或少還是有一些了解的，比如，哥尼斯堡七橋問(wèn)題、中國(guó)郵遞員問(wèn)題、四色定理等等。圖論方法已經(jīng)成為數(shù)學(xué)模型中的重要方法。許多難題由于歸結(jié)為圖論問(wèn)題被巧妙地解決。而且，從歷年

3、的數(shù)學(xué)建模競(jìng)賽看，出現(xiàn)圖論模型的頻率極大，比如：AMCM90B掃雪問(wèn)題；AMCM91B尋找最優(yōu)Steiner樹(shù)；AMCM92B緊急修復(fù)系統(tǒng)的研制（最小生成樹(shù)）AMCM94B計(jì)算機(jī)傳輸數(shù)據(jù)的最小時(shí)間（邊染色問(wèn)題）CMCM93B足球隊(duì)排名（特征向量法）CMCM94B鎖具裝箱問(wèn)題（最大獨(dú)立頂點(diǎn)集、最小覆蓋等用來(lái)證明最優(yōu)性）CMCM98B災(zāi)情巡視路線（最優(yōu)回路）等等。這里面都直接或是間接用到圖論方面的知識(shí)。要說(shuō)明的是，這里圖論只是解決問(wèn)題的一種方法，而不是唯一的方法。本文將從圖論的角度來(lái)說(shuō)明如何將一個(gè)工程問(wèn)題轉(zhuǎn)化為合理而且可求解的數(shù)學(xué)模型，著重介紹圖論中的典型算法。這里只是一些基礎(chǔ)、簡(jiǎn)單的介紹，目的在

4、于了解這方面的知識(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)。圖Gi=(Vi,Ei)稱為G的子圖，如果Vi(=V,Ei(=Eo3 .頂點(diǎn)v的度(或“次”)是指與v相關(guān)聯(lián)的邊的個(gè)數(shù)。圖G的度數(shù)之和為邊數(shù)的兩倍。4 .若圖G中任意兩個(gè)頂點(diǎn)u、v之間都存在連

5、接它們的路，稱G為連通圖。5 .W=v0eivie2ekvk,其中eiE,vjV,ei與vi-i,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è)無(wú)圈的連通圖稱為樹(shù)。樹(shù)是最簡(jiǎn)單而最重要的一類圖。樹(shù)有下列重要性質(zhì)：性質(zhì)：i)在樹(shù)中去掉任意一條邊，所得的圖是不連通的。7 )在樹(shù)中任意兩個(gè)不相鄰的頂點(diǎn)u、v之間添加一條新的邊，所得的圖恰有一個(gè)圈。下述定理是樹(shù)的判斷定理：定理：若圖G具有下列性質(zhì)中的兩條，

6、則它是樹(shù)，且也具有第三條性質(zhì)。(1) .G是連通圖；(2) .G沒(méi)有圈；(3) .G的頂點(diǎn)數(shù)=G的邊數(shù)+i。7 .如果圖G=(V,E)的子圖Gt=(Vt,Et)是一個(gè)樹(shù)，且Vt=V,稱Gt是G的生成樹(shù)。G連通的充要條件是G有生成樹(shù)。生成樹(shù)一般而言數(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*)=ZW(e)為最eE小。顯然G*應(yīng)為G的一個(gè)生成樹(shù)。G的權(quán)最小的生成樹(shù)稱為G的最小生成樹(shù)。三、算法介紹3.i最短軌道問(wèn)題背景：給定連接若干城市的鐵路網(wǎng)，尋求從指定城市V0到各城

7、v去的最短道路。數(shù)學(xué)模型：圖G為一賦權(quán)圖，對(duì)任給的vV(G),尋求軌道P(v0,v),使得W(P(v0,v)尸minW(P),P取自所有v0至Uv的軌道集合其中W(P)是軌道P上各邊權(quán)之和。這一問(wèn)題可用迪克斯特拉(Dijkstra)算法解決?；舅枷耄簭钠瘘c(diǎn)v0開(kāi)始，逐步尋找到達(dá)各點(diǎn)的最短路，在每一步都對(duì)頂點(diǎn)記錄一個(gè)數(shù)，稱之為該點(diǎn)的標(biāo)號(hào)，它表示v0到該點(diǎn)的最短距離的上界，或就是v0到該點(diǎn)的最短距離。實(shí)際上每一步都通過(guò)把至少一個(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)過(guò)|V(G)|-1步就可完成。步驟：記l(v)為v0到v的距離。(1) l(

8、v0)=0,l(v)=,(vv0);S0=v0,i=0。(2)對(duì)vSi,minl(v),l(vi)+w(viv)代替l(v);這樣找到點(diǎn)vi+1使得l(v)取最小值，v(i+1)(Si的余集)。令S(i+1)=Si+v(i+1)。i=|V(G)|-1時(shí)停止，否則，i+1,轉(zhuǎn)到(2)。實(shí)例：CMCM94A公路選址問(wèn)題。3. 2求最小生成樹(shù)1 .克羅斯克爾(Kruskal)算法(1956年)，俗稱“避圈法”背景：筑路選線問(wèn)題欲修筑連接n個(gè)城市的鐵路，已知i城與j城之間的鐵路造價(jià)為Cij。設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。分析：選線問(wèn)題的數(shù)學(xué)模型是在連通加權(quán)圖上求權(quán)最小的連通生成子圖。顯然，權(quán)最小的連通

9、生成子圖是一個(gè)生成樹(shù)，即求取連通加權(quán)圖上的權(quán)最小的生成樹(shù)，這就歸結(jié)為最小生成樹(shù)問(wèn)題。這個(gè)問(wèn)題可由克羅斯克爾(Kruskal)算法解決。思路：從“邊”著手選最小生成樹(shù)。步驟：設(shè)G為由m個(gè)節(jié)點(diǎn)組成的連通賦權(quán)圖。(1)先把G中所有的邊按權(quán)值大小由小到大重新排列，并取權(quán)最小的一條邊為樹(shù)T中的邊。即選e1E,使得w(e1)=min。(2)從剩下的邊中按(1)中的排列取下一條邊。若該邊與前面已取進(jìn)T中的邊構(gòu)成一個(gè)回路，則舍棄該邊，否則也把它取進(jìn)T中。若e1,e2,，ei已經(jīng)選好，則從E-e1,e2,，ei中選取ei+1,使得Ge1,e2,，ei,ei+1中無(wú)圈，且w(ei+1)=min。(3)重復(fù)步驟(2

10、),直到T中有m1條邊為止。則T為G的最小生成樹(shù)。該算法的復(fù)雜度為O(eloge),其中e是圖G中的邊數(shù)。2 .普萊姆(Prim)算法思路：從點(diǎn)入手來(lái)選邊步驟：(1)在圖G中任取一個(gè)節(jié)點(diǎn)vi1,并放入T中。(2)令S=V(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(nA2)，其中n為圖G的節(jié)點(diǎn)數(shù)。3 .1975年管梅谷提出的“破圈法”3.3Stein

11、er生成樹(shù)實(shí)際背景：在已有網(wǎng)絡(luò)上選擇連通幾個(gè)城市的最廉價(jià)交通或通訊網(wǎng)。數(shù)學(xué)模型：從已知的加權(quán)連通圖上求取最小的樹(shù)狀子圖，使此樹(shù)包含指定的頂點(diǎn)子集。第一個(gè)的邊長(zhǎng)為J3,第二個(gè)的邊長(zhǎng)為1,總費(fèi)用第二個(gè)更少。分析：與傳統(tǒng)的最小生成樹(shù)相比，這里可以引入若干“虛擬站”并構(gòu)造一個(gè)新的Steiner樹(shù)，這樣可以降低由一組站生成的傳統(tǒng)的最小生成樹(shù)所需的費(fèi)用(降低的費(fèi)用大概為13.4%)。而且為構(gòu)造一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)的費(fèi)用，最低的Steiner樹(shù)決不需要多于(n2)個(gè)虛設(shè)站。當(dāng)然，有時(shí)最小Steiner生成樹(shù)與最小生成樹(shù)相同。尋求最小Steiner生成樹(shù)的算法有Melzak算法(1961年)，但是這是一個(gè)指數(shù)

12、時(shí)間的算法，現(xiàn)在沒(méi)有多項(xiàng)式時(shí)間的算法，換句話說(shuō)它是一個(gè)NP問(wèn)題。而且，這里的要求是用直折線代替歐氏直線距離，因而不能利用直接的算法。所以在解決這樣的問(wèn)題的時(shí)候，為減少運(yùn)算的時(shí)間，理論上的分析是必要的：比如樹(shù)的長(zhǎng)度的下界，Steiner樹(shù)的存在性，虛設(shè)站的位置等等。常用的算法還包括窮舉法、模擬退火法等。Melzak算法：其基礎(chǔ)是3點(diǎn)steiner樹(shù)，即3點(diǎn)Fermat問(wèn)題的幾何作圖法。參考2,Page375。模擬退火法原理：模擬退火法(Simulatedannealing,SA)是模擬熱力學(xué)中經(jīng)典粒子系統(tǒng)的降溫過(guò)程，來(lái)求解極值問(wèn)題。當(dāng)孤立粒子系統(tǒng)的溫度以足夠慢的速度下降時(shí)，系統(tǒng)近似處于熱力學(xué)平衡

13、狀態(tài)，最后系統(tǒng)將達(dá)到本身的最低能量狀態(tài)，即基態(tài)，這相當(dāng)于能量函數(shù)的全局極小點(diǎn)。其步驟如下(也稱為Metropolis過(guò)程）:(1)給定初始溫度To,及初始點(diǎn)，計(jì)算該點(diǎn)的函數(shù)值f(x)。(2)隨機(jī)產(chǎn)生擾動(dòng)Ax,得到新點(diǎn)x'=x+A,x計(jì)算新點(diǎn)函數(shù)值f(x'及,函數(shù)值差A(yù)f=f(x-f(X)。(3)若AfW,0則接受新點(diǎn)，作為下一次模擬的初始點(diǎn)；(4)若Af>0,則計(jì)算新點(diǎn)接受概率："(一KT：產(chǎn)生0,1區(qū)間上均勻分布的偽隨機(jī)數(shù)r,rC0,1,如果p(Af)牙則接受新點(diǎn)作為下一次模擬的初始點(diǎn)；否則放棄新點(diǎn)，仍取原來(lái)的點(diǎn)作為下一次模擬的初始點(diǎn)。模擬退火法實(shí)例：1 .M

14、CM91B(通訊網(wǎng)絡(luò)中的極小生成樹(shù))是一個(gè)求STEINER生成樹(shù)問(wèn)題，參見(jiàn)工科數(shù)學(xué)專輯Page：7078。2、CMCM97A題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è)問(wèn)題變成組合優(yōu)化模型。這個(gè)問(wèn)題算法的狀態(tài)調(diào)整規(guī)則是：每次從7個(gè)自變量中隨機(jī)選取1-4個(gè)，讓選取的自變量隨機(jī)移動(dòng)，考慮選取的自變量在兩個(gè)方向移動(dòng)組合，從中選取最佳的作為候選者，自變量移動(dòng)的距離隨著溫度的降

15、低而減少，為避免陷入局部極小，可以從多個(gè)隨機(jī)選取的初始值開(kāi)始計(jì)算，算法的其它步驟同上。3、CMCM98B題98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題水災(zāi)巡視問(wèn)題”，是一個(gè)推銷員問(wèn)題，本題有53個(gè)點(diǎn)，所有可能性大約為exp(53)，目前沒(méi)有好方法求出精確解，既然求不出精確解，我們使用模擬退火法求出一個(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:隨

16、機(jī)確定將選定的路線反轉(zhuǎn)或移動(dòng)，即兩種調(diào)整方式：反轉(zhuǎn)、移動(dòng)。步6:計(jì)算代價(jià)D,即調(diào)整前后的總路程的長(zhǎng)度之差步7:按照如下規(guī)則確定是否做調(diào)整：如果D<0,則調(diào)整如果D>0,則按照EXP(-D/T)的概率進(jìn)行調(diào)整步8:T*0.9->T,降溫3.4Euler回路設(shè)G是一個(gè)圖，若存在這樣一條回路，使它經(jīng)過(guò)圖中的每條邊且只經(jīng)過(guò)一次又回到起始節(jié)點(diǎn)，就稱這樣的回路為Euler回路。背景：哥尼斯堡七橋問(wèn)題定理：對(duì)連通圖G,下列條件是相互等價(jià)的：(1) G是Euler圖；(2) G的每個(gè)節(jié)點(diǎn)的度數(shù)都是偶數(shù)；(3) G的邊集可以分解為若干個(gè)回路的并。對(duì)有向圖，出度=入度。算法：弗羅萊(Fleury

17、)算法(1921)(1)任名v0V(G),R=v0(2)設(shè)路R=v0e1v1e2v2eivi已選定，則從E(G)e1,e2,ei中選邊ei+1,且滿足：ei+1與vi相連；除非已無(wú)選擇，ei+1不要選E(Gi)=E(G)e1,e2,ei中的橋(注：橋，去掉之后圖不連通)(3)重復(fù)(2),直到不能再選為止實(shí)例：MCM90B鏟雪問(wèn)題中單車道單車掃雪一地圖是Euler圖的情形。說(shuō)明：如果圖G不是Euler圖，也就是說(shuō)不存在Euler回路，這時(shí)候求解就比較困難。求解前需要做一些處理，添加一個(gè)邊子集E1,E1+G=G1構(gòu)成一個(gè)Euler圖，然后再尋找Euler回路。注意圖G不是Euler圖時(shí)，必有偶數(shù)個(gè)

18、奇數(shù)度的節(jié)點(diǎn)，可以給這些節(jié)點(diǎn)兩兩配對(duì)，求兩點(diǎn)間的最短路，將這些最短路畫(huà)在一起構(gòu)成附加邊子集E1。這里的困難在于：奇數(shù)度的節(jié)點(diǎn)較多時(shí)，配對(duì)方案也多。3.5網(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),0wf(e)wc(e)；(c2)任名VvV(G)s,t,£f(e)-£f(e)=0;其中a(v)是以v為頭的邊集(流

19、進(jìn))，b(v)ev)e：=|.：(v)是以v為尾的邊集(流出)，即除起點(diǎn)和終點(diǎn)外，各節(jié)點(diǎn)流入量總和等于流出量總和。稱f(e)為流函數(shù)，稱F=Zf(e)-Zf(e)eq,(t)e：=|.；(t)為流量。我們的目標(biāo)是尋找一個(gè)流函數(shù)f,使其流量最大。1956年，福特(Ford)和福爾克遜(Fulkerson)提出了求最大流的算法。最大流最小割定理：流過(guò)網(wǎng)絡(luò)的最大流量等于最小割集的容量。2F算法：(1)對(duì)每邊e,選f(e)=0;(2)標(biāo)志頂s,其它頂未標(biāo)志；(3)選可“向前標(biāo)志”或可“向后標(biāo)志”的頂vo若無(wú)此種頂可選時(shí)，停止，現(xiàn)流函數(shù)即為最大流；若有此種頂可選時(shí)，則得到新的標(biāo)志頂v及標(biāo)志邊e。若v=t

20、,則轉(zhuǎn)(4);否則轉(zhuǎn)(3)。(4)設(shè)已得標(biāo)志之軌為(此軌為無(wú)向的)se1v1e2V2ett,從t開(kāi)始沿此軌逆行，令v=msinnV(ei)>若ei是前進(jìn)邊，即在有向圖中ei=vi1vi(s=v0,t=vl),則f(ei)=f(ei)+;若ei是后退邊，即在有向圖中ei=vivi1,則f(ei)=f(ei)一;轉(zhuǎn)(2)。向前和向后標(biāo)志的含義如下：若e=uv,u已有標(biāo)志，v沒(méi)有標(biāo)志，且c(e)>f(e),則稱通過(guò)邊e可以向前標(biāo)志頂點(diǎn)v,且規(guī)定(e)=c(e)f(e),得到標(biāo)志邊e。若e=vu,u已有標(biāo)志，v沒(méi)有標(biāo)志，且f(e)>0,則稱通過(guò)邊e可以向后標(biāo)志頂v,規(guī)定(e)=f(e

21、),且得到標(biāo)志邊e。(e)的含義是邊e上可以增載的上界。說(shuō)明：1 .如果每邊之容量c(e)都是有理數(shù)，則2F算法在有限步之內(nèi)可以求得最大流。2 .容量有上下界的網(wǎng)絡(luò)，需要構(gòu)造附加網(wǎng)絡(luò)。3 .6最小費(fèi)用一一最大流問(wèn)題這是在上述討論的基礎(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)輸問(wèn)題，如CMCM200

22、0B鋼管的采購(gòu)和運(yùn)輸問(wèn)題。說(shuō)明：1 .這里的介紹只是圖論中的一部分內(nèi)容，更多的需要我們進(jìn)一步學(xué)習(xí)。2 .算法都是描述性的，有些可以找到現(xiàn)成的程序，但是最好是自己實(shí)現(xiàn)。3 .這里的例子只是解決問(wèn)題的一種方法，不是唯一的方法。4 .注意實(shí)際應(yīng)用中直接利用所給算法解決問(wèn)題的情況很少，通常只是解決問(wèn)題的一部分，而且需要建立模型，把實(shí)際問(wèn)題用圖論術(shù)語(yǔ)描述出來(lái)。所以要善于利用這里的工具。其它方面的應(yīng)用，如工序問(wèn)題，最大獨(dú)立集，最小覆蓋集，郵遞員問(wèn)題，規(guī)劃審核技術(shù)，關(guān)鍵軌道方法，可靠通信網(wǎng)絡(luò)的構(gòu)造問(wèn)題，班級(jí)人員分配等等。3.7工序問(wèn)題統(tǒng)籌方法是組織生產(chǎn)計(jì)劃的方法，它用網(wǎng)絡(luò)圖表達(dá)生產(chǎn)和工程的進(jìn)度，計(jì)算各項(xiàng)工序

23、的有關(guān)時(shí)間參數(shù)。一項(xiàng)工程總是由許多相互獨(dú)立的工序組成的，各道工序之間有一定的先后次序。完成每道工序需要的時(shí)間（不妨設(shè)單位為小時(shí)）稱為工序的長(zhǎng)度。因此我們可以用一個(gè)各條邊有方向的圖（稱為有向圖）表示各項(xiàng)工序之間的互相依賴關(guān)系。以一條有向變來(lái)表示一道工序，有向邊的權(quán)即為此工序的長(zhǎng)度，有向邊的起點(diǎn)和終點(diǎn)分別表示相應(yīng)工序的開(kāi)工和完工，稱為事項(xiàng)，前接工序和完工事項(xiàng)即為后續(xù)工序和開(kāi)工事項(xiàng)。實(shí)例：上海MCM91B四、網(wǎng)絡(luò)規(guī)劃的應(yīng)用1.最小生成樹(shù)網(wǎng)絡(luò)規(guī)劃例1例1.求下圖的一個(gè)最小生成樹(shù)。VD解：首先取Gi=(Vi,Ei),Vi=vo,Ei=其次，一端屬于Vi,一端不屬于Vi的最短邊是v°vi,所以有

24、G2=(V2,E2),V2=V0,Vi,E2=V0Vi?，F(xiàn)在，一端屬于V2,一端不屬于V2的最短邊是ViV3,所以有G3=(V3,E3),V3=V0,Vi,V3,E3=VoVi,ViV3。類似做下去，最后得最小生成樹(shù)的邊為：V0Vi,ViV3,V2V3,V2V5,V5V6,V4V6。2.存儲(chǔ)糧食模型一一網(wǎng)絡(luò)規(guī)劃例2例2.某鄉(xiāng)有七個(gè)村Ai,A2,，A7,需儲(chǔ)存糧食數(shù)量分別為50,75,62,40,i00,80,35噸。各村之間有公路連通，如圖?，F(xiàn)要選擇某村建立倉(cāng)庫(kù)儲(chǔ)存所有糧食，問(wèn)應(yīng)選擇何處最好？解：圖上連結(jié)兩村的邊所注的數(shù)字表示該段公路的千米數(shù)。我們的目的是選擇倉(cāng)庫(kù)的位置使運(yùn)糧的噸千米數(shù)最小。首

25、先比較Ai和A2兩處。在比較這兩個(gè)村莊時(shí)，因?yàn)閭}(cāng)庫(kù)無(wú)論建在Ai或A2,其他各村的糧食都要先運(yùn)到A2,所以我們可認(rèn)為除Ai外各村的糧食都集中在A2,共357噸?，F(xiàn)在事情很明顯，倉(cāng)庫(kù)建在A2時(shí)需把50噸糧食運(yùn)3千米到A2,建在Ai時(shí)需把357噸糧食運(yùn)3千米到Ai,所以A2較Ai好。以后我們不再考慮Ai,因此可把Ai的糧食移到A2以簡(jiǎn)化問(wèn)題。同理A5也不必考慮，它的糧食可集中到A4?？紤]其他五個(gè)村。我們猜想現(xiàn)在糧食數(shù)量大的村莊可能是個(gè)好主意。假定選擇A4,我們考慮A6是否會(huì)更好：A2、A7的糧食少運(yùn)4千米，而A3、A4的糧食多運(yùn)4千S米，可見(jiàn)A4較A6好。同理可證A4比其他各村都好。因此倉(cāng)庫(kù)應(yīng)建在A

26、4。3.工作順序模型網(wǎng)絡(luò)規(guī)劃例3例3.某工廠的改造工程由下列7道工序組成：A:拆遷；B:工程設(shè)計(jì)；C:土建工程設(shè)計(jì)，前接工序?yàn)锽;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è)工程的開(kāi)工，t表示完工。有時(shí)，為了表示工序之間的順序關(guān)系，需要引入虛工序。注意，用來(lái)表示工程進(jìn)度的有向圖是不允許有回路的。現(xiàn)在我們研究網(wǎng)絡(luò)圖的各種時(shí)間參數(shù)。考慮圖3.5表示的網(wǎng)絡(luò)，我們把各事項(xiàng)(即圖的頂點(diǎn))編號(hào)，一般要求每一工序的開(kāi)工事項(xiàng)(即箭尾)的編號(hào)少于完工事項(xiàng)的編號(hào)(即箭頭)。每條有向邊旁所標(biāo)數(shù)

27、字為相應(yīng)工序的長(zhǎng)度。t e (k),例如圖3.5中，事項(xiàng)4的最早時(shí)某一工序A的最早開(kāi)工時(shí)間te(A),表示該工序最早可在整個(gè)工程開(kāi)工后te(A)小時(shí)開(kāi)工，這時(shí)間僅與該工序的開(kāi)工事項(xiàng)有關(guān)，所以也可以說(shuō)某一事項(xiàng)的最早時(shí)間間是9(即工序1->4和2->4都完成的時(shí)間)。因而有下列遞推公式-0,1為整個(gè)工程開(kāi)工事項(xiàng)*£/無(wú)1Mmax斗用上：讓三/'kj-5ik表示起點(diǎn)為i,終點(diǎn)為k的有向邊。整個(gè)工程完工事項(xiàng)的最早時(shí)間，就是全工程完工的最短時(shí)間，稱為總工期，記為Te。某一工序的最遲完工時(shí)間(或該工序完工事項(xiàng)的最遲時(shí)間)tE(k),是在不誤總工期的條件下，該工序最遲應(yīng)在整個(gè)工

28、程開(kāi)工后tl(A)小時(shí)完成。因此/月'=方,并為整個(gè)工程完工事項(xiàng)，工面=看-max；?；-“十%,:同£)實(shí)際上，te(k)就是由事項(xiàng)1到事項(xiàng)k的最長(zhǎng)路的長(zhǎng)度。tl(k)就是Te減去k到n的最長(zhǎng)路的長(zhǎng)度。因而(2)的第二式也可寫(xiě)成工序j的總時(shí)差定義為跖"向即不誤總工期的條件下該工序的開(kāi)工時(shí)間的機(jī)動(dòng)時(shí)間，即可延遲開(kāi)工的時(shí)間；而工序ij的自由時(shí)差定義為出"r曲一峰即在不誤下道工序最早開(kāi)工時(shí)間的前提下，該工序開(kāi)工時(shí)間的機(jī)動(dòng)時(shí)間。從事項(xiàng)1到事項(xiàng)n的一條最長(zhǎng)路稱為網(wǎng)絡(luò)圖的一條關(guān)鍵路，顯然在關(guān)鍵路上的每一事項(xiàng)k滿足tl（k尸te（k）,關(guān)鍵路上每一工序的總時(shí)差為0,反

29、之亦然。顯然，若關(guān)鍵路上工序能提前完成，整個(gè)工程才有可能提前完成；若關(guān)鍵路上工序未能按時(shí)完成，整個(gè)工程必然不能按期完成。求總工期和關(guān)鍵路的方法如下：首先對(duì)所有te（i）置初始值零，然后利用公式（1）進(jìn)行迭代，直到所有的tE（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)）。3(3)2一.Ford和Fulkerson迭加算法.基本思路：把各條弧上單位流量的費(fèi)用看成某種長(zhǎng)度，用求解最短路問(wèn)題的方法確定一條自V1至Vn的最短

30、路；在將這條最短路彳為可擴(kuò)充路，用求解最大流問(wèn)題的方法將其上的流量增至最大可能值；而這條最短路上的流量增加后，其上各條弧的單位流量的費(fèi)用要重新確定，如此多次迭代，最終得到最小費(fèi)用最大流.迭加算法：設(shè)圖中雙線所示路徑為最短路徑，費(fèi)用有向圖為W（fij）.1）給定目標(biāo)流量F或8,給定最小費(fèi)用的初始可行流fij=02）若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,

31、在圖（b）中找到最小費(fèi)用有向路，修改圖（a）中的可行流，8=min4,3,5=3,得圖（c）,再做出（c）的調(diào)整容量圖，再構(gòu)造相應(yīng)的新的最小費(fèi)用有向路得圖（d）,修改圖（c）中的可行流，8=min1,1,2,2=1,得圖（e）,以此類推，一直得到圖（h）,在圖（h）中以無(wú)最小費(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)中的

32、負(fù)費(fèi)用有向圖C(Floyd算法),若沒(méi)有則停止,否則轉(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,見(jiàn)圖(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附錄一：Ford和Fulkerson迭加算法求網(wǎng)絡(luò)的最小費(fèi)用最大流問(wèn)題的C語(yǔ)言程序/*Ford和Fulkerson迭加算法*/#include"stdio.h"

33、voidmain()inta,b,i,j,k,p,n,B1010,C1010,D1010,P101010;printf("pleaseinputn:n");scanf("%d",&n);printf("pleaseinputC%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)Bijfor(i=0;i<=n;i+)for(

34、j=0;j<=n;j+)Dij=Bij;for(k=0;k<=n;k+)Pijk=0;if(Dij<100)/注：100表示Vi到Vj之間無(wú)可行路Piji=1;Pijj=1;for(k=0;k<=n;k+)for(i=0;i<=n;i+)for(j=0;j<=n;j+)if(Dik+Dkj<Dij)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+)pri

35、ntf("%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(Dij<100)Pi皿i=1;Pi皿=1;for(k=0;k<=n;k+)for(i=0;i<=n;i+)for(j=0;j<=n;j+)if(Dik

36、+Dkj<Dij)Dij=Dik+Dkj;for(p=0;p<=n;p+)Pijp=Pikp|Pk皿p;調(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

37、=0;i<=n;i+)for(j=0;j<=n;j+)Dij=BiD：for(k=0;k<=n;k+)PiDk=0;if(Dij<100)for(k=0;k<=n;k+)for(i=0;i<=n;i+)for(j=0;j<=n;j+)if(Dik+DkD<DiD)Dij=Dik+DkD：for(p=0;p<=n;p+)PiDp=Pikp|PkDp;調(diào)用FLOYD算法printf("D%d%d:n",n,n);for(i=0;i<=n;i+)for(j=0;j<=n;j+)printf("%7d&qu

38、ot;,Dij);printf("n");由表D中的數(shù)值確定VO到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=BiD：for(k=0;k<=n;k+)Pijk=0;if(Dij<100)Piji=1;Pijj=1;for(k=0;k<=n;k+)for(i=0;i<=n;i+)for(j=0;j<=n;j+)if(Dik+Dkj<Di

39、j)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)有無(wú)V0到V5的新最短路運(yùn)行結(jié)果:pleaseinputn:5pleaseinputC55,B55:0,04,15,30,1000,1000,1000,1000,01,13,30,1000,1000,1000,1000,00,1002,4

40、0,1000,1000,1000,1000,00,1005,20,1000,1000,1001,10,02,40,1000,1000,1000,1000,1000,0D55:012466100013551001000547100100100010021001001001031001001001001000a=3,b=18D55:012769100016581001000547100100100010021001001001031001001001001000a=4,b=27D55:010031007111000100100100100100100010048100100100010021001

41、00100100041001001001001000a=5,b=38D55:0100310010010010001001001001001001000100100100100100100010021001001001001000/注：100表示Vi到Vj之間無(wú)可行路附錄二：破圈法求網(wǎng)絡(luò)的最小費(fèi)用最大流問(wèn)題的C語(yǔ)言程序/*圈算法*/#include"stdio.h"intmin(intx,inty)if(x<y)return(x);elsereturn(y);voidmain()inta=0,b=0,i,j,k,p,n,t,A1010,P1010,B1010,C1010,D1010;printf("pleaseinputn:n");scanf("%d",&n);printf("pleaseinputC%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)Bijfor(i=0;i<=n;i+)for(j=0;j<=n;j+)