数学建模论文学校广播站网络的建立与优化

《数学建模论文学校广播站网络的建立与优化》由会员分享，可在线阅读，更多相关《数学建模论文学校广播站网络的建立与优化（12页珍藏版）》请在金锄头文库上搜索。

1、I第七届数学建模竞赛题号 A题论文题目学校广播站网络的建立与优化参赛密码（由组委会填写）II姓名 XXXXXX XXXXXXX XXXXXXXX手机班级 诚 信 承 诺 书本 论 文 是 我 组 独 立 完 成 ， 论 文 中 所 有 引 用 其 他 已 有 成 果 处 均 已 标 明 。 论 文 一 经 提交 ， 组 委 会 有 权 对 其 进 行 审 阅 、 评 定 ， 并 对 获 奖 论 文 有 权 组 织 公 开 发 表 。如 果 论 文 是 抄 袭 他 人 成 果 ， 本 组 将 承 担 所 有 相 关 责 任 。签名： XXXXXXXXXXXXXXXX1摘要本 问 题 要 求 我

2、们 建 立 一 种 合 理 的 模 型 ， 使 得 学 校 的 十 二 个 广 播 站 能 够 达 到 信 息 互 通的 目 的 ， 组 成 广 播 站 网 络 。首 先 通 过 了 MATLAB 对 十 二 组 坐 标 数 据 进 行 处 理 和 分 析 ， 得 出 了 十 二 个 坐 标 点 ， 并通 过 算 法 得 到 了 每 两 点 之 间 的 距 离 。在 对 数 据 的 分 析 之 后 ， 建 立 一 个 模 型 。 该 模 型 为 ： 运 用 “ floyd” 经 典 算 法 对 题 目进 行 分 析 和 研 究 ， 得 出 两 个 “ 欧 拉 回 路 ” ， 再 通 过 比 较

3、 两 个 “ 欧 拉 回 路 ” 之 间 的 坐 标 点的 最 短 距 离 并 连 接 ， 从 而 最 终 形 成 一 张 最 佳 的 广 播 站 网 络 。关 键 词 ： floyd 欧 拉 回 路 最 短 距 离问题重述为 丰 富 同 学 的 业 余 生 活 ， 现 学 校 要 架 设 12 个 广 播 站 ， 选 取 适 当 的 坐 标 系 后 ， 它 们的 位 置 可 以 用 如 下 的 坐 标 表 示 为 ： 4,7a , 10,3b , 5,20c , 8,13d , 15,10e , 13,17f , 20,20g , 23,15h , 28,12i ， (24,9)j ， (3

4、0,5)k ， (33,12)l 。现 在 要 求 把 这 些 广 播 站 连 接 成 一 张 网 络 ， 而 连 线 费 用 与 长 度 成 正 比 ， 应 该 如 何 连 接才 能 使 总 费 用 最 省 。对 于 所 建 立 的 网 络 的 理 解 ， 可 以 是 多 种 多 样 的 。 例 如 对 于 每 个 站 点 的 连 接 要 求 ， 是每 个 点 都 要 和 其 余 11个 站 点 都 要 连 接 还 是 一 条 线 将 12个 站 点 串 起 来 等 等 ， 对 于 这 些 我们 都 要 进 行 分 析 。问题的分析问 题 是 通 过 建 立 一 个 预 测 模 型 ， 来

5、计 算 在 十 二 个 广 播 站 之 间 建 立 网 络 的 最 短 长 度 。建 立 模 型 的 关 键 ： 能 够 计 算 出 广 播 站 点 之 间 的 最 短 距 离 ， 组 成 最 短 距 离 的 广 播 站 网络 。 通 过 对 问 题 的 分 析 ， 在 建 立 模 型 的 过 程 中 需 要 做 到 以 下 几 点 ；1） 建 立 一 个 简 单 实 用 的 数 学 模 型 ；2） 通 过 算 法 对 每 组 数 据 进 行 处 理 ， 计 算 出 两 点 之 间 的 距 离 ；3） 假 设 出 多 种 模 型 方 案 ， 利 用 两 点 之 间 的 距 离 算 出 总 距

6、离 ， 寻 找 出 最 短 总 距 离 ；4） 将 优 化 后 的 最 短 距 离 利 用 MATLAB进 行 绘 图 ， 形 象 化 的 以 图 片 形 式 呈 现 出 广 播 站网 络 。对 于 网 络 建 立 的 方 法 ， 我 们 做 出 如 下 几 种 假 设 ：1） 将 所 有 的 站 点 两 两 相 连 ， 形 成 每 个 站 点 都 与 其 余 十 一 个 站 点 互 通 的 网 络 连 接 方式 ， 此 种 的 连 接 方 式 ， 线 路 总 长 始 终 是 一 个 定 值 ；2） 寻 找 任 意 一 个 站 点 ， 将 其 余 的 十 一 点 都 连 接 到 这 个 站 点

7、 ， 如 此 也 能 形 成 信 息 互通 的 广 播 站 网 络 ， 以 这 样 的 方 式 连 接 的 网 络 ， 有 十 二 种 连 接 总 长 结 果 ；3） 从 A点 开 始 ， 将 该 点 与 其 最 近 点 连 接 ， 形 成 “ 欧 拉 回 路 ” ， 之 后 再 将 “ 欧 拉 回 路 ”以 最 短 的 线 路 连 接 ， 如 此 便 有 了 一 张 信 息 互 通 的 广 播 站 网 络 。2然 后 我 们 对 这 三 种 假 设 进 行 对 比 ：假 设 一 中 ， 所 有 站 点 两 两 相 连 ， 总 长 即 是 将 所 有 两 点 之 间 的 距 离 相 加 ， 并

8、 未 符 合 题目 中 距 离 最 短 ， 费 用 最 少 的 要 求 。 假 设 二 中 以 任 意 点 为 起 点 ， 再 将 另 外 十 一 点 与 之 连 接 ，这 十 一 点 与 该 点 距 离 有 长 有 短 ， 所 以 线 路 也 并 未 达 到 最 短 。 假 设 三 中 ， 首 先 是 利 用“ floyd” 经 典 算 法 算 出 最 短 距 离 ， 再 将 最 短 距 离 的 两 点 连 接 ， 如 此 所 以 的 连 接 距 离 皆是 最 短 ， 总 长 便 也 是 最 短 1， 符 合 题 目 要 求 。通 过 对 三 种 假 设 的 阐 释 对 比 ， 我 们 了

9、解 到 假 设 三 的 方 法 形 成 的 网 络 相 比 较 假 设 一 和假 设 二 是 更 加 优 化 的 ， 所 以 我 们 以 假 设 三 的 网 络 连 接 方 法 建 立 模 型 。模型假设模 型 建 立 的 假 设 ：1） 连 线 费 用 与 长 度 成 正 比 ；2） 所 提 供 的 广 播 站 坐 标 准 确 ， 无 误 差 ；3） 广 播 站 之 间 可 以 直 线 连 接 线 路 ， 即 广 播 站 之 间 没 有 阻 隔 ；4) 不 考 虑 外 界 干 扰 因 素 。符号说明ix ： 第 i个 点 的 横 坐 标 ；iy ： 第 i个 点 的 纵 坐 标 ；1S ：

10、最 近 点 的 距 离 总 和 ， 它 表 示 每 个 点 与 其 最 近 的 一 个 点 的 距 离 之 和 ；2S ： DF与 IL距 离 之 和 ， 它 表 示 在 求 与 其 最 近 一 个 点 距 离 之 和 过 程 中 ， 最 近 点 重 复 的 两端 线 段 的 距 离 之 和 ；3S ： GF的 距 离 ， 它 表 示 在 将 最 近 点 连 接 之 后 ， 坐 标 点 被 分 为 两 部 分 ， 用 最 近 的 坐 标 点将 这 两 部 分 连 接 ， S3即 为 这 两 最 近 坐 标 点 之 间 的 距 离 之 和 ；S ： 最 近 的 网 络 连 接 距 离 ， 它 表

11、 示 用 最 短 的 连 接 方 式 将 坐 标 点 连 接 成 网 络 的 这 段 距 离 。基本模型的建立根 据 对 题 目 的 初 步 分 析 ， 设 想 出 用 “ floyd” 算 法 来 建 立 一 种 最 优 化 的 数 学 模 型 。对 十 二 个 坐 标 点 ： 4,7a , 10,3b , 5,20c , 8,13d , 15,10e , 13,17f , 20,20g , 23,15h , 28,12i ， (24,9)j ， (30,5)k ， (33,12)l 进 行 分 析 ， 我 们 可 以 通 过 使 用 MATLAB来 画 出 十 二 个 点 的 位 置 的

12、分 布 图2。于 是 ， 我 们 把 十 二 个 坐 标 点 数 据 输 入 MATLAB中 做 数 据 处 理 ， 得 到 了 十 二 个 广 播 站3的 坐 标 分 布 图 ， 如 图 1所 示 ：0 5 10 15 20 25 30 3505101520253035ABCDEFGHIJKL图 1 十 二 个 广 播 站 的 坐 标 分 布 图我 们 可 以 清 楚 的 看 到 ， 十 二 个 点 大 致 都 在 范 围 (0,0)到 (35,20)中 ， 于 是 试 图 通 过 某种 算 法 来 把 这 些 广 播 站 连 接 成 一 张 网 络 ， 要 求 线 段 最 短 ， 即 费

13、用 最 少 。通 过 MATLAB计 算 出 了 每 两 点 之 间 的 距 离 ， 得 到 所 有 两 点 之 间 最 短 距 离 ， 可 以 从 这些 数 据 中 得 到 最 短 连 线 的 方 法 。 以 下 是 我 们 计 算 出 的 数 据3：表 1： 两 点 之 间 的 距 离A B C D E F G H I J K LA 0 7.21 13.0 7.21 11.4 13.4 20.6 20.6 24.5 20.1 26.0 29.4B 7.2 0 17.7 10.1 8.6 14.3 19.7 17.6 20.1 15.2 20.1 24.6C 13.0 17.7 0 7.6

14、14.1 8.5 15 0 18.6 24.3 21.9 29.1 29.1D 7.21 10.1 7.6 0 7.6 6.4 13.8 15.1 20.0 16.4 23.4 25.0E 11.4 8.6 14.1 7.6 0 7.2 11.1 9.4 13.1 9.0 15.8 18.1F 13.4 14.3 8.54 6.4 7.2 0 7.6 10.1 15.8 13.6 20.8 20.6G 20.6 19.7 15 13.8 11.1 7.6 0 5.8 11.3 11.7 18.0 15.2H 20.6 17.6 18.6 15.1 9.4 10.1 5.8 0 5.8 6.0

15、12.2 10.4I 24.5 20.1 24.3 20.0 13.1 15.8 11.3 5.8 0 5 0 7.2 5J 20.1 15.2 21.9 16.4 9.0 13.6 11.7 6.0 5 0 0 7.2 9.4K 26.0 20.1 29.1 23.4 15.8 20.8 18.0 12.2 7.2 7.2 0 7.6L 29.4 24.6 29.1 25.0 18.1 20.6 15.2 10.4 5 0 9.4 7.6 0模型的求解4在 计 算 出 每 两 点 之 间 距 离 的 基 础 之 上 ， 可 以 计 算 出 与 每 点 距 离 最 近 的 点 ， 通 过 表

16、1的 数 据 ， 再 利 用 “ floyd” 经 典 算 法 ， 得 出 所 有 连 线 最 短 的 点 的 对 应 点 ， 如 表 2所 示 ：表 2： 广 播 站 网 络 中 最 近 坐 标 点A B C D E F G H I J K LD/B A D F F D H I/G L/J I J I在 对 数 据 进 行 判 断 后 ， 通 过 A（ 4,7） 与 另 外 十 一 个 坐 标 点 之 间 距 离 的 比 较 ， 得 出 据A点 的 最 近 点 分 别 是 B（ 10,3） 和 D（ 8,13） ， 将 A点 与 该 两 点 连 接 ， 以 此 类 推 ， 将 会 得出 另 外 十 一 个 坐 标 点 的 最 近 点 ， 并 将 其 连 接 ， 最 终 会 形 成 一 张 广 播 站 网 络 。由 此 ， 我 们 得 到 这 样 一 个 计 算 方 法 ： 对 所 有 每 一 个 点 与 其 最 近