20xx全国数学建模竞赛b题优秀论文

20xx全国数学建模竞赛b题优秀论文内容摘要：

时间大于 3分钟时，损失时间 =到达时间 3。 即 0 , 3= 3,im jt o th e r w is e??? ???到 达 时 间 不 超 过 分 钟损 失 时 间 其中， 1mjt 表示 A 区 m 号平台到 j 号节点的最短时间， 1,2,...,92j ? ? 管辖范围和事故发生地的界定 A 区的交通网络由路口节点与连通节点的各个路段组成，在管辖范围的划分时我们必须考虑节点、路段如何归属的问题。 我们定义路段 (, )Qi j （ ij? ）是由节点 i 和节点 j 连通而成的路段，路段中间不存在节点。 考虑事故发生地的界定，当事故发生在路口节点 i 时，我们认为事故发生地即为节点 i ； 当事故发生在路段 (, )Qi j （ ij? ） 时，考虑路段长度一般较小，简化处理，认为事故发生地为节点 i。 这样即把事故的发生地统一于路口节点。 考虑节点、路段的归属范围，当平台 m 管辖节点 i 时，我们认为平台 m 管辖路段 (, )Qi j （ ij? ） ，这样，一旦路口节点 i 的管辖范围确定下来，路段 (, )Qi j 的管辖范围也随之确定下来，即把管辖范围的归属问题转化为节点的划分归属问题。 基于以上考虑，我们 只要给出 A 区 20 个平台管辖路口节点的方案，即完成了平台的管辖范围分配。 ? 建立罚函数 题目中要求事故发生后平台警力到达时间尽量不超过 3 分钟，这个是解决问题的关键约束条件。 首先，我们将其作为紧约束建立以 所有平台到各个管辖节点总时间最小为目标函数的优化模型，经过检验发现约束过强导致模型无解，从图1中分析原因可知，交通网络中部分路段（如 1416,1528,1529）过长，无论如何分配，必存在个别节点到周围的任意平台的路段长超过 3000m,如节点 28只与节点 29（未设置平台）、 15（设置平台）连通，节点 28只能 归平台 15 管辖，但路段 2815 长度为 4750m(3000m),故无论如何分配，管辖节点 28的平台到达该节点的时间都大于 3 分钟，不满足要求。 因此，我们利用 罚函数法 [3] 求解该模型（该模型实际上为带约束的非线形规划问题），其思想是：利用问题的原目标函数和损失时间约束函数构造出增广目 10 标函数，把该问题转化为不考虑损失时间约束的非线形规划问题来求解。 增广目标函数由两个部分构成，一部分是原目标函数，另一部分是由损失时间约束函数构造出的“惩罚”项，“惩罚”项的作用是 对“到达时间超出 3 分钟”的点进行“惩罚”。 我们采用外部罚函数法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近。 我们设法加大不可行点处对应的目标函数值，使不可行点不能成为非线性约束问题的最优解，于是对于可行域基于损失时间作一惩罚函数，如下： 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 21 0 ( 3 ) , 3 m inmjmj i m j m jtf m jtt???? ? ?????? 其中，1mjt表示 A 区 m 号平台到 j 号节点的最短时间， 1,2,...,92j ? 如果损失时间大于 0，则以 10 倍的损失时间 10( 3)imjt ? 作为“惩罚”项对“到达时间超出 3 分钟”的点进行“惩罚”；如果损失时间为 0，则说明到达时间不超出 3 分钟，不予惩罚。 模型建立 决策变量 题目中关键是确定路口节点的分配方案，即节点 j 是否属于 1m 服务平台管辖，服务 平台编号 km 表示第 k 区的第 m 个服务平台， 1,2,...,6k? 分别代表 6 个城区，故模型的决策变量为 1 1 , 1 , 1 , 2 , . . . , 2 00,mj jmWmo th e r w is e????? 号 路 口 节 点 由 号 平 台 管 辖 增广目标函数 题目要求当服务平台管辖的范围内出现突发事件时，交巡警尽量能在 3 分钟内到达事发地。 从全区的服务平台服务情况考虑，取所有平台到各个节点的总时间最小为目标函数，同时考虑 损失时间约束函数构造出增广目标函数，利用外部罚函数法对“到达时间超出 3 分钟”的点进行“惩罚”。 增广目标函数如下： 2 0 9 2 2 0 9 2111 1 1 1m in m j m jm j m jtf? ? ? ??? ? ? ? 其中， （ 1） 1mjt 表示 1m 号平台到 j 号节点的最短时间， 1,2,...,92j ? 1,2,...,20m? （ 2） 1mjf 表示 1m 号平台 到 j 号节点的损失时间的惩罚函数， 1,2,...,92j ? 1,2,...,20m? 约束条件 11 ? 服务平台数量限制 A区的交巡警服务平台共 20 个，约束如下： 9211 2 0 1 , 2 , .. ., 2 0 1 , 2 , .. ., 9 2mjj W m j? ? ? ?? ? 事故管辖权归属限制 我们认为一起事故仅由管辖该事故发生地的服务平台负责解决，即每一个路口节点仅有一个服务平台 管辖，约束如下： 2011 1 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 2mjm W m j? ? ? ?? ? 事故发生地到达时间限制 此为该问题的关键限制条件。 事故发生后，管辖该路口节点的服务平台尽量在 3 分钟内派出 交巡警到达现场。 根据前面对此限制条件的分析，我们利用罚函数法将此约束放到目标函数中，罚函数如下： 11 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 2m j j m jim j MWt m jv???? ? ? 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 23 , 3 m inmjmj i m j m jtf m jtt???? ? ?????? 其中， （ 1） j? 表示 j 号节点是 否有人报警， 1,2,...,92j ? （ 2） 1mjM 表示 1m 号平台到 j 号节点的最短距离， 1,2,...,92j ? （ 3） v 表示每辆警车的时速， 60 /v km h? ? 综上所述，我们给出平台管辖范围分配模型 [4] ，如下： 12 20 92 20 92111 1 1 111192112011111m i n0 , 3 m i n1 , 2 , ..., 20 1 , 2 , ..., 923 , 3 m i n20 1 , 2 , ..., 20 1 , 2 , ..., 92.. 1 1 , 2 , ..., 20 1 , 2 , ..., 921 , 2 , ..m j m jm j m jmjmjim j m jmjjmjmm j j m jmjtftf m jttW m jst W m jMWtmv?? ? ? ???????? ? ??????? ? ?? ? ?????? ? ? ???1., 20 1 , 2 , ..., 921 , 1 , 2 , ..., 20 1 , 2 , ..., 92mjjW i f m j m j???????????? ???? ? ? ???? 其中， （ 1） j? 表示 j 号节点是否有人报警， 1,2,...,92j ? （ 2） 1mjM 表示 1m 号平台到 j 号节点的最短距离， 1,2,...,92j ? （ 3） v 表示每辆警车的时速， 60 /v km h? （ 4） 1mjt 表示 A 区 m 号平台到 j 号节点的最短时间， 1,2,...,92j ? （ 5） 1 1 , 1 , 1 , 2 , . . . , 2 00,mj jmWmo th e r w is e????? 号 路 口 节 点 由 号 平 台 管 辖 （ 6） 1mjf 为罚函数， 1110 , 3 m in 1 , 2 , . . . , 2 0 1 , 2 , . . . , 9 23 , 3 m inmjmj im j m jtf m jtt???? ? ?????? 模型求解 对上述模型利用 lingo 软件 [5] 求解（代码见附录 3），其中 1mjM 表示 1m 号平台到 j 号节点的最短距离， 1,2,...,92j ? ，可由 dijskstra 算法得到（见附 录 2）。 最终计算结果数据及平台管辖范围方案（见表 1），下给出分配方案的示意图（图2）。 13 图 2 A 区平台管辖范围分配方案 表 1 各平台的管辖范围分配 平台编号 所管辖节点编号 1 1， 67,68,69,71,73,74,75,76,78 2 2， 39,40,43。