运筹学模拟试题

1、运筹学模拟试题 运筹学模拟试题 一、填空题：（10分） 1、 运输问题中，求总利润最大时，当运输图所有空格的检验数 ，得最优解； 求总运费最小时，当运输图所有空格的检验数 ，得最优解。 2、 若线性规划问题的最优基为b，则问题的最优值为 ，线性规划的对偶问 题的最优解是 ，其中cb是基b所对应的基变量在目标函数中的系数向量， maxz?cx线性规划问题是： ?ax?b?x?0 3、 运输问题中，当总供应量小于总需求量时，求解时需虚设一个 点，此点的供应量应 （总需求量与总供应量之差）。 4、 结点的最迟完成时间又称 时间，若将最迟完成时间后延，将使整个络工期 。 5、 树是 的连通图，在树上任

2、意除去一条边则该树余下的图 。 二、单项选择题（10分） 1、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（ ）。 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毫克 维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示： 要求确定既满足动物生长的营

4、养需要，又使费用最省的选用饲料的方案。 饲料 成分 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/千克） 1 2 3 4 5 3 2 1 6 18 1 0.5 0.2 2 0.5 0.5 1.0 0.2 2 0.8 0.2 0.7 0.4 0.3 0.8 1 五、（8分）已知线性规划问题 x?2x?3x?4x?x?2x?2x?3x?20?2x?x?3x?2x?20?x,x,x,x?0maxz?1123223441312344 其对偶问题最优解为 y1?1.2， y2?0.2，试根据队友理论求出原问题的最优解。 六、已知运输问题的供需关系表与单位运价表如下所示，试用伏格尔法求出该问题的近

5、似最优解。（6分） 产地 销地 1 2 3 销量 甲 3 7 2 60 乙 2 5 5 40 丙 7 2 4 20 丁 6 3 5 15 产量 50 60 25 七、用图解法找出下列目标规划问题的满意解（8分） minz?pd1?3?pd2?2?p(d3?1?d?1)?246x2xdd1211?x1x2d2d2?5?5x2?d3?d3?15?,?0;,?didi?0(i?1,2,3)?x1x2 八、请用匈牙利法求解该指派问题：（8分） ?3?8?已知效率矩阵如下：?6?8?9874410222261097393?7?5? ?5?10?九、络最大流问题：（12分） 下面为一容量络，各弧上的( f

6、ij,cij)代表该弧的（可行流流量，容量） 2 请用标号法求出该络最大流。 一、单项选择题：(10分) 1、若用图解法求解线性规划问题，则该问题所包含决策变量的数目应为（ ）。 a 、二个 b 、五个以上 c 、三个以上 d 、无限制 2、原问题的检验数对应于对偶规划的一个解，符号相反，对偶规划的检验数对应于原规划的一个解（符号性反），特别的，若原问题的最优基为b，则对偶问题的最优解为：（ ） a 、y*= -cbb-1 b、y*= cbb-1 c 、y*= cn-cbb-1 d、y*= b-cbb-1 3、甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比

7、赛状况的图是（ ）。 a 、一棵树 b、没有圈 c 、连通图 d、任两点之间有一条带有方向的线 4、下列图形中是一棵树的为：( ) a b c d 5、以下哪个性质是对偶问题所不具有的（ ） a、对称性 b、互补松弛性 c、弱对偶性 d、可行性 二、判断题：（10分） 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ） 2、线性规划问题每一个基解对应于可行域的一个顶点。（ ） 3、正偏差变量应取正值，负偏差变量应取负值。（ ） 4、线性规划问题是目标规划问题的一种特殊形式。（ ） 5、表上作业法实质就是求解运输问题的单纯形法。（ ） 三、填空题：（10分） 1、在图论方

8、法中，通常用 表示人们研究的对象，用 表示对象之间的某 种联系。 2、xi是某线性规划问题的一个决策变量，若它是该线性规划问题某步单纯形表中的一个基变量，则xi的检验数为 ；若其检验数不为零，则其为 变量。 3、利用单纯形法求解线性规划问题时，在最终单纯形表中，若某一基变量为零，该基解称为 解；若某一非基变量检验数为零，则该问题可能有 解。 4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 。 5、求支撑树有 法和 法两种方法。 3 四、指派问题：（10分） 现有五个人ai (i=1,2,3,4,5)被分配去完成完成五项工作bj (j=1,2,3,4,5)，每人只能完成一项工作，且每

9、项工作只能有一人来完成，每人完成每项工作所花费的费用如下表，请求使总费用最小的最优解。 人员 任务 a1 a2 a3 a4 a5 b1 12 8 7 15 4 b2 7 9 17 14 10 b3 9 6 12 6 7 b4 7 6 14 6 10 b5 9 6 12 10 6 五、规划问题：（7分） 用单纯形法求解某线性规划问题得如下单纯形表： cj a b 基变量 c d cj-zj 100 x1 0 1 e 80 x2 1 0 f 0 x3 3/10 -1/10 -14 0 x4 -1/5 2/5 -24 s 12 16 g （1） 上述问题是求maxs=100x1+80x2 ,x3,x

10、4为松弛变量，则a,b,c,d,e,f,g各为多少，上述 表所给出的解是最优解吗？ （2） 上述问题的对偶问题的解是什么？最优值是什么？ 六、运输问题：（10分） 对如下表的运输方案： （1） 若要使总利润最大，该方案是否为最优方案？ （2） 若问题中b1的需要量改为700，该方案是否为最优方案？ （3） 填空题：（10分） 1、在图论中，图的基本要素有两个，它们是 和 。 2、结点的最早开始时间和 时间是同一时间，最早开始是对结点的后接工序而言， 是对结点的紧前工序而言。 3、对需要量 供应量的运输问题，求最优解时要先 一个供应点。 4、关键路线是从起点到终点所有路中的最 路，它的线路时差为

11、 。 5、在图论中，为了表示两个队比赛的胜负关系可以用一条带 的 来表示。 （4） 选择题（10分） 1、若t是图g的最小支撑树，则（ ） at必唯一 b. g不一定是连通图 4 ct中必不含圈 d.g中不含圈 4、若线性规划问题的最优解在可行域的两个顶点达到，则最优解（ ）。 a有两个 b.有无穷多个 c.过这两点的直线 d.不可能发生 5、在n个产地，m个销地的产销平衡运输问题中，（ ）是错误的。 a 运输问题是线性规划问题 b 基变量的个数是数字格的个数 c 空格有mn-n-m+1个 d 每一格在运输图中均有一闭合回路 一、判断题（10分） 1、用单纯形法求解标准型式的线性规划问题时，与?量。（ ） 2、对偶问题的对偶一定是原问题。（ ） 3、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。（ ） 4、指派问题效率矩阵地每个元素都乘以同意常数k，将不影响最优指派方案。（ ） 5、求络最大流的问题可归结为求解一个线性规划模型。（ ） 二、规划问题（16分） 已知线性规划问题 minz?j0对应的变量都可以被选作换入变 2x?3x12?5x3?6x4?x12x2?3x3?x4?2?2x1?x2?x3?3x4?3?0(j?1,2,3,4)?xj （1） 写出其对偶问题； （2） 用图解法求对偶