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