[管理學(xué)]運(yùn)輸經(jīng)濟(jì)學(xué)第7章運(yùn)輸合理化-閱讀頁
2024-10-31 22:03本頁面
【正文】 的車輛類型 ？ ? 客戶是如何限制發(fā)送時間的？ 第二節(jié) 運(yùn)輸優(yōu)化的基本問題 所謂運(yùn)輸優(yōu)化 ， 是指在一定的運(yùn)輸條件下 （ 如道路 、 車輛 ） ， 如何使輸送量最大 ， 輸送距離最短 ， 輸送費(fèi)用最省 。 制定運(yùn)輸優(yōu)化方案時 ，先要解決最短運(yùn)輸路線等基本問題 。如武鋼的鋼材要運(yùn)往神龍公司，汽車應(yīng)按什么路線行駛，運(yùn)距最短；再如，武鋼的鋼材如果放在武漢市地區(qū)的幾個倉庫，當(dāng)需要調(diào)往多個用戶時，就要制定優(yōu)化運(yùn)輸方案，制定方案時首先要解決的是倉庫到用戶的最短運(yùn)輸路線問題。 1 7 4 5 2 2 5 1 2 V1 V2 V4 V5 V6 V3 狄氏標(biāo)號法 可在表上進(jìn)行求解，這樣會顯得更方便。 V 1 V 2 V 3 V 4 V 5 V 6 V k P （ V k ） 改進(jìn)點 導(dǎo)致點 1 0 ? ? ? ? ? V 1 0 V 1 V 1 2 1 4 ? ? ? V 2 1 V 2 , V 3 V 1 3 3 8 6 ? V 3 3 V 3 V 4 V 5 V 2 4 8 5 ? V 4 5 V 5 V 3 5 6 7 V 5 6 V 4 ， V 6 V 5 6 7 V 6 7 V 6 例：如圖所示為一有六個節(jié)點的運(yùn)輸網(wǎng)絡(luò)，網(wǎng)絡(luò)中的路權(quán)均以公里表示，求節(jié)點 v1至 v6的最短路線及路程。例如，配送中心一次按順序為多個用戶配送商品，完成后返回配送中心。這類問題可以歸納為運(yùn)籌學(xué)中旅行商問題 和 中國郵遞員問題。問：如何選擇行進(jìn)路線，從而使總行程最短？ ? 旅行商問題的算法，目前已有多種。 ?無向圖的距離矩陣是對稱的。先 減價 dij從小到大排序。 v1 v2 v5 v4 v3 11 1 17 2 23 1 3 10 8 6 （一）旅行商問題 匈牙利算法 ?減價 :每行減去該行的最小值， ∞ 10 0 16 110 ∞ 22 0 20 22 ∞ 9 716 0 9 ∞ 50 1 6 4 ∞1∞ 10 0 16 010 ∞ 22 0 10 22 ∞ 9 616 0 9 ∞ 40 1 6 4 ∞∞ 11 1 17 2 111 ∞ 23 1 3 11 23 ∞ 10 8 117 1 10 ∞ 6 12 3 8 6 ∞ 2?再每列減去該列的最小值。 ∞ 11 1 17 2 111 ∞ 23 1 3 11 23 ∞ 10 8 117 1 10 ∞ 6 12 3 8 6 ∞ 2∞ 10 0 16 110 ∞ 22 0 20 22 ∞ 9 716 0 9 ∞ 50 1 6 4 ∞1?調(diào)整兩次即得。 S表示到達(dá)城市 i之前 中途所經(jīng)過的城市集合 ， 則有： 因此，可選擇（ i， S）作為描述過程的 狀態(tài)變量 ，決策為由一個城市走到另一個城市，并定義 最優(yōu)值函數(shù) 為從城市 1開始經(jīng)由 k個中間城市的 S集到城市 i的 最短路線的距離 。 ),( SiPk]}{\,([m i n),( 1 jiksjkdjSjfSif ?? ??)., . . . ,3, . . . ,2,1( iNSnink ????idif 10 ),( ??? 舉例：求解 4個城市推銷員問題 。設(shè)推銷員從城市 1出發(fā)，經(jīng)過每一個城市且僅一次，最后回到城市 1。 j:1 2 3 4 5 i： 1 0 10 20 30 40 2 12 0 18 30 25 3 23 9 0 5 10 4 34 32 4 0 8 5 45 27 11 10 0 作業(yè)： 第三節(jié) 直達(dá)供貨系統(tǒng)的運(yùn)輸 一、運(yùn)輸規(guī)劃原理 運(yùn)輸規(guī)劃研究的是單一品種物資的典型運(yùn)輸問題 。有些問題，比如有 m臺機(jī)床加工 n種零件的問題，工廠的合理布局問題等，雖要求與提法不同，但經(jīng)過適當(dāng)變化也可以使用本模型求得最優(yōu)解。 ,..., 2 , 1 ( n n m i c ij ? ? 是平衡的， ，問應(yīng)如何安排運(yùn)輸可使總運(yùn)費(fèi)最小？ 假定 ij x 表示由 i A 到 j B 的運(yùn)輸量，則平衡條件下的 如下的線性規(guī)劃模型： 運(yùn)輸問題的一般提法和模型 ，假設(shè)產(chǎn)銷 運(yùn)輸問題可寫出 ?????n1jjm1ii ba ) ,..., 2 , 1 ( 1 m i a x i n j ij ? ? ? ? ) ,..., 2 , 1 ( 1 n j b x j m i ij ? ? ? ? 0 ? ij x 平衡條件下的運(yùn)輸問題一定有最優(yōu)解。這與運(yùn)輸問題的特點有關(guān)。物流流動方向用 → ，流量標(biāo)在右邊。 ? 圖上作業(yè)法的核心就是規(guī)劃出物流的最優(yōu)流向圖，最優(yōu)流向圖是指沒有對流、迂回運(yùn)輸?shù)牧飨驁D。 舉例 A3 B3 A4 A1 A2 B1 B4 B2 280 180 165 118 165 252 317 118 349 ? 檢驗的方法： d內(nèi)（外） ≦ d ? 圖上作業(yè)法的口訣： ? 流向畫右方，對流不應(yīng)當(dāng)；內(nèi)圈外圈分別算，要求不過半圈長。這和單純形法的求解思想完全一致，但是具體的作法則更加簡捷。本例就是一個分派問題，因此完全可以用運(yùn)輸問題的解法求解。 12 7 22 7 5 6 8 5 8 B1 B2 B3 B4 6 7 5 3 A1 6 8 14 8 4 2 7 A2 22 5 27 5 9 10 6 A3 7 12 19 22 13 12 13 2 λ11=(c14+c21)(c11 + c24) =(3 +8) –(6 +7)=2 經(jīng)檢驗，檢驗數(shù) λ 11＝－ 2，故需調(diào)整方案?？煽紤]將公司所需配備的船只數(shù)分為兩個部分：（ 1） 載貨航程所需的周轉(zhuǎn)船只數(shù) 。如此計算的各航線周轉(zhuǎn)船只數(shù)共 91條 ，詳見下表： 航線 裝貨天數(shù) 航程天數(shù) 卸貨天數(shù) 小計 航班數(shù) 需船只數(shù) 1 17 1 19 3 57 1 3 1 5 2 10 1 7 1 9 1 9 1 13 1 15 1 15 合計 91 （ 2） 各港口間調(diào)度所需船只數(shù)。如 D每天到達(dá)的船只有 3條，發(fā)出則只需要 1條，各港口 每天余缺的船只數(shù)如下表： 港口城市 A B C D E F 每天到達(dá) 0 1 2 3 0 1 每天需求 1 2 0 1 3 0 余缺數(shù) 1 1 2 2 3 1 ? 要使得配備的船只數(shù)最少，其實質(zhì)就是要使用于周轉(zhuǎn)的空船數(shù)最少。按該方案所需的空船總數(shù)是： Z= 40。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1