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

一、简答题

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

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

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

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

即即

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

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

2． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?

【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。

二、计算题

3． 设有三种资源，每单位的成本分别为a ，b ，c ，给定的利润函数为ri （xi ，yi ，zi ）（i=1，2，…，n ），现有资金为，应购买各种资源多少单位分配给n 个行业才能使总利润最大，试给出动态规划的公式，并写出它的一维递推关系式。

【答案】由题意，可建立该问题的数学模型为:

按n 个行业划分为n 个阶段。阶段变量k=l，2，…，n ，第k 阶段为第k 个行业分配资源; 状态变量

为第1至第k 个行业的总金额; 决策变量（x k , y k , z k ）为第k 个行业所用三种资源的数

; 最优值函数

在状态

下从第1

量; 状态转移方程为:

阶段至第k 阶段的最大利润。

动态规划的一维递推关系式为:

4． 试求解下列线性规划问题:

将本问题的目标变成maxz=-xl +x2，约束条件不变，何为其解? 【答案】（1）用图解法可得图

由图形可知，在（0，l ）处，-x 1+x2取得最大值为1。 故最优解为x 1=0，x 2=1，目标函数值为z=1。 （2

）当目标函数变为故最优解为x 1+x2=1

即

，由于约束条件不变，即为上图中所示的阴影部分，

故目标函数值为下z=l。

由x 1+x2=0可 得，目标函数与边界直线x 1+x2=0平行。

5． 下表给出了12种工件在设备A 和B 上的加工时间，试求:

（l ）若所有工件都先在设备A 上加工，再在设备B 上加工，试确定使总加工时间最短的工件加工顺序，并计算总加工时间;

（2）若工件8~12先在设备B 上加工，再在设备A 上加工，其他条件同上，试设计一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。

表

【答案】（l ）采用启发式算法进行计算，计算过程如下表所示。

由上表可以看出，总加工时间最短的工件加工顺序为 4→8→0→5→1→2→7→6→9→1→12→3

总加工时间为（2+3+3+4+6+8+12+7+9+5+10+11）+4=84。 （2）可设计如下启发式算法: ①②③

④将A j ，B j 删去，即不再考虑己排好加工顺序的工件j ； ⑤转入步骤②，直至步骤②中的工件加工时间表变成空集。 故设备A 最优加工顺序为7→2→5→6→l →3→4→12→9→1→10→8 设备B 最优加工顺序为12→9→11→10→8→7→2→5→6→1→3→4 总加工时间为（12+8+4+7+5+11+2）+（10+9+6+3+3）=49+31=80。

6． 试用SUMT 外点法求解

【答案】原非线性规划问题可改写为: