圖上作業(yè)法課件

圖

上

作

業(yè)

法本節(jié)課的主要內(nèi)容編

制

交

通

圖

和

流

向

圖對(duì)

流

向

圖

的

檢

驗(yàn)圖上作業(yè)法的求解過(guò)程(重點(diǎn))在

求

解

最

佳

運(yùn)

輸

方

案

時(shí)

，

用

噸

公

里

作

為

度

量

單

位，還可以在已經(jīng)畫(huà)出的交通圖上進(jìn)行，操作起來(lái)較為簡(jiǎn)單、方便、直觀(guān)、快捷。在

鐵

路

、

公

路

等

交

通

部

門(mén)

經(jīng)

常

使

用

這

種

方

法

決

策最優(yōu)運(yùn)輸問(wèn)題，這種方法被稱(chēng)為圖上作業(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è)法●

交

通

圖●反

映

發(fā)

點(diǎn)

(

產(chǎn)

地

)

與

收

地

(

銷(xiāo)

地

)

及

交

通

線(xiàn)

路

及

其

距離組成的圖形?！?/p>

發(fā)點(diǎn)用

“O”

表示，發(fā)出貨物的數(shù)量記在

“O”

之

內(nèi)

(

單

位

：

噸

)●收地(銷(xiāo)地)用“□”表示，收取貨物的數(shù)量記在

“

□

”

之

內(nèi)

(

單

位

：噸

)·兩點(diǎn)之間的線(xiàn)路長(zhǎng)度記在交通線(xiàn)路的旁邊。二

、

編

制

交

通

圖

和

流

向

圖1、交通圖A

103

B552F

8D9

4

9

E3口交通圖舉例C2了G1、交通圖300001801655000025280000G115393317C500003000020000口交

通

圖

舉

例A

5000026660000239I50000EF349120HB流向圖：在交通圖上表示物資流向的圖被稱(chēng)為流向圖。在

圖中每個(gè)發(fā)點(diǎn)噸數(shù)全部運(yùn)完，每個(gè)收點(diǎn)所需噸數(shù)均已滿(mǎn)足。流向用箭頭畫(huà)在兩點(diǎn)連線(xiàn)的右方。(即：站在發(fā)點(diǎn)，看向收點(diǎn)，右手所在的一側(cè)或

從發(fā)點(diǎn)到收點(diǎn)，順時(shí)針?lè)较虻囊粋?cè))2

、流向圖2

、流向圖口

流

向

圖■

物資

調(diào)

運(yùn)的

方

案

可以用

流向圖

表

示點(diǎn)A到

收

點(diǎn)B的輸

量

，

用

括

號(hào)

括

起

。C10(10個(gè)(8)8(7)7

G發(fā)

運(yùn)B5AF(7)(9)9

ED9關(guān)于流向圖的一些規(guī)定箭頭必須表示物資運(yùn)輸?shù)姆较蛄髁繉?xiě)在箭頭的旁邊，加小括號(hào)。流向不能直接跨越路線(xiàn)上的收點(diǎn)、發(fā)點(diǎn)、交叉點(diǎn)

任何一段弧上最多只能顯示一條流向!即同一段

弧上的多條流向必須合并。除端點(diǎn)外，任何點(diǎn)都可以流進(jìn)和流出2

、流向圖2

、流向圖A

50000(50000)E

30000(20000)F

5000060000(60000)|50000(10000)G(50000)口

含

有

圈

的

流

向

圖I50000(70000)(50000)(30000)H

300008000020000CB含有圈的流向圖的補(bǔ)充規(guī)定順時(shí)針?lè)较虻牧飨虮仨毊?huà)在圈的內(nèi)側(cè)，稱(chēng)為內(nèi)圈

流向逆

時(shí)

針

方

向

的

流

向

必

須

畫(huà)

在

圈

的

外

側(cè)

，

稱(chēng)

為

外

圈

流向2

、流向圖(4)6(4)42圖：

內(nèi)圈流向內(nèi)圈流向、外圈流向舉例圖：外圈流向4在

物

資

運(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è)?/p>

制定流向圖時(shí)，就要避免它的出現(xiàn)。二

、

對(duì)

流

向

圖

的

檢

驗(yàn)

(

1

)

對(duì)

流

：

所

謂

對(duì)

流

就

是

在

一

段

線(xiàn)

路

上

有

同

一種

物資出

現(xiàn)

相

對(duì)

運(yùn)

輸

現(xiàn)象(

往返

運(yùn)

輸

)(同一段線(xiàn)

路

上

，

兩

各

方

向

都

有

流

向

)

,

如

左

圖

。甲

乙

兩

地

是

一

種

對(duì)

流

現(xiàn)

象

。

如

果

把

圖

，

就

可

以

避

免

對(duì)

流

現(xiàn)

象

，

從

而

可

20×10=200(噸公里)。(20)(

4

)

不

合

理

的

現(xiàn)

象

1

:

對(duì)

流流

向

圖

改

成

右

以

節(jié)

約

運(yùn)

輸

量1010(10)甲

20右圖左圖甲

20(10)(10)(20)乙乙1010

(e)

不

合

理

的

現(xiàn)

象

2

:

迂

回(2)

迂

回：

當(dāng)收點(diǎn)與發(fā)點(diǎn)之間的運(yùn)輸線(xiàn)路有兩

條或兩條以上時(shí)(即交通圖成圈),如果運(yùn)送的貨物不是走最短線(xiàn)路，則稱(chēng)這種運(yùn)輸為迂回運(yùn)輸。注：當(dāng)交通圖成圈時(shí)，如果流向圖中內(nèi)圈流向的

總長(zhǎng)(簡(jiǎn)稱(chēng)內(nèi)圈長(zhǎng))或外圈流向的總長(zhǎng)(簡(jiǎn)稱(chēng)外圈長(zhǎng))

超過(guò)整個(gè)圈長(zhǎng)的一半就稱(chēng)為迂回運(yùn)輸。例

如某物資流向圖如圖所示。迂

回

運(yùn)

輸

的

判

斷6(4)42(4)左圖顯

然

：

左

圖

為

迂

回

運(yùn)

輸右圖4正

規(guī)

(

最

優(yōu)

)

流

向

圖：

一

個(gè)

最

優(yōu)

的

調(diào)

運(yùn)

方

案

，

它

的

流

向

圖

必

是

無(wú)

對(duì)

流

、

無(wú)

迂

回

的流

向圖，稱(chēng)這種流向圖為正規(guī)流向圖。物資調(diào)運(yùn)的圖上作業(yè)法就是尋找一個(gè)無(wú)對(duì)

流

、

無(wú)迂回的正規(guī)流向圖

。步

驟

如

下

：●

作出

一

個(gè)

無(wú)

對(duì)

流

的

初

始

可

行

方

案

；●

檢

驗(yàn)

有

無(wú)

迂

回●若無(wú)，結(jié)束

；●

否

則

，

調(diào)

整

，

直

到

最

優(yōu)

。(3)、

正

規(guī)

(

最

優(yōu)

)

流

向

圖1、

無(wú)

圈

(

線(xiàn)

狀

)

的

交

通

圖2、

有

圈

的

交

通

圖三

、

圖

上

作

業(yè)

法

的

求

解

過(guò)

程方法

：

供

需

歸

鄰

站1、交通圖無(wú)圈

(現(xiàn)狀)

情形

【

例

】

求最優(yōu)調(diào)運(yùn)方案B?A?A?B?32471As4B?8A?5A?6B?口訣：

抓各端，

各端供需歸鄰站即

：

先

滿(mǎn)

足

端

點(diǎn)

的

要

求

，

逐

步

向

中

間

逼

近

，

直

至

收點(diǎn)與發(fā)點(diǎn)得到全部滿(mǎn)足為止。案例分析D9

4

9

E3103

B528練一練C27AFG5D9C(7)7

G

答案10(10)(8)8B5(7)AF(9)9

E2、

交通

圖有圈情形【

例

】

求

最

優(yōu)

調(diào)

運(yùn)

方

案A?它的原則可歸納為：流向劃右方，對(duì)流不應(yīng)當(dāng)；

里圈、外圈分別算，

要求不

過(guò)半圈

長(zhǎng)；

如若

超

過(guò)半圈長(zhǎng)，

應(yīng)甩運(yùn)量最

小段；反復(fù)求算最優(yōu)方案。第

一

步：

變

有圈

為

無(wú)圈

。方法：

“丟邊破圈”。即丟掉一條邊，破

去

一

個(gè)圈

。注意：

丟

邊時(shí)，

往

往

是

丟

掉圈中

長(zhǎng)

度

最

大

的

邊。如

圖所示解

題

步

驟

：第

一

步

：

“

丟

邊

破

圈

”A?第二步：在無(wú)圈的交通圖上作流向圖。原則：先外后內(nèi)，先端點(diǎn)后中間點(diǎn)，要求

每

個(gè)

邊

都

有

流

向

。

當(dāng)

某

條

邊

無(wú)

流

向

時(shí)

，

必

須

填

上

運(yùn)

輸

量

為

零

的

虛

流

向

。第二步

：

作流向圖A?第三步：檢查有無(wú)迂回。圈BsB?B?A?

的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)=

4

+

4

+

5

=

1

3

>

(

2

1

/

2

)

,

有

迂

回

，

所

以

流

向

圖

不是最優(yōu)流向圖。需要調(diào)整。第四步：對(duì)方案進(jìn)行調(diào)整。方法：找出有迂回圈的流量最小的邊

(去掉的邊

除

外

)

,

改此邊為丟掉的邊

(

邊BsB?),

并

補(bǔ)上

原來(lái)丟掉的邊

(

邊BsA?),

得到新的交通圖。在

此交通圖上做新的流向圖。第

四

步

：

調(diào)

整

方

案A?第五步：對(duì)新方案進(jìn)行檢驗(yàn)。圈BsB?B?A?

的圈長(zhǎng)=4+4+5+8=21,內(nèi)圈長(zhǎng)=4

+

5

=

9

<

2

1

/

2

,

外

圈

長(zhǎng)

=

8

<

2

1

/

2

.

內(nèi)

圈

、

外

圈

的長(zhǎng)度均不超過(guò)圈長(zhǎng)的一半，所以該圈不存在迂

回

。圈A?

B?

B?A?

B?

B?的圈長(zhǎng)=7+2+3+6+4+3=25,

內(nèi)

圈

長(zhǎng)

=

2

+

3

+

6

+

3

=

1

4

>

2

5

/

2

,

有

迂

回

，

所

以流向圖不是最優(yōu)流向圖。需要調(diào)整。第六步：對(duì)方案進(jìn)行調(diào)整。方法：找出有迂回圈的流量最小的邊(去掉的邊

除外),改此邊為丟掉的邊(邊A?B?),

并補(bǔ)上

原來(lái)丟掉的邊(邊B?A?),

得到新的交通圖。在

此交通圖上做新的流向圖。直到所有圈的內(nèi)圈長(zhǎng)

小于二分之一圈長(zhǎng)，外圈長(zhǎng)小于二分之一圈長(zhǎng)，得到最優(yōu)方案。第

六

步

：

調(diào)

整

方

案A?發(fā)收B1B2B3B4B5發(fā)貨量A1347A2422A3145收貨量44462可驗(yàn)證：此方案中無(wú)迂回現(xiàn)象。即為最優(yōu)方案。A

500002663000018016550000600