线性规划在垃圾运输问题的应用毕业论文

学科分类号 110 黑龙江科技大学本科学生毕业论文题 目 线 性 规 划 在 垃 圾 运 输 问 题 的 应 用 Linear programming is applied in waste transportation problem 姓 名 * 学 号 2011* 院 （系） 理 学 院 专 业 、 年 级 数 学 与 应 用 数 学 指 导 教 师 * 2015 年 6 月 12 日I摘 要我 们 知 道 ,随 着 市 场 经 济 发 展 迅 速 ， 竞 争 也 随 之 加 快 。 为 了 能 在 这 激 烈 的市 场 竞 争 中 立 足 ， 企 业 都 谋 取 最 大 的 利 润 ， 最 少 的 成 本 也 就 是 最 小 的 费 用 。企 业 通 过 不 断 的 改 进 ， 利 用 各 种 方 式 企 图 使 得 费 用 最 少 。 运 输 问 题 关 心 的 是以 最 低 的 总 配 送 成 本 把 供 应 中 心 的 任 何 产 品 运 送 到 每 一 个 接 收 中 心 。 每 一 个出 发 地 都 有 一 定 供 应 量 配 送 到 目 的 地 ， 每 一 个 目 的 地 都 需 要 一 定 的 需 求 量 。运 输 问 题 (Transportation Problem)是 一 个 典 型 的 线 性 规 划 问 题 。 一 般 的 运 输 问题 就 是 要 解 决 把 某 种 产 品 从 若 干 个 产 地 调 运 到 若 干 个 销 地 ， 在 每 个 产 地 的 供应 量 与 每 个 销 地 的 需 求 量 已 知 ， 并 知 道 各 地 之 间 的 运 输 单 价 的 前 提 下 ， 如 何确 定 一 个 使 得 总 的 运 输 费 用 最 小 的 方 案 的 问 题 。本 论 文 运 用 线 性 规 划 的 数 学 模 型 来 解 决 此 运 输 问 题 中 总 费 用 最 小 的 问 题 。针对斯特兰运输公司南大西洋办公处的经理雷切尔对于垃圾处理的困惑，对其的三个处理方案进行优化求解，并运用 excel 电子表格的线性优化来计算各个方案的数学模型。关 键 词 最 优 化 运 输 问 题 线 性 规 划IIAbstractAs we know, with the market economy has developed rapidly, competition also will speed up. In order to establish oneself in the fierce market competition, enterprises seek maximum profit, the least cost is the minimum cost. Enterprise through continuous improvement, the use of a variety of ways in an attempt to make cost minimum. Transportation problem concerned in the lowest total distribution cost and the supply of any product shipped to each receiving center. Each source has certain supply and distribution to the destination, each destination needs certain demand. Transportation Problem, Transportation Problem) is a typical linear programming Problem. General transportation problem is to solve a product from a number of origin transportation to several Sales site , in each origin of supply and demand for each Sales site known, and know that all the transportation between the unit price under the premise of how to determine a scheme to make the total transportation cost minimum. In this paper, using the mathematical model of linear programming to solve the transportation problem of minimum total cost. For strenger transport company of south Atlantic office manager Rachel for garbage disposal confusion, three of its treatment scheme optimization solution, and using the excel spreadsheets to calculate the linear optimization mathematical model of each scheme. Keywords optimization Transportation problem Linear programmingIII目 录摘 要 .IAbstract.II第 1 章 绪 论 .11.1 研 究 的 目 的 和 意 义 .11.2 国 内 外 研 究 状 况 .11.3 本 文 的 主 要 工 作 .5第 2 章 Excel 与 线 性 规 划 的 运 输 问 题 .62.1 线 性 规 划 .62.1.1 线性规划简介 62.1.2 线性规划模型 62.2 线 性 规 划 与 运 输 问 题 .72.2.1 运 输 问 题 的 基 本 特 征 72.2.2 运 输 问 题 的 分 类 72.3 Excel 解 决 运 输 问 题 .112.3.1 软 件 介 绍 112.3.2 运输问题形式 122.3.3 在 excel 中 的 形 式 .122.3.4 excel 求 解 步 骤 .12第 3 章 垃 圾 运 输 问 题 .133.1 问 题 的 提 出 .133.1.1 事 例 133.1.2 对 上 述 问 题 的 几 种 解 决 方 案 143.2 实 例 的 分 析 .153.2.1 实 例 的 数 据 分 析 .153.2.2 对 于 几 种 方 案 的 模 型 建 立 153.2.3 对 于 几 种 方 案 的 模 型 的 excel 求 解 18待解决问题 24结 论 .25致 谢 .26参 考 文 献 .27IVContentsAbstract .IAbstract .IIChapter 1 Introduction .11.1Research purpose and meaning .11.2 The research status at home and abroad.11.3 The main work of this article .5Chapter 2 Excel with linear programming transportation question.62.1 Linear programming .62.1.1 Introduction of linear programming 62.1.2 Linear programming model62.2 Linear programming and transportation problem.72.2.1 The basic characteristics of transportation problem72.2.2 The classification of the transportation problem72.3 Excel solve the transportation problem .112.3.1 The software is introduced112.3.2 Form of transportation problem122.3.3 In the excel form .122.3.4 excel solving steps.12Chapter 3 waste transportation problem.133.1 raise of problem.133.1.1 example133.1.2 Several solutions to the problem 143.2 The analysis of the instance .153.2.1 Example analysis of the data .153.2.2 For several solution model is established in this paper 153.2.3 For several kinds of schemes of excel to solve the model18待解决问题 24conclusions.25Acknowledgements .26References .271第 1 章 绪 论1.1 研究的目的和意义当 前 ， 运 输 市 场 具 有 非 常 激 烈 的 竞 争 ， 每 一 个 企 业 都 为 了 提 高 自 己 的 竞争 力 ， 寻 求 一 种 使 产 销 地 之 间 的 供 应 量 以 及 需 求 量 均 达 到 最 优 搭 配 的 运 输 方案 ， 从 而 增 加 运 输 速 度 、 减 少 运 输 成 本 、 提 高 运 输 可 靠 性 。 所 以 ， 采 用 何 种运 输 方 式 可 以 保 证 原 材 料 和 成 产 品 的 有 效 运 送 和 及 时 供 给 ， 如 何 能 够 将 一 定数 量 的 产 品 以 最 佳 的 运 输 方 式 运 送 给 消 费 者 对 企 业 来 说 成 为 一 种 考 验 。 由 于经 济 和 社 会 的 发 展 的 需 要 ， 定 性 定 量 地 回 答 下 列 问 题 ， 在 有 关 运 输 问 题 的 决策 过 程 中 相 当 重 要 ： 在 当 前 已 有 的 运 输 条 件 下 ， 如 何 分 配 各 种 运 力 和 组 织 货物 的 合 理 流 动 使 运 输 问 题 达 到 最 佳 化 ； 为 了 使 运 输 系 统 的 整 体 性 能 最 优 ， 在各 运 输 项 目 间 考 虑 如 何 合 理 分 配 有 限 的 投 资 或 资 源 ； 未 来 年 代 ， 为 解 决 运 输需 求 和 运 输 能 力 的 矛 盾 ， 应 该 按 照 什 么 顺 序 新 建 、 扩 建 或 改 建 哪 些 运 输 项 目 ，等 等 。 运 输 和 转 运 问 题 在 理 论 和 实 际 应 用 上 都 是 非 常 有 意 义 的 一 类 问 题 ， 为了 回 答 上 述 问 题 建 立 了 一 系 列 的 运 输 系 统 的 模 型 。 所 建 立 的 模 型 应 是 科 学 地从 运 输 活 动 中 抽 象 出 来 的 ， 它 们 可 以 被 公 式 化 应 作 为 线 性 规 划 问 题 求 解 。随 着 我 国 市 场 经 济 的 不 断 完 善 ， 同 地 区 、 不 同 地 区 、 甚 至 跨 国 间 的 企 业交 易 活 动 更 加 频 繁 。 因 此 ， 在 运 输 中 如 何 降 低 运 输 费 用 、 减 少 运 输 路 线 等 问题 ， 已 成 为 交 易 活 动 的 重 点 ， 而 线 性 规 划 主 要 应 用 于 解 决 最 优 化 问 题 。 本 文根 据 运 输 问 题 的 基 本 特 征 ， 通 过 实 例 对 运 输 问 题 进 行 了 优 化 分 析 ， 建 立 了 运输 问 题 的 线 性 规 划 数 学 模 型 ， 并 借 助 于 计 算 机 进 行 求 解 ， 从 而 得 到 最 优 化 的方 案 ， 提 高 了 实 际 运 输 工 作 中 的 经 济 效 益 。 日 常 生 活 中 ， 人 们 经 常 需 要 将 某些 物 品 由 一 个 空 间 位 置 移 动 到 另 一 个 空 间 位 置 ， 这 就 产 生 了 运 输 ， 如 何 判 定科 学 的 运 输 方 案 ， 使 运 输 所 需 的 总 费 用 最 少 ， 是 本 文 要 解 决 的 问 题 。1.2 国 内 外 研 究 状 况运输问题是社会经济生活和军事活动中经常出现的优化问题,是特殊的线性规划问题,它是早期的线性网络最优化的一个例子。最早研究这类问题的Hitchcock 以及后来的 Koopmans 独立地提出运输问题并详细地对该问题加以讨论;同时 KaHTop0BH 也围绕着运输问题作了大量的研究,因此运输问题义称为2Hitchcock 问题或 Kantorovich 问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题.有些其他类型的问题经过适当变换后也可以归结为运输问题,如指派问题、最短路问题、最小费用流题可转化为运输问题或转运问题。运 输 问 题 国 外 相 关 文 献 评 述 。 由 于 运 输 问 题 的 特 殊 数 学 结 构 ， 人 们 很 早 就 意 识 到 通 过 给 出 进 基 变 量 和离 基 变 量 的 最 优 性 条 件 ， 可 以 更 有 效 地 利 用 单 纯 形 法 对 运 输 问 题 进 行 求 解 。Danzig（ 1951） 提 出 的 单 纯 形 法 作 为 求 解 运 输 问 题 的 最 初 单 纯 形 方 法（ Primal Simplex Transportation Method， PSTM） 。 随 后 Charnes 和Cooper（ 1954） 发 展 了 逐 级 算 法 （ Stepping-Stone Method， SSM） ， 该 算 法 提供 了 决 定 单 纯 形 方 法 信 息 的 可 选 择 途 径 。 除 了 PSTM 与 SSM， Adriano 和Claudio（ 1974） 给 出 了 求 解 经 典 运 输 问 题 的 一 种 搜 索 算 法 ， 该 算 法 思 想 以Balas（ 1967） 过 滤 算 法 为 基 础 ， 最 后 给 出 了 该 运 输 问 题 在 实 际 中 的 应 用 。Barr（ 1981） 利 用 增 加 原 有 线 路 指 标 数 据 结 构 ， 对 Kennington 和Unger（ 1976） 的 算 法 进 行 了 改 进 。 Cabot and Erenguc （ 1984， 1986） 提 出 原问 题 的 拉 格 郎 日 松 弛 问 题 ， 由 此 可 获 得 条 件 惩 罚 函 数 ， 但 由 于 缺 少 有 效 运 输节 点 ， 使 算 法 的 计 算 结 果 并 不 理 想 。 Dimitri 和 David（ 1989） 给 出 求 解 运 输问 题 的 拍 卖 算 法 。 拍 卖 算 法 是 一 种 求 解 经 典 指 派 问 题 的 平 行 松 弛 算 法 。 他 们将 拍 卖 算 法 应 用 于 线 性 运 输 问 题 的 求 解 ， 该 算 法 的 思 想 是 将 运 输 问 题 转 化 为指 派 问 题 ， 然 后 修 改 拍 卖 算 法 ， 使 其 适 用 于 运 输 问 题 的 特 殊 结 构 。 Vignaux和 Michalewicz（ 1991） 给 出 了 求 解 线 性 运 输 问 题 的 遗 传 算 法 （ 遗 传 算 法 是 仿照 自 然 选 择 的 进 化 过 程 寻 找 问 题 的 解 ） ， 并 举 例 说 明 了 具 有 代 表 性 的 结 构 之 间的 关 系 ， 研 究 了 遗 传 算 法 实 现 的 程 序 ， 给 出 了 多 种 不 同 结 构 的 运 输 问 题 。Kleinschmidt 和 Schannath（ 1995） 在 改 进 网 络 流 算 法 的 基 础 上 ， 给 出 了 一 般运 输 问 题 的 网 络 流 算 法 ， 算 法 使 用 了 大 量 的 检 测 迭 代 ， 是 一 种 求 解 运 输 问 题的 强 多 项 式 算 法 。 国 外 学 者 从 算 法 角 度 考 虑 ， 对 于 运 输 问 题 的 求 解 提 出 了 很 多 可 行 的 解 法 ，如 表 上 作 业 法 、 图 上 求 解 法 以 及 应 用 计 算 机 实 现 的 启 发 式 多 种 算 法 等 ， 其 基本 上 可 以 总 结 如 下 ：表 上 作 业 法 是 解 决 一 般 运 输 问 题 最 常 用 的 解 法 ， 因 其 求 解 工 作 均 在 运 输表 上 进 行 而 得 名 。 它 是 一 种 迭 代 算 法 ， 迭 代 步 骤 为 ： 先 按 某 种 规 则 找 出 一 个初 始 解 ； 再 对 现 行 解 作 最 优 性 判 别 ； 若 该 解 不 是 最 优 解 ， 就 在 运 输 表 上 对 它进 行 调 整 改 进 ， 从 而 得 出 一 个 新 解 ， 再 重 复 判 别 改 进 的 过 程 ， 直 至 得 到 运 输3问 题 的 最 优 解 为 止 。 最 短 路 线 法 。 当 已 知 某 物 资 从 出 发 地 运 往 目 的 地 ， 可 有 多 条 运 输 路 线 供选 择 ， 这 时 可 构 造 费 用 网 络 图 ， 用 求 最 短 路 线 的 方 法 ， 选 择 最 优 的 运 输 方 案 ，需 画 出 各 种 运 输 路 线 的 线 路 图 及 图 上 每 一 条 边 （ 或 弧 ） 上 的 距 离 或 费 用 （ 也可 以 用 邻 接 矩 阵 表 示 ） ， 然 后 用 Dijkstra 标 号 法 或 邻 接 矩 阵 法 求 最 优 运 输 路 线 。最 小 费 用 最 大 流 是 网 络 最 大 流 问 题 加 上 对 总 费 用 最 小 这 一 约 束 条 件 后 求最 大 流 问 题 。 其 算 法 是 从 费 用 为 0 的 最 小 费 用 出 发 ， 结 合 弧 费 用 构 造 赋 权 有向 图 ， 再 利 用 求 最 短 路 算 法 寻 找 最 小 费 用 增 广 链 对 原 最 小 费 用 流 进 行 调 整 ，重 复 此 过 程 直 至 最 小 费 用 增 广 链 不 存 在 为 止 。 随 着 智 能 搜 索 算 法 的 发 展 ， 近 年 来 有 许 多 有 关 解 决 这 类 运 输 问 题 的 人 工智 能 方 法 的 研 究 ， 如 神 经 网 络 算 法 、 禁 忌 搜 索 算 法 、 遗 传 算 法 等 。 尤 其 是 遗传 算 法 在 解 决 运 输 问 题 方 面 ， 已 经 得 到 了 不 错 的 效 果 。 Michalewicz（ 1991）等 人 首 先 讨 论 了 使 用 遗 传 算 法 来 解 决 线 性 和 非 线 性 运 输 问 题 。 运 输 问 题 国 内 相 关 文 献 评 述 国 内 学 者 对 于 运 输 问 题 的 研 究 主 要 可 以 分 为 三 个 角 度 ： 一 是 在 国 外 算 法的 基 础 上 ， 对 运 输 问 题 算 法 的 改 进 研 究 ； 二 是 从 目 标 函 数 的 角 度 ， 在 运 输 问题 中 有 时 要 同 时 考 虑 运 输 成 本 最 小 、 运 输 过 程 中 货 物 损 坏 率 最 低 以 及 单 位 运价 变 化 的 调 整 等 多 个 目 标 ； 从 约 束 函 数 的 角 度 ， 有 研 究 供 给 量 和 需 求 量 在 某个 区 间 变 化 的 不 确 定 型 运 输 问 题 、 有 时 间 窗 口 的 运 输 问 题 等 。 （ 一 ） 算 法 角 度 的 运 输 问 题 评 述 臧 运 华 （ 2002） 将 运 输 问 题 转 化 为 图 问 题 ， 通 过 构 造 赋 权 二 分 图 G， 应 用图 论 理 论 ， 给 出 运 输 问 题 一 种 图 上 解 法 。 郭 强 （ 2004） 从 基 变 量 判 断 和 寻 找闭 回 路 思 想 出 发 ， 提 出 不 同 于 位 势 法 和 闭 回 路 调 整 的 运 输 问 题 迭 代 算 法 ， 但算 法 仍 具 有 传 统 表 上 作 业 法 的 缺 点 ， 先 求 初 始 可 行 解 再 构 造 上 述 三 个 矩 阵 进行 检 测 调 整 。 刘 徽 （ 2005） 讨 论 了 两 类 运 输 问 题 的 算 法 ， 传 统 运 输 问 题 的 算法 和 受 时 间 约 束 运 输 问 题 的 方 案 及 算 法 。 该 算 法 从 运 输 问 题 可 行 域 的 内 部 出发 ， 沿 着 中 心 路 径 的 方 向 ， 通 过 反 复 迭 代 寻 找 运 输 问 题 的 近 似 最 优 解 。 张 美玉 、 黄 翰 等 （ 2006） 针 对 实 数 线 性 运 输 问 题 ， 提 出 了 一 种 新 型 进 化 算 法 ， 在遗 传 算 法 的 基 础 上 引 进 了 差 异 进 化 的 思 想 ， 设 计 出 具 有 全 局 搜 索 能 力 的 重 组算 子 ， 重 组 算 子 能 够 从 理 论 上 保 证 约 束 条 件 的 满 足 ， 仿 真 实 例 显 示 了 该 算 法的 可 行 性 和 有 效 性 。 周 先 东 等 （ 2008） 设 计 了 基 于 遗 传 算 法 和 粒 子 群 优 化 算4法 的 求 解 运 输 问 题 的 GAPSO 算 法 ， 为 避 开 对 非 可 行 解 的 处 理 ， 该 算 法 对 迭代 过 程 也 进 行 了 特 殊 设 计 ， 从 而 简 化 了 运 用 随 机 搜 索 算 法 解 决 运 输 问 题 的 过程 。 （ 二 ） 目 标 函 数 角 度 的 运 输 问 题 评 述 自 从 建 立 了 基 本 的 运 输 问 题 模 型 以 来 ， 根 据 不 同 的 物 资 调 运 实 际 状 况 建 立的 运 输 问 题 各 种 扩 展 模 型 也 层 出 不 穷 。 根 据 运 输 问 题 优 化 目 标 不 同 ， 基 本 上可 以 将 运 输 问 题 分 为 三 大 类 ： 即 以 费 用 最 小 为 目 标 的 费 用 优 化 运 输 问 题 、 以时 间 最 短 为 目 标 的 时 间 优 化 运 输 问 题 和 两 类 目 标 综 合 最 优 化 的 多 目 标 优 化 运输 问 题 。 费 用 最 优 化 运 输 问 题 模 型 。 此 类 运 输 问 题 模 型 将 运 输 费 用 的 最 小 化 作 为 模型 的 优 化 目 标 ， 目 前 大 多 数 运 输 问 题 模 型 都 属 于 该 类 模 型 的 扩 展 与 引 申 。 如变 量 有 限 制 的 运 输 问 题 ， 其 在 物 资 收 发 量 约 束 的 基 础 上 还 加 入 了 对 调 运 变 量的 约 束 ； 变 约 束 的 运 输 问 题 将 物 资 收 发 量 确 定 为 某 一 个 变 化 范 围 而 不 是 一 个确 定 的 值 。 此 外 还 有 带 中 转 点 的 运 输 问 题 、 多 运 输 方 式 综 合 运 输 模 型 等 等 。 时 间 最 优 化 运 输 问 题 模 型 。 此 类 运 输 问 题 以 缩 短 调 运 时 间 为 模 型 的 优 化目 标 ， 从 而 实 现 物 资 的 快 速 运 输 。 迄 今 为 止 ， 围 绕 解 决 这 类 问 题 已 经 进 行 了大 量 卓 有 成 效 的 研 究 。 较 早 的 有 运 筹 学 的 网 络 最 短 路 模 型 、 生 产 管 理 的 调 度理 论 和 所 谓 的 瓶 颈 运 输 问 题 。 时 间 优 化 运 输 问 题 的 特 点 即 整 体 运 输 时 间 最 短成 为 优 化 的 第 一 目 标 ， 这 时 运 用 费 用 优 化 运 输 问 题 模 型 就 难 以 给 出 满 意 的 结果 。 前 面 所 述 的 费 用 优 化 运 输 问 题 模 型 的 优 化 目 标 为 整 体 运 输 费 用 最 小 ， 运输 费 用 具 有 线 性 叠 加 特 性 ， 或 认 为 具 有 串 联 特 性 ， 即 整 体 运 输 费 用 等 于 各 分段 费 用 的 线 性 叠 加 ； 而 运 输 时 间 则 不 具 有 线 性 叠 加 特 性 ， 因 为 各 供 应 点 的 操作 可 同 时 或 平 行 进 行 ， 整 体 完 成 时 间 并 不 是 各 分 段 时 间 的 线 性 叠 加 ， 而 是 由各 分 段 时 间 中 的 最 大 值 控 制 ， 运 输 时 间 的 这 一 特 点 使 运 输 时 间 的 优 化 具 有 明显 的 并 联 特 性 。 程 桦 、 宋 执 环 （ 2003） 将 物 流 运 输 中 以 时 间 为 第 一 目 标 加 入 到 一 般 运 输问 题 中 作 为 目 标 ， 将 其 分 为 先 后 发 货 即 以 总 运 输 时 间 最 小 为 目 标 和 同 时 发 货以 各 地 运 输 时 间 最 长 为 目 标 的 两 类 运 输 问 题 ， 并 重 点 对 后 者 求 解 给 出 了 算 法 。白 国 仲 （ 2007） 提 出 了 该 类 问 题 的 简 算 法 。 该 算 法 实 则 是 对 传 统 算 法 表 上作 业 法 稍 作 改 进 ， 以 每 次 所 求 最 优 解 中 非 零 变 量 的 单 位 运 价 为 界 ，