運(yùn)籌學(xué)課件ch10圖與網(wǎng)絡(luò)分析.ppt

《運(yùn)籌學(xué)課件ch10圖與網(wǎng)絡(luò)分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué)課件ch10圖與網(wǎng)絡(luò)分析.ppt（58頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第十章,圖與網(wǎng)絡(luò)分析 Graph & Network Analysis,章節(jié)大綱,圖的基本概念 樹(shù)與最小支撐樹(shù)的應(yīng)用 最短路問(wèn)題 網(wǎng)絡(luò)最大流問(wèn)題 最小費(fèi)用最大流問(wèn)題,1847年 物理學(xué)家克希荷夫發(fā)表了關(guān)于樹(shù)的第一篇論文,1857年 英國(guó)數(shù)學(xué)家凱萊利用樹(shù)的概念研究有機(jī)化合物的分子結(jié)構(gòu),,1878年雪爾佛斯脫首次使用“圖”這個(gè)名詞,1936年匈牙利數(shù)學(xué)家哥尼格發(fā)表了第一本圖論專著《有限圖與無(wú)限圖的理論》,20世紀(jì)50年代 圖論形成了兩個(gè)本質(zhì)上不同的發(fā)展方向,圖論系統(tǒng)的理論研究,1736年 數(shù)學(xué)家歐拉發(fā)表了關(guān)于圖的第一篇論文,圖論的代數(shù)方向,圖論的最優(yōu)化方向,,1736年 瑞士數(shù)學(xué)家 歐拉（E. Euler) 提出“七橋問(wèn)題” 通過(guò)每座橋剛好一次又回到原地。,,,,,,,,,,,,,,,,,,,是否可以 一筆畫？,,,,,1859年 英國(guó)數(shù)學(xué)家 哈密爾頓(Hamiltonian),,用一個(gè)規(guī)則的實(shí)心十二面體，它的20個(gè)頂點(diǎn)標(biāo)出世界 著名的20個(gè)城市，要求游戲者找一條沿著各邊通過(guò)每 個(gè)頂點(diǎn)剛好一次的閉回路，即 “環(huán)球旅行” 。,—— 由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多 問(wèn)題都可以化為哈密頓問(wèn)題，從而引起廣泛的注意和 研究。,—— 發(fā)明“環(huán)球旅行”游戲,用圖論的語(yǔ)言來(lái)說(shuō)，游戲的目的是在十二面體的圖中 找出一個(gè)生成圈。這個(gè)問(wèn)題后來(lái)就被稱為哈密頓問(wèn)題。,,1850年 英國(guó)人格思里提出了“四色猜想”,1976年，美國(guó)數(shù)學(xué)家阿佩爾與哈肯在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上， 用了1200個(gè)小時(shí)，作了100億個(gè)判斷，終于完成了四色定理的證明。,任何一個(gè)平面圖，都可以用四種顏色來(lái)染色，使得任何兩個(gè)相鄰的區(qū)域有不同的顏色。,—— 世界近代三大數(shù)學(xué)難題之一,格思里和其弟弟格里斯,德摩爾根的好友、著名數(shù)學(xué)家哈密爾頓爵士,幾百年來(lái)，許多數(shù)學(xué)家致力于這項(xiàng)研究：,格思里弟弟的老師、著名數(shù)學(xué)家德摩爾根,英國(guó)最著名數(shù)學(xué)家凱利…………,1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四 色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。,11年后，即1890年，數(shù)學(xué)家赫伍德以自己的精確計(jì)算指出肯普的證明是錯(cuò)誤的。,不久，泰勒的證明也被人們否定了。,例 2 有A、B、C、D、E 五個(gè)球隊(duì)舉行比賽，已知A 隊(duì)與其它各隊(duì)都比賽過(guò)一 次；B 隊(duì)和A、C 隊(duì)比賽過(guò)；C 隊(duì)和A、B、D 隊(duì)賽過(guò)； D 隊(duì)和A、C、E 隊(duì)比賽過(guò)；E 隊(duì)和A、D 隊(duì)比賽過(guò)。,那么：這種比賽關(guān)系就可以用圖來(lái)表示,,,,,,,,A,B,C,D,E,點(diǎn)：表示球隊(duì),點(diǎn)與點(diǎn)之間的連線：表示兩球隊(duì)間比賽過(guò),,,,,,例3 五個(gè)球隊(duì)之間的比賽結(jié)果是：A隊(duì)勝了B、D、E隊(duì)； B隊(duì)勝了C隊(duì)； C隊(duì) 勝了A、D隊(duì)； D隊(duì)沒(méi)有勝過(guò)；E隊(duì)勝了D隊(duì)；,—— 用點(diǎn)與點(diǎn)之間帶箭頭的線描述“勝負(fù)關(guān)系”關(guān)系,從圖中可以看出各球隊(duì)之間比賽情況：,,,,,,,,A,B,C,D,E,,,,,,那么，這種勝負(fù)關(guān)系該如何用圖來(lái)描述呢？,10.1 圖的基本概念,定義 一個(gè)圖G是指一個(gè)二元組(V(G),E(G))，即圖是由點(diǎn)及點(diǎn)之間的聯(lián)線所組成。其中:,,1）圖中的點(diǎn)稱為圖的頂點(diǎn)(vertex)，記為：v,2）圖中的連線稱為圖的邊(edge)，記為：e ＝［vi, vj]，vi、vj是邊 e 的端點(diǎn)。,3）圖中帶箭頭的連線稱為圖的弧(arc)，記為：a ＝(vi, vj)，vi、vj是弧 a 的 端點(diǎn)。,—— 要研究某些對(duì)象間的二元關(guān)系時(shí)，就可以借助于圖進(jìn)行研究,分類 無(wú)向圖：點(diǎn)集V和邊集E構(gòu)成的圖稱為無(wú)向圖(undirected graph)，記為： G(V，E) —— 若這種二元關(guān)系是對(duì)稱的，則可以用無(wú)向圖進(jìn)行研究 有向圖：點(diǎn)集V和弧集A構(gòu)成的圖稱為有向圖(directed graph) ，記為：D(V，A) —— 若這種二元關(guān)系是非對(duì)稱的，則可以用有向圖進(jìn)行研究 有限圖: 若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱為有限圖.只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.,,1 圖反映對(duì)象之間關(guān)系的一種工具，與幾何圖形不同。,2 圖中任何兩條邊只可能在頂點(diǎn)交叉，在別的地方是立體交叉，不是圖的頂點(diǎn)。,3 圖的連線不用按比例畫，線段不代表真正的長(zhǎng)度，點(diǎn)和線的位置有任意性。,4 圖的表示不唯一。如：以下兩個(gè)圖都可以描述“七橋問(wèn)題”。,圖的特點(diǎn)：,3 奇點(diǎn)：次為奇數(shù)的點(diǎn)。,4 偶點(diǎn)：次為偶數(shù)的點(diǎn)。,5 孤立點(diǎn)：次為零的點(diǎn)。,6 懸掛點(diǎn)：次為1的點(diǎn)。,1 端點(diǎn)：若e =[u，v] ?E，則稱u，v 是 e 的端點(diǎn)。,2 點(diǎn)的次：以點(diǎn) v 為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn) v 的次，記為：d(v)。 在無(wú)向圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點(diǎn)v的度或次數(shù)，記為d(v)或 dG(v). 在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)v的出度，記為d+(v)，從頂點(diǎn)v引入的邊的數(shù)目稱為v的入度，記為d -(v). 稱d(v)= d+(v)+d -(v)為頂點(diǎn)v的度或次數(shù)．,點(diǎn)(vertex)的概念,例1 G =(V, E),V＝｛v1, v2, v3, v4 , v5 , v6 , v7 ｝,E＝｛e1, e2, e3, e4 , e5 , e6 , e7 , e8 ｝,奇點(diǎn)：v2，v3,偶點(diǎn)：v1，v4,懸掛點(diǎn)：v5，v6,孤立點(diǎn)：v7,,如：e1、e2 是多重邊。,e8 是懸掛邊。,e7 是環(huán),圖 G 或 D 中點(diǎn)的個(gè)數(shù)記為 p(G) 或 p(D) ，簡(jiǎn)記為 p,圖 G 或 D 中邊的個(gè)數(shù)記為 q(G) 或 q(D)，簡(jiǎn)記為 q,點(diǎn)的個(gè)數(shù)p＝7,邊的個(gè)數(shù)q＝8,定理,推論 任何圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)．,,3 初等鏈（圈）：若鏈（圈）中各點(diǎn)均不同，則稱為初等鏈（圈） 。,如：,{ v1, e1, v2, e3, v3 },4 簡(jiǎn)單鏈（圈） ：若鏈（圈）中各邊均不同，則稱為間單鏈（圈） 。,1 鏈：一個(gè)點(diǎn)、邊的交替的連續(xù)序列｛vi1, ei1, vi2, ei2, …, vik, eik｝稱為鏈，記為μ。,2 圈(cycle)：若鏈μ的 vi1＝vik，即起點(diǎn)＝終點(diǎn)，則稱為圈。,鏈(chain)的概念,{ v1, e1, v3, e4, v4 },μ：,鏈,初等鏈,簡(jiǎn)單鏈,不是鏈,{ v1, e1, v2, e3, v3 , e6 , v1 },圈,初等圈,間單圈,圈一定是鏈，鏈不一定是圈,,,路PATH,路(path)：頂點(diǎn)和邊均互不相同的一條途徑。 若在有向圖中的一個(gè)鏈μ中每條弧的方向一致，則稱μ為路。（無(wú)向圖中的路與鏈概念一致。） 回路(circuit)：若路的第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)相同，則稱為回路。 連通性: 點(diǎn)i和j點(diǎn)是連通的：G中存在一條（i，j）路 G是連通的：G中任意兩點(diǎn)都是連通的,—— 路一定是鏈，但鏈不一定是路,,,,,例 在右邊的無(wú)向圖中：,途徑或鏈：,跡或簡(jiǎn)單鏈：,路或路徑：,圈或回路：,,,,,,,,,,,,,,,,,,,μ＝{ v1, e1, v2, e3, v3 },鏈,不是路,μ＝{ v1, e2, v2, e3, v3 },鏈,且是路,μ＝{ v1, e2, v2, e1, v1 },鏈,是回路,—— 注意區(qū)別：環(huán)、圈、回路的概念,在右邊的有向圖中：,連通圖(connected graph)：若圖中任何兩點(diǎn)間至少有一條鏈，則稱為連通圖 。否則， 為不連通圖。,簡(jiǎn)單圖(simple graph)：一個(gè)無(wú)環(huán)、無(wú)多重邊的圖稱為間單圖。,多重圖(multiple graph)：一個(gè)無(wú)環(huán)，但有多重邊的圖稱為多重圖。,連通分圖：非連通圖的每個(gè)連通部分稱為該圖的連通分圖。,基礎(chǔ)圖：去掉有向圖中所有弧上的箭頭，得到的圖稱為原有向圖的基礎(chǔ)圖。,圖G＝(V, E)為不連通圖,但G’＝(V’, E’)是G的連通分圖 其中：V’＝{v1, v2, v3, v4} E’＝{e1, e2, e3, e4, e5, e6, e7},圖G＝(V, E)是多重圖,連通圖,10.2 樹(shù)（tree）,一、樹(shù)的定義,樹(shù)：一個(gè)無(wú)圈的連通圖稱為樹(shù)。,例：《紅樓夢(mèng)》中賈府人物之間的血統(tǒng)關(guān)系樹(shù),,,,,,,,,,,,,,,,,,,賈演,賈源,賈代化,賈代善,賈放,賈敷,賈珍,賈蓉,賈赦,賈政,賈璉,賈寶玉,賈環(huán),賈珠,賈蘭,,,,,,,,,,,,,,（寧國(guó)府）,（榮國(guó)府）,,,二、樹(shù)的性質(zhì),1 設(shè)圖G＝(V, E)是一個(gè)樹(shù)，點(diǎn)數(shù)P(G) ≥ 2，則 G 中至少有兩個(gè)懸掛點(diǎn)。,2 圖G＝(V，E)是一個(gè)樹(shù)G不含圈，且恰有p-1條邊（p是點(diǎn)數(shù)）。,3 圖G＝(V，E)一個(gè)樹(shù) G 是連通圖，且q(G)＝p(G)－1 （q是邊數(shù)）。,4 圖G＝(V，E)是樹(shù) 任意兩個(gè)頂點(diǎn)之間恰有一條鏈。,圖的支撐樹(shù)(spanning tree),1 支撐子圖：設(shè)圖G＝(V，E)，圖G’＝(V’，E’)的V’＝V，E’ ? E，則稱G’是G的一個(gè) 支撐子圖。,2 支 撐 樹(shù)：設(shè)圖T＝(V，E’)是圖G＝(V，E)的支撐子圖，如果T＝(V，E’)是一個(gè)樹(shù)， 則稱 T 是 G 的一個(gè)支撐樹(shù)。,如何尋找 “支撐樹(shù)” 呢？,—— 圖G’＝(V’，E’)的點(diǎn)集與圖G＝(V，E)的點(diǎn)集相同，V’＝V，但圖G’＝(V’，E’) 的邊集僅是圖G＝(V，E)的子集E’ ? E。,,特點(diǎn)——邊少、點(diǎn)不少。,1 最小樹(shù)定義,如果T＝(V，E’)是 G 的一個(gè)支撐樹(shù)，稱 T 中所有邊的權(quán)之和為支撐樹(shù)T的權(quán)， 記為W（T），即：,若支撐樹(shù)T* 的權(quán)W（T*）是G的所有支撐樹(shù)的權(quán)中最小者， 則稱T* 是G 的最小 支撐樹(shù)（最小樹(shù)）， 即：W（T*）＝ min W(T),最小樹(shù)(minimum spanning tree)問(wèn)題,例8：,1） 破圈法：在圖G中任取一個(gè)圈，從圈中去掉權(quán)數(shù)最大的邊，對(duì)余下的圖重復(fù)這個(gè) 步驟， 直到G中不含圈為止，即可得到 G 的一個(gè)最小樹(shù)。,2 求最小樹(shù)的算法（minimum spanning tree algorithm）,且p＝5 q＝4,1）在圈 v1→v2→v3→v1中去掉［v1,v3］,2）在圈 v2→v4→v3→v2中去掉［v2,v3］,3）在圈 v2→v4→v5→v2中去掉［v2,v5］,4）在圈 v3→v4→v5→v3中去掉［v3,v5］,∵圖中已經(jīng)不含圈,∴ 已經(jīng)求出了最小樹(shù),W(T*)＝4＋2＋1＋2＝9,避圈法是一種選邊的過(guò)程，其步驟如下：,1. 從網(wǎng)絡(luò)D中任選一點(diǎn)vi，找出與vi相關(guān)聯(lián)的 權(quán)最小的邊[vi，vj]，得第二個(gè)頂點(diǎn)vj；,2. 把頂點(diǎn)集V分為互補(bǔ)的兩部分V1, 1 ，其中,用避圈法解,?,,,,,,,最小部分樹(shù)如圖上紅線所示； 最小權(quán)和為14。,思考：破圈法與必避圈法各自的思路是怎樣做的呢？,——見(jiàn)圈就破，去掉其中權(quán)最大的。 ——加邊取其中最小的。,例8 要在5個(gè)城市架設(shè)電話線，使城鎮(zhèn)之間能夠通話兩鎮(zhèn)直接連接，每?jī)蓚€(gè)城鎮(zhèn)之 間的架設(shè)電話線的造價(jià)如下圖所示，各邊上的數(shù)字為造價(jià)（ 單位：萬(wàn)元 ）。 問(wèn)：應(yīng)如何架線，可使總造價(jià)最小？,解：,1 破圈法：,2 避圈法：,,,,,,,總造價(jià)：W(T*)＝2＋2＋1＋1＋2＋2＝10 （萬(wàn)元）,本節(jié)重點(diǎn)及難點(diǎn),重點(diǎn),難點(diǎn),1 圖的概念及性質(zhì),4 樹(shù)的概念及性質(zhì),5 部分樹(shù)及最小樹(shù),2 點(diǎn)的概念及性質(zhì),3 鏈的概念及性質(zhì),1 圖的概念及性質(zhì),4 部分樹(shù)及最小樹(shù),2 點(diǎn)的概念及性質(zhì),3 鏈的概念及性質(zhì),10.3．最短路問(wèn)題,最短路問(wèn)題是圖論應(yīng)用的基本問(wèn)題，很多實(shí)際,問(wèn)題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi),用流等問(wèn)題,都可通過(guò)建立最短路問(wèn)題模型來(lái)求解.,1) 求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路.,2) 求賦權(quán)圖中任意兩點(diǎn)間的最短路.,例 如下圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度。現(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過(guò)這個(gè)交 通網(wǎng)到達(dá)v6， 要尋求總路 程最短的線 路。,最短路徑問(wèn)題,2) 在賦權(quán)圖G中，從頂點(diǎn)u到頂點(diǎn)v的具有最小權(quán),定義 1) 若H是賦權(quán)圖G的一個(gè)子圖，則稱H的各,邊的權(quán)和 為H的權(quán). 類似地，若,稱為路P的權(quán)．,若P(u,v)是賦權(quán)圖G中從u到v的路,稱,的路P*(u,v)，稱為u到v的最短路．,3) 把賦權(quán)圖G中一條路的權(quán)稱為它的長(zhǎng)，把(u,v),路的最小權(quán)稱為u和v之間的距離，并記作 d(u,v).,,,給定一個(gè)賦權(quán)有向圖D＝ ( V，A ) ,對(duì)每一條弧aij＝w (vi，vj)，相應(yīng)地有權(quán)w (aij )= wij ，又有兩點(diǎn)vs、vt ∈V,設(shè) p 是 D 中從vs 到vt 的一條路，路 p 的權(quán)是 p 中所有弧的權(quán)之和,記為w(p)．最短路問(wèn)題就是求從vs 到vt 的路中一條權(quán)最小的路 p*:,最短路徑問(wèn)題,10.3 最短路徑問(wèn)題,下面僅介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法——雙標(biāo)號(hào)法（Dijkstra算法），它是在1959年提出來(lái)的。目前公認(rèn)，在所有的權(quán)wij ≥0時(shí)，這個(gè)算法是尋求最短路問(wèn)題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。,二、最短路問(wèn)題的算法,方法：標(biāo)號(hào)法（Dijkstra，1959） 給每點(diǎn)vj標(biāo)號(hào)[dj，vi]。 其中dj為v1至vj的最短距，vi為最短路上Vj的前一點(diǎn)。,標(biāo)號(hào)法步驟：,例 求v1到v6的最短路。,③ [4，V2] [5，V1],④ [5，V3],② [3，V1],⑤ [7，V5] [9，V2] [8，V3],⑥ [10，V4] [11，V5],（1）首先將v1賦給VS。給V1以P標(biāo)號(hào)，d(v1)＝0，vs=V1 （2）考察V1的關(guān)聯(lián)邊，選最小權(quán)的邊的端點(diǎn)加以標(biāo)號(hào),① [0,V1],10.3 最短路徑問(wèn)題,用標(biāo)號(hào)法解例3,[0，v1],[2，v1],[3，v1],其中2=min{0+2,0+5,0+3},[4，v2],[7，v3],[8，v5],[13，v6],最短距為13；,,,,,,[4，v4],,,最短路有2條為v1-v2-v3-v5-v6-v7 和v1-v4-v3-v5-v6-v7。,最短路問(wèn)題的應(yīng)用例子,某汽車公司正在制訂5年內(nèi)購(gòu)買汽車的計(jì)劃。下面給出一輛新汽車的價(jià)格以及一輛汽車的使用維修費(fèi)用(萬(wàn)元)： 年號(hào) 1 2 3 4 5 價(jià)格 2 2.1 2.3 2.4 2.6 汽車使用年齡 0–1 1–2 2–3 3–4 4–5 維修費(fèi)用 0.7 1.1 1.5 2 2.5 試用網(wǎng)絡(luò)分析中求最短路的方法確定公司可采用的最優(yōu)策略。,方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以 費(fèi)用作路長(zhǎng)。,1,3,4,5,6,2,2.7,3.8,5.3,7.3,9.8,2.8,7.4,3.9,5.4,3.1,3.3,4.2,3.0,4.1,5.6,2.7, 1,3.8, 1,7.9, 3,9.4, 3,5.3, 1,,,P284 10.4（a）10.7,作 業(yè),10.4 最大流問(wèn)題,流量問(wèn)題在實(shí)際中是一種常見(jiàn)的問(wèn)題。如公路系統(tǒng)中有車輛流量問(wèn)題，供電系統(tǒng)中有電流量問(wèn)題等等。最大流問(wèn)題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量最大。,網(wǎng)絡(luò)——賦權(quán)圖，記D=（V，E，C），其中C={c1，…，cn}， ci為邊ei上的權(quán)（設(shè)ci ）。 網(wǎng)絡(luò)分析主要內(nèi)容——最小部分樹(shù)、最短路、最大流。,1. 問(wèn)題 已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點(diǎn) 集，A為弧集，C={cij}為容量集， cij 為弧（vi，vj ） 上的容量?，F(xiàn)D上要通過(guò)一個(gè)流f={fij}，其中fij 為弧 （vi，vj ）上的流量。問(wèn)應(yīng)如何安排流量fij可使D上 通過(guò)的總流量v最大？,2. 數(shù)學(xué)模型,（容量約束） （平衡條件）,問(wèn)題：最大流問(wèn)題的決策變量、目標(biāo)函數(shù)、約束條件各是什么？,,,3. 基本概念與定理,如：在前面例舉的網(wǎng)絡(luò)流問(wèn)題中，若已給定一個(gè)可行流（如括號(hào)中后一個(gè)數(shù)字所示），請(qǐng)指出相應(yīng)的弧的類型。,（2）可增值鏈（增廣鏈）,,,,,（3） 截集與截量,截量：截集上的容量和，記為 。,例4 對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的截集與截量。,例4 對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的截集與截量。,解：,（4） 流量與截量的關(guān)系,截集上的流量和,相應(yīng)于截 集的反向 弧上流量和,最大流最小割定理：,,4. 解法,（5） 最大流的判別條件,步驟：,例5 用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。,解：第一次標(biāo)號(hào)及所得可增值鏈如圖，調(diào)量 =1，調(diào)后進(jìn)行第二次標(biāo)號(hào)如圖。第二次標(biāo)號(hào)未進(jìn)行到底，得最大流如圖，最大流量v=5，同時(shí)得最小截,,最大流問(wèn)題的應(yīng)用例子（1）,汽車由A城通往B城的可能的路線如下圖所示。環(huán)境保護(hù)部門擬建立足夠數(shù)量的汽車尾氣檢查站，以便使每輛汽車至少必須經(jīng)過(guò)一個(gè)檢查站。建立檢查站的費(fèi)用根據(jù)各路段的條件而有所不同(如圖上數(shù)字所示)。若求這個(gè)問(wèn)題的最小費(fèi)用解，可使用 模型。 a. 最短路模型； b.最大流模型； c.最小支撐樹(shù)模型,,A,,a,,c,,b,,d,,e,,f,,g,,B,,,,,,,,,,,,,,8,2,4,4,5,2,6,4,3,3,6,7,3,7,8,,,某汽車公司有兩家汽車配件制造廠A和B，負(fù)責(zé)向兩個(gè)服務(wù)配送中心C和D供應(yīng)汽車配件。運(yùn)送的道路網(wǎng)絡(luò)及各路段的允許通過(guò)容量如下圖所示。假設(shè)配件廠的供應(yīng)量無(wú)限制。求向C、D的供應(yīng)量最大的運(yùn)送方案和相應(yīng)的最大供應(yīng)量。,求解：最大流模型,100,200,60,160,最大流問(wèn)題的應(yīng)用例子（2）,100,200,60,160,1。確定從s到t的可行流（觀測(cè)法）,60,160,70,80,10,20,40,30,30,60,60,30,40,70,30,30,20,40,80,140,2。確定從s到t的最小割（截集） 標(biāo)號(hào)集{s,A,B，2，4} 未標(biāo)號(hào)集{1,3,5,6,7,c,D,t},割集: (a,1)(2,6)(b,3)(4,7) 割量：60+60+70+30=220,,此時(shí)已找到最大流，即此可行流就是最佳的運(yùn)送方案。C、D的供應(yīng)量分別為60和160,P285 11.12,作 業(yè),某個(gè)城市的街道圖如下圖，圖上數(shù)字為道路的最大通行能力。求從S到T的最大流，如果要提高S到T的車流量，應(yīng)首先改擴(kuò)哪幾條道路？,Thank You !,,