当前位置:文档之家› 04第四章 图论方法建模2

04第四章 图论方法建模2

04第四章  图论方法建模2
04第四章  图论方法建模2

第四章 图论方法建模

20 第四章 图论方法建模

图论是离散数学的重要分支,是研究离散问题的重要手段,已经建立起来了一些重要的理论和算法,虽然这些理论还不系统、不完备,但是能解决许多的实际问题。不系统就没有太强的连贯性,这就使得学习起来较为方便,可以随意挑选适宜的内容去学习。

如果将要解决的实际问题归结为图论中的某些概念或某些算法,就可以利用图论中已有的理论,这样就可以较快的解决问题。

在国内外的大学生数学建模竞赛中,利用图论知识去建立数学模型的机会还是很多的。限于时间与篇幅,我们在本章先学习一些图论知识,愿意深入学习的可以参阅有关的资料。然后学习一个较为完整的数学建模例子。

§4.1 有关的图论知识——图、算法与矩阵

一.图的定义

例1.城市之间的运输通路问题

A 城与

B 城间有通路,为2公里,B 城与

C 城间有通路,为1公里,C 城与

D 城间有通路,为5公里,D 城与F 城间有通路,为3公里,F 城与A 城间有通路,为7公里,B 城与F 城间有通路,为6公里。问A 城到D 城的最短路程为多少?

用这么长的一段话来表述,听起来太累,想起来也不清楚。若换一种方式,用下面的图4.1来描述该问题,看起来就清楚多了。

C

图4.1

由此我们引进图的定义。 定义1:称}),(),({G G E G V G ψ=为一个图,其中φ≠)(G V 叫做顶点集合,E(G)

第四章 图论方法建模 21

叫做边集合,φ=)()(G E G V I ,而G ψ是关联函数,使G的每条边对应于G的无序顶点对。若,而,使得)(G E e ∈)(,G V v u ∈uv e G =)(ψ,则称与u 、相关联。顶点和称为的端点,此时也称和相邻。

e v u v e u v 一个图常常简记为G=(V,E )或G (V,E ),这是因为边集E 中的任一 元素总是和某二顶点相连接的,所以V 、E 确定了,就可以了。

上述例子的图即为:G(V,E),其中V={A,B,C,D,F },E={e 1,e 2,e 3,e 4,e 5,e 6}

,e 1=AB, e 2=BC, e 3=CD, e 4=DF, e 5=FA, e 6=BF 。

说明:①这里用图表述城市间的运输通路问题很清楚,说明对这类问题,用图来表述是恰当的,“图”是一个强有力的表述工具。

②数学里有“图论”这门学科,一个问题用图表达后,可用图论的知识、算法等来解决此问题。关于图论方面的知识可参阅有关的书籍、资料。

③若A为一集合,其元素个数记为:|A|。如上例中的顶点集合和边集的元素个数分别为:|V|=5,|E|=6。

例2.哥尼斯堡(k?nigsberg )七桥问题

1736年以前,哥尼斯堡市民热中于一有趣的游戏,在如下图4.2所示的该市桥河图中,从A,B,C,D四块陆地某一处出发,通过每座桥恰好一次,再回到出发地,是否可能?

1736年,欧拉(Euler )发表了图论的第一篇论文,证明了七桥问题无解.欧拉就是把A,B,C,D四陆地抽象成为四个点,桥用连接两点的线段表示,于是就得到一个图G(V,E)。, },,,{D C B A V =},,,,,,{7654321e e e e e e e E =, 这里,e 1=AD, e 2=BD, e 3=CD, e 4=BC, e

5=BC, e 6=AB, e 7

=AB 。

定义2:图G(V , E)中顶点的度数是指顶点所连的边数。图G 的度数为图G 中各顶点度数中的最大者。记为或V v ∈)(v d v Δ)(G Δ。

说明:①七桥问题可归结为一笔画问题。

②关于一笔画问题有如下的结论:

若图中每个顶点的度数都为偶数,则可从某点画完每条边,且回到起点。

第四章 图论方法建模

22 若图中顶点的度数为奇数的顶点仅仅有两个,则可从此二点中的一个起始,画完每条边到达另一顶点(即不能回到起始点)。

③七桥问题的图中4个顶点的度数为奇数,由上面的结论知,不可能从出发点走完每条边恰好一次,又回到出发点。

定义3:一个图中任意两顶点之间至多有一边,则称之为简单图。

定义4:若图G(V ,E)中边有头尾之分,即E uv ∈vu uv ≠,则称之为有向图。

以后说“图”皆指无向图,要指有向图应特别说明。并且若无特别说明,我们所说的图皆指简单图。每对顶点都相邻的图称为完全图。

定理:对于简单图,有:

),(E V G ∑∈=)(||2)(G V v E v d 。

二.最短路问题及其算法

定义5:在G 中, 其中,...2110k k e v e v e v w =)(G E e i ∈,k i ≤≤1;)(G V v i ∈,;与、关联,称是从到的一条途径,也记为或。若途径中的边,,……,互不相同,称为迹。若的顶点,,…,也互不相同,则称为路。

k i ≤≤0i e 1?i v i v w 0v k v ),(0k v v w ),(0k v v 1e 2e k e w w 0v 1v k v w 上述例1中问题的一般提法为:给定连接若干城市的铁路网,寻找两个指定城市间的最短路。

这个问题用图论的语言来描述就是:已知图及每条边的权,对于任意指定的二点、,寻找路,使得

),(E V G )(e w 0v )(0G V u ∈),(00u v P )}({)),((min 00P w u v P w P Ω

∈=

其中是从到的所有路的集合,是路Ω0v 0u )(P w P 上的各边权之和。

解决这一问题可用下面的Dijkstra 算法:

(1):令;,;0)(0=v l ∞=)(v l 0v v ≠}{00v S =;0=i ;

(2):对每个,用i S v ?)}()(),(min{v v w v l v l i i +代替,计算

)(v l )}({min v l i

S v ?,并把达到这个最小值的一个顶点记为,置1+i v }{11++=i i i v S S U 。 (3):若1?=V i ,则停止。若1?

i 说明:①当算法结束时,从到的距离(最短路的长度)由标号的终值给出。即算法求出了至其它所有顶点的最短路的长度。

0v v )(v l 0v ②Dijkstra 算法仅确定了从到所有其它顶点的距离,而并未给出实际最短路。实际最短路可以很容易确定。

0v ③若只是想计算某指定两点、的最短路(或最短距离)也较为容易求出。 0v 0u

第四章 图论方法建模 23

三.对集和二部图

例3.人员分派问题:工作人员x 1,x 2,……,x n 去做n 项工作y 1,y 2,……,y n ,每人适合做其中一项或几项工作,问能否每人都能被分派一项适合的工作?如果不能,最多几人可以有适合的工作?

作为一个简单的例子,我们设n=4,将4个人用4个点表示,将4项工作也用4个点表示,若有某人x i

适合作某项工作y j ,则用边连接起来。这样可以得到一个图如下:

定义5:二部图(偶图)是指一个图G(V ,E),V=X ∪Y ,X ∩Y=?,,X 中无相邻顶点,Y 中亦无相邻顶点。

0||||≠?Y X 定义6:若,)(G E M ?M e e j i ∈?,,与无公共顶点(i e j e j i ≠)

,则称M 为图G 的对集(或称为匹配)。M 中的一条边的两个端点叫做在对集中相配;M 中的边的端点叫做被M 许配;若图G 中每个端点皆被M 许配时,M 称为完备对集。若G 中无使的对集M’,则称M 为最大对集。

|||'|M M >说明:①人员分派问题的图是二部图。

②若人员分派问题的图有完备对集,则可以为每人分派一项适合的工作。

③最多有几个人可以有适合的工作,就是人员分派图中最大对集M 的边数,即|M |。

四.求最大对集的算法

定义7:若G 中有一条路,其边交替地在对集M 内外出现,则称此路为M 的交错路,交错路之起止顶点都未被M 许配时,此交错路称为可增广路。

注:若把可增广路上在M 外的边纳入对集,把M 内的边从对集中删除,则被许配的顶点数增加2,对集中的边增加一个。

关于一般图求最大对集的算法,Edmonds 在1965年提出了一种算法。关于偶图求最大对集的算法有多种。这里介绍一种偶图求完备对集的算法――匈牙利算法。

设G 为二分图,,求此图的完备对集的匈牙利算法如下:

(0):从G 中任意取定一个初始对集M 。

(1):若M 把X 中的顶点都许配,止。M 即为完备对集;否则取X 中未被M 许配的一顶点u ,记S={u},T=?。

第四章 图论方法建模

24 (2):若N(S)=T ,止。无完备对集;否则取y ∈N(S)-T 。

(3):若y 是被M 许配的,设yz ∈M ,S ←S ∪{z},T ←T ∪{y},转(2)。否则,取可增广路P(u,y),令M ←M ΔE(P),转(1)。

说明:①算法的要点是把已有的对集通过可增广路逐次增广以至得到完备对集。 ②N(S)={y | y 与S 中的某点相邻}

③M ΔE(P)是将可增广路P 中的在M 外的边纳入对集,把M 内的边从对集中删除,该运算结果仍为对集。

五.独立数与色数

例4.化学制品的存放问题

一家公司制造n 种化学制品,C 1,C 2,……,C n ,其中某些制品是互不相容的,如果它们互相接触则会引起爆炸。作为一种预防措施,该公司希望把它的仓库分成若干隔间,以便使不相容的药品存放在不同的隔间里。试问,这个仓库至少应分成几个隔间?

为了方便,设n=6,这6种化学制品C 1,C 2,……,C 6

分别用6个点代表,它们之间互不相容的制品用一条边连接起来,这样就得到一个图如下所示:

定义8:若,I 中任意二顶点不相邻,则称I 为图G 的一个独立集。,不是独立集,则称I 为极大独立集。顶点数最多的独立集叫做最大独立集,其顶点数记成)(G V I ?I G V u ?∈?)(}{u I ∪)(G α,称为图G 的独立数。

定义9:把图G 的顶点都染上颜色,且使相邻顶点异色,又使所用的颜色数最少,称这个颜色数为G 的顶点色数,记成)(G χ。

定理:1)(+Δ≤G χ,

(其中为图G 的度数)。 Δ说明:①每个隔间里存放的化学制品集合即为独立集。

②极大独立集和最大独立集是不同的。

③仓库至少应分成几个隔间就化为求一个图的顶点色数)(G χ,而)(G χ的求法是较为困难的。虽然也有些算法可求,但都不是十分有效。

六.关联矩阵与邻接矩阵

一个图存放在计算机里的方式很多,但一般是以矩阵的方式来存储的。

第四章 图论方法建模 25

定义10:设图G(V, E),,},...,,{21γv v v V =},......,,{21εe e e E =,

称矩阵()

γγ×=ij a G A )(为图G 的邻接矩阵,其中)(G V =γ, ??????∈=).(,0);(,1G E v v G E v v a j i j i ij 称矩阵()εγ×=ij b G B )(为图G 的关联矩阵,其中)(G V =γ,|)(|G E =ε,

。 )(),(0,1G E e G V v e v e v b j i j i j i ij ∈∈??

???=不相关联;与,相关联;与§4.2 锁具装箱问题

一.问题的提出

此问题是1994年全国大学生数学建模竞赛B 题。问题如下:

某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1,2,3,4,5,6} 6个数(单位略)中任取一数。由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽的高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。

从顾客的利益出发,自然希望在每批锁具中“一把钥匙开一把锁”。但是在当前工艺条件下,对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个槽的高度差为1,则可能互开;在其它情形下,不可能互开。

原来,销售部门在一批锁具中随意地取每60个装一箱出售。团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互开的情形。现请回答以下问题:

1. 每一批锁具有多少个,装多少箱?

2. 如何给箱子以标志,出售时如何利用这些标志,排除或减少抱怨?

3. 团体顾客购买多少箱时,保证一定不会出现互开的情形?

4. 按照原来的装箱方案,如何定量地衡量团体顾客抱怨互开的程度(试对购买一,二

箱者给出具体结果)。

二.问题分析

某厂生产一种弹子锁具,由于其钥匙有5个槽,所以用五元数组来记一个锁具:

),,,,(Key 54321h h h h h =

其中hi 表示第i 个槽的高度,i=1,2,3,4,5. 此五元数组表示一把锁应满足下述条件:

条件1. . {

}6,5,4,3,2,1∈i h 5,4,3,2,1=i 条件2. 对于任意一种槽高排列, ,至少有三个不同的槽高。

54321,,,,h h h h h

第四章 图论方法建模

26 条件3. 对于任意一种槽高排列, ,有: ,。

54321,,,,h h h h h 5||1≠??i i h h 5,4,3,2=i 而两个锁具可以互开的条件为:两个锁的钥匙有四个槽高相同,其余一个槽高相差为1。

三.模型假设

我们假设锁具厂在生产锁具的过程中能够准确地知道每个钥匙的槽高排列。

四.模型建立

① 定义锁具图:

我们定义锁具图G(V , E),其中:

V 是顶点集,V 中一顶点表示一个锁具,即V 是一批锁具的全体。

E 是边集,对V 中任意二顶点,当且仅当它们所代表的锁具能够互开时,则用一条边将此二点连接。

② 定义总槽高

我们对锁具定义总槽高:

),,,,(Key 54321h h h h h =∑==5

1i i h Total 易得。

278≤≤Total 根据每个锁具的总槽高值,可将锁具图的顶点集V 分为20个子集,分别记为:

}|),,,,{(54321i Total h h h h h A i ==, 27,......,9,8=i . 每个子集的元素个数如下表:

集合

A 8A 9A 10A 11A 12A 13A 14A 15A 16A 17集合中的元素个数 20 50120162251322405508 539 563 集合 A 18A 19A 20

A 21A 22A 23A 24A 25A 26A 27集合中的元素个数 563 539

508405322251162120 50 20 注;上表的数值可编程(具体的C 语言源程序参见附录A )来计算得到。

③ 锁具图的性质 具有下列性质:

)27,......,9,8(=i A i (1)为锁具图G(V , E)的独立集。

)27,......,9,8(=i A i (2)中的元素只可能与或中的元素有连边。

i A 1?i A 1+i A 令:

i i A P U 为偶数=i i A Q U 为奇数

=则:P,Q 仍为独立集,且。

Q P V U =

第四章 图论方法建模 27

所以,锁具图G(V , E)为二部图。

④ 总结

(1) 一批锁具的个数即为锁具图G(V , E)的顶点数|V|。

(2) 关于团体顾客抱怨的问题,归结为研究锁具图G(V , E)的独立集问题,这里很重要的是锁具图的独立数)(G α是多少。

五.模型求解

1.一批锁具个数的计算

一批锁具的个数即为锁具图G(V, E)顶点数|V|,必然有:|V|≤65。可采用逐个检验条件1,2,3的方法编程计算,可求得|V|=5880。

用排列组合的方法来求一批锁具的个数,也是可以的。请看下面的介绍。 令}5,4,3,2,1},6,45,3,2,1{|),,,,{(54321=∈=i h h h h h h S i ,

A ?S ,A 内的五位数中互不相同的数字少于3 个。

B ?S ,B 内的五位数中存在相邻数字其差为5。

则锁具图G(V, E)的顶点数,即一批锁具的总数为:

||||||||||||||B A B A S B A S V I U +??=?=

容易算出:,,77766||5==S 4566)22(||526=+?=C A 1470||=B , 3022||5=?=B A I 于是58803014704567776||=+??=V 。

2.装箱与标记

由于|P|=2940, |Q|=2940,且P ,Q 都是独立集,所以我们采取下面的装箱销售策略。 (1)装箱:将P 中元素代表的锁具每60把装一箱,共49箱,并标记为P 。

将Q 中元素代表的锁具每60把装一箱,共49箱,并标记为Q 。

(2)销售:根据标记,当团体顾客到来时,尽量选同一种标记的箱子售给团体顾客。

3.问题3的答案

由第2问的解答可知,只要团体顾客一次购买不超过49箱,我们就可以保证他们购买的锁具不会出现互开情形。

4.抱怨程度的刻划

任意装箱造成的抱怨是由于团体顾客购买的锁具出现互开情形,抱怨程度的刻划,就涉及到团体顾客所购买的锁具之间互相连的边的多少。下面就来进行计算,这里需要一点概率的知识。

锁具图G(E, V)的总边数:|E|=22778(此数是计算机程序求得的)。 任取二锁具互开的可能性是:2588022778

C

第四章 图论方法建模

28 所以一箱中互开锁对的期望值为: 33.22277826058801≈×=

C C E 两箱中互开锁对的期望值为:40.9227782120258802≈×=C C E

一般地,k 箱中互开锁对的期望值为:2602588022778

k

k C C E ×= 所以我们就用团体顾客购买的锁具中互开锁对的期望值来刻划抱怨程度。

关于购买一、二箱时的互开锁对的期望值也可以用计算机模拟去计算,得到的结果与上述结果是一致的。

说明:直接用互开锁对的期望值来刻划抱怨程度是简单的,但有一定的不合理性。因为这样来刻划,购买的箱数越多,抱怨程度就越大,而实际上,购买的越多,自然互开的可能性就越大,这是顾客意料之中的,不应有太多的抱怨,顾客所不能容忍的是在购买少量的锁具而出现互开现象。因此应把购买箱数作为一个因素考虑到抱怨函数中。理想的抱怨函数应该是,开始随购买量的增加而增加,到一定量后下降,这才合理。

六.进一步提高的讨论

1. 独立数的讨论

锁具图G(E, V)的独立数,即是一批锁具中不能互开锁具集合中元素最多的集合的元素个数,这是一个较难的理论问题。但在图论知识中已有这方面关于独立数的研究。我们这里介绍一种不需要太多图论知识的方法来证明:锁具图G(E, V)的独立数2940)(=G α。

定理1. 锁具图G(E, V)中有完备对集。

此定理的证明实际上是用计算机来找出一个完备对集。锁具图G(E, V)为二部图,,且Q P V U =2940||||==Q P ,所以锁具图的完备对集的边数为2940。我们是编制出程序让计算机求出一个完备对集的,而该程序的设计思想是:

将P 中的元素作为整数

),,,,(Key 54321h h h h h =5432110100100010000h h h h h ++++

放入数组ou[2940]中,Q 中元素类似地放入数组ji[2940]中。

再构造矩阵,其中。 29402940)(×=ij a A ?

??=无连边与有连边与][][,0][][,1j ji i ou j ji i ou a ij 注意到A 中的一个值为1的元素对应对应于锁具图的一条边,A 中不同行不同列值为1的元素的一个集合对应于锁具图的一个对集。A 中不同行不同列值为1的元素的最大个数,即是锁具图G(E, V)的最大对集的边数。A 中2940个不同行不同列值为1的元素就对应于锁具图的一个完备对集。为求完备对集,我们采用下面的方法找出A 中2940个不同

第四章 图论方法建模 29

行不同列值为1的元素。在矩阵A 中找出行和最小的行(设为第行),再在此行元素为1的列中找出列和最小的列(设为第i j 列),此时得A 的元素,其值为1。在A 中将第行第ij a i j 列划去,又得一新的矩阵,对新的矩阵同样处理,直到找不出值为1的元素,或找到了2940个不同行不同列的值为1的元素。

按上述程序设计思想,我们画出框图如下: 按总齿高Total值从小到大生成每个锁具,并分别顺序将总齿高Total 值为偶数的锁具放入数组Ou[2940]中,将总齿高Total值为奇数的锁具放入数组ji[2940]中。

计算每个锁具的度数并分别放入数组ouedn[2940]与jiedn[2940]中。 For k=2939 To 0 step -1

从ouedn[0]到ouedn[2939] 中找最小的数,用变量minou记其序

号。若最小数<=0,则程序打印出错信息后结束。

找ji[0]到ji[k]中与ou[minou] 连边的锁,若连边,则

jiedn[i]-1, 并求这些与ou[minou]连边的锁中jiedn[i]最小的

锁,记其序号为minji。

在ou[0]到ou[k]中, 若有与ji[minji]连边的锁,则ou[i]-1。

Ji[minji]与ji[k] 交换,jiedn[minji]与jiedn[k]交换。

ou[minou]与ou[k] 交换,ouedn[minou]与ouedn[k]交换。

屏显找到的一对锁具ou[k],ji[k], 及 已经找到的锁具对数

2940-k。

将数组ou[2940]和ji[2940]输出到磁盘文件中。

注:此框图略去了写程序时的某些细节。如ou[2940]在程序里是分为两个数组ou1[2940]和ou2[2940]的等等。

第四章 图论方法建模

30 我们希望找到2940个不同行不同列的值为1的元素,实际上编出的程序(具体程序可参见附录A )也确实找出了2940个不同行不同列的值为1的元素,即找到了一个完备对集。

对用上述程序思想编制程序时应当注意到以下三点:

(1)关于偶图求最大对集的算法有匈牙利方法和Hoperoft-Kerp 方法。关于一般图求最

大对集的算法,1965年Edmonds 就提出了一种好的算法。我们的程序没有采用这些算法。

(2)在微型计算机中存储矩阵A 是不现实的。

(3)不求行和最小的行及列和最小的列,可得边数为2928的对集。

定理2. 锁具图G(E, V)的独立数2940)(=G α。

证明:因P为独立集,且,所以 2940||=P 2940)(≥G α。

下用反证法证明:2940)(≤G α。

假设2940)(>G α,则存在一个独立集,V D ?2940)(||>=G D α。由定理1,可将V中的所有元素(按边数为2940的一个完备对集配对)放在2940个抽屉中,每个抽屉中有二元素且有连边。而D是V的子集,其元素个数多于2940个,D可看成是在上述2940个抽屉中抽出的,则由抽屉原则,D中至少有两个元素在同一个抽屉中,则D中的元素之间有连边,所以D不是独立集。矛盾。 故:2940)(=G α。证毕。

2. 装箱销售的深入研究

厂家生产销售锁具实际上是多批的,顾客流是贯序的。在锁具装箱、标记、销售的过程中考虑到这一情况,可以采取更细致的方法方案(此方案请自行考虑),得到结论:在连续销售中,可以保证任意顾客购买不超过42箱均不会出现互开的情形。这样的讨论就更深入和符合实际了。

3. 关于顾客抱怨程度的定量描述

这个问题的灵活性较大,没有固定答案,学生有较大发挥余地,答案也是形形色色的。若用了平均互开总对数,或它的单调函数去定义抱怨函数,因此购买箱数越多,抱怨程度越大。这不太符合顾客的心理状态。其实,顾客抱怨程度与购买箱数是有关的,购买越多,自然互开的可能性越大,这是顾客预料之中的,不应有太多的抱怨,顾客所不能容忍的是在购买少量锁具时而出现互开情形。因此应把购买箱数作为一个因素考虑到抱怨函数中。理想的抱怨函数应该是:开始随购买量的增加而增加,到一定量后下降。这才更合情合理。

数学建模笔记

数学模型按照不同的分类标准有许多种类: 1。按照模型的数学方法分,有几何模型,图论模型,微分方程模型.概率模型,最优控制模型,规划论模型,马氏链模型. 2。按模型的特征分,有静态模型和动态模型,确定性模型和随机模型,离散模型和连续性模型,线性模型和非线性模型. 3.按模型的应用领域分,有人口模型,交通模型,经济模型,生态模型,资源模型。环境模型。 4.按建模的目的分,有预测模型,优化模型,决策模型,控制模型等。 5.按对模型结构的了解程度分,有白箱模型,灰箱模型,黑箱模型。 数学建模的十大算法: 1.蒙特卡洛算法(该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,比较好用的算法。) 2.数据拟合、参数估计、插值等数据处理算法(比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用matlab作为工具。) 3.线性规划、整数规划、多元规划、二次规划等规划类问题(建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用lingo、lingdo软件实现) 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 题逢山开路,山体海拔高度的插值计算,还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法,观察数据的

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

哈工大年集合论与图论试卷

-- 本试卷满分90分 (计算机科学与技术学院09级各专业) 一、填空(本题满分10分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么?(A B ?) 2.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?(22-n ) 3.在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系, 则 最大元是什么? ( 无 ) 4.设{,,}A a b c =,给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =) 5.设∑为一个有限字母表,∑上所有字(包括空字)之集记为*∑,则*∑是 否是可数集? ( 是 ) 6.含5个顶点、3条边的不同构的无向图个数为多少? ( 4 ) 7.若G 是一个),(p p 连通图,则G 至少有多少个生成树? ( 3 ) 8. 如图所示图G ,回答下列问题: (1)图G 是否是偶图? ( 不是 ) (2)图G 是否是欧拉图? ( 不是 ) (3)图G 的色数为多少? ( 4 ) 二、简答下列各题(本题满分40分) 1.设D C B A ,,,为任意集合,判断下列等式是否成立?若成立给出证明,若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ; (2)()()()()A B C D A C B D ?=??。 解:(1)不成立。例如}{,a c B D A ====φ即可。 (2)成立。(,)x y ?∈()()A B C D ?,有,x A B y C D ∈∈,即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??,有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?,从而()()A C B D ???()()A B C D ?。

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

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

集合论与图论习题册

集合论与图论习题册 软件基础教研室 刘峰 2015.02

第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的,哪些为假 a)对每个集A ,A φ∈; b)对每个集A ,A φ?; c)对每个集A ,{}A A ∈; d)对每个集A ,A A ∈; e)对每个集A ,A A ?; f)对每个集A ,{}A A ?; g)对每个集A ,2A A ∈; h)对每个集A ,2A A ?; i)对每个集A ,{}2A A ?; j)对每个集A ,{}2A A ∈; k)对每个集A ,2A φ∈; l)对每个集A ,2A φ?; m)对每个集A ,{}A A =; n) {}φφ=; o){}φ中没有任何元素; p)若A B ?,则22A B ? q)对任何集A ,{|}A x x A =∈; r)对任何集A ,{|}{|}x x A y y A ∈=∈; s)对任何集A ,{|}y A y x x A ∈?∈∈; t)对任何集A ,{|}{|}x x A A A A ∈≠∈。 答案: 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ,试证:12n A A A === 。 4.设{,{}}S φφ=,试求2S ? 5.设S 恰有n 个元素,证明2S 有2n 个元素。

16P 习题 6.设A 、B 是集合,证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合,试证A B A B φ=?=?。 9.设A ,B ,C 为集合,证明:\()(\)\A B C A B C = 。 10.设A ,B ,C 为集合,证明:()\(\)(\)A B C A C B C = 。 11.设A ,B ,C 为集合,证明:()\(\)(\)A B C A C B C = 。 12.设A ,B ,C 都是集合,若A B A C = 且A B B C = ,试证B=C 。 15.下列命题是否成立?说明理由(举例)。 (1)(\)\(\)A B C A B C = ;(2)(\)()\A B C A B C = ; (3)\()()\A B C A B B = 。(答案:都不正确)

数学建模图论模型图论

§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个顶点的网可以生成许多互不相同的生成树,每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。

集合论与图论

《集合论与图论》课程示范性教学设计 1 本课程教学方法 (一)教学方法 在这里,仅总结一下我的教学方法,不细展开,因此不涉及专业术语和与专业有关的例子。以下仅是一些指导思想: (1 )启发式、由浅入深、从直观到抽象。要用些生动的例子帮助学生理解抽象概念的含义,但要做到生动而有趣又不失概念的准确性和推理的严格性,使学生易于接受,又了解直观背景。 (2 )突出基本思想及方法,强调规律性,提高学生的抽象能力。要从哲学的高度强调概念是第一位的,引导学生思考问题时必须清楚理解所涉及的概念,使问题有一个明确的提法,引导学生掌握从问题到建立数学模型这一抽象过程的方法。 (3 )利用集合论某些概念和理论与方法总结已学过的知识(如微积分、线性代数)找出本质的规律或主线,使学生认识事物内部的深刻规律。其次,随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。这不仅提高了学习的积极性,也使学生增强了学习的目的性。 (4 )只要有可能就要以建立数学模型组织教学,讲习题也不例外。这样,能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。 (5 )鼓励学生多问为什么,为什么会是这样子而不是那个样子。不是教会学生怎样去使用工具、去模仿或复制,而是要教会学生独立思考,发现问题,提出问题和解决问题的思考,否则思维会退化。 (5 )适当地提出一些未解决的问题。尚无答案的问题是摆在我们及学生面前的有无限价值的东西,因为支持大学的最高准则是探究未知领域。事实上,在每年教此课时,提一些问题确实有学生在思考。 (6 )注意每个学科(内部)的美。如果某部分很丑或太复杂,人们倾向于认为是不清楚的和暂时的,它没有真正反映客观规律,因为我们相信,越接近终极真理,我们的解释中的不自然的东西就越少。科学是以越来越完美、有力的理论向终极真理发展的。 (二)关于素质教育、培养创新精神的人才的思考 素质教育应该是各类教育的核心,而培养创新人才则是高等教育的任务(见高等教育法,第五条)。在这里讨论这个题目不太合适,因为题太大。其实,在(五)中就本课的特点贯穿了素质教育和培养创新人才的思想。以下只扼要地总结一下。 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为自变量的个数;

《集合论与图论》课堂练习2

《集合论与图论》课堂练习3 (2013年12月18日 13:20-15:00 复旦大学计算机学院2012级) 学号姓名 一、判断下列命题是否正确,并说明理由。(括号内写“是”或“否”)(40分,每题8分,是非判断4分,证明或反例4分) 1 存在7个结点的自补图。 (否) /*西安交通大学1999*/ 自补图对应的完全图的边数必须是偶数,而7个结点的完全图的边数为21。 n≥的连通图。则G没有割点当且仅当G的剖分也没有割点。 2 设G是顶点数3 (真) 如果G的剖分有割点,则G有割点,矛盾;所以G没有割点,则G的剖分也没有割点。 如果G有割点,则该割点为G的剖分的割点,所以G的剖分有割点,矛盾;所以G的剖分也没有割点则G没有割点。 3 若G是简单连通图,边数为e,结点数为n。若e≥n,则G至少有3棵生成树。 (是) /*复旦大学1998*/ /*只需证明e=n时,命题成立*/ 若e=n-1,因为G是连通的,所以为一棵树;再添加一边时,因为G是简单图,所以图中必存在一个长度大于等于3的回路,则在这个回路上任意删除一条边就得到一棵树。 4 一个有向图D中仅有一个顶点的入度为0,其余顶点的入度均为1,则D是有根树。 (否) 一个自环和孤立点 /*北京大学1991*/ 5 设C是简单连通图G的回路,若删去C中任一边后所得到的路C’为G中的最长路,则C是图G的哈密顿回路。 (是) /*复旦大学1999*/ /*反证法证明*/ 令C的长度为m。若C不是哈密顿回路,则圈外必存在一点u,它与圈上一点v邻接(因为G是连通图)。圈上与v关联的一边为e,则C-e的长度为m-1;而C-e+uv的长度为m;得C-e不是最长路。矛盾。

数学建模常用算法模型

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

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

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

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

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

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

集合论与图论答案 第四章习题

第四章 无穷集合及其基数习题 136P 1.设A 为由序列 12,,,,n a a a 的所有项组成的集合,则是否市可数的?为什么? 解:因为序列是可以重复的,故 若A 是由有限个数组成的集合,则A 是有限的集合; 若A 是由无限个数组成的集合,则A 是可数的。 故本题A 是至多可数的。 2.证明:直线上互不相交的开区间的全体所构成的集合至多可数。 证:在每个开区间中取一个有理数,则这些有理数构成的集合是整个有理数集合Q 的子集,因此是至多可数的。 3.证明:单调函数的不连续点的集合至多可数。 证:设A 是所有不连续点的集合,f 是一个单调函数,则00,x A x ?∈对应着一个区间0((0),(0))f x f x -+,于是由上题便得到证明。 4.任一可数集A 的所有有限子集构成的集族是可数集合。 证:设1212{,,,,},{,,,},n i i ik A a a a B a a a ==则B A ?且B k =<∞。 令{,}B B A B B =?<∞, 设:{0,1}A ?→,则?是A的子集的特征函数。 ,()B B ??∈B ={0,1的有穷序列} ,即i a A ?∈, 若i a B ∈,则对应1;若i a B ?则对应0。于是 ,()B B ??∈B 就对应着一个由0,1组成的有限序列0,1,1,0,…,0,1。此序列对应着一个二进制小数,而此小数是有理数。于是,可数集A 的所有有限子集B 对应着有理数的一个子集。 又121212,,,,B B B B B B ?∈B ≠对应的小数也不同,故?是单射。而可数集A的所有有限子集B 是无穷的,故B 是可数的。

数学建模图论

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

集合论与图论(下)教学大纲

集合论与图论(下)教学大纲 《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课。本课程为后继的专业基础课及专业课提供必要的数学工具,为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力,提高学生提出问题、分析问题和解决问题的能力,提高学生的数学修养及计算机科学素质。 课程概述 要想用计算机解决问题就要为它建立数学模型,即描述研究对象及对象与对象之间的联系,并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。 本课程的目标是通过理论学习,使学生正确地理解概念,正确地使用概念进行推理,养成一个好的思维习惯,理解理论与实践的关系。引导学生观察生活、社会和大自然,分析事物间的联系,建立系统的模型,提出和解决其中的复杂工程问题。 本课程主要包含二部分内容:集合论与图论。集合论是整个数学的基础,也是计算机科学的基础,计算机科学领域中的大多数基本概念和理论,几乎均采用集合论的有关术语来描述和论证,而图论的基本知识则将始终陪伴着每一个计算机工作者的职业生涯。 计算学科以抽象、理论、设计为其学科形态,以数学方法和系统方法为其学科方法,本课程的核心目标就是在抽象和理论的基础上提供数学方法,因此,本课程是整个专业的基础课程,是计算机专业最重要的课程之一。 《集合论与图论》(上)主要讲述集合论部分,《集合论与图论》(下)主要讲述图论部分。 授课目标 课程具体目标如下: 课程目标1:掌握集合论与图论的基本概念、基本原理、基本方法等基本知识,培养形式化、模型化的抽象思维能力,使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题,逐步学会为计算类复杂工程问题建立数学模型;

数学建模指导

建模方法 接受参加数学建模竞赛赛前培训的同学大都需要学习诸如数理统计、最优化、图论、微分方程、计算方法、神经网络、层次分析法、模糊数学,数学软件包的使用等等“短课程”(或讲座) 培训中广泛地采用的讨论班方式,同学自己报告、讨论、辩论,教师主要起质疑、答疑、辅导的作用,竞赛中一定要使用计算机及相应的软件,如Spss,Lingo,Mapple, 1、蒙特卡罗算法(该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必用的方法) 2、数据拟合、参数估计、插值等数据处理算法(比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用Matlab作为工具) 3、线性规划、整数规划、多元规划、二次规划等规划类问题(建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用Lindo、 Lingo软件实现) 4、图论算法(这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备) 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法(这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中) 6、最优化理论的三大非经典算法:模拟退火法、神经网络、遗传算法(这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用) 7、网格算法和穷举法(网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具) 8、一些连续离散化方法(很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的) 9、数值分析算法(如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用) 10、图象处理算法(赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用Matlab进行处理) 竞赛参考书 l、中国大学生数学建模竞赛,李大潜主编,高等教育出版社(1998).

数学建模图论

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

相关主题
相关文档 最新文档