凯恩斯选美的图论模型及其进化算法.李拉亚

凯恩斯选美的图论模型及其进化算法1

李拉亚

华侨大学数量经济研究院

【摘要】本文中，我们用图论方法分析凯恩斯选美。我们发现凯恩斯选美的从众原则可归结为图上的最长路径问题，并设计了一种能同步得出图上所有最长路径的进化算法。

我们还提出了改进算法有效性的方法和存在Hamiltonian圈的一个新的充分必要条件，由此分析了凯恩斯选美的复杂行为。

关键词：凯恩斯选美，从众行为，算法，最长路径，Hamiltonian圈

中图分类号 F0 文献标识码 A

The Graph Model of Keynesian Beauty Contest and its

Evolutionary Algorithm

Abstract: In this paper, we use graph theory to analyze Keynesian beauty contest. We find that the conformity principle of Keynesian beauty contest is equal to find the longest path in a graph. We also design an evolutionary algorithm that can find all longest paths in a graph synchronously.

We present methods of our improving performance of the algorithm. We also present a new sufficient and necessary condition of Hamiltonian cycles. Based on these methods and this new condition, we analyze the complicated behavior of Keynesian beauty contest.

Key words: Keynesian beauty contest, Conformity behavior, Algorithm, Longest path, Hamiltonian cycle

一、导言

从众行为指群体中个体行为追随群体中大多数个体的行为。在自然界中，我们会发现许多动物具有从众行为的本能。这种普遍存在的现象表示其存在的合理性，它有助于群体的生存，是动物漫长进化过程中优胜劣淘的结果。

在经济社会的一些场合，经济人也具有从众行为。《就业利息和货币通论》第12章《长期预期状态》第五节的凯恩斯选美比喻便是一种典型的从众行为。凯恩斯指出：“或者，上述比喻稍有改变，专业投资好比报纸上的选美比赛。比赛中，评选人在100张照片中挑选出6个最美者。谁的选择结果与全体评选人平均爱好最接近，奖就授予谁。因此，每个评选人不选择他自己认为的最美者，而是选择那些他认为最可能是其他评选人挑选的最美者。而所

有其他评选人也都用同样观点，不选择自己真认为的最美者，也不选一般人真认为的最美者。我们已进入第三阶段，我们用自己的智慧去预期一般人预期一般人认为的最美者。还有一些人，我相信，他们将到达第四，第五和更高的阶段。”

凯恩斯选美的本质思想是，个体选择追随群体中大多数人的选择。决定选择的关键因素是持某种选择的人数多少，而不是这个选择本身正确与否。凯恩斯选美的关键问题是，群体中大多数人的共同选择是怎样形成的。

实验经济学家设计了一种猜数游戏，用于探索凯恩斯选美中理性人的行为。如

Nagel(1995)、Stahl(1996)和Ho等人(1998)提出的实验经济学案例，要求群体中每个人写下1到100间的一个数字，要求这个数字是大家所写下数字平均数再乘以p值(p小于1大于0，如p为2/3)。他们假定每一个人均认为自己会比其他人提前考虑下一阶段的情况。在第一阶段，每人均随机选择一个数，如均值50。第二阶段，每个人认为既然其他人在第一阶段选50，那么自己就选50p。如此类推，第k阶段，大家选50p k-1。这样，最终选值趋于0。类似方法还可见Moulin(1986)、Bosch-Domenech等人(2002)的实验分析。

计算机算法中的一致算法可特别用于研究网络上所用点的状态收敛到一个一致值。该算法只要求网络上的每一点与自己相邻的点交流信息，通过一定的控制条件，达到全局的控制目标。Schmalz, Fujita和Sawodny(2009)以一致算法为基础，设计了一种新算法分析金融市场的泡沫行为等，其中也涉及到从众行为问题。

上述两种方法，凯恩斯选美结果均收敛到一个值。这样，凯恩斯选美没有反映其比喻的金融市场的复杂性。本文中，我们以图论为基础，以算法为手段，研究凯恩斯选美的复杂性。我们方法关于凯恩斯选美结果的唯一性和多样性，关于为提高算法的有效性而产生的凯恩斯选美结果的不确定性，关于凯恩斯选美特征与混沌系统特征类似等内容，反映了凯恩斯选美的复杂性，故也反映了凯恩斯选美比喻的金融市场的复杂性。

本文分六节。第一节是导言。第六节是总结。本文的主要贡献：第二节提出了凯恩斯选美的从众原则可视为图上的最长路径算法；第三节设计了一种能同步得出所有最长路径的进化算法；第四节解释了算法有效性与相关经济学思想的联系；第五节给出了存在Hamiltonian圈的新充分必要条件，由此解释了凯恩斯选美对图形结构的敏感性及其对初始淘汰条件的敏感性和不确定性，比较了凯恩斯选美特征与混沌系统特征，揭示了凯恩斯选美的复杂性。

二、凯恩斯选美的图论模型

1.关系图定义

设在一经济系统中存在N个经济人。如果每个人视为一个点，两点之间的边表示这两个人相识。这样，这N个人和他们之间的相识关系就构成一个图，称之为关系图。关系图是每边长度均为一的无向单纯图。无向指边没有方向。单纯图指图中不存在起于一个点又回到这个点的边，并且两点之间最多只存在一条边。本文说的图，均指这样定义的关系图。

2

图1是一关系图。我们用v00, v01, v02, ……, v19分别表示图1的20个点。这20个点代表20个人。两点之间的边表示这两个人相识。在图1中，每个人均只认识三个人。因之，每个点均只有三条边。

图 1

2.从众原则的最长路径法

我们可以把凯恩斯选美看作是评选人推销自己选美结果的竞赛。每个评选人均努力推销自己的选美结果。

前面介绍的实验经济学方案的假设不能用电话、电视、广告、集会等方法，并且人们之间没有交流，每个人均是孤立的，每个人只能猜别人下一步的行为，每一个人还均认为自己会比其他人提前考虑下一阶段的情况。我们的方法可视为一种计算机实验方法，也假设评选人不能用电话、电视、广告、集会等方法，只能在关系图上从某一位置出发，一个点一个点推销自己的选美结果，并每人说服别人接受自己的选美结果的能力是一样的。每一位评选人最终只能选择一种选美结果。

依据图论知识，在相同时间内，通过图上尽可能多的点一次并仅一次的评选人的选美结果，其效率最高，影响的人数也最多。依据凯恩斯选美从众原则，影响人数最多的选美结果将成为大多数人的选美结果或群体的共同选美结果。这一方法相当于在图上找出最长路径。

我们把评选人分成两类。一类是公众。他们知识较少，只能从自己在关系图中的位置出发，随机选择下一个要走的点。绝大多数人属于这一类。另一类是专家。他们拥有更多知识，知道关系图结构和可能的最长路径，能依据最长路径选择要走的点及其顺序，依次说服别人接

3

受自己的选美结果。推销选美结果的竞赛刚开始时，每个人并不知谁能影响更多的人，因此，他要预期别人的选择，还要预期别人预期别人的选择，即作高阶预期。通过一段时期后，他会识别出影响人数多的专家。依据从众原则，公众会采纳影响人数最多的专家的选美结果。

3.选美结果唯一性或多样性

我们知道，当图存在Hamiltonian路径(即通过图上每一点一次并仅一次的路径)时，图上最长的路径是Hamiltonian路径。如果Hamiltonian路径两端的点是相邻点，那么这个路径是Hamiltonian圈。

如果图上仅存在一条最长路径，则存在一个选美结果。存在多个相同长度的最长路径，则存在多个可能的选美结果。

如果存在一个Hamiltonian圈，因为每个评选人都能处在一条Hamiltonian路径的起点上，则至少每个专家的选美结果都能影响到全体评选人，这导致选美结果的分散化。

三、最长路径的进化算法

1.基本概念

简单路径：一个简单路径指路径上的所有点是不相同的。换言之，简单路径不包含圈。

相邻路径：如果两个简单路径有且仅有一个相同的点，并且这个点是端点(端点指路径最两边的点)，那么这两条路径称之为相邻路径。换言之，相邻路径相连不相交。

种群：本文中，种群是一个集合，它的元素由简单路径构成。每一代种群的简单路径具有相同的点数和边数。图中的所有边构成第一代种群p(0)。

合并：如果两个简单路径相邻，我们合并这两个简单路径得到一个新的简单路径。如在图1中，我们合并简单路径v00v01v02和简单路径v02v03v04，得到新的简单路径

v00v01v02v03v04。我们的合并运算是一般进化算法的杂交或交叉运算。

2.计算过程

我们的算法存在两个过程：倍增过程和扩展过程。我们由倍增过程开始。

在倍增过程中，合并种群p(i)中的所有两两相邻的简单路径，由此得到的所有新的简单路径构成新的种群p(i+1)。

倍增过程形成新种群的元素所包含的点数不能大于图的点数，如果下一步这种情况会发生，进入扩展过程。当得到的新种群为空时，则退回到上一步，进入扩展过程。

4

在扩展过程中，我们有两个种群。一个是新种群。另一个是以前产生的旧种群中的一个。合并这两个种群中所有相邻的简单路径时，要求其中一个简单路径来自于新种群，而另一个简单路径来自于被选择的旧种群。由此得到的所有新的简单路径构成新种群。

在扩展过程中，每一被选择的旧种群最多只能使用一次，并且元素长度大的旧种群被优先选择，但形成新种群的元素所包含的点数不能大于图的点数。如果某一步形成新种群为空，则退回到上一步，挑选下一个旧种群。此过程直到p(0)被挑选或者新种群的任一元素所包含的点数等于图的点数为止。

如果求得的最长路径为Hamiltonian路径，我们便可从中寻找Hamiltonian圈。

我们看到，在倍增过程中，新种群的元素是上一种群的所有相邻元素合并而成。在扩展过程中，新种群的元素是由分别来自上一种群和一旧种群的所有相邻元素合并而成。因之，每一不为空的新种群包含了图上与新种群元素长度相同的所有简单路径。故我们的算法能得到图上所有的最长路径。因此，凯恩斯选美最终结果是可预测的。

3.计算过程结果

我们用上述进化算法对图1进行运算，计算过程的结果由表1描述。Hamiltonian路径长度19可用2的指数表示，即为24 + 21 + 20。由此可预先猜测图中存在Hamiltonian路径时，倍增过程的迭代次数和扩展过程中旧种群被依次使用的情况。

表1

四、算法有效性及相关经济学思想

1.算法有效性

我们把算法完成任务所需计算次数用图的点数的函数表示，如果该函数是多项式函数，该算法是有效的。如果该函数是指数函数，该算法是无效的。

目前，科学界尚未找到寻找最长路径的有效算法。我们算法虽是无效的，但它较之其它寻找最长路径算法，有自己的特点。一是能同步得出所有最长路径。二是该算法稍加修改还可用于求最大独立集问题，有一定的通用性。如用我们的算法可得图1的所有5个最大独立集。

5

采用传统数学方法研究经济问题，我们要研究解的存在性，唯一性，稳定性等，并试图求出存在的解。引进算法的有效概念后，我们还要问获得这个解的算法是有效的还是无效的。如果获得这个解的算法是无效的，那么获得解就没有可操作性。可见，在经济理论中引进算法有效性概念是必要的。另外，我们还可见，经济理论的一些思想也可用于提高算法的有效性。尽管这会带来计算结果的近似性和不确定性，但它反映了为提高算法有效性，凯恩斯选美最终结果便由上节的可预测性转变为不可预测性。

2.部分信息假设

理性预期理论坚持完备信息假设，经济人充分使用所有可以利用的信息去分析经济问题。当要分析的经济问题尚没有有效算法处理时，理性预期理论的这一假设就难以成立。

李拉亚(1991)和Sims(2003)认为，经济人为了能在有限的时间和成本下取得结果，或在有限注意力下分析信息，或经济人信息处理能力不足，他不能充分利用他可能得到的信息，只使用其中部分信息。使用部分信息进行预期，只能得到近似结果，可能存在系统误差，从而导致不确定性。这一思想可用到我们的上述进化算法中来。

我们可在所有可能的路径中，只采用其中一部分路径，如在新种群中淘汰掉部分元素。尽管这样做极有可能丢掉最优解，带来不确定性，但它能节省计算的时间和空间，提高算法的有效性。

3.带头羊假设

我们看到凯恩斯选美的一个重要思想是高阶预期，即别人预期别人的预期。高阶预期导致预期形成的复杂化，会影响到群体达成共识的效率。

带头羊能解决高阶预期这一难题。如果在凯恩斯选美的评选人群中有一位能起到带头羊作用的权威专家，每个评选人都能依据这一带头羊的选择调整自己的选择，他相信别人也依据带头羊的选择调整自己的选择。因此，他就不用再考虑别人的预期了，也不用考虑别人预期别人的预期了，即不用考虑高阶预期了。这个带头羊起到了协调群体中预期的作用。带头羊导致预期较快向同一性靠拢，即导致带头羊的选择较快成为群体中大多数人的共同选择，提高群体达成共识的效率。这也是预期管理理论的协调预期思想，其简要介绍可见Morris和

Shin(2008)的论文。

我们可在原有算法的基础上，加进权数来分析带头羊行为。虽加进带头羊行为能提高算法的有效性，但这也可能会导致最优解的丢失，带来不确定性。

五、凯恩斯选美对图型结构的敏感性

如果图上出现Hamiltonian圈，则选美结果分散化。分析图上能否出现Hamiltonian圈，是凯恩斯选美分析的难点。它不仅涉及算法，更涉及图论知识。对凯恩斯选美认识的深入，必伴随对它相关数学知识认识的深入。

6

7

图论中，关于一般图Hamiltonian 圈的充分条件很多，必要条件极少，充分必要条件更少。在本节中，我们给出一般图Hamiltonian 圈新必要条件和新充分必要条件。它们将帮助我们认识凯恩斯选美对图型结构的敏感性。

1.基本思路

如果一个图的点分别在两个不相交的集合中，该图每一条边的端点分别位于这两个集合中，这样的图称之为二分图。如果二分图两个不相交的集合有相同的点数，则这种二分图称之为平衡二分图。二分图存在Hamiltonian 圈的一个必要条件，是它的两个集合必须包含相同的点数。换言之，二分图必须是平衡二分图才有可能存在Hamiltonian 圈。

我们的基本思路是试图在一般图中利用二分图的这一必要条件。换言之，我们试图证明一个具有Hamiltonian 圈的图在一定的方法下一定能转换为一个具有Hamiltonian 圈的二分图，因此也是一个平衡二分图。如果一个一般图不能依据这一方法转换为一个具有

Hamiltonian 圈的二分图，或者一个平衡二分图，则该图不可能存在Hamiltonian 圈。

2.转换一般图到平衡二分图的方法

第一步，我们使用BFS(breadth first search)方法得到图G 的BFS 树T 。让这个BFS 树T 有与图G 同样的点与边，我们得到图GT 。图GT 等于图G 。本文下面使用的一般图均具有图GT 形式。如我们有图2，我们使用BFS 方法得到它的图GT ，见图3。

A

B

图2 图 G

图3 图 GT

图3有四层。点A在层1。点B，点H和点D在层2。点C，点I，点G和点E在层3。点F在层4。把不相邻的层上的点作为一个点集合，可得图3的两个点集合{A，C，I，G，E}和{B，H，D，F}。这两个点集合不相交。在同一层次上两点的边称为横边，如在层3上的边IG 和边GE。

第二步，在图3中，如果我们收缩点I和点G为一点S，保留点I和点G的所有连接其它层次点的边，如果有重复的边，则只保留一条边，并删去图中其余横边，得图4。图4的两个不相交的点集合是{A，C，S，E}和{B，H，D，F}。因此，图4是平衡二分图。注意，两点或多点间有横边联接，这两点或多点才能被收缩为一点。如果收缩多个点到一个点，则只保留其两个端点连接其它层次点的边，删掉中间点的所有边。

图4 收缩点后的二分图 ST

3.一般图GT存在Hamiltonian圈的新的必要条件和充分必要条件

8

定理一、一般图GT存在Hamiltonian圈的必要条件是，由一般图GT删去横边和收缩点的方式形成的一个二分图上存在Hamiltonian圈。

证明：设一般图GT存在Hamiltonian圈。Hamiltonian圈通过的横边，我们可把横边上的点收缩为一点。这是把Hamiltonian圈相邻的点收缩为一点，Hamiltonian圈仍然存在。同时，我们删去Hamiltonian圈不通过的横边。由此我们得到一个保留了Hamiltonian圈的二分图。证毕。

推论一、若一般图GT存在Hamiltonian圈，则必可由一般图GT删去横边和收缩点的方式形成一个平衡二分图。

证明：由定理一知该一般图可转换一个有Hamiltonian圈的二分图。由Hamiltonian圈的二分图的必要条件，有Hamiltonian圈的二分图是平衡二分图。证毕。

我们知道Petersen图不存在Hamiltonian圈。我们也知道Petersen图是1-tough图，因此，Hamiltonian图的1-tough必要条件对Petersen图失效。我们用定理一不难证明Petersen图不存在Hamiltonian圈，即可证明Petersen图的图GT的奇数层次上的点数与偶数层次上的点数不相等，而无论怎样收缩点，均形成一个非二连通的图，而非二连通的图不可能存在Hamiltonian圈。

定理二、如果一般图GT的奇数层次上的点数与偶数层次上的点数不相等，设其差的绝对值为X。如果点数多的层次上横边的个数大于或等于X，则一般图GT能由删去横边和收缩点的方式变为一个平衡二分图，或者变为一个图，该图至少有一个点，该点没有边。

证明：因为点数多的层次上横边的个数大于或等于X，故可由收缩点的方法减少该层次上的点数，只到奇数层次上的点数与偶数层次上的点数相等，再删去所有横边后，如果不存在没有边的点，便得一个平衡二分图，否则得一含没有边的点的图。证毕。

如果收缩多个点到一个点，并且每个端点只保留一条连接其它层次点的边，删掉两端点其余的边，删掉中间点的所有边，那么上述定理一可变为Hamiltonian圈的充分必要条件。

定理三、一般图GT存在Hamiltonian圈的充分必要条件是，由一般图GT删去横边和收缩点的方式形成的一个二分图上存在Hamiltonian圈。

证明：必要条件的证明同定理一的证明。这里证明充分条件。设由一般图GT删去横边和收缩点的方式形成的一个二分图上存在Hamiltonian圈。若Hamiltonian圈上存在收缩点，则把收缩点还原为原来的点，这相当于在Hamiltonian圈上添加原来的点，再加上所有删掉的边，则二分图还原为原一般图GT，Hamiltonian圈仍然存在。证毕。

4.凯恩斯选美的复杂特征

前面分析表明，即使是图1这样的简单图形，也可存在1620条Hamiltonian路径，30个Hamiltonian圈，反映了凯恩斯选美结果的分散化和复杂化。

但是，并不是所有图都具有Hamiltonian圈。由上述定理，我们看到Hamiltonian圈对图形结构的敏感性。这也反映了凯恩斯选美对图形结构的敏感性。在图中增加一条边(一个点)

9

或减少一条边(一个点)，Hamiltonian圈的存在与否便会出现完全不同的结果。如图2存在Hamiltonian圈，如果我们删去图2的边IG和边GE得到一新图，则这一新图不存在Hamiltonian圈。

如果我们只搜寻部分路径去寻找最长路径时，最初淘汰的边可能会对最终的结果产生重

大影响，导致最终结果的不确定，或者说，不可预测。凯恩斯选美对图形结构的敏感性决定了其对初始淘汰条件的敏感性和不确定性。

我们知道混沌系统具有简单方程可导致复杂行为的特点，及具有对初始条件的敏感性和

不确定性的特点。我们揭示凯恩斯选美的上述特征与混沌系统特征类似，较能反映金融市场的复杂行为。

六、结论

本文提出了凯恩斯选美的图论模型。该模型可以归结为找出图上的最长路径。

本文设计了一种进化算法，能同步找出图上的所有最长路径。如果关系图中仅存在一条

最长路径，则存在一种选美结果。如果关系图中存在多个相同长度的最长路径，则存在多种选美结果。如果存在一个Hamiltonian圈，则选美结果分散化。

本文在凯恩斯选美分析中，引进了算法有效性概念，分析了能提高我们算法有效性的两

种相关经济学思想。

本文证明了一般图上存在Hamiltonian圈的新必要条件和新充分必要条件，这是本文方

法上的创新。由此，我们研究了凯恩斯选美对图形结构的敏感性，及其对初始淘汰条件的敏感性和不确定性。

我们的这些研究，揭示了凯恩斯选美的复杂性。

本文结合图论和算法研究凯恩斯选美的方法，是经济学一个具有广阔发展前景的研究方向。算法有效性将成为经济理论中的一个重要概念。离散数学(如图论)和算法也将成为经济理论的一个重要部分和基本分析工具，成为数量经济学的一个新分支。它反映了20世纪40年代计算机革命来，数学研究重心从连续数学向离散数学转移的大趋势。

我们的研究方法也可推广到其它涉及从众行为的学科，如社会学、政治学和心理学等。

参考文献

[1] 李拉亚：《通货膨胀机理与预期》[M]，中国人民大学出版社，北京，1991。

[2] 周翼，项杨：《凯恩斯的“选美论”：一个网络经济学的解释》[J]，《数量经济技术经济研究》，2001年第4期。

[3] Allen, F., S. Morris, and H.S. Shin, 2006, Beauty Contests and Iterated Expectations in Asset Markets [J], Review of Financial Studies 19(3), pp.719-752.

10

[4] Bosch-Domenech, A., Montalvo, J. G., Nagel, R., and Satorra, A., 2002, One, Two, Three, Infinity, ...: Newspaper and Lab Beauty-Contest Experiments [J]， American Economic Review, December, Vol 92 No.5, pp.1687-1701.

[5] Ho, Teck-Hua, Colin Camerer and Keith Weigelt, 1998, Iterated Dominance and Iterated Best-Response in Experimental p-Beauty Contests [J], American Economic Review 88, No. 4, pp.947-969.

[6] Keynes, John Maynard,1936，The general theory of employment, interest, and money [M], Macmillan，London.

[7] Morris，S. and H.S. Shin，2008，Coordinating Expectations in Monetary Policy [M]，in Central Banks as Economic Institutions, edited by.Jean-Philippe Touffut, Edward Elgar Publishing, pp.88-104.

[8] Moulin, Herve, Game Theory for the Social Sciences [M], 2nd Ed. New York: NYU Press, 1986.

[9] Nagel, Rosemarie, 1995, Unraveling in Guessing Games: An Experimental Study [J], American Economic Review 85, pp.1313-1326.

[10] Schmalz, M., Fujita, M., Sawodny, O., 2009, Directed Gossip Algorithms, Consensus Problems, and Stability Effects of Noise Trading [J], European Journal of Economic and Social Systems, Vol. 22, No. 1, pp.43-61.

[11] Sims, C.A., 2003，Implications of rational inattention [J], Journal of Monetary Economics, 50(3),

pp.665-690.

[12] Stahl,Dahl O., 1996, Rule Learning in a Guessing Game [J]，Games and Economic Behavior, 16(2), pp.303-330.

附录一、我们算法得出的图1所有30个Hamiltonian圈

v00v01v02v03v04v13v12v11v10v09v08v07v06v16v17v18v19v15v14v05v00

v00v01v02v03v04v13v14v15v16v17v18v19v12v11v10v09v08v07v06v05v00

v00v01v02v03v11v10v09v08v07v06v05v14v15v16v17v18v19v12v13v04v00

v00v01v02v03v11v12v19v15v16v17v18v10v09v08v07v06v05v14v13v04v00

v00v01v02v09v08v07v06v05v14v13v12v19v15v16v17v18v10v11v03v04v00

v00v01v02v09v08v07v06v16v17v18v10v11v03v04v13v12v19v15v14v05v00

v00v01v02v09v10v11v03v04v13v12v19v18v17v08v07v06v16v15v14v05v00

v00v01v02v09v10v18v17v08v07v06v16v15v19v12v11v03v04v13v14v05v00

v00v01v02v09v10v18v19v12v11v03v04v13v14v15v16v17v08v07v06v05v00

11

v00v01v02v09v10v18v19v15v16v17v08v07v06v05v14v13v12v11v03v04v00

v00v01v07v06v05v14v13v12v11v10v18v19v15v16v17v08v09v02v03v04v00

v00v01v07v08v09v02v03v04v13v14v15v19v12v11v10v18v17v16v06v05v00

v00v01v07v08v09v02v03v11v10v18v17v16v06v05v14v15v19v12v13v04v00

v00v01v07v08v17v16v06v05v14v15v19v18v10v09v02v03v11v12v13v04v00

v00v04v03v02v09v10v11v12v13v14v05v06v16v15v19v18v17v08v07v01v00

v00v04v03v11v10v18v17v08v09v02v01v07v06v16v15v19v12v13v14v05v00

v00v04v03v11v10v18v19v12v13v14v15v16v17v08v09v02v01v07v06v05v00

v00v04v13v12v19v18v10v11v03v02v09v08v17v16v15v14v05v06v07v01v00

v00v04v13v14v05v06v16v15v19v12v11v03v02v09v10v18v17v08v07v01v00

v00v05v06v07v01v02v03v11v12v19v18v10v09v08v17v16v15v14v13v04v00

v00v05v06v16v15v14v13v04v03v02v09v10v11v12v19v18v17v08v07v01v00

v00v05v06v16v15v14v13v12v19v18v17v08v07v01v02v09v10v11v03v04v00

v00v05v06v16v17v08v07v01v02v09v10v18v19v15v14v13v12v11v03v04v00

v00v05v06v16v17v18v10v09v08v07v01v02v03v11v12v19v15v14v13v04v00

v00v05v06v16v17v18v19v15v14v13v12v11v10v09v08v07v01v02v03v04v00

v00v05v14v13v04v03v02v09v08v17v18v10v11v12v19v15v16v06v07v01v00

v00v05v14v13v12v11v10v09v08v17v18v19v15v16v06v07v01v02v03v04v00

v00v05v14v15v16v06v07v01v02v03v11v10v09v08v17v18v19v12v13v04v00

v00v05v14v15v19v18v10v09v08v17v16v06v07v01v02v03v11v12v13v04v00

v00v05v14v15v19v18v10v11v12v13v04v03v02v09v08v17v16v06v07v01v00

附录二、我们算法得出的图1所有五个最大独立集

12

v00v13v15v18v02v11v06v08

v00v14v16v18v03v12v07v09

v01v13v16v19v03v10v05v08

v01v14v17v19v04v11v06v09

v02v12v15v17v04v10v05v07

13

数学建模笔记

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

数学建模中的图论方法

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

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

数学建模常用的十大算法==转 (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、基本概念： 图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。 邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。 无向图（graph）：边无方向的图；有向图（digraph）：边有方向的图。 路(path)：由相邻边组成的序列，其中中间顶点互不相同。 圈(cycle)：首、尾顶点相同的路，即闭路。 连通图（connected graph）：图中任意两顶点间都存在路的图。 树（tree）：无圈连通图 完全图（complete graph）：任意两个顶点之间都有边相连的无向图，记为K n。 竞赛图（tournament）：由完全图给每条边定向而得到的有向图。 二部图（bipartite graph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。 网络（Network）：边上赋了权的有向图。

3、图的矩阵表示 无向图 有向图 0100010 11001011 011000 1 00???????????????? ???? ? ? ? ? ????????0110010100000100100000110

数学建模模拟题,图论,回归模型,聚类分析,因子分析等 (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

图论 模型

251 图论模型 图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。 图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. K?nig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。 9.1 图的基础理论 9.1.1 图的基本概念 所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。E 是边的集合，称为边集。边一般用(,)i j v v 表示，其中 ,i j v v 属于顶点集V 。 以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。 如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 (,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =. 2 3 v 45 v 3 4 (a) (c) 图9.1 图的示意图 1.无向图和有向图 如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。 如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点i v 和j v 的弧记为,i j v v ??，其中i v 称为起点，j v 称为终点。显然此时弧,i j v v ??与弧,j i v v ??是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为(,)D V A =，其中V 为顶点集，A 为弧集。 例如图9.1 (C)可以表示为(,)D V A =，顶点集1234{,,,}V v v v v =，弧集为1223{,,,, A v v v v =????243441,,,,,}v v v v v v ??????。 对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用G 表示。 例9.1 设12345{,,,,}V v v v v v =，12345{,,,,}E e e e e e =，其中

数学建模中常见的十大模型讲课稿

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

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

数据建模目前有两种比较通用的方式

数据建模目前有两种比较通用的方式1983年，数学建模作为一门独立的课程进入我国高等学校，在清华大学首次开设。1987年高等教育出版社出版了国内第一本《数学模型》教材。20多年来，数学建模工作发展的非常快，许多高校相继开设了数学建模课程，我国从1989年起参加美国数学建模竞赛，1992年国家教委高教司提出在全国普通高等学校开展数学建模竞赛，旨在“培养学生解决实际问题的能力和创新精神，全面提高学生的综合素质”。近年来，数学模型和数学建模这两个术语使用的频率越来越高，而数学模型和数学建模也被广泛地应用于其他学科和社会的各个领域。本文主要介绍了数学建模中常用的方法。 一、数学建模的相关概念 原型就是人们在社会实践中所关心和研究的现实世界中的事物或对象。模型是指为了某个特定目的将原型所具有的本质属性的某一部分信息经过简化、提炼而构造的原型替代物。一个原型，为了不同的目的可以有多种不同的模型。数学模型是指对于现实世界的某一特定对象，为了某个特定目的，进行一些必要的抽象、简化和假设，借助数学语言，运用数学工具建立起来的一个数学结构。 数学建模是指对特定的客观对象建立数学模型的过程，是现实的现象通过心智活动构造出能抓住其重要且有用的特征的表示，常常是形象化的或符号的表示，是构造刻画客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。 二、教学模型的分类 数学模型从不同的角度可以分成不同的类型，从数学的角度，按建立模型的数学方法主要分为以下几种模型：几何模型、代数模型、规划模型、优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型等。 三、数学建模的常用方法 1.类比法 数学建模的过程就是把实际问题经过分析、抽象、概括后，用数学语言、数学概念和数学符号表述成数学问题，而表述成什么样的问题取决于思考者解决问题的意图。类比法建模一般在具体分析该实际问题的各个因素的基础上，通过联想、归纳对各因素进行分析，并且与已知模型比较，把未知关系化为已知关系，

数学建模常用算法模型

数学模型的分类 按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握） 解决预测类型题目。由于属于灰箱模型，一般比赛期间不优先使用。 满足两个条件可用： ①数据样本点个数少，6-15个 ②数据呈现指数或曲线的形式 2、微分方程预测（高大上、备用） 微分方程预测是方程类模型中最常见的一种算法。近几年比赛都有体现，但其中的要求，不言而喻。学习过程中 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式推导转化为原始数据的关系。 3、回归分析预测（必掌握） 求一个因变量与若干自变量之间的关系，若自变量变化后，求因变量如何变化； 样本点的个数有要求： ①自变量之间协方差比较小，最好趋近于0，自变量间的相关性小； ②样本点的个数n＞3k+1，k为自变量的个数；

数学建模常用算法模型

按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）

3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握）

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

数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】

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

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

数学建模方法归类(很全很有用)

在数学建模中常用的方法：类比法、二分法、量纲分析法、差分法、变分法、图论法、层次分析法、数据拟合法、回归分析法、数学规划（线性规划，非线性规划，整数规划，动态规划，目标规划）、机理分析、排队方法、对策方法、决策方法、模糊评判方法、时间序列方法、灰色理论方法、现代优化算法（禁忌搜索算法，模拟退火算法，遗传算法，神经网络）。 用这些方法可以解下列一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。拟合与插值方法（给出一批数据点，确定满足特定要求的曲线或者曲面，从而反映对象整体的变化趋势）：matlab可以实现一元函数，包括多项式和非线性函数的拟合以及多元函数的拟合，即回归分析，从而确定函数；同时也可以用matlab实现分段线性、多项式、样条以及多维插值。 在优化方法中，决策变量、目标函数（尽量简单、光滑）、约束条件、求解方法是四个关键因素。其中包括无约束规则（用fminserch、fminbnd实现）线性规则（用linprog实现）非线性规则、（用fmincon实现）多目标规划（有目标加权、效用函数）动态规划（倒向和正向）整数规划。 回归分析：对具有相关关系的现象，根据其关系形态，选择一个合适的数学模型，用来近似地表示变量间的平均变化关系的一种统计方法（一元线性回归、多元线性回归、非线性回归），回归分析在一组数据的基础上研究这样几个问题：建立因变量与自变量之间的回归模型（经验公式）；对回归模型的可信度进行检验；判断每个自变量对因变量的影响是否显著；判断回归模型是否适合这组数据；利用回归模型对进行预报或控制。相对应的有线性回归、多元二项式回归、非线性回归。 逐步回归分析：从一个自变量开始，视自变量作用的显著程度，从大到地依次逐个引入回归方程：当引入的自变量由于后面变量的引入而变得不显著时，要将其剔除掉；引入一个自变量或从回归方程中剔除一个自变量，为逐步回归的一步；对于每一步都要进行值检验，以确保每次引入新的显著性变量前回归方程中只包含对作用显著的变量；这个过程反复进行，直至既无不显著的变量从回归方程中剔除，又无显著变量可引入回归方程时为止。（主要用SAS来实现，也可以用matlab软件来实现）。 聚类分析：所研究的样本或者变量之间存在程度不同的相似性，要求设法找出一些能够度量它们之间相似程度的统计量作为分类的依据，再利用这些量将样本或者变量进行分类。 系统聚类分析—将n个样本或者n个指标看成n类，一类包括一个样本或者指标，然后将性质最接近的两类合并成为一个新类，依此类推。最终可以按照需要来决定分多少类，每类有多少样本（指标）。 系统聚类方法步骤： 1.计算n个样本两两之间的距离 2.构成n个类，每类只包含一个样品 3.合并距离最近的两类为一个新类 4.计算新类与当前各类的距离（新类与当前类的距离等于当前类与组合类中包含的类的距离最小值）， 若类的个数等于1，转5，否则转3 5.画聚类图 6.决定类的个数和类。 判别分析：在已知研究对象分成若干类型，并已取得各种类型的一批已知样品的观测数据，在此基础上根据某些准则建立判别式，然后对未知类型的样品进行判别分类。 距离判别法—首先根据已知分类的数据，分别计算各类的重心，计算新个体到每类的距离，确定最短的距离（欧氏距离、马氏距离） Fisher判别法—利用已知类别个体的指标构造判别式（同类差别较小、不同类差别较大），按照判别式的值判断新个体的类别 Bayes判别法—计算新给样品属于各总体的条件概率，比较概率的大小，然后将新样品判归为来自概率最大的总体 模糊数学：研究和处理模糊性现象的数学（概念与其对立面之间没有一条明确的分界线）与模糊数学相关的问题：模糊分类问题—已知若干个相互之间不分明的模糊概念，需要判断某个确定事物用哪一个模糊概念来反映更合理准确；模糊相似选择—按某种性质对一组事物或对象排序是一类常见的问题，但是用来比

数学建模图论模型图论

§1 最小生成树 1．1 生成树的概念 设图G＝(V，E)是一个连通图，当从图中任一顶点出发遍历图G时，将边集E(G)分成两个集合A(G)和B(G)。其中A(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1＝(V，A)是图G的子图，则称子图G1是连通图G的生成树。图的生成树不是惟一的。如对图1(a)，当按深度和广度优先搜索法进行遍历就可以得到图1中(b)和(c)的两棵不同的生成树，并分别称之为深度优先生成树和广度优先生成树。 对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若图G的生成树中任意加一条边属于边集B(G)中的边，则必然形成回路。 求解生成树在许多领域有实际意义。例如，对于供电线路或煤气管道的铺设问题，即假设要把n个城市联成一个供电或煤气管道网络，则需要铺设n－1条线路。任意两城市间可铺设一条线路，n个城市间最多可能铺设n(n－1)/2条线路，各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择n-1条使该网络的建造费用最少，这就是下面要讨论的最小生成树问题。 1.2 网的最小生成树 在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。 假设，要在n个居民点之间敷设煤气管道。由于，在每一个居民点与其余n－1个居民点之间都可能敷设煤气管道。因此，在n个居民点之间，最多可能敷设n(n-1)/2条煤气管道。然而，连通n个居民点之间的管道网络，最少需要n-1条管道。也就是说，只需要n-1条管道线路就可以把n个居民点间的煤气管道连通。另外，还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2条可能的线路中优选n-1条线路，构成一个煤气管道网络，从而既能连通n个居民点，又能使总的花费代价最小。 解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点，把居民点之间的煤气管道看作边，而把敷设各条线路的代价当作权赋给相应的边。这样，便构成一个带权的图，即网。对于一个有n个顶点的网可以生成许多互不相同的生成树，每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。

图论模型及其解答

各种图论模型及其解答 摘要： 本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。 符号约定： Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。 一、引言 图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下： 原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解 整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况： ①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图 ②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图 如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。 综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。 例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友M：点表示人，连线表示当且仅当该两个人是朋友 A：问题转化为任何一个图一定存在两个顶点的度相等 二、图论模型 接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。 2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这

数学建模图论

图论 一．最短路问题 问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 将问题抽象为赋权有向图或无向图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初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。然后以新纳入的点为起点继续搜索，直到所有的点遍历。

数学建模图论

数学建模图论 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 标号。若在算法运行过程中，将

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

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

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

数学建模中常见的十大 模型 集团标准化工作小组 #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 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。