数学建模模最短路

基于最短路问题的研究及应用令狐采学

姓名：Fanmeng

学号：

指导老师：

摘要

最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。

关键字数学建模最短路问题Dijkstra算法水渠修建。

目录

第一章．研究背景1

第二章．理论基础2

2.1 定义2

2.2 单源最短路问题Dijkstra求解:2

2.2.1 局限性2

2.2.2 Dijkstra算法求解步骤2

2.2.3 时间复杂度2

2.3 简单样例3

第三章．应用实例4

3.1 题目描述4

3.2 问题分析4

3.3符号说明4

3.4 模型假设5

3.5模型建立与求解5

3.5.1模型选用5

3.5.2模型应用及求解5

3.6模型评价5

第四章. 参考文献5

第五章．附录6

第一章．研究背景

在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

第二章．理论基础

2.1 定义

最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。

2.2 单源最短路问题Dijkstra 求解: 2.2.1局限性

Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。

2.2.2Dijkstra 算法求解步骤

(1).先给图中的点进行编号，确定起点的编号。 (2).得到图的构成，写出写出图的矩阵

0000(,)(,)

(,)

(,)

n n n n u u u u G u u u u

=

(3).根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合

unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点；

(4).利用这个顶点来松弛其它和它相连的顶点距离S 的值

(5).重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。

2.2.3时间复杂度

时间复杂度达到

2

()O N

2.3简单样例

给出对应的结点之间的关系

注释：其中（A,B）= 2 表示结点A到B 的长度为2第一步：进行编号，假定A点即为起点。

第二步：得到图

02151010

201115

15110207

1012003

105730

G=

第三步：首先从起点A开始找到距离A最近的点，那就是A点了；

第四步：把A点标记到已经用过的的集合

{}

vist A

=用A来更新其它点

{,,,}

unvist B C D E

=到起点的距离得到的集合

dist =

02151010

A B C D E

表示起点到B,C,D,E的距离分别为2,15,10,10

第五步：重复上述步骤：得到

{,}

vist A B

=,{,,}

unvist C D E

=,

dist =

021337

A B C D E

继续重复上述步骤，最后的到

{,,,,}

vist A B C D E

=,unvist=?,得到的

dist =

021336

A B C D E

，

即最短路求解完毕。

第三章．应用实例

3.1 题目描述

农村的孩子应该都会听到大人们经常谈论这样的问题-------修建水渠。在我们北方采用深井灌溉，所以说修建水渠更加普遍，因为一般都是水渠直接引流到田地旁边。经常一些土地需要开发，在这个过程中，我们需要能够将在某一个地点的水源引流到新建的田地里面，这个过程很麻烦，有时候大家很激动的去引流，结果最后修建的水渠并不能满足要求，往往浪费了大量的物力人力和财力，所以现在我们要设计一定的数学模型来帮助农民来规划一下，如何修建的水渠最优，并且给出修建的路径。通常是通过步长来估计两个点之间的长度，我们通常可以这样理解，每两步可以认为是1米。给出的点之间的关系描述关系为（其他因素先可以不用考虑）：

注：A表示的是总的进水口，其余字母表示的是每块田地的进水口的位置,这只是部分数据。

3.2 问题分析

问题是让我们来规划一下水渠该如何来修建的问题，并且已经知道了出水口所在的位置，并且简单的知道了一些点之间的距离，让我们帮农民找到一条最优的水渠来完成引流工作。既然给出的是关于长度的问题，那么长度一定是很重要的标记量了，那么我们只需要找到一条从总出水到某一块地的修建的距离最短即可。

3.3符号说明

3.4 模型假设

假设其余条件不会影响水渠修建，比如土壤硬度

假设水渠宽度不会对水流量造成影响即水渠内的流量会满足要求

3.5模型建立与求解

3.5.1模型选用

最短路模型最短路模型解决的就是图论中任意两点之间的最短路问题。

3.5.2模型应用及求解

我们的指标是

（X,Y） = min(x,y) | x

∈∈

{{,....},{,,...}}

L A B y A B

首先对数据进行抽取，得到我们所需要的数值，并把它存储到矩阵G这应该是一个9*9的矩阵，其次我们可以按照最短路的模型使用Dijkstra算法来进行求解，得到的值便是S到任一点的最短距离值，最后按照路径还原的思想还原修建的路径即可。3.6模型评价

最短路模型的是行能够较好的解决单源最短路径问题，可以较好的模拟出路径修建，得到的一定是最短的路径，能够达到预期要求的效果，得到的最终结果如附录里“3.

应用实例结果输出”所示

第四章.参考文献

[1]. 韩中庚著，《数学建模方法与应用》，高等教育出版社

[2].

[3].[美] Frank R.Giordano著《数学建模》（原书第五版）

[4].刘晓妍著《基于最短路的设备更新问题的数学建模》河南教育学院学报(自然科学版) 第22卷第四期2013年12月

[5].杨启帆、边馥萍著，《数学模型》，浙江大学出版社

第五章．附录

1.应用实例矩阵

0111200300400500600

102342573

12010611121314

131001001234 G

20046100010203040

3002111100506060

4005122205002334

5007133306023012

6003144406034120

2.应用实例C++程序

#include

#include

#include

#include

#include

#include

#include

#include

usingnamespacestd;

constdouble INF = 0xFFFFFFF;

constint MAX_N = 10005;//表示最大有顶点10005个；

intn,m;//表示有n个结点；给出了m条边

double G[MAX_N][MAX_N];//用邻接矩阵来从这个图

doubledist[MAX_N];//表示起点到当前点的最短距离

boolvist[MAX_N];

intprev[MAX_N];

vector getpath(int t){ //路径还原可变长数组类型

vector path;

for(; t !=-1; t =prev[t]){

path.push_back(t);

}

reverse(path.begin(),path.end());

return path;

}

voidDijkstra(int s){//求得最短路径

dist[s]= 0;

while(true){

int v =-1;

double mx = INF;

for(inti= 1;i<= n;i++){//挑选出未被标记集合最短的点

if(!vist[i]&& mx >dist[i]){

mx=dist[i];

v =i;

}

}

if(v ==-1){

break;

}

vist[v]=true;

for(inti= 1;i<= n;i++){ //用当前的到的值来松弛其他不在标记的集合中的值if(!vist[i]&&dist[i]>dist[v]+G[v][i]){

dist[i]=dist[v]+G[v][i];

prev[i]= v;

}

}

}

}

voidinit(){ //初始化值

for(inti= 1;i<= n;i++){

for(int j = 1; j <= n; j++){

G[i][j]= INF;

G[i][i]= 0;

}

dist[i]= INF;

vist[i]=false;

prev[i]=-1;

}

}

int main(){

freopen("data.in","r",stdin);//默认数据读入用data.in

freopen("data.out","w",stdout);//输出默认到data.out

cin>> n;

init();

for(inti= 1;i<= n;i++){

for(int j = 1; j <= n; j++){

cin>> G[i][j];

}

}

Dijkstra(1);

for(inti= 1;i<= n;i++){

printf("出水口到目标点%d 的最短距离= %.0f\n",i,dist[i]);

vector q =getpath(i);

printf("目标点%d 的路径为\n",i);

printf("%d",q[0]);

for(inti= 1;i<(int)q.size();i++){

printf("-> %d ",q[i]);

}

printf("\n");

}

return 0;

}

3.应用实例结果输出

出水口到目标点1 的最短距离= 0

目标点1 的路径为

1

出水口到目标点2 的最短距离= 1

目标点2 的路径为

1-> 2

出水口到目标点3 的最短距离= 1

目标点3 的路径为

1-> 3

出水口到目标点4 的最短距离= 1

目标点4 的路径为

1-> 4

出水口到目标点5 的最短距离= 5

目标点5 的路径为

1-> 2 -> 5

出水口到目标点6 的最短距离= 2

目标点6 的路径为

1-> 4 -> 6

出水口到目标点7 的最短距离= 3

目标点7 的路径为

1-> 4 -> 7

出水口到目标点8 的最短距离= 4

目标点8 的路径为

1-> 4 -> 8

出水口到目标点9 的最短距离= 4

目标点9 的路径为

1-> 2 -> 9

数学建模实验报告第十一章最短路问答

实验名称：第十一章最短路问题 一、实验内容与要求 掌握Dijkstra算法和Floyd算法，并运用这两种算法求一些最短路径的问题。 二、实验软件 MATLAB7.0 三、实验内容 1、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。 V1 1 V2 3 V3 1 V5 6 V6 V4 2 V7 4 V8

程序： function y=bijiaodaxiao(f1,f2,f3,f4) v12=1;v23=3;v24=2;v35=1;v47=2;v57=2;v56=6;v68=3;v78=4; turn=3; f1=v12+v23+v35+v56+turn+v68; f2=v12+v23+v35+turn+v57+turn+v78; f3=v12+turn+v24+turn+v47+v78; f4=v12+turn+v24+v47+turn+v57+turn+v56+turn+v68; min=f1; if f2

f4 实验结果： v1到v8的最短时间路径为15，路径为1-2-4-7-8. 2、求如图所示中每一结点到其他结点的最短路。V110 V3V59 V6

floy.m中的程序： function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end R for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)

数学建模模最短路

基于最短路问题的研究及应用 ： Fanmeng 学号： 指导老师：

摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题 Dijkstra算法水渠修建。

目录 第一章．研究背景 (1) 第二章．理论基础 (2) 2.1 定义 (2) 2.2 单源最短路问题Dijkstra求解: (2) 2.2.1 局限性 (2) 2.2.2 Dijkstra算法求解步骤 (2) 2.2.3 时间复杂度 (2) 2.3 简单样例 (3) 第三章．应用实例 (4) 3.1 题目描述 (4) 3.2 问题分析 (4) 3.3符号说明 (5) 3.4 模型假设 (5) 3.5模型建立与求解 (5) 3.5.1模型选用 (5) 3.5.2模型应用及求解 (5) 3.6模型评价 (5) 第四章. 参考文献 (6) 第五章．附录 (7)

第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

数学建模运输问题

运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线： 1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,) i j(,1,,10) i j=位置上的数表示（其中∞表示两个客户之间无直接的路线到达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送 货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个 客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。 3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小

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

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

数学建模模最短路

基于最短路问题的研究及应用令狐采学 姓名：Fanmeng 学号： 指导老师：

摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题Dijkstra算法水渠修建。

目录 第一章．研究背景1 第二章．理论基础2 2.1 定义2 2.2 单源最短路问题Dijkstra求解:2 2.2.1 局限性2 2.2.2 Dijkstra算法求解步骤2 2.2.3 时间复杂度2 2.3 简单样例3 第三章．应用实例4 3.1 题目描述4 3.2 问题分析4 3.3符号说明4 3.4 模型假设5 3.5模型建立与求解5 3.5.1模型选用5 3.5.2模型应用及求解5 3.6模型评价5 第四章. 参考文献5 第五章．附录6

第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

第二章．理论基础 2.1 定义 最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。 2.2 单源最短路问题Dijkstra 求解: 2.2.1局限性 Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。 2.2.2Dijkstra 算法求解步骤 (1).先给图中的点进行编号，确定起点的编号。 (2).得到图的构成，写出写出图的矩阵 0000(,)(,) (,) (,) n n n n u u u u G u u u u = (3).根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合 unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点； (4).利用这个顶点来松弛其它和它相连的顶点距离S 的值 (5).重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。 2.2.3时间复杂度 时间复杂度达到 2 ()O N

数学建模运筹学模型一

运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 或更简洁地表为 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 或更简单地写为 3.运输问题模型 运输问题也是一种线性规划问题，只是决策变量设置为双下标变量.假如问题具有m 个产地和n 个销地，第i 个产地用A i 表示，其产量为a i （i =1，2，…，m ），第j 个销地用B j 表示，其销量为b j （j =1，2，…，n ），从A i 运往B j 的运价为c ij ， 而 ∑∑===m i n j j i b a 11表示产销平衡.那么产销平衡运输问题的一般模型可以写成为 4.目标规划模型 某工厂生产代号为Ⅰ、Ⅱ的两种产品，这两种产品都要经甲、乙两个车间加工，并经检验与销售两部门处理.已知甲、乙两车间每月可用生产工时分别为120小时和150小时，每小时费用分别为80元和20元，其它数据如下表 表4-1 问题分析与模型假设 经与工厂总经理交谈，确定下列几条：

浅谈最短路的数学模型解问题

浅谈最短路的数学模型解问题 在生产与科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整个过程达到最好的活动效果。因此，各个阶段的决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作一个前后关联且具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题，而最短路问题是这类问题中的比较典型的一种。 现在我们一起来探讨这类问题的特点和解决方法。 问题1（最小价格的管道铺设方案） 如下图 用点表示城市，现有共7个城市。点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市A到城市D铺设一条天然气管道，请设计出最小价格管道铺设方案。 首选我们要明确以下2点： （1）管道长短与成本价格之间有什么关系？显然，管道越短，成本越低。 （2）你能在众多管道路线中找到一条最短的管道路线吗？答案是肯定的。这是一般人都有的最直接最原始的思路。 我们在这里就是要寻找一个比较简便的方法。 本题的实质就是求从城市A到城市D的一条最短路。 1、建立数学模型： Min{d（xk，xk+1）+f（xk+1）}的含义是： 前一个阶段距离加上后一状态变量到终点的最短距离，然后在这些距离和中取最小者，即为所求的最短距离。 其中xk+1=u（xk），即从状态xk出发，采取决策uk到达下一状态xk+1； Sk表示从状态xk 出发的所有可能选取的决策的集合； 而f4（x4）=0称为边界条件，因为状态x4=D已经是终点；

最短路径问题数学模型

问题重述： 现准备在7 个居民点v 1, v 2, … , v7中设置一银行.问设在哪个点, 最合理？要建2个银行呢？ 解：先作出距离矩阵,如下: D （0）=???????????? ??????????????0 1.5 ∞ ∞ ∞ ∞ ∞ v7 1.5 0 4 ∞ ∞ 2.5 ∞ v6∞ 4 0 3 2 18 ∞ v5∞ ∞ 3 0 6 ∞ ∞ v4∞ ∞ 2 6 0 2 ∞ v3∞ 2.5 18 ∞ 2 0 3 v2∞ ∞ ∞ ∞ ∞ 3 0 v1 v7 v6 v5 v4 v3 v2v1 然后对k=1,2,3…,n 依次利用算法原理中第n 步递归公式，由已知的D n-1各元素确定D n 的各元素值。插入v 1后D （1）的个元素和相应的最短路径因为对成性，D （1）的第一行元素和第一列元素与D (0)相同，D （1）的主对角线上的元素均为0，所以只需要计算其余15个元素的值： D 23(1)=min{d 23(0),d 21(0)+d 13(0)}=min{2,3+∞}=2 D 24(1)=min{d 24(0),d 21(0)+d 14(0)}=min{∞,3+∞}=3 D 25(1)=min{d 25(0),d 21(0)+d 15(0)}=min{18,3+∞ }=3

D 26(1)=min{d 26(0),d 21(0)+d 16(0)}=min{2.5,3+∞}=2.5 D 27(1)=min{d 27(0),d 21(0)+d 17(0)}=min{∞,3+∞}=3 D 34(1)=min{d 34(0),d 31(0)+d 14(0)}=min{6,∞+∞}=6 D 35(1)=min{d 35(0),d 31(0)+d 15(0)}=min{2,∞+∞}=2 D 36(1)=min{d 36(0),d 31(0)+d 16(0)}=min{∞,∞+∞}=∞ D 37(1)=min{d 37(0),d 31(0)+d 17(0)}=min{∞,∞+∞}=∞ D 45(1)=min{d 45(0),d 41(0)+d 15(0)}=min{3,∞+∞}=3 D 46(1)=min{d 46(0),d 41(0)+d 16(0)}=min{∞,∞+∞}=∞ D 47(1)=min{d 47(0),d 41(0)+d 17(0)}=min{∞,∞+∞}=∞ D 56(1)=min{d 56(0),d 51(0)+d 16(0)}=min{4,∞+∞}=4 D 57(1)=min{d 57(0),d 51(0)+d 17(0)}=min{∞,∞+∞}=∞ D 67(1)=min{d 67(0),d 61(0)+d 17(0)}=min{1.5,∞+∞}=1.5 由此可知 D （1）=?? ? ? ??? ?? ? ? ???????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞0 1.5 3 1.5 0 4 2.5 4 0 3 2 3 3 0 6 3 2 6 0 2 3 2.5 3 3 2 0 3 3 0,依次插入中间点v 2,v 3,v 4,v 5,v 6,v 7 可得不断更新的距离矩阵为：

数学建模最短时间路径

最短时间路径 摘要：本问题是一个最短时间问题，本文首先对路线图进行分析，找出并画出了汽车在拐弯时所消耗时间的等效图，经分析，找到四条规则（具体见：五、模型的建立与求解），可以按这四条规则把转弯的时间算在南北走向的路线上，对图形上数据进行处理，然后通过Dijkstra算法求的从入口点v1到出口点的v8最短时间路径为：v1——>v2——>v4——>v7——>v8，时间为：15。 关键词：最短路径Dijkstra算法 一、问题重述 在一个城市交通系统中取出一段如下图所示，其入口为定点v1，出口为定点v8，每条弧段的数字表示通过该路段所需的时间，每次转弯需要附加时间为3，求v1到V8的最短时间路径。（看图时，以上下为北南，左右为西东，那么城市路线分为南北路线、东西路线） （图一） 二、问题分析 本问题是最短路模型，所求为从城市的一定点（入口点）到另一定点（出口点）所需时间最少路径。由于每次转弯时要耽搁一定时间为3，所以必须对图形及数据进行等效处理易便找出最短时间路径。于是就有以下猜想和分析看法： 1.是否可以把转弯的的时间附加在某条路线上，假如可以的，那么应该加在出口点的那几条路线上（例如图一的v7---v8与v6---v8这两条路）还是其他路线上. 2.若加在出口点的那几条路线上，那么应在v7---v8 加6而在v6---v8应加3或15（5个拐弯）这样就可以解决此题，但是对于稍微复杂一点交通路线图这种做法就不科学了。 3.由于每次拐弯要附加一定的时间消耗，而城市路线以2条东西路线为主，南北3条路线使东西2条路线相同，那么是否可以把转弯的时间统一加在南北路线上，经分析是可行的，而且有一定的规则（具体见：五、模型的建立与求解） 问题的关键: 1.找到把转弯时间附加在南北路线的内在规则。 2.找到一个等效的图形（等效的办法）使得求解更为方便。 三、模型假设 1.无论何时交通路线是可行的。 2.城市的路线均为方行路线（直线图）。

数学建模送货线路设计问题答案仅供参考

装订线 第九届西安电子科技大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目 A (B)题 剪切线 通信工程学院第队

送货路线设计问题 1、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。 现在送货员要将100件货物送到50个地点。请完成以下问题。 1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可

不考虑中午休息时间。 2、问题分析 送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。 图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。 对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解 对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。 3、模型假设与符号说明 、模型的假设 （1）、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物（2）、要求达到不超过的时间不包括此次在该点交易的时间。 （3）、所用的距离数据都精确到米而时间则精确到 （4）、同一地点有多件货物也简单按照每件3分钟交接计算。 、符号说明

最短路数学建模

题 目：最短路问题 摘要： 1 引言： 图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。 最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 （1） 基 本 概 念： 定义１ 在无向图G=(V,E,ψ)中： （1）顶点与边相互交错且i i i v v e 1)(-=ψ (i=1,2,…k)的有限非空序列 )(12110k k k v e v e v e v w -= 称为一条从0v 到k v 的通路，记为k v v W 0 （２）边不重复但顶点可重复的通路称为道路，记为k v v T 0 （３）边与顶点均不重复的通路称为路径，记为k v v P 0

A=4 3 21 432105375083802720v v v v v v v v ??????? ? ?∞∞ 定义２ （１）任意两点均有路径的图称为连通图． （２）起点与终点重合的路径称为圈． （３）连通而无圈的图称为树． 定义３ （１）设P(u,v)是赋权图G 中从u 到v 的路径， 则称∑∈= ) ()()(P E e e w P w 为路径P 的权． (2) 在赋权图G 中，从顶点u 到顶点v 的具有最小权的路 ),(*v u P ，称为u 到v 的最短路． 1.实验的目的和要求 了解最短路的算法及应用，会用Matlab 软件求最短路。 2.实验内容和原理 内容:最短路求法,求下图从顶点1u 到其余顶点的最短路。

数学建模模最短路

基于最短路问题的研究及应用 姓名： Fanmeng 学号： 指导老师：

摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题 Dijkstra算法水渠修建。

目录 第一章．研究背景 (1) 第二章．理论基础 (2) 定义 (2) 单源最短路问题Dijkstra求解: (2) 局限性 (2) Dijkstra算法求解步骤 (2) 时间复杂度 (2) 简单样例 (3) 第三章．应用实例 (4) 题目描述 (4) 问题分析 (4) 符号说明 (5) 模型假设 (5) 模型建立与求解 (5) 模型选用 (5) 模型应用及求解 (5) 模型评价 (5) 第四章. 参考文献 (6) 第五章．附录 (7)

第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

第二章．理论基础 定义 最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。 单源最短路问题Dijkstra 求解: 局限性 Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。 Dijkstra 算法求解步骤 (1). 先给图中的点进行编号，确定起点的编号。 (2). 得到图的构成，写出写出图的矩阵 0000(,)(,) (,)(,) n n n n u u u u G u u u u = (3). 根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中 vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点； (4). 利用这个顶点来松弛其它和它相连的顶点距离S 的值 (5). 重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。 时间复杂度 时间复杂度达到 2 ()O N