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

一、选择题

1． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。

A. 松弛变量

B. 多余变量

C. 闭回路

D. 圈

【答案】C

【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。

2． 若f 是G 的一个流，K 为G 的一个割，且f 的流量等于K 的容量，则K 一定是（ ）。

A. 最大流

B. 最大割

C. 最小流

D. 最小割

【答案】D

【解析】网络从发点到收点的各通路中，由容量决定其通过能力，最小割集则是这些路中的咽喉部分，或者叫瓶口, 其容量最小，它决定了整个网络的最大通过能力。

二、计算题

3． 某百货公司去外地采购A 、B 、C 、D 四种规格的服装，数量分别为:A —1500套，B 一2000套，C 一3000 套，D 一3500套。有三个城市可供应上述规格的服装，供应数量为城市I 一2500套，城市II 2500套，城市III —5000套，由于这些城市的服装质量、运价及销售情况不一，预计售出后的利润（元/套）也不同，详见表1。 请帮助该公司确定一个预期盈利最大的采购方案。

表1

【答案】 用10减去利润表上的数字，使之变成一个运输问题，如表2所示。

表

2

利用伏格尔法求出表37运输问题的初始解，求解结果见表3。

表

3

利用位势法求出表4中各空格的检验数，如表4。

表

4

在表4中，。所以，表3中的运输方案不是最优调运方案，需进一步调整。利用闭

表5

回路 法进行调整，结果如表5所示。

利用位势法求出表40中各空格的检验数，如表6所示。

表

6

由表6可知，所有空格处的检验数均为非负。所以，表40中的运输方案即为此问题的最优调运方案， 最小运价为72000元。

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

表

1

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

【答案】设人为第A i 年的正常生产能力，A i ‘为第i 年的加班生产能力; B j 为第j 年的需求订货，S 为因积压而产生的供货能力。因为产大于销，所以虚拟一个销地B 4，于是可构造如表2的运价表。问题变为求解表1 的最优调运方案。

表2 单位：千万元