《运筹学》第八章图与网络分析习题
1.思考题
(１)解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边；
②环，多重边，简单图；③链，初等链；④圈，初等圈，简单拳；⑤ 回
路，初等路；⑥节点的次，悬挂点，孤立点；⑦）连通图，连同分图， 支
撑子图；⑧有向图，基础图，赋权图。⑨子图，部分图，真子图．
(２)通常用记号Ｇ＝（Ｖ，Ｅ）表示一个图，解释Ｖ及Ｅ的涵义及这个表达式
的涵义．
(３)通常用记号Ｄ＝（Ｖ，Ａ）表示一个有向图，解释Ｖ及Ａ的涵义及这个表
达式的涵义．
(４) 图论中的图与一般几何图形的主要区别是什么？
(５) 试述树与图的区别与联系．
(６) 试述 求最短路问题的Ｄijkstra算法的基本思想及其计算步骤．
(７) 试述寻求最大流的标号法的步骤与方法．
(８) 简述最小费用最大流的概念及其求解的基本思想和方法．
(９) 通常用记号Ｎ＝（Ｖ，Ａ，Ｃ）表示一个网络，试解释这个表达式的涵义．
(10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？
(11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。
2.判断下列说法是否正确
(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何
形状无关。
(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。
(3) 如果一个图G从V1到各点的最短路是唯一的，则连接V1到各点的最短路，再去掉重复边，得到的图即为最小支撑树。
(4 )图G的最小支撑树中从V1到Vn的通路一定是图G从V1到Vn的最短路。
(5) {fij=0}总是最大流问题的一个可行流。
(6 )无孤立点的图一定是连通图。
(7) 图中任意两点之间都有一条简单链，则该图是一棵树。
(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。
(9)在图中求一点Ｖ１到另一点Ｖn的最短路问题总可以归结为一个整数规划问题
(10) 图G中的一个点V1总可以看成是G的一个子图。
专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型代码 08 试题类型名称 ；
计算题 出题人 管理员 出题
日期 2005-11-4
知识点
代码 题 干 答 案 评分标准 …
难度系数 认知分类 建议分数 建议时间
10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表所示。应该如何装载货物使总价值最大。
货物编号 1 2 3
[
单位加工时间 2 3 4
单位价值 3 4 5 【解】设装载第I种货物的件数为xi（ i =1,2,3）则问题可表为：
123123123max3452349,,0zxxxxxxxxx且为整数
&
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，
121210/2()max(3)xsfsx。计算结果如下：
s2 0 1 2 3 4 5 6 7 8 |
9
f（s2） 0 0 3 3 6 6 9 9 12 】
12
x1* 0 0 1 1 2 2 3 3 4 ￥
4
当R=2时，f2（s3）=4/210maxsx[4x2+f1（s3-3x2）]
计算结果如下：
s3 0 1 2 3 4 5 6 ;
7 8 9
x2 0 0 0 0 1 0 1 。
0 1 0 1 2 0 1 2 0 1 2 "
0 1 2 3
C2+f2 0 0 3 3 4 6 "
4 6 7 9 7 8 9 10 8 12 10 $
11 12 13 11 12
f2（s3） 0 0 3 4 <
6 7 9 10 12 ~
13
x2* 0 0 0 …
1 0 1 0 1 ，
0 1
当R=3时，f3（9）=230maxx[5x3+f2（9-4x3）] （x3为整数）=220maxx[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=13 较难 分析 $
第八章 存储论
２０９ 8.1 请建立最简单的单阶段存贮模型，推导出经济批量公式，要求说明模型成立的假设条件，所用字母的经济意义，并要有一定的推理过程。
8.2 若某工厂每年对某种零件的需要量为10000件，订货的固定费用为2000元，采购一个零件的单价为100元，保管费为每年每个零件20元，求最优订购批量。8.3 某厂对某种材料的全年需要量为1040吨，其单价为1200元/吨。每次采购该种材料的订货费为2040元，每年保管费为170元/吨。试求工厂对该材料的最优订货批量、每年订货次数。8.4 某货物每周的需要量为2000件，每次订货的固定费用为15元，每件产品每周保管费为0.30元，求最优订货批量及订货时间。
8.5 加工制作羽绒服的某厂预测下年度的销售量为15000件，准备在全年的300个工作日内均衡组织生产。假如为加工制作一件羽绒服所需的各种原材料成本为48元，又制作一件羽绒服所需原料的年存贮费为其成本的22%，提出一次订货所需费用为250元，订货提前期为零，不允许缺货，试求经济订货批量。
8.6 一条生产线如果全部用于某种型号产品生产时，其年生产能力为600000台。据预测对该型号产品的年需求量为260000台，并在全年内需求基本保持平衡，因此该生产线将用于多品种的轮番生产。已知在生产线上更换一种产品时，需准备结束费1350元，该产品每台成本为45元，年存贮费用为产品成本的24%，不允许发生供应短缺，求使费用最小的该产品的生产批量。
8.7 某生产线单独生产一种产品时的能力为8000件／年，但对该产品的需求仅为2000件／年，故在生产线上组织多品种轮番生产。已知该产品的存贮费为60元／年·件，不允许缺货，更换生产品种时，需准备结束费300元。目前该生产线上每季度安排生产该产品500件，问这样安排是否经济合理。如不合理，提出你的建议，并计算你建议实施后可能带来的节约。
8.8 某电子设备厂对一种元件的需求为R＝2000件/年，订货提前期为零，每次订货费为25元。该元件每件成本为50元，年存储费为成本的20％。如发生缺货，可在下批货到达时补上，但缺货损失费为每件每年30元。求：
西安邮电学院试题库管理系统——试题表
第 1 页 共 17 页 专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型代码 08 试题类型名称 计算题 出题人 管理员 出题
日期 2005-11-4
知识点
代码 题 干 答 案 评分标准 难度系数 认知分类 建议分数 建议时间
11180801 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表所示。应该如何装载货物使总价值最大。
货物编号 1 2 3
单位加工时间 2 3 4
单位价值 3 4 5 【解】设装载第I种货物的件数为xi（ i =1,2,3）则问题可表为：
123123123max3452349,,0zxxxxxxxxx且为整数
利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，
121210/2()max(3)xsfsx。计算结果如下：
s2 0 1 2 3 4 5 6 7 8 9
f（s2） 0 0 3 3 6 6 9 9 12 12
x1* 0 0 1 1 2 2 3 3 4 4
当R=2时，f2（s3）=4/210maxsx[4x2+f1（s3-3x2）]
计算结果如下：
s3 0 1 2 3 4 5 6 7 8 9
x2 0 0 0 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3
C2+f2 0 0 3 3 4 6 4 6 7 9 7 8 9 10 8 12 10 11 12 13 11 12
f2（s3） 0 0 3 4 6 7 9 10 12 13
x2* 0 0 0 1 0 1 0 1 0 1
当R=3时，f3（9）=230maxx[5x3+f2（9-4x3）] （x3为整数）=220maxx[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=13 较难 分析 12 14
