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

一、简答题

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

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

2． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界

; 。分支定界法就是将B 的可行域分成

子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。

3． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。

【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。

（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。

（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。

4． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。

（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

当存在两个以

上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

二、计算题

5． 某整数规划模型如下:

T

其最优解为x=（18/7，19/7）。试用分枝定界法写出后续的两个分枝模型。

【答案】选择x l =18/7进行分支，问题B

l

则得问题B l ，B 2

问题B

2

6． 用逐次逼近法求解下述问题:

【答案】逐次逼近法的基本思想是:先保持一个变量不变，对另一个变量实现最优化，再交替固定，以迭代的形式反复进行，直至达到某种要求为止。

（1） 先设

，固定

利用动态规划方法求解:

，对y 进行求解，则问题转化为

，必须计算f 2（30）, f2（25）, f2（20）, f2（15）, f2（10）, f2（5）和f 2（0）要求出f 3（30）如

同理，可得出

要求出f 2（30）, f2（25）, f2（20）, f2（15）, f2（10）, f2（5）和f 2（0）, 就必须先计算出f 1（30）, f1（27）, f1（24）, f1（25）, f1（21）, f1（22）, f1（20）, f1（19）, f1（18）, …, f1（1）和f 1（0）。计算如下：注意符号[ ]表示取整数。