实用运筹学习题选详解.doc

1、 第 1 页 （ 共 37 页 ） 运筹学 判断题 一、 第 1 章 线性规划的基本理论及其应用 1、线性规划问题的可行解集不一定是凸集。（） 2、若线性规划无最优解则其可行域无界。（） 3、线性规划具有惟一的最优解是指最优表中非基变量检验数全部非零。（） 4、线性规划问题的每一个基本可行解对应可行域的一个顶点。（） 5、若线性规划模型的可行域非空有界，则其顶点中必存在最优解。（） 6、线性规划问题的大 M 法中， M 是负无穷大。（） 7、单纯形法计算中，若不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。（） 8、对于线性规 划问题的基本可行解，若大于零的基变量数小于约束条

2、件数，则解是退化的。（）。 9、一旦一个人工变量在迭代过程中变为非基变量后，则该变量及相应列的数字可以从单纯性表中删除，且这样做不影响计算结果。（） 10、线性规划的目标函数中系数最大的变量在最优解中总是取正值。（） 11、对一个有 n 个变量， m 个约束的标准型的线性规划问题，其可行域的顶点恰好为个 mnC 。（ ） 12、线性规划解的退化问题就是表明有多个最优解。（） 13、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。（） 14、单纯型法解线性规划问题时值为 0 的变量未必是非基变量。（） 15、任何线性规划问题度存在并具有唯一的对偶问题。（） 16、对偶问题的对偶问题

3、一定是原问题。（） 17、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题为无界解。（） 18、若原问题有可行解，则其对偶问题也一定有可行解。（） 19、若原问题无可行解， 其对偶问题也一定无可行解。（） 20、若原问题有最优解，其对偶问题也一定有最优解。（） 21、已知 *iy 为线性规划的对偶问题的最优解，若 * 0iy ，说明在最优生产计划中，第 i 种资源一定有剩余。（） 22、原问题具有无界解，则对偶问题不可行。（） 23、互为对偶问题，或者同时都有最优解，或者同时都无最优解。（） 24、某公司根据产品最优生产计划，若原材料的影 子价格

4、大于它的市场价格，则可购进原材料扩大生产。（） 25、对于线性规划问题，已知原问题基本解不可行，对偶问题基本解可行，可采用对偶单纯形法求解。（） 26、原问题（极小值）第 i 个约束是“ ”约束，则对偶变量 0iy 。（） 27、线性规划问题的原单纯形解法，可以看作是保持原问题基本解可行，通过迭代计算，逐步将对偶问题的基本解从不可行转化为可行的过程。（ ） *28、运输问题不能化为最小费用流问题来解决。（） 29、运输问题一定有最优解。（） 第 2 页 （ 共 37 页 ） 30、若运输问题的可行解退化，则存在等于零的数字格。（） 31、运输问题是特殊的线性规划问题，表上作业法也是特殊形式的单

5、纯形法。（） 32、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出，而且仅能找出唯一闭合回路。（） 33、如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数 k ，调运方案将不会发生变化。（） 34、如果运输 问题单位运价表的某一行（或某一列）元素分别加上一个常数 k ，调运方案将不会发生变化。（） 35、如果运输问题单位运价表的全部元素分别乘上一个常数 0kk ，调运方案将不会发生变化。（） 36、运输问题独立约束条件数 1mn个，变量数是 mn 个，于是基变量数为 mn m n个。（ ） 37、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函

6、数值。（） 38、一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解。（） 39、分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解 。（） 40、整数规划的最优解是先求相应的线性规划的最优解然后取整得到。（） 41、用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题的下界。（） 42、用分支定界法求解一个极大化的整数规划问题， 当得到多于一个可行解时。通常可任取其中一个作为下界值，再进行比较剪枝。（） 43、求最大值的整数规划问题中，其松弛问题的最优解是整数规划问题最优解的上界。（）44、匈牙

7、利算法是对指派问题求最小值的一种求解方法。（） 45、指派问题效率矩阵的每个元素分别乘上一个常数 k ，将不影响最优指派方案。（） 46、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。（） 47、匈牙利算法是对指派问题求最小值的一种求解方法。（） 48、应用匈牙 利算法求解工作指派问题时，对不打勾的行和打钩的列画横线。（） 49、求解效率最大的指派问题，可以用指派矩阵的最小元素减去该矩阵的各元素，得到新的指派矩阵，再用匈牙利算法求解。（） 二 、 第 4 章 1、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点的连线的长短曲

8、直等都要严格注意。（） 2、连通图 G 的部分树是取图 G 的点和 G 的所有边组成的树。（） 3、在有向图中，链和路是一回事。（） 4、连通图一定有支撑树。（） 5、避圈法（加边法）是：去掉图中所有边，从 最短边开始添加，加边的过程中不能形成圈，直到有 n 条边（ n 为图中的点数）。（） 6、应用矩阵法计算网络最小支撑树问题，应当在所有记有 T 的行里没有划去的元素中寻找最小元素。（） 7、用避圈法得到的最小树是惟一的，但破圈法得到的则不是。（） 8、最小生成树的 Kruskal 算法，每次迭代是将剩下边集中的最小权边加入树中。（） 9、 Dijkstra 算法和 Ford 算法均要求边的

9、权重非负。（？）。（） 10、 Dijkstra 算法可用于正权网络也可用于负权网络。（） 第 3 页 （ 共 37 页 ） 11、 Dijkstra 算法可用于求解有负权的网络最短路问题。（） 12、 Dijkstra 算法可用于求解最短路中的所有情形。（） 13、 Dijkstra 算法是求最大流的一种标号算法。（） 14、在最短路问题中，发点到收点的最短路长是惟一的。（） 15、求图的最小支撑树以及求图中一点到另一点的最短路问题，都可以归结为求解整数规划问题。（） 16、只有一个奇点的连通图是欧拉图。（） 17、在任何网络流中，零流总是一个可行流。（） 18、在 最大流问题中，最大流是惟

10、一的。（） 19、最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。（） 20、容量 ijC 是弧 ,ij 的实际通过量。（） 21、可行流是最大流的充要条件是不存在发点到收点的增广链。（） 22、一个具有多个发点和多个收点地求网络最大流的问题一定可以转化为具有单个发点和单个收点地求网络最大流问题。（） 23、形成增广链的条件是对于正向弧必须满足 0ijf 。（） 24、可行流的流量等于每条弧上的流量之和。（） 25、最大流量等于最大流。（） 26、求网络最大流的问题可归结为求解一个线性规划模型。（） 27、若已求得网络最大流，已标号节点的集合和未标号节点的集合给出了网络的最小割集

11、。（） 28、网络最大流等于该网络最大割容量。（） 29、割集中弧的流量之和称为割量。（） 30、最小割集等于最大流量。（） 31、任意可行流得流量不超过任意割量。（） 32、若已给网络的一个最小费用可行流，它的最小费用增广链对应于长度网络（ 赋权图）的最短路。（） 33、总时差为零的各项作业所组成的路线即为关键路线。（） 34、工程网络图中关键路线是最长路线。（） 35、网络规划中，工作的机动时间或富余时间叫做时差，分为总时差和单时差。（） 36、以同一节点为开始事件的各项作业的最早开始时间相同。（） 37、以同一节点为结束事件的各项作业的最迟结束时间相同。（） 38、节点的最早开始时间与最

12、迟完成时间两两相同所组成的路线是关键路线。（） 39、优化网络图计划，保证资源的最优配置和工期的按时完成，通常根据工作的时差，采用非关键路线上 的工作开始时间来实现。（） 40、采取应急措施，往往不但缩短了工期环可以减少工程总费用。（） 41、工程网络图中，只能有一个开始节点，但可以有多个结束节点。（） 42、工程网络图中，事项只表示某项工作结束的状态。（） 43、工程网络图可以有几个初始事项，但不可以有几个最终事项。（） 44、虚活动的作业时间等于零。（） 45、在网络图得关键路线上，总时差等于零。（） 三 、 第 6 章 1、矩阵对策中，如果最优解要求一个局中人采取纯策略，则另一个局中人也

13、必须采取纯策第 4 页 （ 共 37 页 ） 略。（） 2、任何矩阵对策一定存在混 合策路意义下的解，并可以通过求解两个互为对偶的线性规划问题得到。（） 3、对策模型的三要素：局中人、策略、赢得函数。（） 4、在两人零和对策支付矩阵的某一行（或某一列）上加上一个常数 k ，将不影响对策双方各自的最优策略。（） 5、二人零和对策支付矩阵的所有元素乘上一个常数 k ，将不影响对策双方各自的最优策略。（） 6、应对灾害天气制定预案的策略，同制订对一场可能发生的军事冲突的策略，具有相同的性质和过 程。（） 7、如果在任一“局势”中，全体局中人的“得失”相加总是等于零，这个对策就叫做“零和对策”。（）

14、8、任何一个给定的矩阵对策 G 一定有解（在混合扩充中的解）。（） 9、一个矩阵对策问题的赢得矩阵 ijAa，一定有不等式 m a x m in m in m a xij ijjjiiaa。（） 10、已知某对策问题的赢得函数矩阵为 1 3 25 2 3243，所以它是纯策略对策问题。（） 11、二人零和有限对策问题中，对局双方的赢得函数值 互为相反数。（） 12、最优纯策略中， m a x m i n m i n m a x ,ij ij ijjjiia a a为局中人赢得函数中的元素。（） 第 5 页 （ 共 37 页 ） 运筹学 实用教程 解答 题 一、 第 1 章 线性规划的基本理论及

15、其应用 1（ 1.3.1） 、 用图解法解 线性规划问题121212121212m ax 3 22 4 224 10. . 2 4 731,0z x xxxxxs t x xxxxx （答案： 12m a x 2 1; 5 , 3z x x ） x=(0:0.1:12); y1=(22-2*x)/4; y2=2*x-7; y3=(x+10)/4; y4=(x-1)/3; z1=(1-3*x)/2; z2=(4-3*x)/2; z3=(8-3*x)/2; z4=(12-3*x)/2; plot(x,y1,g:,x,y2,g:,x,y3,g:,x,y4,g:,x,z1,b-,x,z2,b-,x,z

16、3,b-,x,z4,b-); title(); 第 6 页 （ 共 37 页 ） 2（ 1.3.2）、用图解法解线性规划问题12212121212m ax 2102 5 60. . 183 44,0z x xxxxs t x xxxxx （答案： 12m a x 3 1; 1 3 , 5z x x ） x=(0:0.1:15); y1=10; y2=(60-2*x)/5; y3=18-x; y4=44-3*x; z1=1-2*x; z2=4-2*x; z3=8-2*x; z4=12-2*x; plot(x,y1,g:,x,y2,g:,x,y3,g:,x,y4,g:,x,z1,b-,x,z2,b

17、-,x,z3,b-,x,z4,b-); title(); 3（ 1.3.3）、用图解法解线性规划问题1211212m ax 3 23. . 0,0z x xxs t x xxx （答案： 可行 域无界，无最优解 ） 第 7 页 （ 共 37 页 ） - 3 x1+ 2 x2= 4- 3 x1+ 2 x2= 1x1= 3x1- x2= 0(图形是 matlab 结合几何画板绘制出来的 ) 4（ 1.3.4）、用图解法解线性规划问题12121212max 3 21. . 2 2 4,0z x xxxs t x xxx （答案： 无可行域，无最优解 ） x1+ x2= 12 x1+ 2 x2= 4(

18、图形是 matlab 结合几何画板绘制出来的 ) 第 8 页 （ 共 37 页 ） 5（ 1.3.5）、用图解法解线性规划问题12121212m ax 4 33 2 6. . 3 18,0z x xxxs t x xxx （答案： 可行域无界，无最优解 ） x=(0:0.1:3); y1=(6+3*x)/2; y2=(18+x)/3; z1=(12-4*x)/3; z2=(20-4*x)/3; plot(x,y1,g:,x,y2,g:,x,z1,b-,x,z2,b-); title(); (图形是 matlab 结合几何画板绘制出来的 ) 6（ 1.3.6）、用图解法解线性规划问题121121

19、2max 2 34 16. . 2 8,0z x xxs t x xxx （答案： 12m a x 1 4 ; 4 , 2z x x ） x=(0:0.1:9); y1=(8-x)/2; z1=(12-2*x)/3; z2=(20-2*x)/3; plot(x,y1,g:,x,z1,b-,x,z2,b-); title(); 第 9 页 （ 共 37 页 ） 2 x1+ 3 x2= 122 x1+ 3 x2= 202 x1+ 3 x2= 12x1+ 2 x2= 84 x1= 16(图形是 matlab 结合几何画板绘制出来的 ) 7（ 1.4.1）、用单纯形法计算12212121212m ax

20、 2102 5 60. . 183 44,0z x xxxxs t x xxxxx （答案： 12m a x 3 1; 1 3 , 5z x x ，松弛变量 3 4 5 65 , 9 , 0x x x x ） 详解：引进 松弛变量 3 4 5 6, , ,x x x x ，标准化模型为12231 2 41 2 51 2 61 2 3 4 5 6m a x 2102 5 60. . 183 44, , , , , 0z x xxxx x xs t x x xx x xx x x x x x 。 建立初始单纯形表并 作基的变换如下， x X1 X2 X3 X4 X5 X6 b thita c 2

21、1 0 0 0 0 X3 0 0 1 1 0 0 0 10 X4 0 2 6 0 1 0 0 60 60/2=30 第 10 页 （ 共 37 页 ） X5 0 1 1 0 0 1 0 18 18/1=18 X6 0 3 1 0 0 0 1 44 44/3 最小！ zj 0 0 0 0 0 0 0 Zj-cj -2 -1 0 0 0 0 先找负的绝对值最大的定入 X3 0 0 1 1 0 0 0 10 10 X4 0 0 13/3 0 1 0 -2/3 92/3 92/13 X5 0 0 2/3 0 0 1 -1/3 10/3 5 最小！定出 X1 2 1 1/3 0 0 0 1/3 44/3

22、 44 zj 2 2/3 0 0 0 2/3 88/3 下一行 +cj Zj-cj 0 -1/3 0 0 0 2/3 先找负的绝对值最大的定入 X3 0 0 0 1 0 -3/2 1/2 5 X4 0 0 0 0 1 -13/2 3/2 9 X2 1 0 1 0 0 3/2 -1/2 5 X1 2 1 0 0 0 -1/2 1/2 13 zj 2 1 0 0 1/2 1/2 31 下一行 +cj Zj-cj 0 0 0 0 1/2 1/2 最优性判别，得知最优解 从表中得 答案 ， 12m a x 3 1; 1 3 , 5z x x ，松弛变量 3 4 5 65 , 9 , 0x x x x

23、。 8（ 1.4.2）、用单纯形法计算1 2 31 2 31 2 31 2 3m a x 4 3 63 3 3 0. . 2 3 3 4 0, , 0z x x xx x xs t x x xx x x （答案： 1 2 3m a x 7 0 ; 0 , 1 0 , 2 0 / 3z x x x ） 详解：引进松弛变量 45,xx，标准化模型为1 2 31 2 3 41 2 3 51 2 3 4 5m a x 4 3 63 3 3 0. . 2 3 3 4 0, , , , 0z x x xx x x xs t x x x xx x x x x 。 建立初始单纯形表并作基的变换如下， x X1 X2 X3 X4 X5 b thita c 4 3 6 0 0 X4 0 3 1 3 1 0 30 30/3=10, 最小出基 X5 0 2 2 3 0 1 40 40/310 zj 0 0 0 0 0 0 Zj-cj -4 -3 -6 0 0 先找负的绝对值最大的定入 X3 6 1 1/3 1 1/3 0 10 30 X5 0 -1 1 0 -1 1 10 10, 最小出基 zj 6 2 6 2 0 60 下一行 +cj Zj-cj 2 -1 0 2 0 先找负的绝对值最大的定入 X3 6 4/3 0 1 2/3 -1/3 20/3 X2 3 -1 1 0 -1 1 10