物流運輸路徑規(guī)劃

1、小李的難題小李自廣西大學營銷專業(yè)畢業(yè)進入利客隆工作前天剛 過1年，昨天得到了一個好消息，公司調(diào)它到總部做配送調(diào)度。小李very理巳ry高興，說公司很給力，決定 一定要做好這份工作。而公司也希望借用小李的學識， 以進一步規(guī)范企業(yè)配送，提高質(zhì)量，降低成本，在沃 爾瑪、南城百貨等大型超市擠壓下爭取生存機會。但 對小李來說，調(diào)度還真是新鮮事。對于干了！年的小李,對公司的規(guī)模、布局了如指掌。iU金宇新城獅叱屯綠村卷續(xù)河帽圃恒博醫(yī)院+邕賓立交橋六安-7W虛樂?；▓@怎么走，成本最低？應該先送哪一個商店?-哮何caroJ為丁卬里emKM何踰3一.刈：+壯曰H 厶.rtdrrr 南城百貨北屯悄士如; 7 伺現(xiàn)需

2、要送20噸百貨到A、B.等10個分店, 每個分店的需求都很零散， 至少需要多少什么型號的車輛？南寧市財經(jīng)學校陳西村.翩嶺茅橋矢彎弓T硒寧太酒店fw W南飯店H心規(guī)華夫灑詢/會電視大學f小八U富寧新興苑每天各個分店都有部分百貨要運回或轉(zhuǎn)移到 其他分店，怎么運輸車輛返空率最低，成本最低?麗江村小區(qū)橋丁石一東越J!南大5fi三月花國際廂昊g紅林大泅1夫灑店長嶺W黃茅坪水庫綠都百Ng連順新汽-皈険映購津頭鄉(xiāng)利客隆超市分部圖總部H 1 *depssss太原重慶石家莊鄭州武漢南京匕京天津濟南徐州塘沽青烏連云港上海長途運輸路線問題長虹街道近年新建了 個居民小區(qū)，各小區(qū)的大致位置及相互間的道路距離如圖所示，單

3、位（100m）,各居住小區(qū)居民數(shù)為：2000,3000,3500,3700, 5000, 2800,4500。政府的難題政府想在7個小區(qū)準備共建一套醫(yī)務所、郵局、儲蓄所等服務設施，應建于哪一居民小區(qū)，使對居民總體來說感到方便。電信部分擬將布設寬帶到各個小區(qū)，應如何鋪設最為經(jīng)濟?工作組組織考察，從小區(qū)出發(fā)，經(jīng)過各小區(qū) （順序不限）,最后到小區(qū)再離去，哪條路 最近？第一節(jié)圖的基本概念第二節(jié)最短路徑問題 第三節(jié)最大流問題第四節(jié)最小費用流問題 第五節(jié) 單、多回路運輸路線問題圖論是應用非常廣泛的運籌學分支，它已經(jīng)廣泛地應用于物理學控制論，信息論，工程 技術(shù)，交通運輸，經(jīng)濟管理，電子計算機等各項領域。對于

4、科學研究，市場和社會生活中的 許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網(wǎng)絡的合理布局等問 題，都可以應用圖論的方法，簡便、快捷地加 以解決。隨著科學技術(shù)的進步，特別是電子計算機技術(shù)的發(fā)展，圖論的理論獲得了更進一步的發(fā)展，應用更加廣泛。如果將復雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術(shù)人員和經(jīng)營管理人員的重視。第六章物流運輸路徑規(guī)劃1736年瑞士科學家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學論文與位置幾何有關(guān)的一個 問題的解，解決了著名的哥尼斯堡七座橋問 題。17世紀的東

5、普魯士有一座哥尼斯堡城（現(xiàn) 在叫加里寧格勒，在波羅的海南岸），城中有 一條普雷格爾河，河中有兩個島嶼，河的兩岸 和島嶼之間有七座橋相互連接，如下圖所示。哥尼斯堡一角座橋，并且每座橋只能走過_次,最終回到原當?shù)氐木用駸嶂杂?這樣一個問題，一個漫 步者如何能夠走過這七出發(fā)地。盡管試驗者很多, 但是都沒有成功。為了尋找答案，1736年歐拉把陸地縮為一點，把橋作為連接點的A邊，將這個問題抽象成圖形的一筆 畫問題。即能否從某一點開始不重 復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這 是不可能的，因為這個圖形中每一 個頂點都與奇數(shù)條邊相連接，不可 能將它一筆畫出，這就是古典圖論 中的第一個

6、著名問題。第_節(jié)圖的基本概念在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的 關(guān)系，常常在紙上用點和線來畫出各式各樣的示意圖。例 有六支球隊進行足球比賽，我們分別用點 勺表示這六支球隊，它們之間的比賽情況，也可 以用圖反映出來，已知巾隊戰(zhàn)勝卩2隊，卩2隊戰(zhàn)勝人隊 ,卩3隊戰(zhàn)勝卩5隊，如此等等。這個勝負情況，可以用 下圖所示的有向圖反映出來。第一節(jié)圖的基本概念第_節(jié)圖的基本概念我們就把類似以上的幾個例子中通過點和點之間 的線來反映實際生產(chǎn)和生活中的某些特定對象之間的 特定關(guān)系的所構(gòu)成圖形稱為圖（Graph）。一般來說， 通常用點表示研究對象，用點與點之間的線表示研究對 象之間的特定關(guān)系。由于在一般情

7、況下，圖中的相對 位置如何，點與點之間線的長短曲直，對于反映研究 對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖 與幾何圖，工程圖等本質(zhì)上是不同的。第一節(jié)圖的基本概念一.圖的定義圖論中所研究的圖，是指反映或描述自然界或人類社會中，大量的事物及事物之間關(guān)系的圖形。 是由點和線組成的。點稱為頂點，它的集合用V(Vertex)表示，頂點通常表示有形或無形的事物。線稱為邊，它的集合用E (Edge)表示，邊通常表示事物與事物(點與點)之間的聯(lián)系或特定的關(guān)系。一、圖的定義iD例1某地區(qū)有五 個鎮(zhèn)A、B、C、D、 E它們之間有公路 相通的情況如圖所 zjs O一、圖的定義在圖論中，我們只關(guān)心兩點間是否有聯(lián)

8、系，至于 公路的大小、等級、狀況均無關(guān)緊要，亦即不考慮線段（邊）的長度，點的位置帶有隨意性，它們并不按比例尺畫，如五個鎮(zhèn)之間的連接圖也可畫成右圖表示。一、圖的定義目I定義I: 一個圖是由點集V=和V中元素的 無序?qū)疎= % 所構(gòu)成的二元組，記作：G = (V, E),其中叫稱為頂點，稱為邊。IV I表 示頂點個數(shù)，IE I表示邊的個數(shù)。當V和E都是有 限集合時，G為有限圖，否則，稱為無限圖。本 書只論及有限圖。圖中所有邊都沒有方向，稱為 無向圖，否則稱為有向圖。例如下面圖6-3,即 為無向圖.、圖的定義無向圖G= (V, E)H6-3其中：V = (vp v2 V3 V4、V5 E = (e

9、P e2 e3 e4 e5 e6 e7 并且：第一節(jié)圖的基本概念A (arc)為邊或弧一、圖的定義目一關(guān)聯(lián)邊:和同一個頂點相 連的邊，均稱為該點的 關(guān)聯(lián)邊，如圖6-4中的 勺4、勺4、耳5均是卩4的關(guān) 噪邊。相鄰點:一條邊的兩個頂 點，稱為相鄰點，如卩2 與卩4，卩4與5等是相鄰 點,而叫與卩5則不是。一、圖的定義一環(huán)與多重邊去兩個頂點相同的邊稱為環(huán)，如勺2, 兩個頂點之間的邊數(shù)N2時，叫多重邊，如勺3 2 就是二重邊。6一4、圖的定義一個頂點卩具有關(guān)聯(lián)邊的總數(shù)稱為該頂點的次,記作dW)(每個環(huán)視作兩條邊)，如圖6-4。dej= 3, t/(v2)= 4,d(v5)= lo把次為奇數(shù)的頂點稱

10、為奇頂點，次為偶數(shù) 的頂點稱為偶頂點。、圖的定義懸掛點與孤立點:次為1的頂點稱為 懸掛點，如卩5。次為4 e一、圖的定義一%簡單圖:無環(huán).無多重邊的圖稱為簡單圖，如圖6-4(a)(b)、(c),后面如無特殊說明，均指簡單圖。斯圖與支備圖:在圖G=(V, E)中，若VUV, EUE,則圖GRV1、EJ稱為G的子圖，如圖6-4中的(b)就是(a)的子圖。特別地：V1=V, EWE時，稱G是G的支撐子圖(生成子圖)。如圖6-4中(c)、(b)都是(a)的支撐圖。旳巳5圖64 (b)、圖的定義定理1在任何圖中頂點次數(shù)總和等于邊數(shù)的2倍。 定理2任何圖中，次為奇數(shù)的頂點必有偶數(shù)個。即奇頂點必有偶數(shù)個。定

11、義2無向圖G=（V, E）中，稱某些點及其關(guān)聯(lián)邊的交替序列卩1勺v2 e2 . J % 為從人到的一條鏈，卩1、分別稱為鏈的始點和終點，鏈長為肌若一條鏈的始點與終點重合，則稱為閉鏈（在 無向圖中閉鏈又稱為回路），否則，稱為開鏈。 點邊序列中若只有重復的點而無重復的邊，則稱 為簡單鏈。點邊序列中若既沒有重復的點也無重 復的邊，則稱為初等鏈（也稱為通路）。eviV2連通圖例如在圖 65 中:S=v6 e6 v5 e7 vx e8 v5 e7 片 e9 v4 e4 V3是一 條連接V6、V3的鏈，鏈長為6.Si=v6 e6 v5 e7 Vj e8 v5 e5 v4 e4 V3是一條連接V6、V3的簡

12、單 鏈，鏈長為5S2=V6e6V5e7Vie9V4e4V3是一條連接V6、V3的初等鏈。V6圖6-5連通的在無向圖中，若頂點耳與號之間存在鏈,則稱V,與號是連通的。規(guī)定:V,與自身是連通的連通圖若無向圖G中的任意兩個頂點都是連通的,則稱G是連通圖，否則稱G是非連通圖。3網(wǎng)絡一個圖連同定義在其邊集上的實函數(shù)一起稱為一 個網(wǎng)絡.網(wǎng)絡一般是連通圖.定義在邊集上的實函數(shù) 稱為邊的權(quán)數(shù)記為Wy = W (Vp Vj)它與邊(Vp Vj)具有一一對應關(guān)系，可以用以表達 網(wǎng)絡上的各種有關(guān)性質(zhì)，如路長、流量、費用等 等.網(wǎng)絡的圖解即在每條邊旁標上相應的權(quán)數(shù).若一網(wǎng)絡的每條邊都是無向邊，則稱為無向網(wǎng)絡, 記為N

13、= (G, w)或 N=(V，E)3網(wǎng)絡若一網(wǎng)絡的每條邊都是有向邊，則稱為有向網(wǎng)絡, 記為N=(D, w)或 N =(匕 A )若一網(wǎng)絡中既有無向邊，也有有向邊，則稱為混合 網(wǎng)絡.所謂網(wǎng)絡分析，即對網(wǎng)絡進行定性和定量分析，以 便為實現(xiàn)某種優(yōu)化目標而尋求最優(yōu)方案.這方面的典型 問題有：最小樹問題，最短路問題，中心問題，重心問 題，最大流問題，最小費用最大流問題，網(wǎng)絡計劃問題, 等等.33vi5從V到V&的路線是很多 的。比如從V出發(fā)，經(jīng)過 V2 , V4至11達V6或者從V出 發(fā)，經(jīng)過V?, V3，V5到達V6等等。但不同的路線，經(jīng)過的總長度是不同的。例如， 按照第一個線路，總長度是3+6+3=

14、12單位，按照第二個路 線，總長度是3+1+1+6=11單位。第二節(jié)最短路徑問題基本算法有兩種:Dijkstra算法：求某一點到其他各點之間的最短距離 矩陣算法：求任意兩點之間的距離。二、最短路問題的算法1、雙標號法（Dijkstra算法），它是在1959年提出來 的。目前公認，在所有的權(quán)M0時，這個算法是尋 求最短路問題最好的算法。并且，這個算法實際上也 給出了尋求從一個始定點Vs到任意一個點號的最短路。第二節(jié)最拒踣徑問題Dijkstra 算法假定1 23 4是1一4的最短路。則123定是1一3的最短路， 2 34也一定是24的最短路。Dijkstra 算法反證：設13的最短路為153O則1

15、534的路長肯定小于1234o這與假設矛盾。Dijkstra 算法設如表不兩個相鄰點i點距禺；如果不相鄰(1巧0設5表示不相鄰的S“之間的距離。為了標志最短路的點，就對其標號。整個方法里面有 兩種標號：(1) 最短路上的點的標號，用P (permanent)表示；(2) 不是最短路上的點的標號，用T(temporary)表示。Dijkstra 算法步驟：(1) 初始化，從起點S出發(fā)，給起點標P號，距離值為0,即 P(s)二0,其余個點標T號，距離為7(/) = oo 。(2) 考察與s相應的點，計算s至U這些點的距離4.=mmr(0,P(5)+ z.然后，在所有標T號的點中，選擇距離最小的那個

16、標P號。Dijkstra 算法步驟：(3) 考察新P的點，方法同(2),直到所有點都都考察完畢,標上P號。(4) 根據(jù)P號點距離值的來源，追溯最短路徑即求出最短路。V3 #8V5 *8例6求V到V6的最短路。（1）首先給V以P標號， P（Vi）=0,給其余所有點 T標號，T（Vj）= + 8 （ j =2, 3,6）P標號以（）形式標 在結(jié)點旁邊，T標號以 不帶（）的數(shù)字標在結(jié) 點旁邊(2) 考察J：T(v2) =min T (v2),=min , 0+3 T (v3) =min T (v3),=min 0+5 = 5 所以，P(v2)= 3T (v4)二 9326(4)p(v3)= 4P(v

17、j) +ai2=3P(vJ +ai3T)二 53*8V6+ 00T (v3),3+1 = 4 T (v4), P(v2),3+6二 9(3) 考察V2： T(vJ =min +23*1 =min 5, TCvJ =min J =min (4) 考察 V3： T(v5) =min T(v5),=min , 4+1 = 5 T(v4)=min T (v4), P(v3) +a34=min 9, 4+4 = 8 所以，P(v5) = 5P W3) +35 1P(V4)二 7(7)T (v6) = 11(5) 考察V5：T(v6) =min T (v6), P(v5) +a56 =min , 5+6 = 11T(v4) =min T (v4), P(v5) +a54=min 8, 5+2 = 7V2 (3) 6332(5)所以，P(v4) = 7P(V