數(shù)學(xué)模型第七章457.doc

第七章 圖論模型 7.4 網(wǎng) 絡(luò) 最 大 流7.4.1引例v1v6v2v3v4v51048535631117圖7.4.1如圖有一連接某產(chǎn)品的產(chǎn)地v1與銷地v6的交通網(wǎng).每條弧表示運(yùn)輸線路.弧旁的數(shù)字表示該運(yùn)輸線的最大通過能力.要求制定一個運(yùn)輸計劃使從v1到v6的產(chǎn)品輸送量最大.這就是一個網(wǎng)絡(luò)最大流問題.7.4.2基本概念設(shè)有一有向圖D=(V,A), 發(fā)點是指定的起始點 vsV; 收點是指定的終止點 vtV. 對每一弧(vi,vj)A , 規(guī)定一個非負(fù)數(shù)Cij表示流量的上限稱為容量; 指定了發(fā)點、收點和各弧容量的有向圖D稱為網(wǎng)絡(luò); 所謂網(wǎng)絡(luò)上的一個流是指定義在弧集A上的一個實函f = f(vi,vj). fij =f(vi,vj) 稱為從vi到vj的流量.若f滿足以下2個條件者，則稱f為可行流. (1) 容量限制 對每一條弧(vi,vj)A, 0fijCij(2) 平衡條件 (i)對每個中間點viA，流入量等于流出量. （流出vi） (流入vi)(ii) 發(fā)點凈流出量等于收點凈流入量 (稱為總流量)最大流問題就是求一個可行流f，使達(dá)到最大.網(wǎng)絡(luò)最大流問題的線性規(guī)劃模型：對可行流f，若fij=Cij，則稱(vi,vj)為飽和弧;對可行流f，若fij=0，則稱(vi,vj)為零弧; 根據(jù)原網(wǎng)絡(luò)的每條弧變作一條順向弧和一條逆向弧，且把順向弧的容量定義為，逆向弧的容量定義為，這樣得到的網(wǎng)絡(luò)稱為原網(wǎng)絡(luò)D=(V,A,C)關(guān)于流f的增量網(wǎng)絡(luò)，記為.例7.4.1圖7.4.2(b) 就是圖7.4.2(a) 的一個增量網(wǎng)絡(luò).3, 05,14, 14,32, 2st240111333st0圖7.4.2(a)(b)7.4.3求網(wǎng)絡(luò)最大流的方法（1） 增量網(wǎng)絡(luò)與原網(wǎng)絡(luò)的關(guān)系N(f)的順向弧的數(shù)表示原網(wǎng)絡(luò)對應(yīng)弧上最大可增加的流量.N(f)的逆向弧的數(shù)表示原網(wǎng)絡(luò)對應(yīng)弧上最大可減少的流量.若在N(f)中能找到從s到t的一條路P，且每條弧容量為正數(shù)，則稱P為f的增廣路.令：，則，稱為增廣量.對原網(wǎng)絡(luò)的流f作如下調(diào)整：, (7.4.1)則是新的可行流且，若N(f)中不存在增廣路，則對應(yīng)的流f已是最大流.（2） 步驟以零流f=0作初始可行流作增量網(wǎng)絡(luò)N(f)尋找增廣路P.若無，則結(jié)束.令按（7.4.1）式調(diào)整流量，得新流f.轉(zhuǎn)v1v2v3v43,04,05,02,04,0 (a)34 0504 0v1v2v3v4020圖7.4.3(b)例 求圖7.4.3(a)的網(wǎng)絡(luò)的最大流, 初始可行流零流=0, 對應(yīng)的增量網(wǎng)絡(luò)N(f)如圖7.4.3(b)所示. 得增廣路P:. v1v2v3v4,求得=4. v1v2v3v43,04,45,42,04,4(a)(b)v1v2v3v430 4140 4002圖7.4.4按(7.4.1)式調(diào)整流量，得新可行流f ,如圖7.4.4(a) 所示, 總流量V(f)=4,對應(yīng)的增量網(wǎng)絡(luò)N(f)如圖7.4.4(b)所示. 找得增廣路P:. v1v3v2v4,求得=2.v1v2v3v43,24,45,22,24,4(a)(b)v1v2v3v410 4320 4202圖7.4.5再按（7.4.1）式調(diào)整流量，得新可行流f” ,如圖7.4.5(a) 所示, 對應(yīng)的增量網(wǎng)絡(luò)N(f”如圖7.4.5(b)所示.沒有增廣路, f”已經(jīng)是最大流, V(f”)=6.7.4.4應(yīng)用實例-房產(chǎn)商的推銷策略某房產(chǎn)商現(xiàn)有6套房（用Xi表示）要出售，現(xiàn)來了7個買主（用Yj表示），分別看中了其中若干套房（如圖），假設(shè)每個買主至多只買1套房，求房產(chǎn)商使銷量最大的推銷策略。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6補(bǔ)充發(fā)點S和收點T，定義所有弧的容量都是1，得下圖，需要求S到T的最大流。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6ST可用運(yùn)籌學(xué)求解網(wǎng)絡(luò)最大流的軟件求解，就得房產(chǎn)商使銷量最大的推銷策略，下圖藍(lán)色粗弧都是飽和弧，其他弧是零弧。Y1Y2Y3Y4Y5Y6Y7X1X2X3X4X5X6ST即得房產(chǎn)商最佳的推銷策略是：即極力說服買主Y1去買X1, Y2去買X3, Y3去買X4, Y4去買X2, Y5去買X6. 這樣能賣出5套房。（當(dāng)然，此題最優(yōu)解是不唯一的）注：此題也可以轉(zhuǎn)化為指派問題，方法是先虛擬一套房X7，然后定義Cij，若Yi看中了Xj，則Cij=1，否則Cij=0，當(dāng)然Ci7=0，目標(biāo)最大化。應(yīng)用案例-BMZ公司的最大流問題1.背景 BMZ 公司是歐洲一家生產(chǎn)豪華汽車的制造商。它因為提供優(yōu)質(zhì)的服務(wù)而獲得很好的聲譽(yù)，保持這個聲譽(yù)一個很重要的秘訣就是它有著充裕的汽車配件供應(yīng)，從而能夠隨時供貨給公司眾多的經(jīng)銷商和授權(quán)維修店。 這些供應(yīng)件主要存放在公司的配送中心里，這樣一有需求就可以立即送貨?？?BMZ公司的供應(yīng)鏈的經(jīng)理)優(yōu)先考慮的是改進(jìn)這些配送中心的不足之處。 該公司在美國有幾個配送中心。但是，離洛杉機(jī)中心最近的一個配送中心卻坐落離洛杉機(jī) 1000 多英里的西雅圖。保證洛杉機(jī)中心良好的供應(yīng)是尤為重要的。因此，現(xiàn)在那里的供應(yīng)不斷減少的現(xiàn)狀成為了公司高層管理真正關(guān)心的問題。 大部分的汽車配件以及新車是在該公司坐落于德國的斯圖加特的總廠和新車一起生產(chǎn)的。也就是這家工廠向洛杉機(jī)中心供應(yīng)汽車配件。每月有超過 300000 立方英尺的配件需要運(yùn)到?，F(xiàn)在，下個月需要多得多的數(shù)量以補(bǔ)充正在減少的庫存。 2.問題 卡爾需要盡快制定一個方案，使得下個月從總廠運(yùn)送到洛杉機(jī)配送中心的供應(yīng)件盡可能多。他認(rèn)識到了這是個最大流的問題 一個使得從總廠運(yùn)送到洛杉機(jī)配送中心的配件流最大的問題。因為總廠生產(chǎn)的配件量遠(yuǎn)遠(yuǎn)要大于能夠運(yùn)送到配送中心的量，所以，可以運(yùn)送多少配件的限制條件就是公司配送網(wǎng)絡(luò)的容量。 這個配送網(wǎng)絡(luò)如下圖。在圖中，標(biāo)有 (ST) 和(LA)的節(jié)點分別代表斯圖加特的工廠和洛杉機(jī)的配送中心。由于工廠所在地有一個鐵路運(yùn)轉(zhuǎn)點，所以首先通過鐵路把配件運(yùn)輸?shù)綒W洲的三個港口：鹿特丹（RO）波爾圖（BO）和里斯本 (LI) ；然后通過船運(yùn)到美國的港口紐約（NY）或新奧爾良（NO）；最后用卡車送到洛杉機(jī)的配送中心。 3.模型描述 STLIBOORONYNOLA507040604050308070（弧旁的方括號里的數(shù)字代表該弧的容量：萬立方英尺）4.最優(yōu)方案從 到 運(yùn)輸量 容量 斯圖加特（ST）鹿特丹（RO）50 50 斯圖加特（ST）波爾圖（BO）70 70 斯圖加特（ST）里斯本(LI)30 40 鹿特丹（RO）紐約（NY）50 60 波爾圖（BO）紐約（NY）30 40 波爾圖（BO）新奧爾良(NO)40 50 里斯本(LI)新奧爾良(NO)30 30 紐約（NY）洛杉磯(LA)80 80 新奧爾良(NO)洛杉磯(LA)70 70 總運(yùn)輸量 150 7.5統(tǒng)籌方法統(tǒng)籌方法是一種研究如何對工程計劃進(jìn)行合理組織、統(tǒng)籌安排使其發(fā)揮最大效益的方法.常用工序流線圖對各工序的關(guān)系進(jìn)行描述.7.5.1. 工序流線圖工序流線圖是用于描述各工序的邏輯關(guān)系與工程進(jìn)度的一種有向網(wǎng)路圖.繪圖規(guī)則如下：（1）用箭號表示工序，箭號旁可用數(shù)字表示該工序所需時間;（2）用小圓表示事項（工序開工或完工的時刻）, 箭尾處為開工事項, 箭頭處為完工事項;（3）全部事項從小到大進(jìn)行編號，不得重復(fù);（4）任一工序的開工事項編號小于完工事項編號，如 ;（5）不同的工序不得使用兩個相同的相關(guān)事項，如圖7.5.1是不允許的;從而可用（i,j）表示開工事項編號為i, 完工事項編號為j的工序;（6）必要時可使用虛工序（無須實際執(zhí)行的工序，工時為0），用虛箭號 表示，如圖7.5.2所示;AB46圖7.5.1BA465圖7.5.2（7）一個工程只有一個始點與一個終點.例7.5.1 某工廠改建工程由下列6道工序構(gòu)成:A:拆舊廠房;B:工程設(shè)計;C:采購設(shè)備,緊前工序(緊接本工序之前的工序)是B;D:廠房土建, 緊前工序是A與B;E:設(shè)備安裝, 緊前工序是C與D;F:設(shè)備調(diào)試, 緊前工序是E.123456ABCDEF圖7.5.3本工程可用圖7.5.3的工序流線圖來描述作工序流線圖時我們要小心虛箭號的合理使用,否則容易出錯.例7.5.2 現(xiàn)有一工程：代號ABCDEFGH緊前工序ABBBC，DC，EF，G工序時間13162424作出圖7.5.4.圖7.5.4 請注意, 圖7.5.5的作法是錯的.圖7.5.5 這樣畫的話,工序D也變?yōu)楣ば騁的緊前工序了,與原題意不符.提醒:使用虛工序時盡量避免多個同向相連7.5.2工序流線圖的時間參數(shù)設(shè)工序流線圖中始點編號為1，終點編號為n.以下引進(jìn)幾個記號.TE總工期，等于圖中終點的最早完工時間，也等于終點的最遲完工時間;工序（i,j）的耗用工時;tE(k)事項k的最早時間，即以事項k為開工事項的工序的最早可以開工時間，也即它前面全部工序都已完工的時間.遞推公式為 (7.5.1)如圖7.5.6所示.若已算得tE(2)=3, tE(3)=2又知w24=2,w34=4從而按(7.5.1)式算得tE(4)=max3+2,2+4=6.tE(1)=0tE(2)=3tE(3)=2tE(4)=6圖7.5.6 tL(k)事項k的最遲時間，即以事項k為完工事項的工序的最遲必須完工時間（以不耽誤總工期而言）,遞推公式為 (7.5.2)如圖7.5.7所示.若已算得tL(8)=5, tL(9)=6又知w78=3,w79=2從而按(7.5.2)式算得tL(7)=min5-3,6-2=2.7tL(7)=2tL(8)=5tL(9)=6圖7.5.7R(i,j)-工序（i,j）的總時差（指不誤總工期條件下的最大機(jī)動時間）.定義 , (7.5.3) 如果，w45=3, 則R(i,j)=8-2-3=3ktEtL圖7.5.8 若圖不太復(fù)雜,則時間參數(shù)tE與tL可直接在圖上計算, 稱為圖算法. 把每個事項分為3部分，分別表示編號、最早時間和最遲時間,如圖7.5.8.先按編號從小到大計算tE(k)，再按編號從大到小算tL(k); 如圖7.5.9所示.圖7.5.97.5.3 關(guān)鍵路工序流線圖中按箭頭方向從始點到終點的一條順向通道稱為路;圖7.5.9中有四條路.路上各工序時間之和稱為路長;圖中最長的路稱為關(guān)鍵路; 關(guān)鍵路上的工序稱為關(guān)鍵工序.注意,每個工序流線圖都一定有關(guān)鍵路，關(guān)鍵路的長就是全工程的完工 的總工時; 關(guān)鍵路可能不是唯一的;要想工程提前完工，只有縮短關(guān)鍵工序的工時.故尋找工序流線圖的關(guān)鍵路,在工程項目的管理中,有十分重要的作用.我們可以用以下方法確定關(guān)鍵路. 由于關(guān)鍵路上的各工序都是不停留地一道緊接一道進(jìn)行.才能保證不誤總工期.從而關(guān)鍵路上各事項必滿足tL(k)=tE(k).故只須把圖中全部滿足此關(guān)系的事項連接起來就得關(guān)鍵路.在圖7.5.9中, 關(guān)鍵路為，總工期為41天.注：一道工序是關(guān)鍵工序的充要條件是總時差為0.再看一例：根據(jù)下列資料繪制網(wǎng)絡(luò)圖，計算各項時間參數(shù)，并確定關(guān)鍵路線. 工 序緊前工序工 時工 序緊前工序工 時AG , M3GB , C4BH4H-7C-7IA , L3DL3KF , I5EC5LB , C6FA , E5MC41023231128289182081720718186181851515411113711277100H , 7C , 7B , 4M , 4G , 4L , 6A , 3E , 5I , 3F , 5D , 3K , 5解：圖與參數(shù)為關(guān)鍵路線如圖中粗線所示?？偣て跒?8.7.7 匹配問題 設(shè)有X、Y、Z三家公司，各有一個職位空缺。三個求職者Alice, Bob, Charles希望得到一個職位。假設(shè)X公司雇傭Charles，Y公司雇傭Alice，Z公司雇傭Bob。我們可用圖7.7.1表示這一結(jié)果。圖 7.7.1XYZAliceBobChales二部圖(bipartite graph)：若一個圖G=(V, E)的頂點集V可分為兩個互不相交的子集V1和V2，且G中任何一條邊e的一個頂點屬于V1另一個頂點屬于V2，則稱G是一個二部圖(bipartite graph)。匹配：設(shè)，若M中任兩條邊都沒有公共頂點，則稱M是G的一個匹配。最大匹配：G中邊數(shù)最多的匹配。ABab婚姻介紹所需要為顧客（n位男士和n位女士）推薦合適的配偶。推薦是基于每個人的偏好，每個顧客都要給出他們對異性的優(yōu)先順序。障礙對：假設(shè)給男士a指定配偶女士A, 而給男士b指定配偶女士B, 但在a的心目中，B比A更好，而在B的心目中，a比b更好. 就是說，a和B更愿意配成一對，那么a和B稱為該匹配中的一個障礙對。（注意，在該匹配中，a和B并沒有配成一對）穩(wěn)定匹配(婚姻)：如果一個匹配中沒有障礙對，則稱該匹配是穩(wěn)定的。GS算法：（用于求穩(wěn)定匹配）(1962年，美國數(shù)學(xué)家戈爾（Gale）和夏普利（Shapley）就解決了)首先要給出男士對女士的偏好矩陣和女士對男士的偏好矩陣（用排序或評分）.在第一輪循環(huán)中, 每位男士向他最喜歡的女士求婚. 而每位女士則選擇向她求婚的男士中, 她最喜歡的一個男士作為暫時的配偶. 沒有人求婚的女士等待下一輪.在下一輪循環(huán)中, 已經(jīng)有暫時配偶的男士什么也不做. 每一個沒有配偶的男士再向他的偏好順序表里排在最前面而沒有拒絕過他的女士求婚. 而每位女士則選擇向她求婚的男士(包括原來的暫時配偶)中,她最喜歡的一位男士作為暫時的配偶. 如此循環(huán)，直到所有的男士都有配偶時, 算法結(jié)束.例 設(shè)男士a，b，c與女士A，B，C的偏好矩陣為順序abcABC一BAAbcb二ACBaac三CBCcba以下用 表示男士向女士求婚或女士暫時接納男士第1輪aBbA cAAb拒cBaC空第2輪a停b停cBAbBc拒aC空第3輪aAb停c停Ab拒aBcC空第4輪aCb停c停AbBcCa這就得到穩(wěn)定匹配ABCabc穩(wěn)定匹配是不是最滿意的匹配？把偏好排序換成評分，分值越大表示越偏好男士對女士評分女士對男士評分ABCABCa231a221b312b313c321c132ABCabc上面的穩(wěn)定匹配的總分S1=(3