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

一、简答题

1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

2． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若

当且仅当为

最优解。

分别是原问题和对偶问题的可行解。那么

，

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

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

（2）若

和

和

是对策G 的两个解，则是对策G 的两个解，则

。

和

也是对策G 的解。

【答案】（1）因为是G 的解，所以

①

同理，因为是G 的解，所以

②

由不等式①可知

③

由不等式②可知

由不等式③与不等式④可知

（2）由（1）证明过程中不等式③和不等式④可知即也是解。 6． 设

是正定二次函数

。试证:若

关于Q 共扼

分别

在两条平行

，

故

④

，即可知

。

于方向P 的直线上的极小点，则方向p 与方向

【答案】因为则有从而又由于则有

分别是f （x ）在两条平行于方向P 的直线上的极小点， ，

7． 对于单服务台情形，试证: （1）定长服务时间长服务时间是负指数服务时间的一半。

【答案】对于排队系统，

，是负指数服务时间的一半; （2）定

当k=l时，则

变成M 分布，即上式指标变成M/M/1排队系统指标，即

当k →∞时，则

分布变成D 分布，即上式指标变成M/D/l排队系统指标，即

所以，

定长服务时间时间

的一半。

，是负指数服务时间的一半; 定长服务时间是负指数服务

三、计算题

8． 某软件公司可承揽四个软件开发项目，每一项目均由A ，B ，C ，D 四个模块中的不同模块构成。对于 项目中的共有模块，只需研发一次就可以为所有需要的项目服务. 各项目售价与模块构成及各模块研发成本如表1 、表2所示. 那么这家公司应选择承揽哪些项目才能使利润最大化? 试就这一问题建立相应的数学模型。

表

1

表

2

【答案】设

9． 某一警卫部门共有12支巡逻队，负责4个要害部门的警卫巡逻。对每个部位可以考虑派出2~4支巡逻 队，并且由于派出巡逻队的数目不同，各部位可能造成的损失会有差别，具体数字如表所示:

表

问该警卫部门应往各部位分别派多少巡逻队，总的预期损失为最小。要求明确表述出状态变量，决策变量，并写出状态转移方程和动态规划基本方程。

【答案】该问题可以看成是4阶段的决策问题，采用动态规划的逆序解法进行求解。

①分阶段k=l，2，3，4

②状态变量S K ，表示可以派往第k 个部位的巡逻队数目;