城区公路选址最优方案设计--数模论文.pdf

2012 年东南大学数学建模竞赛 1 东东 南南 大大 学学 第六届大学生数学建模竞赛第六届大学生数学建模竞赛 20122012 年年 5 5 月月 17 17 日日 13 13 时 时 5 5 月月 2323 日日 13 13 时时 参赛题目参赛题目 A BA B 在所选题目上打勾 在所选题目上打勾 参赛队员参赛队员 1 1 参赛队员参赛队员 2 2 参赛队员参赛队员 3 3 姓名姓名 傅玮烽傅玮烽 路畅路畅 方晗婧方晗婧 学号学号 0401112204011122 0401162404011624 0401120204011202 学院学院 系 系 信息科学与工程信息科学与工程 学院学院 信息科学与工程学信息科学与工程学 院院 信息科学与工程信息科学与工程 学院学院 手机手机 1585069796915850697969 1585185699315851856993 1585183699315851836993 EmailEmail 464695699 464695699 L Luchangharry uchangharry 310689057 310689057 东南大学教务处东南大学教务处 东南大学数学建模竞赛组委会东南大学数学建模竞赛组委会 2012 年东南大学数学建模竞赛 2 A A 题题 城区公路选址问题城区公路选址问题 摘要摘要 本题要求对不同的修路方案进行综合考虑 并从中选出费用最少的方案 该问题可以归结为一 个 0 1 整数规划和动态规划最短路径模型 我们将每个格点定义为 0 1 变量 建立目标函数 即各 0 1 变量格点与费用权值的乘积之和 其最小值即费用最小值 取值为 1 的格点即为最优点 方案 一和方案二可归结为离散的点和离散的权值问题 方案三和方案四是连续的点和离散的权值问题 第五问为连续的点和连续的权值问题 问题 1 要求在图 1 所示的网格上选一个转弯点 使得 A 点经过该转弯点到达 B 点的建设费 用最低 通过求解 A 或 B 到网格点上的费用权值 建立线性规划模型 得到从 A 点经过一个转弯 点到达 B 点的最小费用为 14 5746 百万元 最优路径为 0 9 2 8 9 0 AB 或者 0 9 8 2 9 0 AB 问题 2 要求在图 1 所示的网格上找 2 个转弯点 使得 A 点经过这两个转弯点到达 B 点的建 设费用最低 将网格点分为三种情形进行讨论 分别建立线性规划模型 得到从 A 点经过一个转弯 点到达 B 点的最小费用为 14 6151 百万元 最优路径为 0 9 2 8 5 6 9 0 AB 或者 0 9 6 5 8 2 9 0 AB 问题 3 要求在图 1 所示的网格线找 2 个转弯点 使得 A 点经过这两个转弯点到达 B 点的建 设费用最低 与问题 2 类似 建立数学规划模型 得到从 A 点经过一个转弯点到达 B 点的最小费 用为 14 5657 百万元 最优路径为 0 9 1 00 8 43 5 00 6 28 9 0 AB 或者 0 9 6 28 5 00 8 43 1 00 9 0 AB 问题 4 要求在图 1 所示的网格线找 2 个转弯点 使得 A 点经过这两个转弯点到达 B 点的建 设费用最低 与问题 2 类似 建立数学规划模型 得到从 A 点经过一个转弯点到达 B 点的最小费 用为 13 5926 百万元 最优路径为 0 9 6 84 5 62 8 36 1 19 9 0 AB 或者 0 9 1 19 8 36 5 62 6 84 9 0 AB 问题 5 要求在图 1 所示的网格线找 2 个转弯点 使得 A 点经过这两个转弯点到达 B 点的建 设费用最低 与问题 2 类似 建立数学规划模型 得到从 A 点经过一个转弯点到达 B 点的最小费 用为 14 1312 百万元 最优路径为 0 9 1 36 8 47 9 0 0 9 8 47 1 36 9 0 ABAB 或者 关键字关键字 公路选址 费用最省路径 0 1 整数规划 动态规划 权值 2012 年东南大学数学建模竞赛 3 一一 问题重述问题重述 某区政府计划在下列区域 见图 1 修建一条从 A 0 9 到 B 9 0 的直线型公路 由于涉及 路面拆迁等因素 各地段建设费用有所不同 图 1 中的数字代表该区域公路单位建设费用 单位 百万元 未标数字的任何地方单位建设费用均为 1 图 1 的每个网格长与宽都是 1 个单位 每个网 格的边界上建设费用按该地区最小单位费用计算 现有下列五种方案 1 公路至多只能有 1 个转弯点 且转弯点只能建在图 1 所示的网格点上 2 公路至多可以有 2 个转弯点 且转弯点只能建在图 1 所示的网格点上 3 公路至多只能有 2 个转弯点 且转弯点只能建在图 1 所示的网格线上 4 公路至多只能有 2 个转弯点 转弯点可以建在图 1 所示区域的任何位置 5 如果各区域的单位建设费用为 22 1 5 0 1 4 4 xy 百万元 公路至多只能有 1 个转 弯点 转弯点可以建在图 1 所示区域的任何位置 图 1 2012 年东南大学数学建模竞赛 4 二二 问题分析问题分析 本题要求建立一个从 A 地到 B 地修一条穿过不同修路费用区域的直线型公路 并使费用最少的 最优方案 该问题可以归结为运筹学中的 0 1 整数规划与动态规划中最短路径的模型 0 1 型整数 规划是整数规划的特殊情形 它的决策变量仅取 0 或 1 这两个值 这时的决策变量也称为 0 1 变 量 在实际问题中 有些问题只需回答 是 或 否 问题就解决了 描述这类问题的变量只需 取两个值就可以了 例如是否采纳某个方案 某项任务是否可以交某人承担 集装箱内是否装入某 种货物等等 对于这类问题我们可以用逻辑变量来描述 1 0 C 是 否 0 1 整数规划法的主要优点是它能够把固定成本以最优的的方式考虑进去 是商业选址模型中最最 受欢迎的方法 本题中选用 0 1 混合整数规划来解决选址模型 目标是使公路建造的成本最小 通 过构建关于公路建造成本的目标函数 并设置约束条件 即可解决问题 图 2 从图 1 的对称性 我们首先可以得出如下结论 转弯点只能设定在直线 AB 右上方的网格上 事 x0 y0 x1 y1 2012 年东南大学数学建模竞赛 5 实上 如果以直线段 AB 作为中轴线 A 点 或 B 点 到直线 AB 右上方任何一点 00 xy的费用比 A 点 或 B 点 到直线 AB 左下方与之关于直线 AB 对称 11 x y的点费用要小 如图 2 所示 将转弯 点限制在直线 AB 右上方的网格上 缩小搜索范围 三三 符号说明符号说明 ijx 某两点间的权值 修路价格 具体点在解题过程中说明 ijX 为 0 1 型变量 0 表示点 i j 未被选用 1 表示点 I j 被选用 i D i 1 2 3 20 为图 2 1 中区域一的点 不包括边界 i E i 1 2 3 20 为图 2 1 中区域二的点 不包括边界 四四 模型假设 模型假设 我们认为逢山开路主要从路线及价钱考虑 寻找一种可行的路线同时又较为省钱 为这个问题 的最佳方案 为简化该问题 我们先做出几点假设 1 每个网格边界建设费用按该地区最小单位费用计算 2 该区域地势平坦无起伏 3 不考虑路面的宽度 4 修路过程中 各区域建设费用不发生变动 5 修路过程中 不产生其它附加费用 五五 问题的分析及模型的建立问题的分析及模型的建立 5 5 1 1 问题 问题 1 1 的的解决方案解决方案 本题要求所设计的公路之多只能有一个拐弯点 且拐弯点只能在图 1 所示的网格点上 在第二 18 12 2012 年东南大学数学建模竞赛 6 部分已经分析过 本题中所选定的一个最优拐弯点在直线 AB 右上方的网格点上 对图 1 作如图 3 所 示的标定 坐标为 i j的点记为 i j C 其中i j且09ji 本题首先计算 A 点 B 点 到网格点 i j C 上的权值 然后利用 0 1 优化模型求解最优网格点 使得总费用最小 图 3 1 1 A A 点点 B B 点点 到到直线段直线段 ABAB 右上方网格点的费用右上方网格点的费用 下面首先计算 0 9 A到直线 AB 右上方网格点上任意一点 i j C的费用 A点的坐标为 0 9 i j C的坐标为 i j 则直线 A 到 i j C的方程为 9 9 j yx i 1 由于直线 A 到 i j C经过不同网格单位费用不一样 因此有必要计算直线段 i j AC 在各个网格内 的长度 然后以该长度乘以相应的单位费用 就是经过该网格的建设费用 最后将经过所有网格点 的费用相加 就得 A 点到 i j C点的建设费用 由 9 9 1 2 1 j yx i xi 2 C19 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 C29 C39 C49 C59 C69 C79 C89 C99 C28 C38 C48 C58 C68 C78 C88 C98 C37 C47 C57 C67 C77 C87 C97 C46 C56 C66 C76 C86 C96 C55 C65 C75 C85 C95 C64 C74 C84 C84 C73 C83 C93 C82 C92 C91 2012 年东南大学数学建模竞赛 7 9 9 1 9 j yx i yj 3 具体计算方法如下 在网格点中任意选取一点 C 得到 AC 的连线方程 将方程和 AC 之间的网格线联立 解得 AC 与 横向网格线和纵向网格线的交点 分别保存到数组中 然后将两个数组整合并排序 按交点的横坐 标大小从小到大排列 然后进入修路费用的分段计算过程 用 if 语句根据不同地段单位长度修路 的费用不同 对交点所在区域进行判断 然后对不同区域中的的线段分别计算 并累加起来 得到 AC 点间修路的费用权 用遍历的办法对所有点的情况进行计算 从中得到最优解 图 4 算法流程图 通过 C 程序 主程序见附件一 计算 A 点和 B 点到点 i j C 09ji 的建设费用 表 1 和表 2 分别是 A 点和 B 点到点 i j C的建设费用 表 1 A 点到直线 AB 右上方网个点的费用 单位 百万元 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 9 9 1 2 3 4 5 6 7 8 9 8 8 2 23607 3 16228 4 12311 5 09902 6 08276 7 07107 8 06226 9 05539 第五步 按点输出费用权值 得到最小值 第四步 对被网格线分割成若干段的线段逐段判断计算并累加起来 第三步 对2中保存的交点按横坐标由大到小排列 第二步 将该线段与网格线的交点保存下来 第一步 在网格中任取一点C 得到其与A点连线的直线方程 2012 年东南大学数学建模竞赛 8 7 7 3 78583 4 69574 5 65442 6 64078 7 64412 8 55544 9 47564 6 6 5 54167 6 49179 7 37902 8 30482 9 1492 9 90847 5 5 7 45964 8 23268 9 09883 9 7269 10 697 4 4 9 24213 10 0279 10 6604 11 3481 3 3 10 9098 11 4583 12 0786 2 2 12 3386 13 0125 1 1 13 7642 表 2 B 点到直线 AB 右上方网个点的费用 单位 百万元 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 9 9 13 7642 13 0125 12 0786 11 3481 10 697 9 90847 9 47564 9 05539 9 8 8 12 3386 11 4583 10 6604 9 7269 9 1492 8 55544 8 06226 8 7 7 10 9098 10 0279 9 09883 8 30482 7 64412 7 07107 7 6 6 9 24213 8 23268 7 37902 6 64078 6 08276 6 5 5 7 45964 6 49179 5 65442 5 09902 5 4 4 5 54167 4 69574 4 12311 4 3 3 3 78583 3 16228 3 2 2 2 23607 2 1 1 1 2 2 建立优化模型 建立优化模型 设 i j 09ji 表 示 A 点 到 任 意 一 点 i j C 09ji 的 建 设 费 用 i j 09ji 表示 B 点到任意一点 i j C 09ji 的建设费用 下面利用 0 1 整数规划 找 到一个转弯点 使得从 A 点经过一个这个转弯点到达 B 点的总建设费用最小 建立如下最优目标函 数 19 min i j i ji jiji j C j i MCC 4 由于只需要找一个转弯点 也就是说只有某一个 i j C为 1 其余的为 0 即有如下约束 2012 年东南大学数学建模竞赛 9 110 1 i j ij C 且 0 1 i j C 5 用 Lingo 软件对最优问题 4 和 5 进行求解 得到当 2 8 1C 或 8 2 1C 时 从 A 到 B 点经 过转弯点 2 8 或 8 2 的建设费用为最少 最少费用为 14 5746 百万 即经过一个转晚点的最优 路径为 0 9 2 8 9 0 AB 如图 5 所示 或者 0 9 8 2 9 0 AB 如图 6 所示 图 5 建 1 个转弯点时的最优路径 0 9 2 8 9 0 AB 2 8 2012 年东南大学数学建模竞赛 10 图 6 建 1 个转弯点时的最优路径 0 9 8 2 9 0 AB 5 5 2 2 问题 问题 2 2 的解决方案 的解决方案 本题要找两个转弯点 使得从 A 点经过这 2 个转弯点的总建设费用最少 首先作直线 AB 的中垂 线 将直线 AB 右上放区域分为两个区域 分别记为区域 1 和区域 2 如图 7 所示 由图中可以看出 两个区域中网格点的单位建设费用是关于中垂线对称的 下面三种情况进行讨论 情形一 两个转弯点 1 个在区域一内 另 1 个在区域二内 情形二 两个转弯点同在区域一内或区域二内 情形三 两个转弯点一个在 AB 的中垂线上 另一个区域一内或区域二内 8 2 2012 年东南大学数学建模竞赛 11 图 7 情形一 两个转弯点情形一 两个转弯点 1 1 个在区域一内 另个在区域一内 另 1 1 个在区域二内 个在区域二内 首先对区域一和区域二中的网格点按照如图 7 所示进行编号 区域一中的第i个网格点用 1 20 i D i 表示 A 点到点 i D的费用记为 i d 区域二中的第j点用 1 20 j Ej 表示 B 点到点 i E的费用权值记为 i d 区域一中的第i个网格点到区域二中的第j个网格点的线段记为 i j F 建设费用为 ij f 于是 从 A 到 B 经过两个转弯点的简化网络图如图 8 所示 图 8 根据图 8 可以建立如下最优目标函数 A B 1 D 2 D 3 D 20 D 20 E 1 E 2 E 3 E 1 2 3 4 5 6 7 8 9 10 15 111213 14 16 18 19 20 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 区域一 10 区 域 二 2012 年东南大学数学建模竞赛 12 20202020 1111 min iii ji jjj iijj d Df Ff E 6 约束条件 20 1 20 1 2020 11 10 1 1 0 1 1 F0 1 ii i jj i i ji j ij DD EE F 7 A 点到区域一中的任意一点 i D费用 i d和 B 点到区域二中的任意一点 j E的费用权值 j f 在问题 一中已经求出 对于区域一中任意一点与区域二任意一点的费用权值 类似于问题一中权值的计算 方法 同样可以得到区域一中任意一点到区域二中任意一点的费用权值 i j e 用 Lingo 软件对最优问题 8 和 9 进行求解 得到当 99 22 1 1 1DHG 时 即从 A 到 B 点经过转弯点 2 8 和 8 2 的建设费用为最少 最少费用为 14 7017 百万 即经过两个转弯 点的最优路径为 0 9 2 8 8 2 9 0 AB 情形二 两个转弯点同在区域一内或区域二内 情形二 两个转弯点同在区域一内或区域二内 假设两个点同在区域一内 设 i j D表示连接区域一中第i个网格点和第j个网格点的连线 该线 段的费用为 i j d 并且满足120ij 类似于情形一可以建立如下最优目标函数 20202020 1111 min iii ji jjj iij ij i d Dd Dd D 8 约束条件 20 1 20 1 2020 11 10 1 1 D0 1 1 F0 1 ii i jj j i i ji j ij i DD D D 9 用 Lingo 软件对最优问题 8 和 9 进行求解 得到当 99 2020 1 1 1DEE 时 即从 A 2012 年东南大学数学建模竞赛 13 到 B 点经过转弯点 2 8 和 5 6 的建设费用为最少 最少费用为 14 6151 百万 即经过两个转 弯点的最优路径为 0 9 2 8 5 6 9 0 AB 由于区域二和区域一是关于直线 AB 的中垂线高度对称 类似于两个转弯点同在区域一的情形 同样可以得到在区域二中的两个点 从 A 到 B 点经过转弯点 6 5 和 8 2 的建设费用为最少 最少 费用为 14 6151 百万 即经过两个转弯点的最优路径为 0 9 6 5 8 2 9 0 AB 情形三 两个转弯点一个在情形三 两个转弯点一个在 ABAB 的中垂线上 另一个区域一内或区域二内 的中垂线上 另一个区域一内或区域二内 假设一个点在区域一内 一个点在直线 AB 的中垂线上 直线 AB 右上方在中垂线线上有 5 个点 坐标分别为 5 5 6 6 7 7 8 8 和 9 9 分别记为 1 G 2 G 3 G 4 G和 5 G 连接区域 一中任意一点 i D与 j G的线段记为 i j H 该线段上的建设费用为 i j h 类似于情形一 建立如下最 优目标函数 202055 1111 min iii ji jjj iijj d Dh Hg G 10 约束条件 20 1 5 1 205 11 10 1 1 0 1 1 0 1 ii i jj j i ji j ij DD GE HH 11 用 Lingo 软件对最优问题 8 和 9 进行求解 得到当 99 22 1 1 1DHG 时 即从 A 到 B 点经过转弯点 2 8 和 6 6 的建设费用为最少 最少费用为 14 7432 百万 即经过两个转弯 点的最优路径为 0 9 2 8 6 6 9 0 AB 如果一个点在区域二内 另一个点在直线 AB 的中垂线上 同样可以得到建设费用为 14 7432 百 万 的最优路径 0 9 6 6 8 2 9 0 AB 综上三种情形 情形二得到的建设费用最低 建设费用为 14 6151 百万 最优路径为 2012 年东南大学数学建模竞赛 14 0 9 2 8 5 6 9 0 AB 或者 0 9 6 5 8 2 9 0 AB 这 两条路径分别如图 9 和图 10 所示 图 9 图 10 程序见附件二 6 5 8 2 2 8 5 6 2012 年东南大学数学建模竞赛 15 5 5 3 3 问题 问题 3 3 的解决方案 的解决方案 问题 2 已经找到的是网格点上的两个转弯点 2 8 和 5 6 或 6 5 和 8 2 本题要找两个在网格线上的转弯点 由于网格点可以看成是网格线上的特殊点 容易证明区域一中 网格线上的第 1 个点在与 2 8 邻近的 2 条网格线上 4 条网格线分别记为 1 l和 2 l 如图 11 所示 区域一中网格线上的第 2 个点在与 5 6 邻近的 4 条网格线上 4 条网格线分别记为 1 k和 2 k 如 图 11 所示 图 11 将 8 条直线 1 l 2 l 1 k 2 k的直线方程分别为 1 2 13 8 2 79 lxy lxy 12 1 2 45 6 5 57 kxy kxy 13 下面分 4 中情况进行讨论 情形 1 第一个转弯点点在线段 1 l上 第一个转弯点点在线段 1 k上 情形 2 第一个转弯点点在线段 1 l上 第一个转弯点点在线段 2 k上 2 8 5 6 1l 2l 2k 1k 2012 年东南大学数学建模竞赛 16 情形 3 第一个转弯点点在线段 2 l上 第一个转弯点点在线段 1 k上 情形 4 第一个转弯点点在线段 2 l上 第一个转弯点点在线段 2 k上 首先讨论情形 1 假设第一个转弯点点在线段 1 l上 该转弯点坐标为 1 8 x 其中 1 1 3 x 去步长为x 将区间 1 3 进行离散化 得到N个离散的点 1 1 3 3xx 于是将线段 1 l 分为N个离散的点 分别记为 12 N P PP 类似于问题 1 中权值的计算 可以得到 A 点到每一 点 i P的权值 1 i p iN 同样 第二个转弯点在线段 1 k 也可以得到N个离散的点 分别记为 12 N Q QQ 从 B 点到点 j Q的建设费用分别为 1 j qjN 另外 记 i j Z表示连接 i P和 j Q 线段的选段 这条线段的费用记为 i j z 类似于问题 2 中的情形一 建立如下最优模型 1111 min NNNN iii ji jjj iijj p Pz Zq Q 14 约束条件 20 1 20 1 2020 11 10 1 1 Q0 1 1 Z0 1 ii i jj i i ji j ij PD Q Z 15 用 Lingo 软件对最优问题 8 和 9 进行求解 步长0 01x 得到当 99 22 1 1 1DHG 时 即从 A 到 B 点经过转弯点 6 82 5 00 和 8 43 1 00 或 5 00 6 82 和 1 00 8 43 的建设费用为最少 最少费用为 14 5971 百万 即经过两个转弯点的最优路径为 0 9 6 82 5 00 8 43 1 00 9 0 AB 或者 0 9 1 00 8 43 5 00 6 82 9 0 AB 2012 年东南大学数学建模竞赛 17 图 12 图 13 5 5 4 4 问题 问题 4 4 的解决方案 的解决方案 5 00 6 82 1 00 8 43 6 82 5 00 8 43 1 00 2012 年东南大学数学建模竞赛 18 本题的目标是在图 1 所示的区域内任意位置上找两个转弯点 问题 2 已经找到网格点上的两 个转弯点 2 8 和 5 6 或 6 5 和 8 2 类似与问题 3 容易证明区域一中第 1 个点一定在以 2 8 为中心的一个区域内 假设该区域为正方形区域 1 边长为r 取沿x轴 的步长为x 沿y轴的步长为y 将正方形区域 1 离散化 得到一个大小为 11 MN 离散化的矩 阵 然后将该矩阵进行行排序 于是将区域 1 离散化为 11 M N个离散的点 分别记为 11 12 M N S SS 费用分别为 11 12 M N s ss 同样 第二个转弯点在线段 2 也可以得到 22 M N个离散的点 分别 记为 22 12 M N T TT 费用分别为 22 12 M N t tt 另外 记 i j U表示连接 i S和 j T线段的选段 这条 线段的费用记为 i j u 类似于问题 3 中的情形一 建立如下最优模型 11112222 1111 min M NM N M NM N iii ji jjj iijj s Su Ut T 15 约束条件 11 22 1122 1 1 11 10 1 1 0 1 1 U0 1 M N ii i M N jj i M N M N i ji j ij SS TT U 16 用 Lingo 软件对最优问题 8 和 9 进行求解 步长0 01x 得到当 99 22 1 1 1DHG 时 即从 A 到 B 点经过转弯点 6 84 5 62 和 8 36 1 19 或 5 62 6 84 和 1 19 8 36 的 建设费用为最少 最少费用为 14 5971 百万 即经过两个转弯点的最优路径为 0 9 6 84 5 62 8 36 1 19 9 0 AB 0 9 1 1 9 8 3 6 5 6 2 6 8 4 9 0 AB 或 2012 年东南大学数学建模竞赛 19 图 14 图 15 5 5 5 5 问题 问题 5 5 的解决方案 的解决方案 问题 5 要求建设费用是随着坐标 x y的变化 费用计算公式为 22 1 5 0 1 4 4 xy 通过计算 利用该公式在每个网格内进行积分 计算出来的面积近似于图 1 中给定的单位建设费 1 19 8 36 5 62 6 84 6 84 5 62 8 36 1 19 2012 年东南大学数学建模竞赛 20 用 因此 本题的一个转弯点应该设定在问题 1 中的最优点 2 8 或 8 2 周围 类似于问题 4 中的分析 假设是以 2 8 为中心的一个区域内 假设该区域为正方形区域 1 边长为r 取沿 x轴的步长为x 沿y轴的步长为y 将正方形区域 离散化 得到一个大小为MN 离散化 的矩阵 其中每个元素记为 1 1 i j RiMjN A 点到 i j R的费用为 i j a B 点到 i j R费用为 i j b建立如下最优模型 min i j MN i ji jiji j R ij a Rb R 16 约束条件为 1 MN i j ij R 且 0 1 i j R 17 用 Lingo 软件对最优问题 5 进行求解 即从 A 到 B 点经过转弯点 1 36 8 47 或者 8 47 1 36 的建设费用为最少 最少费用为 14 5971 百万 即经过两个转弯点的最优路径为 0 9 1 3 6 8 4 7 9 0 AB 0 9 8 4 7 1 3 6 9 0 AB 或 图 16 1 36 8 47 2012 年东南大学数学建模竞赛 21 图 17 六六 模型评价模型评价 本问题利用线性规划的方法来解决 本题要求对不同的修路方案进行综合考虑 并从中选出费 用最少的方案 该问题可以归结为一个 0 1 整数规划和动态规划最短路径模型 首先 我们将每个 格点定义为 0 1 变量 建立目标函数 即各 0 1 变量格点与费用权值的乘积之和 其最小值即费用 最小值 取值为 1 的格点即为最优点 前两个方案可归结为离散的点和离散的权值问题 方案三和 方案四是连续的点和离散的权值问题 第五问为连续的点和连续的权值问题 我们通过 C 的遍历穷举和 lingo 软件的双重检验 得到了极其相近的结果 说明了该模型建立 的合理性 下面对模型的优缺点进行评价 优点 优点 1 通过数学变换 把实际问题的求解成功地转化为对一个目标函数的求解 目标函数值的大小就反 映了修路费用的高低 2 使用自定义的算法 能够求得一组精确的解 算法可以抽象为通用的算法 并可编程实现 3 模型比较灵活 将相同的算法略加修改便能够对不同方案得到比较优化的结果 4 使用自定义的算法成功解答问题后能够将算法很好的进行推广 5 综合考虑了距离 价格多方面的需求和冲突 虽然求解复杂度变大 但是求解的方式却灵活多样 8 47 1 36 2012 年东南大学数学建模竞赛 22 缺点 缺点 1 使用 lingo 求解时 由于目标函数涉及较多项求和 输入过程较繁杂 效率较低 2 方案三和方案四的取点从离散点变为了连续点 但由于 C 与 Lingo 软件的局限性 只能将线 或者区域进行微分 基本能表示真正的连续点的情况 但是仍有微小的差距 七七 模型的推广 改进模型的推广 改进 1 1 推广 推广 1 由于模型建立在 0 1 整数规划模型上 所以很容易推广到更一般的情形 2 对应相应结果的数量级 可选取相应合适密集度的离散点 易推广 2 2 改进 改进 1 由于问题本身的复杂度很高 所以各个问题的模型都做了数学处理 即采用取尽量多的离散点的 做法 这种做法虽然给解答带来了很大的方便 却使精度受到了一定的影响 虽然这种影响很小 但是模型应尽可能的向提高精度方面做适当改进 以利于实际问题的解决 2 在 0 1 整数规划模型中 采用 Lingo 作为求解模型的软件 由于数据较多 目标函数的输入较 为复杂 在实际问题中可实施性不大 若要取得更高的吻合度 应该对模型的算法进行改进 选择更 优秀的软件 进一步简化模型 可减少模型的求解规模 提高权值系数的精度 八八 参考文献参考文献 1 程理民 吴江 运筹学模型与方法教程 北京 清华大学出版社 2000 2 傅鹂 龚劬 刘琼荪 何中市编著 数学实验 北京 科学出版社 2000 3 姜启源 数学模型 第 3 版 北京 高等教育出版社 1999 4 姜启源 谢金星 叶俊 数学模型 北京 高等教育出版社 2006 5 赵则民 运筹学 重庆 重庆大学出版社 2002 2012 年东南大学数学建模竞赛 23 附件一附件一 include using namespace std double aij int x0 int y0 if y0 8 double d return d sqrt x0 x0 1 if y0 9 double d return d x0 else double k k double y0 9 0 double x0 double xk 9 double yk 9 for int i 0 iy0 xk i i 9 k else xk i 0 for i 0 i 9 i if i x0 yk i k i 9 else yk i 0 2012 年东南大学数学建模竞赛 24 double ik 17 double jk 17 ik 0 0 jk 0 9 for int m 1 m x0 1 m ik m m int n m 7 y0 for m n m i y0 1 ik m xk i i 冒泡排序 bool noswap double temp for m 0 mm j if ik j ik j 1 temp ik j ik j ik j 1 ik j 1 temp noswap false if noswap break 给 jk 赋值 2012 年东南大学数学建模竞赛 25 for m 1 m x0 y0 7 m if ik m 1 ik m 2 ik m 3 ik m 4 ik m 5 ik m 6 ik m 7 i k m 8 int g int ik m jk m yk g else for int j y0 1 j 8 j if ik m xk j jk m j break ik m x0 jk m y0 开始计算费用权 double d 0 for m 1 m 0 continue 2012 年东南大学数学建模竞赛 27 return d return 0 double aijandbij int x0 int y0 return aij x0 y0 aij y0 x0 2012 年东南大学数学建模竞赛 28 附件二附件二 include include using namespace std double result int x0 int y0 int x1 int y1 double k double y1 y0 double x1 x0 double h 20 z 20 double d 0 if x1 x0 1 return d for int i x0 1 i x1 i z i k i x1 y1 for int j y1 1 j y0 j h j j y1 k x1 double ik 20 jk 20 ik x0 x0 jk x0 y0 for int m x0 1 m x1 m ik m m for m y0 x1 y