1、 运筹学期末复习题 一、判断题： 1、任何线性规划一定有最优解。（ ） 2、若线性规划有最优解，则一定有基本最优解。（ ） 3、线性规划可行域无界，则具有无界解。 （ ） 4、基本解对应的基是可行基。 （ ） 5、在基本可行解中非基变量一定为零。（ ） 6、变量取 0 或 1 的规划是整数规划。（ ） 7、运输问题中应用位势法求得的检验数不唯一。（ ） 8、产地数为 3，销地数为 4 的平衡运输中，变量组 X11， X13， X22， X33，X34可作为一组基变量 .（ ） 9、不平衡运输问题不一定有最优解。（ ） 10、 m+n-1 个变量构成基变量组的充要条件是它们不包含闭回路。（ ）
2、11、含有孤立点的变量组不包含有闭回路。 （ ） 12、不包含任何闭回路的变量组必有孤立点。（ ） 13、产地个数为 m销地个数为 n的平衡运输问题的系数距阵为 A，则有 r(A) m+n-1（ ） 14、用一个常 数 k加到运价矩阵 C的某列 的所有元素上 ,则最优解不变。（ ） 15、匈牙利法是求解最小值分配问题的一种方法。（ ） 16、连通图 G 的部分树是取图 G 的点和 G 的所有边组成的树。 （ ） 17、求最小树可用破圈法 .（ ） 18、 Dijkstra 算法要求边的长度非负。（ ） 19、 Floyd 算法要求边的长度非负。（ ） 20、在最短路问题中，发点到收点的最短路长
3、是唯一的。（ ） 21、连通图一定有支撑树。 （ ） 22、网络计划中的总工期等于各工序时间之和。 （ ） 23、网络计划中，总时差为 0 的工序称为关键工序。 （ ） 24、在网络图中，关键路线一定存在。 （ ） 25、紧前工序是前道工序。 （ ） 26、后续工序是紧后工序。 （ ） 27、虚工序是虚设的 ,不需要时间 ,费用和资源 ,并不表示任何关系的工序。（ ） 28、动态规划是求解多阶段决策问题的一种思路，同时是一种算法。（ ） 29、求最短路径的结果是唯一的。 （ ） 30、在不确定型决策中，最小机会损失准则比等可能性则保守性更强。（ ） 31、决策树比决策矩阵更适于描述序列决策过程
4、。 （ ） 32、在股票市场中，有的股东赚钱，有的股东赔钱，则赚钱的总金额与赔钱的总金额相等，因此称这一现象为零和现象。 （ ） 33、若矩阵对策 A 的某一行元素均大于 0，则对应值大于 0。 （ ） 34、矩阵对策中，如果最优解要求一个局中人采取纯策略，则另一局中人也必须采取纯策略。 （ ） 35、多阶段决策问题的最优解是唯一的。 （ ） 36、网络图中相邻的两个结点之间可以有两条弧。 （ ） 37、网络图 中可以有缺口和回路。 （ ） 二、选择题 1、线性规划的约束条件为： x1+x2+x3=3 2x1+2x2+x4=4 x1, x2, x3, x4 0 则可行解为： A、（ 3， 0，
5、 4， 0） B、（ 1， 1， 1， 0） C、（ 3， 4， 0， 0） D、（ 3， 0， 0， -2） 2、有 3 个产地 4 个销地的平衡运输问题模型具有特征： A、有 7 个变量 B、有 12 个约束 C、有 6 个约束 D、有 6 个基变量 3、当线性规划的可行解集合非空时一定： A、 包含原点 X=(0,0, 0) B、有界 C、无界 D、是凸集 4、线性规划的条件为： x1+x2+x3=3 2x1+2x2+x4=4 x1, x2, x3, x4 0 则基本可行解是： A、 (0,0,4,3) B、 (0,0,3,4) C、 (2,0,1,0) D、 (3,4,0,0) E 、
6、(3,0,0,-2) 5、线性规划具有无界解是指 A、可行解集合无界 B、有相同的最小比值 C、存在某个检验数 k 0 且 ik 0（ i=1,2 ,m） D、最优表中所有非基变理的检验数非零 6、线性规划可行域的顶点是： A、可行解 B、非基本解 C、基本可行解 D、最优解 E 、基本解 7、 minZ=x1-2x2-x1+2x2 5, 2x1+x2 8, x1, x2 0，则 A、有惟一最优解 B、有多重最优解 C、有无界解 D、无可行解 E、存在最优解 8、下列变量组是一个闭回路的有： A、 x21, x11, x12, x32, x33, x23 B、 x11, x12, x23, x
7、34, x41, x13 C、 x21, x13, x34, x41, x12 D、 x12, x32, x33, x23, x21, x11 E、 x12, x22, x32, x33, x23, x21 9、具有 m个产地 n个销地的平衡运输问题模型具有特征： A、有 mn 个变量 m+n 个约束 B、有 m+n 个变量 mn 个约束 C、有 mn 个变量 m+n-1 个约束 D、有 m+n-1 个基变量 mn-m-n+1 个非基变量 E、系数矩阵的秩等于 m+n-1 10、下列结论正 确的有： A、任意一个运输问题不一定存在最优解 B、任何运输问题都存在可行解 C、产量和销量均为整数的运
8、输问题必存在整数最优解 D、 m+n-1 个变量组构成基变量的充要条件是它不包括任何闭回路 E 运输单纯形法（表上作业法）的条件是产量等于销量的平衡问题 11、下列说法错误的是： A、若变量组 B 包含有闭回路，则 B 中的变量对应的列向量线性无关 B、平衡运输问题的对偶问题的变量非负 C、运输问题的对偶问题的约束条件为大于等于约束 D、运输问题的对偶问题的约束条件为大于等于约束 E、第 i行的位势 ui 是第 i个对偶变量 12、有 6 个产地 7 个销地的平衡运输问题模型的对偶模型具有特征 A、有 42 个变量 B、有 42 个约束 C、有 13 个约束 D、是线性规划模型 E、有 13
9、个变量 13、运输问题的数学模型属于 A、线性规划模型 B、整数规划模型 C、 0-1 整数规划模型 D、网络模型 E、不属于以上任何一种模型 14、匈牙利法的条件是： A、问题求最小值 B、效率矩阵的元素非负 C、人数与工作数相等 D、问题求最大值 E、效率矩阵的元素非正 15、下列说法正确的是 A、将指派（分配）问题的效率矩阵每行分别乘以一个非零数后最优解不变 B、将指派问题的效率矩阵每行分别加上一个数后最优解不变 C、将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变 D、指派问题的数学模型是整数规划模型 E、指派问题的数学模型属于网络模型 16、连通 G 有 n个点，其部分树是
10、 T，则有： A、 T 有 n个 n 条边 B、 T 的长度等于 G 的每条边的长度之和 C、 T 有 n个点 n-1 条边 D、 T 有 n-1 个点 n 条边 17、求最短路 的计算方法有： A、 Dijkstra 算法 B、 Floyd 算法 C、加边法 D、破圈法 E、 Ford-Fulkerson 算法 18、下列错误的结论是： A、给定某一阶段的状态，则在这一阶段以后过程的发展不受这一阶段以前各个阶段状态的影响，而只与当前状态有关，与过程过去的历史无关 B、动态规划是求解多阶段决策问题的一种算法策略，当然也是一种算法 C、动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题
11、的解而避免计算重复的子问题，以解决最优化问题的算法策略 D、动态规划数 学模型由阶段、状态、决策与策略、状态转移议程及指标函数 5 个要素组成 19、下列正确的结论是： A、顺推法与逆推法计算的最优解可能不一样 B、顺推法与逆推法计算的最优解相同 C、各阶段所有决策组成的集合称为决策集 D、各阶段所有决策组成的集合称为允许决策集合 E、状态 SK 的决策就是下一阶段的状态 20、对于不确定型的决策，由决策者的主观态度不同基本可分为以下几种准则 A、乐观主义准则 B、悲观主义准则 C、最大期望收益准则 D、等可能性准则 E、最小机会损失准则 21、对于不确定型的决策，某人采用乐观主义准则进行决策
12、，则应在收益表中 A、大中取大 B、大中取小 C、小中取大 D、小中取小 22、对于矩阵对策 G=S1, S2, A来说，局中人 I 有把握的至少得益为 V1，局中人 II 有把握的至多损失为 V2，则有 A、 V1 V2 B、 V1 V2 C、 V1=V2 D、 V1 V2 E、 C 或D 三、求解下列各题： 1、用图解法求解下列线性规划问题，并指出问题是具有唯一最优解，无穷多解，无界解还是无可行解。 （ 1） minZ=x1+1.5x2 （ 2） MaxZ=x1+x2 x1+3x2 3 x1 x2 2 x1 x2 2 0.5x1 1.5 x1， x2 0 x1+2x2 10 x1， x2
13、0 （ 3） MaxZ=x1+3x2 （ 4） minZ=100x1+800x2 5x1+10x2 50 x1 1 x1+x2 1 0.8x1+x2 1.6 x2 4 x2 2 x1， x2 0 x1， x2 0 （ 5） minX=x1+2x2 x1 x2 2 x1 3 x2 6 x1， x2 0 2、如下图所示， （ 1）求 A 到 F 的最短路线及最短距离 （ 2）求 A 到 E 的最短路线及最短距离 3、某公司有资金 400 万元，向 A、 B、 C 三个项目追加投资，三个项目可以有不同的投资额度，相应的效益如下表所示，问如何分配资金，才可使效益值最大。 投资额 效益值 项目 0 1
14、2 3 4 A 1 5 13 25 30 B 3 6 15 25 32 A 1B 1B 2B 3C 1C 2C 3C 4D 1D 2D 3E 1E 2F4322357634389876101 277 10345A 1B 1B 2B 3C 1C 2C 3D 1D 2E343546353 241525745 44C 0 24 30 42 42 4、某公司将某种设备 4 台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如下表所示，问如何安排，所获得利润最大。 工厂 盈利 设备台数 甲厂 乙厂 丙厂 0 1 2 3 4 0 2 10 12 13 0 3 7 11 12 0 4
15、5 13 13 5、有 5 个零件，先在车床上削，再在磨床上加工，时间如下表，问如何按排加工顺序，使 5 个零件的总工加工时 间为最少。（注：不计算时间长度） 零件 车床 磨床 1 1.5 0.25 2 1.0 2.5 3 2.0 0.5 4 0.75 1.25 5 1.25 1.75 6、请根据项目工序明细表（下表） （ 1）画出网络图 （ 2）计算各项时间参数 （ 3）确定关键路线 （ 1） 工序 a b c d e f g 紧前工序 a,b a,b b c d,e 时间 2 4 5 4 3 2 4 （ 2） 工序 a b c d e f g 紧前工序 a a b, c e d,e d,e
16、 时间 9 6 12 19 6 7 8 （ 3） 工序 a b c d e f g h i j k l m n o p q 紧前期序 a a a a a b,c e,f f d,g h j,k j,k i,l h m o,p 工序时间 60 14 20 30 21 10 7 12 60 10 25 10 5 15 2 7 5 8、在一台机床上要加工 10 个零件，下面列出它们的加工时间，请确定加工顺序，以便各零件在车间里停留的平均时间最短。 零件 1 2 3 4 5 6 7 8 9 10 时间 11 7 15 8 3 1 2 7.5 1.5 16 9、求解下列运输问题 （ 1）求 min 5
17、8 9 2 80 3 6 4 7 50 （参） 10 12 14 5 40 30 60 40 40 （ 2）求 min 3 11 3 10 7 1 9 2 8 4 7 4 10 5 9 3 6 5 6 （ 3）求 max 2 5 8 9 9 10 7 10 6 5 4 12 8 14 9 （ 4）求 min 21 17 23 25 300 10 15 30 19 400 23 21 20 22 500 200 200 250 550 10、求解下列指派问题（ min） （ 1） 12 6 9 15 C= 20 12 18 26 35 18 10 25 6 10 15 20 （ 2） 58 69 180 260 C= 75 50 150 230 65 70 170 250 82 55 200 280 （ 3） 85 90 73 90 C= 82 87 78 91 83 82 79 88 86 90 80 85 11、求解下列指派问题（ max） 10 9 6 17 C= 15 14 10 20 18 13 13 19 16 8 12 26 12、如图，求任意两个城市间的最短路 6 345121 223 10982 7616
