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

一、简答题

1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧

这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

2． 什么是关于可行流f 的增广链?

【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，

若满足下列条件:

（l ）在弧（2）在弧称是关于可行流f 的一条增广链。 即即中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。 是从v s 到v t ，的一条链，

3． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;

【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，

则最优方案不发生变化。

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

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

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

二、计算题

5． 案例分析:需要多少个服务人员?

某商科技公司的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个服务人员时，其成本最少。

6． 某一运输问题的初始基可行解如表所示，括号内数据为非基变量的检验数，试确定新的基可行解。

表

【答案】选择空格A 2B 3，对其所在回路进行调整，调整量为min （5，30）=5，得新的基可行解如下:

表

7． 某公司需要决定建大厂还是建小厂来生产一种新产品，该产品的市场寿命为10年，建大工厂的投资 费用为280万，建小厂的投资额为140万。10年内销售状况的离散分布状态如下:高需求量的可能性为0.5; 中 等需求量的可能性为0.3; 低需求量的可能性为0.2。公司进行了成本一产量一利润分析，在工厂规模和市场容量的组合下，它们的条件收益如下:

①大工厂，高需求，每年获利100万元;

②大工厂，中等需求，每年获利60万元;

③大工厂，低需求，由于开工不足，引起亏损20万元;

④小工厂，高需求，每年获利25万元（供不应求引起销售损失较大）;

⑤小工厂，中等需求，每年获利45万元（销售损失引起的费用较低）;

⑥小工厂，低需求，每年获利55万元（因工厂规模与市场容量配合得好）。

用决策树方法进行决策。

【答案】构造决策树，并将有关数据标在决策树上，如图所示。

图

建大厂的收入期望值为:1000*0.5+600*0.3-200*0.2-280=360（万元）; 建小厂的收入期望值为:250*0.5+450*0.3+550*0.2-140=230（万元）

计较结果，建大厂为最优方案。