圖上作業(yè)法[高教課堂]

1、圖上作業(yè)法,1,詳細(xì)課資,本節(jié)課的主要內(nèi)容,編制交通圖和流向圖 對(duì)流向圖的檢驗(yàn) 圖上作業(yè)法的求解過(guò)程（重點(diǎn)）,2,詳細(xì)課資,一、圖上作業(yè)法,在運(yùn)輸中，若使用同一種運(yùn)輸工具，則運(yùn)費(fèi)的計(jì)算往往僅與運(yùn)送物資的多少及里程有關(guān)。因此，在求最佳的運(yùn)輸方案時(shí)，用噸公里作為度量的標(biāo)準(zhǔn)比用運(yùn)費(fèi)作為度量標(biāo)準(zhǔn)更加方便、實(shí)用。 在求解最佳運(yùn)輸方案時(shí)，用噸公里作為度量單位，還可以在已經(jīng)畫出的交通圖上進(jìn)行，操作起來(lái)較為簡(jiǎn)單、方便、直觀、快捷。 在鐵路、公路等交通部門經(jīng)常使用這種方法決策最優(yōu)運(yùn)輸問(wèn)題，這種方法被稱為圖上作業(yè)法。,3,詳細(xì)課資,二、編制交通圖和流向圖,交通圖 反映發(fā)點(diǎn)（產(chǎn)地）與收地（銷地）及交通線路及其距離組

2、成的圖形。 發(fā)點(diǎn)用“”表示，發(fā)出貨物的數(shù)量記在“”之內(nèi)（單位：噸） 收地（銷地）用“”表示，收取貨物的數(shù)量記在“”之內(nèi)（單位：噸） 兩點(diǎn)之間的線路長(zhǎng)度記在交通線路的旁邊。,4,詳細(xì)課資,1、交通圖,5,詳細(xì)課資,1、交通圖,6,詳細(xì)課資,2、流向圖,流向圖: 在交通圖上表示物資流向的圖被稱為流向圖。在圖中每個(gè)發(fā)點(diǎn)噸數(shù)全部運(yùn)完，每個(gè)收點(diǎn)所需噸數(shù)均已滿足。流向用箭頭畫在兩點(diǎn)連線的右方。（即：站在發(fā)點(diǎn)，看向收點(diǎn)，右手所在的一側(cè)或從發(fā)點(diǎn)到收點(diǎn)，順時(shí)針?lè)较虻囊粋?cè)）,7,詳細(xì)課資,2、流向圖,8,詳細(xì)課資,2、流向圖,關(guān)于流向圖的一些規(guī)定 箭頭必須表示物資運(yùn)輸?shù)姆较?流量寫在箭頭的旁邊，加小括號(hào)。 流向不

3、能直接跨越路線上的收點(diǎn)、發(fā)點(diǎn)、交叉點(diǎn) 任何一段弧上最多只能顯示一條流向！即同一段弧上的多條流向必須合并。 除端點(diǎn)外，任何點(diǎn)都可以流進(jìn)和流出,9,詳細(xì)課資,2、流向圖,10,詳細(xì)課資,2、流向圖,含有圈的流向圖的補(bǔ)充規(guī)定 順時(shí)針?lè)较虻牧飨虮仨毊嬙谌Φ膬?nèi)側(cè)，稱為內(nèi)圈流向 逆時(shí)針?lè)较虻牧飨虮仨毊嬙谌Φ耐鈧?cè)，稱為外圈流向,11,詳細(xì)課資,內(nèi)圈流向、外圈流向舉例,12,詳細(xì)課資,二、對(duì)流向圖的檢驗(yàn),在物資運(yùn)輸中，把某種物資從各發(fā)點(diǎn)調(diào)到各收點(diǎn)的調(diào)運(yùn)方案是很多的，但我們的目的是找出噸公里數(shù)是最小的調(diào)運(yùn)方案。這就要注意在調(diào)運(yùn)中不要發(fā)生對(duì)物流運(yùn)輸和迂回運(yùn)輸，因此，我們?cè)谥贫飨驁D時(shí)，就要避免它的出現(xiàn)。,13,詳

4、細(xì)課資,（1）不合理的現(xiàn)象1：對(duì)流,（1）對(duì)流：所謂對(duì)流就是在一段線路上有同一種物資出現(xiàn)相對(duì)運(yùn)輸現(xiàn)象（往返運(yùn)輸）（同一段線路上，兩各方向都有流向），如左圖。 甲乙兩地是一種對(duì)流現(xiàn)象。如果把流向圖改成右圖，就可以避免對(duì)流現(xiàn)象，從而可以節(jié)約運(yùn)輸量2010=200(噸公里)。,14,詳細(xì)課資,（2）不合理的現(xiàn)象2：迂回,（2）迂回：當(dāng)收點(diǎn)與發(fā)點(diǎn)之間的運(yùn)輸線路有兩條或兩條以上時(shí)（即交通圖成圈），如果運(yùn)送的貨物不是走最短線路，則稱這種運(yùn)輸為迂回運(yùn)輸。 注：當(dāng)交通圖成圈時(shí)，如果流向圖中內(nèi)圈流向的總長(zhǎng)（簡(jiǎn)稱內(nèi)圈長(zhǎng)）或外圈流向的總長(zhǎng)（簡(jiǎn)稱外圈長(zhǎng)）超過(guò)整個(gè)圈長(zhǎng)的一半就稱為迂回運(yùn)輸。例如某物資流向圖如圖所示。,1

5、5,詳細(xì)課資,迂回運(yùn)輸?shù)呐袛?顯然：左圖為迂回運(yùn)輸,16,詳細(xì)課資,（3）、正規(guī)（最優(yōu)）流向圖,正規(guī)（最優(yōu)）流向圖：一個(gè)最優(yōu)的調(diào)運(yùn)方案，它的流向圖必是無(wú)對(duì)流、無(wú)迂回的流向圖，稱這種流向圖為正規(guī)流向圖。 物資調(diào)運(yùn)的圖上作業(yè)法就是尋找一個(gè)無(wú)對(duì)流、無(wú)迂回的正規(guī)流向圖。 步驟如下： 作出一個(gè)無(wú)對(duì)流的初始可行方案； 檢驗(yàn)有無(wú)迂回 若無(wú)，結(jié)束； 否則，調(diào)整，直到最優(yōu)。,17,詳細(xì)課資,三、圖上作業(yè)法的求解過(guò)程,1、無(wú)圈（線狀）的交通圖 2、有圈的交通圖 方法：供需歸鄰站,18,詳細(xì)課資,1、交通圖無(wú)圈（現(xiàn)狀）情形,【例】求最優(yōu)調(diào)運(yùn)方案,19,詳細(xì)課資,案例分析,口訣：抓各端，各端供需歸鄰站 即：先滿足端點(diǎn)

6、的要求，逐步向中間逼近，直至收點(diǎn)與發(fā)點(diǎn)得到全部滿足為止。,（3）,（4）,（2）,（3）,（4）,（7）,（3）,（10）,20,詳細(xì)課資,練一練,21,詳細(xì)課資,答案,22,詳細(xì)課資,2、交通圖有圈情形,【例】求最優(yōu)調(diào)運(yùn)方案,23,詳細(xì)課資,它的原則可歸納為： 流向劃右方，對(duì)流不應(yīng)當(dāng)；里圈、外圈分別算，要求不過(guò)半圈長(zhǎng)；如若超過(guò)半圈長(zhǎng)，應(yīng)甩運(yùn)量最小段；反復(fù)求算最優(yōu)方案。,24,詳細(xì)課資,解題步驟：,第一步：變有圈為無(wú)圈。 方法：“丟邊破圈”。即丟掉一條邊，破去一個(gè)圈。 注意：丟邊時(shí)，往往是丟掉圈中長(zhǎng)度最大的邊。如圖所示,25,詳細(xì)課資,第一步： “丟邊破圈”,26,詳細(xì)課資,第二步：在無(wú)圈的交

7、通圖上作流向圖。 原則：先外后內(nèi)，先端點(diǎn)后中間點(diǎn)，要求每個(gè)邊都有流向。當(dāng)某條邊無(wú)流向時(shí)，必須填上運(yùn)輸量為零的虛流向。,27,詳細(xì)課資,第二步：作流向圖,（4）,（8）,（1）,（5）,（3）,（2）,（8）,28,詳細(xì)課資,第三步：檢查有無(wú)迂回。 圈B5B4B3A2的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)= 4+4+5=13（21/2），有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。,29,詳細(xì)課資,第四步：對(duì)方案進(jìn)行調(diào)整。 方法：找出有迂回圈的流量最小的邊（去掉的邊除外），改此邊為丟掉的邊（邊B5B4），并補(bǔ)上原來(lái)丟掉的邊（邊B5A2），得到新的交通圖。在此交通圖上做新的流向圖。,30,詳細(xì)課資,

8、第四步：調(diào)整方案,4,5,4,7,8,6,4,5,4,A1,A2,B1,B3,B2,B5,A3,8,B4,2,2,7,3,4,6,3,（4）,（8）,（1）,（5）,（1）,（2）,（6）,31,詳細(xì)課資,第五步：對(duì)新方案進(jìn)行檢驗(yàn)。 圈B5B4B3A2的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)= 4+5=925/2，有迂回，所以流向圖不是最優(yōu)流向圖。需要調(diào)整。,32,詳細(xì)課資,第六步：對(duì)方案進(jìn)行調(diào)整。 方法：找出有迂回圈的流量最小的邊（去掉的邊除外），改此邊為丟掉的邊（邊A1B3），并補(bǔ)上原來(lái)丟掉的邊（邊B1A3），得到新的交通圖。在此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長(zhǎng)小于二分之一圈長(zhǎng)，外圈長(zhǎng)小于二分之一圈長(zhǎng)，得到最優(yōu)方案。,33,詳細(xì)課資,第六步：調(diào)整方案,4,5,4,7,8,6,4,5,4,A1,A2,B1,B3,B2,B5,A