文档介绍：数学建模基础知识
第一页，课件共71页
我们介绍三种优化模型：
图论
动态优化
排队论
重点：图论模型的数学建模案例分析
第二页，课件共71页
基本方法
机理分析
测试分析
根据对客观事物特性的认识，
找出反映内部机理的数量规律
将研究对象看作“黑箱”,通过对量测数据
的统计分析，找出与数据拟合最好的模型
二者结合
机理分析建立模型结构,测试分析确定模型参数
数学建模的方法和步骤
第三页，课件共71页
数学建模的一般步骤
模型准备
模型假设
模型构成
模型求解
模型分析
模型检验
模型应用
第四页，课件共71页
一、图论方法
最短路问题
两个指定顶点之间的最短路径—给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线（Dijkstra算法）
每对顶点之间的最短路径（Dijkstra算法、Floyd算法）
最小生成树问题
连线问题—欲修筑连接多个城市的铁路设计一个线路图，使总造价最低（prim算法、Kruskal算法）
图的匹配问题
人员分派问题：n个工作人员去做n份工作，每人适合做其中一份或几份，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？(匈牙利算法)
第五页，课件共71页
遍历性问题
中国邮递员问题—邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线
最小费用最大流问题
在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案
第六页，课件共71页
（1）基本概念
（2）固定起点的最短路
（3）每对顶点之间的最短路
1、最短路问题
第七页，课件共71页
基本概念
第八页，课件共71页
固定起点的最短路
从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上的权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。
第九页，课件共71页
从一个顶点到其余各顶点的最短路径

问题：给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。
第十页，课件共71页