第三講最大流與最小費(fèi)用流演示文稿當(dāng)前1頁(yè)，總共65頁(yè)。（優(yōu)選）第三講最大流與最小費(fèi)用流當(dāng)前2頁(yè)，總共65頁(yè)。當(dāng)前3頁(yè)，總共65頁(yè)。㎡當(dāng)前4頁(yè)，總共65頁(yè)。當(dāng)前5頁(yè)，總共65頁(yè)。當(dāng)前6頁(yè)，總共65頁(yè)。當(dāng)前7頁(yè)，總共65頁(yè)。二、最大流與最小割當(dāng)前8頁(yè)，總共65頁(yè)。圖2當(dāng)前9頁(yè)，總共65頁(yè)。當(dāng)前10頁(yè)，總共65頁(yè)。當(dāng)前11頁(yè)，總共65頁(yè)。當(dāng)前12頁(yè)，總共65頁(yè)。當(dāng)前13頁(yè)，總共65頁(yè)。當(dāng)前14頁(yè)，總共65頁(yè)。當(dāng)前15頁(yè)，總共65頁(yè)。當(dāng)前16頁(yè)，總共65頁(yè)。當(dāng)前17頁(yè)，總共65頁(yè)。當(dāng)前18頁(yè)，總共65頁(yè)。例2：求圖3中網(wǎng)絡(luò)的最大流。圖3當(dāng)前19頁(yè)，總共65頁(yè)。當(dāng)前20頁(yè)，總共65頁(yè)。當(dāng)前21頁(yè)，總共65頁(yè)。當(dāng)前22頁(yè)，總共65頁(yè)。當(dāng)前23頁(yè)，總共65頁(yè)。當(dāng)前24頁(yè)，總共65頁(yè)。當(dāng)前25頁(yè)，總共65頁(yè)。當(dāng)前26頁(yè)，總共65頁(yè)。當(dāng)前27頁(yè)，總共65頁(yè)。當(dāng)前28頁(yè)，總共65頁(yè)。當(dāng)前29頁(yè)，總共65頁(yè)。當(dāng)前30頁(yè)，總共65頁(yè)。上機(jī)實(shí)驗(yàn)當(dāng)前31頁(yè)，總共65頁(yè)。三、最小費(fèi)用最大流當(dāng)前32頁(yè)，總共65頁(yè)。當(dāng)前33頁(yè)，總共65頁(yè)。當(dāng)前34頁(yè)，總共65頁(yè)。圖5當(dāng)前35頁(yè)，總共65頁(yè)。當(dāng)前36頁(yè)，總共65頁(yè)。當(dāng)前37頁(yè)，總共65頁(yè)。當(dāng)前38頁(yè)，總共65頁(yè)。當(dāng)前39頁(yè)，總共65頁(yè)。當(dāng)前40頁(yè)，總共65頁(yè)。當(dāng)前41頁(yè)，總共65頁(yè)。上機(jī)練習(xí)程序?qū)崿F(xiàn)最小費(fèi)用最大流當(dāng)前42頁(yè)，總共65頁(yè)。思考題四個(gè)人：張三、李四、王五、趙六，四種樂(lè)器：小提琴、大提琴、鋼琴、吉他。已知四人的擅長(zhǎng)如下：張三擅長(zhǎng)拉大提琴和彈鋼琴；李四擅長(zhǎng)拉小提琴、大提琴和吉他；王五擅長(zhǎng)拉小提琴、大提琴；趙六只會(huì)彈吉他。今假設(shè)四人同同臺(tái)演出，每人各奏一種樂(lè)器，問(wèn)四人同時(shí)各演奏一種樂(lè)器時(shí)所有可能的方案，試把此問(wèn)題化為最大流問(wèn)題。當(dāng)前43頁(yè)，總共65頁(yè)。運(yùn)輸網(wǎng)絡(luò)的用途不限于解決運(yùn)輸問(wèn)題。例如求一個(gè)二部圖G=〈X,E,Y〉的最大匹配問(wèn)題,可轉(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ù),最大流通過(guò)的屬于E的邊集,就是最大匹配。最大流問(wèn)題的應(yīng)用當(dāng)前44頁(yè)，總共65頁(yè)。1.最大匹配問(wèn)題⑴二部圖（也叫二分圖）圖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）。當(dāng)前45頁(yè)，總共65頁(yè)。2．匹配：對(duì)給定的二部圖G=（X，Y，E），若有M?E，且M中任意兩條邊都沒(méi)有公共端點(diǎn)，則稱M為G的一個(gè)匹配（也稱對(duì)集）。既滿足：一個(gè)人只多做一件工作，每件工作只多由一人來(lái)做。即為工作集與工人集之間的一個(gè)匹配。當(dāng)前46頁(yè)，總共65頁(yè)。3．最大匹配問(wèn)題：

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

，有則稱M0是G的最大匹配。注：G中最大匹配方案可能不唯一。當(dāng)前47頁(yè)，總共65頁(yè)。2。多端網(wǎng)絡(luò)問(wèn)題：例6設(shè)有5位待業(yè)者，5項(xiàng)工作，他們各自能勝任工作的情況如圖所示，要求設(shè)計(jì)一個(gè)就業(yè)方案，使盡量多的人能就業(yè)。其中表示工人。表示工作。當(dāng)前48頁(yè)，總共65頁(yè)。二部圖中最大匹配問(wèn)題，可以轉(zhuǎn)化為最大流問(wèn)題求解。在二部圖中增加兩個(gè)新點(diǎn)分別作為發(fā)點(diǎn)，收點(diǎn)。并用有向邊把它們與原二部圖中頂點(diǎn)相連，令全部邊上的容量均為1。當(dāng)網(wǎng)絡(luò)流達(dá)到最大時(shí)，如果上的流量為1，就讓作工作，此即為最大匹配方案。當(dāng)前49頁(yè)，總共65頁(yè)。第一次標(biāo)號(hào)。調(diào)整當(dāng)前50頁(yè)，總共65頁(yè)。第二次標(biāo)號(hào)。再調(diào)整。當(dāng)前51頁(yè)，總共65頁(yè)。第三次標(biāo)號(hào)。當(dāng)前52頁(yè)，總共65頁(yè)。調(diào)整。當(dāng)前53頁(yè)，總共65頁(yè)。第四次標(biāo)號(hào)。當(dāng)前54頁(yè)，總共65頁(yè)。調(diào)整當(dāng)前55頁(yè)，總共65頁(yè)。第五次標(biāo)號(hào)。當(dāng)前56頁(yè)，總共65頁(yè)。當(dāng)前57頁(yè)，總共65頁(yè)。標(biāo)號(hào)過(guò)程已無(wú)法再繼續(xù)。流量為1的化彩線。當(dāng)前58頁(yè)，總共65頁(yè)。工人分別作故最多安排四個(gè)人工作。當(dāng)前59頁(yè)，總共65頁(yè)。例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)過(guò)去。地點(diǎn)510

/

/121，8地點(diǎn)232112表1（出發(fā)日期）表2（航行天數(shù)）當(dāng)前60頁(yè)，總共65頁(yè)。解：設(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ā)日期）當(dāng)前61頁(yè)，總共65頁(yè)。任務(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)行：當(dāng)前62頁(yè)，總共65頁(yè)。任務(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)回當(dāng)前63頁(yè)，總共65頁(yè)。任務(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)？一只船可行否？如何解決？當(dāng)前64頁(yè)，總共65頁(yè)。作一個(gè)二部圖，點(diǎn)集｛X｝和｛Y｝都表