大工13春《运筹学》模拟试卷A答案
机密★启用前大连理工大学网络教育学院
2013年9月份《运筹学》课程考试
模 拟 试 卷
考试形式：闭卷 试卷类型：（A）
☆ 注意事项： 1、本考卷满分共：100分；考试时间：90分钟。
2、所有试题必须答到试卷答题纸上，答到试卷上无效。
3、考试结束后，考生须将试卷和试卷答题纸一并交回。
学习中心______________ 姓名____________ 学号____________
一、单项选择题（本大题共5小题，每小题3分，共15分）
1、下列哪项不属于线性规划数学模型的构成要素（ ）。
A．决策变量
B．目标函数
C．约束条件
D．解
2、如果原问题为无界解，则对偶问题的解是（ ）。
A．无解
B．无穷多解
C．无界解
D．不能确定
3、若运输问题在总供应量大于总需要量时，则（ ）。
A．必须用线性规划单纯形法求最优解
B．不存在可行解
C．虚设一个需求点
D．虚设一个供应点
4、下列叙述中，不正确的是（ ）。
A．树的点数为边数加1
B．树的任意两点之间只有一条路
C．图的点数大于边数
D．任何不连通图都不是树
5、下列步骤中，不属于目标规划模型图解法的为（ ）。
A．作平面直角坐标系
B．作出目标约束所在直线，标出偏差方向
C．作出目标函数的一族平行线
D．按优先级次序，确定满意解
二、判断题（本大题共6小题，每小题3分，共18分）
1、若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。（ ）
2、对于m个发点、n个收点的运输问题，该问题的系数矩阵的秩必为m+n-1。（ ）
3、假如一个线性规划问题含有5个变量和3个约束，则用动态规划方法求解时将划分为3个阶段，每个阶段的状态将由一个5维的向量组成。（ ）
4、树的任意两点之间只有一条路。（ ）
5、最短路问题中， 到所有点的最短路是最小生成树。（ ）
6、动态规划的逆推与顺推解法得到不同的最优解。（ ）
三、名词解释题（本大题共4小题，每小题5分，共20分）
1、偏差变量
2、图
3、容量网络
4、状态
四、简答题（本大题共4小题，每小题8分，共32分）
1、简述利用单纯形法求解线性规划问题时检验数（Cj-Zj）的经济意义。
2、简述网络图中确定关键路线的意义。
3、简述只含两个变量的目标规划问题图解分析法的解题步骤。
4、简述动态规划的最优化原理的内容。
五、计算题（本大题1小题，共15分）
1、已知运输问题的供需关系表与单位运价表如下表所示，试用表上作业法求其最优调运方案。
销地
产地 甲 乙 丙 丁 产量
1 3 2 7 6 50
2 7 5 2 3 60
3 2 5 4 5 25
销量 60 40 20 15
机密★启用前
大连理工大学网络教育学院
2013年9月份《运筹学》课程考试 模拟试卷答案
考试形式：闭卷 试卷类型：A
一、单项选择题（本大题共5小题，每小题3分，共15分）
1．D2．A 3． C 4． C 5．C
二、判断题（本大题共6小题，每小题3分，共18分）
1．（对）2．（对） 3．（错）4．（对） 5．（错） 6．（错）
三、名词解释题（本大题共4小题，每小题5分，共20分）
1．偏差变量指实际值与目标值的差距。d+表示实际值超出目标值的差距；d-表示实际值未达到目标值的差距。
2．图是指点V和边E的集合，用以表示对某种现实事物的抽象。其中点表示所研究的事物对象；边表示事物之间的联系。
3．容量网络指对网络上的每条弧(vi，vj)都给出一个最大的通过能力，称为该弧的容量，记为c(vi，vj)，简称容量。以cij表示。
4．状态指某阶段初始状况。既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。是动态规划中各阶段信息的传递点和结合点。
四、简答题（本大题共4小题，每小题8分，共32分）
1、答：检验数（Cj-Zj）的经济意义：是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。
2、答：第一，关键路线的持续时间决定了完成全部计划所必需的最少时间，是整个工程的薄弱和敏感环节。第二，关键路线上的各项作业对影响计划进度起关键作用，是整个工程的控制性环节，也就是需要领导重点抓和安排比较充裕的人力物力以保证按期完工的关键部位。
3、答：（1）作平面直角坐标系；（2）作出系统约束所在直线；（3）作出目标约束所在直线，标出偏差方向；（4）按优先级次序，确定满意解。
4、答：动态规划的最优化原理：作为整个过程的最优策略具有这样性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。
五、计算题（本大题1小题，共15分）
1．解：用最低费用法求得其初始调运方案：
第一步，找出表1中最小运价2，有三个，任选一个。选择销地乙和产地1对应的2进行分配，因为有50>40，确定分配的运量为40。划去销地乙对应的列，那么产地1未分配的产量只剩下10。如表1，2所示。
表1
销地
产地 甲 乙 丙 丁 产量
140 50
2 60
3 25
销量 60 40 20 15
表2
销地
产地 甲 丙 丁 产量
1 3 7 6 10
2 7 2 3 60
3 2 4 5 25
销量 60 20 15
第二步，找出表2中最小运价2，有两个，任选一个。选择销地甲和产地3对应的2进行分配，因为有60>25，确定分配的运量为25。划去产地3对应的行，那么销地甲还需35。如表3，4所示。
表3
销地
产地 甲 乙 丙 丁 产量
140 50
2 60
3 25 25
销量 60 40 20 15
表4
销地
产地 甲 丙 丁 产量
1 3 7 6 10
2 7 2 3 60
销量 35 20 15
第三步，从表4未划去的元素中找出最小元素2，确定分配的运量20，划去销地丙对应的列，产地2对应的未分配的产量只有40，如表5，6所示。
表5
销地
产地 甲 乙 丙 丁 产量
140 50
2 2060
3 25 25
销量 60 40 20 15
表6
销地
产地 甲 丁 产量
1 3 6 10
2 7 3 40
销量 35 15
第四步，进一步从表6剩下的待分配运量的单位运价表中找出最小元素，再进行分配，直到分配完所有的产量和销量，得到初始分配方案，如表7所示。
表7
销地
产地 甲 乙 丙 丁 产量
1 10 40 50
2 2520 15 60
3 25 25
销量 60 40 20 15
（8分）
用踏石法求检验数：
先找出各非基变量的闭回路，即从表7的某一空格（非基变量）为起点，用水平或垂直线，只有碰到数字格（基变量）后才旋转 ，继续向前划，直到回到起始空格为止。检验数的计算，就是从空格对应的单位运价开始，对闭回路所对应的单位运价交替地赋予“+”和“-”号，并计算它们的代数和，如表8所示。
表8
空格 闭回路 检验数
（1丙） （1丙）—（2丙）—（2甲）—（1甲）—（1丙） 7-2+7-3=9
（1丁） （1丁）—（2丁）—（2甲）—（1甲）—（1丁） 6-3+7-3=7
（2乙） （2乙）—（2甲）—（1甲）—（1乙）—（2乙） 5-7+3-2=-1
（3乙） （3乙）—（3甲）—（1甲）—（1乙）—（3乙） 5-2+3-2=4
（3丙） （3丙）—（3甲）—（2甲）—（2丙）—（3丙） 4-2+7-2=7
（3丁） （3丁）—（3甲）—（2甲）—（2丁）—（3丁） 5-2+7-3=7
调整方案：选出检验数最小的（-1），调整运量，找出该检验数所对应的空格（2乙），再找出它的闭回路，选该闭回路中加“-”号的运量最小的数值作为调整运量，在该闭回路中加“+”号的运量处加上调整运量，加“-”号的运量处减去调整运量，得到新的调运方案的基变量，如表9。
表9
销地
产地 甲 乙 丙 丁 产量
1 35 15 50
225 20 15 60
3 25 25
销量 60 40 20 15
在用闭回路法求出新的调运方案的检验数，如表10所示。
表10
空格 闭回路 检验数
（1丙） （1丙）—（2丙）—（2乙）—（1乙）—（1丙） 7-2+5-2=8
（1丁） （1丁）—（2丁）—（2乙）—（1乙）—（1丁） 6-3+5-2=6
（2甲） （2甲）—（1甲）—（1乙）—（2乙）—（2甲） 7-3+2-5=1
（3乙） （3乙）—（3甲）—（1甲）—（1乙）—（3乙） 5-2+3-2=4
（3丙） (3丙)—(3甲)—(1甲)—(1乙)—(2乙)—(2丙)—(3丙) 4-2+3-2+5-2=3
（3丁） (3丁)—(3甲)—(1甲)—(1乙)—(2乙)—(2丁)—(3丁) 5-2+3-2+5-3=6
因为检验数全为非负，所以表9的调运方案就是最优调运方案。（7分）
页:
[1]