【文章內(nèi)容簡介】 航）；鐵，公（公，鐵）；公，公（公，公）航，公，航鐵，公，鐵公，公，公ctctct127)(2 ?公，航P126P128P 22 ?? （航，航），（鐵，航）；（航，航）航；（鐵，航）鐵；（公，航）公航，鐵，公，206126425PQ)(178128225PQ)(P202327325PQ)(P221122112211??????????????????ccc 物流運輸系統(tǒng)規(guī)劃 表 56 各城市之間的最佳組合運輸方式 運輸方式如下：各城市之間的最佳組合?城市對 12 23 34 運輸方式 鐵路 航空 公路 運輸路線優(yōu)化方法及模型 運輸線路優(yōu)化主要是選擇起點到終點的最短路，最短路的度量單位可能是時間最短、距離最短或費用最小等。 ?????點 到 點 間 運 輸 問 題多 點 間 運 輸 問 題回 路 運 輸 問 題 物流運輸系統(tǒng)規(guī)劃 最短路徑法： 即求兩個頂點間的長度最短的路徑。其中，路徑長度不是指路徑上變數(shù)的總和，而是指路徑上各邊的權(quán)值總和。 （ 1） 假設條件： 1）兩點之間的弧線距離為整數(shù)； 2）在連通圖中，從任何一個端點 到其他端點都有 直接路徑，如果不存在直接相連的端點對，則可以從它們之間加上一個極大的距離，如無窮大； 3）連通圖的所有距離為非負； 4）連通圖是有方向性的。 （ 2） 四種基本原型： 1）連通圖 中，從指定起始點到制定目標點之間的最短路徑； 2）連通圖 中，從指定起始點到所有節(jié)點之間的最短路徑； 3）連通圖 中，所有任意兩點之間的最短路徑； 4）連通圖 中，經(jīng)過 K個節(jié)點最短路徑。 iv ? ?,nmG V E? ?,G V E? ?,? ?, 物流運輸系統(tǒng)規(guī)劃 ： 既用于求解任意指定兩地之間的最短路徑，又用于求解指定點到其余所有節(jié)點之間的最短路徑。 （ 1） 基本思路： 在一個連通圖 中求解從 的最短路徑時，首先求出從 出發(fā)的一條最短路，在參照它求出一條次短路徑，以此類推，知道從頂 點 的最短路徑為止。 （ 2） 兩種不同的 Dijkstra算法： ? ?,nmG V E0 nvv到0v0 nvv到???標 號 設 定 算 法標 號 修 正 算 法 物流運輸系統(tǒng)規(guī)劃 兩者的異同： （ 1）相同點：都是迭代算法，都在每步迭代中用試探性標號標記所有的試探點，通過一系列試探尋找該步的最短距離。 （ 2）不同點： 1）標號設定算法在每次迭代中得到的滿意的試探標號設為永久標號，而標號修改算法設為臨時標號； 2）適用范圍不同：標號設定算法只適用于求解非負網(wǎng)絡中的最短路徑問題，標號修改可以解決一部分含有非負路徑的一般網(wǎng)絡問題。 物流運輸系統(tǒng)規(guī)劃 具體算法步驟 : ① 給 以 P標號， ,其余各點均給 T標號， ； ② 若 為剛得到的 標號的點，考慮這樣的點 屬于 。對 的 T標號進行如下的修改： ； ① 比較所有具有 T標號的點，把最小者改為 P標號，當存在兩個以上最小者時，可同時改為 P標號。若全部點均為 P標號則停止，否則用 代替 轉(zhuǎn)回 ?。 0v 0(v ) 0P ? ???)( ivTi p ),(: jij vvv 為標號且 jm vEjv ? ?ijijj lvPvTT ?? )(),(min)(jviv 物流運輸系統(tǒng)規(guī)劃 例子 ：如圖為單行線交通網(wǎng)絡，用 Dijkstra算法求 點的最短路徑。 61 vv到 4 5 V 1 V 2 V 4 7 6 2 V 6 3 V 3 V 5 5 4 物流運輸系統(tǒng)規(guī)劃 其數(shù)學模型如下： （ 59） （ 510） （ 511） （ 512） （ 513） ),...,2,1。,...2,1(0),...2,1(),...,2,1(..min11111 1njmiXbanjbXmiaXtsXCzijnjjmiijmiijinjijminjijij?????????????? ?????? ? 物流運輸系統(tǒng)規(guī)劃 特點： 1）約束條件系數(shù)矩陣的元素等于 0或 1； 2）約束條件系數(shù)矩陣的每列有兩個非零元素，這對應于每個變量在前 m個約束方程中出現(xiàn)一次，在后 n個約束方程中也出現(xiàn)一次； 3）所有結(jié)構(gòu)約束條件都是等式約束； 4）各產(chǎn)地產(chǎn)量之和等于各銷地之和。 物流運輸系統(tǒng)規(guī)劃 表上作業(yè)法： 5 （ 1) 給出初始調(diào)運方案。 —— 初始基可行解： (2) 求各非基變量的檢驗數(shù)， 即在表上計算空格的檢驗數(shù)。 從而判斷檢驗方案是否達到最優(yōu)，若是最優(yōu)解 ,則停止計算；否則轉(zhuǎn)下一步。 (3)調(diào)整調(diào)運方案，得新的方案。 —— 即改進當前的基本可行解 (確定入基和出基變量 )，找出新的基可行解。 (4) 重復 (2),(3)直到求出最優(yōu)方案。 .3. 基本可行解 是否為最優(yōu)解 換基 結(jié)束 Y N 物流運輸系統(tǒng)規(guī)劃 （ 1）確定初始可行解（初始調(diào)運方案）。 1）最小元素法：就近供應，即選擇具有最小運輸費用的變量作為基變量。 2）差額法（伏格爾法）：考慮到一產(chǎn)地的產(chǎn)品不能按最小運費調(diào)運時，就應該考慮次小運費，這就有有個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加就越多，因此對差額最大處，就應當采用最小運費調(diào)運。 物流運輸系統(tǒng)規(guī)劃 （ 2）解的最優(yōu)性檢驗。 要判定運輸問題的某個解是否為最優(yōu)解，可按單純形法，檢驗這個解的各非基變量的檢驗數(shù)，若某個空格的檢驗數(shù)為負，則將它變成基變量將使運輸費用減少，故當前解不是最優(yōu)解；若所有空格的檢驗數(shù)全為非負時，則不管怎么變換解均不能使運輸費用降低，即目標函數(shù)值無法改進，這個解就是最優(yōu)解。 物流運輸系統(tǒng)規(guī)劃 （ 3）解的改進。 由（ 2）可知，若檢驗數(shù)中存在負數(shù)，則說明將這個非基變量變?yōu)榛兞繒r運費會更小，因而這個解就不是最優(yōu)解，還可以進一步改進。 改進的方法就是在運輸表中找出這個空格對應的閉回路 Lij，在滿足所有約束條件下，使 Xij盡量增大，并相應調(diào)整此閉回路上其他頂點的運輸量，以得到另一個更好的基可行解。 物流運輸系統(tǒng)規(guī)劃 （ 4）需說明的幾個問題。 1）若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負數(shù)，在取它們中的任一變量均可使目標函數(shù)值得到改善時，通常取最小負數(shù)相應的變量換入。 2）當某個非基變量的檢驗數(shù)等于零時，則說明該運輸問題有無窮多最優(yōu)解。 3）最優(yōu)解的檢驗除了閉回路法外，還可采用位勢法進行檢驗。 4）產(chǎn)銷不平衡問題可以轉(zhuǎn)換為產(chǎn)銷平衡問題進行求解。 物流運輸系統(tǒng)規(guī)劃 （ 1）可中轉(zhuǎn)的情況： ?產(chǎn)地與銷地之間沒有直達的路線，貨物運輸必須通過某中間站轉(zhuǎn)運； ?某些產(chǎn)地既輸出貨物，也吸收一部分貨物；某銷地既吸收貨物，又輸出一部分貨物，即產(chǎn)地或銷地也可以起中轉(zhuǎn)站的作用，或者既是產(chǎn)地又是銷地； ?產(chǎn)地與銷地之間雖然有直達路線，但直達運輸?shù)馁M用或運輸距離分別比經(jīng)過某些中轉(zhuǎn)站還要高或遠。 物流運輸系統(tǒng)規(guī)劃 （ 2）假設條件： 1）根據(jù)具體問題求出最大可能中轉(zhuǎn)量 Q； 2）純中轉(zhuǎn)站可視為輸出量和輸入量均為 Q的一個產(chǎn)地和銷地； 3）兼中轉(zhuǎn)站的產(chǎn)地 Ai可視為一個輸入量為