第三講最大流與最小費(fèi)用流

第三講最大流與最小費(fèi)用流演示文稿現(xiàn)在是1頁\一共有65頁\編輯于星期一（優(yōu)選）第三講最大流與最小費(fèi)用流現(xiàn)在是2頁\一共有65頁\編輯于星期一現(xiàn)在是3頁\一共有65頁\編輯于星期一㎡現(xiàn)在是4頁\一共有65頁\編輯于星期一現(xiàn)在是5頁\一共有65頁\編輯于星期一現(xiàn)在是6頁\一共有65頁\編輯于星期一現(xiàn)在是7頁\一共有65頁\編輯于星期一二、最大流與最小割現(xiàn)在是8頁\一共有65頁\編輯于星期一圖2現(xiàn)在是9頁\一共有65頁\編輯于星期一現(xiàn)在是10頁\一共有65頁\編輯于星期一現(xiàn)在是11頁\一共有65頁\編輯于星期一現(xiàn)在是12頁\一共有65頁\編輯于星期一現(xiàn)在是13頁\一共有65頁\編輯于星期一現(xiàn)在是14頁\一共有65頁\編輯于星期一現(xiàn)在是15頁\一共有65頁\編輯于星期一現(xiàn)在是16頁\一共有65頁\編輯于星期一現(xiàn)在是17頁\一共有65頁\編輯于星期一現(xiàn)在是18頁\一共有65頁\編輯于星期一例2：求圖3中網(wǎng)絡(luò)的最大流。圖3現(xiàn)在是19頁\一共有65頁\編輯于星期一現(xiàn)在是20頁\一共有65頁\編輯于星期一現(xiàn)在是21頁\一共有65頁\編輯于星期一現(xiàn)在是22頁\一共有65頁\編輯于星期一現(xiàn)在是23頁\一共有65頁\編輯于星期一現(xiàn)在是24頁\一共有65頁\編輯于星期一現(xiàn)在是25頁\一共有65頁\編輯于星期一現(xiàn)在是26頁\一共有65頁\編輯于星期一現(xiàn)在是27頁\一共有65頁\編輯于星期一現(xiàn)在是28頁\一共有65頁\編輯于星期一現(xiàn)在是29頁\一共有65頁\編輯于星期一現(xiàn)在是30頁\一共有65頁\編輯于星期一上機(jī)實(shí)驗(yàn)現(xiàn)在是31頁\一共有65頁\編輯于星期一三、最小費(fèi)用最大流現(xiàn)在是32頁\一共有65頁\編輯于星期一現(xiàn)在是33頁\一共有65頁\編輯于星期一現(xiàn)在是34頁\一共有65頁\編輯于星期一圖5現(xiàn)在是35頁\一共有65頁\編輯于星期一現(xiàn)在是36頁\一共有65頁\編輯于星期一現(xiàn)在是37頁\一共有65頁\編輯于星期一現(xiàn)在是38頁\一共有65頁\編輯于星期一現(xiàn)在是39頁\一共有65頁\編輯于星期一現(xiàn)在是40頁\一共有65頁\編輯于星期一現(xiàn)在是41頁\一共有65頁\編輯于星期一上機(jī)練習(xí)程序?qū)崿F(xiàn)最小費(fèi)用最大流現(xiàn)在是42頁\一共有65頁\編輯于星期一思考題四個(gè)人：張三、李四、王五、趙六，四種樂器：小提琴、大提琴、鋼琴、吉他。已知四人的擅長(zhǎng)如下：張三擅長(zhǎng)拉大提琴和彈鋼琴；李四擅長(zhǎng)拉小提琴、大提琴和吉他；王五擅長(zhǎng)拉小提琴、大提琴；趙六只會(huì)彈吉他。今假設(shè)四人同同臺(tái)演出，每人各奏一種樂器，問四人同時(shí)各演奏一種樂器時(shí)所有可能的方案，試把此問題化為最大流問題?，F(xiàn)在是43頁\一共有65頁\編輯于星期一運(yùn)輸網(wǎng)絡(luò)的用途不限于解決運(yùn)輸問題。例如求一個(gè)二部圖G=〈X,E,Y〉的最大匹配問題,可轉(zhuǎn)化為運(yùn)輸網(wǎng)絡(luò)求解。方法是把X的元素都看作源點(diǎn),Y的元素都看

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

表示G中所有的匹配集，即=｛M|M為G的匹配集｝|M|表示M的邊數(shù)，若存在M0使對(duì)任意的M∈

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

/

/121，8地點(diǎn)232112表1（出發(fā)日期）表2（航行天數(shù)）現(xiàn)在是60頁\一共有65頁\編輯于星期一解：設(shè)，分別表示每項(xiàng)運(yùn)輸任務(wù)的出發(fā)日期及到達(dá)的日期（i=1，2，3，4，5）則由表1和表2知：任務(wù)路線①57②1013③1213④13⑤810地點(diǎn)232112表2（航行天數(shù)）地點(diǎn)510

/

/121，8表1（出發(fā)日期）現(xiàn)在是61頁\一共有65頁\編輯于星期一任務(wù)路線①57②1013③1213④13⑤810要想用較少的船只在1～15天內(nèi)完成任務(wù)，關(guān)鍵是自上一任務(wù)到達(dá)的時(shí)間加上返回的時(shí)間能否趕上下一個(gè)任務(wù)出發(fā)的時(shí)間。若能，則一只船就能完成兩批貨物的運(yùn)輸任務(wù)。以下試運(yùn)行：現(xiàn)在是62頁\一共有65頁\編輯于星期一任務(wù)路線①57②1013③1213④13⑤810①5號(hào)①7號(hào)8號(hào)回⑤10號(hào)地點(diǎn)232112表8-6（航行天數(shù)）⑤8號(hào)12號(hào)回③13號(hào)③14號(hào)回現(xiàn)在是63頁\一共有65頁\編輯于星期一任務(wù)路線①57②1013③1213④13⑤810②10號(hào)④3號(hào)地點(diǎn)232112表8-6（航行天數(shù)）④1號(hào)②13號(hào)④5號(hào)回共兩只船在13號(hào)以前就把5批貨物全部運(yùn)了出去。是否最優(yōu)？一只船可行否？如何解決？現(xiàn)在是64頁\一共有65頁\編輯于星期一作一個(gè)二