数学建模图论

图论

一．最短路问题

问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。

将问题抽象为赋权有向图或无向图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初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。然后以新纳入的点为起点继续搜索，直到所有的点遍历。

Matlab代码：

Dijk.m

function[mydistance,mypath]=Dijk(a,sb,db);%sb为起点，db为终点

n=size(a,1);visited(1:n)=0;%n为结点数 visited为结点标号

distance(1:n)=inf;distance(sb)=0;%起点到各终点距离的初始化

visited(sb)=1;u=sb;%u为新的P标号顶点（初始点）

parent(1:n)=0;%父节点的初始化

%经过以下一个for..end便可以找到最短路径及该最短路径对应的最短路程

for i=1:n-1%(找所有未标号的点)

id=find(visited==0);%查找未标号的顶点

for v=id %找到一个未标号的点v

if a(u,v)+distance(u)

distance(v)=distance(u)+a(u,v);%修改标号值则v到原点的距离（权）修改。 parent(v)=u; %u是v的父节点

end

end

temp=distance;%以上面的distance作为临时的最小距离，如果下一次循环的未标号顶点有更小的距离则替换

temp(visited==1)=inf;%已标号的点距离换为无穷，避免再次搜索

[t,u]=min(temp);%找出距离最小的点（t是最小值，u是最小值的下标）最后一次循环会得到一个最小距离的点

visited(u)=1;%标记已经标号的顶点

end

%下面一段代码用于输出path

mypath=[];%定义mypath为一个空矩阵

if parent(db)~=0%如果存在路 ~=为不等于即前面有parent点

t=db;%终点标号赋给t

mypath=[db]%将终点放入路径集合里

while t~=sb%当终点不是初始点

P = parent(t);%终点的父节点令为P

mypath=[P mypath];

t=P;%把上一个点的父节点令为下一轮循环的节点，继续搜索父节点

end

end

mydistance=distance(db);%最短路程

main.m

n=29; a=zeros(n);

a(1,2)=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131;

a(2,3)=2;

a(3,4)=2;

a(4,5)=2;

a(5,6)=2;

a(6,7)=2;a(6,22)=35;

a(7,8)=2;

a(8,9)=2;

a(9,10)=2;

a(11,12)=2;

a(12,13)=2;

a(13,14)=2;a(13,20)=108;

a(14,15)=2;

a(15,16)=2;

a(16,29)=41;

a(17,18)=2;

a(18,19)=2;a(18,23)=309; a(18,21)=134;

a(19,20)=2;

a(20,24)=145;a(20,27)=281;a(20,26)=206;

a(21,24)=24;

a(22,25)=60;a(22,28)=142;

a(23,27)=126;

a(24,26)=145;

a(26,29)=77;

a(28,29)=115;

a=a+a';

a(a==0)=inf; %把所有零元素替换成无穷

a([1:n+1:n^2])=0; %对角线元素替换成零，Matlab中数据是逐列存储的

for i=1:10

[mydistance,mypath] = Dijk( a,21,i );%从公交南北到A1-A10的最短路径mypath

end

二．floyed 算法：

2.1基本思想：直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν个矩阵(1)D 、(2)D 、… 、()v D ，使最后得到的矩阵()v D 成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。

2.2基本原理

2.2.1求距离矩阵

把带权邻接矩W 作为距离矩阵的初值，即(0)(0)

()ij v v D d W ?==

(1)(1)(1)()ij v v D d ?=，其中(1)(0)(0)(0)11min{,}

ij ij i j d d d d =+ (1)

ij

d 是从i v 到j v 的只允许1v 作为中间点的路径中最短路的长度 (2)(2)(2)()ij v v D d ?=，其中(2)(1)(1)(1)22min{,}

ij ij i j d d d d =+ (2)

ij

d 是从i v 到j v 的只允许1v 、2v 作为中间点的路径中最短路的长度 %解释：(1)ij d 为从1i j v v v →→；(1)(1)

22i j d d +为从12i

j v v v v →→→ …

(v )()()()v v ij v v D d ?=，其中()(1)(1)(1)

min{,}v v v v ij ij iv vj d d d d ---=+

()

v ij

d 是从i v 到j v 的只允许1v 、2v ……v v 作为中间点的路径中最短路的长度，即是从i v 到j v 中间可插入任何顶点的路径中最短路的长，因此()D v 即是距离矩阵。

2.2.2求路径矩阵

在建立距离矩阵的同时可建立路径矩阵R

()ij v v R r ?=，ij r 的含义是从i v 到j v 的最短路要经过点号为ij r 的点

(0)(0)()ij v v R r ?=，(0)ij r j = %初值

每求得一个()k D 时，按下列方式产生相应的新的()k R

(1)(1)(1)

()

(1)

k k k ij ik kj k ij k ij

k d d d r r ----?>+?

=???若否则 即当k v 被插入任何两点间的最短路径时，被记录在()k R 中，依次求()v R 时求得()v D ，可由()v R 来查找任何点对之间最短的路径

2.2.3查找最短路径

若()1v ij r p =，则点1p 是点i 到点j 的最短路的中间点。 然后用同样的方法再分头查找。若：

(1)向点i 追溯得：12()()()

23,,,k

v v v ip ip ip k r p r p r p ===L (2)向点j 追溯得：12()()()12,,,m v v v p j p j q j

r q r q r j ===L

步骤：

k 32112m

(,)D i j ：i 到j 的距离 (,)R i j ：i 到j 之间的插入点 输入：带权邻接矩阵(,)w i j (1) 赋初值：

对所有,,(,)(,),(,),1i j d i j w i j r i j j k ←←←

(2)

更新(,),(,)d i j r i j

对所有,i j ，

若(,)(,)(,)d i k d k j d i j +<，则(,)(,)(,),(,)d i j d i k d k j r i j k ←+← (3)

若k v =，停止。否则1k k ←+，转(2)

Matlab代码：

floyed.m

%输出最短距离矩阵和最短路径矩阵function [d,r]=floyd(w)

n=length(w);

for i=1:n

for j=1:n

d(i,j)=w(i,j);

r(i,j)=j;

end

end

for k=1:n

for i=1:n

for j=1:n

if d(i,k)+d(k,j)

d(i,j)=d(i,k)+d(k,j); r(i,j)=k;

end

end

end

end

myfloyed.m

%输入起点终点得到最短路径和最短距离

%可用循环求多个距离

function [dist,mypath]=myfloyd(a,sb,db);

%a为邻接矩阵；a(i,j)为顶点i到j的直达距离，可以是有向的

%sb起点，db终点

% dist最短路距离 mypath最短路径

n = size(a,1);path=zeros(n);%初始化

for k=1:n %遍历每个点

for i=1:n

for j=1:n %遍历每两点之间的距离

if a(i,j)>a(i,k)+a(k,j) %如果i,j距离大于从i到k加上从k到j的距离

a(i,j)=a(i,k)+a(k,j) %则i,j距离被更新

path(i,j)=k; %k点加入最短路径

end

end

end

end

dist = a(sb,db);

%打印path

parent = path(sb,:); %起点到终点最短路上各顶点的父亲点

parent(parent==0)=sb; %如果父亲点为0则表示该顶点为起点

mypath=db;t=db; %终点放入路径中

while t~=sb %但某点的父亲点不是不是初始点时，继续循环

p = parent(t); %把该点的父亲点赋给p

mypath = [p,mypath]; %把p加入path中

t = p; %把p作为新的点继续循环找父亲点的父亲点

end

可测试数据：

n=29; a=zeros(n);

a(1,2)=2;a(1,10)=2;a(1,13)=180;a(1,20)=216;a(1,27)=131; a(2,3)=2;

a(3,4)=2;

a(4,5)=2;

a(5,6)=2;

a(6,7)=2;a(6,22)=35;

a(7,8)=2;

a(8,9)=2;

a(9,10)=2;

a(11,12)=2;

a(12,13)=2;

a(13,14)=2;a(13,20)=108;

a(14,15)=2;

a(15,16)=2;

a(16,29)=41;

a(17,18)=2;

a(18,19)=2;a(18,23)=309; a(18,21)=134;

a(19,20)=2;

a(20,24)=145;a(20,27)=281;a(20,26)=206;

a(21,24)=24;

a(22,25)=60;a(22,28)=142;

a(23,27)=126;

a(24,26)=145;

a(26,29)=77;

a(28,29)=115;

a=a+a';

a(a==0)=inf; %把所有零元素替换成无穷

a([1:n+1:n^2])=0; %对角线元素替换成零，Matlab中数据是逐列存储的% for i=1:10

[d,r]=floyd(a)%从公交南北到A1-A10的最短路径

% end

二．最小生成树

在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。

1.Prim 算法（贪心算法）

图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

构造连通赋权图()=,,G V E W 的最小生成树(W 是邻接矩阵)，设置两个集合

P 和Q ，其中P 用于存放G 的最小生成树中的顶点，集合Q 存放G 的最小生成

树中的边。

令集合P 的初值为{}1=P v (即初始(出发)点为1v )，集合Q 的初值为Q =?(空集)。

算法思想：从,p P v V P ∈∈-的边中，选取具有最小权值的边pv ，将顶点v 加入集合P 中，将边pv 加入集合Q 中，如此不断重复，直到P V =时，最小生成树构造完毕，这时集合Q 中包含了最小生成树的所有边。

算法过程： ②

{}1P v =，Q =?。

②while ~P V =

找最小边pv ，其中,p P v V P ∈∈-；

{}{}P P v Q Q pv =+=+；

；

end

代码：

clc

clear all;

%初始化邻接矩阵

a = zeros(7);

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

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

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

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

a(5,6)=70;

a=a+a';

a(a==0)=inf;

%算法主体

result = []; %定义一个空集放结果

p=1;tb=2:length(a); %p为起点tb为下一个点

while size(result,2)~=length(a)-1 %size(result,2)取矩阵result的第二列

temp = a(p,tb); %所有以1为起点的权值

temp = temp(:); %temp=temp(:)把所有的元素都拿出来，从左到右一列一列的拿，变为一列。

d = min(temp); %最小权值

[jb,kb] = find(a(p,tb)==d,1); %找出起点集到终点集的最小权值的下一个点（第一个）所在位置：行jb和列kb

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

result = [result,[j;k;d]];

p = [p,k];

tb(find(tb==k))=[];

end

.

Kruskal 算法：

从边出发，从所有的边当中选一条最小的边（如果最小的边不止一条，则任选一条即可）然后判断这条边的两个端点是否在同一棵树中（并查集判断），如果已经在同一棵树中，则舍去这条边，因为在这之前已经有一条比这条还短的边连接这两个节点了，如果不在，则把这两个节点连到一棵树中，并且记录下这条边，以此类推，直到边数达到1n -，此时n 个点已经在同一棵树中了，算法结束。

输入： 图G

输出： 图G 的最小生成树 具体流程：

(1)选()1e E G ∈，使得1e 是权值最小的边

(2)若12,...,i e e e 已选好，则从(){}12,,...,i E G e e e -中选取1i e +，使得 ①{}121,,...,,i i e e e e +中无圈；

②1i e +是(){}12,,...,i E G e e e -中权值最小的边。 (3)直到选得1V e -为止

.

代码：

clc

clear all;

%初始化邻接矩阵

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

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

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

a(4,[5,6]) = [50,30]; %邻接矩阵另一种输入方式

a(4,7) = 42;a(5,7) = 70;

[i,j,b]= find(a); %a中非零值

data = [i';j';b']; %存放所有非零值位置及值

index = data(1:2,:); %存放非零的两点

loop = length(a)-1;

result = [];

%算法主体

while length(result)

temp = min(data(3,:)); %权值最小

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

flag = flag(1);

v1 = index(1,flag); %权值最小两点的第一个点

v2 = index(2,flag); %权值最小两点的第二个点

if v1~=v2 %如果两点不是同一个点

result = [result,data(:,flag)]; %加入结果集中

end

index(find(index == v2)) = v1; %让两个端点相同，则后面搜索时不再被选

data(:,flag) = [];

index(:,flag) = [];

end

result

三．网络最大流

在一定条件下，求解给定系统的最大流量。

应用背景：铁路运输系统中的车辆流，城市给排水系统的水流问题，控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。

为解决该问题，首先引入一些必要的概念： 1.网络与流

给一个有向图(),D V A =，其中A 为弧集，在V 中指定了一点，称为发点（记为s v ），另一点称为收点（记为t v ），其余的点叫中间点，对于每一条弧(),i j v v A ∈，对应有一个(,)0i j c v v ≥（或简写为ij c ），称为弧的容量。通常把这样的有向图D 叫做一个网络，记为(),,D V A C =，其中{}ij C c =。

所谓网络上的流，是指定义在弧集合{}{}(,)ij i j f f f v v ==，并称ij f 为弧

(),i

j

v v 上的流量。

2.可行流与最大流

满足下列条件的流f 称为可行流： （1）

容量限制条件：对每一弧

(),0i

j

ij

ij v v A f c ∈≤≤，

。

（2） 平衡条件：对于中间点，流出量=流入

量，即对于每个(),i i s t ≠，有

:(,):(,)0i j j i ij ji j v v A

j v v A

f f ∈∈-=∑∑ ，

对于发点s v ，记

:(,):(,)()s j j s sj js j v v A

j v v A

f f v f ∈∈-

=∑∑

，

对于收点t v ，记

:(,):(,)()t j j t tj jt j v v A

j v v A

f f v f ∈∈-

=-∑

∑

，

式中：()v f 为这个可行流的流量，即发点的净输出量。 可行流总是存在的，如零流。

最大流问题可以写为如下的线性规划模型：

():(,):(,)max (),

(),,

(),,.0,,,

0,,i j j i ij

ji j v v A j v v A ij ij i j v f v f i s f f v f i t s t i s t f c v v A ∈∈?=???

-=-=????≠??

?≤≤?∈?∑∑ 3.增广路

给定一个可行流{}ij f f =，把网络中使ij ij f c =的弧称为饱和弧，使ij ij f c <的弧称为非饱和弧。把0ij f =称为零流弧，0ij f >的弧称为费零流弧。

若μ是网络中联接发点s v 和收点t v 的一条路，定义路的方向是从s v 到t v ，则路上的弧被分为两类：一类是弧的方向与路的方向一致，称为前向弧，前向弧的全体即为+μ；另一类弧与路的方向相反称为后向弧，后向弧的全体称为μ-。

定义：设f 是一个可行流， μ是从s v 到t v 的一条路，若μ满足：前向弧是非饱和弧，后向弧是非零流弧，则称μ为（关于可行流f ）一条增广路。

Ford-Fulkerson 算法流程：

其中，每个顶点x v 的标号值有两个，第一个标号值表示在可能的增广路上，

x v 的前驱顶点；x v 的第二个编号值记为δ，标志在可能的增广路上可以调整的流

量。初始化给发点s v 标号()0∞，，对已标号顶点x v 的邻接顶点按以下规则标号：

①若(),x y v v A ∈，且xy xy f c >时，令{}min ,y xy xy x c f δδ=-，则给顶点y v 标号为(),x y v δ，若xy xy f c =，则不给顶点y v 标号。

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

里第一个标号值x v -，表示在可能的增广路上，(),y x v v 为反向弧；若0yx f =，则不给y v 标号。

增流过程： ① 令y t v v =。

②

若y v 的标号为(),x t v δ，则xy xy t f f δ=+；

若y v 的标号为(),x t v δ-，则yx yx t f f δ=-。

Ford_Fulkerson.m

%n表示节点数，C表示容量矩阵

function [f,wf,No]=Ford_Fulkerson(n,C)

for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f为零流

for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号

while(1)

No(1)=n+1;

d(1)=Inf; %给发点vs 标号

while(1)pd=1; %标号过程

for(i=1:n)if(No(i)) %选择一个已标号的点vi

for(j=1:n)if(No(j)==0&f(i,j)

No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;

if(d(j)>d(i))d(j)=d(i);end

elseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当 vjvi 为非零流弧

时

No(j)=-i;d(j)=f(j,i);pd=0;

if(d(j)>d(i))d(j)=d(i);end;end;end;end;end

if(No(n)|pd)break;end;end %若收点vt得到标号或者无法标号, 终止标号过程

if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止

dvt=d(n);t=n; %进入调整过程, dvt 表示调整量

while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整

if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t的标号为vs 时, 终止调整过程

t=No(t);

end;

end; %继续调整前一段弧上的流f

wf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量

f %显示最大流

wf %显示最大流量

No %显示标号, 由此可得最小割, 程序结束

输入：

C = [];

n = ；

四．最小费用最大流

最小费用最大流问题是经济学和管理学的一类典型的基本问题。在一个网络中每条路径都存在“容量”和“费用”两个限制条件，此类问题是想寻找出：车辆从A 地到B 地，选择合适的路径及考虑分配路径的流量，使其能够在流量最大的前提下，达到所用的费用最小的要求。假设n 辆卡车要从A 地到B 地运送物品，由于每条路段都存在不同的收费情况，每条路能容纳的车的数量也有一定限制，最小费用最大流问题指如何分配卡车的出发路径可以使费用降到最低，物品又能准确全部的送达。物流成本最小问题称为最小费用流问题，在现实生活中有很多的应用，一般把其归为一类网络优化问题。可以把容量作为流，费用作为时间代价，来研究交通运输问题。

最小费用最大流算法包含很多经典的算法和流程，本文主要采用最大流算法和最小费用最大流对偶算法。

1.

模型的建立

给定网络()=,,,,,N V E c w s t ，每一条弧上(),i j v v 属于E ，除了已给容量ij c 外，还给了一个单位流量的费用(),0i j w v v ≥（简记为ij w ）。所谓最小费

用最大流问题就是要求一个最大流f 是N 的一个可行流，p 为s v 到t v （关于流f ），使得流的总输送费用取最小值。

()ij ij w f w f =∑

2．对偶法求解最小费用最大流问题

定义：已知网络()=,,,,,N V E c w s t ，f 是N 的一个可行流，p 为s v 到t v （关于流f ）的可增广路径，称()()()ij ij w p w p w p +-=-∑∑为路径p 的费用。

若*p 是从s v 到t v 所有可增广路径中费用最小的路径，则称*p 为最小费用可增广路径。

定理：若f 是流量为()v f 的最小费用流，p 是关于f 的从s v 到t v 的一条最小费用可增广路径，则f 经过p 调整流量Q 得到新的可行流'f （记为'f f Q =+）

，一定是流量为()v f Q +的可行流中的最小费用流。 3.对偶法的基本思路

① 取{}0f =

②

寻找从s v 到t v 的一条最小费用可增广

路径p 。

若不存在p ，则f 为N 中的最小费用最大流，算法结束。

若存在p ，则用求最大流的方法将f 调整成*f ，使(*)()v f v f Q =+，并将*f 赋值给f ，转②

n=6;

C=[0 8 0 7 0 0

0 0 9 5 0 0

0 0 0 2 0 5

0 0 0 0 9 0

0 0 6 0 0 10

0 0 0 0 0 0 ]; %弧容量

b = [0 2 0 8 0 0

0 0 2 5 0 0

0 0 0 1 0 6

0 0 0 0 3 0

0 0 4 0 0 7

0 0 0 0 0 0 ]; %弧容量

wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值

for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流

while(1)

for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图

for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);

elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);

elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end

for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值

for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路

for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;en d

if(pd)break;end;end %求最短路的Ford 算法结束

if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费

dvt=Inf;t=n; %进入调整过程, dvt 表示调整量

while(1) %计算调整量

if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量

elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量

if(dvt>dvtt)dvt=dvtt;end

if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量

t=s(t);end %继续调整前一段弧上的流f

pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于

预定的流

t=n;while(1) %调整过程

if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整

elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整

if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程

t=s(t);end

if(pd)break;end%如果最大流量达到预定的流量值

wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量

zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用f %显示最小费用最大流

wf %显示最小费用最大流量

zwf %显示最小费用, 程序结束

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

（数学建模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

数学建模笔记

数学模型按照不同的分类标准有许多种类: 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）理解理解差分方程的基本概念、减肥问题的建模思想。 第六章稳定性模型

数学建模中的图论方法

数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题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 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的

数学建模模拟题,图论,回归模型,聚类分析,因子分析等 (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/7815199944.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）解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.

关于数学建模的几个问题

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

数学建模图论

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

数学建模图论

图论 一．最短路问题 问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 将问题抽象为赋权有向图或无向图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分钟)

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