图与网络数学建模
- 格式：ppt
- 大小：1.54 MB
- 文档页数：25
文档推荐
-
数学建模网络挑战赛页数:20
-
数学建模网络挑战赛第二阶段题目页数:6
-
第九届数学建模网络挑战赛A题论文页数:35
-
2023年mathorcup数学建模b题页数:2
-
2014第七届认证杯数学中国数学建模网络挑战赛第一阶段成绩初稿页数:1198
下载文档原格式
合集下载
数学建模优化问题的求解方法
数学建模优化问题的求解方法
数学建模优化问题的求解方法有很多。
下面列举几种常见的方法：
1. 数学规划方法：包括线性规划、整数规划、非线性规划、动态规划等。
这些方法通过数学模型和约束条件来描述问题，并通过寻找最优解来优化问题。
2. 图论方法：将问题抽象成图或网络，并利用图论算法来求解最优解。
常见的算法有最短路径算法、最小生成树算法、最大流算法等。
3. 近似算法：对于复杂的优化问题，往往很难找到精确的最优解。
近似算法通过寻找接近最优解的解来近似优化问题。
常见的近似算法有贪心算法、近邻算法、模拟退火算法等。
4. 遗传算法：模拟生物进化的过程，通过选择、交叉和变异等操作来搜索问题的解空间，并逐步优化解。
遗传算法适用于复杂问题和无法直接求解的问题。
5. 物理方法：将优化问题转化为物理模型，利用物理规律求解。
比如蚁群算法模拟蚂蚁找食物的行为，粒子群算法模拟鸟群觅食的行为等。
以上只是数学建模优化问题求解方法的几种常见方法，实际问题求解时要根据问题的特点选择适合的方法，并结合领域知识和实际情况进行调整和优化。
数学建模第七章图与网络方法建模-72竞赛排名
3 5
G2
8
7
6
G1 , G2 , G3 子图之间的边被简化了， 实际上两子图的
每对顶点之间都有边相连，而这些边的方向必是一致 的，否则相应的子图可以合并为更大的双向连通子竞 赛图。 在每个这样的图中按上面介绍的方法排名次，而 子图之间的名次不难由它们相连边的方向决定。例 如：G1 的名次为{1,2,4,3}，G2 的名次 5,6,7 相同，G3 只 一 个 顶 点 8 ， 故 全 部 顶 点 的 名 次 排 列 为 {1,2,4,3, （5,6,7）,8}。
1 存在从顶点i到j的有向边 aij 0 否则
1
例如：
2 4 3
的邻接矩阵为
0 0 A 0 1
1 0 0 0
1 1 0 0
0 1 1 0
(1) T S ( S , S , , S ) 记顶点的得分向量为 ，其中 Si 是 1 2 n
( 2) (1) (k ) ( k 1) k 1 (1) i S AS , , S AS A S ， 顶点 1、竞赛图 在每条边上都标出方向的图称为有向图。每 对顶点间都有一条边相连的有向图称为竞赛图。 如何由竞赛图排出顶点的名次？ （1）两个顶点的竞赛图只有一种形式
1 2
（2）三个顶点的竞赛图只有两种形式
2 2
1
3
1
3
（1）
（2 ）
对（1） ，顶名次排序为{1,2,3}；对（2） ，三个顶 点名次相同。
于是可排出名次为{1,3,2,5,4,6}。
三、其他情况（不属于 1 0 和 2 0 ）下的名次排序 对于既没有唯一完全路径，又不是双向连通的竞 赛图，通常可分解为若干个双向连通的子竞赛图。 例如下图 8 个顶点的竞赛图分解为 3 个双向连通 子竞赛图
数学建模竞赛常用算法
图是由节点（顶点）和边组成的一种数据结构，用于表示对象及 其之间的关系。
网络流概念
网络流是图论中的一个重要概念，表示在有向图中，通过边进行 传输的流量。
图的表示方法
图的常见表示方法包括邻接矩阵、邻接表和边集数组等。
图与网络基本概念
图论基础
图是由节点（顶点）和边组成的一种数据结构，用于表示对象及 其之间的关系。
在非线性规划中，凸函数和凹函数的 性质对于问题的求解和分析具有重要 意义。
局部最优解与全局最优解
非线性规划问题可能存在多个局部最 优解，而全局最优解是所有局部最优 解中目标函数值最优的解。
非线性规划基本概念
非线性规划定义
凸函数与凹函数
非线性规划是一种数学优化技术，用 于求解目标函数或约束条件为非线性 函数的优化问题。
Gomory割等。
03
迭代过程
在每次迭代中生成一个或多个割平面，将原问题转化为一个更小的子问
题，然后求解子问题并更新最优解。重复此过程直到满足终止条件。
应用案例：物流配送路径优化
问题描述
物流配送路径优化问题是指在满足一定约束条件下，寻找总成本最小的配送路径。该问题 可转化为整数规划问题进行求解。
建模方法
使用单纯形法求解该线性规划模 型，得到最优的生产计划安排。 同时，可以进行灵敏度分析以了 解不同参数变化对生产计划的影
响程度。
应用案例：生产计划优化
问题描述
某企业计划生产多种产品，每种 产品需要不同的原料和加工时间， 且市场需求和原料供应有限。如 何安排生产计划以最大化利润或
最小化成本？
建模过程
将每种产品的产量作为决策变量， 以利润或成本作为目标函数，以 市场需求、原料供应和生产能力 等作为约束条件，构建线性规划
网络流概念
网络流是图论中的一个重要概念，表示在有向图中，通过边进行 传输的流量。
图的表示方法
图的常见表示方法包括邻接矩阵、邻接表和边集数组等。
图与网络基本概念
图论基础
图是由节点（顶点）和边组成的一种数据结构，用于表示对象及 其之间的关系。
在非线性规划中，凸函数和凹函数的 性质对于问题的求解和分析具有重要 意义。
局部最优解与全局最优解
非线性规划问题可能存在多个局部最 优解，而全局最优解是所有局部最优 解中目标函数值最优的解。
非线性规划基本概念
非线性规划定义
凸函数与凹函数
非线性规划是一种数学优化技术，用 于求解目标函数或约束条件为非线性 函数的优化问题。
Gomory割等。
03
迭代过程
在每次迭代中生成一个或多个割平面，将原问题转化为一个更小的子问
题，然后求解子问题并更新最优解。重复此过程直到满足终止条件。
应用案例：物流配送路径优化
问题描述
物流配送路径优化问题是指在满足一定约束条件下，寻找总成本最小的配送路径。该问题 可转化为整数规划问题进行求解。
建模方法
使用单纯形法求解该线性规划模 型，得到最优的生产计划安排。 同时，可以进行灵敏度分析以了 解不同参数变化对生产计划的影
响程度。
应用案例：生产计划优化
问题描述
某企业计划生产多种产品，每种 产品需要不同的原料和加工时间， 且市场需求和原料供应有限。如 何安排生产计划以最大化利润或
最小化成本？
建模过程
将每种产品的产量作为决策变量， 以利润或成本作为目标函数，以 市场需求、原料供应和生产能力 等作为约束条件，构建线性规划
数学建模中的图论方法
数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题A和问题B。
一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。
由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。
因此很多人有这样的感觉，A题入手快，而B题不好下手。
另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。
但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。
命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。
这样增加了建立数学模型的难度。
但是这也并不是说无法求解。
一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。
图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。
应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。
图论方法已经成为数学模型中的重要方法。
许多难题由于归结为图论问题被巧妙地解决。
而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B－扫雪问题；AMCM91B－寻找最优Steiner树；AMCM92B－紧急修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特征向量法)CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。
这里面都直接或是间接用到图论方面的知识。
要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。
数学建模简介1
数学建模的方法和步骤
模型假设
在明确建模目的，掌握必要资料的基础上， 通过对资料的分析，根据对象的特征和建 模目的，找出起主要作用的因素，对问题 进行必要的、合理的简化，用精确的语言 提出若干符合客观实际的合理假设。
数学建模的方法和步骤
模型假设
作出合理假设，是建模至关重要的一步。 如果对问题的所有因素一概考虑，无疑是 一种有勇气但方法欠佳的行为，所以高超 的建模者能充分发挥想象力、洞察力和判 断力 ，善于辨别主次，而且为了使处理方 法简单，应尽量使问题线性化、均匀化。
看谁答得快
1、某甲早8时从山下旅店出发沿一路径上山，下 午5时到达山顶并留宿。次日早8时沿同一路径下 山，下午5时回到旅店。某乙说，甲必在两天中 的同一时刻经过路径中的同一地点，为什么？
2、两兄妹分别在离家2千米和1千米且方向相反 的两所学校上学，每天同时放学后分别以4千米/ 小时和2千米/小时的速度步行回家，一小狗以6千 米/小时的速度从哥哥处奔向妹妹，又从妹妹处奔 向哥哥，如此往返直至回家中，问小狗奔波了多 少路程？
四、模型的特点：
逼真性和可行性 渐进性 强健性 可移植性 非预测性 条理性 技艺性 局限性
五、建模能力的培养：
具有广博的知识（包括数学和各种实际知 识）、丰富的经验、各方面的能力、注意 掌握分寸。
具有丰富的想象力和敏锐的洞察力
类比法和理想化方法
直觉和灵感
实例研究法
学 习 、 分 析 别 人 的 模 型 亲 手 去 做
模型集中反映了原型中人们需要的那一部分特征
什么是数学建模
什么是数学模型？
简单地说：数学模型就是对实际问题的一种 数学表述。
具体一点说：数学模型是以部分现实世界为某 种研究目的的一个抽象的、简化的数学结构。 这种数学结构可以是数学公式、算法、表格、 图示等。
数学建模图论模型
若将图G的每一条边e都对应一个实数Fe，则称 F(e)为该边的权，并称图G为赋权图(网络), 记为 G = <V, E , F>。
任意两点均有通路的图称为连通图。
连通而无圈的图称为树，常用T=<V,E>表示树。
若图G’是图 G 的生成子图，且G’又是一棵树， 则称G’是图G 的生成树。
例 Ramsey问题
图1
图2
并且常记: V = v1, v2, … , vn, |V | = n ; E = {e1, e2, … , em}ek=vivj , |E | = m
称点vi , vj为边vivj的端点 在有向图中, 称点vi , vj分别为边vivj的 始点和终点. 该图称为n,m图
8
对于一个图G = V, E , 人们常用图形来表示它, 称其 为图解 凡是有向边, 在图解上都用箭头标明其方向.
4、P'代替P,T'代替T,重复步骤2,3
定理2 设 T为V的子集，P=V-T，设 (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的
点构成, (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即:
l(x)mli(tn )} t{ ,T
(3)令P’=P Ux,T’=T-{x},l’(t)表示T'中结点t关于P'的指标,则
解：用四维01向量表示人,狼,羊,菜例在过河西河岸问的题状态(在
岸则分量取1;否则取0)，共有24 =16 种状态; 在河东岸 态类似记作。
由题设，状态(0,1,1,0)，(0,0,1,1)，(0,1,1,1)是不允许的
其对应状态：(1,0,0,1)， (1,1,0,0)，(1,0,0,0)也是不允许
任意两点均有通路的图称为连通图。
连通而无圈的图称为树，常用T=<V,E>表示树。
若图G’是图 G 的生成子图，且G’又是一棵树， 则称G’是图G 的生成树。
例 Ramsey问题
图1
图2
并且常记: V = v1, v2, … , vn, |V | = n ; E = {e1, e2, … , em}ek=vivj , |E | = m
称点vi , vj为边vivj的端点 在有向图中, 称点vi , vj分别为边vivj的 始点和终点. 该图称为n,m图
8
对于一个图G = V, E , 人们常用图形来表示它, 称其 为图解 凡是有向边, 在图解上都用箭头标明其方向.
4、P'代替P,T'代替T,重复步骤2,3
定理2 设 T为V的子集，P=V-T，设 (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的
点构成, (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即:
l(x)mli(tn )} t{ ,T
(3)令P’=P Ux,T’=T-{x},l’(t)表示T'中结点t关于P'的指标,则
解：用四维01向量表示人,狼,羊,菜例在过河西河岸问的题状态(在
岸则分量取1;否则取0)，共有24 =16 种状态; 在河东岸 态类似记作。
由题设，状态(0,1,1,0)，(0,0,1,1)，(0,1,1,1)是不允许的
其对应状态：(1,0,0,1)， (1,1,0,0)，(1,0,0,0)也是不允许
2022年数学建模算法与应用-图与网络模型着色问题和旅行商问题
{'赵','刘','孙'};{'张','王','孙'};{'李','刘','王'}};
n = length(s); w = zeros(n);
for i = 1:n-1
for j =i+1:n
if ~isempty(intersect(s{i},s{j}))
w(i,j)=1;
end
end
end
[ni,nj] = find(w); %边的顶点编号
航空基础学院数学第教8研页室
数学建模算法与应用
第4章 图与网络模型及方法
v1
v5
v6
v3
v2
v4
图 4.14 部门之间关系图
航空基础学院数学第教9研页室
数学建模算法与应用
第4章 图与网络模型及方法
构造图G (V , E)，其中V {v1,v2 , ,v6 }，这里 v1,v2 , ,v6分别表示部门 1，部门 2，…，部门 6； E 为边集，两个顶点之间有一条边当且仅当它们代表的 委员会成员中有共同的人，如图 4.14 所示，该图可以 用 4 种颜色着色，可以看出至少要用 4 种颜色，v1,v2 ,v3 构成一个三角形，必须用 3 种颜色，v6和这 3 个顶点 都相邻，必须再用一种颜色。
w = w + w'; %计算完整的邻接矩阵
deg = sum(w); K = max(deg) %顶点的最大度
prob = optimproblem;
数学建模算法与应用
第4章 图与网络模型及方法
已知图G (V , E)，对图G 的所有顶点进行着色时， 要求相邻的两顶点的颜色不一样，问至少需要几种颜 色？这就是所谓的顶点着色问题。
数学建模十大经典算法( 数学建模必备资料)
建模十大经典算法1、蒙特卡罗算法。
该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。
2、数据拟合、参数估计、插值等数据处理算法。
比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。
3、线性规划、整数规划、多元规划、二次规划等规划类问题。
建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。
4、图论算法。
这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。
这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。
这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。
7、网格算法和穷举法。
网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8、一些连续离散化方法。
很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。
9、数值分析算法。
如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。
10、图象处理算法。
赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。
历年全国数学建模试题及解法赛题解法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在线租赁随机规划、整数规划06A 出版资源配置06B 艾滋病疗法的评价及疗效的预测 07A 中国人口增长预测 07B 乘公交，看奥运 多目标规划 数据处理 图论 08A 数码相机定位 08B 高等教育学费标准探讨09A 制动器试验台的控制方法分析 09B 眼科病床的合理安排 动态规划 10A 10B赛题发展的特点：1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B ，某些问题需要使用计算机软件，01A 。
数学建模中的图论算法及其应用研究
数学建模中的图论算法及其应用研究引言：数学建模是指利用数学方法和技巧对实际问题进行分析、抽象、描述、求解和预测的一种研究方法。
图论作为数学建模中的重要工具之一，被广泛应用于各个领域，如网络分析、交通规划、社交网络等。
本文将介绍数学建模中常用的图论算法，并探讨它们在实际问题中的应用。
一、图论基础知识1.1 图的概念图是由一些点和连接这些点的边组成的集合。
点表示图中的实体或对象，边表示实体之间的关系。
图包含了很多重要的信息，例如节点的度、连通性等。
1.2 图的表示方法图可以用邻接矩阵或邻接表来表示。
邻接矩阵是一个二维矩阵，其中的元素表示节点之间是否相连。
邻接表是一个由链表构成的数组，数组的每个元素表示一个节点，每个节点的链表存储了与该节点相连的节点列表。
二、图的遍历算法2.1 深度优先搜索（DFS）深度优先搜索是一种用于图的遍历的算法。
从一个节点出发，递归地访问它的相邻节点，直到所有可达的节点都被访问过为止。
DFS可以用于寻找连通分量、路径搜索等问题。
2.2 广度优先搜索（BFS）广度优先搜索是另一种图的遍历算法。
从一个节点出发，依次访问它的相邻节点，然后再依次访问相邻节点的相邻节点。
BFS可以用于寻找最短路径、网络分析等问题。
三、最短路径算法3.1 Dijkstra算法Dijkstra算法用于寻找图中两个节点之间的最短路径。
它基于贪心策略，从起点开始逐步扩展最短路径，直到到达终点或无法扩展为止。
Dijkstra算法在交通网络规划、电力网络优化等领域有广泛应用。
3.2 Floyd-Warshall算法Floyd-Warshall算法用于寻找图中所有节点之间的最短路径。
它通过动态规划的思想，逐步更新每对节点之间的最短路径。
Floyd-Warshall算法在地理信息系统、通信网络等领域有重要应用。
四、最小生成树算法4.1 Prim算法Prim算法用于寻找连通图的最小生成树。
它从一个起始节点开始，逐步选择与当前生成树距离最近的节点，并将其加入最小生成树中。
数学建模 四大模型总结
四类基本模型1 优化模型1.1 数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。
1.2 微分方程组模型阻滞增长模型、SARS 传播模型。
1.3 图论与网络优化问题最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。
1.4 概率模型决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。
1.5 组合优化经典问题● 多维背包问题(MKP)背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。
如何将尽可能多的物品装入背包。
多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。
如何选取物品装入背包，是背包中物品的总价值最大。
多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。
该问题属于NP 难问题。
● 二维指派问题(QAP)工作指派问题：n 个工作可以由n 个工人分别完成。
工人i 完成工作j 的时间为ij d 。
如何安排使总工作时间最小。
二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。
二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。
● 旅行商问题(TSP)旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。
● 车辆路径问题(VRP)车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。
TSP 问题是VRP 问题的特例。
● 车间作业调度问题(JSP)车间调度问题：存在j 个工作和m 台机器，每个工作由一系列操作组成，操作的执行次序遵循严格的串行顺序，在特定的时间每个操作需要一台特定的机器完成，每台机器在同一时刻不能同时完成不同的工作，同一时刻同一工作的各个操作不能并发执行。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
vn 的最短路上；否则 xij = 0 。其数学规划表达式为
min
vi v j Î E
å
n
wij xij ，
n
13/110
ì 1, i = 1, ï ï ï x ji = í - 1, i = n, s.t. 邋 xij ï j= 1 j= 1 ï vi v j 挝 E v j vi E ï ï î 0, i ¹ 1, n, xij = 0 或1.
基础部数学教研室
数学 建模
例 在 图 中 ， 用 点 表 示 城 市 ， 现 有 A, B1 , B2 , C1 , C2 , C3 , D 共 7 个城市。点与点之间的连线表 示城市间有道路相连。连线旁的数字表示道路的长度。 现计划从城市 A 到城市 D 铺设一条天然气管道， 请设计出 最小长度管道铺设方案。
在 Matlab 中无向图和有向图邻接矩阵的使用上有很 大差异。 对于有向图，只要写出邻接矩阵，直接使用 Matlab 的命令 sparse 命令， 就可以把邻接矩阵转化为稀疏矩阵的 表示方式。
7/110
基础部数学教研室
数学 建模
最短路问题:两个指定顶点之间的最短路径
问题如下，给出了一个连接若干个城镇的铁路网 络， 在这个网络的两个指定城镇间， 找一条最短铁路线。
求得 c1 到 c2 ,L , c6 的最便宜票价分别为35，45，35，25，10。
11/110
基础部数学教研室
数学 建模
clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; while sum(pb)<length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; temp2=find(d(index1)==d(temp)-a(temp,index1)); index2(temp)=index1(temp2(1)); end d, index1, index2
素的值可以很容易地查找图中任两个顶点 v i 和 v j 之间有无 边，以及边上的权值。当图的边数 m 远小于顶点数 n 时， 邻接矩阵表示法会造成很大的空间浪费。 6/110
基础部数学教研室
数学 建模
2. 稀疏矩阵表示法 稀疏矩阵是指矩阵中零元素很多，非零元素很少的矩阵。 对于稀疏矩阵，只要存放非零元素的行标、列标、非零元素 的值即可，可以按如下方式存储（非零元素的行地址，非零 元素的列地址） ，非零元素的值。
cij ；
（2）平衡条件 对于中间点，流出量＝流入量，即对于每个 i (i ¹ s, t )有 f ji = 0， 邋 fij j:( vi ,v j )挝 A j:( v j ,vi ) A
对于发点 v s ，记
邋
( v s ,v j )挝 A
f sj ( v j ,v s ) A
f js = v ( f ) ， f jt = - v ( f )，
9/110
基础部数学教研室
数学 建模
在 v 进入 S i 之前的标号 l (v )叫 T 标号， v 进入 S i 时的标号 l (v ) 叫 P 标号。 （1）令 l ( u0 ) = 0 ，对 v ¹ u0 ，令 l (v ) = ? ， S0 = {u0 }， i = 0 。 （2）对每个 v Î Si （ Si = V \ Si ） ，计算 l (v ) = min{l (v ), l ( u) + w( uv )}
12/110
基础部数学教研室
数学 建模
两个指定顶点之间最短路问题的数学规划模型
假设有向图有 n个顶点， 现需要求从顶点 v1到顶点 vn 的最短路。设W = ( wij )n´ n 为邻接矩阵，其分量为 ì ï 边v i v j的权值 , v i v j Î E , ï wij = í ï 其它, ï î¥ , 决策变量为 xij ，当 xij = 1，说明弧 vi v j 位于顶点 v1至顶点
7 个城市间的连线图
14/110
基础部数学教研室
数学 建模
model: sets: cities/A,B1,B2,C1,C2,C3,D/; roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1, B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; endsets data: w=2 4 3 3 1 2 3 1 1 3 4; enddata n=@size(cities); !城市的个数;
构 造 赋 权 图 G = ( V , E, W ， ) 其 中 顶 点 集
V={ 1 vL ,
n
, v，这里 } v1 ,L , vn 表示各个小城镇，E 为边的
集合，邻接矩阵W = ( wij )n´ n ，这里 wij 表示顶点 v i 和 v j 之 间 直 通 铁 路 的 距 离 ， 若 顶 点 vi 和 v j 之 间 无 铁 路 ， 则 问题就是求赋权图G 中指定的两个顶点 u0 , v0 间 wij = ? 。 的具有最小权的路。这条路叫做 u0 , v0 间的最短路，它的 权叫做 u0 , v0 间的距离，亦记作 d ( u0 , v0 ) 。
2/110
基础部数学教研室
数学 建模
图的基本概念
所谓的图，直观地讲就是在平面上 n 个点，把其中的 一些点对用曲线或直线连接起来， 不考虑点的位置与连线 曲直长短，这样形成一个关系结构就是一个 图。记成 G = (V , E )，V 是以上述点为元素的顶点集， E 是以上述 连线为元素的边集。
3/110
uÎ Si
这里 w(uv )表示顶点 u 和 v 之间边的权值。计算 min{l (v )} ，把达
v Î Si
到这个最小值的一个顶点记为 ui + 1 ，令 Si + 1 = Si U {ui + 1 }。 （3）若 i = | V | - 1，停止；若 i < | V | - 1，用 i + 1代替 i ，转（2） 。 算法结束时，从 u0 到各顶点 v 的距离由 v 的最后一次标号
l (v )给出。
注：Dijkstra算法，权值不能为负（Bellman）。
10/110
基础部数学教研室
数学 建模
例 某公司在六个城市 c1 , c2 ,L , c6 中有分公司，从 c i 到 c j 的直接航程票价记在下述矩阵的 ( i , j )位置上。 （¥ 表 示无直接航路） ，请帮助该公司设计一张城市 c1 到其它城 市间的票价最便宜的路线图。 轾 0 50 ¥ 40 25 10 犏 犏 50 0 15 20 ¥ 25 犏 犏 ゥ 15 0 10 20 犏 犏 40 20 10 0 10 25 犏 犏 25 ¥ 20 10 0 55 犏 犏 10 25 ¥ 25 55 0 臌
所谓网络上的流，是指定义在弧集合 A 上的一个函
17/110
数 f = { f ij } = { f (vi , v j )}，并称 f ij 为弧(vi , v j )上的流量。
基础部数学教研室
2 满足下列条件的流 f 称为可行流 （1）容量限制条件：对每一弧 (vi , v j ) Î A ， 0 ＃ f ij
求得最短铺设方案是铺设 AB1 , B1C1 , C1 D 段，最短铺 设长度为 6。
15/110
基础部数学教研室
数学 建模
每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。 具体方法是： 每次以不同的顶点作为起点， 用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n - 1次这样的操作，就可得到从每一个顶点到其它 顶点的最短路径。这种算法的时间复杂度为 O( n3 ) 。第二 种解决这一问题的方法是由 Floyd, R. W.提出的算法，称 之为 Floyd 算法。
16/110
基础部数学教研室
数学 建模
网络最大流问题
1. 网络与流 定义 4.1 给一个有向图 D = (V , A)，其中 A 为弧集， 在V 中指定了一点，称为发点（记为 v s ） ，和另一点，称 为收点（记为 v t ） ，其余的点叫中间点，对于每一个弧 ，称为 (vi , v j ) Î A，对应有一个 c(vi , v j ) ³ 0（或简写为 cij ） 弧的容量。通常我们就把这样的有向图 D 叫作一个网络， 记作 D = (V , A, C )，其中 C = {cij }。
8/110
基础部数学教研室
数学 建模
求最短路已有成熟的算法， 如迪克斯特拉 （Dijkstra） 算法， 其基本思想是按距 u0 从近到远为顺序， 依次求得 u0 到G 的各顶点的最短路和距离，直至 v0（或直至G 的所有 顶点） ， 算法结束。 为避免重复并保留每一步的计算信息， 采用了标号算法。下面是该算法。
min=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#n: @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i))); @sum(roads(i,j)|i #eq#1:x(i,j))=1; @sum(roads(i,j)|j #eq#n:x(i,j))=1; end
min
vi v j Î E
å
n
wij xij ，
n
13/110
ì 1, i = 1, ï ï ï x ji = í - 1, i = n, s.t. 邋 xij ï j= 1 j= 1 ï vi v j 挝 E v j vi E ï ï î 0, i ¹ 1, n, xij = 0 或1.
基础部数学教研室
数学 建模
例 在 图 中 ， 用 点 表 示 城 市 ， 现 有 A, B1 , B2 , C1 , C2 , C3 , D 共 7 个城市。点与点之间的连线表 示城市间有道路相连。连线旁的数字表示道路的长度。 现计划从城市 A 到城市 D 铺设一条天然气管道， 请设计出 最小长度管道铺设方案。
在 Matlab 中无向图和有向图邻接矩阵的使用上有很 大差异。 对于有向图，只要写出邻接矩阵，直接使用 Matlab 的命令 sparse 命令， 就可以把邻接矩阵转化为稀疏矩阵的 表示方式。
7/110
基础部数学教研室
数学 建模
最短路问题:两个指定顶点之间的最短路径
问题如下，给出了一个连接若干个城镇的铁路网 络， 在这个网络的两个指定城镇间， 找一条最短铁路线。
求得 c1 到 c2 ,L , c6 的最便宜票价分别为35，45，35，25，10。
11/110
基础部数学教研室
数学 建模
clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;a(4,5)=10;a(4,6)=25;a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; while sum(pb)<length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; temp2=find(d(index1)==d(temp)-a(temp,index1)); index2(temp)=index1(temp2(1)); end d, index1, index2
素的值可以很容易地查找图中任两个顶点 v i 和 v j 之间有无 边，以及边上的权值。当图的边数 m 远小于顶点数 n 时， 邻接矩阵表示法会造成很大的空间浪费。 6/110
基础部数学教研室
数学 建模
2. 稀疏矩阵表示法 稀疏矩阵是指矩阵中零元素很多，非零元素很少的矩阵。 对于稀疏矩阵，只要存放非零元素的行标、列标、非零元素 的值即可，可以按如下方式存储（非零元素的行地址，非零 元素的列地址） ，非零元素的值。
cij ；
（2）平衡条件 对于中间点，流出量＝流入量，即对于每个 i (i ¹ s, t )有 f ji = 0， 邋 fij j:( vi ,v j )挝 A j:( v j ,vi ) A
对于发点 v s ，记
邋
( v s ,v j )挝 A
f sj ( v j ,v s ) A
f js = v ( f ) ， f jt = - v ( f )，
9/110
基础部数学教研室
数学 建模
在 v 进入 S i 之前的标号 l (v )叫 T 标号， v 进入 S i 时的标号 l (v ) 叫 P 标号。 （1）令 l ( u0 ) = 0 ，对 v ¹ u0 ，令 l (v ) = ? ， S0 = {u0 }， i = 0 。 （2）对每个 v Î Si （ Si = V \ Si ） ，计算 l (v ) = min{l (v ), l ( u) + w( uv )}
12/110
基础部数学教研室
数学 建模
两个指定顶点之间最短路问题的数学规划模型
假设有向图有 n个顶点， 现需要求从顶点 v1到顶点 vn 的最短路。设W = ( wij )n´ n 为邻接矩阵，其分量为 ì ï 边v i v j的权值 , v i v j Î E , ï wij = í ï 其它, ï î¥ , 决策变量为 xij ，当 xij = 1，说明弧 vi v j 位于顶点 v1至顶点
7 个城市间的连线图
14/110
基础部数学教研室
数学 建模
model: sets: cities/A,B1,B2,C1,C2,C3,D/; roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1, B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; endsets data: w=2 4 3 3 1 2 3 1 1 3 4; enddata n=@size(cities); !城市的个数;
构 造 赋 权 图 G = ( V , E, W ， ) 其 中 顶 点 集
V={ 1 vL ,
n
, v，这里 } v1 ,L , vn 表示各个小城镇，E 为边的
集合，邻接矩阵W = ( wij )n´ n ，这里 wij 表示顶点 v i 和 v j 之 间 直 通 铁 路 的 距 离 ， 若 顶 点 vi 和 v j 之 间 无 铁 路 ， 则 问题就是求赋权图G 中指定的两个顶点 u0 , v0 间 wij = ? 。 的具有最小权的路。这条路叫做 u0 , v0 间的最短路，它的 权叫做 u0 , v0 间的距离，亦记作 d ( u0 , v0 ) 。
2/110
基础部数学教研室
数学 建模
图的基本概念
所谓的图，直观地讲就是在平面上 n 个点，把其中的 一些点对用曲线或直线连接起来， 不考虑点的位置与连线 曲直长短，这样形成一个关系结构就是一个 图。记成 G = (V , E )，V 是以上述点为元素的顶点集， E 是以上述 连线为元素的边集。
3/110
uÎ Si
这里 w(uv )表示顶点 u 和 v 之间边的权值。计算 min{l (v )} ，把达
v Î Si
到这个最小值的一个顶点记为 ui + 1 ，令 Si + 1 = Si U {ui + 1 }。 （3）若 i = | V | - 1，停止；若 i < | V | - 1，用 i + 1代替 i ，转（2） 。 算法结束时，从 u0 到各顶点 v 的距离由 v 的最后一次标号
l (v )给出。
注：Dijkstra算法，权值不能为负（Bellman）。
10/110
基础部数学教研室
数学 建模
例 某公司在六个城市 c1 , c2 ,L , c6 中有分公司，从 c i 到 c j 的直接航程票价记在下述矩阵的 ( i , j )位置上。 （¥ 表 示无直接航路） ，请帮助该公司设计一张城市 c1 到其它城 市间的票价最便宜的路线图。 轾 0 50 ¥ 40 25 10 犏 犏 50 0 15 20 ¥ 25 犏 犏 ゥ 15 0 10 20 犏 犏 40 20 10 0 10 25 犏 犏 25 ¥ 20 10 0 55 犏 犏 10 25 ¥ 25 55 0 臌
所谓网络上的流，是指定义在弧集合 A 上的一个函
17/110
数 f = { f ij } = { f (vi , v j )}，并称 f ij 为弧(vi , v j )上的流量。
基础部数学教研室
2 满足下列条件的流 f 称为可行流 （1）容量限制条件：对每一弧 (vi , v j ) Î A ， 0 ＃ f ij
求得最短铺设方案是铺设 AB1 , B1C1 , C1 D 段，最短铺 设长度为 6。
15/110
基础部数学教研室
数学 建模
每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用 Dijkstra 算法。 具体方法是： 每次以不同的顶点作为起点， 用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反 复执行 n - 1次这样的操作，就可得到从每一个顶点到其它 顶点的最短路径。这种算法的时间复杂度为 O( n3 ) 。第二 种解决这一问题的方法是由 Floyd, R. W.提出的算法，称 之为 Floyd 算法。
16/110
基础部数学教研室
数学 建模
网络最大流问题
1. 网络与流 定义 4.1 给一个有向图 D = (V , A)，其中 A 为弧集， 在V 中指定了一点，称为发点（记为 v s ） ，和另一点，称 为收点（记为 v t ） ，其余的点叫中间点，对于每一个弧 ，称为 (vi , v j ) Î A，对应有一个 c(vi , v j ) ³ 0（或简写为 cij ） 弧的容量。通常我们就把这样的有向图 D 叫作一个网络， 记作 D = (V , A, C )，其中 C = {cij }。
8/110
基础部数学教研室
数学 建模
求最短路已有成熟的算法， 如迪克斯特拉 （Dijkstra） 算法， 其基本思想是按距 u0 从近到远为顺序， 依次求得 u0 到G 的各顶点的最短路和距离，直至 v0（或直至G 的所有 顶点） ， 算法结束。 为避免重复并保留每一步的计算信息， 采用了标号算法。下面是该算法。
min=@sum(roads:w*x);
@for(cities(i)|i #ne#1 #and# i #ne#n: @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i))); @sum(roads(i,j)|i #eq#1:x(i,j))=1; @sum(roads(i,j)|j #eq#n:x(i,j))=1; end