线路的优化模型.doc

《数学模型》课程结业论文 线路的优化模型 任 务 书 [要求] 1、将所给的问题翻译成汉语； 2、给论文起个题目（名字或标题） 3、根据任务来完成数学模型论文； 4、论文书写格式要求按给定要求书写； 5、态度要认真，要独立思考，独立完成任务； 6、论文上交时间：6月1日前（要求交纸质论文和电子文档）。 7、严禁抄袭行为，若发现抄袭，则成绩记为“不及格”。 [任务] 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 　 成 绩 评 定 单 评语： 成绩 任课教师签字 年 月 日 摘 要 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解，最短树结构模型给出了局部寻优的原则，算法模型体，算法模型体现了由简到繁，确保较优的思想；而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上，我们的结果也是比较令人满意的，如对第一题给了总长599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 关键词：关键词1；关键词2；关键词3；关键词4 目 录 1 第1级标题 1 1.1 第2级标题 1 1.1.1 第3级标题 1 1.1.2 第3级标题 2 1.2 第2级标题 2 1.2.1 第3级标题 3 1.2.2 第3级标题 3 1.2.3 第3级标题 4 1.3 第2级标题 4 参考文献 13 附录Ⅰ程序清单 16 论文正文： 正文所含内容： 1．标题： 2．问题提出（问题重述）： 3．模型假设 4．模型的建立： 5．模型求解（算法设计和计算机实现）： 6．结果（数据、图形）。 7．结果分析和检验（如误差分析、统计检验、灵敏性检验）： 8．优缺点，改进方向： 9．参考文献 10．附录（程序、更多的计算结果、复杂的推导、证明等）。 标题： 线路的优化模型 问题提出 1998年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各17个乡（镇）、35个村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 (1) 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 (2) 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 (3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 (4) 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 问题重述 本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小. 本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题. 众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式