《运筹学》第八章图与网络分析习题
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的一个子图。
运筹学中网络分析名词解释
运筹学：缩写OR，是利用计划方法和有关多学科的要求。把复杂功能关系。表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据。
定性决策：基本上根据决策人员的主观经验或感受到的感觉或只是而制定的决策。
定量决策：借助于某些正规的计量方法而作出的决策。
混合性决策：必须运用定性和定量两种方法才能制定的决策。
预测：是对未来的不确定的事物进行估计或判断。
专家小组法：是在介绍咨询的专家之间组成一个小组，面对面的进行讨论与磋商，最后对需要预测的课题得出比较一致的意见
指数平滑预测法：是定量与定性方法相结合的一种预测方法。
决策：从狭义方面来说，决策可以解释为对一些可供选择的方案作出抉择。广义的决策过程包括4个程序：明确决策项目的目的，寻求可行的方案，在诸可行方案中进行抉择，对选定的决策方案经过实施后的结果进行总结评价。
常规性决策：它是例行的，重复性的决策。做这类决策的个人或组织。又要需要他们决策的问题不是新问题，一般来说已经有管理和经验作参考。因而进行决策是就比较容易。
特殊性决策：是对特殊的，先例可循的新问题的决策。做这类决策的个人或组织只有认真履行决策过程的四个阶段，才能作出满意的决策。
总之网络就是赋权的图。权是程度的度量。运筹学是现代管理学的一门重要专业基础课，是应用数学和形式科学的跨领域研究，利用统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。它是20世纪30年代初发展起来的一门新兴学科，其主要目的是在决策时为管理人员提供科学依据。
运筹学知识点
运筹学是一门应用广泛的学科，旨在通过科学的方法和技术来解决各种决策和优化问题。它综合运用数学、统计学、计算机科学等多学科知识，为管理和决策提供有力的支持。下面让我们来了解一些运筹学的重要知识点。
一、线性规划
线性规划是运筹学中最基本也是最重要的内容之一。它研究的是在一组线性约束条件下，如何找到目标函数的最优解。
例如，一家工厂生产两种产品 A 和 B，生产单位 A 产品需要消耗 2
单位的原材料和 1 单位的劳动力，生产单位 B 产品需要消耗 3 单位的原材料和 2 单位的劳动力。工厂现有 100 单位的原材料和 80 单位的劳动力，A 产品的单位利润是 5 元，B 产品的单位利润是 8 元。那么，如何安排生产才能使工厂的利润最大化？
解决这个问题，首先要建立线性规划模型。设生产 A 产品 x 件，生产 B 产品 y 件，目标函数就是利润最大化：Z ＝ 5x ＋ 8y。约束条件包括原材料限制：2x ＋ 3y ≤ 100；劳动力限制：x ＋ 2y ≤ 80；以及非负限制：x ≥ 0，y ≥ 0。
通过求解这个线性规划模型，可以得到最优的生产方案，即生产多少 A 产品和多少 B 产品能够使利润达到最大值。 二、整数规划
整数规划是在线性规划的基础上，要求决策变量必须取整数的规划问题。
比如，一个项目需要选择一些地点建设仓库，每个地点的建设成本和运营效益不同。由于仓库的数量必须是整数，这就构成了一个整数规划问题。
整数规划的求解比线性规划更加复杂，常用的方法有分支定界法、割平面法等。
三、动态规划
动态规划是解决多阶段决策过程最优化的一种方法。
以资源分配问题为例，假设一家公司有一定数量的资金要在多个项目中进行分配，每个项目在不同的投资水平下有不同的收益。要在有限的资金条件下，使总收益最大。这个问题就可以用动态规划来解决。
动态规划的核心思想是将一个复杂的多阶段决策问题分解为一系列相互关联的子问题，通过求解子问题的最优解来逐步得到原问题的最优解。
项目四 图与网络分析
任务八 图与网络的应用练习
1、求下图的最小支撑树。
V135461038V2V3V5V6V454
用破圈法求该图的最小支撑树：
V13541038V2V3V5V6V454
（1）
V135438V2V3V5V6V454
（2）
V135438V2V3V5V6V44 （3）
V13543V2V3V5V6V44
（4）
2、分别用破圈法和避圈法求下列各个图的最小支撑树。
a-1：用破圈法求图a的最小支撑树：
V143638V2V3V5V6V744V4123 V14638V2V3V5V6V744V4123
V1463V2V3V5V6V744V4123 V143V2V3V5V6V744V4123
V143V2V3V5V6V74V4123
a-2：用避圈法求图a的最小支撑树： V2V31 V13V2V3V6V712
V13V2V3V6V7V4123 V143V2V3V5V6V7V4123
V143V2V3V5V6V74V4123
b-1：用破圈法求图b的最小支撑树：
ASBDTCE37214353745 ASBDTCE3721435374
ASBDTCE372135374 ASBDTCE32135374 V1V2V312ASBDTCE3213537 ASBDTCE321353
b-2：用避圈法求图b的最小支撑树：
ASBDC3213 ASBDCE32133
ASBDTCE321353
3、用标号法求下图中1v至7v的最短路。
1）标号过程
（1）初始化；令起点v1的标号为P，记做P(1) =0；令其余各点的标号为T，记做T(i)=∞； BD1ABD21ASBD321 （2）计算T标号：刚得到P标号的点为v1，考虑所有与v1相邻的T标号点v2、v3、v5，修改v2、v3、v5的T标号为：
