网络最小支撑树与最短路.doc

数学实验报告实验序号： 日期： 年 月 日班级姓名学号实验名称网络最小支撑树与最短路问题背景描述：有9点 S、A1 、A2 、A3 、B1 、B2 、C1 、C2 ，各点之间的路程如下图所示，各点到T的最短路。56774968658336C1B1C2B2A1A2A3TS6实验目的：1. 理解图与网络分析的研究背景，理解网络图的最小支撑树、两点之间最短路等基础概念，并加强对网络最小支撑树、最短路等问题求解方法的基本思想，求解计算过程的具体步骤等内容的理解和掌握；2 掌握用Matlab求解最小支撑树、两点之间最短路的方法和步骤，学会利用Matlab求解最小支撑树、两点之间最短路及其变形问题。3.锻炼应用所学知识解决综合性问题的能力实验原理与数学模型：图与网络分析是运筹学一个重要分支。网络图具有直观形象、便于分析理解的特点。实际生活中的很多问题都可以转化为一个网络图来进行分析求解，网络图具有鲜明的实际背景和广泛的应用。因此，网络图的建模和分析是极具特色的一个知识板块。最小支撑树和最短路问题是网络图分析中的两类典型问题，受到研究人员的广泛关注，给出很多求解分析算法。我们教材中介绍了典型的破边法、加边法，以及标号算法。这些方法便于人们操作，可以方面的求解小规模问题。但它们不太适合计算机实现，也难以用于中大规模问题求解。计算机进行图与网络分析的时候，引入了一些新的概念和方法，这些方法与课本介绍的方法相比有不同的特色。两者对比分析，可以进一步加深我们对问题及其求解过程的认识，同时也可引发一些有意义的思考。实验所用软件及版本：1.安装win98系统以上的计算机 2.malab6.0或更高版本的软件主要内容（要点）：1 复习运筹学实验指导书第二章，课本运筹学基础及应用第二章，复习巩固线性规划模型及其求解的方法步骤；2 复习课本运筹学基础及应用第六章，熟悉图与网络分析的基础概念和最小支撑树、最短路问题的建模及求解的方法和步骤；3 学习运筹学实验指导书第八章。实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）：建立数学模型：表格一 各点间的原始权矩阵：SA1A2A3B1B2C1C2TS063316035A23086A33074B1387067B2564089C16805C27906T560表格二 线路矩阵原始：SA1A2A3B1B2C1C2TS023456789A110345678A2120456789A313056789B1123406789B2123450789C1123456089C2123456709T123456780（转下页）实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页）：运用MATLAB软件对模型进行求解： 在上述表格一中要求第 行 列上的数必需满足 ，当 时 ，同时而表格二的中 ，直到所有的 都满足条件 。在MATLAB中中实现编程如下（具体程序见附录）for m=1:9 for j=1:9 for i=1:9 if a(i,j)a(m,i)+a(j,m) a(i,j)=a(m,i)+a(j,m); b(i,j)=m; end end endend得到两个新矩阵既是计算结果。运用MATLAB软件中的for if函数对所得结果进行分析得：各点间相互到达的最短路程如下表：SA1A2A3B1B2C1C2TS0633107151620A1609965121317A2390686141519A3396074121317B1106870116711B275641108913C115121412680115C21613151379106T201719171113560由上表格可以知道 点到个点（以S、A1 、A2 、A3 、B1 、B2 、C1 、C2为顺序）间的距离：d = 0 20 17 19 17 11 13 5 6且各点之间的最短路线所经过点如下图：SA1A2A3B1B2C1C2TS023444667A1101156557A2110156557A3111056667B1423402787B2423420787C1655656099C265565