《运筹学》2008-2009学年第一学期期末考试试卷(B)

《运筹学》2008—2009学年第一学期期末考试试卷（B）

时间：2小时

班级： 学号： 姓名： 成绩：

题次 分数 得分 一 10 二 30 三 25 四 35 总 分 100 一、单选题（在以下各题的备选答案中只有一个是正确的，请将你选择的正确答案编号填在以下表格中）（每小题2分，共10分）

1 2 3 4 5 1、以下图1是某费用最小化线性规划问题上机求解后的输出结果，若该问题第1个约束条件所对应的资源增加了2个单位时，这时目标函数的值应（ ）。

(图1)

A. 增加到11 B. 增加到10 C. 减少到8 D. 减少到7 2、在目标规划中，如果要求某一软约束的实现值不超过目标值，则相应的偏离变量应满足（ ）。

A.d0,d0 B.d0,d0 C.d0,d0 D. d0,d0 3. 设T是网络N中的一棵最小生成树，如果将N中任意一条不在树T上的边a添加到树T上，则树T中（ ）。

A. 不形成圈 B. 形成一个圈且a是该圈中权最大的边

1

C. 形成多个圈 D. 形成一个圈且a是该圈上权最小的边 4. 对于一台机器8个零件的排序问题，按照加工时间排加工顺序，若要使各个零件的平均停留时间为最少，则应（ ）

A. 将加工时间最多的零件排在最前面 B. 将加工时间最少的零件排在最前面 C. 将加工时间越多的零件排在越前面 D. 将加工时间越少的零件排在越前面

5. 在非确定型决策中，从最差的估计出发来选择方案时，应采用（ ）。 A. “后悔值”准则 B. 最大最大准则 C. 乐观系数准则并且取其乐观系数为零 D. 悲观准则

二、建模题（每小题10分，共30分）

1、考虑一运输问题，有关的单位运价（元/吨）如表1所示：

表1

销地 产地 B1 B2 供应量（吨） A1 25 30 30 A2 18 32 40 A3 28 23 55 需求量（吨） 50 60 问应如何调运可使总运输费用最小？即该问题的产销平衡表应为：

产销平衡表

销地 产地 供应量（吨） 需求量（吨）

2

2、设某物流公司根据业务的需要计划在华南地区五个城市新建配送中心

Aj(j1,2,,5)，它们所需资金分别为：150、300、250、280

和350万元，现仅

有资金总额1000万元。据估计若A1，A2，A3，A4，A5建成后每年可获利分别为：35、20、28、38和46万元，试建立数学模型决定应修建哪几个配送中心使投资总额不超过现有资金总额，并且使配送中心建成后每年获得的总利润最大？

3、某计算机工厂生产A、S两种微机，需工序Ⅰ、Ⅱ加工，有关数据如下表：

产品 工序 工序Ⅰ(h/台) 工序Ⅱ(h/台) 利润(元/台) A 5 2 350 S 7 5 500 每周最大加工能力 130h 85h 工厂经营目标为：

首先，每周总利润不低于20,000元；

其次，合同要求，A型机每周至少生产20台，S型机每周至少生产35台； 试建立目标规划的数学模型？

3

三、计算题（共25分）

1、（10分）假设以下图2中的点表示居民小区，各点之间的连线表示各居民小区之间的道路，连线上的数字为道路的长度（单位：公里），若连接各居民小区的有线电视网络需沿其道路旁修建，试用破圈法寻找使这8个居民小区相连接的最小费用有线电视网络图，并将其用双线标在图2上（请写出求解过程）。如果假设铺设有线电视网络的费用为10000元/公里，试问上述有线电视网络的最小建设费用为多少？

图2

4

2、（15分）设某排污管道网络如图3所示，网络上的弧表示排污管道，弧上的数字（fij ，Cij）表示该排污管道中污水的流量fij和排污管道的容量Cij，试找出该网络中从V1到V6所有的增广链及每一增广链上的可增流量，并求该网络的最大流量。

V2 (6,8) （2,2） （2,4） （6,6） V1 （7,9） V3 （3,3） （3,5） (0,4) V5 （0,3） (4,5) V4 图3

V6

（4,7）

增广链及该增广链上可增加的流量为：

网络的最大流为：

5

四、应用题（共35分）

1、（20分）设某工程情况如表4所示:

工作 A B C D E F

表4 工时（天） 5 3 6 9 7 3 紧前工作 － A － C，B C E，D 1）试根据表4中的资料建立该工程的网络计划模型，即绘制其统筹图(8分)；

2）计算图中各项工作的最早可能开工时间ES、最早可能完工时间EF、最迟必须开工时间LS和最迟必须完工时间LF，并请填在以下表5中（10分）；

表5 工序 ES EF LS LF A B C D E F 3）求该工程的关键路线（请用双线直接标在图上）和工期（2分）。

6

2、（15分）某企业要投资生产一种新产品，投资方案为A、B、C不同的经济形 利润表如表6所示。

如果经济形势各状况的概率未知， 1）试用悲观准则进行决策（7分）；

2）用后悔值准则进行决策（求解过程中，要求写出后悔值矩阵）（8分）。

表6 单位:万元 投资 不同经济形势 方案 好 平 差 A B C ••••••

••

60 40 25 48 45 －5 50 47 30

7