图上作业法课件

图

上

作

业

法本节课的主要内容编

制

交

通

图

和

流

向

图对

流

向

图

的

检

验图上作业法的求解过程(重点)在

求

解

最

佳

运

输

方

案

时

，

用

吨

公

里

作

为

度

量

单

位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。在

铁

路

、

公

路

等

交

通

部

门

经

常

使

用

这

种

方

法

决

策最优运输问题，这种方法被称为图上作业法。在

运

输

中

，

若

使

用

同

一

种

运

输

工

具

，

则

运

费

的

计

算

往

往

仅

与

运

送

物

资

的

多

少

及

里

程

有

关

。

因

此

，

在

求

最

佳

的

运

输

方

案

时

，

用

吨

公

里

作

为

度

量的标准比用运费作为度量标准更加方便、实

用

。一、图上作业法●

交

通

图●反

映

发

点

(

产

地

)

与

收

地

(

销

地

)

及

交

通

线

路

及

其

距离组成的图形。●

发点用

“O”

表示，发出货物的数量记在

“O”

之

内

(

单

位

：

吨

)●收地(销地)用“□”表示，收取货物的数量记在

“

□

”

之

内

(

单

位

：吨

)·两点之间的线路长度记在交通线路的旁边。二

、

编

制

交

通

图

和

流

向

图1、交通图A

103

B552F

8D9

4

9

E3口交通图举例C2了G1、交通图300001801655000025280000G115393317C500003000020000口交

通

图

举

例A

5000026660000239I50000EF349120HB流向图：在交通图上表示物资流向的图被称为流向图。在

图中每个发点吨数全部运完，每个收点所需吨数均已满足。流向用箭头画在两点连线的右方。(即：站在发点，看向收点，右手所在的一侧或

从发点到收点，顺时针方向的一侧)2

、流向图2

、流向图口

流

向

图■

物资

调

运的

方

案

可以用

流向图

表

示点A到

收

点B的输

量

，

用

括

号

括

起

。C10(10个(8)8(7)7

G发

运B5AF(7)(9)9

ED9关于流向图的一些规定箭头必须表示物资运输的方向流量写在箭头的旁边，加小括号。流向不能直接跨越路线上的收点、发点、交叉点

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

弧上的多条流向必须合并。除端点外，任何点都可以流进和流出2

、流向图2

、流向图A

50000(50000)E

30000(20000)F

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

含

有

圈

的

流

向

图I50000(70000)(50000)(30000)H

300008000020000CB含有圈的流向图的补充规定顺时针方向的流向必须画在圈的内侧，称为内圈

流向逆

时

针

方

向

的

流

向

必

须

画

在

圈

的

外

侧

，

称

为

外

圈

流向2

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

内圈流向内圈流向、外圈流向举例图：外圈流向4在

物

资

运

输

中

，

把

某

种

物

资

从

各

发

点

调

到

各

收

点

的调运方案是很多的，但我们的目的是找出吨—

公里数是最小的调运方案。这就要注意在调运中

不要发生对物流运输和迂回运输，

因此，我们在

制定流向图时，就要避免它的出现。二

、

对

流

向

图

的

检

验

(

1

)

对

流

：

所

谓

对

流

就

是

在

一

段

线

路

上

有

同

一种

物资出

现

相

对

运

输

现象(

往返

运

输

)(同一段线

路

上

，

两

各

方

向

都

有

流

向

)

,

如

左

图

。甲

乙

两

地

是

一

种

对

流

现

象

。

如

果

把

图

，

就

可

以

避

免

对

流

现

象

，

从

而

可

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

4

)

不

合

理

的

现

象

1

:

对

流流

向

图

改

成

右

以

节

约

运

输

量1010(10)甲

20右图左图甲

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

(e)

不

合

理

的

现

象

2

:

迂

回(2)

迂

回：

当收点与发点之间的运输线路有两

条或两条以上时(即交通图成圈),如果运送的货物不是走最短线路，则称这种运输为迂回运输。注：当交通图成圈时，如果流向图中内圈流向的

总长(简称内圈长)或外圈流向的总长(简称外圈长)

超过整个圈长的一半就称为迂回运输。例

如某物资流向图如图所示。迂

回

运

输

的

判

断6(4)42(4)左图显

然

：

左

图

为

迂

回

运

输右图4正

规

(

最

优

)

流

向

图：

一

个

最

优

的

调

运

方

案

，

它

的

流

向

图

必

是

无

对

流

、

无

迂

回

的流

向图，称这种流向图为正规流向图。物资调运的图上作业法就是寻找一个无对

流

、

无迂回的正规流向图

。步

骤

如

下

：●

作出

一

个

无

对

流

的

初

始

可

行

方

案

；●

检

验

有

无

迂

回●若无，结束

；●

否

则

，

调

整

，

直

到

最

优

。(3)、

正

规

(

最

优

)

流

向

图1、

无

圈

(

线

状

)

的

交

通

图2、

有

圈

的

交

通

图三

、

图

上

作

业

法

的

求

解

过

程方法

：

供

需

归

邻

站1、交通图无圈

(现状)

情形

【

例

】

求最优调运方案B₁A₁A₂B₂32471As4B₄8A₃5A₄6B₃口诀：

抓各端，

各端供需归邻站即

：

先

满

足

端

点

的

要

求

，

逐

步

向

中

间

逼

近

，

直

至

收点与发点得到全部满足为止。案例分析D9

4

9

E3103

B528练一练C27AFG5D9C(7)7

G

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

E2、

交通

图有圈情形【

例

】

求

最

优

调

运

方

案A₂它的原则可归纳为：流向划右方，对流不应当；

里圈、外圈分别算，

要求不

过半圈

长；

如若

超

过半圈长，

应甩运量最

小段；反复求算最优方案。第

一

步：

变

有圈

为

无圈

。方法：

“丢边破圈”。即丢掉一条边，破

去

一

个圈

。注意：

丢

边时，

往

往

是

丢

掉圈中

长

度

最

大

的

边。如

图所示解

题

步

骤

：第

一

步

：

“

丢

边

破

圈

”A₂第二步：在无圈的交通图上作流向图。原则：先外后内，先端点后中间点，要求

每

个

边

都

有

流

向

。

当

某

条

边

无

流

向

时

，

必

须

填

上

运

输

量

为

零

的

虚

流

向

。第二步

：

作流向图A₂第三步：检查有无迂回。圈BsB₄B₃A₂

的圈长=4+4+5+8=21,内圈长=

4

+

4

+

5

=

1

3

>

(

2

1

/

2

)

,

有

迂

回

，

所

以

流

向

图

不是最优流向图。需要调整。第四步：对方案进行调整。方法：找出有迂回圈的流量最小的边

(去掉的边

除

外

)

,

改此边为丢掉的边

(

边BsB₄),

并

补上

原来丢掉的边

(

边BsA₂),

得到新的交通图。在

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

四

步

：

调

整

方

案A₂第五步：对新方案进行检验。圈BsB₄B₃A₂

的圈长=4+4+5+8=21,内圈长=4

+

5

=

9

<

2

1

/

2

,

外

圈

长

=

8

<

2

1

/

2

.

内

圈

、

外

圈

的长度均不超过圈长的一半，所以该圈不存在迂

回

。圈A₃

B₁

B₂A₁

B₃

B₄的圈长=7+2+3+6+4+3=25,

内

圈

长

=

2

+

3

+

6

+

3

=

1

4

>

2

5

/

2

,

有

迂

回

，

所

以流向图不是最优流向图。需要调整。第六步：对方案进行调整。方法：找出有迂回圈的流量最小的边(去掉的边

除外),改此边为丢掉的边(边A₁B₃),

并补上

原来丢掉的边(边B₁A₃),

得到新的交通图。在

此交通图上做新的流向图。直到所有圈的内圈长

小于二分之一圈长，外圈长小于二分之一圈长，得到最优方案。第

六

步

：

调

整

方

案A₂发收B1B2B3B4B5发货量A1347A2422A3145收货量44462可验证：此方案中无迂回现象。即为最优方案。A

500002663000018016550000600