物流運輸路徑規(guī)劃(文件)
【正文】 stra算法算法 步驟： （ 1）初始化，從起點 s出發(fā)，給起點標 P號，距離值為 0，即P(s) =0, 其余個點標 T號，距離為 。二、最短路問題的算法二、最短路問題的算法 例 6 求 v1到 v6的最短路。第二節(jié)第二節(jié) 最短路徑問題最短路徑問題 Dijkstra算法算法 步驟： （ 3）考察新 P的點，方法同（ 2），直到所有點都都考察完畢，標上 P號。 整個方法里面有兩種 標 號： （ 1）最短路上的點的 標 號，用 P（ permanent）表示 。則 1——5——3——4的路長肯定小于1——2——3——4。并且，這個算法實際上也給出了尋求從一個始定點 vs到任意一個點 vj的最短路。例如，按照第一個線路，總長度是 3+6+3=12單位，按照第二個路線，總長度是 3+1+1+6=11單位。規(guī)定：規(guī)定： vi與自身是連通的連通圖連通圖 若無向圖 G中的任意兩個頂點都是連通的， 則稱 G是 連通圖 ， 否則稱 G是 非連通圖 。點邊序列中若只有重復的點而無重復的邊，則稱為 簡單鏈 。定理定理 2 任何圖中，次為奇數(shù)的頂點必有偶數(shù)個。一、圖的定義一、圖的定義圖 64（ a） 圖 64（ b） 圖 64（ c）子圖與支撐子圖子圖與支撐子圖 ：： 在圖 G=(V， E)中，若 V1?V， E1?E，則圖 G1=(V E1)稱為 G的 子圖 ，如圖 64中的 (b)就是 (a)的子圖。 把次為奇數(shù)的頂點稱 為 奇頂點 ，次為偶數(shù) 的頂點稱為 偶頂點 。相鄰點相鄰點 ：： 一條邊的兩個頂點，稱為相鄰點，如 v2與 v4， v4與 v5等是相鄰點，而 v2與 v5則不是。當 V和 E都是有限集合時， G為有限圖，否則，稱為無限圖。一、圖的定義一、圖的定義第一節(jié)第一節(jié) 圖的基本概念圖的基本概念 例例 1 某地區(qū)有五個鎮(zhèn) A、 B、 C、 D、 E它們之間有公路相通的情況如圖所示。第一節(jié)第一節(jié) 圖的基本概念圖的基本概念 圖論中所研究的圖，是指反映或描述自然界或人類社會中，大量的事物及事物之間關(guān)系的圖形。這個勝負情況，可以用下圖所示的有向圖反映出來。即 能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。 17世紀的東普魯士有一座哥尼斯堡城（現(xiàn)在叫加里寧格勒，在波羅的海南岸）， 城中有一條普雷格爾河，河中有兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，如下圖所示。第六章第六章 物流運輸路徑規(guī)劃物流運輸路徑規(guī)劃 隨著科學技術(shù)的進步，特別是電子計算機技術(shù)的發(fā)展，圖論的理論獲得了更進一步的發(fā)展，應用更加廣泛。123456764472235567政府的難題n 政府想在 7個小區(qū)準備共建一套醫(yī)務所、郵局、儲蓄所等服務設施，應建于哪一居民小區(qū)，使對居民總體來說感到方便。而公司也希望借用小李的學識，以 進一步規(guī)范企業(yè)配送，提高質(zhì)量，降低成本，在沃爾瑪、南城百貨等大型超市擠壓下爭取生存機會。小李 very,very高興，說公司很給力，決定一定要做好這份工作。小李的難題小李的難題利客隆 超市分部圖 總部怎么走，成本最低？應該先送哪一個商店？現(xiàn)需要送 20噸百貨到 A、 B… 等 10個分店，每個分店的需求都很零散，至少需要多少什么型號的車輛？每天各個分店都有部分百貨要運回或轉(zhuǎn)移到其他分店，怎么運輸車輛返空率最低，成本最低？小李的答案類似解太原重慶 武漢 南京徐州連云港上海鄭州石家莊 塘沽青島濟南天津北京長途運輸路線問題n 長虹街道近年新建了
教學課件相關(guān)推薦
鄂ICP備17016276號-1