案例最佳灾情巡视路线学习教案.pptx

《案例最佳灾情巡视路线学习教案.pptx》由会员分享，可在线阅读，更多相关《案例最佳灾情巡视路线学习教案.pptx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学 1案例最佳灾情巡视路线第一页，编辑于星期日：十六点 二十四分。1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1 小时，汽车行驶速度V=35 公里/小时.要在24 小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.第 1 页/共 20 页第二页，编辑于星期日：十六点 二十四分。公路边的数字为该路段的公里数.第 2 页/共 20 页第三页，编辑于星期日：十六点 二十四分。2)问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图

2、的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条再回到点 O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点 O 出发，行遍所有顶点至少一次第 3 页/共 20 页第四页，编辑于星期日：十六点 二十四分。如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸 多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是 m 条众所周知，旅行售货员问题属于 NP 完全问题，显然本问题更应属于 NP 完全问题.有鉴于此，经过同一点并覆盖所有其他顶点又使边权

3、之和达到最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.第 4 页/共 20 页第五页，编辑于星期日：十六点 二十四分。6.6.最佳灾情巡视路线的模型的建立与求解问题转化为在给定的加权网络图中寻找从给定点 O 出发,行遍所有顶点至少一次再回回到点 O,使得总权(路程或时时间)最小,即最佳旅行售货员问题.第 5 页/共 20 页第六页，编辑于星期日：十六点 二十四分。最佳旅行售货员问题是 NP 完全问题,采用一种近似算法求其一个近似最优解，来代替最优解.

4、算法一 求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出 G 中任意两个顶点间的最短路,构造出完全图2)输入图 的一个初始 H 圈；3)用对角线完全算法（见23）产生一个初始圈;4)随机搜索出 中若干个 H 圈，例如2000 个；5)对第2)，3)，4)步所得的每个 H 圈，用二边逐次修正法进行优化，得到近似最优 H 圈；6)在第5)步求出的所有 H 圈中，找出权最小的一个,此即要找的最优 H 圈的近似解.因二边逐次修正法的结果与初始圈有关,故本算法第2)，3)，4)步分别用三种方法产生初始圈，以保证能得到较优的计算结果.第 6 页/共 20 页第七页，编辑于星期日：十六点 二十四分

5、。问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题.4)第 7 页/共 20 页第八页，编辑于星期日：十六点 二十四分。此问题包含两方面：a)对顶点分组,b)在每组中求(单个售货员)最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法.故 多也不第 8 页/共 20 页第九页，编辑于星期日：十六点 二十四分。而图中节点数较多，为53 个，我们只能去寻求一种较合理的划分准则，对图1 进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整，使得各部分满足均衡性条件3).从 O 点出发去其

6、它点，要使路程较小应尽量走O 点到该点的最短路.故用软件包求出O 点到其余顶点的最短路.这些最短路构成一棵O 为树根的树.将从O 点出发的树枝称为 干枝.第 9 页/共 20 页第十页，编辑于星期日：十六点 二十四分。从O 点出发到其它点共有6 条干枝，它们的名称分别为，.在分组时应遵从准则：准则1 尽量使同一干枝上及其分枝上的点分在同一组.准则2 应将相邻的干枝上的点分在同一组；准则3 尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组1:（，），（，），（，）分组2:（，），（，），（，）分组1 极不均衡,故考虑分组2.第 10 页/共 20 页第十一页，编

7、辑于星期日：十六点 二十四分。分组2:(,),(,),(,)对分组2 中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线.在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H 圈作为其第2)步输入的初始圈.第 1 1 页/共 20 页第十二页，编辑于星期日：十六点 二十四分。分组2 的近似解 第 12 页/共 20 页第十三页，编辑于星期日：十六点 二十四分。因为该分组的均衡度.所以此分法的均衡性很差.为改善均衡性，将第 组中的顶点C,2,3,D,4分给第 组（顶点2 为这两组的公共点），重新分分组后的近似最优解见表2.第 13 页/共 20 页第十四页，编辑于星期日：十六点

8、 二十四分。第 14 页/共 20 页第十五页，编辑于星期日：十六点 二十四分。因该分组的均衡度 所以这种分法的均衡性较好.问题二 当巡视人员在各乡（镇）、村的停留停留时间一定,汽车的行驶速度一定,要在24 小时内完成巡视,至少要分几组及最佳旅行的巡视路线.第 15 页/共 20 页第十六页，编辑于星期日：十六点 二十四分。由于T=2 小时,t=1 小时,V=35 公里/小时,需访问的乡镇共有17 个，村共有35 个.计算出在乡(镇)及村的总停留时间为17 2+35=69 小时，要在24 小时内完成巡回，若不考虑行走时间，有:69/i24(i 为分的组数).得 i 最小为4，故 至少要分4 组

9、.由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分4 组时各组停停留时间大约为小时，则每组分配在路路途上的时间大约为小时.而前面讨论过,分三组时有个总路程公里的巡视路线，分4 组时的总路程不会比公里大太多,不妨以公里来计算.路上约用小时,若平均分配给4 个组,每个组约需小时小小时,故分成4 组是可能办到的.第 16 页/共 20 页第十七页，编辑于星期日：十六点 二十四分。现在尝试将顶点分为4 组.分组的原则：除遵从前面准则1、2、3 外，还应遵从以下准则：准则4 尽量使各组的停留时间相等.用上述原则在下图上将图分为4 组，同时计算各组的停留时间,然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间.用算法一计计算时，初始圈的输入与分三组时同样处理.这4 组的近似最优解见表3.第 17 页/共 20 页第十八页，编辑于星期日：十六点 二十四分。第 18 页/共 20 页第十九页，编辑于星期日：十六点 二十四分。表3 符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留;加框的表示此点只经过不停留.可看出,表3 分组的均衡度很好,且完全满足24小时完成巡视的要求.该分组实际均衡度 4.62%第 19 页/共 20 页第二十页，编辑于星期日：十六点 二十四分。