粮仓选址问题的数学模型.pdf

第 2 7卷第 1期 2 0 1 1年 3月 北 京 建 筑 工 程 学 院 学 报 J o u r n a l o f B e i j i n g Un i v e r s it y o f C iv i l E n g in e e r i n g a n d Ar ch i t e ct u r e V0 1 27 NO 1 M a r 2 01 1 文 章编 号 1 0 0 4 6 01 1 2 0 1 1 0 1 0 0 6 9 0 3 粮仓选址 问题 的数 学模 型 代 西武 北京建筑工程学 院 理学院 北京1 0 0 0 4 4 摘 要 提 出了计算加权 图中任意两点之 间最短距 离的算法 D i j k s t r a矩阵算法 证 明 了结论 当粮仓可建在村庄里或道路上时 则粮仓建在村庄里可使 总运费达到最小 因此 粮仓建在道路上 不能使 总运 费更 少 不 必要 建在道 路上 给 出 了最优 粮 仓地 址 的计 算 方 法 对 一个 具体 例 子 求 出 了最 优 粮 仓 地 址 关 键词 粮 仓 选址 D i j k s t r a算 法 最短路 问题 中图分 类号 O1 5 7 6 文献标 志码 A M a t h e m a t ica l M o de l f o r S e le ct ing Gr a in S t o r e Po s it io n Da i Xiwu S ch o o l o f S cie n ce B U C E A B e i j in g 1 0 0 0 4 4 Ab s t r a ct I n t h i s p a p e r t h e Di j k s t r a S ma t r i x a lg o r i t h m is p r o p o s e d wh ich is t o ca lcu l a t e t h e s h o r t e s t d is t a n c e b e t we e n t wo a r b it r a r y v e r t e x e s i n a we ig h t e d g r a p h Th e pr o v e d c o n clu s io n I f g r a i n s t o r e c a n b e b u ilt in a v illa g e o r o n a p a t h t he mini mu m t r a n s p o r t co s t s will b e a ch ie v e d b y b ui ld in g g r a in s t o r e in a v illa g e Th e me t h o d f o r de t e r mi n in g t h e b e s t p o s it io n o f g r a in s t o r e is s u p p lie d a n d a n e x a mp le i s ca lcu la t e d Ke y wo r d s g r a in s t o r e p o s it i o n d i j k s t r a S a lg o r i t h m p r o b le m o f t h e s h o rt e s t p a t h 1 问题提 出 某 乡有 1 2个 村庄 两 村 连 线 上 的 数 字表示 两村 之 间 的公 路 距 离 单 位 k m 各 村 上 缴粮食数量依次为 7 0 t 8 0 t 6 0 t 3 0 t 6 5 t 1 0 0 t 2 0 t 4 0 t 3 0 t 4 5 t 3 5 t 2 0 t 现 计 划 建 一 个 粮仓 来 储存 这些粮 食 粮仓 可 以建 在村庄 里 或道路 上 请确 定粮仓 的地 址 使运 输 的总 费用最 小 并 求 出最 小 的 总运 费 假 设 粮食 的运 费为 1 5元 k m t 这 就是粮 仓 选址 问题 自然地 各村 庄 村庄 之 间的公 路及 距离 可 以看 成 是 图论里 的加权 图 可用 图论 知识 来求 解此 问题 我 们提 出 了计 算加 权 图 中任意 两点 之 间最 短距 离 的 图 1 1 2村 庄 图 算法 D s t r a矩 阵 算 法 证 明 了结 论 当粮 仓 可 建在 村庄 里或 道 路上 时 则 粮 仓 建 在 村 庄 里 可使 总 运 费达 到最小 因此 粮 仓 建 在 道 路 上 不 能 使 总 运 费更少 不 必要 建 在道 路 上 我 们 还 给 出 了最 优 粮 仓 地址 的计 算方 法 对上 面给 出 的具体 例子 求 出 了 最 优粮 仓地 址为 村 参 考文 献 1 中 对粮 仓 选 址 问题 进 行 了探 讨 给 出 的计算 方 法 复 杂 也 没 有 给 出理 论 证 明 我 们 收稿 日期 2 0 1 1 0 2 2 2 作者简介 代西武 1 9 6 3 一 男 副教授 硕 研究方向 计算机科学 图论 数学建模 7 0 北 京建筑 工 程 学院 学 报 提出的方法简单 并且给出了严格的理论证 明 2问题 分 析 为了清楚 我们假设 1 粮 仓所 在 的村 庄 该村 庄 的 粮食 不计 运 费 即运费 为 0 2 只考 虑本 年 度 的粮 食 运 输 费 用 也 可 以认 为 其它年度 各村庄上缴 的粮食 数量与 本年度 的 一 样 若粮仓地址选定后 总运费的计算可分为三步 首先 求出各个村庄到粮仓的最短距离 这可用图论 中的两点间的最短距离算法来计算 其次 求每个村 庄 的运 费 此 运费就是 最短距 离 上 缴 的粮 食数 量 以 及单 位运 费三者 的乘积 最后 求 总 运 费 即是 各 村 庄 的运 费之和 我 们 可 以将 粮仓 选 址 问题 简 化 为 两 个 问 题 来 求解 1 设 粮仓 只 能建 在 村庄 里 则 粮仓 的地 址 只 有有 限的侯 选地 点 对 于每个 地点 可 以计 算 出总运 费 进行 比较 就可 以确定最优 的粮 仓地址 2 设粮仓 可 以建 在 村庄 里 或 道路 上 则 粮 仓 的地 址有无 穷 多的侯选 地点 这时我们 将证 明 粮仓 建在 道路 上并不 能使 总运费 比粮仓建 在村 庄里 的总 运 费更少 这样 粮 仓 的地 址仍 然只有 有 限的侯 选 地 点 村庄 与第一个问题 的最优粮仓地址的计算方 法 相 同 3 D i j k s t r a矩阵算法 在图论中 计算加权图里的两个指定顶点 与 之 间的最短距 离 可 用 D i j k s t r a 算 法 为 了计 算 加 权 图 中 任 意 两 顶 点 之 间 的 最 短 距 离 我 们 对 D i j k s t r a 算 法进 行 了改进 提 出 了 D i j k s t r a 矩 阵 算 法 该算 法 比 D i j k s t r a算 法 更 容 易 在 计 算 机 上 实 现 能 够计算加权 图中任意两顶点之间的最短距离 下面介绍 D ij k s t r a矩阵算法的思想 将加权 图 G V E 储存在矩阵 A a 里 其 中 r t 为图 G 的顶 点个数 0 当 时 j W 当i J 顶点 与 有连边时 当i 顶点 与 无连边时 W 边 I i 的权重 显然 A为对称矩阵 将 D i j k s t r a 算法的思想应用于此矩阵的第 k行 k 1 2 n 可求出顶点 到其它各顶点的最短距离 将最短距 离还 保存 在矩 阵 A 的第 k行 算 法 结 束 时 矩 阵 A 的元 素值就 是任 意两个顶 点之 问的最 短距 离 D i j k s t r a 矩 阵算 法 1 输 入加权 图 保存 在矩 阵 A a 里 2 对矩阵 A进行操作 求任意两个顶点间的 最短距 离 循环k以 1 为 步长 从 1到 n一1 执行 2 1 6 一 1 2 k一1 k 1 k 2 n k k le n g t h b a 一 一 2 2 循环反复执行下列语 句 直到 触 O 2 2 1 循环 以 1为步 长 从 1到 执 行 e 一 0 k a i d a n i d b 若 t e a k b j a k b j 2 2 2 m 一1 2 2 3 循环 以 1为步 长 从 2到 执 行 若 a k b a k b m il d m iid j 2 2 4 a 一 一 6 miid b 一 b 1 mi id一1 b mi id 1 k k 在数 组 b 中去 掉一个 元素 触一 Z e b 数组 b 的长度 减少 了 1 3 对矩阵A的最后一行赋值 即求 与其它 顶点 间的最 短距离 循 环 以 1为步 长 从 1到 n一1 执行 a r t i 0 i r t 4 算法 结束 4 粮仓只能 建在 村庄 里 时 求最优 粮 仓地址的方法 当粮仓 只能 建在 村 庄里 时 我 们 求 最优 粮仓 地 址 的方法是 1 利用 D i j k s t r a 矩阵算法 计算任意两村庄之 间的最短距离 保存 为对称矩阵 A a 其 中 o 表示 第 i个 村庄 到第 7 个村 庄 的最短距 离 2 分 别计算 粮仓选 在各 个村庄 时 的总运费 3 对 总运 费进行 比较 得 出最优 的粮 仓地址 对于前面给出的具体例子 容易用 Ma t la b编程 实现 D i j k s t r a 矩阵算法 计算得 到任 意两村庄 间的 最短距 离 第 1期 代 西武 粮仓选址 问题 的数学模 型 7 1 A 0 5 1 3 1 6 1 2 1 0 1 9 21 2 3 2 6 2 7 2 9 l J 5 0 8 1 1 7 5 1 4 1 6 1 8 2 1 2 2 2 4 l I I l 1 3 8 0 3 8 1 0 6 8 1 0 1 3 1 4 1 6 I I l I 1 6 1 1 3 0 5 7 3 5 9 1 2 1 1 1 5 I l l I 1 2 7 8 5 0 2 8 1 0 1 4 1 7 1 6 2 0 l I l 1 0 5 1 0 7 2 0 1 0 1 2 1 6 1 9 1 8 2 2 l I f I 1 9 1 4 6 3 8 1 0 0 2 6 9 8 1 2 I I l I 2 1 1 6 8 5 1 0 1 2 2 0 4 7 6 1 0 f I l l 2 3 1 8 1 0 9 1 4 1 6 6 4 0 3 8 6 I I l I 2 6 21 1 3 1 2 1 7 1 9 9 7 3 0 5 3 I J f I 2 7 2 2 1 4 1 1 1 6 1 8 8 6 8 5 0 8 l l I l 2 9 2 4 1 6 1 5 2 0 2 2 1 2 1 0 6 3 8 0 J 而粮仓 选在 各个 村庄 时 的总运 费分 别是 1 5 A 7 0 8 0 6 0 3 0 6 5 1 0 0 2 0 4 0 3 0 4 5 3 5 2 0 1 5 8 0 4 5 5 7 7 0 5 2 9 5 4 9 6 0 4 9 3 5 5 1 2 5 5 6 0 5 6 1 1 5 7 2 4 5 8 4 3 0 8 6 8 5 1 0 0 9 5 进行 比 较 可 知 粮 仓 建 在 村 时 总 运 费 为 1 5 X 4 9 3 5 7 4 0 2 5元 达到最 小 5粮仓可建在 村庄里或道路上时的求 解 结论 1 设 只有 两个 村庄 粮 仓 可 以建 在 村庄里 或道 路上 则 粮 仓 建 在 村 庄 里 可使 总 运 费 达 到最小 证 明 记 村 庄 之 间 的 道路 距 离 为 d 上 缴 的粮 食 数 量 分 别 为 P q 单 位 t 粮 食 的运 费 为 c 元 k i n t 不 妨设 P q 设 粮 仓建 在 之 间的道 路上 且 距离 V 为 公里 处 0 d 则 总 运 费为 cp x cq d cq d C P q 是 的线 性 函数 斜 率 c P q 0 0 d 显 然 当 0时 即 粮 仓 建 在村 庄 里 时 函 数 值 达 到最小 即 总运费 达 到最小 证 毕 说 明 当 P g时 即 两 个 村 庄 上缴 的 粮 食 相 等 时 粮 仓建 在道 路上 也 可使 总运 费达 到最 小 但 是并 不会 比建在村庄里的总运费更小 当 P q时 即两 个村 庄上 缴 的粮 食 不 相 等 时 粮 仓 建 在 上 缴 粮食 较 多 的村庄 里总运 费最 小 此 时 若 粮仓 建 在 道 路 上 总运 费不 能够达 到最 小 结论 2 设 有 n个 村 庄 V 粮 仓 可 以 建 在村 庄里 或道 路 上 则 粮 仓 建 在村 庄 里 可 使 总 运 费达 到最小 证 明 设 粮 仓建 在 与 两 个村 庄 之 间 的道 路 上 时 总运 费 最 小 下 面 证 明 粮 仓 建 在 村 庄 或 里 总运 费也 可 以达 到最 小 事 实上 若 粮仓建 在 与 两个 村 庄之 间的 道 路 上 的 c 点 时 总 运 费最 小 则 所 有 的粮 食 运 送 到 粮 仓里 都必 须 经过 或 设经 过 的粮 食 为 P吨 经 过 的粮 食 为 q吨 那 么 经 过 村 的 粮食 的 运 费 可分 为两 部分 一部 分 是从 各 个 村 庄运 到 的 费 用 记为 另一 部分 是 从 运 到 粮 仓 的 费用 记 为 同样地 经 过 村 的粮 食 的运 费 也 可 分 为 两 部 分 一部分是从各个村庄运到 的费用 记为 g 另一 部分是从 运到粮仓的费用 记为 g 故 总运费 为 f f l g l g 2 g g 这 里 总运 费 厂 达 到最 小 并 且 是 确定 的 总 运 费 可 以分 成两 部分 g g 来计 算 现在假设