运筹学试题答案.doc

湖北汽车工业学院科技学院 运筹学 考试试卷 课程编号 070070 考试形式 闭卷 考试日期 考 试 学 期 2011-2012（1） 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 阅卷 一：单选题（每题3分，共30分） 1．．，在基变量中仍含有非零的人工变量。表明该线性规划问题（ D ）．．””，这反映的是对偶规划以下哪方面的性质 ( D ) A. 对称性 B. 弱对偶性 C. 最优性 D. 互补松弛性 6．化为，则依次为(?D?? ) A．人工变量，剩余变量，松弛变量，决策变量 B．松弛变量，剩余变量，人工变量，决策变量 C．决策变量，剩余变量，松弛变量，人工变量 D．决策变量，松弛变量，剩余变量，人工变量 7．(??B??? ) A．树的生成法 B. 求最大流法 C．求最小生成树法 D. 求最短路法 8． (???C?? )正确。 A．?B.若A和B都有最优解，则二者最优值未必相等 C．若A无可行解，则B无有界最优解 D．A有最优解，B不一定有最优解 9. 分枝定界法是用来求解以下哪一类问题的？（ D ） A .最大流问题 B.最短路问题 C. 动态规划问题 D.整数规划问题 10. 下列是关于标准的排队模型的叙述，其中不正确的是(???C?? ) A．单通道即只有一个服务台 B. 排队长度及顾客来源无限制 C．服务时间服从泊松分布 D. 顾客到达过程服从泊松分布 二、填空题(本大题共小题，每分，共分)请在每小题的空格中填上正确答案。错填、不填均无分。 ． 图解法 来解。 12．． 无圈 且连通。 14．．用单纯形法求解线性规划问题时，单纯形表中的每个解对应的是线性规划问题的一个 ，与图解法 一一对应。基可行解可行域的顶点 的方法，一个是闭回路法，另一个是位势法。 18. 在求解网络的最大流问题中，把满足守恒条件及流量可行条件的一组网络流称为可行流，即线性规划模型的 可行解 。 19. 在排队论中，我们认定即到达率小于服务率，如果没有这个条件，排队长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客， 称为服务强度。 三、题(本大题共小题，共分) 解：对偶问题是： 21.（10分）将下列线性规划化为标准形式，然后用单纯形法求解。 解：将原问题划为标准形得： =60 （3分） 4 -2 2 0 0 0 b 0 60 3 1 1 1 0 0 0 10 [1] -1 2 0 1 0 0 40 2 2 -2 0 0 1 4 -2 2 0 0 0 4 -2 2 0 0 0 b 0 30 0 4 -5 1 -3 0 4 10 1 -1 2 0 1 0 0 20 0 [4] -6 0 -2 1 0 2 -6 0 -4 0 4 -2 2 0 0 0 b 0 10 0 0 1 1 -1 -1 4 15 1 0 1/2 0 1/2 1/4 -2 5 0 1 -3/2 0 -1/2 1/4 0 0 -3 0 -3 -1/2 (9分) 所以X=（15，5，0，10，0，0）T 为唯一最优解 Max Z=4*15-2*5=50 (10分) 22．（10分）求下图中的最小生成树，并求出该最小生成树所有边的权数之和。 解：最小生成树为：（其中中间的边长均为3的小四边形可去掉其中任意一边，都正确。每找对一条边给1分，正确求出权数和再给1分。） 所有边的权数之和为：2*4+3*5=23 23．． ************************************************************************ ***********学生班号 学号： 姓名：