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

一、简答题

1． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流

（l ）容量限制条件:对每一弧（v i ，v j ）

对于起点Vs ，记

对于终点V t ，记 （2）平衡条件 对于中间点，流出量=流入量，即对每个

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。

2． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

二、计算题

3． 某造船厂根据合同要从当年起连续三年末各提供三艘规格型号相同的大型客货轮，已知该厂在三年内 生产大型客货轮的能力及每艘客货轮的成本如表1所示。

表

1

已知加班生产时，每艘客货轮成本比正常生产时高出70万元。又知造出来的客货轮如当年不交货，每艘每 积压一年造成积压损失为40万元。在签订合同时，该厂已储存了两艘客货轮，而该厂希望在第三年末完成合同 后还能储存一艘备用。问该厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用 加积压损失为最少?

【答案】设人为第A i 年的正常生产能力，A i ‘为第i 年的加班生产能力; B j 为第j 年的需求订

货，S 为因积压而产生的供货能力。因为产大于销，所以虚拟一个销地B 4，于是可构造如表2的运价表。问题变为求解表1 的最优调运方案。

表2 单位：千万元

第一步:用伏格尔法求初始可行解，求得的初始解，如表3所示。

表

3

第二步: 用位势法进行最优解的检验。在对应于表3的数字格处填入单位运价，并增加一行一列，在行 中填入vj ，在列中填入

并依据。令u 1=0，按照表4 求出所有的，和v j ，计算所有空格处的检验数，计算结果如表4所示。

在表3中，存在两个非基变量的检验数小于0。所以，表3中的运输方案不是此问题的最优调运方案， 需进行进一步调整。

第三步:利用闭回路法进行解的改进。

从表4中的空格（A 3，B 3）出发作一闭回路，利用闭回路法进行调整，得到的结果如表5所示。

表

5

第四步:重复第二、三步，得到新的调运方案，如表6所示。

表6