建模案例:最佳灾情巡视路线 这里介绍1998年全国大学生数学模型竞赛B题中的两个问题 问题 今年夏天某县遭受水灾为考察灾情、组织自救,县领导决定,带领有关部门 负责人到全县各乡(镇)、村巡视巡视路线指从县政府所在地出发,走遍各乡 (镇)、村,又回到县政府所在地的路线 1.若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的路线 2.假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间仁=1小 时,汽车行驶速度V=35公里小时要在24小时内完成巡视,至少应分几组;给 出这种分组下最佳的巡视路线 乡镇、村的公路网示意图见图11 ⊙乡(镇)AB,R 0村12.35 图11-9 假设 1.汽车在路上的速度总是一定,不会出现抛铺等现象 2.巡视当中,在每个乡镇、村的停留时间一定,不会出现特殊情况而延误时间; 3.每个小组的汽车行驶速度完全一样 4.分组后,各小组只能走自己区内的路,不能走其他小组的路,除公共路外 三、模型的建立与求解
建模案例：最佳灾情巡视路线 这里介绍 1998 年全国大学生数学模型竞赛 B 题中的两个问题. 一、问 题 今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门 负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡 （镇）、村，又回到县政府所在地的路线. 1． 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线. 2． 假定巡视人员在各乡（镇）停留时间 T=2 小时，在各村停留时间 t=1 小 时，汽车行驶速度 V=35 公里/小时.要在 24 小时内完成巡视，至少应分几组；给 出这种分组下最佳的巡视路线. 乡镇、村的公路网示意图见图 11-9. 图 11-9 二、 假 设 1．汽车在路上的速度总是一定，不会出现抛锚等现象； 2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间； 3．每个小组的汽车行驶速度完全一样； 4．分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外. 三、模 型 的 建 立 与 求 解
将公路网图中,每个乡(镇)或村看作图中的一个节点,各乡(镇)、村之 间的公路看作图中对应节点间的边,各条公路的长度(或行驶时间)看作对应边 上的权,所给公路网就转化为加权网络图,问题就转化为在给定的加权网络图中 寻找从给定点O出发,行遍所有顶点至少一次再回到O点,使得总权(路程或 时间)最小,此即最佳推销员回路问题 在加权图G中求最佳推销员回路问题是NP一完全问题,我们采用一种近似 算法求出该问题的一个近似最优解,来代替最优解,算法如下: 算法一求加权图G(V,E)的最佳推销员回路的近似算法: 用图论软件包求出G中任意两个顶点间的最短路,构造出完备图 G'(,E), V(x,yEE,, o(x, y)=Mind(x,y); 2.输入图G的一个初始H圈; 3.用对角线完全算法(见[23])产生一个初始H圈; 4.随机搜索出G中若干个H圈,例如2000个; 5.对第2、3、4步所得的每个H圈,用二边还次修正法进行优化,得到近 似最佳H圈; 6.在第5步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈 的近似解. 由于二边逐次修正法的结果与初始圈有关,故本算法第2、3、4步分别用三 种方法产生初始圈,以保证能得到较优的计算结果 问题一若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题即在加权图G中求顶点集的 划分1,n2Vn,将G分成n个生成子图2]n,使得 1)顶点O∈V i=1,2,3.n (2) (3)Maxlo(c)-aCj ≤a’其中c为的导出子图c]中的最佳推销员 回路,o(C)为C的权,i,j1,2,3.……n (4)∑o(C1)=M 定义称。Mxp(C)-o(c 为该分组的实际均衡度a为最大容许均 Maxo(c 衡度 显然0≤a0≤1,a越小,说明分组的均衡性越好取定一个a后,a0与a满 足条件(3)的分组是一个均衡分组条件(4)表示总巡视路线最短 此问题包含两方面:第一、对顶点分组;第二、在每组中求最佳推销员回路, 即为单个推销员的最佳推销员问题 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法,故 多个推销员的问题也不存在多项式时间内的精确算法而图中节点数较多,为53
将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之 间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边 上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中 寻找从给定点 O 出发，行遍所有顶点至少一次再回到 O 点，使得总权（路程或 时间）最小，此即最佳推销员回路问题. 在加权图 G 中求最佳推销员回路问题是 NP—完全问题，我们采用一种近似 算法求出该问题的一个近似最优解，来代替最优解，算法如下： 算法一 求加权图 G（V，E）的最佳推销员回路的近似算法： 1． 用图论软件包求出 G 中任意两个顶点间的最短路，构造出完备图 G(V, E) ， (x, y)E， (x y) Mind (x y) G , = , ； 2． 输入图 G 的一个初始 H 圈； 3． 用对角线完全算法（见[23]）产生一个初始 H 圈； 4． 随机搜索出 G 中若干个 H 圈，例如 2000 个； 5． 对第 2、3、4 步所得的每个 H 圈，用二边逐次修正法进行优化，得到近 似最佳 H 圈； 6． 在第 5 步求出的所有 H 圈中，找出权最小的一个，此即要找的最佳 H圈 的近似解. 由于二边逐次修正法的结果与初始圈有关，故本算法第 2、3、4 步分别用三 种方法产生初始圈，以保证能得到较优的计算结果. 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题.即在加权图 G 中求顶点集 V 的 划分 V V Vn , ,....... 1 2 ，将 G 分成 n 个生成子图 G V G V G Vn , ,...... 1 2 ，使得 （1）顶点 O Vi i=1，2，3……n （2） V V (G) n i i = = 1 （3） ( ) ( ) ( ) − i i i j i j Max C Max C C , ，其中 Ci 为 Vi 的导出子图 G Vi 中的最佳推销员 回路， ( ) Ci 为 Ci 的权，i，j=1，2，3……n （4） (C ) Min n i i = =1 定义 称 ( ) ( ) ( ) i i i j i j Max C Max C C − = , 0 为该分组的实际均衡度. 为最大容许均 衡度. 显然 0 0 1， 0 越小，说明分组的均衡性越好.取定一个 后， 0 与 满 足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短. 此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路， 即为单个推销员的最佳推销员问题. 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故 多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为 53
个,我们只能去寻求一种较合理的划分准则,对图11-9进行粗步划分后,求 出各部分的近似最佳推销员回路的权,再进一步进行调整,使得各部分满足均衡 性条件(3). 并、E03 32 图11-10O点到任意点的最短路图(单位:公里) 从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路故用图 论软件包求出O点到其余顶点的最短路,这些最短路构成一棵O为树根的树, 将从O点出发的树枝称为干枝,见图11-10,从图中可以看出,从O点出发 到其它点共有6条干枝,它们的名称分别为①,②,⑧,④⑤,回. 根据实际工作的经验及上述分析,在分组时应遵从以下准则: 准则一:尽量使同一干枝上及其分枝上的点分在同一组; 准则二:应将相邻的干枝上的点分在同一组; 准则三:尽量将长的干枝与短的干枝分在同一组 由上述分组准则,我们找到两种分组形式如下: 分组一:(⑥,①),(②,③),(⑤,④) 分组二:⑨①,②),(③,④),(⑤,⑥) 显然分组一的方法极不均衡,故考虑分组二 对分组二中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路 线使用算法一时,在每个子图所构造的完备图中,取一个尽量包含图11-10中树 上的边的H圖圈作为其第2步输入的初始圈 分组二的近似解见表1 表1(单位:公里) 小组 路线 名称 路 线 总路线长度总长度 O-P-28-27-26-N-2423-22-17-16-1-15--18-K 21-20-25-M0 0-2-5-6-L-19-J-l1-G-13-14H-12-F-10-F9 558.5 E-7-E 241 -8-4-D3-C
个，我们只能去寻求一种较合理的划分准则，对图１1－9 进行粗步划分后，求 出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡 性条件（3）. 从 O点出发去其它点，要使路程较小应尽量走 O点到该点的最短路.故用图 论软件包求出 O 点到其余顶点的最短路，这些最短路构成一棵 O 为树根的树， 将从 O点出发的树枝称为干枝，见图１１－１0，从图中可以看出，从 O点出发 到其它点共有 6 条干枝，它们的名称分别为①，②，③，④，⑤，⑥. 根据实际工作的经验及上述分析，在分组时应遵从以下准则： 准则一：尽量使同一干枝上及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组. 由上述分组准则，我们找到两种分组形式如下： 分组一：（⑥，①），（②，③），（⑤，④） 分组二：（①，②），（③，④），（⑤，⑥） 显然分组一的方法极不均衡，故考虑分组二. 对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路 线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图 11-10 中树 上的边的 H 圈作为其第 2 步输入的初始圈. 分组二的近似解见表 1. 表 1（单位：公里） 小组 名称 路 线 总路线长度 路线的 总长度 I O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K -21-20-25-M-O 191.1 558.5 II O-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9- E-7-E -8-4-D-3-C 241.9 图 11-10 O 点到任意点的最短路图（单位：公里）
OR-29Q30-32-31-33-35-34A-B-1-0 因为该分组的均衡度a0=o(C1)-o(2)=2419-1255542% Maxo(ci 241.9 所以此分法的均衡性很差 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4分给第Ⅲ组(顶点2为 这两组的公共点),重新分组后的近似最优解见表2 表2(单位:公里) 路线「路线总 编号 路 线 长度长度 O-P—28-27-26-N-24—23-22-17 16-15-I18K-21-20-25-M1911 02-5-6-7—E8-E-9—F—10—F 599.8 12-H-14-13-G-1-J-19L-62164 OR-29—Q30-32-31-33-35-34 II A-1-B 192.3 因该分组的均衡度a=2)-oCG)22164-191 l1.69% Max(c 216.4 所以这种分法的均衡性较好 问题〓当巡视人员在眢乡(镇)村的停留时间一定,汽车的行驶谏度 定,要在24小时内完成巡视,至少要分几组及最佳的巡视路线. 由于T=2小时,t1小时,V=35公里小时,需访问的乡镇共有17个,村共 有35个计算出在乡(镇)及村的总停留时间为17×2+35=69小时,要在24小 时内完成巡回,若不考虑行走时间,有:<24(为分的组数)得i最小为4, 故至少要分4组 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡 的分组,当分4组时各组停蜜时间大约为=1725小时,则每组分配在路途上 的时间大约为241725=675小时而前面讨论过,分三组时有个总路程5998公 里的巡视路线,分4组时的总路程不会比5998公里大太多,不妨以5998公里 来计算路上时间约为 599.8 17小时,若平均分配给4个组,每个组约需=425 小时〈6.75小时,故分成4组是可能办到的 现在尝试将顶点分为4组分组的原则:除遵从前面准则一、二、三外,还应 遵从以下准则: 准则四:尽量使各组的停留时间相等 用上述原则在图110上将图分为4组,同时计算各组的停留时间然后用算
III O-R-29-Q-30-32-31-33-35-34-A-B-1-O 125.5 因为该分组的均衡度 0= ( ) ( ) ( ) = − = − = 241.9 241.9 125.5 1,2,3 1 2 i i Max C C C 54.2% 所以此分法的均衡性很差. 为改善均衡性，将第Ⅱ组中的顶点 C，2，3，D，4 分给第Ⅲ组（顶点 2 为 这两组的公共点），重新分组后的近似最优解见表 2. 表 2（单位：公里） 编号 路 线 路线 长度 路线总 长度 I O—P—28—27—26—N—24—23—22—17 —16—I—15—I—18—K—21—20—25—M —O 191.1 599.8 II O—2—5—6—7—E—8—E—9—F—10—F —12—H—14—13—G—11—J—19—L—6 —5—2—O 216.4 III O—R—29—Q—30—32—31—33—35—34 —A—1—B—C—3—D—4—D—3—2—O 192.3 因该分组的均衡度 0 = ( ) ( ) ( ) = − = − = 216.4 216.4 191.1 1,2,3 3 1 i i Max C C C 11.69% 所以这种分法的均衡性较好. 问题二 当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一 定，要在 24 小时内完成巡视，至少要分几组及最佳的巡视路线. 由于 T=2 小时，t=1 小时，V=35 公里/小时，需访问的乡镇共有 17 个，村共 有 35 个.计算出在乡（镇）及村的总停留时间为 17 2+35=69 小时，要在 24 小 时内完成巡回，若不考虑行走时间，有: 24 69 i (i 为分的组数).得 i 最小为 4， 故至少要分 4 组. 由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡 的分组，当分 4 组时各组停留时间大约为 17.25 4 69 = 小时，则每组分配在路途上 的时间大约为 24-17.25=6.75 小时.而前面讨论过，分三组时有个总路程 599.8 公 里的巡视路线，分 4 组时的总路程不会比 599.8 公里大太多，不妨以 599.8 公里 来计算.路上时间约为 17 35 599.8 = 小时，若平均分配给 4 个组，每个组约需 4 17 =4.25 小时〈6.75 小时，故分成 4 组是可能办到的. 现在尝试将顶点分为 4 组.分组的原则：除遵从前面准则一、二、三外，还应 遵从以下准则： 准则四：尽量使各组的停留时间相等. 用上述原则在图 11-10 上将图分为 4 组，同时计算各组的停留时间,然后用算
法一算出各组的近似最佳推销员巡回,得出路线长度及行走时间,从而得出完成 巡视的近似最佳时间用算法一计算时,初始圈的输入与分三组时同样处理 这4组的近似最优解见表3. 表3(路程单位:公里;时间单位:小时) 路线停留行走完成巡视 组名 路 线 总长度时间时间的总时间 0-2-5-6-7—E-8-E I|1-G-12-H-12-F-10-195.8175.592.59 O29—Q30-Q28 I127-26-N-24-23-22-17192165.692.69 16-17-区22-23-N- OM25-2021-K-18 Ⅲr15-14-13-J-19L-阿159.1184.54 M-o OR-A-33-31-32-35 34-B-1C-3-D-4-D-1618474 上表中符号说明:加有底纹的表示前面经过并停留过,此次只经过不需停留; 加框的表示此点只经过不停留 该分组实际均衡度ao 22.74-21.69 =4.62% 22.74 可以看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求
法一算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成 巡视的近似最佳时间.用算法一计算时，初始圈的输入与分三组时同样处理. 这 4 组的近似最优解见表 3. 表 3（路程单位：公里；时间单位：小时） 组名 路 线 路线 总长度 停留 时间 行走 时间 完成巡视 的总时间 I O—2—5—6—7—E—8—E— 11—G—12—H—12—F—10— F—9—E—7—6—5—2—O 195.8 17 5.59 22.59 II O—R—29—Q—30—Q—28— 27—26—N—24—23—22—17 —16—17— K—22—23—N— 26—P—O 199.2 16 5.69 21.69 III O—M—25—20—21—K—18— I—15—14—13—J—19—L—6 —M—O 159.1 18 4.54 22.54 IV O—R—A—33—31—32—35— 34—B—1—C—3—D—4—D— 3—2—O 166 18 4.74 22.74 上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留； 加框的表示此点只经过不停留. 该分组实际均衡度 0= = − 22.74 22.74 21.69 4.62% 可以看出，表 3 分组的均衡度很好，且完全满足 24 小时完成巡视的要求