• / 6
  • 下载费用:5 金币  

一类运输问题的建模1.pdf

关 键 词:
一类 运输 问题 建模
资源描述:
第 31 卷 第 1 期2001 年 1 月数 学 的 实 践 与 认 识M A TH EM A T ICS IN PRA CT ICE AND TH EO R YV o l131 N o11 Jan. 2001 The 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 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 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 roblem.一 类 运 输 问 题 的 建 模费 浦 生 , 赵 社 峰 , 李 健(武 汉 大 学 , 武 汉 430072)摘 要 : 本 文 介 绍 了 2000 年 全 国 大 学 生 数 学 建 模 竞 赛 B 题 的 命 题 思 路 , 两 种 主 要 的 建 模 与 求 解 方 法 .1 命 题 的 思 路2000 年 全 国 大 学 生 数 学 建 模 竞 赛 的 B 题 , 本 质 上 是 一 类 运 输 问 题 .运 输 问 题 是 社 会 经 济 生 活 中 经 常 出 现 的 优 化 问 题 . 由 于 实 际 问 题 的 多 样 性 , 运 输 问 题的 模 型 也 是 各 种 各 样 的 . 往 往 涉 及 到 优 化 领 域 中 的 网 络 优 化 、 线 性 规 划 、 二 次 规 划 、 0— 1 规划 等 分 支 . 有 些 运 输 问 题 还 涉 及 非 线 性 规 划 、 随 机 优 化 、 排 队 论 、 时 间 表 问 题 、 库 存 问 题 等 运筹 学 的 诸 多 领 域 .最 简 单 的 运 输 问 题 模 型 就 是 线 性 规 划 中 的 标 准 运 输 问 题 , 用 单 纯 形 法 求 解 此 类 特 殊 问题 的 具 体 实 现 就 是 表 上 作 业 法 \[ 1 \]. 它 的 存 储 规 模 小 、 求 解 步 骤 简 单 , 是 实 际 中 常 常 遇 到 的 一类 模 型 和 方 法 .B 题 命 题 的 主 要 动 机 是 结 合 当 前 西 气 东 输 工 程 的 背 景 , 让 参 赛 学 生 综 合 运 用 网 络 优 化 、线 性 规 划 或 二 次 规 划 和 整 数 规 划 等 方 面 的 知 识 , 在 建 模 与 求 解 过 程 中 灵 活 地 发 挥 自 身 的 能力 . 因 此 , 题 目 具 有 一 定 的 综 合 性 . 但 是 考 虑 到 竞 赛 只 有 三 天 , 题 目 叙 述 不 宜 过 长 , 数 据 不宜 过 多 , 竞 赛 题 目 对 现 实 的 问 题 作 了 简 化 , 主 要 体 现 在 以 下 方 面 .1. 输 气 管 网 简 化 为 一 条 主 管 道 (题 目 第 一 小 题 ). 这 一 简 化 使 问 题 看 起 来 更 明 朗 , 便 于学 生 思 考 . 而 这 样 做 又 使 建 模 不 失 代 表 性 , 和 复 杂 的 输 气 管 网 的 建 模 方 法 与 模 型 是 一 致 的 .在 第 三 小 题 中 管 道 是 一 个 简 单 的 树 形 图 , 它 与 第 一 小 题 的 模 型 没 有 多 大 区 别 . 这 一 问 题 可使 学 生 了 解 到 所 建 模 型 不 仅 适 用 于 管 道 是 一 条 线 的 情 况 .2. 假 定 所 用 管 道 型 号 只 有 一 种 . 现 实 问 题 中 管 道 各 段 的 口 径 未 必 相 同 , 也 就 是 说 管 道网 上 用 到 几 种 不 同 型 号 的 钢 管 . 不 同 型 号 的 钢 管 价 格 不 同 、 重 量 不 同 而 引 起 运 费 不 同 , 厂 家选 择 方 面 的 约 束 也 与 钢 管 型 号 有 关 . 这 样 一 来 数 据 量 变 得 巨 大 , 模 型 的 表 达 也 变 得 复 杂 .题 目 中 简 化 为 管 道 是 同 一 型 号 的 , 数 学 模 型 没 有 本 质 变 化 , 减 少 了 建 模 与 求 解 中 的 叙 述 、 表达 、 计 算 方 面 的 繁 琐 工 作 .3. 铁 路 只 保 留 了 与 题 目 中 管 道 施 工 最 有 关 的 的 线 路 . 联 结 管 道 与 铁 路 的 公 路 应 该 是一 个 复 杂 的 公 路 网 , 题 目 尽 可 能 简 化 到 几 条 直 接 从 车 站 到 管 道 施 工 线 的 公 路 段 , 因 而 铁 路 上也 只 保 留 了 十 几 个 车 站 . 这 样 , 使 与 网 络 最 短 路 有 关 的 计 算 量 尽 可 能 降 低 , 甚 至 不 用 计 算 机也 可 能 很 快 完 成 这 部 分 工 作 .4. 铁 路 运 价 和 公 路 运 价 加 以 简 化 , 但 保 持 了 现 实 生 活 中 的 计 价 结 构 . 铁 路 运 价 的 分 段计 价 档 次 数 减 少 很 多 , 把 管 道 长 度 换 算 成 吨 位 再 计 价 的 工 作 也 省 去 (规 定 每 km 钢 管 为 一 个单 位 ). 这 样 简 化 虽 然 与 现 实 相 差 较 大 , 但 保 留 了 计 价 结 构 的 特 征 .由 于 作 了 上 述 简 化 , 构 成 了 大 学 生 能 够 在 三 天 内 完 成 的 数 学 建 模 竞 赛 题 .在 命 题 过 程 中 韩 继 业 先 生 和 姜 启 源 先 生 等 提 出 了 宝 贵 的 意 见 , 包 括 第 二 小 题 的 增 加 , 使得 从 竞 赛 中 更 能 比 较 各 参 赛 队 的 水 平 、 能 力 和 发 挥 情 况 .2 模 型 与 方 法假 设 题 目 中 铁 路 、 公 路 构 成 的 图 为 G (V , E ) ,V 是 所 有 火 车 站 (含 钢 厂 ) 及 管 道 结 点 A 1,A 2, … ,A n 的 集 合 , E 是 直 接 联 结 这 些 结 点 的 铁 路 段 和 公 路 段 的 集 合 . 铁 路 部 分 构 成 子 图G 1 (V 1, E 1) , 沿 管 道 的 公 路 构 成 子 图 G2 (V 2, E 2) , G 2 也 是 管 道 网 的 图 . 题 目 中 作 为 目 标 函 数的 费 用 包 括 购 买 钢 管 的 费 用 与 运 输 费 用 . 其 中 购 买 费 用 只 与 向 各 钢 厂 订 购 的 数 量 有 关 , 与运 输 路 线 无 关 . 这 一 部 分 很 容 易 处 理 , 关 键 是 运 费 . 要 把 钢 管 从 生 产 厂 运 到 施 工 沿 线 , 根 据铁 路 网 情 况 , 必 然 要 经 过 管 道 上 的 结 点 . 例 如 在 [A i,A i+ 1 ] 之 间 的 一 段 上 , 钢 管 或 者 经 A i 或者 经 A i+ 1 运 到 施 工 处 . 因 此 , 我 们 可 以 把 运 费 分 为 从 钢 厂 到 管 道 结 点 的 运 费 和 沿 管 道 一 段[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 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 期 费 浦 生 等 : 一 类 运 输 问 题 的 建 模运 输 , 而 两 种 运 输 计 价 方 式 是 不 同 的 , 因 此 需 要 分 开 处 理 .首 先 求 各 钢 厂 到 各 火 车 站 的 最 短 里 程 , 这 是 子 图 G1 (V 1, E 1) 的 里 程 网 络 的 典 型 的 最 短路 问 题 , 可 以 用 求 最 短 路 的 D ijk stra 算 法 或 其 它 算 法 求 解 \[ 2 \]. 对 于 象 本 题 这 样 的 简 单 情 况 ,直 接 就 看 出 最 短 路 . 求 出 这 一 最 短 路 程 就 可 以 根 据 铁 路 运 价 表 得 到 每 单 位 钢 管 由 各 钢 厂 到各 火 车 站 的 最 低 运 费 . 如 果 公 路 网 较 复 杂 , 利 用 公 路 网 络 的 最 短 路 算 法 结 合 钢 厂 到 各 火 车站 的 最 低 运 费 就 能 算 出 由 各 钢 厂 到 管 网 结 点 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 上 , 从 两 端 运 送 到 沿 线 的 钢 管 数 之 和 应 为 A jA k 的 边 长 tjk , 从 G 2 的 一 个 结 点 A j 向 各 边运 送 钢 管 数 量 之 和 ∑k∈ N jy k j 应 等 于 A j 得 到 的 钢 管 数 ∑mi= 1x ij , 再 考 虑 到 对 钢 厂 供 货 的 约 束 , 我 们得 到 优 化 模 型 :m in ∑mi= 1 ∑nj= 1(cij + p i) x ij + 0. 12 ∑nj = 1 ∑k∈ N jy jk (y jk + 1) (1)s. t. ∑mi= 1x ij = ∑k∈ L jy jk j = 1, 2, … , n (2)y jk + y k j = tjk k ∈ N j , k < j , j = 1, 2, … , n (3)x ij ≥ 0 i = 1, 2, … ,m ; j = 1, 2, … , n (4)y jk ≥ 0 k ∈ N j; j = 1, 2, … , n (5)∑nj= 1x ij ∈ {0} ∪ \[500,si ] i = 1, 2, … ,m (6)在 模 型 中 , 求 解 的 主 要 困 难 在 约 束 条 件 (6). 如 果 将 (6)换 成0 ≤ ∑nj= 1x ij ≤ si (7)∑nj= 1x ij = 0 (8)500 ≤ ∑nj = 1x ij ≤ si (9)这 三 种 条 件 中 的 任 何 一 种 , 问 题 就 是 标 准 的 二 次 规 划 问 题 \[ 3 \], 可 以 直 接 用 二 次 规 划 的 程 序 求解 . 约 束 条 件 (6) 实 质 上 每 一 个 式 子 包 含 (8)、 (9) 所 表 示 的 两 种 情 形 . 为 此 , 可 以 用 分 支 定界 法 来 处 理 \[ 4 \]. 首 先 用 (7) 取 代 约 束 (6) 中 的 关 系 式 , 实 际 上 是 扩 大 了 模 型 的 可 行 集 , 形 成模 型 的 松 弛 问 题 . 这 是 一 个 标 准 的 二 次 规 划 问 题 , 求 解 之 . 得 出 的 解 如 果 满 足 (6) , 则 已是 模 型 的 解 . 如 果 (6) 中 的 m 个 条 件 不 全 满 足 , 选 择 一 个 使 0 < ∑nj= 1x ij < si 的 i 对 问 题09 数 学 的 实 践 与 认 识 31 卷(1)— (6) 进 行 分 裂 , 就 这 个 i 分 别 用 (8)和 (9)取 代 (6)中 的 相 应 关 系 式 得 到 两 个 子 问 题 . 这两 个 子 问 题 的 解 中 最 优 值 小 的 一 个 就 是 模 型 的 解 . 求 解 模 型 就 归 结 为 求 解 这 两 个 子 问题 . 在 求 解 子 问 题 时 对 剩 下 的 形 如 (6)中 关 系 式 的 约 束 仍 然 按 以 上 方 法 进 行 松 弛 求 解 , 有 必要 时 再 进 行 分 裂 , 并 在 过 程 中 不 断 舍 弃 不 可 能 产 生 比 现 有 可 行 解 更 好 的 解 的 子 问 题 . 最 终得 到 模 型 的 最 优 解 . 从 理 论 上 来 说 , 分 支 定 界 法 的 子 问 题 形 成 一 个 树 形 图 , 最 坏 的 情 况 可有 2m 个 子 问 题 . 但 就 本 题 而 言 , 模 型 的 松 弛 问 题 的 解 中 只 有 i = 6和 i = 7不 满 足 约 束 (6), 因 此 只 需 要 一 两 次 分 裂 过 程 即 可 完 成 .模 型 还 可 以 有 等 价 的 表 达 方 式 , 引 入 0— 1 变 量 w i, 用 w i = 1 表 示 从 钢 厂 S i 购 买 钢管 , w i = 0表 示 不 从 钢 厂 S i 购 买 钢 管 . 则 问 题 表 示 为 混 合 0— 1 问 题 . 用 分 支 定 界 法 来 求 解 ,和 前 面 所 述 方 法 实 质 上 是 一 致 的 .3 分 析 与 讨 论1. 对 于 赛 题 的 问 题 2 可 以 采 用 对 销 价 和 产 量 上 限 进 行 数 据 扰 动 来 求 解 的 办 法 来 进 行分 析 , 也 可 以 对 模 型 的 求 解 结 果 直 接 结 合 已 知 数 据 来 进 行 分 析 . 有 些 钢 厂 销 价 的 变 化 达到 一 定 程 度 (并 不 一 定 太 大 ) 时 可 能 使 问 题 的 最 优 解 发 生 本 质 的 变 化 , 甚 至 影 响 到 订 购 哪 些钢 厂 的 钢 管 , 对 这 种 情 况 的 分 析 是 很 有 价 值 的 .2. 由 于 问 题 中 所 有 路 段 的 里 程 数 均 为 整 数 , 计 价 的 里 程 档 次 也 是 以 整 km 划 分 的 . 我们 在 模 型 中 也 认 为 所 有 y jk 均 为 整 数 , 当 然 x ik 也 是 整 数 . 但 我 们 在 模 型 的 表 达 (1)— (6)及 求 解 中 并 未 强 调 y jk 为 整 数 . 实 际 上 , 在 A jA k 段 如 果 取 y jk = l 和 y jk = l + 1 达 到 同 样 的效 果 , 这 时 在 l 到 l + 1 这 1km 中 无 论 从 A j 还 是 A k 运 来 钢 管 的 代 价 都 是 一 样 的 . 这 1km 中一 部 分 从 A j 一 部 分 从 A k 运 来 钢 管 的 代 价 也 是 一 样 的 . 这 是 由 于 不 足 1km 按 1km 计 价 所 引起 的 . 所 以 , 我 们 求 解 中 不 必 强 调 y jk 为 整 数 . 具 体 分 析 一 下 这 种 情 况 . 先 看 从 距 A j 第 l 到 l+ 1km 这 1km 中 的 情 况 . 设 钢 管 运 达 A j 和 A k 的 代 价 分 别 为 u j 和 uk. 则 从 A j 和 A k 往 这 1km运 送 所 需 的 总 代 价 分 别 为 u j + 0. 1 (l + 1) 和 uk + 0. 1 (t - l) ,因 此 u j + 0. 1 (l + 1) = uk + 0. 1 (t - l)于 是 u j - uk = 0. 1 (t - 2l - 1)若 从 A j 运 送 l + E(km ) (0 ≤ E≤ 1) , 则 与 A jA k 有 关 的 这 部 分 费 用 为u j (l+ E) + 0. 12 l (l+ 1) + 0. 1 (l+ 1) E+ uk (t- l- E) + 0. 12 (t- l) (t- l+ 1) - 0. 1 (t- l) E= u j l+ 0. 12 l (l+ 1) + uk (t- l) + 0. 12 (t- l) (t- l+ 1) + E(u j - uk ) + 0. 1 (2l- t+ 1) E= u j l+ 0. 12 l (l+ 1) + uk (t- l) + 0. 12 (t- l) (t- l+ 1)明 显 与 E无 关 . 在 这 种 情 况 下 , 取 y jk = l 或 y jk = l + 1 都 是 最 优 解 , 最 优 解 不 唯 一 . 如 果 算出 y jk 不 是 整 数 , 例 如 y jk = l + E, 0 < E< 1, 从 严 格 意 义 上 来 说 目 标 函 数 值 是 有 误 差 的 . 这时 按 (1)中 的 表 达 式 计 算 这 一 部 分 的 费 用 为u j (l + E) + 0. 12 (l + E) (l + 1 + E) + uk (t - l - E) + 0. 12 (t - l - E) (t - l - E+ 1)= u j l + 0. 12 l (l + 1) + uk (t - l) + 0. 12 (t - l) (t - l + 1) - 0. 1E(1 - E)191 期 费 浦 生 等 : 一 类 运 输 问 题 的 建 模比 实 际 费 用 低 了 011E(1 - E) , 因 此 遇 见 这 种 情 况 时 会 算 出 最 优 解 中 y jk = l + 12 , 这 也 是 问题 的 最 优 解 , 但 目 标 函 数 值 比 实 际 费 用 低 了 0. 025 万 元 , 这 相 对 来 说 是 微 不 足 道 的 , 不 影 响解 的 最 优 性 .3. 在 管 网 的 某 些 段 上 , 从 不 同 的 钢 厂 运 来 的 总 代 价 一 样 , 这 也 可 以 引 起 最 优 解 不 唯 一 .4. 若 忽 略 运 价 不 足 1km 按 1km 计 价 这 一 因 素 , 公 路 运 费 是 里 程 y 的 连 续 函 数 , 则 (1)的 第 二 个 和 式 中 的 0. 12 y jk (y jk + 1) 将 变 成 0. 1∫y jk0x dx = 0. 12 y 2jk这 时 A jA k 这 一 段 的 运 费 为 0. 12 [y 2jk + (tjk - y jk ) 2 ]与 (1) 中 相 邻 部 分 的 差 为 0. 12 [y jk + (tjk - y jk ) \] = 0. 05tjk各 段 之 总 费 用 差 为 0. 05L , 其 中 L = ∑A jA k∈ E 2tjk 是 管 道 总 长 . 因 此 目 标 函 数 中 用 y 2jk 代 替 y jk (y jk+ 1) 不 影 响 最 优 解 , 但 是 算 出 的 最 优 值 比 按 (1) 算 出 的 最 优 值 少 0. 05L .4 线 性 规 划 模 型如 果 把 管 网 分 成 每 km 一 段 , 共 r 段 , 编 号 为 k = 1, 2, … r. 则 从 cij 很 容 易 算 出 钢 厂 S i 到 编号 为 h 这 一 段 的 最 低 费 用 eih. 设 编 号 为 h 的 一 段 在 G 2 中 的 边 A jA k 上 从 A j 算 起 的 第 q 段 , 则ejh = m in{p i + cij + 0. 1q, p i + cik + 0. 1 (tjk - q + 1) }在 每 一 段 A jA k 是 依 次 编 号 的 , 特 别 是 在 问 题 1中 是 沿 管 道 从 A 0 向 A 15 依 次 按 里 程 编 号 的 , eih表 现 为 h 的 分 段 线 性 函 数 . 我 们 取 决 策 变 量 为 Z ih (i = 1, 2,. . m ; h = 1, 2,. . . , r) , 用 Z ih = 1表 示 第 h 段 用 S i 厂 的 钢 管 , Z ih = 0 表 示 第 h 段 不 用 S i 厂 的 钢 管 . 则 可 建 立 线 性 模 型 ˚m in ∑ni= 1 ∑rh= 1eihZ ih (10)s. t. ∑ni= 1Z ih = 1 h = 1, 2, … , r (11)∑rh= 1Z ih ∈ {0} ∪ \[500,si ] i = 1, 2, … ,m (12)Z ih ∈ {0, 1} i = 1, 2, … ,m ; h = 1, 2, … , r (13)对 约 束 (12)可 按 对 二 次 规 划 模 型 采 用 的 分 支 定 界 法 处 理 . 如 果 将 (13) 换 成 Z ih ≥ 0, 每次 需 要 求 解 的 松 弛 子 问 题 具 有 标 准 线 性 运 输 问 题 的 形 状 , 可 用 运 输 问 题 的 表 上 作 业 法 求 解 .由 于 所 有 系 数 都 是 整 数 , 用 表 上 作 业 法 可 得 整 数 最 优 解 . 再 由 约 束 (11) 及 Z ih ≥ 0, 可 保 证Z ih ∈ {0, 1}. 虽 然 看 起 来 模 型 的 规 模 较 大 (r 大 ) , 但 由 于 表 上 作 业 法 的 特 点 , 存 储 量 和 计 算量 还 是 可 以 接 受 的 , 可 以 在 微 机 上 求 解 .对 于 本 题 目 , 实 际 上 模 型 用 启 发 式 算 法 来 得 更 简 单 . 我 们 还 注 意 到 , 如 果 没 有 约 束(12) , 我 们 对 每 个 h 计 算 m in1≤ i≤ meih, 若 i0 (h) 使 达 到 这 一 最 小 值 , 即 ei0 (h) , h = m in1≤ i≤ meih , 则Z ih = 1, i = i0 (h)0 i ≠ i0 (h) h = 1, 2, … , r就 是 问 题 (10) (11) (13) 的 最 优 解 . 再 逐 步 调 整 使 满 足 条 件 (12) , 每 一 调 整 均 要 遵 循 使 增 加29 数 学 的 实 践 与 认 识 31 卷第 31 卷 第 1 期2001 年 1 月数 学 的 实 践 与 认 识M A TH EM A T ICS IN PRA CT ICE AND TH EO R YV o l131 N o11 Jan. 2001 的 费 用 最 少 的 原 则 .由 于 Z ih ∈ {0, 1} , 模 型 ˚ 的 可 行 解 是 由 0 和 1 排 成 的 序 列 , 用 遗 传 算 法 求 解 也 是 很 方便 的 . 还 可 以 有 其 它 的 方 法 . 总 之 , 这 个 问 题 的 建 模 和 解 法 可 以 是 多 种 多 样 的 .参 考 文 献 :\[ 1 \] 俞 玉 森 . 数 学 规 划 的 原 理 和 方 法 . 华 中 工 学 院 出 版 社 , 1985.\[ 2 \] 刘 家 壮 , 徐 源 . 网 络 最 优 化 . 高 等 教 育 出 版 社 , 1991.\[ 3 \] 袁 亚 湘 , 孙 文 瑜 . 最 优 化 理 论 与 方 法 . 科 学 出 版 社 , 1997.\[ 4 \] 费 浦 生 , 郑 慧 娆 , 陈 希 . 分 支 定 界 法 及 其 自 组 织 异 步 并 行 实 现 . 武 汉 大 学 学 报 (自 然 科 学 版 ) , 1995, 41 (8) : 281~ 286.M odeling a K ind of Tran sportation Problem sFE I Pu2sheng, ZHAO She2feng, L I J ian(W uhan U niversity, W uhan 430072)Abstract: T h is paper introduces the mo tivitions fo r p roblem B of CUM CM ′ 2000. Tw o modelsand so lving m ethods are also p resented.关 于 “ 钢 管 订 购 和 运 输 ” 的 评 注丁 颂 康(上 海 海 运 学 院 , 上 海 200135)摘 要 : 本 文 从 评 阅 者 的 角 度 对 求 解 这 道 题 目 中 值 得 注 意 的 问 题 作 了 阐 述 , 指 出 了 同 学 们 的 解 答 中 好 的 作结 及 不 足 之 处 .2000 年 网 易 杯 全 国 大 学 生 数 学 建 模 竞 赛 B 题 :“ 钢 管 订 购 和 运 输 ” 是 一 道 离 散 优 化 的 问题 . 它 的 目 标 是 针 对 两 种 不 同 的 天 然 气 输 送 管 道 的 铺 设 要 求 , 制 定 使 总 费 用 最 小 的 钢 管 订购 运 输 计 划 . 此 外 , 还 须 求 出 在 前 一 种 铺 设 要 求 下 , 哪 一 家 钢 厂 钢 管 销 价 的 变 化 以 及 产 量 上限 的 变 化 对 购 运 方 案 和 总 费 用 的 影 响 最 大 .在 本 文 中 , 我 们 根 据 阅 卷 情 况 , 简 述 一 些 本 题 求 解 中 值 得 注 意 的 问 题 .1 关 于 订 购 和 运 输 单 价 的 计 算要 制 定 出 使 总 费 用 最 小 的 订 购 和 运 输 计 划 , 首 先 需 要 计 算 出 单 位 长 度 的 钢 管 从 各 钢 厂S i (i= 1, 2… 7) 到 需 铺 设 的 主 管 道 (问 题 一 ) 或 树 形 图 (问 题 三 ) 上 各 枢 钮 点 A j (j = 1, 2… 15或 j = 1, 2, … 21) 的 最 小 费 用 C ij. (如 果 采 用 运 输 问 题 模 型 或 者 网 络 最 小 费 用 流 模 型 , 更 需
展开阅读全文
1
  金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:一类运输问题的建模1.pdf
链接地址:http://www.gold-doc.com/p-290853.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
copyright@ 2014-2018 金牌文库网站版权所有
经营许可证编号:浙ICP备15046084号-3
收起
展开