数学建模图与网络模型及方法

数学建模图与网络模型

及方法

Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】

第五章 图与网络模型及方法

§1 概论

图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。

图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当

然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。

图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。

我们首先通过一些例子来了解网络优化问题。

例1 最短路问题（SPP －shortest path problem ）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

例2 公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任

意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小

例3 指派问题（assignment problem ）

一家公司经理准备安排N 名员工去完成N 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大

例4 中国邮递员问题（CPP －chinese postman problem ）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

例5 旅行商问题（TSP －traveling salesman problem ）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）这一问题的研究历史十分悠久，通常称之为旅行商问题。

例6 运输问题（transportation problem ）

某种原材料有M 个产地，现在需要将原材料从产地运往N 个使用这些原材料的工厂。假定M 个产地的产量和N 家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低

上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化

（optimization ）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network ）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization ）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow ）为研究的对象，因此网络优化又常常被称为网络流（network flows ）或网络流规划等。

下面首先简要介绍图与网络的一些基本概念。

§2 图与网络的基本概念

无向图

一个无向图(undirected graph)G 是由一个非空有限集合)(G V 和)(G V 中某些元素的无序对集合)(G E 构成的二元组，记为))(),((G E G V G =。其中

},,,{)(21n v v v G V =称为图G 的顶点集（vertex set ）或节点集（node set ）， )(G V 中的每一个元素),,2,1(n i v i =称为该图的一个顶点（vertex ）或节点

（node ）；},,,{)(21m e e e G E =称为图G 的边集（edge set ），)(G E 中的每一个元素k e (即)(G V 中某两个元素j i v v ,的无序对)记为),(j i k v v e =或i j j i k v v v v e ==

),,2,1(m k =，被称为该图的一条从i v 到j v 的边（edge ）。

当边j i k v v e =时，称j i v v ,为边k e 的端点，并称j v 与i v 相邻（adjacent ）；边k e 称为与顶点j i v v ,关联（incident ）。如果某两条边至少有一个公共端点，则称这两条边在图G 中相邻。

边上赋权的无向图称为赋权无向图或无向网络（undirected network ）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。

一个图称为有限图，如果它的顶点集和边集都有限。图G 的顶点数用符号||V 或)(G ν表示，边数用||E 或)(G ε表示。

当讨论的图只有一个时，总是用G 来表示这个图。从而在图论符号中我们常略去字母G ，例如，分别用ν,,E V 和ε代替)(),(),(G G E G V ν和)(G ε。

端点重合为一点的边称为环(loop)。

一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。

有向图

定义 一个有向图（directed graph 或 digraph ）G 是由一个非空有限集合V 和V 中某些元素的有序对集合A 构成的二元组，记为),(A V G =。其中

},,,{21n v v v V =称为图G 的顶点集或节点集， V 中的每一个元素),,2,1(n i v i =称为该图的一个顶点或节点；},,,{21m a a a A =称为图G 的弧集（arc set ），A 中的每一个元素k a (即V 中某两个元素j i v v ,的有序对)记为),(j i k v v a =或

),,2,1(n k v v a j i k ==，被称为该图的一条从i v 到j v 的弧（arc ）。

当弧j i k v v a =时，称i v 为k a 的尾（tail ），j v 为k a 的头（head ），并称弧k a 为i v 的出弧（outgoing arc ），为j v 的入弧（incoming arc ）。

对应于每个有向图D ，可以在相同顶点集上作一个图G ，使得对于D 的每条

弧，G 有一条有相同端点的边与之相对应。这个图称为D 的基础图。反之，给定任意图G ，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为G 的一个定向图。

以下若未指明“有向图”三字，“图”字皆指无向图。

完全图、二分图

每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点的完全图记为n K 。

若Y X G V =)(，Φ=Y X ，0||||≠Y X （这里||X 表示集合X 中的元素个

数），X 中无相邻顶点对，Y 中亦然，则称G 为二分图(bipartite graph)；特别地，若Y y X x ∈?∈?,，则)(G E xy ∈，则称G 为完全二分图，记成|||,|Y X K 。

子图

图H 叫做图G 的子图（subgraph ），记作G H ?，如果)()(G V H V ?，

)()(G E H E ?。若H 是G 的子图，则G 称为H 的母图。

G 的支撑子图（spanning subgraph ，又成生成子图）是指满足)()(G V H V =的子图H 。

顶点的度

设)(G V v ∈，G 中与v 关联的边数（每个环算作两条边）称为v 的度(degree)，记作)(v d 。若)(v d 是奇数，称v 是奇顶点(odd point)；)(v d 是偶数，称v 是偶顶点(even point)。关于顶点的度，我们有如下结果：

(i) ∑∈=V

v v d ε2)(

(ii) 任意一个图的奇顶点的个数是偶数。

图与网络的数据结构

网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联

矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设),(A V G =是一个简单有向图，m A n V ==||,||，并假设V 中的顶点用自然数n ,,2,1 表示或编号，A 中的弧用自然数m ,,2,1 表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。

（i ）邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵（adjacency matrix ）的形式存储在计算机中。图),(A V G =的邻接矩阵是如下定义的：C 是一个n n ?的10-矩阵，即

n n n n ij c C ??∈=}1,0{)(，

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有2n 个元素中，只有m 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

例7 对于右图所示的图，可以用邻接矩阵表示为

同样，对于网络中的权，也可以用类似邻接矩阵的n n ?矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。

（ii ）关联矩阵表示法

关联矩阵表示法是将图以关联矩阵（incidence matrix ）的形式存储在计算机中．图),(A V G =的关联矩阵B 是如下定义的：B 是一个m n ?的矩阵，即

m n m n ik b B ??-∈=}1,0,1{)(，

也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为1-；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个1+，一个1-）。可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有nm 个元素中，只有m 2个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。

例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为

同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。

（iii ）弧表示法

弧表表示法将图以弧表（arc list ）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需m 2个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如下：

按照这样的顺序存储的。

（iv）邻接表表示法

邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为

这是一个5维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接表，如第1行对应于第1个节点的邻接表（即第1个节点的所有出弧）。每个指针单元的第1个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如第1行中的“2”表示弧的另一个端点为2（即弧为（1,2）），“8”表示对应弧(1,2)上的权为8；“3”表示弧的另一个端点为3（即弧为(1,3)），“9”表示对应弧（1，3）上的权为9。又如，第5行说明节点5出发的弧有(5,3)、(5,4)，他们对应的权分别为6和7。

对于有向图)

(i

G=，一般用)

A表示节点i的邻接表，即节点i的所有出弧构

V

,

(A

成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，)5(=

A等。这种记法我们在本书后面将会经常用到。

)1(=

}3,2{

A，}4,3{

（v）星形表示法

星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。

例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下：

节点对应的出弧的起始地址编号数组（记为point）

在数组point中，其元素个数比图的节点数多1（即1

+

n），且一定有

+m

n

(+

point。对于节点i，其对应的出弧存放在弧信息数组的位

=

)1(=

point，1

)1

1

置区间为

i

point

i

point，

+

]1

[-

(

)1

(

),

如果)1

point

i

=i

point，则节点i没有出弧。这种表示法与弧表表示法也非常相

(

)

(+

似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（point）记录每个节点出发的弧的起始编号。

前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点n的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式：

节点对应的入弧的起始地址编号数组（记为rpoint）

弧，则可以综合采用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的rpoint数组和如下的trace数组即可。这相当于一种紧凑的双向星形表示法如下所示：

①星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费)

(m

O的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。

②当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。

③上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含

有元素0和1+，而不含有1-，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。

轨与连通

k k v e e v e v W 2110=，其中)(G E e i ∈，k i ≤≤1，)(G V v j ∈，k j ≤≤0，i e 与

i i v v ,1-关联，称W 是图G 的一条道路(walk)，k 为路长，顶点0v 和k v 分别称为W 的起点和终点，而121,,,-k v v v 称为它的内部顶点。

若道路W 的边互不相同，则W 称为迹(trail)。若道路W 的顶点互不相同，则W 称为轨(path)。

称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。

若图G 的两个顶点v u ,间存在道路，则称u 和v 连通(connected)。v u ,间的最短轨的长叫做v u ,间的距离。记作),(v u d 。若图G 的任二顶点均连通，则称G 是连通图。

显然有：

(i) 图P 是一条轨的充要条件是P 是连通的，且有两个一度的顶点，其余顶点的度为2；

(ii) 图C 是一个圈的充要条件是C 是各顶点的度均为2的连通图。

§3 应用—最短路问题

两个指定顶点之间的最短路径

问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。

以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。

求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。

(i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。

(ii) 对每个i S v ∈（i i S V S \=），用

代替)(v l 。计算)}({min v l i

S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。

(iii). 若1||-=V i ，停止；若1||-

算法结束时，从0u 到各顶点v 的距离由v 的最后一次的标号)(v l 给出。在v 进入i S 之前的标号)(v l 叫T 标号，v 进入i S 时的标号)(v l 叫P 标号。算法就是不断修改各项点的T 标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各项点的最短路也在图上标示出来了。

例9 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。

用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、

2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量

?

??=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号；

)(i d 存放由始点到第i 点最短通路的值。

求第一个城市到其它城市的最短路径的Matlab 程序如下：

clear;

clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25];

a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55];

a(6,:)=zeros(1,6);

a=a+a';

pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));

d(1:length(a))=M;d(1)=0;temp=1;

while sum(pb)

tb=find(pb==0);

d(tb)=min(d(tb),d(temp)+a(temp,tb));

tmpb=find(d(tb)==min(d(tb)));

temp=tb(tmpb(1));

pb(temp)=1;

index1=[index1,temp];

index=index1(find(d(index1)==d(temp)-a(temp,index1)));

if length(index)>=2

index=index(1);

end

index2(temp)=index;

end

d, index1, index2

每对顶点之间的最短路径

计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra 算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行n 次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为)(3n O 。第二种解决这一问题的方法是由Floyd R W 提出的算法，称之为Floyd 算法。

假设图G 权的邻接矩阵为0A ，

来存放各边长度，其中：

0=ii a n i ,,2,1 =；

∞=ij a j i ,之间没有边，在程序中以各边都不可能达到的充分大的数代替； ij ij w a = ij w 是j i ,之间边的长度，n j i ,,2,1, =。

对于无向图，0A 是对称矩阵，ji ij a a =。

Floyd 算法的基本思想是：递推产生一个矩阵序列n k A A A A ,,,,,10 ，其中

),(j i A k 表示从顶点i v 到顶点j v 的路径上所经过的顶点序号不大于k 的最短路径长度。

计算时用迭代公式：

k 是迭代次数，n k j i ,,2,1,, =。

最后，当n k =时，n A 即是各顶点之间的最短通路值。

例10 用Floyd 算法求解例1。

矩阵path 用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd 算法的Matlab 程序如下：

clear;

clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25];

a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55];

a(6,:)=zeros(1,6);

b=a+a';path=zeros(length(b));

for k=1:6

for i=1:6

for j=1:6

if b(i,j)>b(i,k)+b(k,j)

b(i,j)=b(i,k)+b(k,j);

path(i,j)=k;

end

end

end

end

b, path

§4 树

基本概念

连通的无圈图叫做树，记之为T 。若图G 满足)()(T V G V =，)()(G E T E ?，则称T 是G 的生成树。图G 连通的充分必要条件为G 有生成树。一个连通图的生成树的个数很多，用)(G τ表示G 的生成树的个数，则有公式

公式 (Caylay)2)(-=n n n K τ。

公式 )()()(e G e G G ?+-=τττ。

其中e G -表示从G 上删除边e ，e G ?表示把e 的长度收缩为零得到的图。

树有下面常用的五个充要条件。

定理1 （i ）G 是树当且仅当G 中任二顶点之间有且仅有一条轨道。

（ii ）G 是树当且仅当G 无圈，且1-=νε。

（iii ）G 是树当且仅当G 连通，且1-=νε。

（iv ）G 是树当且仅当G 连通，且)(G E e ∈?，e G -不连通。

（v ）G 是树当且仅当G 无圈，)(G E e ??，e G +恰有一个圈。

应用—连线问题

欲修筑连接n 个城市的铁路，已知i 城与j 城之间的铁路造价为ij C ，设计一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。

下面介绍构造最小生成树的两种常用算法。

4.2.1 prim 算法构造最小生成树

设置两个集合P 和Q ,其中P 用于存放G 的最小生成树中的顶点，集合Q 存放G 的最小生成树中的边。令集合P 的初值为}{1v P =（假设构造最小生成树时，从顶点1v 出发），集合Q 的初值为Φ=Q 。prim 算法的思想是，从所有P p ∈，P V v -∈的边中，选取具有最小权值的边pv ，将顶点v 加入集合P 中，将边pv 加入集合Q 中，如此不断重复，直到V P =时，最小生成树构造完毕，这时集合Q 中包含了最小生成树的所有边。

prim 算法如下：

（i ）}{1v P =，Φ=Q ；

（ii ）while V P =~

end

例11 用prim 算法求右图的最小生成树。

我们用n result ?3的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如

下：

clc;clear;

M=1000;

a(1,2)=50; a(1,3)=60;

a(2,4)=65; a(2,5)=40;

a(3,4)=52;a(3,7)=45;

a(4,5)=50; a(4,6)=30;a(4,7)=42;

a(5,6)=70;

a=[a;zeros(2,7)];

a=a+a';a(find(a==0))=M;

result=[];p=1;tb=2:length(a);

while length(result)~=length(a)-1

temp=a(p,tb);temp=temp(:);

d=min(temp);

[jb,kb]=find(a(p,tb)==d);

j=p(jb(1));k=tb(kb(1));

result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];

end

result

4.2.1 Kruskal 算法构造最小生成树

科茹斯克尔（Kruskal ）算法是一个好算法。Kruskal 算法如下:

(i)选)(1G E e ∈，使得m in )(1=e w 。

(ii)若i e e e ,,,21 已选好，则从},,,{)(21i e e e G E -中选取1+i e ，使得

① }],,,,[{121+i i e e e e G 中无圈，且

② min )(1=+i e w 。

(iii)直到选得1-νe 为止。

例12 用Kruskal 算法构造例3的最小生成树。

我们用n index ?2存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。

Matlab 程序如下：

clc;clear;

M=1000;

a(1,2)=50; a(1,3)=60;

a(2,4)=65; a(2,5)=40;

a(3,4)=52;a(3,7)=45;

a(4,5)=50; a(4,6)=30;a(4,7)=42;

a(5,6)=70;

[i,j]=find((a~=0)&(a~=M));

b=a(find((a~=0)&(a~=M)));

data=[i';j';b'];index=data(1:2,:);

loop=max(size(a))-1;

result=[];

while length(result)

temp=min(data(3,:));

flag=find(data(3,:)==temp);

flag=flag(1);

v1=data(1,flag);v2=data(2,flag);

if index(1,flag)~=index(2,flag)

result=[result,data(:,flag)];

end

if v1>v2

index(find(index==v1))=v2;

else

index(find(index==v2))=v1;

end

data(:,flag)=[];

index(:,flag)=[];

end

result

§5 匹配问题

定义 若)(G E M ?，M e e j i ∈?,，i e 与j e 无公共端点（j i ≠），则称M 为图G 的一个对集；M 中的一条边的两个端点叫做在对集M 中相配；M 中的端点称为被M 许配；G 中每个顶点皆被M 许配时，M 称为完美对集；G 中已无使|||'|M M >的对集'M ，则M 称为最大对集；若G 中有一轨，其边交替地在对集M 内外出现，则称此轨为M 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。

若把可增广轨上在M 外的边纳入对集，把M 内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个。

1957年，贝尔热(Berge)得到最大对集的充要条件：

定理2 M 是图G 中的最大对集当且仅当G 中无M 可增广轨。

1935年，霍尔(Hall)得到下面的许配定理：

定理3 G 为二分图，X 与Y 是顶点集的划分，G 中存在把X 中顶点皆许配的对集的充要条件是，X S ??，则|||)(|S S N ≥，其中)(S N 是S 中顶点的邻集。

由上述定理可以得出：

推论1：若G 是k （)0>k 正则2分图，则G 有完美对集。

所谓k 正则图，即每顶点皆k 度的图。

由此推论得出下面的婚配定理：

定理4 每个姑娘都结识)1(≥k k 位小伙子，每个小伙子都结识k 位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。

人员分派问题等实际问题可以化成对集来解决。

人员分派问题：工作人员n x x x ,,,21 去做n 件工作n y y y ,,,21 ，每人适合做其中

一件或几件，问能否每人都有一份适合的工作如果不能，最多几人可以有适合的工作

这个问题的数学模型是：G 是二分图，顶点集划分为Y X G V =)(，

},,{11n x x X =，},,{11n y y Y =，当且仅当i x 适合做工作i y 时，)(G E y x i i ∈，求G 中的最大对集。

解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。

匈牙利算法：

（i ）从G 中任意取定一个初始对集M 。

（ii ）若M 把X 中的顶点皆许配，停止，M 即完美对集；否则取X 中未被M 许配的一顶点u ，记}{u S =，Φ=T 。

（iii ）若T S N =)(，停止，无完美对集；否则取T S N y -∈)(。

（iv ）若y 是被M 许配的，设M yz ∈，}{z S S =，}{y T T =，转（iii ）；否则，取可增广轨),(y u P ，令))(())((M P E P E M M --= ，转（ii ）。

把以上算法稍加修改就能够用来求二分图的最大对集。

最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。

这个问题的数学模型是：在人员分派问题的模型中，图G 的每边加了权

0)(≥j i y x w ，表示i x 干j y 工作的效益，求加权图G 上的权最大的完美对集。

解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres ）算法。为此，我们要引入可行顶点标号与相等子图的概念。

定义 若映射R G V l →)(:，满足Y y X x ∈∈?,，

),()()(y x w y l x l ≥+，

则称l 是二分图G 的可行顶点标号。令

)}()()(),(|{xy w y l x l G E xy xy E l =+∈=，

称以l E 为边集的G 的生成子图为相等子图，记作l G 。

可行顶点标号是存在的。例如

Y y y l ∈= ,0)(。

定理5 l G 的完美对集即为G 的权最大的完美对集。

Kuhn-Munkres 算法

（i ）选定初始可行顶点标号l ，确定l G ，在l G 中选取一个对集M 。

（ii ）若X 中顶点皆被M 许配，停止，M 即G 的权最大的完美对集；否则，取l G 中未被M 许配的顶点u ，令}{u S =， Φ=T 。

(iii)若T S N l G ?)(，转（iv ）；若T S N l G =)(，取

)}()()({min ,xy w y l x l T

y S x l -+=?∈α， ??

???∈+∈-=其它),(,)(,)()(v l T v v l S v v l v l l l αα， l l = ，l l G G =。

（iv ）选T S N l G -)(中一顶点y ，若y 已被M 许配，且M yx ∈，则}{z S S =，

}{y T T =，转（iii ）；否则，取l G 中一个M 可增广轨),(y u P ，令

))(())((M P E P E M M --= ，

转（ii ）。

其中)(S N l G 是l G 中S 的相邻顶点集。

§6 Euler 图和Hamilton 图

基本概念

定义 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E 回路；含Euler 回路的图叫做Euler 图。

直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。

定理7 （i ）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次。

（ii ）G 是Euler 图的充分必要条件是G 连通且 d

i i C G 1==，i C 是圈，

)()()(j i C E C E j i ≠Φ= 。

（iii ）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点。

定义 包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton 轨叫做Hamilton 圈或H 圈；含Hamilton 圈的图叫做Hamilton 图。

直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。

Euler 回路的Fleury 算法

1921年，Fleury 给出下面的求Euler 回路的算法。

Fleury 算法：

1o . )(0G V v ∈?，令00v W =。

2o . 假设迹i i i v e v e v W 110=已经选定，那么按下述方法从},,{1i e e E -中选取边1+i e ：

（i ）1+i e 和i v 相关联；

（ii ）除非没有别的边可选择，否则1+i e 不是},,{1i i e e G G -=的割边(cut

edge)。(所谓割边是一条删除后使连通图不再连通的边)。

3o . 当第2步不能再执行时，算法停止。

应用

邮递员问题

中国邮递员问题

一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。

上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。

显然，若此连通赋权图是Euler 图，则可用Fleury 算法求Euler 回路，此回路即为所求。

对于非Euler 图，1973年，Edmonds 和Johnson 给出下面的解法：

设G 是连通赋权图。

（i ）求)}2(m od 1)(),(|{0=∈=v d G V v v V 。

（ii ）对每对顶点0,V v u ∈，求),(v u d （),(v u d 是u 与v 的距离，可用Floyd 算法求得）。

（iii ）构造完全赋权图||0V K ，以0V 为顶点集，以),(v u d 为边uv 的权。

（iv ）求||0V K 中权之和最小的完美对集M 。

（v ）求M 中边的端点之间的在G 中的最短轨。

（vi ）在（v ）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。

（vii ）在（vi ）中得的图'G 上求Euler 回路即为中国邮递员问题的解。

多邮递员问题：

邮局有)2(≥k k 位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早我们把这一问题记成kPP 。

kPP 的数学模型如下：

),(E V G 是连通图，)(0G V v ∈，求G 的回路k C C ,,1 ，使得

（i ）)(0i C V v ∈，k i ,,2,1 =，

（ii ）min )(max )(1=∑∈≤≤i C E e k

i e w ，

（iii ） k i i G E C E 1

)()(==

旅行商（TSP ）问题

一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

一个可行的办法是首先求一个Hamilton 圈C ，然后适当修改C 以得到具有较小权的另一个Hamilton 圈。修改的方法叫做改良圈算法。设初始圈121v v v v C n =。

（i ）对于n j i <<+<11，构造新的Hamilton 圈:

12112121v v v v v v v v v v v C n j j i j j j i ij +++--=,

它是由C 中删去边1+i i v v 和1+j j v v ，添加边j i v v 和11++j i v v 而得到的。若

)()()()(1111+++++<+j j i i j i j i v v w v v w v v w v v w ，则以ij C 代替C ，ij C 叫做C 的改良圈。

（ii ）转（i ），直至无法改进，停止。

用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。

这个算法的优劣程度有时能用Kruskal 算法加以说明。假设C 是G 中的最优圈。则对于任何顶点v ，v C -是在v G -中的Hamilton 轨，因而也是v G -的生成树。由此推知：若T 是v G -中的最优树，同时e 和f 是和v 关联的两条边，并使得

)()(f w e w +尽可能小，则)()()(f w e w T w ++将是)(C w 的一个下界。

这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。

例13 从北京（Pe ）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短各城

clc,clear

a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;

a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;

a(3,4)=36;a(3,5)=68;a(3,6)=68;

a(4,5)=51;a(4,6)=61;

a(5,6)=13;

a(6,:)=0;

a=a+a';

c1=[5 1:4 6];

L=length(c1);

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if

a(c1(m),c1(n))+a(c1(m+1),c1(n+1))

flag=1;

c1(m+1:n)=c1(n:-1:m+1);

end

end

end

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

circle=c1;

sum=sum1;

c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...

a(c1(m),c1(m+1))+a(c1(n),c1(n+1))

flag=1;

c1(m+1:n)=c1(n:-1:m+1);

end

end

end

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

if sum1

sum=sum1;

circle=c1;

end

circle,sum

§7 最大流问题

最大流问题的数学描述

网络中的流

定义 在以V 为节点集，A 为弧集的有向图),(A V G =上定义如下的权函数：

（i ）R A L →:为孤上的权函数，弧A j i ∈),(对应的权),(j i L 记为ij l ，称为孤

),(j i 的容量下界（lower bound ）；

（ii ）R A U →:为弧上的权函数，弧A j i ∈),(对应的权),(j i U 记为ij u ，称为孤),(j i 的容量上界，或直接称为容量（capacity ）；

（iii ）R V D →:为顶点上的权函数，节点V i ∈对应的权)(i D 记为i d ，称为顶点i 的供需量（supply ／demand ）；

此时所构成的网络称为流网络，可以记为

),,,,(D U L A V N =。

由于我们只讨论A V ,为有限集合的情况，所以对于弧上的权函数U L ,和顶点上的权函数D ，可以直接用所有孤上对应的权组成的有限维向量表示，因此D U L ,,有时直接称为权向量，或简称权。由于给定有向图),(A V G =后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。

在流网络中，弧),(j i 的容量下界ij l 和容量上界ij u 表示的物理意义分别是：通过该弧发送某种“物质”时，必须发送的最小数量为ij l ，而发送的最大数量为ij u 。顶点V i ∈对应的供需量i d 则表示该顶点从网络外部获得的“物质”数量（0i d 时）。下面我们给出严格定义。 定义 对于流网络),,,,(D U L A V N =，其上的一个流（flow ）f 是指从N 的弧集A 到R 的一个函数，即对每条弧),(j i 赋予一个实数ij f （称为弧),(j i 的流量）。如果流f 满足

∑∑∈∈∈?=-A i j j i ji A j i j ij

V i d f f ),(:),(:,, （1）

A j i u f l ij ij ij ∈?≤≤),(,， （2）

则称f 为可行流（feasible flow ）。至少存在一个可行流的流网络称为可行网络（feasible network ）．约束（1）称为流量守恒条件（也称流量平衡条件），约束

（2）称为容量约束。

可见，当0>i d 时，表示有i d 个单位的流量从该项点流出，因此顶点i 称为供应点（supply node ）或源（source ），有时也形象地称为起始点或发点等；当0

（1）可知，对于可行网络，必有

0=∑∈V

i i d

（3）

也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。

一般来说，我们总是可以把0≠L 的流网络转化为0=L 的流网络进行研究。所以，除非特别说明，以后我们总是假设0=L （即所有孤),(j i 的容量下界0=ij l ），并将0=L 时的流网络简记为),,,(D U A V N =。此时，相应的容量约束（2）为

A j i u x ij ij ∈?≤≤),(,0。

定义 在流网络),,,(D U A V N =中，对于流f ，如果

A j i f ij ∈?=),(,0，

则称f 为零流，否则为非零流。如果某条弧),(j i 上的流量等于其容量（ij ij u f =），则称该弧为饱和弧（saturated arc ）；如果某条弧),(j i 上的流量小于其容量（ij ij u f <），则称该弧为非饱和弧；如果某条弧),(j i 上的流量为 0（0=ij f ），则称该弧为空弧（void arc ）。

最大流问题

考虑如下流网络),,,(D U A V N =：节点s 为网络中唯一的源点，t 为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f ，此时称流f 的流量（或流值，flow value ）为s d （根据（3），它自然也等于t d -），通常记为v 或)(f v ，即

t s d d f v v -===)(。

对这种单源单汇的网络，如果我们并不给定s d 和t d （即流量不给定），则网络一般记为),,,,(U A V t s N =。最大流问题（maximum flow problem ）就是在

),,,,(U A V t s N =中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。

因此，用线性规划的方法，最大流问题可以形式地描述如下：

. ∑∑∈∈??

???≠=-==-A i j j ji A j i j ij t s i t i v s i v x x ),(:),(:,,0,, ， （4）

A j i u x ij ij ∈?≤≤),(,0. （5） 定义 如果一个矩阵A 的任何子方阵的行列式的值都等于0，1或1-，则称A 是全幺模的(totally unimodular TU ，又译为全单位模的)，或称A 是全幺模矩阵。

定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。

最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。

单源和单汇运输网络

实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络G 化成单源单汇网络'G 。设X 是G 的源，Y 是G 的汇，具体转化方法如下：

（i ）在原图G 中增加两个新的顶点x 和y ，令其分别为新图'G 中之单源和单汇，则G 中所有顶点V 成为'G 之中间顶点集。

（ii ）用一条容量为∞的弧把x 连接到X 中的每个顶点。

（iii ）用一条容量为∞的弧把Y 中的每个顶点连接到y 。

G 和'G 中的流以一个简单的方式相互对应。若f 是G 中的流，则由

所定义的函数'f 是'G 中使得)()'(f v f v =的流。反之，'G 中的流在G 的弧集上的限制就是G 中具有相同值的流。

最大流和最小割关系

设),,,,(U A V t s N =，V S ?，S s ∈，S V t -∈，则称),(S S 为网络的一个割，其中S V S -=，),(S S 为尾在S ，头在S 的弧集，称 为割),(S S 的容量。

定理9 f 是最大流，),(S S 是容量最小的割的充要条件是

),()(S S C f v =。

在网络),,,,(U A V t s N =中，对于轨),,,,(12t v v s n - （此轨为无向的），若

A v v i i ∈+1，则称它为前向弧；若A v v i i ∈+1，则称它为后向弧。

在网络N 中，从s 到t 的轨P 上，若对所有的前向弧),(j i 都有ij ij u f <，对所有的后向弧),(j i 恒有0>ij f ，则称这条轨P 为从s 到t 的关于f 的可增广轨。

令

???-=为后向弧当为前向弧当（（),,),,j i f j i f u ij

ij ij ij δ， 则在这条可增广轨上每条前向弧的流都可以增加一个量δ，而相应的后向弧的流可减少δ，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中f 可增广轨的存在是有意义的，因为这意味着f 不是最大流。

最大流的一种算法—标号法

标号法是由Ford 和Fulkerson 在1957年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。

即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。

这种方法分为以下两个过程：

A.标号过程：通过标号过程寻找一条可增广轨。

B.增流过程：沿着可增广轨增加网络的流量。

这两个过程的步骤分述如下。

（A ）标号过程：

（i ）给发点标号为),(∞+

s 。

（ii ）若顶点x 已经标号，则对x 的所有未标号的邻接顶点y 按以下规则标号：

① 若A y x ∈),(，且xy xy u f <时，令},min{x xy xy y f u δδ-=，

则给顶点y 标号为),(y x δ+，若xy xy u f =，则不给顶点y 标号。

② A x y ∈),(，且0>yx f ，令},min{x yx y f δδ=，则给y 标号为),(y x δ-，若0=yx f ，则不给y 标号。

（iii ）不断地重复步骤（ii ）直到收点t 被标号，或不再有顶点可以标号为止。当t 被标号时，表明存在一条从s 到t 的可增广轨，则转向增流过程（B ）。如若t 点不能被标号，且不存在其它可以标号的顶点时，表明不存在从s 到t 的可增广轨，算法结束，此时所获得的流就是最大流。

（B ）增流过程

（i ）令t u =。

（ii ）若u 的标号为t v δ,(+），则t vu vu f f δ+=；若u 的标号为),(t v δ-，则

t uv uv f f δ-=。

（iii ）若s u =，把全部标号去掉，并回到标号过程（A ）。否则，令v u =，并回到增流过程（ii ）。

求网络),,,,(U A V t s N =中的最大流x 的算法的程序设计具体步骤如下：

对每个节点j ，其标号包括两部分信息

该节点在可能的增广路中的前一个节点)(pred j ，以及沿该可能的增广路到该节点为止可以增广的最大流量)(f max j 。

STEP0 置初始可行流x （如零流）；对节点t 标号，即令)(f max t =任意正值（如1）。 STEP1 若0)(f max >j ，继续下一步；否则停止，已经得到最大流，结束。

STEP2 取消所有节点V j ∈的标号，即令0)(f max =j ，

0)(pred =j ；令LIST={s }，对节点s 标号，即令=)(f max s 充分大的正值。

STEP3 如果LIST Φ≠且0)(f max =t ，继续下一步；否则：（3a ）如果t 已经有标号（即

第三届“ScienceWord杯”数学中国数学建模网络挑战赛第二阶段B题一等奖论文

目录（CONTENTS） 一、问题重述 (2) 二、问题分析 (2) 2.1方案理论可行性 (2) 2.2波士顿路网实例 (2) 三、条件假设 (2) 四、符号约定 (2) 五、模型的建立与求解 (3) 5.1模型建立 (3) 5.1.1波士顿城市路网抽象图 (3) 5.1.2交通网连通性 (4) 5.1.3非线性规划模型 (4) 5.1.4拥堵评价指标体系 (4) 5.2路网属性参数估计 (5) 5.2.1路网属性参数约束方程 (5) 5.2.2参数曲线拟合求解 (5) 5.3交通流量之NASH均衡求解 (8) 5.3.1非线性规划求解NASH均衡解的可行性分析 (8) 5.3.2 LINGO求解NASH均衡解 (9) 5.4方案优劣性的量化分析 (10) 5.4.1路网流量均衡下的道路拥堵状况 (10) 5.4.2关闭已拥堵路段后的道路拥堵状况 (13) 5.4.3关闭未拥堵路段后的道路拥堵状况 (13) 5.5方案适用范围的数据分析 (14) 5.5.1路网总流量变化对道路拥堵状况的影响 (14) 5.5.2波士顿路网规划方案适用范围 (15) 六、模型的评价 (15) 七、参考文献 (16) 八、附录 (17) 8.1 LINGO求解均衡解程序 (17) 8.2插值多项式曲线的MATLAB程序 (17)

一 问题重述 Braess悖论宣称：提高某一路段的通行能力，反倒可能使整体路网的通行能力下降。那么，在发生交通拥堵的时候，如果暂时关闭其中的某条道路，是否可以缓解交通堵塞的现象？ 请建立合理的模型，研究临时关闭道路以缓解交通堵塞的可行性。如果可行，请给出具体的关闭方案。城区道路网可以使用北京市二环路的地图，也可以使用美国波士顿的部分城区图。 二 问题分析 2.1方案理论可行性 从规划的角度看，理想情况下，司机可以牺牲个人利益成全大局，使得城市路网无时无刻都能达到最优效益，此时关闭其中任何一条道路都有可能使全局最优解降为局部最优解，即在这种情况下关闭道路的方案是不可行的。从实际情况看，具有个性化需求的司机为了追求个人利益最大化往往使得城市路网的整体效益下降，此时有选择有目的的关闭道路会使得个体最优选择服从于或接近于整体最优决策，有利于提升城市路网的整体效益，即政府的调控是可行的。 2.2波士顿路网实例 道路堵塞的评价指标确定为每个车辆通过该段路网的平均时间，选取美国马萨诸塞州的首府--波士顿作为实证对象，用非线性规划的数学思想求得在总流量一定的情况下交通流量的均衡解，比较关闭某条道路前后指标的变化即可判断方案优劣。如果可行，再令总流量在一定范围内变化，求出此方案的适用范围。 三 条件假设 Ⅰ.所有司机的选择是独立的，非合作的。 Ⅱ.城市路网信息完全公开，司机对路网熟悉程度高。 Ⅲ.车辆在转弯或过十字路口时无时间延误。 Ⅳ.道路布局方案的评价指标是车辆通过该路段的平均时间或路网的使用效益。 Ⅴ.假设波士顿城市路网属于对称双通道系统。 Ⅵ.假设波士顿路网均是双向的，但只有单向的增加车流量能使堵塞加剧。 四 符号约定 i 拥堵系数 α 车辆单独通过路段的时间 β 每增加单位流量所增加的通行时间 t车辆实际通行时间 f 路段当前流量 s 路网内某路段车速

数学建模知识及常用方法

数学建模知识——之新手上路 一、数学模型的定义现在数学模型还没有一个统一的准确的定义，因为站在不同的角度可以有不同的定义。不过我们可以给出如下定义：“数学模型是关于部分现实世界和为一种特殊目的而作的一个抽象的、简化的结构。”具体来说，数学模型就是为了某种目的，用字母、数学及其它数学符号建立起来的等式或不等式以及图表、图像、框图等描述客观事物的特征及其内在联系的数学结构表达式。一般来说数学建模过程可用如下框图来表明：数学是在实际应用的需求中产生的，要解决实际问题就必需建立数学模型，从此意义上讲数学建模和数学一样有古老历史。例如，欧几里德几何就是一个古老的数学模型，牛顿万有引力定律也是数学建模的一个光辉典范。今天，数学以空前的广度和深度向其它科学技术领域渗透，过去很少应用数学的领域现在迅速走向定量化，数量化，需建立大量的数学模型。特别是新技术、新工艺蓬勃兴起，计算机的普及和广泛应用，数学在许多高新技术上起着十分关键的作用。因此数学建模被时代赋予更为重要的意义。二、建立数学模型的方法和步骤 1. 模型准备要了解问题的实际背景，明确建模目的，搜集必需的各种信息，尽量弄清对象的特征。 2. 模型假设根据对象的特征和建模目的，对问题进行必要的、合理的简化，用精确的语言作出假设，是建模至关重要的一步。如果对问题的所有因素一概考虑，无疑是一种有勇气但方法欠佳的行为，所以高超的建模者能充分发挥想象力、洞察力和判断力，善于辨别主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。 3. 模型构成根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。这时，我们便会进入一个广阔的应用数学天地，这里在高数、概率老人的膝下，有许多可爱的孩子们，他们是图论、排队论、线性规划、对策论等许多许多，真是泱泱大国，别有洞天。不过我们应当牢记，建立数学模型是为了让更多的人明了并能加以应用，因此工具愈简单愈有价值。 4. 模型求解可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。一道实际问题的解决往往需要纷繁的计算，许多时候还得将系统运行情况用计算机模拟出来，因此编程和熟悉数学软件包能力便举足轻重。 5. 模型分析 对模型解答进行数学上的分析。“横看成岭侧成峰，远近高低各不同”，能否对模型结果作出细致精当的分析，决定了你的模型能否达到更高的档次。还要记住，不论那种情况都需进行误差分析，数据稳定性分析。例题：一个笼子里装有鸡和兔若干只，已知它们共有 8 个头和 22 只脚，问该笼子中有多少只鸡和多少只兔？解：设笼中有鸡 x 只，有兔 y 只，由已知条件有 x+y=8 2x+4y=22 求解如上二元方程后，得解 x=5,y=3，即该笼子中有鸡 5 只，有兔 3 只。将此结果代入原题进行验证可知所求结果正确。根据例题可以得出如下的数学建模步骤： 1）根据问题的背景和建模的目的做出假设（本题隐含假设鸡兔是正常的，畸形的鸡兔除外） 2）用字母表示要求的未知量 3）根据已知的常识列出数学式子或图形（本题中常识为鸡兔都有一个头且鸡有 2 只脚，兔有 4 只脚） 4）求出数学式子的解答 5）验证所得结果的正确性这就是数学建模的一般步骤三、数模竞赛出题的指导思想传统的数学竞赛一般偏重理论知识，它要考查的内容单一，数据简单明确，不允许用计算器完成。对此而言，数模竞赛题是一个“课题”，大部分都源于生产实际或者科学研究的过程中，它是一个综合性的问题，数据庞大，需要用计算机来完成。其答案往往不是唯一的（数学模型是实际的模拟，是实际问题的近似表达，它的完成是在某种合理的假设下，因此其只能是较优的，不唯一的），呈报的成果是一篇论文。由此可见“数模竞赛”偏重于应用，它是以数学知识为引导计算机运用能力及文章的写作能力为辅的综合能力的竞赛。四、竞赛中的常见题型赛题题型结构形式有三个基本组成部分： 1. 实际问题背景涉及面宽——有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。一般都有一个

数学建模- 图与网络模型及方法

第五章 图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总

运筹学图与网络

第二节 最大流和最小割 一、割 若S 为V 的一个子集，S y S V S S x ∈-=∈,,，记),(S S K =为起点在S 中，终点在S 中的全体有向边的集合，即 {} S v S u v u K ∈∈=,),( （11-4） 我们称边集),(S S K =为网络G 的一个割，称∑∈K e e C )(为K 的容量，记为 Cap K 。 例5 给运输网络如图11-8所示，试 求与给定的j S （j =1，2，3）相对应的 Cap j K 。 解取{}11,v x S =， {}),(),,(),,(221311v x v v v v K =， Cap 1K =10+6+9=25。 图11-8 取 {}4212,,,v v v x S =， {}),(),,(),,(5254312v v v v v v K =， Cap 2K =10+6+13=29。 取 {}54213,,,,v v v v x S =， {}),(),,(5313y v v v K =， Cap 3K =10+10=20。 可见，若把割K 的边全从G 中移去，G －K 不一定分离成两部份（如例5中，3K G -仍为一个连通图），但是它一定把G 的全部自源x 到汇y 的路断开，也就是说此时流不能在G 上发生。故从直观上不难理解，G 的任一流f 的流值Val f 不能超过任一割的容量。 二、最大流与最小割 若?f 为满足下列条件的流： Val ?f ={}的一个流 为G f Valf max ， （11-5）

则称?f 为G 的最大流。 若?K 为满足下列条件的割。 Cap ?K ={}的一个割 为G K K Cap min ， （11-6） 则称?K 为G 的最小割。 例1 这个运输问题，就是一个在图11-6中求x 至y 的最大流问题。对此，我们不难建立线性规划模型来求出最优解。但由于网络模型结构的特殊性，我们可以建立有效的求最大流的算法，且求出的最优解是一个整数解。 定理1 对于G 中任一流f 和任一割),(S S K =，有 Val )()(s f S f f -+-= 其中，∑∈+= ),()()(S S e e f S f ，∑∈-=),()()(S S e e f S f 例如，在图11-7中，取{}11,,v x x S =，则 {}),(),,(),,(),,(),,(),(221412121x x x x v v v v v x S S = {}),(),(12v x S S = 4815510315)(=++++=+S f 8)(=-S f 可见，Val )()(40S f S f f -+-== 定理1说明，通过G 的任一横截面的净流值都为Val f ，亦即Val f 为任一横截面的输出量与输入量的代数和。 若f 为G 上一个流，对任E e ∈，若)()(e C e f =，称边e 为f 饱和边；若)(e f ＜)(e C ，称边e 为f 不饱和边；若)(e f ＞0，称边e 为f 正边；若)(e f =0，称e 为f 零边。 定理2 对于G 上任一流f 和任一割),(S S K =，有 1．Val f ≤Cap K ； 2．Val f =Cap K 的充要条件为：任),(S S e ∈，边e 为f 饱和边；任),(S S e ∈，边e 为f 零边。 证 1．∑∈+= ),()()(S S e e f S f ≤∑∈=K e CapK e C )( 又 )(S f -≥0，

2020年MathorCup高校数学建模挑战赛A题

2020年第十届MathorCup高校数学建模挑战赛题目 A题 无车承运人平台线路定价问题 国内公路运输市场开放以来，逐渐形成了“小，散，乱”的发展现状。为规范运输市场，国家交通运输部办公厅于2016年9月印发《关于推进改革试点加快无车承运物流创新发展的意见》，并初步公布了48个无车承运人试点平台。随着我国无车承运行业的逐步兴起，承运线路的科学定价问题是众多无车承运人平台亟待解决的问题。 图1 国内无车承运人模式 图1展示了国内无车承运人的主要运营模式，该模式下有三个主要的参与角色，分别为货主、无车承运人平台以及承运人。作为无车承运人平台，既需要面向货主的运输任务进行报价，同时也需要面向承运司机进行报价。 本研究以无车承运人的视角，暂不考虑面向货主的运输任务的报价，仅面向广大拥有运力资源（货车）的承运端司机，将需要承运的线路任务以一定价格提前发布到网络平台上供承运端司机浏览并决定是否承运该运

输任务。平台采用动态定价的形式保证每个任务必须被承运，若任务未被承运将带来一定损失。作为承运端的司机，会根据平台发布的线路任务和价格进行判断是否接单，司机接单则视为该线路任务交易成功，此线路任务随即从平台下架。若在给定的时间内，该任务没有司机接单，则该线路就可以进行调价。每条线路任务最多允许发布3次价格，即首次发布线路价格后仍可刷新两次线路价格，其中附件1数据文件中的线路指导价为平台首次发布的线路价格。假设上述线路任务全部为固定车型的整车任务，即一个任务需要由某种车型的1辆车完成，不考虑拼载任务。本无车承运人平台在当前阶段较为关注的目标是快速促进成交和较低的承运成本。 基于以上背景，请你们的团队根据附件给出的数据（可不限于此），通过数学建模的方法帮助某无车承运人平台解决以下问题： 问题1：通过定量分析的方法，研究影响无车承运人平台进行货运线路定价的主要因素有哪些，并说明理由。 问题2：根据附件1数据，通过建立数学模型，对已经成交货运线路历史交易数据中的定价进行评价。 问题3：建立关于线路定价的数学模型，给出附件2的线路任务的三次报价以及总成本定价，并填充在附件3的表格中；给出你们的调价策略；评价你们对附件2的线路任务所给出的定价。其中附件3的表格以Excel 文件形式，连同论文答卷一起上传至参赛系统，请勿改变附件3中各任务ID的原有顺序。附件3将用于测试报价的准确性，对于某个确定的任务，三次报价中有一次成交，则后续价格将不再考虑。

数学建模常用的十种解题方法

数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B 实现。 1蒙特卡罗计算重积分的最简算法-------均匀随机数法 二重积分的蒙特卡罗方法(均匀随机数) 实际计算中常常要遇到如()dxdy y x f D ??,的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。 定理 1 )1( 设式()y x f ,区域 D 上的有界函数, 用均匀随机数计算()??D dxdy y x f ,的方法: (l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ; ()j i y x ,,i=1,…,n 在Ω上的均匀分布随机数列,不妨设()j i y x ,, j=1，…k 为落在D 中的k 个随机数, 则n 充分大时, 有

2016年第九届认证杯数学中国数学建模网络挑战赛

2016年第九届数学中国数学建模网络挑战赛 策 划 书 数学建模协会 二零一六年四月九日

一、活动主题: 2016年第九届数学中国数学建模网络挑战赛 二、活动背景: 数学中国数学建模网络挑战赛，自2008年至今已举办了八届，它是由内蒙古自治区数学学会主办，由数学中国（https://www.doczj.com/doc/bd9082103.html,）、北京中科院软件中心有限公司和第五维信息技术有限公司协办，由全球数学建模能力认证中心赞助支持的全国性数学建模活动。今年数学中国继续获得全球数学建模能力认证中心的授权，为参赛获奖的学生颁发数学建模能力认证，其目的是激励学生培养数学建模的能力，明确数学建模能力要求及范围，为数模社会效益化积累人才。 三、活动目的及其意义: （1）自主学习与认证赛相结合：我们举办认证赛的目的，是帮助学生的明确数学建模能力范围，从而勉励自己懂得如何自主学习数模且勤学多问。学生只有明确数学建模能力范围，才会去考虑如何利用数模能力来解决问题，从而对数学建模产生浓厚的学习兴趣，而比赛的真正目的不仅是为了获得的认可，还要让学生掌握数学建模技能。 （2）为了进一步推广美赛在中国的普及，进一步提高我国的数学建模整体水平和英文科技论文书写能力。 (3)旨在帮助广大想参加美赛的同学提高对于开放性题目的处理能力； (4)帮助学生提供数学建模能力证明的认证证书，为深造、学术交

流、求职提供便利； (5)凡获取认证资格的认证者，将会进入数学中国的数模人才库，此人才库是由认证中心和数学中国联合维护； (6)数学中国会对一些具有创新性的文章进行赛后的指导，帮助其将论文发表到全球数学建模能力认证中心的国际（英文）刊物上。 四、活动开展形式: 评议参赛者的英文论文 五、活动时间与地点： 时间：北京时间2016年4月15日上午8时-4月18日上午8 时北京时间2016年5月13日上午8时-4月16日上午8 时 地点：吕梁学院电教楼二楼 六、活动对象： 研究生、本科生、专科生、数学建模爱好者； 七、活动内容： 竞赛与教学相结合：我们竞赛分为两个阶段举行，每次竞赛结束三天后，我们会将所有的论文根据赛题、模型等分类在网上公示，同时提供评阅标准及赛题分析。每篇论文都会获得评分和简短的评阅意见。老师可以组织参赛学生以公示的论文为例，系统学习每道题目的不同模型及算法，使学生逐步积累数学模型及参赛经验，同时教会学生如何去评价模型、指出模型的优缺点，便于以后的论文

什么是数学模型与数学建模

1. 什么是数学模型与数学建模 简单地说：数学模型就是对实际问题的一种数学表述。 具体一点说：数学模型是关于部分现实世界为某种目的的一个抽象的简化的数学结构。 更确切地说：数学模型就是对于一个特定的对象为了一个特定目标，根据特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学结构可以是数学公式，算法、表格、图示等。 数学建模就是建立数学模型，建立数学模型的过程就是数学建模的过程（见数学建模过程流程图）。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的数学手段。 2.美国大学生数学建模竞赛的由来： 1985年在美国出现了一种叫做MCM的一年一度大大学生数学模型（1987年全称为Mathematical Competition in Modeling,1988年改全称为Mathematical Contest in Modeling,其所写均为MCM）。这并不是偶然的。在1985年以前美国只有一种大学生数学竞赛（The william Lowell Putnam mathematial Competition,简称Putman(普特南）数学竞赛），这是由美国数学协会（MAA--即Mathematical Association of America的缩写）主持，于每年12月的第一个星期六分两试进行，每年一次。在国际上产生很大影响，现已成为国际性的大学生的一项著名赛事。该竞赛每年2月或3月进行。 我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为使这一赛事更广泛地展开，1990年先由中国工业与应用数学学会后与国家教委联合主办全国大学生数学建模竞赛（简称CMCM），该项赛事每年9月进行。

数学建模常用方法

数学建模常用方法 建模常用算法,仅供参考： 1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必 用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通 常使用L i n d o、L i n g o软件实现） 4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种 暴力方案,最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计 算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文 中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理） 一、在数学建模中常用的方法： 1.类比法 2.二分法 3.量纲分析法 4.差分法 5.变分法 6.图论法 7.层次分析法 8.数据拟合法 9.回归分析法 10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划） 11.机理分析 12.排队方法

数学建模方法模型

数学建模方法模型 一、统计学方法 1 多元回归 1、方法概述: 在研究变量之间的相互影响关系模型时候用到。具体地说:其可以定量地描述某一现象和某些因素之间的函数关系，将各变量的已知值带入回归方程可以求出因变量的估计值，从而可以进行预测等相关研究。 2、分类 分为两类:多元线性回归和非线性线性回归;其中非线性回归可以通过一定的变化转化为线性回归，比如:y=lnx 可以转化为 y=u u=lnx 来解决;所以这里主要说明多元线性回归应该注意的问题。 3、注意事项 在做回归的时候，一定要注意两件事: (1) 回归方程的显著性检验(可以通过 sas 和 spss 来解决) (2) 回归系数的显著性检验(可以通过 sas 和 spss 来解决) 检验是很多学生在建模中不注意的地方，好的检验结果可以体现出你模型的优劣，是完整论文的体现，所以这点大家一定要注意。 4、使用步骤: (1)根据已知条件的数据，通过预处理得出图像的大致趋势或者数据之间的大致关系; (2)选取适当的回归方程; (3)拟合回归参数; (4)回归方程显著性检验及回归系数显著性检验 (5)进行后继研究(如:预测等)

2 聚类分析 1、方法概述 该方法说的通俗一点就是，将 n个样本，通过适当的方法(选取方法很多，大家可以自行查找，可以在数据挖掘类的书籍中查找到，这里不再阐述)选取 m 聚类中心，通过研究各样本和各个聚类中心的距离 Xij，选择适当的聚类标准，通常利用最小距离法(一个样本归于一个类也就意味着，该样本距离该类对应的中心距离最近)来聚类，从而可以得到聚类结果，如果利用sas 软件或者 spss 软件来做聚类分析，就可以得到相应的动态聚类图。这种模型的的特点是直观，容易理解。 2、分类 聚类有两种类型: (1) Q型聚类:即对样本聚类; (2) R型聚类:即对变量聚类; 通常聚类中衡量标准的选取有两种: (1) 相似系数法 (2) 距离法 聚类方法: (1) 最短距离法 (2) 最长距离法 (3) 中间距离法 (4) 重心法 (5) 类平均法 (6) 可变类平均法 (7) 可变法

2011数学中国数学建模网络挑战赛A题特等奖论文.

数学建模网络挑战赛 承诺书 我们仔细阅读了第四届“互动出版杯”数学中国数学建模网络挑战赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们允许数学中国网站(https://www.doczj.com/doc/bd9082103.html,)公布论文，以供网友之间学习交流，数学中国网站以非商业目的的论文交流不需要提前取得我们的同意。 我们的参赛队号为：1753 参赛队员(签名) ： 队员1：刘少杰 队员2：彭岩 队员3：姚娟娟 参赛队教练员(签名)：无 参赛队伍组别：研究生组

数学建模网络挑战赛 编号专用页 参赛队伍的参赛队号：（请各个参赛队提前填写好）：1753 竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：

2011年第四届“互动出版杯”数学中国 数学建模网络挑战赛 题 目 客机水面迫降时的姿态 关 键 词 水上迫降、 有限元、插值函数、Newmark 摘 要： 随着航空业的不断发展，飞机的不断增多，近年来飞机、直升机在近海或跨海使用越来越频繁，发生水上迫降和坠毁事故也逐渐增多。1959年到1991年以来发生的26起商用飞机水上事故的统计表明，飞机水上迫降安全至少需要考虑两方面因素：飞机着水姿态和结构强度。 水上迫降模型试验表明，客机合适的着水姿态，可以保证客机着水时不出现剧烈的“跳跃”、“翻转”等情况；而且保证机身下部蒙皮不破裂，从而使得机舱在一定时间内不进水，为乘员安全撤离赢得足够时间和空间。 由于客机水上迫降涉及多场耦合，问题十分复杂。基于本问题，从经典的弹性力学出发建立的多场耦合偏微分方程组无法计算。为此，本文采取有限单元法，用三角形壳单元离散了客机模型的求解域，找到了位移插值函数，建立了动力学控制方程。这将问题简化成求解一组常微分方程组，使得客机迫降姿态问题可解。 利用ABAQUS 软件平台，建立了客机的有限元模型，并导入具体参数，基于Newmark 计算方法使控制方程解耦，对4种工况条件进行了动力学计算，得到了如下结果： 工况攻角/° 腹部应力峰 尾翼应力峰 舱门X 方向舱门Y 方向舱门Z 方向2 10 58.79 81.53 9.28 7.73 1.85 3 12 141.2 293.9 16.1 12.5 3.26 4 15 214.6 499.7 25.78 23.75 7.65 结果表明：客机以5°攻角着水时，客机腹部和尾翼应力峰值最小，客机的舱门X 、Y 、Z 三个方向的变形也最小，舱门可安全打开。 参赛队号 1753 所选题目 A

数学建模中常见的十大模型

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的

数学建模 运筹学模型(一)

运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 n n x C x C x C Z ++=211m i n ????? ?? ??=≥≥+++≥+++≥+++??) ,,2,1(0, ,, 22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 ∑== n j j j x C Z 1 m i n ??? ??? ?==≥≥??∑=),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 n n x C x C x C Z +++= 2211m a x

数学建模方法和步骤

数学建模的主要步骤: 第一、模型准备 首先要了解问题的实际背景,明确建模目的,搜集必需的各种信息,尽量弄清对象的特征. 第二、模型假设 根据对象的特征和建模目的,对问题进行必要的、合理的简化,用精确的语言作出假设,是建模至关重要的一步.如果对问题的所有因素一概考虑,无疑是一种有勇气但方法欠佳的行为,所以高超的建模者能充分发挥想象力、洞察力和判断力,善于辨别主次,而且为了使处理方法简单,应尽量使问题线性化、均匀化. 第三、模型构成 根据所作的假设分析对象的因果关系,利用对象的内在规律和适当的数学工具,构造各个量间的等式关系或其它数学结构.这时,我们便会进入一个广阔的应用数学天地,这里在高数、概率老人的膝下,有许多可爱的孩子们,他们是图论、排队论、线性规划、对策论等许多许多,真是泱泱大国,别有洞天.不过我们应当牢记,建立数学模型是为了让更多的人明了并能加以应用,因此工具愈简单愈有价值. 第四、模型求解 可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法,特别是计算机技术.一道实际问题的解决往往需要纷繁的计算,许多时候还得将系统运行情况用计算机模拟出来,因此编程和熟悉数学软件包能力便举足轻重. 第五、模型分析 对模型解答进行数学上的分析."横看成岭侧成峰,远近高低各不?quot;,能否对模型结果作出细致精当的分析,决定了你的模型能否达到更高的档次.还要记住,不论那种情况都需进行误差分析,数据稳定性分析. 数学建模采用的主要方法有： （一）、机理分析法：根据对客观事物特性的认识从基本物理定律以及系统的结构数据来推导出模 型. 1、比例分析法：建立变量之间函数关系的最基本最常用的方法. 2、代数方法：求解离散问题（离散的数据、符号、图形）的主要方法. 3、逻辑方法：是数学理论研究的重要方法,对社会学和经济学等领域的实际问题,在决策,对策等学科中得到广泛应用. 4、常微分方程：解决两个变量之间的变化规律,关键是建立“瞬时变化率”的表达式. 5、偏微分方程：解决因变量与两个以上自变量之间的变化规律. （二）、数据分析法：通过对量测数据的统计分析,找出与数据拟合最好的模型 1、回归分析法：用于对函数f（x）的一组观测值（xi,fi）i=1,2,…,n,确定函数的表达式,由于处理的是静态的独立数据,故称为数理统计方法. 2、时序分析法：处理的是动态的相关数据,又称为过程统计方法. 3、回归分析法：用于对函数f（x）的一组观测值（xi,fi）i=1,2,…,n,确定函数的表达式,由于处理的是静态的独立数据,故称为数理统计方法.

数学建模各类竞赛时间

数学建模竞赛时间汇总（仅供参考） 国家竞赛： ?全国大学生数学建模竞赛 每年9月(一般在中旬某个周末的星期五至下周星期一共3天，72小时）举行 ?全国研究生数学建模竞赛 （从9月24日上午8时开始，至9月28日中午12时结束。 竞赛报名时间顺延至9月18日。） ?数学中国数学建模挑战赛 数学中国数学建模网络挑战赛于4月-6月举行，竞赛分为“建模基础” 及“模型改进、应用”两个阶段进行，第一阶段比赛于4月22日-4 月25日进行，第二阶段比赛于5月20日-23日进行。 ?美国大学生数学建模竞赛 美国大学生数学建模竞赛将于：2012年2月9号晚上8:01分（美国东部时间）——2012年2月13号晚上8:00（美国东部时间）举行!(注明：北京时间2012年2月10日早上9：01分——2012年2月14日早上9:00截止) ?全国大学生电工建模竞赛 两年一次，竞赛于11月下旬 地区赛： ?华东数学建模邀请赛

报名时间：3月21日—4月30日，各校组织报名； 比赛时间：5月4日—5月10日，正式比赛为三个题目，选做一个； 收题时间：5月11日，各校完成答卷回收工作。 ?苏北数学建模联盟赛 ?东北三省数学建模联赛 ?华中数学建模联盟赛 报名时间： 2011年3月30日开始至2011年4月22日晚上9:00截止。 4月25日至4月27日为报名信息公示时间，届时将在华中数学建网（https://www.doczj.com/doc/bd9082103.html,）上公布报名参赛队伍信息（为保护大家隐私只公布部分信息）请大家认真核对报名信息。 竞赛时间： 开始时间：2011年4月29日，上午9：00 结束时间：2011年5月3日，上午9：00 竞赛共为连续的96小时，各参赛队竞赛结束时应在规定时间、地点提交论文。

数学建模常用模型方法总结

数学建模常用模型方法总结 无约束优化 线性规划连续优化 非线性规划 整数规划离散优化 组合优化 数学规划模型多目标规划 目标规划 动态规划从其他角度分类 网络规划 多层规划等… 运筹学模型 （优化模型） 图论模型存 储论模型排 队论模型博 弈论模型 可靠性理论模型等… 运筹学应用重点:①市场销售②生产计划③库存管理④运输问题⑤财政和会计⑥人事管理⑦设备维修、更新和可靠度、项目选择和评价⑧工程的最佳化设计⑨计算器和讯息系统⑩城市管理 优化模型四要素：①目标函数②决策变量③约束条件 ④求解方法(MATLAB--通用软件LINGO--专业软件) 聚类分析、 主成分分析 因子分析 多元分析模型判别分析 典型相关性分 析 对应分析 多维标度法 概率论与数理统计模型 假设检验模型 相关分析 回归分析 方差分析 贝叶斯统计模型 时间序列分析模型 决策树 逻辑回归

传染病模型马尔萨斯人口预测模型微分方程模型人口预 测控制模型 经济增长模型Logistic 人口预测模型 战争模型等等。。 灰色预测模型 回归分析预测模型 预测分析模型差分方程模型 马尔可夫预测 模型 时间序列模型 插值拟合模型 神经网络模型 系统动力学模型(SD) 模糊综合评判法模型 数据包络分析 综合评价与决策方法灰色关联度 主成分分析 秩和比综合评价法 理想解读法等 旅行商(TSP)问题模型 背包问题模型车辆路 径问题模型 物流中心选址问题模型 经典NP问题模型路径规划问题模型 着色图问题模型多目 标优化问题模型 车间生产调度问题模型 最优树问题模型二次分 配问题模型 模拟退火算法(SA) 遗传算法(GA) 智能算法 蚁群算法(ACA) (启发式) 常用算法模型神经网络算法 蒙特卡罗算法元 胞自动机算法穷 举搜索算法小波 分析算法 确定性数学模型 三类数学模型随机性数学模型

2017“认证杯”数学中国数学建模网络挑战赛高中组个人赛赛题

地震监测台站的合理布局问题 （高中组个人赛赛题） 2017年8月8日21时19分46秒，四川省北部阿坝州九寨沟县发生了7.0级地震，震中位于北纬33.20度，东经103.82度的九寨沟核心景区西部5公里处的比芒村，震中东距九寨沟县城永乐镇39公里、南距松潘县66公里、东北距舟曲县83公里、东南距文县85公里、西北距若尔盖县90公里，东偏北距陇南市105公里，南距成都市285公里。九寨沟地震致使九寨沟县经济社会遭到重创，所有在建项目和新建项目全面停工或延期开工，全县预估直接经济损失达224.5亿元。 地震监测台站可以对地震时和地震前的各类自然现象进行监测，其对地震发生时的灾情掌握和地震发生前的预报具有重要的意义，是一个国家抗灾减灾综合实力的体现。基于地震监测设施观测内容、原理的不同，其一般可以分为测震监测设施、强震监测设施与前兆监测设施三类。测震、强震监测设施主要用于地震发生时对地震运动状态的观测，测震监测设施精度较高，可观测1.0级强度的地震；强震监测设施精度较低，用于观测4.0以上级别的地震。前兆监测设施主要通过对多类物理和化学场量的持续观测，研究了解地震发生机理并做出地震预报。根据观测的对象，将前兆观测分为三类，即形变（含重力）观测、电磁观测和地下流体观测。 地震监测台站的布局原则如下： 1、均衡全面原则：各类地震监测设施基本做到均衡分布、全面覆盖。 2、新技术原则：结合地震台预报技术发展特点，大力增加技术更加先进、对城市建设干扰较小的地震监测设施，如GPS卫星观测设施，确保地震监测水平不断提升。 3、城乡建设协调原则：新建、迁建的地震监测设施尽量避开对其有影响的干扰要素，如三级公路，高压输电线路，工厂等。 4、经济原则：如果在半径100公里的范围内台站数少于20的，应以增建新的台站为主，如果在25-30之间的，应以改建原有台站提高台站的观测质量为主。 5、精度原则：达到全县1.0级以上的地震监测能够在3分钟内给出，4.0级以上地震的初步测定结果，能够在20分钟内完成，对有显著影响的地震在震后1小时内能够锁定震中位置。 下图是九寨沟县周围的地震监测台站的分布图，请结合该图解决如下问题：问题一、考虑到地震监测台站的重要性，政府希望新建两个台站，请建立数学模型，规划两个台站的位置和类型。 问题二、对于该地区，在新增两个台站的基础上，是否还有必要再新增站点？如果有资金可以改建3个站点，你打算如何使用？请结合数学模型给出合理化建议。