《圖上作業(yè)法【高教課堂】》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖上作業(yè)法【高教課堂】（38頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、 圖上作業(yè)法1詳細(xì)課資本節(jié)課的主要內(nèi)容本節(jié)課的主要內(nèi)容v編制交通圖和流向圖編制交通圖和流向圖v對(duì)流向圖的檢驗(yàn)對(duì)流向圖的檢驗(yàn)v圖上作業(yè)法的求解過(guò)程（重點(diǎn)）圖上作業(yè)法的求解過(guò)程（重點(diǎn)）一、圖上作業(yè)法圖上作業(yè)法v在運(yùn)輸中，若使用同一種運(yùn)輸工具，則運(yùn)費(fèi)的在運(yùn)輸中，若使用同一種運(yùn)輸工具，則運(yùn)費(fèi)的計(jì)算往往僅與運(yùn)送物資的多少及里程有關(guān)。因計(jì)算往往僅與運(yùn)送物資的多少及里程有關(guān)。因此，在求最佳的運(yùn)輸方案時(shí)，用噸公里作為度此，在求最佳的運(yùn)輸方案時(shí)，用噸公里作為度量的標(biāo)準(zhǔn)比用運(yùn)費(fèi)作為度量標(biāo)準(zhǔn)更加方便、實(shí)量的標(biāo)準(zhǔn)比用運(yùn)費(fèi)作為度量標(biāo)準(zhǔn)更加方便、實(shí)用。用。v在求解最佳運(yùn)輸方案時(shí)，用噸公里作為度量單在求解最佳運(yùn)輸方案時(shí)，用
2、噸公里作為度量單位，還可以在已經(jīng)畫(huà)出的交通圖上進(jìn)行，操作位，還可以在已經(jīng)畫(huà)出的交通圖上進(jìn)行，操作起來(lái)較為簡(jiǎn)單、方便、直觀、快捷。起來(lái)較為簡(jiǎn)單、方便、直觀、快捷。v在鐵路、公路等交通部門(mén)經(jīng)常使用這種方法決在鐵路、公路等交通部門(mén)經(jīng)常使用這種方法決策最優(yōu)運(yùn)輸問(wèn)題，這種方法被稱(chēng)為圖上作業(yè)法。策最優(yōu)運(yùn)輸問(wèn)題，這種方法被稱(chēng)為圖上作業(yè)法。二、編制交通圖和流向圖二、編制交通圖和流向圖 交通圖交通圖 反映發(fā)點(diǎn)（產(chǎn)地）與收地（銷(xiāo)地）及交通線路及其反映發(fā)點(diǎn)（產(chǎn)地）與收地（銷(xiāo)地）及交通線路及其距離組成的圖形。距離組成的圖形。發(fā)點(diǎn)用發(fā)點(diǎn)用“”表示，發(fā)出貨物的數(shù)量記在表示，發(fā)出貨物的數(shù)量記在“”之之內(nèi)（單位：噸）內(nèi)（單位
3、：噸）收地（銷(xiāo)地）用收地（銷(xiāo)地）用“”表示，收取貨物的數(shù)量記在表示，收取貨物的數(shù)量記在“”之內(nèi)（單位：噸）之內(nèi)（單位：噸）兩點(diǎn)之間的線路長(zhǎng)度記在交通線路的旁邊。兩點(diǎn)之間的線路長(zhǎng)度記在交通線路的旁邊。1 1、交通圖、交通圖1 1、交通圖、交通圖2 2、流向圖、流向圖v流向圖流向圖:v在交通圖上表示物資流向的圖被稱(chēng)為流向圖。在在交通圖上表示物資流向的圖被稱(chēng)為流向圖。在圖中每個(gè)發(fā)點(diǎn)噸數(shù)全部運(yùn)完，每個(gè)收點(diǎn)所需噸數(shù)圖中每個(gè)發(fā)點(diǎn)噸數(shù)全部運(yùn)完，每個(gè)收點(diǎn)所需噸數(shù)均已滿足。均已滿足。流向用箭頭畫(huà)在兩點(diǎn)連線的右方。流向用箭頭畫(huà)在兩點(diǎn)連線的右方。（即：站在發(fā)點(diǎn)，看向收點(diǎn)，右手所在的一側(cè)或（即：站在發(fā)點(diǎn)，看向收點(diǎn)，右
4、手所在的一側(cè)或從發(fā)點(diǎn)到收點(diǎn)，順時(shí)針?lè)较虻囊粋?cè)）從發(fā)點(diǎn)到收點(diǎn)，順時(shí)針?lè)较虻囊粋?cè)）2 2、流向圖、流向圖發(fā)點(diǎn)發(fā)點(diǎn)A到收點(diǎn)到收點(diǎn)B的的運(yùn)輸量，用括號(hào)運(yùn)輸量，用括號(hào)括起。括起。2 2、流向圖、流向圖v關(guān)于流向圖的一些規(guī)定關(guān)于流向圖的一些規(guī)定v箭頭必須表示物資運(yùn)輸?shù)姆较蚣^必須表示物資運(yùn)輸?shù)姆较騰流量寫(xiě)在箭頭的旁邊，加小括號(hào)。流量寫(xiě)在箭頭的旁邊，加小括號(hào)。v流向不能直接跨越路線上的收點(diǎn)、發(fā)點(diǎn)、交叉點(diǎn)流向不能直接跨越路線上的收點(diǎn)、發(fā)點(diǎn)、交叉點(diǎn)v任何一段弧上最多只能顯示一條流向！即同一段任何一段弧上最多只能顯示一條流向！即同一段弧上的多條流向必須合并。弧上的多條流向必須合并。v除端點(diǎn)外，任何點(diǎn)都可以流進(jìn)和流
5、出除端點(diǎn)外，任何點(diǎn)都可以流進(jìn)和流出2 2、流向圖、流向圖2 2、流向圖、流向圖v含有圈的流向圖的補(bǔ)充規(guī)定含有圈的流向圖的補(bǔ)充規(guī)定v順時(shí)針?lè)较虻牧飨虮仨毊?huà)在圈的內(nèi)側(cè)，稱(chēng)為內(nèi)圈順時(shí)針?lè)较虻牧飨虮仨毊?huà)在圈的內(nèi)側(cè)，稱(chēng)為內(nèi)圈流向流向v逆時(shí)針?lè)较虻牧飨虮仨毊?huà)在圈的外側(cè)，稱(chēng)為外圈逆時(shí)針?lè)较虻牧飨虮仨毊?huà)在圈的外側(cè)，稱(chēng)為外圈流向流向內(nèi)圈流向、外圈流向舉例內(nèi)圈流向、外圈流向舉例44（4）26圖：內(nèi)圈流向圖：內(nèi)圈流向44（4）26圖：外圈流向圖：外圈流向二、對(duì)流向圖的檢驗(yàn)二、對(duì)流向圖的檢驗(yàn)v在物資運(yùn)輸中，把某種物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)在物資運(yùn)輸中，把某種物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)的調(diào)運(yùn)方案是很多的，但我們的目的是找出噸的
6、調(diào)運(yùn)方案是很多的，但我們的目的是找出噸公里數(shù)是最小的調(diào)運(yùn)方案。這就要注意在調(diào)運(yùn)中公里數(shù)是最小的調(diào)運(yùn)方案。這就要注意在調(diào)運(yùn)中不要發(fā)生對(duì)物流運(yùn)輸和迂回運(yùn)輸，因此，我們?cè)诓灰l(fā)生對(duì)物流運(yùn)輸和迂回運(yùn)輸，因此，我們?cè)谥贫飨驁D時(shí)，就要避免它的出現(xiàn)。制定流向圖時(shí)，就要避免它的出現(xiàn)。（1 1）不合理的現(xiàn)象）不合理的現(xiàn)象1 1：對(duì)流：對(duì)流v（1 1）對(duì)流：所謂對(duì)流就是在一段線路上有同一）對(duì)流：所謂對(duì)流就是在一段線路上有同一種物資出現(xiàn)相對(duì)運(yùn)輸現(xiàn)象（往返運(yùn)輸）（同一段種物資出現(xiàn)相對(duì)運(yùn)輸現(xiàn)象（往返運(yùn)輸）（同一段線路上，兩各方向都有流向），如左圖。線路上，兩各方向都有流向），如左圖。v甲乙兩地是一種對(duì)流現(xiàn)象。如果把流
7、向圖改成右甲乙兩地是一種對(duì)流現(xiàn)象。如果把流向圖改成右圖，就可以避免對(duì)流現(xiàn)象，從而可以節(jié)約運(yùn)輸量圖，就可以避免對(duì)流現(xiàn)象，從而可以節(jié)約運(yùn)輸量202010=200(10=200(噸公里噸公里)。201010(10)(20)乙甲左圖 右圖201010(10)(10)乙甲(20)（2 2）不合理的現(xiàn)象）不合理的現(xiàn)象2 2：迂回：迂回v（2 2）迂回迂回：當(dāng)收點(diǎn)與發(fā)點(diǎn)之間的運(yùn)輸線路有兩當(dāng)收點(diǎn)與發(fā)點(diǎn)之間的運(yùn)輸線路有兩條或兩條以上時(shí)（即交通圖成圈），如果運(yùn)送的條或兩條以上時(shí)（即交通圖成圈），如果運(yùn)送的貨物不是走最短線路，則稱(chēng)這種運(yùn)輸為迂回運(yùn)輸。貨物不是走最短線路，則稱(chēng)這種運(yùn)輸為迂回運(yùn)輸。v注：注：當(dāng)交通圖成圈
8、時(shí)，如果流向圖中內(nèi)圈流向的當(dāng)交通圖成圈時(shí)，如果流向圖中內(nèi)圈流向的總長(zhǎng)（簡(jiǎn)稱(chēng)總長(zhǎng)（簡(jiǎn)稱(chēng)內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)）或外圈流向的總長(zhǎng)（簡(jiǎn)稱(chēng)）或外圈流向的總長(zhǎng)（簡(jiǎn)稱(chēng)外外圈長(zhǎng)圈長(zhǎng)）超過(guò)整個(gè)圈長(zhǎng)的一半超過(guò)整個(gè)圈長(zhǎng)的一半就稱(chēng)為就稱(chēng)為迂回運(yùn)輸迂回運(yùn)輸。例。例如某物資流向圖如圖所示。如某物資流向圖如圖所示。迂回運(yùn)輸?shù)呐袛嘤鼗剡\(yùn)輸?shù)呐袛?4（4）26左圖左圖44（4）26右圖右圖顯然：左圖為迂回運(yùn)輸顯然：左圖為迂回運(yùn)輸（3 3）、正規(guī)（最優(yōu)）流向圖）、正規(guī)（最優(yōu)）流向圖v正規(guī)（最優(yōu)）流向圖正規(guī)（最優(yōu)）流向圖：一個(gè)最優(yōu)的調(diào)運(yùn)方：一個(gè)最優(yōu)的調(diào)運(yùn)方案，它的流向圖必是無(wú)對(duì)流、無(wú)迂回的流案，它的流向圖必是無(wú)對(duì)流、無(wú)迂回的流向圖，稱(chēng)這種
9、流向圖為正規(guī)流向圖。向圖，稱(chēng)這種流向圖為正規(guī)流向圖。v物資調(diào)運(yùn)的圖上作業(yè)法就是尋找一個(gè)無(wú)對(duì)物資調(diào)運(yùn)的圖上作業(yè)法就是尋找一個(gè)無(wú)對(duì)流、無(wú)迂回的正規(guī)流向圖。流、無(wú)迂回的正規(guī)流向圖。v步驟如下：步驟如下：作出一個(gè)無(wú)對(duì)流的初始可行方案；作出一個(gè)無(wú)對(duì)流的初始可行方案；檢驗(yàn)有無(wú)迂回檢驗(yàn)有無(wú)迂回 若無(wú)，結(jié)束；若無(wú)，結(jié)束；否則，調(diào)整，直到最優(yōu)。否則，調(diào)整，直到最優(yōu)。三、圖上作業(yè)法的求解過(guò)程三、圖上作業(yè)法的求解過(guò)程v1 1、無(wú)圈（線狀）的交通圖、無(wú)圈（線狀）的交通圖v2 2、有圈的交通圖、有圈的交通圖v方法：方法：供需歸鄰站供需歸鄰站1 1、交通圖無(wú)圈（現(xiàn)狀）情形、交通圖無(wú)圈（現(xiàn)狀）情形v【例例】求最優(yōu)調(diào)運(yùn)方案求
10、最優(yōu)調(diào)運(yùn)方案324786451A1A2B1B3B2A5A3A4B4案例分析案例分析v口訣口訣：抓各端，各端供需歸鄰站抓各端，各端供需歸鄰站v即即：先滿足端點(diǎn)的要求，逐步向中間逼近，直至：先滿足端點(diǎn)的要求，逐步向中間逼近，直至收點(diǎn)與發(fā)點(diǎn)得到全部滿足為止。收點(diǎn)與發(fā)點(diǎn)得到全部滿足為止。324786451A1A2B1B3B2A5A3A4B4（3）（4）（2）（3）（4）（7）（3）（10）練一練練一練答案答案2 2、交通圖有圈情形、交通圖有圈情形v【例例】求最優(yōu)調(diào)運(yùn)方案求最優(yōu)調(diào)運(yùn)方案454786454A1A2B1B3B2B5A38B42273463v它的原則可歸納為：v流向劃右方，對(duì)流不應(yīng)當(dāng)；里圈、外
11、圈分別算，要求不過(guò)半圈長(zhǎng)；如若超過(guò)半圈長(zhǎng)，應(yīng)甩運(yùn)量最小段；反復(fù)求算最優(yōu)方案。解題步驟：解題步驟：v第一步：變有圈為無(wú)圈。第一步：變有圈為無(wú)圈。v方法：方法：“丟邊破圈丟邊破圈”。即丟掉一條邊，破即丟掉一條邊，破去一個(gè)圈。去一個(gè)圈。v注意注意：丟邊時(shí)，往往是丟掉圈中長(zhǎng)度最大丟邊時(shí)，往往是丟掉圈中長(zhǎng)度最大的邊的邊。如圖所示。如圖所示第一步：第一步：“丟邊破圈丟邊破圈”454786454A1A2B1B3B2B5A38B42273463v第二步：在無(wú)圈的交通圖上作流向圖。第二步：在無(wú)圈的交通圖上作流向圖。v原則：原則：先外后內(nèi)，先端點(diǎn)后中間點(diǎn)，要求先外后內(nèi)，先端點(diǎn)后中間點(diǎn)，要求每個(gè)邊都有流向。當(dāng)某條邊
12、無(wú)流向時(shí)，必每個(gè)邊都有流向。當(dāng)某條邊無(wú)流向時(shí)，必須填上運(yùn)輸量為零的虛流向。須填上運(yùn)輸量為零的虛流向。第二步：作流向圖第二步：作流向圖454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（3）（2）（8）v第三步：檢查有無(wú)迂回。第三步：檢查有無(wú)迂回。v圈圈B B5 5B B4 4B B3 3A A2 2的圈長(zhǎng)的圈長(zhǎng)=4+4+5+8=21,=4+4+5+8=21,內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=4+4+5=134+4+5=13（21/221/2），有迂回，所以流向圖不是），有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。最優(yōu)流向圖。需要調(diào)整。v第四步：對(duì)方案進(jìn)行調(diào)整。第四步：對(duì)方案
13、進(jìn)行調(diào)整。v方法方法：找出：找出有迂回圈的流量最小的邊有迂回圈的流量最小的邊（去掉的邊（去掉的邊除外），除外），改此邊為丟掉的邊改此邊為丟掉的邊（邊（邊B B5 5B B4 4），并），并補(bǔ)上補(bǔ)上原來(lái)丟掉的邊原來(lái)丟掉的邊（邊（邊B B5 5A A2 2），），得到新的交通圖得到新的交通圖。在。在此交通圖上做新的流向圖。此交通圖上做新的流向圖。第四步：調(diào)整方案第四步：調(diào)整方案454786454A1A2B1B3B2B5A38B42273463（4）（8）（1）（5）（1）（2）（6）v第五步：對(duì)新方案進(jìn)行檢驗(yàn)。第五步：對(duì)新方案進(jìn)行檢驗(yàn)。v圈圈B B5 5B B4 4B B3 3A A2 2的圈長(zhǎng)的
14、圈長(zhǎng)=4+4+5+8=21,=4+4+5+8=21,內(nèi)圈長(zhǎng)內(nèi)圈長(zhǎng)=4+5=921/24+5=921/2，外圈長(zhǎng)，外圈長(zhǎng)=821/2.=825/22+3+6+3=1425/2，有迂回，所以流向圖不是最，有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。優(yōu)流向圖。需要調(diào)整。v第六步：對(duì)方案進(jìn)行調(diào)整。第六步：對(duì)方案進(jìn)行調(diào)整。v方法方法：找出有迂回圈的流量最小的邊（去掉的邊：找出有迂回圈的流量最小的邊（去掉的邊除外），改此邊為丟掉的邊（邊除外），改此邊為丟掉的邊（邊A A1 1B B3 3），并補(bǔ)上），并補(bǔ)上原來(lái)丟掉的邊（邊原來(lái)丟掉的邊（邊B B1 1A A3 3），得到新的交通圖。在），得到新的交通圖。在
15、此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長(zhǎng)此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長(zhǎng)小于二分之一圈長(zhǎng)，外圈長(zhǎng)小于二分之一圈長(zhǎng)，小于二分之一圈長(zhǎng)，外圈長(zhǎng)小于二分之一圈長(zhǎng)，得到最優(yōu)方案。得到最優(yōu)方案。第六步：調(diào)整方案第六步：調(diào)整方案454786454A1A2B1B3B2B5A38B42273463（3）（7）（1）（4）（2）（2）（6）v 可驗(yàn)證：此方案中無(wú)迂回現(xiàn)象。即為最優(yōu)方案?？沈?yàn)證：此方案中無(wú)迂回現(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ì)課資
圖上作業(yè)法【高教課堂】
