《运筹学模拟试题-副本解析》由会员分享，可在线阅读，更多相关《运筹学模拟试题-副本解析（15页珍藏版）》请在金锄头文库上搜索。
1、一、填空题：（10分）1、运输问题中，求总利润最大时，当运输图所有空格的检验数 ,得最优解； 求总运费最小时，当运输图所有空格的检验数 ,得最优解。2、若线性规划问题的最优基为B,则问题的最优值为 ,线性规划的对偶问题的最优解是 ，其中Cb是基B所对应的基变量在目标函数中的系数向量，maxZ =CX线性规划问题是：AX=bX 03、运输问题中，当总供应量小于总需求量时，求解时需虚设一个 点，此点的 供应量应 （总需求量与总供应量之差）。4、结点的最迟完成时间又称 时间，若将最迟完成时间后延，将使整个网络 工期。5、树是 的连通图，在树上任意除去一条边则该树余下的图 。二、单项选择题（10分）1
2、、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（）。A.求最大流量法B.求最小支撑树法C.求最短路线法D.树的逐步生成法2、在网络计划中，进行时间与成本优化时，随工期延长，简介费用将（）。A.减少B.增加C.不变D.不易估计3、图论中，图的基本要素是（）。A.点和带方向的连线B.点和线C.点及点与点之间的连线D.点和一定要带权的连线三、判断题。（10分）1、线性规划模型中增加一个约束条件，可行域的范围一般将缩小， 减少一个约束条件，可行域的范围一般将扩大。2、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶 问题无可行解时，其原问题具有无界解。3、运输
3、问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之 一：有唯一最优解，有无穷多最优解，无界解，无可行解。4、目标规划中，英同时包含系统约束（绝对约束）与目标约束。5、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值得下界。四、建立数学模型题：（8分）某饲养场饲养动物出售，设每头动物每天至少需 700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示：要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。蛋白质（克）矿物质（克）维生素（毫克）价格（元/千克）1310.50.2
4、220.51.00.7310.20.20.446220.35180.50.80.8五、（8分）已知线性规划问题maxZ 二 xi 2x2 3x3 4x4xi+2x2+2x3 /202x#x2+3x3+ 2x4*0x1, x2, x3, x4 - 0其对偶问题最优解为y1=1.2,丫2 = 0.2,试根据队友理论求出原问题的最优解。#六、已知运输问题的供需关系表与单位运价表如下所示，试用伏格尔法求出该问题的近似最优解。（6分）甲乙丙丁132765027523603254525销量60402015七、用图解法找出下列目标规划问题的满意解（8分）min Z = Pid3Pzd； P3（ddi）6xi
5、 + 2x2 + d-d：=24* xi 、2 -d2=5 +5x2 +d3-d3=15 十xi,x20dd （i =1,2,3）八、请用匈牙利法求解该指派问题：（8分）382103已知效率矩阵如下:8729764275842359106910九、网络最大流问题：（12分）卜面为一容量网络，各弧上的（f ,.）代表该弧的（可行流流量，容量）ij C|j请用标号法求出该网络最大流。一、单项选择题：（10分）1、若用图解法求解线性规划问题，则该问题所包含决策变量的数目应为（）A、二个B、五个以上C、三个以上D、无限制2、原问题的检验数对应于对偶规划的一个解，符号相反，对偶规划的检验数对 应于原规划
6、的一个解（符号性反），特别的，若原问题的最优基为 B,则对偶问 题的最优解为:* （）*A、Y*= -CbB-1B、Y*= CbB-1C、Y*= Cn-CbB-1D、Y*= B-CbB-13、甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局， 用来表示这四个队比赛状况的图是（）。A、一棵树B、没有圈C、连通图D、任两点之间有一条带有方向的线4、下列图形中是一棵树的为：（）ABCD5、以下哪个性质是对偶问题所不具有的（）A、对称性B 、互补松弛性C、弱对偶性D 、可行性二、判断题：（10分）1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（）2、线性规划问题每
7、一个基解对应于可行域的一个顶点。（）3、正偏差变量应取正值，负偏差变量应取负值。（）4、线性规划问题是目标规划问题的一种特殊形式。（）5、表上作业法实质就是求解运输问题的单纯形法。（）三、填空题：（10分）1、在图论方法中，通常用 表示人们研究的对象， 用 表示对象之间的某种联系。2、y是某线性规划问题的一个决策变量， xi若它是该线性规划问题某步单纯形表中的一个基变量，则 y的检验数为；若其检验数不为零，则其为 变量。xi3、利用单纯形法求解线性规划问题时，在最终单纯形表中，若某一基变量为零，该基解称为 解；若某一非基变量检验数为零，则该问题可能有 解。4、关键路线是从起点到终点所有路中的最
8、 路，它的线路时差为 。5、求支撑树有法和 法两种方法。四、指派问题：（10分）现有五个人Ai (i=1,2,3,4,5)被分配去完成完成五项工作Bj (j=1,2,3,4,5),每人只能完成一项工作，且每项工作只能有一人来完成，每人完成每项工作所花费的费用如下表，请求使总费用最小的最优解。”人员-任务-BiB2B3B4B5Ai127979A289666A3717121412A415146610A54107106五、规划问题：(7分)用单纯形法求解某线性规划问题得如下单纯形表:Ci1008000S基变量X1X2X3X4ac013/10-1/512bd10-1/102/516Cj-Zjef-14
9、-24g(1) 上述问题是求 maxS=100x 1+80x2 ,X3,X4为松弛变量，则 a,b,c,d,e,f,g各为多少，上述表所给出的解是最优解吗？(2) 上述问题的对偶问题的解是什么？最优值是什么？六、运输问题：(10分)对如下表的运输方案：产心、Bl产量Ai25006500350 7应350乱2504503r 300第量600550(1) 若要使总利润最大，该方案是否为最优方案？(2) 若问题中B1的需要量改为700,该方案是否为最优方案？(3) 填空题：(10分)1、在图论中，图的基本要素有两个，它们是 和。2、结点的最早开始时间和 时间是同一时间，最早开始是对结点的后接工序而言
10、， 是对结点的紧前工序而言。3、对需要量 供应量的运输问题，求最优解时要先 一个供应点。4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 5、在图论中，为了表示两个队比赛的胜负关系可以用一条带 的 来表示。(4) 选择题(10分)1、若T是图G的最小支撑树，则()A. T必唯一 B. G不一定是连通图C. T中必不含圈D.G中不含圈4、若线性规划问题的最优解在可行域的两个顶点达到，则最优解（）。A.有两个B.有无穷多个C.过这两点的直线D.不可能发生5、在n个产地，m个销地的产销平衡运输问题中，（）是错误的。A.运输问题是线性规划问题B.基变量的个数是数字格的个数C.空格有 mn-n
11、-m+1个D.每一格在运输图中均有一闭合回路一、判断题（10分）1、用单纯形法求解标准型式的线性规划问题时，与仃j 0对应的变量都可以被选作换入变量。（）2、对偶问题的对偶一定是原问题。（）3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k,最优调运方案将不会发生变化。（）4、指派问题效率矩阵地每个元素都乘以同意常数k,将不影响最优指派方案。 （）5、求网络最大流的问题可归结为求解一个线性规划模型。（）二、规划问题（16分）已知线性规划问题min z = 2xi 3x2 5x3 6x4X1+2X2+3X3 + X4 占2J-2xi+x2-x3 + 3x4-3X 之0 （j =
12、1,2,3,4）（1） 写出其对偶问题；（2） 用图解法求对偶问题的解；（3） 利用（2）的结果及对偶性质求原问题解。三、运输问题（10分）某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表， 求最优运输方案。B1B2B3B4A13113107A219284A3741059销量3656四、支撑树问题（6分）求下面网络图的最小支撑树:五、运输问题(10分) 求总运费最小的运输问题,某步运输图如下:(1)写出a, b ,c ,d ,e的值，并求出最优运输方案；(2) A3到Bi的单位运费满足什么条件时，表中运输方案为最优方案。六、指派问题(10分)分配甲、乙、丙、丁、戊五人去
13、完成五项工作，每人完成一项工作，每人完成各项任务时间 如下表，试确定总花费时间为最少的指派问题。ABCDE甲127979乙89666丙71712149丁15146610戊4107109(Cj, f J。七、求下图所示容量网络中从 vsvt的最大流。其中每边上的数为根据下表资料二工作代号紧前工作工作持续时间（R1且153.415CA14D3、C1036FD6G口1HE. G301F. H8要求：Q绘制网络计划图/用标号法计算时间参数：E“、EF：g L*、LF：巧.FF5确定关键路线o（5确定关键路线。答案，三匚二力TF.匚各时间参数如图所示（或瓦旦 八印图中于.:为零的若工作构成了关键路线（粗红线即关键工作为:二5DG殳八 某项工程的各工作及其持续时间如下表所示：工作名称紧后工作工作盘卖时间（天）A丸C4BD, E6CE3VDF. G3E尸、G
