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

一、简答题

1． 简述求解最小费用最大流的赋权网络设置方法。

【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点，

每条边用两条方向相反的有向边代替，各边的权

②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令

2． 简述割平面法的基本思想。

【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。

按如下规则:

二、计算题

3． 某工厂的生产任务最近波动很大，为降低成本宜雇佣临时工，但熟练的生产工人临时难以雇到，培训新 手的费用又高，今后四个月需要工人数量如下表所示:

表

每月超过需要量聘用，每人浪费600元，聘用或解聘费为200元乘上两个月份聘用人数之差的平方。以这四 个月的总花费最小为目标，写出本问题中厂方应如何聘用工人的动态规划的模型。（假定工资按实际工作时间计算，则聘用人数可为分数）

【答案】按月份将问题分为四个阶段，阶段变量k=1，2，3，4，设状态变量s k 为第k 月末的工人数，决策变量u k 表示第k 月招聘或解聘的工人数（招聘为正，解聘为负），

允许决策集合为

，d k 表示第k 个月所需的工人数，状态转移方程为第1个月至第k 个月的最小总花费。

动态规划的基本方程为:

第 2 页，共 64 页 。为

时，，其数值计算如表所示。

表

当时，，其数值计算如表所示

表

当时，，其数值计算如表所示：

表

所以，得到最优解为：

4． 已知A 、B 各自的纯策略及A 的赢得矩阵如表所示，求双方的最优策略及对策值。

表

第 3 页，共 64 页

【答案】在A 的赢得矩阵中第4列优超于第2列，第l 列优超于第3列，故可划去第2列和第3列，得到新的赢得矩阵

对于A 1，第2行优超于第4行，因此去掉第4行，得到

对于A 2，易知无最优纯策略，用线性规划的方法求解，其相应的相互对偶的线性规划模型如下:

利用单纯形法求解第二个问题，迭代过程如表所示。

表

从表中可以得到，第二个问题的最优解为

第 4 页，共 64 页