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

一、简答题

1． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。

【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。

2． 什么是关于可行流f 的增广链?

【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若

满足下列条件: （l ）在弧（2）在弧称

是关于可行流f 的一条增广链。

即即

中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。

是从v s 到v t ，的一条链，

二、计算题

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

表

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

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

允许决策集合为

，d k 表示第k 个月所需的工人数，状态转移方程为

第1个月至第k 个月的最小总花费。

动态规划的基本方程为:

时，

，其数值计算如表所示。

表

第 2 页，共 50 页

。为

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

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

所以，得到最优解为：

4． 计算从A 到B 、C 和D 的最短路线。已知各段路线的长度如图所示。

图

【答案】设阶段变量k=1，2，3，4，依次表示4个阶段选择路线的过程; 状态变量s k 表示第k 阶段初所处的位置; 决策变量x k 表示第k 阶段初可能选择的路线; 最优值函数点A 到第k 阶段状态S k 的最短距离，则有

第 3 页，共 50 页

表示从起

同理，

于是，从A 到B 、C 和D 的最短路线分别为： A 到B 的最短路线为：A 到C 的最短路线为：A 到D 的最短线路为：

5． 已知运价表如表所示:

表

。 或是，

。

求解总运费最小的最优解（注:求解方法不限，要求写出必要的计算过程）。

【答案】此问题是一个产销不平衡的运输问题，首先增加一个假想的产地戊，其产量为30，运价为0，化为产销平衡问题如表所示:

表

采用伏格尔法，求得初始解如下:

表

采用位势法检验，得下表:

表

第 4 页，共 50 页