2013春 数学实验 实验四：图与网络优化.doc

1．求下图中a到各顶点的最短距离和最短路径？ ? 故最短距离分别为：0，2，8，15，3，Inf，24，11，4，25，20 最短路径为：a ( b: a ( b a ( c: a ( c a ( d: a ( c ( d a ( e: a ( b ( e a ( f: a ( f a ( g: a ( c ( d ( g a ( h: a ( b ( e ( i ( h a ( i: a ( b ( e ( i a ( j: a ( c ( d ( g ( j a ( k: a ( b ( e ( I ( h ( k 2．一辆货车从水泥厂运水泥至某建筑工地。如图，图中a表示水泥厂所在处，f为建筑工地所在处，图中弧旁括弧内的数字，第一个数表示两点间距离，第二个数表示两点间汽车行驶所需时间。试分别依据最短距离和最少行驶时间确定水泥厂至某建筑工地的汽车行驶路线？ ? 最短距离的路径为：a c f 最短时间的路径为： a c f 选作题 某企业使用一种设备，每年年初，决定是购置新的，还是继续用旧的。若购置新设备，则需付一定的购置费用；若继续使用旧设备，则需付一定的维修费用。假设该企业在第一年开始时必须购置一台这种设备，并假设计划使用这种设备的时间为五年。下面给出一台新设备的价格以及一台设备的使用维修费用： 从第1年到第5年的设备价格（单位：千元） 年号 1 2 3 4 5 价格 11 11 12 12 13 不同使用年限的设备的维修费（单位：千元） 使用年限 0-1 1-2 2-3 3-4 4-5 维修费 5 6 8 11 18 这家企业希望确定应在哪一年购买一台新设备，使得维修费和新设备的购置费的总和最小。 可见从第一年到第六年维修费和新设备的购置费的总和最小的“路径”为： ⑴ ⑶ ⑹ 故确定应在第三年购买花费总和最小。 【实验小结与收获】 这次实验虽然算法理解起来不是很容易，但对于应用起来还算简单，虽然其中需要计算。这种图形的最短距离（时间、花费等）优化在实际生活中有着广泛的应用。 但是应该清楚的是，最小路径不唯一，上面求出的路径只是其中之一。当然对于Dijkstra算法和Kruskal算法理解还不彻底，自己尝试过独立编写这两个程序，可惜没能成功。 【附①】Dijkstra算法的MATLAB程序 年级、专业 数学与应用数学2011级 姓名 学号 名单序号 实验时间 2013年 4 月 26 日 MATLAB版本： R2010b 注：实验报告的最后一部分是实验小结与收获 实验四 图与网络优化 2013春 数学实验 实验四 图与网络优化 1 / 4 第一题程序执行结果如下 第二题程序（最短距离）结果如右所示： 第二题程序（最短时间）结果如右所示：