表上作业法在线视频

运输是物流的重要职能之一

在实践中

有一类问题我们叫做运输问题

研究如何制定最合理的物资调运方案

使总运费最低

具体如下

已知有m个产地

Ai（i=1，2，...，m）

可以供应某种物资 其供应量或者说产量分别为ai

同时 有n个销售地

Bj（j=1，2，...，n)

其销量 也就是需求量

分别为bj

从A到B的单位物资运价为Cij

用Xij表示 从产地Ai到销售地Bj的调运量

那么 在产销平衡的条件下

也就是说 所有产地

可供调运的物资总量

与所有销售地所需的物资总量相等

要确定总运输费用最小的调运方案

这就是产销平衡的运输问题

这类问题 可以用下面的数学模型表示

目标函数是总的费用最小

有两个约束条件

一是 从每一个产地

调运到各个销售地的物资之和

正好等于 该产地可供调运的物资量

二是 每一个销售地收到的物资之和

正好等于该销售地的需求量

这类问题 是一个线性规划问题

而且 其系数矩阵中

每一列 只有两个元素为1

其余系数均为零

因此 可以用一种特殊的方法来解决

也就是表上作业法

采用表上作业法解决这类运输问题

有三个步骤

一、寻找一个初始可行解

二、检验解的最优性

三、调整可行解

我们通过一道具体的例题来说明

某公司设有三个加工厂

A1 A2和A3

以及四个门市部门

B1 B2 B3和B4

从各个加工厂

到各门市部的单位运价Cij

如表一所示

各加工厂的产量

和各门市部门的销量如表二所示

在满足各门市部销售需求的情况下

如何进行调运

使总的运输支出最少呢

显然 这是一个产销平衡的运输问题

首先 我们通过最小元素法

来找出一组初始可行解

最小元素法的基本思想是

就近 尽量满足供应

从单位运价表上 运价最低的元素

确定运输的供应关系

以此类推

直到给出一个初始可行方案为止

我们看表三

也是一张运价表

在运价表中找出最小的数值

如果有几个同为最小值

那么任取其中一个

表三中 C21最小 数值为1

这表示 首先应由A2 尽量满足B1的需求

最大可能供应量X21等于3

在方案表中 X21处填上3

表示由A2运3个单位的产品到B1

此时 B1的需求已经被满足

因此 运价表中的第一列数字不起作用

应该划去 并标注①

然后在运价表中 未划去的元素中找最小运价

C23=2

A2剩余的产量 应优先供应给B3

B3需要5个单位

A2只剩一个单位

因此 X23=1

在方案表中 X23的位置填上1

表示由A2运输一个单位的产品到B3

此时 A2所生产的产品

已经全部供应完毕

运价表中 A2所在行的运价也不在起作用

应该划去 并标注②

按照上面的做法 一直做下去

就可以得到表示

此时 在运价表中只有A1 B4对应的运价10 没有划掉

而B4还有3个单位的需求

为了满足供需平衡

所以 最后在平衡表上对应A1 B4处 填上3

这样就得到了初始可行方案表5

表5中 有数字的表格中

数字Xij表示 从Ai到Bj的运量

空格表示没有运量

要注意的是

用最小元素法编制初始调运方案

这里的最小 是指局部而言的

就整体考虑的运费 不一定是最小的

因此 需要检验初始可行解的最优性

我们采用闭回路法

检验初始可行解的最优性

具体步骤是

对表5中的每一个空格

确定一条由该空格出发的闭回路

闭回路必须由水平和垂直直线组成

回路的顶点除了该空格以外

都是有数的

比如 从X11出发

可以构建一个

经过X13 X23和X21 回到X11的闭合回路

其中只有X11是空格

其余的顶点都是有数格

构造闭合回路后

我们需要计算空格顶点的检验数

检验数 等于闭合回路上奇数顶点的运价之和

减去偶数顶点的运价之和

比如X11的检验数为 C11+C23-C13-C21=1

同理 可以计算出X31的检验数为10

以此类推 可以计算出所有空格的检验数

如表7所示

计算检验数的意义是什么呢

每一个空格都是一个非基变量

检验数表示非基变量增加一个单位

使目标函数值增加的变量

运输问题中

目标函数值要求最小化

所以 当所有的检验数都大于或者等于零时

调运方案就是最优的

否则不是

表7中X24的检验数为-1

小于零

因此 现在的可行解不是最优的

该如何将可行解调整到最优呢

既然检验数非负意味着调整运量会增加运费

那么 只需要调整检验数为负数的空格运量就可以

如果有多个检验数为负

就从绝对值最小的负检验数开始

沿着它的闭回路进行调整

在保持方案可行的条件下

尽量增加空格上的运量

比如 对闭回路X24 X14 X13 X23 X24

如果在空格X24上增加Y个单位

必须在顶点X14上减少Y个单位

在X13上增加Y个单位

在X23上减少Y个单位

才能保证平衡

构成一个新的可行解

由于X23等于1 X13等于3

空格X24上最多能增加Y=1个单位

一般来说

调整量为闭回路上 偶数顶点上运量的最小值

调整的结果如表8所示

经过调整后 要重新计算检验数

结果如表9所示

现在所有的检验数 均为非负数

说明现在的调运方案 是最优的

以上 我们通过一道例题

介绍了如何采用最小元素法和闭回路法

解决产销平衡的运输问题

这类问题的模型

不仅适用于物质运输

也适用于其他类似的问题

课后大家可以思考一下

是否可以采用同样的方法

解决产销不平衡的运输问题呢

又如何解决呢

本次课到此结束

谢谢大家