数学建模基础知识.ppt

文档介绍：数学建模基础知识
第1页，共71页，编辑于2022年，星期六
我们介绍三种优化模型：
图论
动态优化
排队论
重点：图论模型的数学建模案例分析
第2页，共71页，编辑于2022年，星期六
基本方法
机理分析
测 v0到0～6各顶点的距离
{0} {1,2,3,4,5,6} {0,4,6,6,∞,∞,∞}
{0,1} {2,3,4,5,6} {0,4,5,6,11,∞,∞}
{0,1,2} {3,4,5,6} {0,4,5,6,11,9,∞}
{0,1,2,3} {4,5,6} {0,4,5,6,11,9,19}
{0,1,2,3,5} {4,6} {0,4,5,6,10,9,17}
{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}
{0,1,2,3,5,4,6} {} {0,4,5,6,10,9,16}
则v0到v1～v6各顶点的最短距离分别为4、5、6、10、9和16。
第13页，共71页，编辑于2022年，星期六
狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：
void Dijkstra(int cost[][MAXV],int n,int v0)
{ int dist[MAXV],path[MAXV]; int s[MAXV];int mindis,i,j,u;
for (i=0;i<n;i++)
{ dist[i]=cost[v0][i]; /*距离初始化*/
s[i]=0; /*s[]置空*/
if (cost[v0][i]<INF) /*路径初始化*/
path[i]=v0;
else
path[i]=-1;
}
s[v0]=1;path[v0]=0; /*源点编号v0放入s中*/
第14页，共71页，编辑于2022年，星期六
for (i=0;i<n;i++) /*循环直到所有顶点的最短路径都求出*/
{ mindis=INF;
u=-1;
for (j=0;j<n;j++) /*选取不在s中且具有最小距离的顶点u*/
if (s[j]==0 && dist[j]<mindis)
{ u=j; mindis=dist[j]; }
s[u]=1; /*顶点u加入s中*/
for (j=0;j<n;j++) /*修改不在s中的顶点的距离*/
if (s[j]==0)
if (cost[u][j]<INF && dist[u]+cost[u][j]<dist[j])
{ dist[j]=dist[u]+cost[u][j]; path[j]=u; }
}
Dispath(dist,path,s,n,v0); /*输出最短路径*/
}
第15页，共71页，编辑于2022年，星期六
void Ppath(int path[],int i,int v0) /*前向递归查找路径上的顶点*/
{ int k;
k=path[i];
if (k==v0) return; /*找到了起点则返回*/
Ppath(path,k,v0); /*找k顶点的前一个顶点*/
printf("%d,",k); /*输出k顶点*/
}
第16页，共71页，编辑于2022年，星期六
void Dispath(int dist[],int path[],int s[],int n,int v0)
{ int i;
for (i=0;i<n;i++)
if (s[i]==1)
{ printf(“从%d到%d的最短路径长度为:
%d\t路径为:",v0,i,dist[i]);
printf("%d,",v0); /*输出路径上的起点*/