運(yùn)籌學(xué)圖與網(wǎng)絡(luò)ppt課件(參考版)
2025-05-15 13:31本頁(yè)面
【正文】 vi vj vi vj （ cij,bij ） （ 0,bij ） （ a） （ b） （ cij,bij ） （ cij,bij ） vi vj （ cji,bji ） （ cij,bij ） vi vj （ cji,bji ） （ 0,bji) （ 0,bji) （ c） （ d） 。從采地 v1向銷(xiāo)地 v7運(yùn)送石 油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流 量和最小費(fèi)用。 一、最小費(fèi)用最大流的數(shù)學(xué)模型 例 7 由于輸油管道的長(zhǎng)短不一，所以在例 6中每段管道（ vi,vj ）除 了有不同的流量限制 cij外，還有不同的單位流量的費(fèi)用 bij ， cij的單位為萬(wàn) 加侖 /小時(shí)， bij的單位為百元 /萬(wàn)加侖。 cij的單位為萬(wàn)加侖 /小時(shí)。 例 6 某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷(xiāo)售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過(guò)這條路增加網(wǎng)絡(luò)的流量 pf。 vi vj vi vj cij 0 （ a） （ b） cij cij vi vj （ cji） （ c） vi vj cij cji （ d） 求最大流的基本算法 （ 1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。 一、最大流問(wèn)題的數(shù)學(xué)模型 ???????????????????? ??ijijjijjjibx0tifs,ti0sifxxfMa x vs 10 11 6 5 4 7 3 9 15 vt v5 v3 v4 v2 二、最大流問(wèn)題網(wǎng)絡(luò)圖論的解法 對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。 3) 在網(wǎng)絡(luò)各條弧上都有一個(gè)權(quán) ， 表示允許流過(guò)的最大流量 。 ? 把所有弧的權(quán)數(shù)計(jì)算如下表： v1 v2 v3 v4 v5 v6 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6 (繼上頁(yè) ) 把權(quán)數(shù)賦到圖中，再用 Dijkstra算法求最短路。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。 V1 （甲地） 15 17 6 2 4 4 4 3 10 6 5 v2 V7 （乙地） v3 v4 v5 v6 ? 例 2最終解得： ? 最短路徑 v1 v3 v5 v6 v7，每點(diǎn)的標(biāo)號(hào)見(jiàn)下圖 （ 0,s） V1 （甲地） 15 17 6 2 4 4 3 10 6 5 (13,3) v2 (22,6) V7 （乙地） V5 (14,3) V6 (16,5) V3 (10,1) V4 (18,5) ? 例 3 設(shè)備更新問(wèn)題。也可直接在無(wú)向圖中用 Dijkstra算法來(lái)求解。 ? 解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。 ? 例 1 求下圖中 v1到 v6的最短路 ? 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 ? 各點(diǎn)的標(biāo)號(hào)圖如下： v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 1 2 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 ? 例 2 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。在所有的 sij中，找到其值為最小的弧。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。如果 vt已標(biāo)號(hào)（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt反向追蹤到起點(diǎn) vs 而得到。 ? 最短路問(wèn)題是網(wǎng)絡(luò)分析中的一個(gè)基本問(wèn)題 ，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問(wèn)題 ， 如管道鋪設(shè) 、 線路安排 、 廠區(qū)布局等 ，而且經(jīng)常被作為一個(gè)基本工具 ， 用于解決其它的優(yōu)化問(wèn)題 。 例如 ， 用節(jié)點(diǎn)表示城市 ， 用邊表示可以在兩個(gè)城市之間架設(shè)光纜 ， 邊上的權(quán)表示光纜的長(zhǎng)度 ， 試求應(yīng)如何架設(shè)光纜 ， 才能使任意兩城市之間均由光纜相通 ， 且使光纜的總長(zhǎng)度最短 。顯然哈密爾頓回路有且只有 n 條邊，若|V|=n ? 連通圖具有哈密爾頓回路的充分必要條件是什么？這個(gè)問(wèn)題是由愛(ài)爾蘭數(shù)學(xué)家哈密爾頓 1859年提出的，但至今仍未解決 ? 歐拉回路是對(duì)邊進(jìn)行訪問(wèn)的問(wèn)題，哈密爾頓回路是對(duì)點(diǎn)進(jìn)行訪問(wèn)的問(wèn)題 ? 搜索哈密爾頓回路的難度是 NPplete ? 任兩點(diǎn)間都有邊的圖稱(chēng)為完全圖 (或全連接圖 ) ? 完全圖中有多少個(gè)不同的哈密爾頓回路？ (n–1)!/2 ? 完全圖中有多少個(gè)邊不相交的哈密爾頓回路？ (n–1)/2 ? 最小哈密爾頓回路問(wèn)題 (NPp
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1