运筹学复习题(2)

供应量运价（元/吨） A1 A2 A3 需求量（吨）

求总运费最小的运输方案

2、 下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价， 试用表上作业法求最优调运方案。

销地 产地 1 2 销量 8 7 4 3 5 9 20 10 20 3、 用表上作业法求下列运输问题的最优解。

销地 产地 1 2 3 销量 5 1 8 2 4 0 3 6 7 9 10 11 4、下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价，试用表上作业法求最优调运方案。

销地 产地 A B C D 产量 12 14 4 A B C 产量 15 25 A B C 产量 B1 9 14 5 9 B2 12 7 13 12 B3 10 6 15 13 B4 （吨） 8 11 20 16 24 8 18 1 2 3 销量 9 3 8 7 4 9 4 5 5 7 6 2 1 3 2 5 11 3 3 5 5、下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价，试用表上作业法求最优调运方案。

销地 产地 1 2 3 销量 4 1 4 6 1 2 5 0 3 7 5 1 6 5 6 3 20 8 8 4 A B C D 产量 第四章 整数规划

一 复习思考题

1．试述研究整数规划的意义，并分别举出一个纯整数规划、混合整数规划和0—1规划的例子。

2．有人提出，求解整数规划时可先不考虑变量的整数约束，而求解其相应的线性规划问题，然后对求解结果中为非整数的变量凑整。试问这种方法是否可行，为什么? 3．试述用分枝定界法求解问题的主要思想及主要步骤，并说明这种方法的优缺点。 5．除教材中列举的例子外，你认为引进0—1变量对建立实际问题的数学模型还有哪些作用，试举例说明。

6．什么是隐枚举法，为什么说分枝定界法也是一种隐枚举法

7..指派问题是0—1型整数规划的一类特殊例子，你能否设计一个用分枝定界法来求解指派问题的程序步骤。

二、判断下列说法是否正确

1 、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值； 2 、用分技定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数是该问题

目标函数值的下界；

3、 用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取

其中一个作为下界值，再进行比较剪枝；

三、计算题

1、 下表是4个小组各自完成各项不同工作所需的时间，试确定最优分派方案。

工作 甲 乙 丙 丁 小组 A 19 10 16 20 B 14 12 9 16 C 12 15 11 13 D 18 10 14 17 2、 6个人完成4项任务，由于个人的技术专长不同，他们完成4项任务所获得的收益如下

表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使总收益最大的分派方案。

工作 甲 乙 丙 丁 人 A 3 5 4 5 B 6 7 6 8 C 8 9 8 10 D 10 10 9 11 E 12 11 10 12 F 13 12 11 13 3、某公司要把4个有关能源工程项目承包给4个互不相关的承包者，规定每个承包商只能

且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？

各承包商对工程的报价如下表所示： 单位：万元

项目 1 2 3 4 投标者 甲 乙 丙 丁 15 19 26 19 18 23 17 21 21 22 16 23 24 18 19 17 4、个人完成五项任务，由于个人的技术专长不同，每人完成各项任务的时间如下表所示。

（1）若规定每人只能做一项工作，一项工作任务只需一人操作，试问这四个人应分派做哪四项工作，他们所花费的总时间最短。

（2） 如果规定四个人必须完成五项工作，其中有一个人可以兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的分派方案。

工作 人 甲 乙 丙 丁 25 39 34 24 29 38 27 42 31 26 28 36 42 20 40 23 37 33 32 45 A B C D E 5、某厂拟用5台机床加工5种零件，加工费（元）如下表所示。若每台机床加工一种零件，则应如何分配任务才能使总加工费最少？

零件 1 2 3 4 5 机床 1 2 3 4 5 解 6、五人翻译五种外文的速度（印刷符号/小时）如下表所示：

语种 英 人 甲 900 400 600 800 500 俄 日 德 法 4 1 8 4 2 9 8 4 7 7 8 4 6 6 3 6 5 7 6 2 5 5 4 3 1 乙 丙 丁 戊 800 900 400 1000 500 700 800 500 900 300 600 300 1000 500 900 600 600 800 500 800 若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题： （1）应如何指派，使总的翻译效率最高？

（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？

第五章 图与网络分析

一 复习思考题

1．通常用G(V，E)来表示一个图，试述符号V，E及这个表达式的涵义。

2．解释下列各组名词，并说明相互间的联系和区别：(a)端点，相邻，关联边；(b)环，多重边，简单图；(c)链，初等链；(d)圈，初等圈，简单圈；(e)回路，初等路；(f)节点的次，悬挂点，孤立点；(g)连通图，支撑子图；(h)有向图，赋权图。 3．图论中的图同一般工程图、几何图的主要区别是什么，试举例说明。

4．试述树图、图的支撑树及最小支撑树的概念定义，以及它们在实际问题中的应用。 5．阐明Dijkstra算法的基本思想和基本步骤，为什么用这种算法能在图中找出从一点至任一点的最短路。

6．最大流问题是一个特殊的线性规划问题，试具体说明这个问题中的变量、目标函数和约

束条件各是什么?

7．什么是增广链，为什么只有不存在增广链时，网络中的流即为最大流。 8．简述最小费用最大流的概念以及求取最小费用最大流的基本思想和方法。 9．试用图的语言来表达中国邮递员问题，并说明该问题同一笔画之间的联系和区别。

二、判断下列说法是否正确：

图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意；

三、计算题

1、 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图所示，图中的v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7表示7个学院办公室，图中的边为可能联通的途径，边上的数字表示这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学复习题(2)在线全文阅读。