线性规划在运输问题中的应用

线性规划在运输问题中的应用

刘茂华

【摘 要】线性规划主要应用于解决最优化问题.根据运输问题的基本特征,通过实例对运输问题进行了优化分析,建立了运输问题的线性规划数学模型.将模型应用于一些特殊的运输问题,从而得到最优化的方案,提高了实际运输工作中的经济效益. 【期刊名称】《大庆师范学院学报》 【年(卷),期】2007(027)002 【总页数】5页(P76-80)

【关键词】线性规划;运输问题;最优化 【作 者】刘茂华

【作者单位】湖南文理学院,计算机科学与技术系,湖南,常德,415000 【正文语种】中 文 【中图分类】教科文艺

第 27 卷 第 2 期 大庆师范学院学报V ol.2 7 N o.2 20 0 7 生4 月 JO U R N A L O F D A Q I N G N O R M A L U N I V E R SIT Y Ap r i l , 2 0 0 7线 性 规 划 在 运 输 问 题 中 的 应 用刘 茂 华 （湖南文理 学院 计算机科学与技术系 ，湖南 常德 4 15 000）摘要：线性规划主要应用 于解决最优化问题 。 根据运输问题的基本特征 ， 通过实例对 运 输问题进行 了优 化 分析 ，建 立 了 运输问题的线性规划数学模型。 将模型应用 于一些特殊的 运 输问 题 ， 从 而 得到最优 化 的方案 ， 提高 了 实 际运输 工 作中的经济效益 。 关键词：线性规划；运输问题；最优化

作者筒介：刘茂华（ 197 0-），女 ，湖南洞 口 人 ，湖南文理学院计算机科学与技术系教师 。中圈分类号：T P2 74 文 献标识 码：A 文章编号：10 06- 2 1 6 5 ( 2 0 0 7 ) 0 2 - 0 0 7 6 - 0 5 收稿 日期：20 06 - 12 - 11各 个 领 域 中 的 大 量 问 题 都 可 以 归 结 为 线 性 规 划 问 题 。 近 几 十 年 来 ， 线 性 规 划 在 各 个 行 业 中 都 得 到 了 广泛 的 应 用 。 根 据 美 国《财 富》杂 志 对 全 美 前 5 0 0 家 大 公 司 的 调 查 表 明 ， 线 性 规 划 的 应 用 程 度 名 列 前 矛 ，有 8 5 % 的 公 司 频 繁 地 使 用 线 性 规 划 ， 并 取 得 了 显 著 提 高 经 济 效 益 的 效 果 。1运 输问题的特征运 输 问 题 关 心 的 是 以 最 低 的 总 配 送 成 本 把 供 应 中 心（出 发 地）的 任 何 产 品 运 送 到 每一 个 接 收 中 心（目 的地）。 每 一 个 出 发 地 都 有 一 定 供 应 量 配 送 到 目 的 地 ， 每一 个 目 的 地 都 需 要 一 定 的 需 求 量 。 需求 假 设 ： 每 一 个 出 发 地 都 有 一 个 固 定 的 供 应 量 ， 所 有 的 供 应 量 都 必 须 配 送 到 目 的 地 。 与 之 类 似 ， 每 一个 目 的 地 都 有 一 个 固 定 的 需 求 量 ， 整 个 需 求 量 都 必 须 由 出 发 地 满 足 。 成本 假 设 ： 从 任 何 一 个 出 发 地 到 任 何 一 个 目 的 地 的 货 物 配 送 成 本 和 所 配 送 的 数 量 成 线 性 比 例 关 系 。 运输 问 题 所 需 要 的 数 据 仅 仅 是 供 应 量 、 需 求 量 和 单 位 成 本 。 这 些 就 是 模 型 参 数 。 如 果 一 个 问 题 可 以 完全 描 述 成 如 表 1 所 示 的 参 数 表 形 式 ， 并 且 符 合 需 求 假 设 和 成 本 假 设 ， 那 么 这 个 问 题（不 管 其 中 是 否 涉 及到 运 输）都 适 用 于 运 输 问 题 模 型 ， 最 终 目 的 都 是 要 使 配 送 的 总 成 本 最 小 。 这 个 模 型 的 参 数 都 包 含 在 参 数表 中 。 下 面 就 通 过 例 题 来 说 明 。 A公 司 是 一 家 汽 车 生 产 商 ， A ． 、 A ： 是 它 的 工 厂 ， 生 产 的 轿 车 用 卡 车 把 它 们 运 送 到 三 个 分 销 仓 库 ： A 3 、 A4 、 A ，。 在 下 表 中 列 有 下 列 数 据 ： 每 辆 轿 车 从 每 个 工 厂 到 每 个 分 销 仓 库 所 需 的 运 输 成 本( C i j ) ， 每 个 工 厂 的 供应 量 ， 以 及 每 个 经 销 商 对 轿 车 的 需 求 量 。 求 能 使 运 输 成 本 最

低 的 从 每 个 工 厂 到 每 个 分 销 仓 库 运 输 轿 车 的数 量 以 及 最 低 的 运 输 成 本 。 表1 A 公 司 的 运 输 数 据 表 每辆 轿 车 的 运 输 成 本（ 兀 ） 一工 厂 A3A 4 A5轿 车 供 应 量A I 20 0 10 0 30 0 0 A24 0 0 30 0 20 0 50 0 0 轿车 需 求 量 30 0 0 40 0 0 10 0 0 解： 设 X j j( i = 1 ，2 ;j = 1 , 2 ，3 ) 为 从 每 个 工 厂 到 每 个 经 销 商 运 输 轿 车 的 数 量 ， 目 标 是 为 了 找 出 能 使 总 运 输 成 本最 低 的 从 每 个 工 厂 到 每 个 经 销 商 运 输 轿 车 的 数 量 。 所 以 ， 76第 27卷第 2期大庆师范学院学报Vol.7No0生4月JOURALFDQIGMESITYpril,刘茂华（湖南文理 学院 计算机科学与技术系 ，湖南 常德 4 15 000）运输 工 作中的经济效益 。关键词：线性规划；运输问题；最优化作者筒介：刘茂华（ 197 0()收稿 日期：20 06 - 12 - 11各个领域中的大量问题都可以归结为线性规划。近几十年来，在行业得到了广泛应用根据美国《财 富》杂 志 对 全 美 前 5 0 0 家 大 公 司 的 调 查 表 明 ， 线 性 规 划 的 应 用 程 度 名 列 前 矛 ，有8%公司频繁地使并取显著提 高 经 济 效 益 的 效 果 。运输关心是最低总配送成本把供心（出 发 地）的 任 何 产 品 运 送 到 每接收心（目地）。每出发都 有定供 应 量 配 送 到 目 的 地 ， 每目都 需 要需求假设：固所必须与之类似整由满足从任何货物和数比例系要仅、单位这些就模型参如果完全描述表示形式且符合那么题（不 管 其 中 是 否 涉 及输）都 适 用 于 运 输 问 题 模 型 ， 最 终 目 的 都 是 要 使 配 送 的 总 成 本 最 小 。 这 个 模 型 的 参 数 都 包 含 在 参 数下面通过说明家汽车生产商．它工厂轿卡们三分销仓库4，。列辆本(Cj及经对能本（ 兀 ）解Xj(=，2;j，3标找目 标 函 数 为 C = 2 0 0 X 1 , + l O O X 1 2 + 3 0 0 X 1 3 + 4 0 0 X 2 , + 3 0 0 X 2 2 + 2 0 0 X 2 3 约束 条 件 是 ： X1 , + X 1 2 + X 1 3 = 3 0 0 0 X2 , + X 2 2 十 X 2 3 = 5 0 0 0 Xl , + X 2 , = 3 0 0 0 X1 2 + X 2 2 = 4 0 0 0 X3 1 + X 3 2 = 1 0 0 0 Lx “ ( i = l ，2 ;j = 1 ， 2 ，3 ) ≥ 0 用微 机 很 快 就 可 以 得 出 决 策 变 量 的 下 列 最 优 值 以 及 最 低 的 运 输 成 本 2 0 0 万 元 。表 2 A