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

一、计算题

1． 某一警卫部门共有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时

，

表

如表所示。

因此得最优 解：

即最优方案为A 部位4支，B 部位2支，C 部分2支，D 部位4支，预计损失最小为97单位。

2． 某公司初步选定6个人去完成4项任务，由于个人和技术专长的不同，他们完成4项任务所获得的收益 如表所示，且规定每个人只能完成一项任务，一项任务只能由一个人来完成，具体完成任务的收益如表 所示，求使总收益最大的指派方案

表

【答案】先将该问题的最大利益改为最小化指派问题，找出最大元素13减去每一个元素，得到最小化指派问题， 但还是一个非标准形式的指派问题，再添加两个虚拟人物，则改为的指派问题矩阵为:

对C’加圈，得到，

对C 进行打钩，能覆盖得到6个独立元素，得到，

得到最优方案:第一个人和第二个人都不做任务，第三个人做第二项任务; 第四个人做第三项任务; 第五个 人做第一项任务; 第六个人做第四项任务，能获得最大利益，为43.

3． 在某单人理发店顾客到达为泊松流，平均到达间隔为20 min，理发时间服从负指数分布，平均时间为 15 min。求:

（l ）顾客来理发不必等待的概率; （2）理发店内顾客平均数;