現(xiàn)代物流與物流中心規(guī)劃

第三章運(yùn)輸優(yōu)化技術(shù)

ModernLogisticsandLogisticscentersPlanning

本章要點(diǎn)運(yùn)輸?shù)闹黧w和客體運(yùn)輸線路選擇與優(yōu)化運(yùn)輸流量優(yōu)化車輛裝載優(yōu)化運(yùn)輸?shù)闹黧w（實(shí)施運(yùn)輸?shù)慕M織）：（從事運(yùn)輸?shù)模┢髽I(yè)（從事運(yùn)輸?shù)模┎块T（從事運(yùn)輸?shù)模┤藛T運(yùn)輸?shù)目腕w（運(yùn)輸?shù)膶ο螅簽榭蛻暨\(yùn)輸?shù)漠a(chǎn)品運(yùn)輸?shù)闹黧w和客體

運(yùn)輸線路的選擇和優(yōu)化

3.1.1單一起迄點(diǎn)的運(yùn)輸線路優(yōu)化問題3.1.2運(yùn)輸問題3.1.1單一起迄點(diǎn)的運(yùn)輸線路優(yōu)化問題在一個(gè)交通網(wǎng)絡(luò)中，尋找由出發(fā)點(diǎn)到目的地的最短路線問題。單行線交通網(wǎng)絡(luò)，求V1到V8的最短路線這還用問？最短路的求解方法？

當(dāng)然是：Dijkstra算法Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法－－－輕松搞定Dijkstra算法非常適合使用計(jì)算機(jī)進(jìn)行求解。地球人都知道僅考慮最短距離，而不考慮運(yùn)行時(shí)間？暈!3.1.2運(yùn)輸問題平衡運(yùn)輸問題不平衡運(yùn)輸問題3.1.2運(yùn)輸問題－平衡運(yùn)輸問題算例：某玻璃制造廠與三個(gè)不同地點(diǎn)的純堿供應(yīng)商簽訂合同，由他們供貨給三個(gè)分廠，條件是不超過合同所定的數(shù)量，但必須滿足生產(chǎn)需要。該問題如表3-1所示。問題中所給費(fèi)率是每個(gè)供應(yīng)商到每個(gè)工廠之間最短路徑的運(yùn)輸費(fèi)率。求運(yùn)輸方案3.1.2運(yùn)輸問題－平衡運(yùn)輸問題工廠1工廠2工廠3供應(yīng)量供應(yīng)商1x11x12x13400供應(yīng)商2x21x22x23700供應(yīng)商3x31x32x33500需求量6005005003-1運(yùn)輸問題－供需情況供銷平衡3.1.2運(yùn)輸問題－平衡運(yùn)輸問題工廠1工廠2工廠3供應(yīng)商1476供應(yīng)商2314供應(yīng)商39583-1運(yùn)輸問題－運(yùn)輸成本3.1.2運(yùn)輸問題－平衡運(yùn)輸問題求解算法－－表上作業(yè)法3.1.2運(yùn)輸問題－平衡運(yùn)輸問題表上作業(yè)法非常適合大腦中有兩塊P4-CPU的人:(1):展示自己非凡的計(jì)算才能(2):體驗(yàn)當(dāng)年的工作艱辛準(zhǔn)備好筆、橡皮和紙吧準(zhǔn)備開始講求解算法？

麻煩！你確認(rèn)你的CPU是P4的么？求解算法－－數(shù)學(xué)軟件包工欲善其事，必先利其器

LingoLINGO:LinearINteractiveGeneralOptimizerLingo給我們帶來了什么？大家下課后認(rèn)真思考采用Lingo求解運(yùn)輸問題需要準(zhǔn)備什么？構(gòu)造好明確的數(shù)學(xué)模型將數(shù)學(xué)模型按照指定的語法規(guī)范輸入軟件供銷平衡情況

就是這么簡單

3.1.2運(yùn)輸問題－不平衡運(yùn)輸問題供大于需需大于供表上作業(yè)法需要設(shè)立虛擬庫存，將該問題轉(zhuǎn)化成為一個(gè)平衡運(yùn)輸問題求解

Lingo軟件法需要修改供需約束的不等號，再進(jìn)行求解3.1.2運(yùn)輸問題－不平衡運(yùn)輸問題銷地1銷地2銷地3銷地4產(chǎn)量產(chǎn)地1x11x12x13x146產(chǎn)地2x21x22x23x244產(chǎn)地3x31x32x33x346銷量2235不平衡產(chǎn)量為6+4+6=16，銷量為2+2+3+5=12。產(chǎn)量比銷量多4。從供需平衡看，需要虛擬庫存不平衡運(yùn)輸?shù)睦樱?.1.2運(yùn)輸問題－不平衡運(yùn)輸問題銷地1銷地2銷地3銷地4產(chǎn)地121034產(chǎn)地28357產(chǎn)地368123.1.2運(yùn)輸問題－不平衡運(yùn)輸問題表上作業(yè)法的思路：轉(zhuǎn)化成為一個(gè)平衡問題例如：銷地1銷地2銷地3銷地4產(chǎn)量產(chǎn)地1x11x12x13x145產(chǎn)地2x21x22x23x243產(chǎn)地3x31x32x33x344銷量2235平衡產(chǎn)地1存儲1，產(chǎn)地2存儲1，產(chǎn)地3存儲2，此時(shí)平衡3.1.2運(yùn)輸問題－不平衡運(yùn)輸問題

Lingo作業(yè)法的思路：修改對應(yīng)的供需約束條件例如：3.1.2運(yùn)輸問題－不平衡運(yùn)輸問題強(qiáng)！運(yùn)輸問題搞定

3.1.2運(yùn)輸問題－不平衡運(yùn)輸問題如果用Lingo求解最短路線問題如何？（該部分僅做了解，不作為考試的考察內(nèi)容）當(dāng)然可以！如果用Lingo求解最短路線問題如何？單行線交通網(wǎng)絡(luò)，求V1到V8的最短路線如果用Lingo求解最短路線問題如何？為了尋找網(wǎng)絡(luò)的最短路線距離，我們將使用下面的動態(tài)規(guī)劃遞歸式：

F(i)是從節(jié)點(diǎn)i到終點(diǎn)的最短距離，D(i,j)是從節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。具體說：從節(jié)點(diǎn)i到終點(diǎn)的最短距離是從節(jié)點(diǎn)i到臨接點(diǎn)的距離加上鄰接點(diǎn)的終點(diǎn)的最小距離之和的最小值用Lingo求解最短路線問題的計(jì)算結(jié)果從V1到V8的最短距離F(1)＝12，對應(yīng)的路徑可以對應(yīng)找出Lingo求解最短路線問題很強(qiáng)！Lingo能整的東西還挺多

運(yùn)輸流量優(yōu)化

3.2.1最大運(yùn)輸流量問題3.2.2最小費(fèi)用最大流問題

最大運(yùn)輸流量問題如下圖所示，連接煤產(chǎn)地V1（發(fā)點(diǎn)）到銷地V6（收點(diǎn)）的交通網(wǎng)絡(luò)，V2、V3、V5表示交通網(wǎng)絡(luò)的中間節(jié)點(diǎn)，每條運(yùn)輸線（?。┥系臄?shù)字表示這條線的單位時(shí)間最大通過能力（稱弧的容量），現(xiàn)在要制訂一個(gè)運(yùn)輸方案，使單位時(shí)間從發(fā)點(diǎn)V1到點(diǎn)V6煤的運(yùn)輸量最多？

可行流的網(wǎng)絡(luò)

2：最大流所謂最大流就是在有容量限制的網(wǎng)絡(luò)中流量最大的可行流。最大流問題應(yīng)用很廣泛： 運(yùn)輸系統(tǒng)中的車輛流、物資流； 通訊系統(tǒng)中的信息流；供水系統(tǒng)中的水流；供電系統(tǒng)中的電；金融系統(tǒng)中的資金流；供銷系統(tǒng)中的商品流都有最大流問題的足跡。涉獵廣泛

求最大流的方法

標(biāo)號法Lingo軟件求解法還用Lingo？

標(biāo)號法思路

第一個(gè)初始可行解如何給出？

最簡單的辦法是每條弧上的流量都為零

優(yōu)點(diǎn)：簡單

缺點(diǎn)：可能會增加調(diào)整次數(shù)

增廣鏈及流的調(diào)整法

前向弧、后向弧以及增廣鏈的概念

用標(biāo)號法找出網(wǎng)絡(luò)中的最大流

給出初始可行流：第一次流量調(diào)整就完成了累！繼續(xù)講

接下來，再在新的可行流基礎(chǔ)上，從發(fā)點(diǎn)開始重新標(biāo)號找增廣鏈并對此調(diào)整，直至找不到增廣鏈，即找到最大流為止第二次尋找增廣鏈－－尋找過程第二次尋找增廣鏈－－流量調(diào)整第三次尋找增廣鏈－－尋找過程第三次尋找增廣鏈－－流量調(diào)整第四次尋找增廣鏈－－尋找過程終于完成了！看Lingo輕松搞定

Lingo的必須－－構(gòu)造好明確的數(shù)學(xué)模型目標(biāo)函數(shù)：路段上流量最大約束條件：（可行流的滿足條件）EASY！真能整

多個(gè)發(fā)點(diǎn)和收點(diǎn)的運(yùn)輸流量問題問題：在運(yùn)輸流量問題中，可能同時(shí)存在多個(gè)發(fā)點(diǎn)可以供應(yīng)某種物資，也可能多個(gè)收點(diǎn)需要這種物資。多個(gè)發(fā)點(diǎn)和收點(diǎn)的運(yùn)輸流量問題解決方式：將問題轉(zhuǎn)化成為只有一個(gè)收點(diǎn)和一個(gè)發(fā)點(diǎn)的網(wǎng)絡(luò)最大流問題，運(yùn)用相關(guān)方法求解

最小費(fèi)用最大流問題

問題的提出：

在實(shí)際的物流運(yùn)作過程中，不僅要考慮容量限制下的流量問題，而且還要求考慮費(fèi)用問題。

例如：某公司欲將產(chǎn)品從工廠運(yùn)到倉庫，雖然可以在許多運(yùn)輸線路中選擇，在不同的路線上，運(yùn)費(fèi)是不同的，而每條路線只能負(fù)擔(dān)有限的貨物運(yùn)輸量。如何找到運(yùn)費(fèi)最小的貨物運(yùn)輸方式，并盡可能多地運(yùn)輸產(chǎn)品。

這就構(gòu)成了所謂的：最小費(fèi)用，最大流問題。賦權(quán)圖法對問題進(jìn)行求解

求解最小費(fèi)用流的算法很多，其中易于理解的一種流行算法是用最短路算法求最小費(fèi)用的增廣鏈。

算法思路：

（1）從零流開始，在始點(diǎn)到終點(diǎn)的所有可能增加流量的增廣鏈中尋找總費(fèi)用最小的的鏈，并對該鏈增加流量，得到第一次