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

一、简答题

1． 试写出标准指派问题的线性规划问题。

【答案】

A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:

2． 试写出求解最短径路的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）。

二、计算题

3． 某工程的各工序的清单及直接费用增长率如表所示。

表

（l ）画出双代号（箭线式）网络图，在图上计算各工序的时间参数; （2）标出关键路线，总工期是多少?

（3）若将工期限制为33天，应压缩哪几个工序的工时，各压缩几天? 为什么?

【答案】（l ）画出双代号网络图，并在图上计算个工序的时间参数（前者为工序最早开始时间，后者为工序最迟 结束时间）如下:

图

（2）关键路线为

总工期为37天。

（3）要将工期限制为33天，则要缩短关键路线的长度。关键路线中B ，D ，F , G , H 中，B 的直接费用增长率最 小，首先缩短B 的工时1天，F 、D 的直接费用增长率次之，所以二者共缩短3天即可达到目标。于是优化方案 有两个:

①缩短B 工序1天，缩短F 工序3天;

②缩短B 工序3天，缩短F 工序2天，缩短D 工序l 天。

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

表

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

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

②状态变量S K ，表示可以派往第k 个部位的巡逻队数目; ③决策变量x k ，表示派到第k 个部位的巡逻队数目; ④状态转移方程:⑤阶段指标函数⑥递推方程:⑦边界条件:逆序求解。 当k=4时

，

表

如表所示。

表示第k 阶段的预期损失;

当k=3时，

表

如表所示。

当k=2时

，

表

如图所示。

当k=1时

，

表

如表所示。