圖上作業(yè)法【高教課堂】

《圖上作業(yè)法【高教課堂】》由會員分享，可在線閱讀，更多相關(guān)《圖上作業(yè)法【高教課堂】（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 圖上作業(yè)法1詳細(xì)課資本節(jié)課的主要內(nèi)容本節(jié)課的主要內(nèi)容v編制交通圖和流向圖編制交通圖和流向圖v對流向圖的檢驗對流向圖的檢驗v圖上作業(yè)法的求解過程（重點）圖上作業(yè)法的求解過程（重點）一、圖上作業(yè)法圖上作業(yè)法v在運輸中，若使用同一種運輸工具，則運費的在運輸中，若使用同一種運輸工具，則運費的計算往往僅與運送物資的多少及里程有關(guān)。因計算往往僅與運送物資的多少及里程有關(guān)。因此，在求最佳的運輸方案時，用噸公里作為度此，在求最佳的運輸方案時，用噸公里作為度量的標(biāo)準(zhǔn)比用運費作為度量標(biāo)準(zhǔn)更加方便、實量的標(biāo)準(zhǔn)比用運費作為度量標(biāo)準(zhǔn)更加方便、實用。用。v在求解最佳運輸方案時，用噸公里作為度量單在求解最佳運輸方案時，用

2、噸公里作為度量單位，還可以在已經(jīng)畫出的交通圖上進(jìn)行，操作位，還可以在已經(jīng)畫出的交通圖上進(jìn)行，操作起來較為簡單、方便、直觀、快捷。起來較為簡單、方便、直觀、快捷。v在鐵路、公路等交通部門經(jīng)常使用這種方法決在鐵路、公路等交通部門經(jīng)常使用這種方法決策最優(yōu)運輸問題，這種方法被稱為圖上作業(yè)法。策最優(yōu)運輸問題，這種方法被稱為圖上作業(yè)法。二、編制交通圖和流向圖二、編制交通圖和流向圖 交通圖交通圖 反映發(fā)點（產(chǎn)地）與收地（銷地）及交通線路及其反映發(fā)點（產(chǎn)地）與收地（銷地）及交通線路及其距離組成的圖形。距離組成的圖形。發(fā)點用發(fā)點用“”表示，發(fā)出貨物的數(shù)量記在表示，發(fā)出貨物的數(shù)量記在“”之之內(nèi)（單位：噸）內(nèi)（單位

3、：噸）收地（銷地）用收地（銷地）用“”表示，收取貨物的數(shù)量記在表示，收取貨物的數(shù)量記在“”之內(nèi)（單位：噸）之內(nèi)（單位：噸）兩點之間的線路長度記在交通線路的旁邊。兩點之間的線路長度記在交通線路的旁邊。1 1、交通圖、交通圖1 1、交通圖、交通圖2 2、流向圖、流向圖v流向圖流向圖:v在交通圖上表示物資流向的圖被稱為流向圖。在在交通圖上表示物資流向的圖被稱為流向圖。在圖中每個發(fā)點噸數(shù)全部運完，每個收點所需噸數(shù)圖中每個發(fā)點噸數(shù)全部運完，每個收點所需噸數(shù)均已滿足。均已滿足。流向用箭頭畫在兩點連線的右方。流向用箭頭畫在兩點連線的右方。（即：站在發(fā)點，看向收點，右手所在的一側(cè)或（即：站在發(fā)點，看向收點，右

4、手所在的一側(cè)或從發(fā)點到收點，順時針方向的一側(cè)）從發(fā)點到收點，順時針方向的一側(cè)）2 2、流向圖、流向圖發(fā)點發(fā)點A到收點到收點B的的運輸量，用括號運輸量，用括號括起。括起。2 2、流向圖、流向圖v關(guān)于流向圖的一些規(guī)定關(guān)于流向圖的一些規(guī)定v箭頭必須表示物資運輸?shù)姆较蚣^必須表示物資運輸?shù)姆较騰流量寫在箭頭的旁邊，加小括號。流量寫在箭頭的旁邊，加小括號。v流向不能直接跨越路線上的收點、發(fā)點、交叉點流向不能直接跨越路線上的收點、發(fā)點、交叉點v任何一段弧上最多只能顯示一條流向！即同一段任何一段弧上最多只能顯示一條流向！即同一段弧上的多條流向必須合并?；∩系亩鄺l流向必須合并。v除端點外，任何點都可以流進(jìn)和流

5、出除端點外，任何點都可以流進(jìn)和流出2 2、流向圖、流向圖2 2、流向圖、流向圖v含有圈的流向圖的補(bǔ)充規(guī)定含有圈的流向圖的補(bǔ)充規(guī)定v順時針方向的流向必須畫在圈的內(nèi)側(cè)，稱為內(nèi)圈順時針方向的流向必須畫在圈的內(nèi)側(cè)，稱為內(nèi)圈流向流向v逆時針方向的流向必須畫在圈的外側(cè)，稱為外圈逆時針方向的流向必須畫在圈的外側(cè)，稱為外圈流向流向內(nèi)圈流向、外圈流向舉例內(nèi)圈流向、外圈流向舉例44（4）26圖：內(nèi)圈流向圖：內(nèi)圈流向44（4）26圖：外圈流向圖：外圈流向二、對流向圖的檢驗二、對流向圖的檢驗v在物資運輸中，把某種物資從各發(fā)點調(diào)到各收點在物資運輸中，把某種物資從各發(fā)點調(diào)到各收點的調(diào)運方案是很多的，但我們的目的是找出噸的

6、調(diào)運方案是很多的，但我們的目的是找出噸公里數(shù)是最小的調(diào)運方案。這就要注意在調(diào)運中公里數(shù)是最小的調(diào)運方案。這就要注意在調(diào)運中不要發(fā)生對物流運輸和迂回運輸，因此，我們在不要發(fā)生對物流運輸和迂回運輸，因此，我們在制定流向圖時，就要避免它的出現(xiàn)。制定流向圖時，就要避免它的出現(xiàn)。（1 1）不合理的現(xiàn)象）不合理的現(xiàn)象1 1：對流：對流v（1 1）對流：所謂對流就是在一段線路上有同一）對流：所謂對流就是在一段線路上有同一種物資出現(xiàn)相對運輸現(xiàn)象（往返運輸）（同一段種物資出現(xiàn)相對運輸現(xiàn)象（往返運輸）（同一段線路上，兩各方向都有流向），如左圖。線路上，兩各方向都有流向），如左圖。v甲乙兩地是一種對流現(xiàn)象。如果把流

7、向圖改成右甲乙兩地是一種對流現(xiàn)象。如果把流向圖改成右圖，就可以避免對流現(xiàn)象，從而可以節(jié)約運輸量圖，就可以避免對流現(xiàn)象，從而可以節(jié)約運輸量202010=200(10=200(噸公里噸公里)。201010(10)(20)乙甲左圖 右圖201010(10)(10)乙甲(20)（2 2）不合理的現(xiàn)象）不合理的現(xiàn)象2 2：迂回：迂回v（2 2）迂回迂回：當(dāng)收點與發(fā)點之間的運輸線路有兩當(dāng)收點與發(fā)點之間的運輸線路有兩條或兩條以上時（即交通圖成圈），如果運送的條或兩條以上時（即交通圖成圈），如果運送的貨物不是走最短線路，則稱這種運輸為迂回運輸。貨物不是走最短線路，則稱這種運輸為迂回運輸。v注：注：當(dāng)交通圖成圈

8、時，如果流向圖中內(nèi)圈流向的當(dāng)交通圖成圈時，如果流向圖中內(nèi)圈流向的總長（簡稱總長（簡稱內(nèi)圈長內(nèi)圈長）或外圈流向的總長（簡稱）或外圈流向的總長（簡稱外外圈長圈長）超過整個圈長的一半超過整個圈長的一半就稱為就稱為迂回運輸迂回運輸。例。例如某物資流向圖如圖所示。如某物資流向圖如圖所示。迂回運輸?shù)呐袛嘤鼗剡\輸?shù)呐袛?4（4）26左圖左圖44（4）26右圖右圖顯然：左圖為迂回運輸顯然：左圖為迂回運輸（3 3）、正規(guī)（最優(yōu)）流向圖）、正規(guī)（最優(yōu)）流向圖v正規(guī)（最優(yōu)）流向圖正規(guī)（最優(yōu)）流向圖：一個最優(yōu)的調(diào)運方：一個最優(yōu)的調(diào)運方案，它的流向圖必是無對流、無迂回的流案，它的流向圖必是無對流、無迂回的流向圖，稱這種

9、流向圖為正規(guī)流向圖。向圖，稱這種流向圖為正規(guī)流向圖。v物資調(diào)運的圖上作業(yè)法就是尋找一個無對物資調(diào)運的圖上作業(yè)法就是尋找一個無對流、無迂回的正規(guī)流向圖。流、無迂回的正規(guī)流向圖。v步驟如下：步驟如下：作出一個無對流的初始可行方案；作出一個無對流的初始可行方案；檢驗有無迂回檢驗有無迂回 若無，結(jié)束；若無，結(jié)束；否則，調(diào)整，直到最優(yōu)。否則，調(diào)整，直到最優(yōu)。三、圖上作業(yè)法的求解過程三、圖上作業(yè)法的求解過程v1 1、無圈（線狀）的交通圖、無圈（線狀）的交通圖v2 2、有圈的交通圖、有圈的交通圖v方法：方法：供需歸鄰站供需歸鄰站1 1、交通圖無圈（現(xiàn)狀）情形、交通圖無圈（現(xiàn)狀）情形v【例例】求最優(yōu)調(diào)運方案求

10、最優(yōu)調(diào)運方案324786451A1A2B1B3B2A5A3A4B4案例分析案例分析v口訣口訣：抓各端，各端供需歸鄰站抓各端，各端供需歸鄰站v即即：先滿足端點的要求，逐步向中間逼近，直至：先滿足端點的要求，逐步向中間逼近，直至收點與發(fā)點得到全部滿足為止。收點與發(fā)點得到全部滿足為止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）練一練練一練答案答案2 2、交通圖有圈情形、交通圖有圈情形v【例例】求最優(yōu)調(diào)運方案求最優(yōu)調(diào)運方案454786454A1A2B1B3B2B5A38B42273463v它的原則可歸納為：v流向劃右方，對流不應(yīng)當(dāng)；里圈、外

11、圈分別算，要求不過半圈長；如若超過半圈長，應(yīng)甩運量最小段；反復(fù)求算最優(yōu)方案。解題步驟：解題步驟：v第一步：變有圈為無圈。第一步：變有圈為無圈。v方法：方法：“丟邊破圈丟邊破圈”。即丟掉一條邊，破即丟掉一條邊，破去一個圈。去一個圈。v注意注意：丟邊時，往往是丟掉圈中長度最大丟邊時，往往是丟掉圈中長度最大的邊的邊。如圖所示。如圖所示第一步：第一步：“丟邊破圈丟邊破圈”454786454A1A2B1B3B2B5A38B42273463v第二步：在無圈的交通圖上作流向圖。第二步：在無圈的交通圖上作流向圖。v原則：原則：先外后內(nèi)，先端點后中間點，要求先外后內(nèi)，先端點后中間點，要求每個邊都有流向。當(dāng)某條邊

12、無流向時，必每個邊都有流向。當(dāng)某條邊無流向時，必須填上運輸量為零的虛流向。須填上運輸量為零的虛流向。第二步：作流向圖第二步：作流向圖454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）v第三步：檢查有無迂回。第三步：檢查有無迂回。v圈圈B B5 5B B4 4B B3 3A A2 2的圈長的圈長=4+4+5+8=21,=4+4+5+8=21,內(nèi)圈長內(nèi)圈長=4+4+5=134+4+5=13（21/221/2），有迂回，所以流向圖不是），有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。最優(yōu)流向圖。需要調(diào)整。v第四步：對方案進(jìn)行調(diào)整。第四步：對方案

13、進(jìn)行調(diào)整。v方法方法：找出：找出有迂回圈的流量最小的邊有迂回圈的流量最小的邊（去掉的邊（去掉的邊除外），除外），改此邊為丟掉的邊改此邊為丟掉的邊（邊（邊B B5 5B B4 4），并），并補(bǔ)上補(bǔ)上原來丟掉的邊原來丟掉的邊（邊（邊B B5 5A A2 2），），得到新的交通圖得到新的交通圖。在。在此交通圖上做新的流向圖。此交通圖上做新的流向圖。第四步：調(diào)整方案第四步：調(diào)整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）v第五步：對新方案進(jìn)行檢驗。第五步：對新方案進(jìn)行檢驗。v圈圈B B5 5B B4 4B B3 3A A2 2的圈長的

14、圈長=4+4+5+8=21,=4+4+5+8=21,內(nèi)圈長內(nèi)圈長=4+5=921/24+5=921/2，外圈長，外圈長=821/2.=825/22+3+6+3=1425/2，有迂回，所以流向圖不是最，有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。優(yōu)流向圖。需要調(diào)整。v第六步：對方案進(jìn)行調(diào)整。第六步：對方案進(jìn)行調(diào)整。v方法方法：找出有迂回圈的流量最小的邊（去掉的邊：找出有迂回圈的流量最小的邊（去掉的邊除外），改此邊為丟掉的邊（邊除外），改此邊為丟掉的邊（邊A A1 1B B3 3），并補(bǔ)上），并補(bǔ)上原來丟掉的邊（邊原來丟掉的邊（邊B B1 1A A3 3），得到新的交通圖。在），得到新的交通圖。在

15、此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長小于二分之一圈長，外圈長小于二分之一圈長，小于二分之一圈長，外圈長小于二分之一圈長，得到最優(yōu)方案。得到最優(yōu)方案。第六步：調(diào)整方案第六步：調(diào)整方案454786454A1A2B1B3B2B5A38B42273463（3）（7）（1）（4）（2）（2）（6）v 可驗證：此方案中無迂回現(xiàn)象。即為最優(yōu)方案?？沈炞C：此方案中無迂回現(xiàn)象。即為最優(yōu)方案。發(fā)發(fā)收收B1B1B2B2B3B3B4B4B5B5發(fā)貨量發(fā)貨量A1A13 34 47 7A2A24 42 22 28 8A3A31 14 45 5收貨量收貨量4 44 44 46 62 2練一練練一練答案答案38詳細(xì)課資