《運籌學圖與網絡》ppt課件(文件)
【正文】 e1 e2 e3 e4 e5 v2 v3 v1 必須指出，并不是從圖G2中任選一些頂點和邊在一起就組成 G2的子圖G1，而只有在 G2中的一條邊以及連接該邊的兩個端點均選入 G1時， G1才是 G2的子圖。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 有向圖 ? 在有些圖中，邊是沒有方向的，即 [u,v]=[v,u]，這種圖稱為 無向圖 。 ? 當路的起點與終點相同，即 u=v時，稱作一條 回路 。 ? 一個連通的無圈圖則稱為 樹 ， 一個林的每個連通子圖都是一個樹 。 4. 無圈 ， 但若任意增加一條邊 ， 則可得到一個且僅一個圈 。 ? 網絡 賦權的圖 ? 權 程度的度量 ， 數量描述 。 例如 ， 用節(jié)點表示城市 ， 用邊表示可以在兩個城市之間架設光纜 ， 邊上的權表示光纜的長度 ， 試求應如何架設光纜 ， 才能使任意兩城市之間均由光纜相通 ， 且使光纜的總長度最短 。如果 vt已標號（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt反向追蹤到起點 vs 而得到。在所有的 sij中，找到其值為最小的弧。 ? 解：這是一個求無向圖的最短路的問題。 V1 （甲地） 15 17 6 2 4 4 4 3 10 6 5 v2 V7 （乙地） v3 v4 v5 v6 ? 例 2最終解得： ? 最短路徑 v1 v3 v5 v6 v7，每點的標號見下圖 （ 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 設備更新問題。請設計一個五年之內的更新設備的計劃，使得五年內購置費用和維修費用總的支付費用最小。 3) 在網絡各條弧上都有一個權 ， 表示允許流過的最大流量 。 vi vj vi vj cij 0 （ a） （ b） cij cij vi vj （ cji） （ c） vi vj cij cji （ d） 求最大流的基本算法 （ 1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。 例 6 某石油公司擁有一個管道網絡，使用這個網絡可以把石油從采地運送到一些銷售點，這個網絡的一部分如下圖所示。 一、最小費用最大流的數學模型 例 7 由于輸油管道的長短不一，所以在例 6中每段管道（ vi,vj ）除 了有不同的流量限制 cij外，還有不同的單位流量的費用 bij ， cij的單位為萬 加侖 /小時， bij的單位為百元 /萬加侖。 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向銷地 v7運送石 油，怎樣運送才能運送最多的石油并使得總的運送費用最小？求出最大流 量和最小費用。 cij的單位為萬加侖 /小時。 （ 2）找出這條路上各條弧的最小的順流的容量 pf，通過這條路增加網絡的流量 pf。 一、最大流問題的數學模型 ???????????????????? ??ijijjijjjibx0tifs,ti0sifxxfMa x vs 10 11 6 5 4 7 3 9 15 vt v5 v3 v4 v2 二、最大流問題網絡圖論的解法 對網絡上弧的容量的表示作改進。 ? 把所有弧的權數計算如下表： 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 (繼上頁 ) 把權數賦到圖中，再用 Dijkstra算法求最短路。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用就低。也可直接在無向圖中用 Dijkstra算法來求解。 ? 例 1 求下圖中 v1到 v6的最短路 ? 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 ? 各點的標號圖如下： v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3
教學課件相關推薦
鄂ICP備17016276號-1