数学建模中的图论方法

数学建模中的图论方法

一、引言

我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。

另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。

图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：

AMCM90B－扫雪问题；

AMCM91B－寻找最优Steiner树；

AMCM92B－紧急修复系统的研制(最小生成树)

AMCM94B－计算机传输数据的最小时间(边染色问题)

CMCM93B－足球队排名(特征向量法)

CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)

CMCM98B－灾情巡视路线(最优回路)

等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。

本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。

二、基本概念和性质

首先给出图论中的一些基本概念。

1．一个图G由一个顶点集V和一个边的集E组成。E中每个元素e是连接顶点集V中两个顶点u和v的边，称e与u，v关联。我们规定连接两个顶点u、v至多有一条边，且一条边的两个顶点不重合，这种图称为简单图。

2．顶点集为V，边集为E的图G通常记为G=（V，E）。图G1=（V1，E1）称为G的子图，如果V1V，E1E。

3．顶点v的度(或“次”)是指与v相关联的边的个数。图G的度数之和为边数的两倍。

4．若图G中任意两个顶点u、v之间都存在连接它们的路，称G为连通图。

5．W=v0e1v1e2……ekvk，其中ei∈E，vj∈V，ei与vi-1，vi关联，称W是图G的一条道路。v0是起点，vk是终点；各边相异的道路叫做行迹，各顶点相异的道路叫做轨道；起点和终点重合的道路为回路；起点和终点重合的轨道为圈；包含图中每条边的回路称为Euler回路；含Euler回路的图称为Euler图。

6．一个无圈的连通图称为树。树是最简单而最重要的一类图。树有下列重要性质：

性质：

1)在树中去掉任意一条边，所得的图是不连通的。

2)在树中任意两个不相邻的顶点u、v之间添加一条新的边，所得的图恰有一个圈。

下述定理是树的判断定理：

定理：若图G具有下列性质中的两条，则它是树，且也具有第三条性质。

(1)．G是连通图；

(2)．G没有圈；

(3)．G的顶点数=G的边数+1。

7．如果图G=（V，E）的子图G t=（V t，E t）是一个树，且V t=V，称G t是G的生成树。G连通的充要条件是G有生成树。生成树一般而言数量很大。

8．设对图G=（V，E）的每一条边e赋予一个实数W（e），称为e的权，G称为赋权图(加权

图)。假设G是连通的赋权图，要找G的连通子图G *=（V，E*），使得W（G*）=∑

∈E

e

e W) (为最

小。显然G*应为G的一个生成树。G的权最小的生成树称为G的最小生成树。

三、算法介绍

3．1 最短轨道问题

背景：给定连接若干城市的铁路网，寻求从指定城市v0到各城v去的最短道路。

数学模型：图G为一赋权图，对任给的v∈V(G)，寻求轨道P(v0,v)，使得

W(P(v0,v))=min{W(P),P取自所有v0到v的轨道集合}

其中W(P)是轨道P上各边权之和。

这一问题可用迪克斯特拉(Dijkstra)算法解决。

基本思想：从起点v0开始，逐步寻找到达各点的最短路，在每一步都对顶点记录一个数，称之为该点的标号，它表示v0到该点的最短距离的上界，或就是v0到该点的最短距离。实际上每一步都通过把至少一个具有T标号的点变成P标号(即把一个不是最短距离标号的顶点变成是最短距离标号的顶点)，这样最多经过|V(G)|-1步就可完成。

步骤：记l(v)为v0到v的距离。

(1) l(v0)=0，l(v) = ∞，(v≠v0)；S0={v0}，i=0。

(2) 对v?Si，min{l(v)，l(vi)+w(viv)}代替l(v)；这样找到点vi＋1使得l(v)取最小值，v(i＋1)∈(Si的余集)。令S(i＋1)＝Si＋{v(i+1)}。

(3) i=|V(G)|-1时停止，否则，i+1，转到(2)。

实例：CMCM94A－公路选址问题。

3．2 求最小生成树

1．克罗斯克尔(Kruskal)算法(1956年)，俗称“避圈法”

背景：筑路选线问题欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij。设计一个线路图，使总造价最低。

分析：选线问题的数学模型是在连通加权图上求权最小的连通生成子图。显然，权最小的连通生成子图是一个生成树，即求取连通加权图上的权最小的生成树，这就归结为最小生成树问题。这个问题可由克罗斯克尔(Kruskal)算法解决。

思路：从“边”着手选最小生成树。

步骤：设G为由m个节点组成的连通赋权图。

(1) 先把G中所有的边按权值大小由小到大重新排列，并取权最小的一条边为树T中的边。即选e1∈E，使得w(e1)＝min。

(2) 从剩下的边中按(1)中的排列取下一条边。若该边与前面已取进T中的边构成一个回路，则舍弃该边，否则也把它取进T中。若e1，e2，…，ei已经选好，则从E－{e1，e2，…，ei}中选取ei＋1，使得G[{e1，e2，…，ei，ei+1}]中无圈，且w(ei+1)=min。

(3) 重复步骤(2)，直到T中有m－1条边为止。则T为G的最小生成树。

该算法的复杂度为O(e log e)，其中e是图G中的边数。

2．普莱姆(Prim)算法思路：从点入手来选边

步骤：(1) 在图G中任取一个节点vi1，并放入T中。

(2) 令S＝V(G)/V(T)，V(G)、V(T)分别是G、T的节点集。

(3) 在所有连接V(T)节点与S节点的边中，选出权值最小的边(u0,v0)，即

w(u0,v0)=min{w(u,v)|u∈V(T), v∈S}。

(4) 将边(u0,v0)放入T中。

(5) 重复步骤(2)－(4)，直到G中节点全部取完。

该算法的复杂度为O(n^2)，其中n为图G的节点数。

3．1975年管梅谷提出的“破圈法”

3．3 Steiner生成树

实际背景：在已有网络上选择连通几个城市的最廉价交通或通讯网。

数学模型：从已知的加权连通图上求取最小的树状子图，使此树包含指定的顶点子集。

第一个的边长为3，第二个的边长为1，总费用第二个更少。

分析：与传统的最小生成树相比，这里可以引入若干“虚拟站”并构造一个新的Steiner树，这样可以降低由一组站生成的传统的最小生成树所需的费用(降低的费用大概为13.4%)。而且为构造一个有n个顶点的网络的费用，最低的Steiner树决不需要多于(n－2)个虚设站。当然，有时最小Steiner 生成树与最小生成树相同。寻求最小Steiner生成树的算法有Melzak算法(1961年)，但是这是一个指数时间的算法，现在没有多项式时间的算法，换句话说它是一个NP问题。而且，这里的要求是用直折线代替欧氏直线距离，因而不能利用直接的算法。所以在解决这样的问题的时候，为减少运算的时间，理论上的分析是必要的：比如树的长度的下界，Steiner树的存在性，虚设站的位置等等。常用的算法还包括穷举法、模拟退火法等。

Melzak算法：其基础是3点steiner树，即3点Fermat问题的几何作图法。参考[2]，Page375。

模拟退火法原理：模拟退火法(Simulated annealing, SA)是模拟热力学中经典粒子系统的降温过程，来求解极值问题。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局极小点。其步骤如下(也称

为Metropolis过程)：

（1）给定初始温度T0，及初始点，计算该点的函数值f(x)。

（2）随机产生扰动Δx，得到新点x′=x+Δx，计算新点函数值f(x′),及函数值差Δf=f(x′)-f(x)。

（3）若Δf≤0，则接受新点，作为下一次模拟的初始点；

（4）若Δf>0，则计算新点接受概率：，产生［0，1］区间上均匀分布的伪随机数r,r∈［0,1］，如果p(Δf)≥r，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。

模拟退火法实例：

1．MCM91B(通讯网络中的极小生成树)是一个求STEINER生成树问题，参见《工科数学专辑》Page：70－78。

2、CMCM 97A题

97年全国大学生数模竞赛A题“零件的参数设计”，可以归结为非线性规划模型，由于目标函数很复杂，且又是一个多维函数，因此求解比较困难，为应用模拟退火法进行求解，将7个自变量的取值范围进行离散化，取步长为0.0001，这样，所有7个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。

这个问题算法的状态调整规则是：每次从7个自变量中随机选取1-4个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取最佳的作为候选者，自变量移动的距离随着温度的降低而减少，为避免陷入局部极小，可以从多个随机选取的初始值开始计算，算法的其它步骤同上。

3、CMCM 98B题

98年全国大学生数学建模竞赛B题“水灾巡视问题”，是一个推销员问题，本题有53个点，所有可能性大约为exp(53),目前没有好方法求出精确解，既然求不出精确解，我们使用模拟退火法求出一个较优解，将所有结点编号为1到53，1到53的排列就是系统的结构，结构的变化规则是：从1到53的排列中随机选取一个子排列，将其反转或将其移至另一处，能量E自然是路径总长度。具体算法描述如下：

步1：设定初始温度T，给定一个初始的巡视路线。

步2：步3 --8循环K次

步3：步4--7循环M次

步4：随机选择路线的一段

步5：随机确定将选定的路线反转或移动，即两种调整方式：反转、移动。

步6：计算代价D，即调整前后的总路程的长度之差

步7：按照如下规则确定是否做调整：

如果D<0，则调整

如果D>0，则按照EXP(-D/T)的概率进行调整

步8：T*0.9-->T，降温

3．4 Euler回路

设G是一个图，若存在这样一条回路，使它经过图中的每条边且只经过一次又回到起始节点，就称这样的回路为Euler回路。

背景：哥尼斯堡七桥问题

定理：对连通图G，下列条件是相互等价的：

(1) G是Euler图；

(2) G的每个节点的度数都是偶数；

(3) G的边集可以分解为若干个回路的并。

对有向图，出度＝入度。

算法：弗罗莱(Fleury)算法(1921)

(1) 任给v0 V(G)，R＝{v0}

(2) 设路R＝v0e1v1e2v2……eivi已选定，则从E(G)\{e1,e2,……ei}中选边ei+1，且满足：

ei+1与vi相连；除非已无选择，ei+1不要选E(Gi)＝E(G)－{ e1,e2,……ei }中的桥(注：桥，去掉之后图不连通)

(3) 重复(2)，直到不能再选为止

实例：MCM90B铲雪问题中单车道单车扫雪－地图是Euler图的情形。

说明：如果图G不是Euler图，也就是说不存在Euler回路，这时候求解就比较困难。求解前需要做一些处理，添加一个边子集E1，E1＋G＝G1构成一个Euler图，然后再寻找Euler回路。注意图G不是Euler图时，必有偶数个奇数度的节点，可以给这些节点两两配对，求两点间的最短路，将这些最短路画在一起构成附加边子集E1。这里的困难在于：奇数度的节点较多时，配对方案也多。3．5 网络中的最大流

背景：把商品从生产地运往市场，交通网上每个路段能力给定的条件下，设计一个运输方案，使得

运输最快。

网络：规定起点s 、中间点和终点t 的赋权图。

数学模型：有向图G ，每边加权c(e)，称c(e)为边e 之容量，设G 为严格的有向图，则称这个有向的加权图为一个网络。映射f ：E(G)→R 满足

(c1) 任给e ∈E(G)，0≤f(e)≤c(e)；

(c2) 任给v ∈V(G)－{s,t}，

∑∈)()(v e e f α－∑∈)

()(v e e f β＝0；其中a(v)是以v 为头的边集(流进)，b(v)是以v 为尾的边集(流出) ，即除起点和终点外，各节点流入量总和等于流出量总和。称f(e)为流函数，称

F ＝

∑∈)()(t e e f α－∑∈)()(t e e f β 为流量。

我们的目标是寻找一个流函数f ，使其流量最大。1956年，福特(Ford)和福尔克逊(Fulkerson)提出了求最大流的算法。

最大流最小割定理：流过网络的最大流量等于最小割集的容量。

2F 算法：

(1) 对每边e ，选f(e)＝0；

(2) 标志顶s ，其它顶未标志；

(3) 选可“向前标志”或可“向后标志”的顶v 。若无此种顶可选时，停止，现流函数即为最大流；若有此种顶可选时，则得到新的标志顶v 及标志边e 。若v ＝t ，则转(4)；否则转(3)。

(4) 设已得标志之轨为(此轨为无向的)s e1v1e2v2……et t ，从t 开始沿此轨逆行，令

)(min 1i l

i e ?=?≤≤， 若ei 是前进边，即在有向图中ei ＝vi －1vi(s ＝v0，t ＝v l )，则f(ei)＝f(ei)＋?；

若ei 是后退边，即在有向图中ei ＝vivi －1，则f(ei)＝f(ei)－?；

(5) 转(2)。

向前和向后标志的含义如下：若e ＝uv ，u 已有标志，v 没有标志，且c(e)>f(e)，则称通过边e 可以向前标志顶点v ，且规定?(e)＝c(e)－f(e)，得到标志边e 。若e ＝vu ，u 已有标志，v 没有标志，且f(e)>0，则称通过边e 可以向后标志顶v ，规定?(e)＝f(e)，且得到标志边e 。?(e)的含义是边e 上可以增载的上界。

说明：

1． 如果每边之容量c(e)都是有理数，则2F 算法在有限步之内可以求得最大流。

2．容量有上下界的网络，需要构造附加网络。

3.6 最小费用——最大流问题

这是在上述讨论的基础上增加关于使费用最小的目标。解决的办法是采用“对偶法原理”：1．先用上面讨论的方法求出网络的最大流量；

2．然后在原始的网络中福德算法找出从起点 v s 到终点 v t 的最短路线——最短增广链；

3．在该增广链上找出最大调整量，并调整流量得到一个可行流，则此可行流的费用最小。如果此时流量等于最大流量，那么它就是最小费用最大流；否则应继续调整。

应用：运输问题，如CMCM2000B钢管的采购和运输问题。

说明：

1．这里的介绍只是图论中的一部分内容，更多的需要我们进一步学习。

2．算法都是描述性的，有些可以找到现成的程序，但是最好是自己实现。

3．这里的例子只是解决问题的一种方法，不是唯一的方法。

4．注意实际应用中直接利用所给算法解决问题的情况很少，通常只是解决问题的一部分，而且需要建立模型，把实际问题用图论术语描述出来。所以要善于利用这里的工具。

其它方面的应用，如工序问题，最大独立集，最小覆盖集，邮递员问题，规划审核技术，关键轨道方法，可靠通信网络的构造问题，班级人员分配等等。

3．7 工序问题

统筹方法是组织生产计划的方法，它用网络图表达生产和工程的进度，计算各项工序的有关时间参数。

一项工程总是由许多相互独立的工序组成的，各道工序之间有一定的先后次序。完成每道工序

需要的时间（不妨设单位为小时）称为工序的长度。因此

我们可以用一个各条边有方向的图（称为有向图）表示各

项工序之间的互相依赖关系。以一条有向变来表示一道工

序，有向边的权即为此工序的长度，有向边的起点和终点

分别表示相应工序的开工和完工，称为事项，前接工序和

完工事项即为后续工序和开工事项。

实例：上海MCM91B

四、网络规划的应用

1．最小生成树——网络规划例1

例1．求下图的一个最小生成树。

解：首先取G1=（V1，E1），V1={v0}，E1=

其次，一端属于V1，一端不属于V1的最短边是v0v1，所以有

G2=（V2，E2），V2={v0，v1}，E2={v0v1}。

现在，一端属于V2，一端不属于V2的最短边是v1v3，所以有

G3=（V3，E3），V3={v0，v1，v3}，E3={v o v1，v1v3}。

类似做下去，最后得最小生成树的边为：

v0v1，v1v3，v2v3，v2v5，v5v6，v4v6。

2．存储粮食模型——网络规划例2

例2．某乡有七个村A1，A2，...，A7，需储存粮食数量分别为50，75，62，40，100，80，35吨。各村之间有公路连通，如图。现要选择某村建立仓库储存所有粮食，问应选择何处最好？

解：图上连结两村的边所注的数字表示该段公路的千米数。我们的目的是选择仓库的位置使运粮的吨千米数最小。首先比较A1和A2两处。在比较这两个村庄时，因为仓库无论建在A1或A2，其他各村的粮食都要先运到A2，所以我们可认为除A1外各村的粮食都集中在A2，共357吨。现在事情很明显，仓库建在A2时需把50吨粮食运3千米到A2，建在A1时需把357吨粮食运3千米到A1，所以A2较A1好。以后我们不再考虑A1，因此可把A1的粮食移到A2以简化问题。同理A5也不必考虑，它的粮食可集中到A4。

考虑其他五个村。我们猜想现在粮食数

量大的村庄可能是个好主意。假定选择A4，

我们考虑A6是否会更好：A2、A7的粮食

少运4千米，而A3、A4的粮食多运4千

米，可见A4较A6好。同理可证A4比其

他各村都好。因此仓库应建在A4。

3．工作顺序模型——网络规划例3

例3．某工厂的改造工程由下列7道工序组成：A：拆迁；B：工程设计；C：土建工程设计，前接工序为B；D：采购设备，前接工序为B；E：厂房土建，前接工序为A、C；F：设备安装，前接工序为D、E；G：设备调试，前接工序为F。那么我们可用图3.4表示这个工程，其中S表示整个工程的开工，t表示完工。有时，为了表示工序之间的顺序关系，需要引入虚工序。注意，用来表示工程进度的有向图是不允许有回路的。现在我们研究网络图的各种时间参数。

考虑图3.5表示的网络，我们把各事项（即图的顶

点）编号，一般要求每一工序的开工事项（即箭尾）的

编号少于完工事项的编号（即箭头）。每条有向边旁所

标数字为相应工序的长度。

某一工序A的最早开工时间t E (A)，表示该工序最

早可在整个工程开工后t E (A)小时开工，这时间仅与该

工序的开工事项有关，所以也可以说某一事项的最早时间t E (k)，例如图3.5中，事项4的最早时间是9（即工序1->4和2->4都完成的时间）。

因而有下列递推公式

[ik]表示起点为i，终点为k的有向边。整个工程完工事项的最早时间，就是全工程完工的最短时间，称为总工期，记为T E 。

某一工序的最迟完工时间（或该工序完工事项的最迟时间）t E (k)，是在不误总工期的条件下，该工序最迟应在整个工程开工后t L (A)小时完成。因此

实际上，t E (k)就是由事项1到事项k的最长路的长度。t L (k)就是T E 减去k到n的最长路的长度。因而（2）的第二式也可写成

工序[ij]的总时差定义为

即不误总工期的条件下该工序的开工时间的机动时间，即可延迟开工的时间；而工序[ij]的自由时差定义为

即在不误下道工序最早开工时间的前提下，该工序开工时间的机动时间。

从事项1到事项n的一条最长路称为网络图的一条关键路，显然在关键路上的每一事项k满足t L (k)=t E (k)，关键路上每一工序的总时差为0，反之亦然。显然，若关键路上工序能提前完成，整个工程才有可能提前完成；若关键路上工序未能按时完成，整个工程必然不能按期完成。

求总工期和关键路的方法如下：首先对所有t E (i)置初始值零，然后利用公式（1）进行迭代，直到所有的t E (i)不再改变，而自由时差为0的工序就是关键路上的工序。例如图3.5中网络图的总工期为28天，关键路为1->3->5->6->8。

4．求网络的最小费用最大流

求网络的最小费用最大流，弧旁的数字是容量(运费)。

一．Ford和Fulkerson迭加算法.

基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.

迭加算法：

设图中双线所示路径为最短路径，费用有向图为W（fij）．

1) 给定目标流量F或∞,给定最小费用的初始可行流{fij}=0

2) 若V(f)=F,停止,f为最小费用流;否则转(3).

3) 构造{fij}

相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加

流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.

在图(a)中给出零流f, 在图(b)中找到最小费用有向路,修改图(a)中的可行流,δ=min{4,3,5}=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d),

修改图(c)中的可行流, δ=min{1,1,2,2}=1,得图(e),以此类推,一直得到图(h),在图(h)中以无最小费用有向路,停止,经计算:

图(h)中最小费用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38

图(g)中最大流=5

二．圈算法：

具体解题步骤:

1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f.

2) 构造f对应的调整容量的流网络N'(f).

3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4).

4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).

利用Ford和Fulkson标号算法,得网络的最大流F=5,见图(a),由图(a)构造相应的调整容量的流网络(b),图(b)中不存在负费用有向图,故停止．经计算:

图(b)中最小费用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38

图(a)中最大流为F=5

附录一：Ford和Fulkerson迭加算法求网络的最小费用最大流问题的C语言程序/*Ford和Fulkerson迭加算法*/

#include"stdio.h"

void main()

{int a,b,i,j,k,p,n,B[10][10],C[10][10],D[10][10],P[10][10][10];

printf("please input n:\n");

scanf("%d",&n);

printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

scanf("%7d,%7d",&C[i][j],&B[i][j]); //输入各点(i,j)之间的容量C[i][j]和运费B[i][j] for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{D[i][j]=B[i][j];

for(k=0;k<=n;k++)

P[i][j][k]=0;

if(D[i][j]<100) //注：100表示Vi到Vj之间无可行路

{P[i][j][i]=1;P[i][j][j]=1;}

}

for(k=0;k<=n;k++)

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

if(D[i][k]+D[k][j]

{D[i][j]=D[i][k]+D[k][j];

for(p=0;p<=n;p++)

P[i][j][p]=P[i][k][p]||P[k][j][p];

} //调用FLOYD算法

printf("D[%d][%d]:\n",n,n);

for(i=0;i<=n;i++)

{for(j=0;j<=n;j++)

printf("%7d",D[i][j]);

printf("\n");

} //由表D中的数值确定V0到V5的最短路a=C[1][3];b=B[1][3]*D[0][5];

printf("a=%d,b=%d\n",a,b);

B[1][3]=100; //将容量已满的路改为不可行路for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{D[i][j]=B[i][j];

for(k=0;k<=n;k++)

P[i][j][k]=0;

if(D[i][j]<100)

{P[i][j][i]=1;P[i][j][j]=1;}

}

for(k=0;k<=n;k++)

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

if(D[i][k]+D[k][j]

{D[i][j]=D[i][k]+D[k][j];

for(p=0;p<=n;p++)

P[i][j][p]=P[i][k][p]||P[k][j][p];

} //调用FLOYD算法

printf("D[%d][%d]:\n",n,n);

for(i=0;i<=n;i++)

{for(j=0;j<=n;j++)

printf("%7d",D[i][j]);

printf("\n");

} //由表D中的数值确定V0到V5的新最短路a=a+C[1][2];b=b+D[0][5];

printf("a=%d,b=%d\n",a,b);

B[0][1]=100;B[1][2]=100;B[4][3]=100; //将容量已满的路改为不可行路for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{D[i][j]=B[i][j];

for(k=0;k<=n;k++)

P[i][j][k]=0;

if(D[i][j]<100)

{P[i][j][i]=1;P[i][j][j]=1;}

}

for(k=0;k<=n;k++)

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

if(D[i][k]+D[k][j]

{D[i][j]=D[i][k]+D[k][j];

for(p=0;p<=n;p++)

P[i][j][p]=P[i][k][p]||P[k][j][p];

} //调用FLOYD算法

printf("D[%d][%d]:\n",n,n);

for(i=0;i<=n;i++)

{for(j=0;j<=n;j++)

printf("%7d",D[i][j]);

printf("\n");

} //由表D中的数值确定V0到V5的新最短路

a=a+C[2][4]-C[4][3];b=b+D[0][5];

printf("a=%d,b=%d\n",a,b);

B[2][4]=100; //将容量已满的路改为不可行路

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{D[i][j]=B[i][j];

for(k=0;k<=n;k++)

P[i][j][k]=0;

if(D[i][j]<100)

{P[i][j][i]=1;P[i][j][j]=1;}

}

for(k=0;k<=n;k++)

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

if(D[i][k]+D[k][j]

{D[i][j]=D[i][k]+D[k][j];

for(p=0;p<=n;p++)

P[i][j][p]=P[i][k][p]||P[k][j][p];

} //调用FLOYD算法

printf("D[%d][%d]:\n",n,n);

for(i=0;i<=n;i++)

{for(j=0;j<=n;j++)

printf("%7d",D[i][j]);

printf("\n");

} //检验有无V0到V5的新最短路}

运行结果:

please input n:

5

please input C[5][5],B[5][5]:

0,0 4,1 5,3 0,100 0,100 0,100

0,100 0,0 1,1 3,3 0,100 0,100

0,100 0,100 0,0 0,100 2,4 0,100 0,100 0,100 0,100 0,0 0,100 5,2 0,100 0,100 0,100 1,1 0,0 2,4

0,100 0,100 0,100 0,100 0,100 0,0

D[5][5]:

0 1 2 4 6 6

100 0 1 3 5 5

100 100 0 5 4 7

100 100 100 0 100 2 100 100 100 1 0 3 100 100 100 100 100 0 a=3,b=18

D[5][5]:

0 1 2 7 6 9

100 0 1 6 5 8

100 100 0 5 4 7

100 100 100 0 100 2 100 100 100 1 0 3 100 100 100 100 100 0 a=4,b=27

D[5][5]:

0 100 3 100 7 11

100 0 100 100 100 100 100 100 0 100 4 8 100 100 100 0 100 2 100 100 100 100 0 4 100 100 100 100 100 0 a=5,b=38

D[5][5]:

0 100 3 100 100 100 100 0 100 100 100 100 100 100 0 100 100 100 100 100 100 0 100 2 100 100 100 100 0 4

100 100 100 100 100 0

//注：100表示Vi到Vj之间无可行路

附录二：破圈法求网络的最小费用最大流问题的C语言程序

/*圈算法*/

#include"stdio.h"

int min(int x,int y)

{if(x

else return(y);

}

void main()

{int

a=0,b=0,i,j,k,p,n,t,A[10][10],P[10][10],B[10][10],C[10][10],D[10][10];

printf("please input n:\n");

scanf("%d",&n);

printf("please input C[%d][%d],B[%d][%d]:\n",n,n,n,n);

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

scanf("%7d,%7d",&C[i][j],&B[i][j]); //输入各点(i,j)之间的容量C[i][j]和运费B[i][j] for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{A[i][j]=C[i][j];D[i][j]=0;P[i][j]=B[i][j];}

for(i=n;i>1;i--)

for(j=i-1;j>0;j--)

for(k=j-1;k>=0;k--)

if(A[j][i]!=0&&A[k][j]!=0)

D[k][j]=min(A[j][i],A[k][j]);

printf("D[%d][%d]:\n",n,n);

for(i=0;i<=n;i++)

{for(j=0;j<=n;j++)

printf("%7d",D[i][j]);

printf("\n");

}

for(i=0;i

for(j=i+1;j

for(k=j+1;k<=n;k++)

if(D[i][j]!=0&&D[j][k]!=0)

if(D[i][j]+D[j][k]==C[i][j])

{A[i][j]=0;A[j][k]=0;A[j-i][k-j]=0;

P[i][j]=100;P[j][k]=100;P[j-i][k-j]=0;

a=a+C[i][j];

b=b+B[i][j]*C[i][j]+B[j][k]*C[j][k]+B[j-i][k-j]*C[j-i][k-j]; for(p=k+1;p<=n;p++)

if(C[i][j]

{b=b+B[k][p]*C[i][j];

A[k][p]=C[k][p]-C[i][j];

}

for(p=k-j+1;p<=n;p++)

if(C[j-i][k-j]

{b=b+B[k-j][p]*C[j-i][k-j]+B[4][3]*C[4][3];

A[k-j][p]=C[k-j][p]-C[j-i][k-j];

}

A[4][3]=0;

}

printf("a=%d,b=%d\n",a,b);

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

D[i][j]=0;

for(i=n;i>1;i--)

for(j=i-1;j>0;j--)

for(k=j-1;k>=0;k--)

if(A[j][i]!=0&&A[k][j]!=0)

D[k][j]=min(A[j][i],A[k][j]);

数学建模竞赛中阅卷的问题

（数学建模B题） 数学建模竞赛阅卷中的问题 参赛队员：梁俊元（10044124，信息工程学院） 张育榕（10044139，信息工程学院） 余景荣（11044127，信息工程学院）参赛时间：2012年8月25 - 28日

承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D 中选择一项填写）：B 所属学校（请填写完整的全名）：南昌航空大学 参赛队员：1、梁俊源 2、张育榕 3、余景荣 日期：2012 年8月25日-28日

目录 1.摘要 -----------------------------------------4 2.关键词 ---------------------------------------4 3.问题重述 ---------------------------------------5 4.模型的条件和假设 ------------------------------5 5.符号说明 --------------------------------------5 6.问题的分析及模型的建立 ------------------------6 6.1问题一的分析与求解 -----------------------6 6.2问题二的分析与求解 -----------------------10 6.3问题三的分析与求解 -----------------------18 6.4问题死的求解 -----------------------------21 7.模型的评价 ------------------------------------23 8.参考文献 --------------------------------------23 9.附录 ------------------------------------------23

数学建模中的图论方法

数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。

数学建模笔记

数学模型按照不同的分类标准有许多种类: 1。按照模型的数学方法分，有几何模型，图论模型，微分方程模型.概率模型，最优控制模型,规划论模型,马氏链模型. ２。按模型的特征分,有静态模型和动态模型,确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型. 3.按模型的应用领域分,有人口模型,交通模型,经济模型，生态模型，资源模型。环境模型。 4.按建模的目的分,有预测模型，优化模型,决策模型，控制模型等。 ５.按对模型结构的了解程度分，有白箱模型,灰箱模型,黑箱模型。 数学建模的十大算法： 1.蒙特卡洛算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性,比较好用的算法。) 2.数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用matlａb作为工具。) 3.线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用lingｏ、linｇdo软件实现) 4.图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决，需要认真准备。) 5.动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6.最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法(这些问题时用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助,但是算法的实现比较困难，需谨慎使用） 7.网格算法和穷举法(当重点讨论模型本身而情史算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8.一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的,而计算机只认得是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。

《数学模型》

《数学模型》考试大纲 适应专业：数学与应用数学、信息与计算科学、统计学、应用统计学专业 一、课程性质与目的要求 数学模型课亦称为数学建模课，它是数学与应用数学、信息与计算科学、统计学、应用统计学专业必修课或限选课，教育部1998年颁布的高等学校本科专业目录中，把“数学模型”课作为数学类专业的必开课。数学模型是架于实际问题与数学理论之间的桥梁。数学模型就是应用数学语言和方法，对于现实世界中的实际问题进行抽象、简化和假设所得到的数学结构。本课程是研究数学建模的理论、思想和方法，研究建立数学模型、简单的优化模型、数学规划模型、微分方程模型、代数方程与差分方程模型、稳定性模型、离散模型、概率模型等。 数学模型课需要用到数学分析、高等代数、微分方程、图论、概率统计、运筹学等数学知识，它是学生所学数学知识的综合应用，是培养学生综合素质以及应用数学知识解决实际问题的能力的良好课程。该课程的考试评价依据是按照课程目标、教学内容和要求，把握合适的难易程度出试卷，用笔试的方法对学生学习情况和学习成绩做出评价。 二、课程内容和考核要求 第一章建立数学模型 １、考核知识点： 数学建模的背景及重要意义、数学模型与数学建模、数学模型的分类与特点、数学建模的基本方法和步骤、数学建模举例等。 ２、考核要求： （1）理解数学建模的背景及意义、原型、模型、数学模型、数学建模等概念。 （2）理解数学模型的各种分类、数学模型的特点。 （3）理解数学建模的基本方法和步骤、通过实例初步了解数学建模的思想和方法。 第二章简单的优化模型 １、考核知识点： 存储模型、生猪的出售时机、森林救火、冰山运输等。

２、考核要求： （1）掌握应用微积分理论建立存储问题模型。 （2）理解应用微积分理论建立生猪的出售时机模型和森林灭火模型。 （3）理解应用微积分理论建立冰山运输问题模型。 第三章数学规划模型 １、考核知识点： 数学规划问题的基本概念、数学规划问题图解法步骤、生产安排问题、奶制品的生产与销售等。 ２、考核要求： （1）掌握数学规划问题的基本概念、数学规划问题图解法步骤。 （2）掌握生产安排问题的模型及图解法。 （3）理解奶制品的生产与销售的模型及求解。 第四章微分方程模型 １、考核知识点： 传染病模型、正规战与游击战、药物在体内的分布与排除、香烟过滤嘴的作用等。 ２、考核要求： （1）理解传染病问题的建模及讨论。 （2）理解战争问题、房室问题的建模及讨论。 （3）了解香烟过滤嘴作用问题的建模及讨论。 第五章代数方程与差分方程模型 １、考核知识点： 量纲、量纲齐次原理、量纲分析法、差分方程的基本概念、市场经济中蛛网模型、节食与运动问题等。 ２、考核要求： （1）掌握量纲、量纲齐次原理、量纲分析法建模及解法步骤。 （2）掌握市场经济中蛛网模型及解法步骤。 （3）理解理解差分方程的基本概念、减肥问题的建模思想。 第六章稳定性模型

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

数学建模常用的十大算法==转 (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 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的

数学建模模拟题,图论,回归模型,聚类分析,因子分析等 (83)

二十一章第三题 摘要 建立目标规划模型，先找出目标函数和约束条件，然后建立模型，利用Lingo程序求解。 关键词：Lingo 目标规划

Ⅰ 问题重述 某工厂生产两种产品,每件产品I 可获利10元，每件产品II 可获利8元。每生产一件产品I ，需要3小时；每生产一件产品II ，需要2.5小时。每周总的有效时间为120小时。若加班生产，则每件产品I 的利润降低1.5元；每件产品II 的利润降低1元。决策者希望在允许的工作及加班时间内取得最大利润，试建立该问题的目标规划模型并求解 Ⅱ 问题分析 建立目标规划模型前，先找出目标函数和约束条件，然后建立模型，利用Lingo 程序求解。 由题可知，无论生产产品Ⅰ或Ⅱ每小时的盈利不超过4元，每周的生产时间不超过160小时，因而最大利润不超过640。 Ⅲ 模型假设 （1） 生产过程中没有出现其他问题； Ⅳ 符号说明 （1）1x 为产品I 在允许的时间内生产的件数； （2）2x 为产品 在允许的时间内生产的件数； （3）3x 为产品I 在加班的时间内生产的件数； （4）4x 为产品 在加班的时间内生产的件数。 Ⅴ 模型建立与求解 () ---++=32211min d p d d p z ???????=≥=≥=++++=++++=++----.4,3,2,10;3,2,1,0, 64075.8810,1605.235.23,1205.23..3432124321121i x i d d x x x x d x x x x d x x t s i i 且为整数， 利用LINGO 编写程序（见附录） 求得1x =40 2x =0 3x =10 4x =4 d -1=0 d -2=0 d - 3 =1即产品I 生产50件，产品II 生产4件时，总的利润最大，最大利润为413元。

数学建模模拟题,图论,回归模型,聚类分析,因子分析等 (48)

第11章第2题 摘要 本题分析4 种化肥和3 个小麦品种对小麦产量的影响，以及二者交互作用对小麦产量的影响，可视为两因素方差分析，即化肥和小麦品种两个因素，4种化肥可看作是化肥的四个不同水平，3个小麦品种也可以看作是小麦品种的三个不同水平。 试验的目的是分析化肥的四个不同水平以及小麦品种的三个不同水平对小麦产量有无显着性影响。 关键词：方差分析显着性化肥种类小麦品种

一．问题重述 为了分析4 种化肥和3 个小麦品种对小麦产量的影响，把一块试验田等分成36个小块，分别对3种种子和四种化肥的每一种组合种植3 小块田，产量如表1所示（单位公斤），问不同品种、不同种类的化肥及二者的交互作用对小麦产量有无显着影响。 二．问题分析 本题意在分析四种化肥和三种小麦品种对小麦产量的影响，以及二者交互作用对小麦产量的影响，为两因素方差分析问题，即化肥和小麦品种两个因素，4种化肥可看作是化肥的四个不同水平，3个小麦品种也可以看作是小麦品种的三个不同水平。通过对这两种因素的不同水平及交互作用的分析，从而分析 4 种化肥和3 个小麦品种对小麦产量的影响。 三．模型假设 1.假设只有化肥种类和小麦品种两个因素，其他因素对试验结果不构成影响。 2.假设不存在数据记录错误。 3.假设每一块试验田本身各项指标相同，不会影响结果。 四．符号说明 数字1,2,3,4——不同的化肥种类 数字1,2,3——不同的小麦品种 五．模型建立 将化肥种类和小麦品种视为两个因素，四种化肥种类看作是化肥种类的四个不同水平，三个小麦品种看作是小麦品种的三个不同水平，将表1的数据进行整理，如表2所示。

六．模型求解 将表2数据导入到spss软件中，进行两因素方差检验，得到结果如下：表3

数学建模常见问题

1 预测模块：灰色预测、时间序列预测、神经网络预测、曲线拟合（线性回归）； 2 归类判别：欧氏距离判别、fisher判别等； 3 图论：最短路径求法； 4 最优化：列方程组用lindo 或lingo软件解； 5 其他方法：层次分析法马尔可夫链主成分析法等； 6 用到软件：matlab lindo （lingo）excel ； 7 比赛前写几篇数模论文。 这是每年参赛的赛提以及获奖作品的解法，你自己估量着吧…… 赛题解法 93A非线性交调的频率设计拟合、规划 93B足球队排名图论、层次分析、整数规划 94A逢山开路图论、插值、动态规划 94B锁具装箱问题图论、组合数学 95A飞行管理问题非线性规划、线性规划 95B天车与冶炼炉的作业调度动态规划、排队论、图论 96A最优捕鱼策略微分方程、优化 96B节水洗衣机非线性规划 97A零件的参数设计非线性规划 97B截断切割的最优排列随机模拟、图论 98A一类投资组合问题多目标优化、非线性规划 98B灾情巡视的最佳路线图论、组合优化 99A自动化车床管理随机优化、计算机模拟 99B钻井布局0-1规划、图论 00A DNA序列分类模式识别、Fisher判别、人工神经网络 00B钢管订购和运输组合优化、运输问题 01A血管三维重建曲线拟合、曲面重建 01B 工交车调度问题多目标规划 02A车灯线光源的优化非线性规划 02B彩票问题单目标决策 03A SARS的传播微分方程、差分方程 03B 露天矿生产的车辆安排整数规划、运输问题 04A奥运会临时超市网点设计统计分析、数据处理、优化 04B电力市场的输电阻塞管理数据拟合、优化 05A长江水质的评价和预测预测评价、数据处理 05B DVD在线租赁随机规划、整数规划

数学建模应该注意问题

一．关于参赛时间分配，竞赛共72个小时完成。 下题：今年是9月11日早上8：00在https://www.doczj.com/doc/1418368976.html,下载，9月14日早8：00交试题。 选题：这三天的时间按排基本如下：11日8：00-15：00左右选题，选题分为粗选，细选。粗选就是直观的看这两道题是否平时练习相关问题或方法的，选题要对每试题的每一问都要认真分析，大至看看基本能用哪些方法，做到心中有数，对两道题都分析后在选择自已能够容易完成的一题去做。选题的过程中要去查资料、找数据、看论文，通过这些工作，你可以发现找到的东西能否够解决你选的题。 做题：11日15点-13日22点左右。从第一天下午开始去做题，做题的过程分为问题分析，数据处理，模型建立，模型求解等，一会在下边要专门讨论。 换题：如果选题后做一些后其它问题不好处理，或者没有办法处理，有人就会想到换题，当然尽可能的不要换题，要是换题一定不能晚于11日20:00,否则就有做不完题的可能。当然也因人而宜。 写论文：最迟要在13日22：00开始，到14日凌晨5：00写完，尽可能让指导教师帮着修改。7：00打印，打印好后要仔细看一遍，有问题在修改。8：00交论文。写论文的过程贯穿于选题做题过程之中，我们在选题做题时就把做的一些东西分别处理好，只是这说的写论文就是把所做的题目的不同问题，不同部分都贯穿在一起，形成一篇有血有肉的论文。论文写作应该专门有一人在做题的过程中进行。 二、关于写论文 1.正确的论文格式： 论文属于科学性的文章，它有严格的书写格式规范，因此一篇好的论文一定要有正确的格式，就拿摘要来说吧，它要包括6 要素（问题,方法,模型,算法,结论,特色），它是一篇论文的概括，摘要的好坏将决定你的论文是否吸引评委的目光，但听阅卷老师说，有些论文的摘要里出现了大量的图表和程序，这都是不符合论文格式的，这种论文也不会取得好成绩，因此我们写论文时要端正态度，注意书写格式。 2、论文的写作： 论文的写作是至关重要的，其实大家最后的模型和结果都差不多，为什么有些队可以送全国，有些队可以拿省奖，而有些队却什么都拿不到，这关键在于论文的写作上面。一篇好的论文首先读上去便使人感到逻辑清晰，有条例性，能打动评委；其次，论文在语言上的表述也很重要，要注意用词的准确性；另外，一篇好的论文应有闪光点，有自己的特色，有自己的想法和思考在里面，总之，论文写作的好坏将直接影响到成绩的优劣。

数学建模中竞赛阅读中的问题

数学建模中竞赛阅读中的问题 摘要 本文主要研究的是数学建模竞赛中试卷的优化配发，评分的标准化处理及对教师的评阅效果定量评价的问题． 问题一：针对试卷的随机分发问题，先利用MATLAB软件自带的randperm 函数产生一个1至500的随机矩阵，再用reshape函数对其进行重新排列成25行20列的矩阵，对矩阵y进行列列交换的变化成两个新矩阵y1与y2，构成75行20列的新矩阵z=[]2 ,1 y y，从而实现对试卷的随机分发；针对均匀性问题， ,y 以交叉数的方差作为评价任务单均匀性的评定指标，从多个随机分配方案中，选取交叉数方差最小的任务单供组委会使用． 问题二：评分的预处理需要对评阅教师的分数进行标准化，评分预处理方法是将不同的评分者变换到同一个尺度下，就是以某一位评分者的均值作为参照点，以其标准差表示距离转化为以零为参照点的标准分；然后采用均值为70标准差为10将标准分转化为百分制的标准，分这样使得标准分与原始分相差不大；最后将同一份试卷的三个标准评分的几何平均值作为该份试卷的最终标准分．将附录中的200份试卷的数据根据用Excel软件的统计与函数功能最终得到各份试卷的标准分值． 问题三：针对教师评阅效果的评价问题，本文给出两个评价标准：分别是评阅的原始成绩的可信度和评阅的原始成绩与成绩标准化合成后的最终成绩的偏差值的稳定性．对于可信度，结合评分分制，对评阅的原始成绩与成绩标准化合成后的最终成绩的差分值做百分化处理，建立可信度数学模型，得出可信度最高的有10，11，15，19，20号教师，高达96%；对于偏差值的稳定性，采用偏差值的方差来反映，得出稳定性最好的是第3号教师，稳定性较好的还有第1，7，10，11，19号教师．最后，综合可信度和偏差值的稳定性两项指标，得出评阅效果较好的教师有第1，3，10，11，15，19，20号教师，在下一次阅卷后合成成绩的时候可以考虑给他们以更大的权重． 关键词：随机数矩阵标准化参照点可信度偏差值

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

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

关于数学建模竞赛的一点思考总结和建议

关于数学建模竞赛的一点思考、总结和建议 关于数学建模竞赛的一点思考、总结和建议 宋一凡 环境保护与安全工程学院核安全工程专业 大学生活即将结束，回顾几年的经历，数学建模竞赛留给我太多的回忆。虽然数模竞赛已经远去，但至今看到听到“三天三夜72小时”时，精神还会为之一振。在要告别数模竞赛的时候，想写一点自己零零碎碎的思考和总结，并给以后参赛的学弟学妹一点建议。 1. 关于我的数模之路 大一从学长口中知道了数模竞赛，就想参加，自学了姜启源的《数学模型》，但校赛时，队友不给力使第一次校赛不了了之，至今仍然遗憾大一时校赛未能入围；大二时，和本院的两个同学组队，比我高一级的闯哥给了不少经验和资料，经过暑假的培训和多次模拟赛训练，12年国赛拿到了湖南赛区的三等奖。 13年寒假，留在学校参加美赛，偌大的宿舍楼空无一人，好不凄凉，南方湿冷的冬天让我这个北方人冻得难以忍受，搞完比赛回到家时已经是腊月二十七夜里，美赛S奖使我很失落，也从中找到了自己的很多不足之处。 因今年考研，本不愿参加国赛，但两位新队友的盛情邀请让我不忍拒绝，于是重新组队，再战国赛，一雪前耻，最后拿到国家一等奖，为大学的数模之路画上一个圆满的句号。 从大一到现在，关于数模的比赛，热身赛、校赛、模拟赛、国赛、美赛，大大小小不记得参加过多少次，也不知道熬过了多少个“72小时”。建模、程序员、写手，三个角色的工作我都认认真真做过，饱尝里面的酸甜苦辣，一步一个脚印走来，最后得到一个不错的成绩，收获颇多，感触颇深。 数模给我打开了一扇窗，窗外的世界带给我不一样的精彩，而不仅仅是拿几张证书，加几分综测。外人看来，数模痛苦、费人，而我感觉数模自由、快乐。尤其是竞赛结束，早上八点交卷的时刻，经过三天三夜的努力，队友通力合作，从第一天的一筹莫展，到最后一天的顺利解决，疲惫、兴奋、满足、急切、不安，很多的感受一时涌上心头，那是只有真正参加比赛的人才能体会到的快乐！ 2. 关于数学建模竞赛的作用 在做一件事情之前总会去思考做成这件事情有什么好处，这样的心里再正常不过了。而数模竞赛这种需要投入很多时间和精力的事情，更需要好好决定下是否要参加。指导老师说：数模“费时间，强意志，提能力”，我以自己的经历来讲下数模竞赛的作用。 2.1 对自身能力的提高 参加数模竞赛可以提高自身能力，这一点是毋庸置疑的，全国数模竞赛组委会的网站上都有写“一次参赛，终生受益”。可能一两次的比赛看不出来，经过多次竞赛的锻炼，与没有经过

数学竞赛中的图论问题

数学竞赛中的图论问题

分类号密级 U D C 编号 本科毕业论文(设计) 题目数学竞赛中的图论问题 所在院系数学与数量经济学院 专业名称数学与应用数学 年级 08级 学生姓名李曼 学号 0850410013 指导教师孙静

二 0一二年三月 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担. 作者：

日期：2012年3月29日 文献综述 一综述 在18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题就是著名的哥尼斯堡七桥问题，即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后，欧拉发表了著名的论文《依据集合位置的阶梯方法》，这是图论领域的第一篇论文，标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科. 图论极有趣味性，严格来讲，它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理等. 总的来说，图论这门科学具有以下特点：（1）图论蕴含了丰富的思想、漂亮的图形和巧妙的证明； （2）涉及的问题多且广泛，问题表明上简单朴素，本质上却十分深刻复杂； （3）解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.

关于数学建模的几个问题

数学建模应该注意的一些事项 一、序 数学建模比赛已经成为当今各个高校每年必参加的活动。要想在比赛中取得比较好的成绩，尤其是在全国赛中取得好成绩经验第一，运气第二，实力第三，这种说法是功利了点，但是在现在中国这种科研浮躁的大环境中要在全国赛中取得好成绩经验是首要的。全国赛注重“稳”，与参考答案越接近，文章通顺就可以有好成绩了，在数模竞赛中经验会告诉我们该怎么选题，怎么安排时间，怎么控制进度，知道什么是最重要的，该怎么写论文......，或许有人会认为选题也需要经验吗？选题是有技巧的，选个好题成功的机会就大的多，选题不能一味的根据自己的兴趣或能力去选，还要和全体参赛队互动下，不大容易做到，只能是在极小的范围内做到，分析下选这个题的利弊后决定选哪个题，这里面学问也不少。希望自己总结的一些经验能帮助大家能尽快的成长，尽快的发挥自己的能力，体验数学在应用中的作用，爱上数学，甚至和数学打一辈子交道。 二、组队和分工 数学建模竞赛是三个人的活动，参加竞赛首要是要组队，而怎么样组队是有讲究的。此外还需要分工等等一般的组队情况是和同学组队，很多情况是三个人都是同一系，同一专业以及一个班的，这样的组队是不合理的。让三人一组参赛一是为了培养合作精神，其实更为重要的原因是这项工作需要多人合作，因为人不是万能的，掌握知识不是全面的，当然不排除有这样的牛人存在，事实上也是存在的，什么都会，竞赛可以一个人独立搞定。但既然允许三个人组队，有人帮忙总是好的，至少不会太累。而三个人同系同专业甚至同班的话大家的专业知识一样，如果碰上专业知识以外的背景那会比较麻烦的。所以如果是不同专业组队则有利的多。众所周知，数学建模特别需要数学和计算机的能力，所以在组队的时候需要优先考虑队中有这方面才能的人，根据现在的大学专业培养信息与计算科学，应用数学专业的较为有利，尤其是信息与计算科学可以说是数学和计算机专业的结合，两方面都有兼顾，虽然说这个专业的出路不是很好，数学和计算机都涉及点但是都没有真正的学通这两门专业的，但对于弄数学建模来说是再合适不过了。应用数学则偏重于数，但是一般来讲玩计算机的时

数学建模图论

图论 一．最短路问题 问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 将问题抽象为赋权有向图或无向图G ，边上的权均非负 对每个顶点定义两个标记（()l v ，()z v ），其中： ()l v ：表示从顶点到v 的一条路的权 ()z v ：v 的父亲点，用以确定最短路的路线 S ：具有永久标号的顶点集 1.1Dijkstra 算法：即在每一步改进这两个标记，使最终()l v 为最短路的权 输入：G 的带权邻接矩阵(,)w u v 步骤： （1） 赋初值：令0()0l u =，对0v u ≠，令 ()l v =∞，0={u }S ，0i = 。 （2） 对每个(\)i i i v S S V S ∈= （即不属于上 面S 集合的点），用min{(),()()}i u S l v l u w uv ∈+ 代替()l v ，这里()w uv 表示顶点u 和v 之间边的权值。计算min{()}i u S l v ∈，把达到这个最小值的一个顶点记为1i u +，令11{}i i i S S u ++=?。 （3） 若1i V =-，则停止；若1i V <-，则 用1i +代替i ，转（2） 算法结束时，从0u 到各顶点v 的距离由v 的最后一次编号()l v 给出。在v 进入i S 之前的编号()l v 叫T 标号，v 进入i S 之后的编号()l v 叫P 标号。算法就是不断修改各顶点的T 标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各顶点的最短路也在图上标示出来了。 理解：贪心算法。选定初始点放在一个集合里，此时权值为0初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。然后以新纳入的点为起点继续搜索，直到所有的点遍历。

数学建模优秀赛题-图论的相关赛题

数学建模图论问题 B题灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行 驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 3.在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少； 给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.若巡视组数已定(如三组)，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线 的影响。 B题：乘公交，看奥运 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)：3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)

数学建模图论

数学建模图论 Document number：WTWYT-WYWY-BTGTT-YTTYU-2018GT

图论 一．最短路问题 问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 将问题抽象为赋权有向图或无向图G ，边上的权均非负 对每个顶点定义两个标记（()l v ，()z v ），其中： ()l v ：表示从顶点到v 的一条路的权 ()z v ：v 的父亲点，用以确定最短路的路线 S ：具有永久标号的顶点集 算法：即在每一步改进这两个标记，使最终()l v 为最短路的权 输入：G 的带权邻接矩阵(,)w u v 步骤： （1） 赋初值：令0()0l u =，对0v u ≠， 令()l v =∞，0={u }S ，0i =。 （2） 对每个(\)i i i v S S V S ∈=（即不属 于上面S 集合的点），用min{(),()()}i u S l v l u w uv ∈+代替()l v ，这里()w uv 表示顶点u 和v 之间边的权值。计算min{()}i u S l v ∈，把达到这个最小值的一个顶点记为1i u +，令11{}i i i S S u ++=?。 （3） 若1i V =-，则停止；若 1i V <-，则用1i +代替i ，转（2） 算法结束时，从0u 到各顶点v 的距离由v 的最后一次编号()l v 给出。在v 进入i S 之前的编号()l v 叫T 标号，v 进入i S 之后的编号()l v 叫P 标号。算法就是不断修改各顶点的T 标号，直至获得P 标号。若在算法运行过程中，将

高中竞赛数学讲义第68讲图论问题(二)

第68讲图论问题(二) 本讲主要内容：本讲将继续研究用图来解决问题的方法． 偶图取图G＝(V，E)，如果V＝X∪Y，X∩Y＝，其中X＝{x1，x2，…，x n}，Y＝{y1，y2，…，y m}，且x i及x j(1≤i＜j≤n)，y s 及y t (1≤s＜t≤m)均互不相邻，则称G为偶图． 色数：将图G的顶点涂上颜色，如果至少要k种颜色才能使任意两个相邻的顶点颜色不同，则称G的色数为k．显然，偶图的色数≤2．即偶图色数不超过2． A类例题 例1 在空间中给定2n个不同的点A1，A2，…，A2n，n＞1，其中任意三点不共线．设M是n2+1条以给定的点为端点的线段的集合．⑴证明：存在一个三角形，其顶点为给定的点，其边都属于M．⑵证明：若集合M的元素不超过n2个，则这样的三角形可能不存在．(1973年奥地利数学竞赛) 分析可以从简单的情况开始试验，发现规律再证明．从K4(4阶完全图，见67讲)共有多少条线及多少个三角形、擦去1条线去掉几个三角形入手得出结论，对于K5、K6也能用此法得到结论，但对于p＞6，K p难用此法，如何过渡到一般情况？可以用数学归纳法． 证明：n＝2时，在4个点间连了5条线，由于4阶完全图在4个点间共可连出6条线，这6 v 3v 4 v 3 2k

条线连出了4个以此4点中的某3点为顶点的三角形．而每条线的两个端点及(除这条线的两个端点外的)另两个顶点可以连出共2个三角形，故去掉任何一条边都使连出三角形数减少2，于是在4个点间连5条线必连出了以此4点中的3点为顶点的三角形．设n＝k时，2k个点间连有k2＋1条线时，必有三角形出现．则当n＝k＋1时，2(k＋1)个点间连了(k＋1)2＋1条线．此时，任取两个相邻的顶点v1，v2，如果在其余的顶点中有某个顶点及v1，v2都连了线，例如v3及v1，v2都连了线(图4(1))，则出现了三角形．如果其余所有的点及此二点都至多连出1条线(图4(2))，则去掉点v1，v2及及这两点相邻的边，此时，余下2k个点，至多去掉了2k ＋1条边，余下至少(k＋1)2＋1－(2k＋1)＝k2＋1条边，由归纳假设知，其中必有三角形． 综上可知，命题成立． 说明若2n个点间连了n2条边，可以把这2n个点分成两组，每组n个点，规定同组的点间都不连线，不同组的任何两点都连1条线，这样得到了一个完全偶图K n，n，此时共计连了n2条线，但任取三点，必有两点在同一组，它们之间没有连线，于是不出现三角形． 例2 一个舞会有n(n≥2)个男生及n个女生参加，每个男生都及一些女生(不是全部)跳过舞，而每个女生都至少及1名男生跳过舞，证明，存在男生b1，b2及女生g1，g2，其中b1及g1跳过舞，b2及g2跳过舞．但b1及g2没有跳过舞，b2及g1没有跳过舞．

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

数学建模中常见的十大 模型 集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。

8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。