第三講最大流與最小費用流

第三講最大流與最小費用流㎡二、最大流與最小割圖212大家應(yīng)該也有點累了，稍作休息大家有疑問的，可以詢問和交流例2:求圖3中網(wǎng)絡(luò)得最大流。圖3上機實驗三、最小費用最大流圖5上機練習(xí)程序?qū)崿F(xiàn)最小費用最大流思考題四個人:張三、李四、王五、趙六,四種樂器:小提琴、大提琴、鋼琴、吉她。已知四人得擅長如下:張三擅長拉大提琴與彈鋼琴;李四擅長拉小提琴、大提琴與吉她;王五擅長拉小提琴、大提琴;趙六只會彈吉她。今假設(shè)四人同同臺演出,每人各奏一種樂器,問四人同時各演奏一種樂器時所有可能得方案,試把此問題化為最大流問題。運輸網(wǎng)絡(luò)得用途不限于解決運輸問題。例如求一個二部圖G=〈X,E,Y〉得最大匹配問題,可轉(zhuǎn)化為運輸網(wǎng)絡(luò)求解。方法就是把X得元素都瞧作源點,Y得元素都瞧

作阱點,邊得方向都就是從源點指向阱點,再用上述方法,虛設(shè)一個源點a與一個阱點z,并設(shè)所有邊得權(quán)均為1。對所得得圖求得最大流得值就就是最大匹配得邊數(shù),最大流通過得屬于E得邊集,就就是最大匹配。最大流問題得應(yīng)用1、最大匹配問題⑴二部圖(也叫二分圖)圖G=(V,E),若V=X∪Y且X∩Y=ф,使得E中每一條邊得兩個端點必有一個屬于X,另一個屬于Y,則稱G為二部圖。記G=(X,Y,E),或G=(X,E,Y)。2、匹配:對給定得二部圖G=(X,Y,E),若有M?E,且M中任意兩條邊都沒有公共端點,則稱M為G得一個匹配(也稱對集)。既滿足:一個人只多做一件工作,每件工作只多由一人來做。即為工作集與工人集之間得一個匹配。3、最大匹配問題:

表示G中所有得匹配集,即

=｛M|M為G得匹配集｝|M|表示M得邊數(shù),若存在M0使對任意得M∈

,有則稱M0就是G得最大匹配。注:G中最大匹配方案可能不唯一。2。多端網(wǎng)絡(luò)問題:例6設(shè)有5位待業(yè)者,5項工作,她們各自能勝任工作得情況如圖所示,要求設(shè)計一個就業(yè)方案,使盡量多得人能就業(yè)。其中表示工人。表示工作。二部圖中最大匹配問題,可以轉(zhuǎn)化為最大流問題求解。在二部圖中增加兩個新點分別作為發(fā)點,收點。并用有向邊把它們與原二部圖中頂點相連,令全部邊上得容量均為1。當(dāng)網(wǎng)絡(luò)流達到最大時,如果上得流量為1,就讓作工作,此即為最大匹配方案。第一次標(biāo)號。調(diào)整第二次標(biāo)號。再調(diào)整。第三次標(biāo)號。調(diào)整。第四次標(biāo)號。調(diào)整第五次標(biāo)號。標(biāo)號過程已無法再繼續(xù)。流量為1得化彩線。工人分別作故最多安排四個人工作。例7現(xiàn)有5批貨物,每批只需一條船裝運,要由,所在地域運往,,地域。至于貨物從,運向,,三點何處都一樣,每批貨物出發(fā)日期如表1,航船行所需天數(shù)如表2。船只空載與重載時航行時間相同。要求制定一個計劃,在半個月內(nèi)用最少得船只把5批貨物運過去。地點510

/

/121,8地點232112表1(出發(fā)日期)表2(航行天數(shù))解:設(shè),分別表示每項運輸任務(wù)得出發(fā)日期及到達得日期(i=1,2,3,4,5)則由表1與表2知:任務(wù)路線①57②1013③1213④13⑤810地點232112表2(航行天數(shù))地點510

/

/121,8表1(出發(fā)日期)任務(wù)路線①57②1013③1213④13⑤810要想用較少得船只在1～15天內(nèi)完成任務(wù),關(guān)鍵就是自上一任務(wù)到達得時間加上返回得時間能否趕上下一個任務(wù)出發(fā)得時間。若能,則一只船就能完成兩批貨物得運輸任務(wù)。以下試運行:任務(wù)路線①57②1013③1213④13⑤810①5號①7號8號回⑤10號地點232112表8-6(航行天數(shù))⑤8號12號回③13號③14號回任務(wù)路線①57②1013③1213④13⑤810②10