求图的最小生成树
权为 26
8 6
4
9
9 7 8 4 3 3 5 权为 30
5 7
6
求图的最小生成树
3
3
5
3
9 4
3
4
3
10
3
8 8
3 3
7
3
6
3
6
3
2
3
求图的最小生成树
权为 20
10 8 4 7 5 求图的最小生成树 3 4 权为 23 6 7 2
8 1
4
2
353 6Fra bibliotek3 4 2 4
1 6
6
第 1 页 共 10 页
V2 3 V1 2 V3 3 5
1 8 7
V4 6 2 V6 3 V5
在该网络图中：
此为网络分析之“最短路问题” ，可用顺向追踪“TP 标号法”解决如下：
8 7 2 3 1 4 3 1 2 2
v1
v4
4 7
v7
7
4
9 8 2 5 3 1 2 4
v2
v5
2
v3
求 v1 到 v7 的最短路径和最短距离。
最优票价表：
有三个电站 T 1 ,T 2 ,T 3 ，每月每个电站各需 60kt 煤，有两个煤矿 s 1 ,s 2 ，每月每个煤矿可提 供 100kt 煤，煤矿向电站每月的最大运输量能力为(以 kt 为单位)： 运输量 t1 40 40 t2 40 20 t3 30 50
供应量
t1 4 2
t2 4 2
v6 v1
0
v4
3
v7
7
7
1
4
v3
1
v6
4
v1 到 v7 的最短路径是：v1→v3→v4→v7，最短距离为 1+4+2=7。
第 3 页 共 10 页
西安邮电学院试题库管理系统——试题表
求图中从 v 1 到顶点的距离，并给出从 v 1 到 v p 的最短路。 v 1 到各点的距离依次是 2、6、4 v 1 到 v p 的最短路 (v 1 、v 3 、v 2 、v p ) v1
总费用最小的设备更新方案为：第一种方案，第 1 年购置一台设备使用到第 5 年年末； 第二种方案，第 1 年购置一台设备使用到第 2 年年末，第 3 年年初更新后使用到第 5 年年 末。总费用为 11.5 万元。
第 4 页 共 10 页
西安邮电学院试题库管理系统——试题表
图是世界某 6 大城市之间的航线，边上的数字为票价（百美元） ，用 Floyd 算法设计任意两 城市之间票价最便宜的路线表。 【解】 L1 v1 v1 v2 v3 v4 v5 v6 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v1 v1 v2 v3 v4 v5 v6 v1 v1 v2 v3 v4 v5 v6 v1 v1 v2 v3 v4 v5 v6 v1、v2、„、v6 到各点的最优路线图分别为： 0 0 8.8 8.6 5.6 8 6 v2 8.8 0 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v6 6 4 14 100 9 0 L2 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 L3 v3 8.6 8 0 3 4.8 12 v3 8.6 8 0 v4 5.6 5 3 0 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 v6 6 4 12 9 9 0 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0
t3 1 5
s1 s2
s1 s2
各线路的千吨运费为 运价 t1 4 5 t2 5 5 t3 8 8
s1 s2
试给出供煤方案，使总运费最小。 今有一只 10kg 装的瓶内装满了油，还有两只空瓶，可分装 7kg 和 3kg，问能不能把油分 9 次 成两份，每份 5kg？如果可以的话，至少要倒几次？
今有一只 10kg 装的瓶内装满了油，还有两只空瓶，可分装 6kg 和 4kg，问能不能把油分成 不可能分成两个 2.5kg 两份，每份 5kg？如果可以的话，至少要倒几次？
西安邮电学院试题库管理系统——试题表
专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型 代码 08 试题类 型名称 计算题 出题人 管理员 出题 日期 难 度 系 数 中 2005-11-4 认 知 分 类 运 用 建 议 分 数 10 建 议 时 间 10
知识点 代码 11180601
最低总成本 74.3 万元。
在图中，求 A 到 H、I 的最短路及最短路长。
【解】
较 难
运 用
12
14
A 到 H 的 最 短 路 PAH={A,B,F,H},{A,C,F,H} 最 短 路 长 22 ； A 到 I 的 最 短 路 PAI={A,B,F,I},{A,C,F,I}最短路长 21。 在图中，求 A 到 H、I 的最短路及最短路长。
设图是某汽车公司的 6 个零配件加工厂， 边上的数字为两点间的距离(km)。 现要在 6 个工厂 计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。 中选一个建装配车间。 装配一辆汽车 6 个零配件加工厂所提供零件重量分别是 0.5、 0.6、 0.8、 v1 v2 v3 v4 v5 v6 单件产品运费 1.3、1.6 和 1.7 吨，运价为 2 元/吨公里。应选那个工厂使总运费最小。 v1 0 8.8 8.6 5.6 8 6 84.88 v2 v3 v4 v5 v6 运价 如图所示，求解中国邮路问题。即一个邮递员从邮局出发，将邮件投递到他管辖的所有街 道最后回到邮局，如何安排他的行驶路线是总路长最短。 8.8 8.6 5.6 8 6 1 0 8 5 13 4 1.2 8 0 3 4.8 12 1.6 5 3 0 7.8 9 2.6 13 4.8 7.8 0 9 3.2 4 12 9 9 0 3.4 89.16 82.16 71.96 81.92 82.2
从 v 1 到 v 2 、 v 3 、v 4 的距离为 7、4、6，不能到达 v 5 、v 6
1 V2 8 3 4 2 1 V6 2 2 V3 V5 1 V4 4
V1 4
2
已知某设备可继续使用 5 年，也可以在每年年末卖掉重新购置新设备。已知 5 年年初购置 【解】设点 vj 为第 j 年年初购置新设备的状态， （i，j）为第 i 年年初购置新设备使用到第 j 新设备的价格分别为 3.5、3.8、4.0、4.2 和 4.5 万元。使用时间在 1～5 年内的维护费用分别 年年初，弧的权为对应的费用（购置费＋维护费） ，绘制网络图并计算，结果见下图所示。 为 0.4、0.9、1.4、2.3 和 3 万元。试确定一个设备更新策略，使 5 年的设备购置和维护总费 用最小。
3
求图 2 中从 v 1 到顶点的距离，并给出从 v 1 到 v p 的最短路。
-2 v1 v3
v 1 到各点的距离依次是 4、-2、6 v 1 到 v p 的最短路 (v 1 、v 3 、v p )
-4 8 -3 6 -4 8
v2
3
vp
求图从 v 1 到 v 6 的最短路和最长路
答案：最短路（v 1 、 v 3 、v 5 、v 6 ） ，最长路（v 1 、 v 3 、v 2 、v 5 、v 6 ）
西安邮电学院试题库管理系统——试题表
图表示一片水稻田，用堤埂分成若干小块，为了用水灌溉需要挖开一些堤埂。问最少挖多 少堤埂，才能是水浇灌到每小块稻田。 10 条
用破圈法求图的最小部分树。
【解】该题有 4 个解，最小树长为 21，其中一个解如下图所示。
用加边法求图的最小部分树。
最小树长为 20。最小树如下图所示。
一公司拨出一千万元专款用来研制一种新产品。研制工作可以分为 4 个阶段，在每一阶段 C、A、A、B 有 2 和 3 个方案。他们所需的时间和经费如下： 阶段 方案 A B C 时间 5 4 2 一 费用 1 2 3 时间 3 2 二 费用 2 3 时间 2 1 三 费用 1 2 时间 5 3 四 费用 3 4
1
v 1 到各点的距离依次是 2、3、5、5、6、7、8、10 v 1 到 v p 的最短路有两条(v 1 、v 2 、v 3 、v 5 、v 6 、v 7 、v 8 、v p ) 3 3 1 v7 2 3 1
v4
（v 1 、v 2 、v 3 、v 5 、v 7 、v p ）
v 6 v5 1 1 1
6 3 -1
8 vp
-1
2
v3
-4
v2
6
在图中， （i）是否有权小于 0 的回路？若没有请给出从 v 1 到其他各顶点的距离， （ii）是否 有从 v 1 出发不能到达的顶点？若有请指出这样的顶点。
存在负回路，不能到达 v 3
V5 -2 -2
3
V4 V1 2 3 -5 6 V3 3 V2 -2
在图中， （i）是否有权小于 0 的回路？若没有请给出从 v 1 到其他各顶点的距离， （ii）是否 有从 v 1 出发不能到达的顶点？若有请指出这样的顶点。
题
干
答
案
评分标准
如图所示，建立求最小部分树的 0－1 整数规划数学模型。
【解】边[i，j]的长度记为 cij，设 1 边[i, j ]包含在最小部分树内 xij 0 否则 数学模型为：
min Z cij xij xij 5 i, j x x x 2, x x x 2 13 23 23 24 34 12 x34 x36 x 46 2, x35 x36 x56 2 x 23 x 26 x36 2, x12 x13 x 24 x34 3 x x x x 3, x x x x 3 35 46 56 12 13 26 36 34 x 23 x35 x 26 x56 3, x12 x15 x 26 x56 3 xij 1或0, 所有边[i, j ]