《ljz运筹学复习题集.docx》由会员分享，可在线阅读，更多相关《ljz运筹学复习题集.docx（15页珍藏版）》请在三一文库上搜索。
1、运筹学复习题1 .某一求目标函数极大值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下：A.ai 0 a 5 0 a 3 0B. as 0 a5- 0 ae_ 0C. a2= 0 a5 0 a6 0D. ai 0 a6V 0 a 5V 0XbbXiX2X3X4X5X6X2ai0i000a2X3420ia402X5i0a3004i3Cj- Zja500ae0-6当现行解为唯一最优解时有D2.单纯形乘子是指AoA. CbBj b. CBBb C. CBB AD. C CbB, b3. 在满足下列条件 旦时，增加资源是有利的。A.单位资源代价大于资源的影子价格B.单位资源代价小于资源的影子价
2、格C ?单位资源代价等于资源的影子价格D ?单位资源代价不等于资源的影子价格4?线性规划的灵敏度分析应在 B_的基础上，分析系数的变化对最优解产生的影响。A.初始单纯形表B.最优单纯形表C.对偶问题初始单纯形表D.对偶问题的最优单纯形表5. 一个图G中，奇点的个数为_B oA.偶奇数B.偶数C.奇数或偶数 D.不能确定6?若运输问题已求得最优解，此时所求出的检验数一定是全部A oA.大于或等于零 B .大于零 C .小于零 D .小于或等于零7.线性规划一般模型中，自由变量可以用两个非负变量的_B 代换。A.和B .差C .积D .商&目标规划中，对于优先级别，则下列说法正确的是_C oA.
3、P X P +i =0 B . PkPP k+i D . Pk=R+i9. 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是A oA.非负的B .大于零C .无约束D .非零常数10. 若运输网络G中发点到收点不存在流 f的增广链，则称流f为G的_C 0A.最小流B .零流C .最大流 D .无法确定11. 运输问题中，闭合同路的数字格分布在每行每列的个数必定为B oA. i B. 2 C. 3 D. 412.目标规划中，以下式子正确的为A. d 0, d 0D. d x d = 013线性规划的原问题与其对偶问题之间关系不存在的是CA.对偶问题的对偶问题是原问题；B.原问题存在最优解，其对
4、偶问题必存在最优解；C.原问题无可行解，其对偶问题必无可行解；D.原问题有无界解，其对偶问题无可行解。14求解整数规划常用的算法有_B oA.单纯形法和分枝定界法B.分枝定界法和割平面法C.单纯形法和割平面法D.单纯形法和完全枚举法15含有n个顶点的完全图，其边数有C条。21A.n B.2n C.?n （n-1 ） D. 2n （n-1）16用割平面法求解整数规划时，构造的割平面只能切去CA.整数可行解B ?整数解最优解C ?非整数解 D ?无法确定1.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可 行域的范围一般将扩大。（V ）2 .如果线性规划问题存在最优解，
5、则最优解点不一定在可行域边界上。（X ）3 .单纯形法计算中，如果不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。（V ）4 .可以米用避圈法和破圈法求解网络中的最短路问题。（V ）5 .所有顶点次数之和等于所有边数的2倍。（V ）6 .树图的任意两个顶点间有且只有有一条连通路。（V ）7 .对可行流来说，发点的净流出量，等于收点的净流入量。（V ）8 .割平面法每次切割的都是原问题的非可行整数解。（V ）9 .可以米用避圈法和破圈法求解网络中的最短路问题。（V ）10.目标规划中的优先因子 P1, P2，Pk中，必定有 P1?P2,，Pk?Pk+1,。（V）1 .已知A
6、 B、C、D四项任务分别由甲、乙、丙、丁四个人去完成，每人最多承担一项工作，每项工作只能由一个人单独完成。由于各人的专长不同，他们完成各项任务的时间（h）不相同（如下表），现问该如何分配才能使得四个人完成这四项任务总的时间为最少。（写出计算过程及最终答案）（8分）人 任务甲乙丙丁A21097B154148C13141611D4151392 .已知运输的产销平衡表和单位运单位运价表单位：元/t”,销地BT!BT1BalB4价表如下，试米用表上作业法确定运费最少的最佳运输方案，弁求出最少费用。（10分）产销平衡表单位：t销地产地、B1B2B3B4*曰 ）单A17A24A39销吊3656A13113
7、10A21928A3741053 .用单纯形表上作业法求解下列线性规划。max z = 2 吾 3x22xi 2x2 124 165x2 乞 15Xx2 -写出下列线性规划问题的对偶问题。（8分）min z - 7x1 4x2 - 3x3T-4x1 - 2x2 - 6x3 乞 24 -3X - 6xA 4X 155x2 3x3 二 30xA 0, x 2取值无约束,x3 - 0(1)用闭回路法求检验数(表 5-55 )表 5-55B1B2B3B4AiA11052370A2431280A3564430bj60604020（2）用位势法求检验数（表 5-56）表 5-56B1B2B3B4AiA19
8、154810A2317630A321013420A 4458343bi20155015某机械厂计划生产甲、乙两种产品，分别在A、B、C三种设备上加工，已知各设备加工不同产品所需的时间和机器的生产能力及其利润情况如下表：甲乙机器生产能力(小时)A2212B4016C0515利润(元/件)23该机械厂经营的目标如下：(1) 力求使利润不低于 15元；(2)甲、乙两种产品的常量需保持1 : 2的比例；(3) A为贵重设备，严格禁止超时使用；设备的(4)设备C可以适当加班，但是要控制；设备B既要充分利用，又尽可能不加班。且重要性上B是C的3倍。试建立该问题的目标规划模型。(2) C2目标函数求最大值2
9、 7 10 15 20 60C=14 13 9 6 305 8 7 10 90求下列运输问题的最优解(1) Ci目标函数求最小值；35 950G = 64 8 5 2511 13 127 3060 3050 401545 20 40求解下列最小值的指派问题，其中第(2)题某人要作两项工作，其余 3人每人做一项工作12 6915 20 12 18 26(1) C 一35 18 10 25610 15 20 一m最优解-111X=,Z=431J一2638 4152272533 445921C =2030 475625231 455320一【解】虚拟一个人，其效率取4人中最好的，构造效率表为1234
10、5甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最优解：甲？戊完成工作的顺序为3、5、1、2、4,最优值Z=165最优分配方案：甲完成第 3、4两项工作，乙完成第 5项工作，丙完成第1项工作，丁完成 第2项工 作。5.9求解下列最大值的指派问题(1)c =1015189617114 10 2013 13 19J6m最优解12 26-9 1016 C =101215m最优解,Z =44第5人不安排工作。已知A、B、C D四项任务分别由甲、乙、丙、丁、戊五个人去完成，每人最多承担一项工作，每项工作只能由一个人来完成。因各人的专长不同，
11、他们完成各项任务的时间（h）不相同（如下表）。由于某种原因，丁不愿承担D任务。现问该如何分配才能使得完成这四项任务总的时间为最少。（写出计算过程及最终答案）-人1甲乙丙丁戊任务A1023159B5101524C15514715D20151368单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的哪一个极点.max Z=x 3X2-2x 1 X2 -22x 3X2_12xz - 0用单纯形法求解下列线性规划maxZ = 3x 1 4x2 x32八 3X2X3 三 1* % +2x2 +2X3 兰 3xj 0, j 1,2,3网络最短路问题。求解下列网络图中V1点到V7点之间
12、的最短距离。要求有求解过程弁将最终路线标7K在图上。如下图所示，给定一个出租汽车的行驶线路网格，两点连线上的数字表示两点间的距离（或费用），试求由A到E的最佳行驶线路，使其距离（运输总费用）最小。用大M法求解下列线性规划：m a) Z = 1 ? - 5 X5xi 3x2 怡=1 0* -5xi + X2_1 OX3 兰 1 5Xj 兰 0 ,j = 1,2,3求解对偶问题：max Z = x 1 2X2 4X3 - 3x4jOxA i+X2 -x3 4x4 =87x104x1 -8X2 6X3 x4 乞 6x1, x2 _0,x3 _0, x4 无约束maxZ 二-2 为 3x2 6x37x
13、43 为 一 2x2 + x3 - 6% = 96 片 + 5x3 _ x4 启 6* 一为 + 2x2 x3 + 2& 兰2Ax1 10求下列运输问题的最优解(1)01目标函数求最小35 92 50G = 64 85 25J1 13 12 7 301545 20 40（2） C2目标函数求最大值7100= 1413.5860 3015 20 609630710 9050 40求最小部分树。 （a）用破圈法,（b）用生成树 法。0I II6.5某乡政府计划未来 3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。表 6-20两村庄之间修建公路的费用（万元）12345678910112.810.58.512.713.914.813.212.78.929.67.713.111.215.712.413.610.5313.812.68.68.510.515.813.4411.47.59.69.39.814.658.38.98.88.29.168.012.711.710.5714.813.612.689.78.998.810m属于最小树问题。6.6在图6- 42中，求A到H、I的最短路及最短路长。图6 -42求Vi到Vio的最大流及最大流量图6 44