《一类运输问题的建模》由会员分享，可在线阅读，更多相关《一类运输问题的建模（6页珍藏版）》请在金锄头文库上搜索。
1、第 31 卷 第 1 期2001 年 1 月数 学 的 实 践 与 认 识M A TH EM A T ICS IN PRA CT ICE AND TH EO R YV o l131 N o11Jan. 2001The Order and Tran sportation of P ipelinesD IN G Yong, XU E Fei, ZHAN G Zhen(Southeast U niversity, N angjing 210096)Abstract: W e succeeded in draw ing up an op tim al p lan fo r the o rder and
2、 transpo rtation ofp ipelines by establish ing tw o models. A diagramm atic model is set up fo r the first p roblem inw h ich there is no branch in the track of p ipelines. So lution of the p roblem is then equivalent tothe p lan that m inim izes som e area of a special diagram. T he idea of flow in
3、 netw o rk help s to setup a non2linear p rogramm ing model fo r the last p roblem w here the track is a tree diagram. T heregular fo rm of the model m akes it convenient to find the so lution by T he SA S System. T hemodel is also used to give an accurate sensitivity analysis fo r the first p roble
4、m.一 类 运 输 问 题 的 建 模费 浦 生 , 赵 社 峰 , 李 健(武 汉 大 学 , 武 汉 430072)摘 要 : 本 文 介 绍 了 2000 年 全 国 大 学 生 数 学 建 模 竞 赛 B 题 的 命 题 思 路 , 两 种 主 要 的 建 模 与 求 解 方 法 .1 命 题 的 思 路2000 年 全 国 大 学 生 数 学 建 模 竞 赛 的 B 题 , 本 质 上 是 一 类 运 输 问 题 .运 输 问 题 是 社 会 经 济 生 活 中 经 常 出 现 的 优 化 问 题 . 由 于 实 际 问 题 的 多 样 性 , 运 输 问 题的 模 型 也 是 各
5、种 各 样 的 . 往 往 涉 及 到 优 化 领 域 中 的 网 络 优 化 、 线 性 规 划 、 二 次 规 划 、 0 1 规划 等 分 支 . 有 些 运 输 问 题 还 涉 及 非 线 性 规 划 、 随 机 优 化 、 排 队 论 、 时 间 表 问 题 、 库 存 问 题 等 运筹 学 的 诸 多 领 域 .最 简 单 的 运 输 问 题 模 型 就 是 线 性 规 划 中 的 标 准 运 输 问 题 , 用 单 纯 形 法 求 解 此 类 特 殊 问题 的 具 体 实 现 就 是 表 上 作 业 法 1 . 它 的 存 储 规 模 小 、 求 解 步 骤 简 单 , 是 实
6、际 中 常 常 遇 到 的 一类 模 型 和 方 法 .B 题 命 题 的 主 要 动 机 是 结 合 当 前 西 气 东 输 工 程 的 背 景 , 让 参 赛 学 生 综 合 运 用 网 络 优 化 、线 性 规 划 或 二 次 规 划 和 整 数 规 划 等 方 面 的 知 识 , 在 建 模 与 求 解 过 程 中 灵 活 地 发 挥 自 身 的 能力 . 因 此 , 题 目 具 有 一 定 的 综 合 性 . 但 是 考 虑 到 竞 赛 只 有 三 天 , 题 目 叙 述 不 宜 过 长 , 数 据 不宜 过 多 , 竞 赛 题 目 对 现 实 的 问 题 作 了 简 化 , 主 要
7、 体 现 在 以 下 方 面 .1. 输 气 管 网 简 化 为 一 条 主 管 道 (题 目 第 一 小 题 ). 这 一 简 化 使 问 题 看 起 来 更 明 朗 , 便 于学 生 思 考 . 而 这 样 做 又 使 建 模 不 失 代 表 性 , 和 复 杂 的 输 气 管 网 的 建 模 方 法 与 模 型 是 一 致 的 .在 第 三 小 题 中 管 道 是 一 个 简 单 的 树 形 图 , 它 与 第 一 小 题 的 模 型 没 有 多 大 区 别 . 这 一 问 题 可使 学 生 了 解 到 所 建 模 型 不 仅 适 用 于 管 道 是 一 条 线 的 情 况 .2. 假
8、定 所 用 管 道 型 号 只 有 一 种 . 现 实 问 题 中 管 道 各 段 的 口 径 未 必 相 同 , 也 就 是 说 管 道网 上 用 到 几 种 不 同 型 号 的 钢 管 . 不 同 型 号 的 钢 管 价 格 不 同 、 重 量 不 同 而 引 起 运 费 不 同 , 厂 家选 择 方 面 的 约 束 也 与 钢 管 型 号 有 关 . 这 样 一 来 数 据 量 变 得 巨 大 , 模 型 的 表 达 也 变 得 复 杂 .题 目 中 简 化 为 管 道 是 同 一 型 号 的 , 数 学 模 型 没 有 本 质 变 化 , 减 少 了 建 模 与 求 解 中 的 叙 述
9、 、 表达 、 计 算 方 面 的 繁 琐 工 作 .3. 铁 路 只 保 留 了 与 题 目 中 管 道 施 工 最 有 关 的 的 线 路 . 联 结 管 道 与 铁 路 的 公 路 应 该 是一 个 复 杂 的 公 路 网 , 题 目 尽 可 能 简 化 到 几 条 直 接 从 车 站 到 管 道 施 工 线 的 公 路 段 , 因 而 铁 路 上也 只 保 留 了 十 几 个 车 站 . 这 样 , 使 与 网 络 最 短 路 有 关 的 计 算 量 尽 可 能 降 低 , 甚 至 不 用 计 算 机也 可 能 很 快 完 成 这 部 分 工 作 .4. 铁 路 运 价 和 公 路 运
10、 价 加 以 简 化 , 但 保 持 了 现 实 生 活 中 的 计 价 结 构 . 铁 路 运 价 的 分 段计 价 档 次 数 减 少 很 多 , 把 管 道 长 度 换 算 成 吨 位 再 计 价 的 工 作 也 省 去 (规 定 每 km 钢 管 为 一 个单 位 ). 这 样 简 化 虽 然 与 现 实 相 差 较 大 , 但 保 留 了 计 价 结 构 的 特 征 .由 于 作 了 上 述 简 化 , 构 成 了 大 学 生 能 够 在 三 天 内 完 成 的 数 学 建 模 竞 赛 题 .在 命 题 过 程 中 韩 继 业 先 生 和 姜 启 源 先 生 等 提 出 了 宝 贵
11、的 意 见 , 包 括 第 二 小 题 的 增 加 , 使得 从 竞 赛 中 更 能 比 较 各 参 赛 队 的 水 平 、 能 力 和 发 挥 情 况 .2 模 型 与 方 法假 设 题 目 中 铁 路 、 公 路 构 成 的 图 为 G (V , E ) ,V 是 所 有 火 车 站 (含 钢 厂 ) 及 管 道 结 点 A 1,A 2, ,A n 的 集 合 , E 是 直 接 联 结 这 些 结 点 的 铁 路 段 和 公 路 段 的 集 合 . 铁 路 部 分 构 成 子 图G 1 (V 1, E 1) , 沿 管 道 的 公 路 构 成 子 图 G2 (V 2, E 2) , G
12、2 也 是 管 道 网 的 图 . 题 目 中 作 为 目 标 函 数的 费 用 包 括 购 买 钢 管 的 费 用 与 运 输 费 用 . 其 中 购 买 费 用 只 与 向 各 钢 厂 订 购 的 数 量 有 关 , 与运 输 路 线 无 关 . 这 一 部 分 很 容 易 处 理 , 关 键 是 运 费 . 要 把 钢 管 从 生 产 厂 运 到 施 工 沿 线 , 根 据铁 路 网 情 况 , 必 然 要 经 过 管 道 上 的 结 点 . 例 如 在 A i,A i+ 1 之 间 的 一 段 上 , 钢 管 或 者 经 A i 或者 经 A i+ 1 运 到 施 工 处 . 因 此
13、, 我 们 可 以 把 运 费 分 为 从 钢 厂 到 管 道 结 点 的 运 费 和 沿 管 道 一 段A i,A i+ 1 内 的 运 费 两 部 分 .我 们 就 问 题 3 这 种 较 一 般 的 情 形 来 叙 述 , 问 题 1 只 是 问 题 3 的 特 例 . 引 入 以 下 记 号 :m 钢 厂 数n G 2 的 结 点 数cij 一 个 单 位 钢 管 从 S i 到 A j 的 最 小 运 价tjk 图 G 2 中 两 相 邻 结 点 A j 与 A k 之 间 的 边 A jA k 的 边 长 (里 程 数 )N j 图 G 2 中 与 A j 相 邻 的 结 点 A
14、k 的 下 标 k 的 集 合x ij 从 S i 运 到 A j 的 运 量y ik A j 得 到 的 钢 管 沿 边 A jA k 向 A k 方 向 运 送 的 里 程 数其 中 x j j , y jk 是 问 题 的 决 策 变 量 .首 先 要 解 决 的 问 题 是 确 定 cij , 由 于 从 S i 到 A j 可 能 既 包 括 一 段 铁 路 运 输 又 包 括 一 段 公 路981 期 费 浦 生 等 : 一 类 运 输 问 题 的 建 模运 输 , 而 两 种 运 输 计 价 方 式 是 不 同 的 , 因 此 需 要 分 开 处 理 .首 先 求 各 钢 厂 到
15、 各 火 车 站 的 最 短 里 程 , 这 是 子 图 G1 (V 1, E 1) 的 里 程 网 络 的 典 型 的 最 短路 问 题 , 可 以 用 求 最 短 路 的 D ijk stra 算 法 或 其 它 算 法 求 解 2 . 对 于 象 本 题 这 样 的 简 单 情 况 ,直 接 就 看 出 最 短 路 . 求 出 这 一 最 短 路 程 就 可 以 根 据 铁 路 运 价 表 得 到 每 单 位 钢 管 由 各 钢 厂 到各 火 车 站 的 最 低 运 费 . 如 果 公 路 网 较 复 杂 , 利 用 公 路 网 络 的 最 短 路 算 法 结 合 钢 厂 到 各 火 车
16、站 的 最 低 运 费 就 能 算 出 由 各 钢 厂 到 管 网 结 点 A i 的 单 位 运 费 cij. 对 于 本 题 只 有 少 量 公 路 联结 铁 路 网 G 1 与 公 路 网 G 2 的 情 况 , 计 算 cij 是 直 接 而 简 单 的 .对 于 由 管 网 结 点 A j 沿 边 A jA k 向 A k 方 向 运 送 y jkkm 钢 管 这 一 部 分 运 费 , 由 于 不 足 1km部 分 按 1km 计 价 , y jk 应 作 为 整 数 看 待 , 这 部 分 运 费 应 为 011 (1 + 2 + + y jk ) = 0112 y ik (y ik+ 1) .根 据 以 上 分 析 , 我 们 就 很 容 易 得 到 总 费 用 的 表 达 式 , 即 优 化 问 题 的 目 标 函 数 . 根 据 在 边A jA k 上 , 从 两 端 运 送 到 沿 线 的 钢 管 数 之 和 应 为
