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

一、计算题

1． 考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题），其中变量x 1，x 2取整数。该 问题的求解由子问题1开始，如图所示。

图

请回 【答案】

（1）在当前状态下，如何对整数规划的最优解进行定界。

（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束? 附加的两个约束分别是什么?

答:（l ）设整数规划的最优目标值为Z*，则对其定界范围为:

（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为:

2． 某箭线式网络计划如图（时间单位:周）

图

（l ）求项目完成工期及关键线路。 （2）填写表。

表 单位：周

【答案】（l ）线路有

故项目完工期为T=16。 关键路线为（2）填写表格如表。

表

3． 某公司现拥有资金3万元。现做今后3年的投资计划每年允许投资额不能超过5万元. 若某年投资x 元， 当年有l/3可能性损失x 元，而有2/3可能性增收x 元。现要确定能使3年后将拥有资金超过5万元的可能性 最大的投资力案

试结合题中说明，当用动态规划方法求解时的下列基本概念（不必计算）: （l ）阶段变量:

（2）状态变量、状态集台: （3）决策变量、允许决策范围 （4）状态转移关系: （5）递推方程。

【答案】（l ）阶段变量k :按三年的投资计划，分为3个阶段; （2）状态变量s k :表示第k 年初投资时剩余的全部资金金额 状态集合为:s 1=3

（3）决策变量x k :表示第k 年初用于投资的金额（4）状态转移关系为:

（5）递推方程:

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

表

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

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

②状态变量S K ，表示可以派往第k 个部位的巡逻队数目; ③决策变量x k ，表示派到第k 个部位的巡逻队数目; ④状态转移方程:⑤阶段指标函数⑥递推方程:

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