运筹学模拟试题
一、填空题：（10分）
1、 运输问题中，求总利润最大时，当运输图所有空格的检验数 ，得最优解；
求总运费最小时，当运输图所有空格的检验数 ，得最优解。
2、 若线性规划问题的最优基为B，则问题的最优值为 ，线性规划的对偶问
题的最优解是 ，其中CB是基B所对应的基变量在目标函数中的系数向量，
maxZ?CX线性规划问题是： ?AX?b??X?0
3、 运输问题中，当总供应量小于总需求量时，求解时需虚设一个 点，此点的供应量应 （总需求量与总供应量之差）。
4、 结点的最迟完成时间又称 时间，若将最迟完成时间后延，将使整个网络工期 。 5、 树是 的连通图，在树上任意除去一条边则该树余下的图 。 二、单项选择题（10分）
1、为了在各住宅之间安装一条供暖管道，若要求所用材料最省，则应采用（ ）。 A．求最大流量法 B.求最小支撑树法 C．求最短路线法 D.树的逐步生成法
2、在网络计划中，进行时间与成本优化时，随工期延长，简介费用将（ ）。 A．减少 B.增加 C.不变 D.不易估计 3、图论中，图的基本要素是（ ）。 A．点和带方向的连线 B.点和线
C．点及点与点之间的连线 D.点和一定要带权的连线 三、判断题。（10分）
1、 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，
可行域的范围一般将扩大。 2、 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶
问题无可行解时，其原问题具有无界解。
3、 运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。 4、 目标规划中，英同时包含系统约束（绝对约束）与目标约束。
5、 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是
该问题目标函数值得下界。 四、建立数学模型题：（8分）
某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克
维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示： 要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。 饲料 成分 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/千克） 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，试根据队友理论求出原问题的最优解。
六、已知运输问题的供需关系表与单位运价表如下所示，试用伏格尔法求出该问题的近似最优解。（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分） 下面为一容量网络，各弧上的(
fij,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、甲、乙、丙、丁四个球队进行比赛，任两个队都有一场比赛，且没有和局，用来表示这四个队比赛状况的图是（ ）。
A 、一棵树 B、没有圈
C 、连通图 D、任两点之间有一条带有方向的线
4、下列图形中是一棵树的为：( )
A B C D
5、以下哪个性质是对偶问题所不具有的（ ）
A、对称性 B、互补松弛性 C、弱对偶性 D、可行性
二、判断题：（10分）
1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ） 2、线性规划问题每一个基解对应于可行域的一个顶点。（ ） 3、正偏差变量应取正值，负偏差变量应取负值。（ ） 4、线性规划问题是目标规划问题的一种特殊形式。（ ） 5、表上作业法实质就是求解运输问题的单纯形法。（ ） 三、填空题：（10分）
1、在图论方法中，通常用 表示人们研究的对象，用 表示对象之间的某
种联系。
2、xi是某线性规划问题的一个决策变量，若它是该线性规划问题某步单纯形表中的一个基变量，则xi的检验数为 ；若其检验数不为零，则其为 变量。 3、利用单纯形法求解线性规划问题时，在最终单纯形表中，若某一基变量为零，该基解称为 解；若某一非基变量检验数为零，则该问题可能有 解。 4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 。 5、求支撑树有 法和 法两种方法。
3
四、指派问题：（10分）
现有五个人Ai (i=1,2,3,4,5)被分配去完成完成五项工作Bj (j=1,2,3,4,5)，每人只能完成一项工作，且每项工作只能有一人来完成，每人完成每项工作所花费的费用如下表，请求使总费用最小的最优解。
人员 任务 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,x4为松弛变量，则a,b,c,d,e,f,g各为多少，上述
表所给出的解是最优解吗？ （2） 上述问题的对偶问题的解是什么？最优值是什么？ 六、运输问题：（10分） 对如下表的运输方案：
（1） 若要使总利润最大，该方案是否为最优方案？
（2） 若问题中B1的需要量改为700，该方案是否为最优方案？ （3） 填空题：（10分）
1、在图论中，图的基本要素有两个，它们是 和 。
2、结点的最早开始时间和 时间是同一时间，最早开始是对结点的后接工序而言， 是对结点的紧前工序而言。
3、对需要量 供应量的运输问题，求最优解时要先 一个供应点。 4、关键路线是从起点到终点所有路中的最 路，它的线路时差为 。 5、在图论中，为了表示两个队比赛的胜负关系可以用一条带 的 来表示。 （4） 选择题（10分）
1、若T是图G的最小支撑树，则（ ） A．T必唯一 B. G不一定是连通图
4
C．T中必不含圈 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?j>0对应的变量都可以被选作换入变
2x?3x12?5x3?6x4??x12x2?3x3?x4?2????2x1?x2?x3?3x4??3??0(j?1,2,3,4)??xj
（1） 写出其对偶问题；
（2） 用图解法求对偶问题的解；
（3） 利用（2）的结果及对偶性质求原问题解。 三、运输问题（10分）
某土石方从三个产地运往四个工地，产地的产量、工地的需求量及单位运费如下表，求最优运输方案。
产地 销地 B1 A1 A2 A3 销量 四、支撑树问题（6分） 求下面网络图的最小支撑树：
3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 5