ljz运筹学复习题集.doc

运筹学复习题1. 某一求目标函数极大值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下：XBbX1X2X3X4X5X6X2X3X5141002a31000100a44001a223CjZja500a60-6 当现行解为唯一最优解时有 D 。 A. 10 a50 a30 B. a30 a50 a60 C. 20 a50 a60 D. a10 a60 a50 2. 单纯形乘子是指 A 。A B. C. D. 3在满足下列条件 B 时，增加资源是有利的。 A单位资源代价大于资源的影子价格B单位资源代价小于资源的影子价格 C单位资源代价等于资源的影子价格 D单位资源代价不等于资源的影子价格 4线性规划的灵敏度分析应在_B_的基础上，分析系数的变化对最优解产生的影响。A初始单纯形表 B. 最优单纯形表 C. 对偶问题初始单纯形表 D. 对偶问题的最优单纯形表 5一个图G中,奇点的个数为 B 。 A.偶奇数 B.偶数 C.奇数或偶数 D. 不能确定 6若运输问题已求得最优解，此时所求出的检验数一定是全部 A 。A大于或等于零 B大于零 C小于零 D小于或等于零 7. 线性规划一般模型中，自由变量可以用两个非负变量的 B 代换。A和 B差 C积 D商 8目标规划中，对于优先级别，则下列说法正确的是 C 。 APkPk+1=0 BPkPk+1 DPk=Pk+1 9求解指派问题的匈牙利方法要求系数矩阵中每个元素都是 A 。A非负的 B大于零 C无约束 D非零常数 10若运输网络G中发点到收点不存在流f的增广链，则称流f为G 的 C 。A最小流 B零流 C最大流 D无法确定 11.运输问题中，闭合回路的数字格分布在每行每列的个数必定为B。A. 1 B. 2 C. 3 D. 4 12. 目标规划中，以下式子正确的为 D 。 A. d+ 0, d- 0 B. d+ d- 0 C. d+ d- 0 D. d+ d- 0 13线性规划的原问题与其对偶问题之间关系不存在的是 C ；A.对偶问题的对偶问题是原问题；B.原问题存在最优解，其对偶问题必存在最优解；C.原问题无可行解，其对偶问题必无可行解；D.原问题有无界解，其对偶问题无可行解。14求解整数规划常用的算法有 B 。A.单纯形法和分枝定界法 B.分枝定界法和割平面法C.单纯形法和割平面法 D.单纯形法和完全枚举法15含有n个顶点的完全图，其边数有 C 条。A.n2 B.2n C. D. 2n(n-1)16用割平面法求解整数规划时，构造的割平面只能切去 C 。 A整数可行解 B整数解最优解 C非整数解 D无法确定1. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 （ ）2. 如果线性规划问题存在最优解，则最优解点不一定在可行域边界上。（ ）3. 单纯形法计算中，如果不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （ ）4. 可以采用避圈法和破圈法求解网络中的最短路问题。 （ ）5. 所有顶点次数之和等于所有边数的2倍。 （ ）6.树图的任意两个顶点间有且只有有一条连通路。 （ ）7.对可行流来说，发点的净流出量,等于收点的净流入量。 （ ）8.割平面法每次切割的都是原问题的非可行整数解。 （ ）9. 可以采用避圈法和破圈法求解网络中的最短路问题。 （ ）10.目标规划中的优先因子P1，P2，Pk中，必定有P1P2,，PkPk+1,。 ()1.已知A、B、C、D四项任务分别由甲、乙、丙、丁四个人去完成，每人最多承担一项工作，每项工作只能由一个人单独完成。由于各人的专长不同，他们完成各项任务的时间（h）不相同（如下表），现问该如何分配才能使得四个人完成这四项任务总的时间为最少。（写出计算过程及最终答案）（8分）人任务甲乙丙丁A21097B154148C13141611D4151392. 已知运输的产销平衡表和单位运价表如下，试采用表上作业法确定运费最少的最佳运输方案，并求出最少费用。（10分） 产销平衡表 单位：t销地产地B1B2B3B4产量A17A24A39销量3656单位运价表 单位：元/t销地产地B1B2B3B4A1311310A21928A374105 3. 用单纯形表上作业法求解下列线性规划。 写出下列线性规划问题的对偶问题。（8分） （1）用闭回路法求检验数（表5-55）表5-55B1B2B3B4AiA11052370A2431280A3564430bj60604020（2）用位势法求检验数（表5-56）表5-56B1B2B3B4AiA19154810A2317630A321013420A4458343bj20155015某机械厂计划生产甲、乙两种产品，分别在A、B、C三种设备上加工，已知各设备加工不同产品所需的时间和机器的生产能力及其利润情况如下表：甲乙机器生产能力(小时)A2212B4016C0515利润(元/件)23该机械厂经营的目标如下：（1）力求使利润不低于15元；（2）甲、乙两种产品的常量需保持1：2的比例；（3）A为贵重设备，严格禁止超时使用；（4）设备C可以适当加班，但是要控制；设备B既要充分利用，又尽可能不加班。且设备的重要性上B是C的3倍。试建立该问题的目标规划模型。求下列运输问题的最优解（1）C1目标函数求最小值； （2）C2目标函数求最大值 15 45 20 40 60 30 50 40 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作 （1） 【解】最优解（2）【解】虚拟一个人，其效率取4人中最好的，构造效率表为12345甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最优解：甲戊完成工作的顺序为3、5、1、2、4，最优值Z=165最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。5.9 求解下列最大值的指派问题： （1）【解】最优解（2）【解】最优解第5人不安排工作。已知A、B、C、D四项任务分别由甲、乙、丙、丁、戊五个人去完成，每人最多承担一项工作，每项工作只能由一个人来完成。因各人的专长不同，他们完成各项任务的时间（h）不相同（如下表）。由于某种原因，丁不愿承担D任务。现问该如何分配才能使得完成这四项任务总的时间为最少。（写出计算过程及最终答案）人任务甲乙丙丁戊A1023159B5101524C15514715D20151368单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的哪一个极点 用单纯形法求解下列线性规划网络最短路问题。求解下列网络图中V1点到V7点之间的最短距离。要求有求解过程，并将最终路线标示在图上。V1V2V5V4V6V7V357276216342如下图所示，给定一个出租汽车的行驶线路网格，两点连线上的数字表示两点间的距离（或费用），试求由A到E的最佳行驶线路，使其距离（运输总费用）最小。 243533313211355 52用大M法求解下列线性规划： 求解对偶问题： 求下列运输问题的最优解（1）C1目标函数求最小值； （2）C2目标函数求最大值 15 45 20 40 60 30 50 40 求最小部分树。（a）用破圈法,（b）用生成树法。6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。表6-20两村庄之间修建公路的费用(万元)123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.8【解】属于最小树问题。6.6在图642中，求A到H、I的最短路及最短路长。 图642图644求v1到v10的最大流及最大流量；（ 共 8 页，第 8 页 ）