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

一、计算题

1． 某公司有五台新设备，将有选择地分配给三个工厂，所得的收益如表所示

表

表中---表示不存在这样的方案。请用动态规划求出收益最大的分配方案。

【答案】将问题按工厂的个数分为3个阶段，

设s k 表示为分配给第k 个工厂到第n 个工厂的新设备数目，

x k 表示为分配给第k 个工厂的新设备数目， 则

为分配给第k+l个工厂至第n 个工厂的设备数目，

表示为x k 个新设备分配给第k 个工厂所得的收益，

表示为s k 个设备分配给第k 个工厂到第n 个工厂时所得到的最大收益。

因而可写出逆推关系式为

下面从最后一阶段开始向前逆推计算:

第三阶段:

表

第二阶段：

表

第一阶段：

表

得到最优分配方案为:分配给工厂1两台新设备; 工厂3三台新设备，可得最大收益为16。

2． 在如图所示的网络中，每弧旁的数字是

（l ）确定所有的截集;

（2）求最小截集的容量;

（3）证明指出的流是最大流。

。

图

【答案】（l ）确定所有的截集与对应的容量，如表所示。

表

（2）由表可知，在此可行流中的最小截集的容量为

。

（3）根据最大流量最小截量定理，其最大流f 的流量为5。

3． 分析下列参数规划中当t 变化时最优解的变化情况。 （1）

*

（2）

（3）

（4）

【答案】 （1）在约束条件中分别加入松弛变量x 4，x 5，x 6，并将模型化为标准型为

令t=0，并利用单纯形法进行求解，如表所示。

表