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

一、简答题

1． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。

【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。

（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。

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． 案例分析:需要多少个服务人员?

某商科技公司的MIS 中心处理本公司信息系统的维护服务。公司其他部门职员打电话到信息中心进行咨询 和服务请求，不过如果恰巧所有服务人员都在忙的时候，该职员就必须等待。该中心每小时平均接受到40个服 务请求，服务请求的到达服从泊松分布。每个请求的平均服务时间是3分钟，且服从负指数分布。

信息中心服务人员每小时的平均工资是巧元。公司职员每小时为公司创造的收益是25元。（如果该职员在等待或正在接受MIS 维护服务，则这段时间内该职员不为公司创造任何收益）。

我们己经通过软件计算出服务中心的服务人员个数与等待接受MIS 维护服务的平均职员数（不包括正在接 收MIS 维护服务地职员）以及平均等待时间（不包括接受MIS 维护服务的时间）之间的关系，如表:

表

请分析下面两个问题:

（l ）如果公司经理希望职员等待MIS 维护服务（排队等待和服务等待的平均时间）不要超过5分钟，则该信息中心最少需要聘用多少个服务人员?

（2）如果公司经理考虑聘用服务人员的成本以及因为等待或正在接受MIS 维护服务造成的企业损失成本，使两者成本之和尽量小，则此时该信息中心需要雇佣多少个服务人员。

【答案】（l ）要求等待MIS 维护服务时间小于等于5分钟，已知平均服务时间是3分钟，故服务时间是2分钟，约是0.0333小时，查上表可知，该信息中心最少需要聘用服务人员3人。

（2）此问题属于M/M/C模型

查表可知不同的c 对应的Lq ，Wq ，从而得Ls ，Ws ，如表所示:

表

则总成本z 二15×C+25×Ws ×Ls 在不同的c 对应的数值如表所示:

表

经比较可知该信息中心需要雇佣3个服务人员时，其成本最少。

4． 用大M 法（极小化为标准形式）求解得某极小化线性规划问题的最优单纯形表如表所示。

表

表中x 4为松弛变量、x 5为剩余变量、x 6和x 7为人工变量。试回答如下问题:

（l ）计算C 1和C 2的数值;

（2）求使最优基不变的C 1、C 2的关系;

（3）求原问题的三个右端常数。

【答案】（l ）由最优单纯形表得到下列关系式为:

（2）若最优基不变，则有下列关系式:

（3）

解得原问题的三个右端常数为

5． 某公司兴建一座港口码头，只有一个装卸船只的位置。设船只到达的间隔时间和装卸时间都服从负指数 分布，预计船只的平均到达率为3只/天，船只到港后如不能及时装卸，停留一日公司将损失1500元。现需设 计该港口码头的装卸能力（即每日可以装卸的船只数），已知单位装卸能力每日平均生产费用为2000元，问装卸 能力为多大时，每天的总支出最少? 在此装卸能力之下，求:

（l ）装卸码头的利用率;

（2）船只到港后的平均等候时间;

（3）船只到港后总停留时间大于一天的概率。

【答案】设装卸能力为刀，公司的支出

则

令所以解得时，每天的总支出最少。

码头的利用率为