应用运筹学11-12-1期末考试试卷

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格

浙江大学城市学院

2011— 2012学年第一学期期末考试试卷

《应用运筹学》

开课单位： 计算分院 ；考试形式：闭卷；考试时间： _2012_年_1_月_13_日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 八 九 总 分 得分 评卷人 （注：答案全部写在答卷上）

得分 一．判断题 (本大题共10小题，每题1分，共10分。)

在你认为正确的叙述后面打“√”，错误的后面打“╳”。 1． 线性规划中“线性”的含义是指约束条件关于决策变量是线性等式或不等式，而对目标函数没有要求。 ( )

2． 线性规划求解的结果可能会有无穷多个最优解，但解相应的最优值都相等。

( )

3． 若线性规划有最优解则其可行域一定有界。 ( )

4． 若线性规划无解，则其可行域是空集。 ( )

5． 影子价格为0时，表明该资源未得到充分利用。 ( )

6． 平衡运输问题的约束是资源约束。 ( )

7． 指派问题是运输问题的特例。 ( )

8． 匈牙利法是对运输问题求最小值的一种求解方法。 ( )

9． 点vi表示自来水厂及用户，vi与vj之间的边表示两点间可以铺设管道，权为vi与vj间铺设

管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5个用户并且使总的费用最小。这属于最短路问题。 ( )

10．邮递员从邮局vi出发要经过每一条边将邮件送到用户手中，最后回到邮局vi，如何安排路线使总路程最短。这属于运输问题。 ( )

第 1 页 共 11 页

得分 二．填空题 (本题每行1分，共10分。) 根据灵敏度报告进行分析，对下列情形能否得到相应的最优值和最优解？或是只能重新求解？在相应方格打“√”。 最优值 最优解 重新求解 灵敏度报告 单个目标函数系数变动且在变动范围内 多个目标函数系数变动且在变动范围内 单个约束右端值变动且在变动范围内 多个约束右端值变动且在变动范围内 约束条件系数变化 增加一个新变量 增加多个新变量 增加一个约束条件 增加多个约束条件 同时增加变量和约束条件 得分 三．分析解答题 (共10分。)

某公司目前正在制造两种产品，产品I和产品II，现在产品I和产品II的每天产量分 别为30个和120个，工资负责制造的副总经理希望了解是否可以通过改变这两种产品 的数量来提高公司的利润。公司制造每个产品所需的加工工时和每个车间的加工能力

（每天加工工时数）如下表产品I和产品II一所示：

生产两种产品的有关数据

车间 1 2 3 4 每件产品利润（元） 产品I 2 0 2 1.2 500 产品II 0 3 2 1.5 400 车间能力 300 540 440 300 利用EXCEL进行线性规划建模求解后的表格（表格一）和敏感性性分析报告（表格二）如下： 问：

（1） 假设生产的全部产品都能销售出去，请确定最优产品组合，即确定使得总利润最大的产

品I和产品II每天的产量。

（2） 在问题（1）所求得的最优产品组合中，在1、2、3、4四个车间中哪些车间的能力还有

剩余，剩余多少？

（3） 1、2、3、4四个车间能力的影子价格各为多少？即1、2、3、4四个车间的能力分别增

加一个加工工时数时能给公司带来多少的额外利润？

第 2 页 共 11 页

（4） 当产品I的单位利润不变，产品II的单位利润在什么范围内变化时，此最优解不变？

分别讨论各个单位产品利润在什么范围内变化时，原生产计划不变。当产品II的单位利润不变，产品I的单位利润在什么范围内变化时，此最优解不变？

（5） 当产品I的单位利润从500元降为450元，而产品II的单位利润从400元降为430元时，

最优解是否改变？

表格一、EXCEl建模表格

表格二、第三题的敏感性分析报告

四．计算解答题 (共20分。)

某公司铺设光导纤维网络问题（最小支撑树问题）。 某公司的管理层已经决定铺设最先进的光导纤维网络，为它的主要中心之间提供 高速通信（数据、声音和图像）。图一中的节点显示了该公司主要中心（包括公司的总

部、巨型计算机、研究区、生产和配送中心等八个位置）的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。（分别用破圈法和避圈法、Prim算法和Sollion算法求解，给出算法步骤，不用建立模型。）

图一、第三题的节点分布图 得分 第 3 页 共 11 页

4 E 2 6 C 2 H

得分 B 2 5 D 3 F 3 A 6 5 G F 2 7

五．计算解答题 (共10分。) 指派问题。

根据下面的费用矩阵，采用匈牙利算法给出最优的指派方案。（给出算法步骤，不用建立模型。）

?127979??89666????717121412? ??15146610????4107106??

得分 六．线性规划建模题(共10分。)

解题要求：给出三要素，建立相应的规划模型。

（生产与存储问题问题）。某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表三所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用1500元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。

表格三、各季度的生产能力及生产每台柴油机的成本

季度 1 2 3 4 生产能力（台） 单位成本（万元） 25 35 30 10 10.8 11.1 11.0 11.3 （1） 以各季度的产量及库存为决策变量，建立线性规划模型；

（2） 以第i季度生产的第j季度交货的柴油机数为决策变量，建立产大于销的运输问题模型。

第 4 页 共 11 页

得分 七．优化建模题 (共10分。)

解题要求：给出三要素，建立相应的规划模型。 图二、第五题的城市网络图

1 3 4 2 7 2 3 4 10 2 11 4 3 4 4 8 3 2 1 3 3 5 1 4 2 3 3 3 6 9 3 12

1) 在进行货郎担问题试求解时，有回路“2—>3—>6—>5—>2”，“4—>7—>8—>4”，“9<

—>12”，给出货郎担问题的数学模型； 2) 给出上图求解中国邮路问题的数学模型；

得分 八．最大流建模题(共10分。)

解题要求：给出三要素，建立相应的规划模型。

计划编制问题。某市政工程公司在未来5～8月份内需完成4项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见表3。该公司共有劳动力120人，任一工程在一个月内的劳动力投入不能超过80人，问公司应如何分配劳动力完成所有工程，是否能按期完成？

(1) 画出将该问题转化为最大流问题的网络图； (2) 给出求解最大流问题的数学模型； 工程 A.地下通道 B.人行天桥 C.新建道路 D.道路维修 工期 5～7月 6～7月 5～8月 8月

第 5 页 共 11 页

需要劳动力（人） 100 80 200 80

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库应用运筹学11-12-1期末考试试卷在线全文阅读。