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

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

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

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

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

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

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

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

8、系，至于 公路的大小、等級、狀況均無關(guān)緊要，亦即不考慮線段（邊）的長度，點(diǎn)的位置帶有隨意性，它們并不按比例尺畫，如五個鎮(zhèn)之間的連接圖也可畫成右圖表示。一、圖的定義目I定義I: 一個圖是由點(diǎn)集V=和V中元素的 無序?qū)疎= % 所構(gòu)成的二元組，記作：G = (V, E),其中叫稱為頂點(diǎn)，稱為邊。IV I表 示頂點(diǎn)個數(shù)，IE I表示邊的個數(shù)。當(dāng)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(yù) (arc)為邊或弧一、圖的定義目一關(guān)聯(lián)邊:和同一個頂點(diǎn)相 連的邊，均稱為該點(diǎn)的 關(guān)聯(lián)邊，如圖6-4中的 勺4、勺4、耳5均是卩4的關(guān) 噪邊。相鄰點(diǎn):一條邊的兩個頂 點(diǎn)，稱為相鄰點(diǎn)，如卩2 與卩4，卩4與5等是相鄰 點(diǎn),而叫與卩5則不是。一、圖的定義一環(huán)與多重邊去兩個頂點(diǎn)相同的邊稱為環(huán)，如勺2, 兩個頂點(diǎn)之間的邊數(shù)N2時，叫多重邊，如勺3 2 就是二重邊。6一4、圖的定義一個頂點(diǎn)卩具有關(guān)聯(lián)邊的總數(shù)稱為該頂點(diǎn)的次,記作dW)(每個環(huán)視作兩條邊)，如圖6-4。dej= 3, t/(v2)= 4,d(v5)= lo把次為奇數(shù)的頂點(diǎn)稱

10、為奇頂點(diǎn)，次為偶數(shù) 的頂點(diǎn)稱為偶頂點(diǎn)。、圖的定義懸掛點(diǎn)與孤立點(diǎn):次為1的頂點(diǎn)稱為 懸掛點(diǎn)，如卩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在任何圖中頂點(diǎn)次數(shù)總和等于邊數(shù)的2倍。 定理2任何圖中，次為奇數(shù)的頂點(diǎn)必有偶數(shù)個。即奇頂點(diǎn)必有偶數(shù)個。定

11、義2無向圖G=（V, E）中，稱某些點(diǎn)及其關(guān)聯(lián)邊的交替序列卩1勺v2 e2 . J % 為從人到的一條鏈，卩1、分別稱為鏈的始點(diǎn)和終點(diǎn)，鏈長為肌若一條鏈的始點(diǎn)與終點(diǎn)重合，則稱為閉鏈（在 無向圖中閉鏈又稱為回路），否則，稱為開鏈。 點(diǎn)邊序列中若只有重復(fù)的點(diǎn)而無重復(fù)的邊，則稱 為簡單鏈。點(diǎn)邊序列中若既沒有重復(fù)的點(diǎn)也無重 復(fù)的邊，則稱為初等鏈（也稱為通路）。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連通的在無向圖中，若頂點(diǎn)耳與號之間存在鏈,則稱V,與號是連通的。規(guī)定:V,與自身是連通的連通圖若無向圖G中的任意兩個頂點(diǎn)都是連通的,則稱G是連通圖，否則稱G是非連通圖。3網(wǎng)絡(luò)一個圖連同定義在其邊集上的實函數(shù)一起稱為一 個網(wǎng)絡(luò).網(wǎng)絡(luò)一般是連通圖.定義在邊集上的實函數(shù) 稱為邊的權(quán)數(shù)記為Wy = W (Vp Vj)它與邊(Vp Vj)具有一一對應(yīng)關(guān)系，可以用以表達(dá) 網(wǎng)絡(luò)上的各種有關(guān)性質(zhì)，如路長、流量、費(fèi)用等 等.網(wǎng)絡(luò)的圖解即在每條邊旁標(biāo)上相應(yīng)的權(quán)數(shù).若一網(wǎng)絡(luò)的每條邊都是無向邊，則稱為無向網(wǎng)絡(luò), 記為N

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

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

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

16、標(biāo)P號。Dijkstra 算法步驟：(3) 考察新P的點(diǎn)，方法同(2),直到所有點(diǎn)都都考察完畢,標(biāo)上P號。(4) 根據(jù)P號點(diǎn)距離值的來源，追溯最短路徑即求出最短路。V3 #8V5 *8例6求V到V6的最短路。（1）首先給V以P標(biāo)號， P（Vi）=0,給其余所有點(diǎn) T標(biāo)號，T（Vj）= + 8 （ j =2, 3,6）P標(biāo)號以（）形式標(biāo) 在結(jié)點(diǎn)旁邊，T標(biāo)號以 不帶（）的數(shù)字標(biāo)在結(jié) 點(diǎn)旁邊(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