1、（ 共 8 页，第 1 页 ） 运筹学复习题1. 某一求目标函数极大值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下：XB b X1 X2 X3 X4 X5 X6X2X3X5141002a31000100a44001a223CjZ j a5 0 0 a6 0 -6当现行解为唯一最优解时有 D 。A. 10 a50 a30 B. a30 a50 a60C. 20 a50 a60 D. a10 a60 a50 2. 单纯形乘子是指 A 。A B. C. D. 1BCbB1ACB1bBC13在满足下列条件 B 时，增加资源是有利的。 A单位资源代价大于资源的影子价格B单位资源代价小于资源的
2、影子价格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 。 AP
3、 kPk+1=0 BP kPk+1 DP k=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 （ 共 8 页，第 2 页 ） 12. 目标规划中，以下式子正确的为 D 。A. d+ 0, d- 0 B. d+ d- 0 C. d+ d- 0 D. d + d- 0 13 线性规划的原问题与其对偶问题之
4、间关系不存在的是 C ；A.对偶问题的对偶问题是原问题；B.原问题存在最优解，其对偶问题必存在最优解；C.原问题无可行解，其对偶问题必无可行解；D.原问题有无界解，其对偶问题无可行解。14 求解整数规划常用的算法有 B 。A.单纯形法和分枝定界法 B.分枝定界法和割平面法C.单纯形法和割平面法 D.单纯形法和完全枚举法15 含有 n 个顶点的完全图，其边数有 C 条。A.n2 B.2n C. D. 2n(n-1)1(2n16 用割平面法求解整数规划时，构造的割平面只能切去 C 。 A整数可行解 B整数解最优解 C非整数解 D无法确定1. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，
5、减少一个约束条件，可行域的范围一般将扩大。 （ ）2. 如果线性规划问题存在最优解，则最优解点不一定在可行域边界上。 （ ）3. 单纯形法计算中，如果不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （ ）4. 可以采用避圈法和破圈法求解网络中的最短路问题。 （ ）5. 所有顶点次数之和等于所有边数的 2 倍。 （ ）6.树 图 的 任 意 两 个 顶 点 间 有 且 只 有 有 一 条 连 通 路 。 （ ）7.对 可 行 流 来 说 ， 发 点 的 净 流 出 量 ,等 于 收 点 的 净 流 入 量 。 （ ）8.割 平 面 法 每 次 切 割 的 都 是 原 问
6、题 的 非 可 行 整 数 解 。 （ ）9. 可 以 采 用 避 圈 法 和 破 圈 法 求 解 网 络 中 的 最 短 路 问 题 。 （ ）10.目 标 规 划 中 的 优 先 因 子 P1， P2， Pk 中 ， 必 定 有 P1P2,， PkPk+1,。 ( )1.已知 A、B、C、D 四项任务分别由甲、乙、丙、丁四个人去完成，每人最多承担一项工作，每项工作只能由一个人单独完成。由于各人的专长不同，他们完成各项任务的时间（h）不相同（如下表） ，现问该如何分配才能使得四个人完成这四项任务总的时间为最少。（写出计算过程及最终答案） （8 分）人任务 甲 乙 丙 丁A 2 10 9 7B
7、 15 4 14 8C 13 14 16 11D 4 15 13 9（ 共 8 页，第 3 页 ） 2. 已知运输的产销平衡表和单位运价表如下，试采用表上作业法确定运费最少的最佳运输方案，并求出最少费用。 （10分） 产销平衡表 单位：t销地产地 B1 B2 B3 B4 产量A1 7A2 4A3 9销量 3 6 5 6单位运价表 单位：元/t销地产地 B1 B2 B3 B4A1 3 11 3 10A2 1 9 2 8A3 7 4 10 53. 用 单 纯 形 表 上 作 业 法 求 解 下 列 线 性 规 划 。213maxxz0,5642211x写 出 下 列 线 性 规 划 问 题 的 对
8、 偶 问 题 。 （ 8 分 ）32147minxxz0,0351564321321 xx取 值 无 约 束 ，（1）用闭回路法求检验数（表 5-55）表5-55B1 B2 B3 B4 AiA1 10 5 2 3 70A2 4 3 1 2 80A3 5 6 4 4 30bj 60 60 40 20（2）用位势法求检验数（表 5-56）表5-56B1 B2 B3 B4 AiA1 9 15 4 8 10A2 3 1 7 6 30（ 共 8 页，第 4 页 ） A3 2 10 13 4 20A4 4 5 8 3 43bj 20 15 50 15某机械厂计划生产甲、乙两种产品，分别在 A、B、C 三种
9、设备上加工，已知各设备加工不同产品所需的时间和机器的生产能力及其利润情况如下表：甲 乙 机器生产能力(小时)A 2 2 12B 4 0 16C 0 5 15利润(元/件) 2 3该机械厂经营的目标如下：（1）力求使利润不低于 15 元；（2）甲、乙两种产品的常量需保持 1：2 的比例；（3）A 为贵重设备，严格禁止超时使用；（4）设备 C 可以适当加班，但是要控制；设备 B 既要充分利用，又尽可能不加班。且设备的重要性上 B 是 C 的 3 倍。试建立该问题的目标规划模型。求下列运输问题的最优解（1）C 1 目标函数求最小值； （2）C 2 目标函数求最大值13590648273 903617
10、8514215 45 20 40 60 30 50 40 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余 3 人每人做一项工作（1） 20156836209C【解】最优解 1,43XZ（ 共 8 页，第 5 页 ） （2） 2053416701986C【解】虚拟一个人，其效率取 4 人中最好的，构造效率表为1 2 3 4 5甲 26 38 41 52 27乙 25 33 44 59 21丙 20 30 47 56 25丁 22 31 45 53 20戊 20 30 41 52 20最优解：甲戊完成工作的顺序为 3、5、1、2、4，最优值 Z=165最优分配方案：甲完成第 3、4
11、 两项工作，乙完成第 5 项工作，丙完成第 1 项工作，丁完成第 2 项工作。5.9 求解下列最大值的指派问题： （1） 261869304570C【解】最优解 1,64XZ（2） 86917520469C【解】最优解 1,4XZ第 5 人不安排工作。（ 共 8 页，第 6 页 ） 已知 A、B、C、D 四项任务分别由甲、乙、丙、丁、戊五个人去完成，每人最多承担一项工作，每项工作只能由一个人来完成。因各人的专长不同，他们完成各项任务的时间（h）不相同（如下表） 。由于某种原因，丁不愿承担 D 任务。现问该如何分配才能使得完成这四项任务总的时间为最少。 （写出计算过程及最终答案）人任务 甲 乙
12、丙 丁 戊A 10 2 3 15 9B 5 10 15 2 4C 15 5 14 7 15D 20 15 13 6 8单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的哪一个极点1212max3,0Z用单纯形法求解下列线性规划 123123max40,jZxx网络最短路问题。求解下列网络图中 V1点到 V7点之间的最短距离。要求有求解过程，并将最终路线标示在图上。V1V2 V5V4V6V7V3572 762 16342如下图所示，给定一个出租汽车的行驶线路网格，两点连线上的数字表示两点间的距离（或费用） ，试求由 A 到 E 的最佳行驶线路，使其距离（运输总费用）最小。
13、（ 共 8 页，第 7 页 ） 3用大 M 法求解下列线性规划：123123max055,jZxx求解对偶问题：无 约 束4321432143,0, 684156780maxxxxxZ 123412341234max679650,Zxx无 约 束求下列运输问题的最优解（1）C 1 目标函数求最小值； （2）C 2 目标函数求最大值13592064873 9036178514215 45 20 40 60 30 50 40 求最小部分树。 （a）用破圈法,（b）用生成树法。6.5 某乡政府计划未来 3 年内，对所管辖的 10 个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10 个村之间修
14、建公路的费用如表 6-20 所示。乡镇府如何选择修建公路 A B1B2 B3321 C1 C245 D1D2 D3 E25231533315（ 共 8 页，第 8 页 ） 的路线使总成本最低。表 6-20两村庄之间修建公路的费用( 万元)1 2 3 4 5 6 7 8 9 101234567891012.8 10.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求 v1 到 v10 的最大流及最大流量；图 644
