当前位置：问答库＞考研试题

一、计算题

1． 图中V s 表示仓库，V t 表示商店. 现要从仓库运10单位的物资到商店，应如何调运才能使运费，其中C ij ，表示交通线上运输能力限制，b ij 最省（图 中弧表示交通线，弧旁的数字为（C ij ，b ij ）表示单位运价）。

图

000

【答案】（l ）从f （）={0}开始，做L （f （））如图1，用Dijkastra 算法求得L （f （））网络中最短

路为整，结果见

，在网络中相应的可增广链，如图2所示:

上用最大流算法进行流的调

图1

图2

（2）作

（2），

如图1，找出最短路为，在网络内相应的可增广链上进行调整，得到流f

如图2所示:

图

1

图2

（3）作得到 流

与如图1，找出最短路为，如图2所示

，在网络内相应的可增广链上进行调整，

图

1

图

2

即为所求的最小费用流。

2． 设某工厂每年需用某种原料1800吨，不需每日供应，但不得缺货。设每吨每月的保管费为60元，每次订购费为200元，试求最佳订购量。

，按E.Q.Q 计算Q*得

【答案】由题意知，该模型为“不允许缺货，生产时间很短”

所以最佳订购量为32顿。

3． 某运输问题，两个产地，三个销地，两个中转站，有关数据如图所示，中转站3的容量限制为800。

（l ）建立使总运输成本之和最小的调运数学模型。 （2）试将问题转化成可用表上作业法计算的调运表。