第7章_物資調(diào)運問題的圖上作業(yè)法

1、第第 7 章章 物資調(diào)運問題的物資調(diào)運問題的 圖上作業(yè)法圖上作業(yè)法劉群鋒劉群鋒 講師講師東莞理工學(xué)院東莞理工學(xué)院1 物資調(diào)運的交通圖物資調(diào)運的交通圖p交通圖交通圖n反映產(chǎn)地與銷地的交通路線及其距離反映產(chǎn)地與銷地的交通路線及其距離n產(chǎn)地用產(chǎn)地用“”表示，產(chǎn)量寫在圓圈內(nèi)表示，產(chǎn)量寫在圓圈內(nèi)n銷地用銷地用“”表示，銷量寫在方框內(nèi)表示，銷量寫在方框內(nèi)n距離寫在弧的旁邊距離寫在弧的旁邊1 物資調(diào)運的交通圖物資調(diào)運的交通圖p交通圖舉例交通圖舉例ACBGFDE10589793325241 物資調(diào)運的交通圖物資調(diào)運的交通圖p交通圖舉例交通圖舉例ABHECI500006000030000200003000050

2、000266239180393D80000F50000G500001151653172523491202 物資調(diào)運的流向圖物資調(diào)運的流向圖p流向圖流向圖n物資調(diào)運的方案可以用流向圖表示物資調(diào)運的方案可以用流向圖表示n例如例如ACBGFDE1058979(10)(8)(7)(7)(9)2 物資調(diào)運的流向圖物資調(diào)運的流向圖p關(guān)于流向圖的一些規(guī)定關(guān)于流向圖的一些規(guī)定n箭頭必須表示物資運輸?shù)姆较蚣^必須表示物資運輸?shù)姆较騨流量寫在箭頭的旁邊，流量寫在箭頭的旁邊，加小括號加小括號。n流向不能直接跨越路線上的收點、發(fā)點、交流向不能直接跨越路線上的收點、發(fā)點、交叉點叉點n任何一段弧上最多只能顯示一條流向！任

3、何一段弧上最多只能顯示一條流向！即同即同一段弧上的多條流向必須合并。一段弧上的多條流向必須合并。n除端點外，任何點都可以流進和流出除端點外，任何點都可以流進和流出2 物資調(diào)運的流向圖物資調(diào)運的流向圖p含有圈的流向圖含有圈的流向圖ABHECI500006000030000200003000050000D80000F50000G50000(50000)(20000)(30000)(50000)(60000)(10000)(70000)(50000)2 物資調(diào)運的流向圖物資調(diào)運的流向圖p含有圈的流向圖的補充規(guī)定含有圈的流向圖的補充規(guī)定n順時針方向的流向必須畫在圈的內(nèi)側(cè)，稱為順時針方向的流向必須畫在圈

4、的內(nèi)側(cè)，稱為內(nèi)圈流向內(nèi)圈流向n逆時針方向的流向必須畫在圈的外側(cè)，稱為逆時針方向的流向必須畫在圈的外側(cè)，稱為外圈流向外圈流向2 物資調(diào)運的流向圖物資調(diào)運的流向圖p最優(yōu)流向圖最優(yōu)流向圖n總噸公里數(shù)最小總噸公里數(shù)最小的流向圖的流向圖l把每一條弧上的流量乘以相應(yīng)的距離，再求和把每一條弧上的流量乘以相應(yīng)的距離，再求和p怎樣得到最優(yōu)流向圖？怎樣得到最優(yōu)流向圖？n作出第一個流向圖作出第一個流向圖n檢驗其是否最優(yōu)？檢驗其是否最優(yōu)？l若是，結(jié)束；若是，結(jié)束；l否則，調(diào)整，直到最優(yōu)。否則，調(diào)整，直到最優(yōu)。3 第一個流向圖的作法第一個流向圖的作法p無圈的交通圖無圈的交通圖n供需歸鄰站法供需歸鄰站法p有圈的交通圖有圈

5、的交通圖n首先首先破圈破圈，變?yōu)闊o圈交通圖，變?yōu)闊o圈交通圖n再用再用“供需歸鄰站法供需歸鄰站法”3 第一個流向圖的作法第一個流向圖的作法p供需歸鄰站法舉例供需歸鄰站法舉例ACBGFDE10589793325243 第一個流向圖的作法第一個流向圖的作法(10)(8)(7)(7)(9)p供需歸鄰站法舉例供需歸鄰站法舉例ACBGFDE10589793 第一個流向圖的作法第一個流向圖的作法p含有圈的交通圖含有圈的交通圖ABHECI500006000030000200003000050000266239180393D80000F50000G500001151653172523491203 第一個流向圖的

6、作法第一個流向圖的作法ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)p含有圈的交通圖含有圈的交通圖3 第一個流向圖的作法第一個流向圖的作法p含有圈的交通圖含有圈的交通圖3233332223334412621GABCFIHDE223 第一個流向圖的作法第一個流向圖的作法p含有圈的交通圖含有圈的交通圖334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)4 檢驗與調(diào)整檢驗與調(diào)整p圖上作業(yè)法的基本定理圖上作業(yè)法

7、的基本定理n用用“供需歸鄰站法供需歸鄰站法”得到的無圈流向圖是最得到的無圈流向圖是最優(yōu)的！優(yōu)的！n含圈流向圖的每一個圈上的內(nèi)圈流向和外圈含圈流向圖的每一個圈上的內(nèi)圈流向和外圈流向的總長度都不超過圈長的一半，該流向流向的總長度都不超過圈長的一半，該流向圖就是最優(yōu)的！圖就是最優(yōu)的！4 檢驗與調(diào)整檢驗與調(diào)整p怎樣檢驗一個含圈流向圖是否最優(yōu)？怎樣檢驗一個含圈流向圖是否最優(yōu)？n計算每一個圈的內(nèi)圈長和外圈長計算每一個圈的內(nèi)圈長和外圈長n檢驗它們是否超過圈長的一半檢驗它們是否超過圈長的一半l若是，則非最優(yōu)；否則，最優(yōu)若是，則非最優(yōu)；否則，最優(yōu)4 檢驗與調(diào)整檢驗與調(diào)整p檢驗含圈流向圖是否最優(yōu)檢驗含圈流向圖是否

8、最優(yōu)AC1050D3030(10)(30)2344(20)BAC1050D3030(10)(20)2344(30)B4 檢驗與調(diào)整檢驗與調(diào)整p檢驗含圈流向圖是否最優(yōu)檢驗含圈流向圖是否最優(yōu)ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491204 檢驗與調(diào)整檢驗與調(diào)整p怎樣調(diào)整流向圖使之成為最優(yōu)？怎樣調(diào)整流向圖使之成為最優(yōu)？n當外圈流向的總長度超過圈長的一半時當外圈流向的總長度超過圈長的

9、一半時l找出調(diào)整量，每個外圈流量減去調(diào)整量，每個內(nèi)找出調(diào)整量，每個外圈流量減去調(diào)整量，每個內(nèi)圈流量加上調(diào)整量圈流量加上調(diào)整量l無流量的弧添上內(nèi)圈流向，流量為調(diào)整量無流量的弧添上內(nèi)圈流向，流量為調(diào)整量n當內(nèi)圈流向的總長度超過圈長的一半時當內(nèi)圈流向的總長度超過圈長的一半時l找出調(diào)整量，每個內(nèi)圈流量減去調(diào)整量，每個外找出調(diào)整量，每個內(nèi)圈流量減去調(diào)整量，每個外圈流量加上調(diào)整量圈流量加上調(diào)整量l無流量的弧添上外圈流向，流量為調(diào)整量無流量的弧添上外圈流向，流量為調(diào)整量4 檢驗與調(diào)整檢驗與調(diào)整p調(diào)整流向圖使成為最優(yōu)調(diào)整流向圖使成為最優(yōu)AC1050D3030(10)(30)2344(20)BAC1050D30

10、30(10)(20)2344(30)B5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p檢驗與調(diào)整下面的流向圖檢驗與調(diào)整下面的流向圖3233332223334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)225 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p改進圖上作業(yè)法改進圖上作業(yè)法n作出第一個流向圖，使之成為基本流向圖作出第一個流向圖，使之成為基本流向圖n檢驗其是否最優(yōu)？檢驗其是否最優(yōu)？l若是，結(jié)束；若是，結(jié)束；l否則，調(diào)整，直到最優(yōu)。否則，調(diào)整，直到最優(yōu)。5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p基本流向圖基本流向圖n投影圖

11、投影圖連通且不含圈連通且不含圈的流向圖的流向圖p流向圖的投影圖流向圖的投影圖n流向圖中有流向的弧留下流向圖中有流向的弧留下n流向圖中無流向的弧去掉流向圖中無流向的弧去掉5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p畫出投影圖、判斷是否基本流向圖畫出投影圖、判斷是否基本流向圖50103030(10)(30)2344(20)501030305 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p畫出投影圖、判斷是否基本流向圖畫出投影圖、判斷是否基本流向圖5030305050303050(30)(50)23445 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p畫出投影圖、判斷是

12、否基本流向圖畫出投影圖、判斷是否基本流向圖ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491205 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p怎樣把非基本流向圖化成基本流向圖？怎樣把非基本流向圖化成基本流向圖？n在流向圖中添加虛流向，讓投影圖連通在流向圖中添加虛流向，讓投影圖連通5 基本流向圖與改進圖上作業(yè)法基本流向

13、圖與改進圖上作業(yè)法p將流向圖化成基本流向圖將流向圖化成基本流向圖5030305050303050(30)(50)23445 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p將流向圖化成基本流向圖將流向圖化成基本流向圖ABHECI500006000030000200003000050000D80000F50000G50000(30000)(80000)(50000)(110000)(60000)(20000)(50000)2662391803931151653172523491205 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)

14、法p基本流向圖的作用基本流向圖的作用n最優(yōu)流向圖一定是基本流向圖！最優(yōu)流向圖一定是基本流向圖！n所有所有“要檢查的圈要檢查的圈”都合格的基本流向圖必都合格的基本流向圖必定是最優(yōu)流向圖！定是最優(yōu)流向圖！p基本流向圖的基本流向圖的“要檢查的圈要檢查的圈”n要檢查的圈的個數(shù)要檢查的圈的個數(shù)=小圈的個數(shù)小圈的個數(shù)n每次對投影圖每次對投影圖(在變化中在變化中) 加上一條無流向加上一條無流向的弧得到的圈的弧得到的圈5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法p改進圖上作業(yè)法舉例改進圖上作業(yè)法舉例n已知交通圖如下，求最優(yōu)流向圖已知交通圖如下，求最優(yōu)流向圖3233332223334412621GA

15、BCFIHDE225 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法n第一個流向圖如下，它是不是基本流向圖第一個流向圖如下，它是不是基本流向圖334412621GACFIHDE(3)(6)(3)(2)(4)(1)(7)(1)5 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法n檢查并調(diào)整所有檢查并調(diào)整所有“要檢查的圈要檢查的圈”直到合格直到合格3233332223334412621GABCFIHDE(3)(6)(3)(2)(4)(1)(7)(1)225 基本流向圖與改進圖上作業(yè)法基本流向圖與改進圖上作業(yè)法n最優(yōu)流向圖為最優(yōu)流向圖為3233332223334412621GABCFIHDE(3)(4)(0)(1)(1)22(3)(3)(0)7 車輛調(diào)度問題車輛調(diào)度問題p某運輸公司接受了一項貨運業(yè)務(wù)如下表，收、某運輸公司接受了一項貨運業(yè)務(wù)如下表，收、發(fā)點的位置如下圖。求車輛的最優(yōu)調(diào)度方案。發(fā)點的位置如下圖。求車輛的最優(yōu)調(diào)度方案。貨名貨名發(fā)貨點發(fā)貨點收貨點收貨點運量運量距離距離水泥水泥B1A2803石灰石灰B2A1505磚磚B3A3805341322B3