运筹学 第3章运输问题

《运筹学 第3章运输问题》由会员分享，可在线阅读，更多相关《运筹学 第3章运输问题（47页珍藏版）》请在装配图网上搜索。

1、1 Chapter3 运 输 问 题( Transportation Problem ) 运 输 问 题 的 数 学 模 型 表 上 作 业 法 运 输 问 题 的 应 用 2 从 m个 发 点 向 n个 收 点 发 送 某 种 货 物 . 发 点 的 发量 为 ， 收 点 的 收 量 为 。 由 运往 单 位 货 物 的 运 费 为 ， 问 如 何 调 配 ，才 能 使 运 费 最 省 ？问 题 的 提 出 mAAA , 21nBBB , 21 jB iAia jb iAjB jic.题否 则 称 为 非 平 衡 运 输 问 运 输 问 题 ， 称 此 运 输 问 题 为 平 衡若 ji b

2、a 3 表 1 产 销 平 衡 表 销 地 产 地 1 2 n 产 量 1 a1 2 a2 m am 销 量 b1 b2 bn 上 述 数 据 可 以 汇 总于 表 格 中 ,如 下 :表 2 单 位 运 价 表 销 地 产 地 1 2 n 1 c 11 c12 c1n 2 c21 c22 c2n m cm1 cm2 cmn 4 运 输 问 题 的 数 学 模 型 设 xij代 表 为 从 第 i个 产 地 调 运 给 第 j个 销 地 的 物 资的 数 量 .在 产 销 平 衡 的 条 件 下 ， 即 使 总 的 运 费 支 出 最 小 ， 可 以 表 为 以 下 数 学 形 式 ： nj

3、jmi i ba 11 0 ,1 ,1.min 11 1 1ij jmi ij inj ijmi nj ijijx njbx miaxts xcz 5 运 输 问 题 的 约 束 方 程 组 系 数 矩 阵 及 特 征11 12 1 21 22 2 1 21 1.1 1 1.1 . 1 1.11 1 11 1 . . . . 11 1 1n n m m mnx x x x x x x x xA 矩 阵 A是 一 个 m+n行 mn列 的 矩 阵 ， 它 的 秩 为 m+n-1。 运 输 问 题 应 该 有 m+n-1个 基 变 量 。 3. x ij的 系 数 列 向 量 为 ： m行n行(0

4、.1.0.1.0)Tij i m jP e e 6 表 上 作 业 法 7 表 上 作 业 法 的 基 本 思 路 ：确 定 初 始 调 运 方 案最 优 性 检 验改 进 方 案 8 1 确 定 初 始 基 可 行 解 运 输 问 题 确 定 初 始 基 可 行 解 ， 就 是 求 出 运 输 问题 的 初 始 调 运 方 案 . 确 定 初 始 基 可 行 解 的 方 法 有最 小 元 素 法伏 格 尔 法 9 【 例 2-1】 某 公 司 经 销 甲 产 品 ,下 设 3个 加 工 厂 A1、A2、 A3， 产 品 分 别 运 往 销 售 点 B1、 B2、 B3、 B4， 各 工 厂的

5、 日 产 量 和 各 销 售 点 的 日 需 求 量 及 各 工 厂 到 各 销 售 点的 运 价 如 下 表 所 示 ： （ 运 输 问 题 供 需 平 衡 表 和 运 价 表如 下 ） ， 求 总 运 费 最 少 的 调 运 方 案 。 销 地产 地 B1 B2 B3 B4 发 量（ T）A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9收 量 （ T） 3 6 5 6 表 3-3 10 思 路 ： 为 了 减 少 运 费 ， 应 优 先 考 虑 单 位 运 价 最 小 (或运 距 最 短 )的 供 销 业 务 ， 最 大 限 度 地 满 足 其 供 销 量 。

6、 在 可供 物 品 已 用 完 的 产 地 或 需 求 已 全 部 满 足 的 销 地 ， 以 后 将 不再 考 虑 。 然 后 ， 在 余 下 的 供 、 销 点 的 供 销 关 系 中 ， 继 续 按上 述 方 法 安 排 调 运 ， 直 至 安 排 完 所 有 供 销 任 务 ， 得 到 一 个完 整 的 调 运 方 案 (完 整 的 解 )为 止 。 这 样 就 得 到 了 运 输 问 题的 一 个 初 始 基 可 行 解 (初 始 调 运 方 案 )。 由 于 该 方 法 基 于 优 先 满 足 单 位 运 价 (或 运 距 )最 小 的 供销 业 务 ， 故 称 为 最 小 元 素

7、 法 。1、 最 小 元 素 法 11 1. 最 小 元 素 法 销 产 B1 B2 B3 B4 产 量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销 量 3 6 5 6 3 14 6 33Z=4 3+3 10+3 1+1 2+6 4+3 5=86该 方 案 总 运 费 ：（ 思 想 ： 就 近 供 应 ）不能同时划去行和列 保 证 填有 运 量的 格 子为 m+n-1表 3-4 12 最 小 元 素 法 ， 有 时 按 某 一 最 小 单 位 运 价 优 先 安 排物 品 调 运 时 ， 却 可 能 在 其 他 供 销 点 多 花 几 倍 的 运 费

8、 ，从 而 使 整 个 运 输 费 用 增 加 。55 552. 沃 格 尔 法沃 格 尔 法 考 虑 到 ： 一 个 产 地 的 产 品 假 如 不 能 按 照 最 小运 费 就 近 供 应 ， 就 考 虑 次 小 运 费 ， 这 就 有 个 差 额 。 如 果 差额 不 大 ， 当 不 能 按 最 小 单 位 运 价 安 排 运 输 时 造 成 的 运 费 损失 不 大 ； 反 之 ， 如 果 差 额 很 大 ， 不 按 最 小 运 价 组 织 运 输 就会 造 成 很 大 损 失 ， 故 应 尽 量 按 最 小 单 位 运 价 安 排 运 输 。 沃格 尔 法 就 是 基 于 这 种 考

9、 虑 提 出 来 的 。 13 沃 格 尔 法 计 算 步 骤 ：1) 分 别 算 出 各 行 、 各 列 的 最 小 运 费 与 次 小 运 费 的 差 额 。2) 从 行 、 列 中 选 出 差 额 最 大 者 ， 选 择 它 所 在 行 、 列 中 的最 小 元 素 ， 进 行 运 量 调 整 。3) 对 剩 余 行 、 列 再 分 别 计 算 各 行 、 列 的 差 额 。 返 回 1)、2)。 14 2.伏 格 尔 法 2 5 1 3 0 1 1 表 3-6 6 2 1 3 0 1 2 3 2 1 2 0 1 3 1 2 7 6 5 21 表 3-5 Z=85 15 v1 若 有 两

10、 个 以 上 相 同 的 最 大 差 值 ， 可 任 取 其一 。v2 剩 下 一 行 或 者 一 列 有 空 格 ， 填 数 字 ， 不 能划 掉 。v3 计 算 行 差 ， 列 差 时 ， 已 经 划 去 的 列 或 者 行不 再 考 虑 。 16 销产 B1 B2 B3 产 量A1 5 1 8 12A2 2 4 1 14A3 3 6 7 4销 量 9 10 11例 用 伏 格 尔 法 求 初 始 调 运 方 案 17 销产 B1 B2 B3 产 量A1 2 10 12A2 3 11 14A3 4 4销 量 9 10 11初 始 调 运 方 案 18 2.2 最 优 解 的 判 别 判 别

11、 办 法 是 计 算 空 格 (非 基 变 量 )的 检 验 数 ,因 为 运输 问 题 的 目 标 函 数 是 实 现 最 小 化 ,所 以 当 所 有 空 格 处的 检 验 数 大 于 等 于 零 时 ,为 最 优 解 .下 面 分 别 介 绍 两 种 计 算 检 验 数 的 方 法 : 闭 回 路 法 (2) 位 势 法 19 闭 回 路 法 闭 回 路 ： 从 空 格 出 发 画 水 平 (或 垂 直 )直 线 ， 遇 到填 有 运 量 的 方 格 （ 数 字 格 ） 可 转 90 ， 然 后 继 续 前 进， 直 到 到 达 出 发 的 空 格 所 形 成 的 闭 合 回 路 。 调

12、 运 方 案 的 任 意 空 格 一 定 存 在 唯 一 闭 回 路 。 销产 B1 B2 B3 B4 供 量A1 5 2 7A 2 3 1 4A3 6 3 9销 量 3 6 5 6 表 3-7 20 5 10 4 7A3 8 2 9 1A2 10 3 11 3A1 B4B3B2B1 销 地产 地 6 3 3 4 3 1计 算 最 小 元 素 法 得 到 的 初 始 基 可 行 解 的 检 验 数 (+1) (-1) (+1) (-1)(+1) 3+(-1) 3+(+1) 2+(-1) 1=1调 整 后 总 运 费 增 加 ： 空 格 处检 验 数为 1表 3-8 21 5 10 4 7A3

13、8 2 9 1A2 10 3 11 3A1 B4B3B2B1 销 地产 地 6 3 3 4 3 1 (+1) (-1) (+1) (-1) 7-5+10-3+2-1=10调 整 后 总 运 费 增 加 ： 空 格 处检 验 数为 10 (-1) (+1) 表 3-9 22 检 验 数 表110 121 -12 因 为 存 在 小 于 零 的 检 验 数 ,所 以 最 小 元 素 法 给 出 的方 案 不 是 最 优 方 案 . 表 3-10 23 2. 位 势 法位 势 ： 运 输 问 题 的 对 偶 变 量 称 为 位 势 。因 为 m个 供 应 点 n个 需 求 点 的 运 输 问 题 有

14、 m+n个 约 束 ，因 此 运 输 问 题 就 有 m+n个 位 势 。 行 位 势 :关 于 供 应 点 Ai的 约 束 对 应 的 对 偶 变 量 ， 记 为 u i, i=1,2,m。列 位 势 :关 于 需 求 点 Bj的 约 束 对 应 的 对 偶 变 量 ， 记 为 vj, j = 1,2,n。 24 定 理 ： 运 输 问 题 变 量 xij的 检 验 数ij ij i jc u v 1 1 1 01( ,. , ,. ) 10ij ij B ij ij m n ij i jc C B P c u u v v c u v 证 明 ： 25 位 势 法 求 检 验 数 的 步 骤

15、 :1.在 表 中 下 面 和 右 面 增 加 一 行 和 一 列 ,列 中 添 入 ui,行 中 添 入 vj ,令 u1=0, 按 照 , 根 据 表 中 已 有的 数 字 确 定 所 有 的 ui及 vj ; jiij vuC 2.计 算 所 有 空 格 处 的 检 验 数 . )vu(C jiijij 26 B1 B2 B3 B4 ui3 11 3 10A 1 1 9 2 8A 2 7 4 10 5A 3v j 2 -1 3 010 -5 9检验数表 1 21 -110 1224=-1 0， 当 前 方 案 不 是 最 优 方 案 。最优方案判别准则 表 3-12 27 2.3 闭 回

16、 路 调 整 法 改 进 方 案 xpq 为 换 入 变 量 =min1， 3=1 从 (p,q)空 格 开 始 画 闭 回 路 ， 其 它 转 角 点 都 是填 有 运 量 的 方 格 ， 并 从 (p,q)空 格 开 始 给 闭 回 路 上的 点 按 +1， -1， +1， -1编 号 ， -1格 的 最 小 运 量 为调 整 量 。 pqij 0min 表 3-13 28 找 到 最 小 调 整 量 以 后 ,按 照 闭 回 路 上 的 正 、 负号 ， 分 别 加 上 和 减 去 此 值 ， 得 到 新 的 运 输 方 案 。 销产 B1 B2 B3 B4 供 量A1 5 2 7A2

17、3 1 4A3 6 3 9销 量 3 6 5 6 再 用 闭 回 路 法 或 者 位 势 法 求 检 验 数 ， 得 到 下表 : 表 3-14 29 销产 B1 B2 B3 B4 供 量A1 0 2 7A2 2 1 4A3 9 12 9销 量 3 6 5 6这 时 所 有 的 检 验 数 都 非 负 ， 表 中 的 解 就 是 最 优 解 .表 3-15 30 销产 B1 B2 B3 B4 供 量A1 3 7 6 4 5A2 2 4 3 2 2A3 4 3 8 5 3销 量 3 3 2 2例 求 该 运 输 问 题 的 最 优 解 31 v表 上 作 业 法 的 计 算 步 骤 ：分 析 实

18、 际 问 题 列 出 产 销 平衡 表 及 单 位 运 价 表确 定 初 始 调 运 方 案 （ 最 小元 素 法 或 伏 格 尔 法 ）求 检 验 数 闭 回 路 或 位 势 法所 有 检 验 数 0 找 出 绝 对 值 最 大 的 负 检 验 数 ， 用 闭 合回 路 调 整 ， 得 到 新 的 调 运 方 案 得 到 最 优 方 案 ，算 出 总 运 价 32 （ 1） 若 运 输 问 题 的 某 一 基 可 行 解 有 多 个 非 基 变 量 的 检 验 数 为 负 ，在 继 续 迭 代 时 ， 取 它 们 中 任 一 变 量 为 换 入 变 量 均 可 使 目 标 函 数值 得 到

19、改 善 ， 但 通 常 取 ij0中 最 小 者 对 应 的 变 量 为 换 入 变 量 。（ 2） 无 穷 多 最 优 解产 销 平 衡 的 运 输 问 题 必 定 存 最 优 解 。 如 果 非 基 变 量 的 ij 0，则 该 问 题 有 无 穷 多 最 优 解 。 33 退 化 解 ： 表 格 中 一 般 要 有 (m+n-1)个 数 字 格 。 但 有 时 在 分 配 运 量时 则 需 要 同 时 划 去 一 行 和 一 列 ， 这 时 需 要 补 一 个 0， 以 保 证有 (m+n-1)个 数 字 格 作 为 基 变 量 。 一 般 可 在 划 去 的 行 和 列 的任 意 空

20、格 处 加 一 个 0即 可 。 利 用 进 基 变 量 的 闭 回 路 对 解 进 行 调 整 时 ， 标 有 负 号 的最 小 运 量 （ 超 过 2个 最 小 值 ） 作 为 调 整 量 ， 选 择 任 意 一 个 最小 运 量 对 应 的 基 变 量 作 为 换 出 变 量 ， 而 经 调 整 后 ， 得 到 退 化解 。 这 时 另 一 个 数 字 格 必 须 填 入 一 个 “ 0”以 示 它 为 基 变 量 。 34 销 地产 地 B1 B2 B3 B4 产 量A1 16A2 10A3 22销 量 8 14 12 1412 4 1148 3102 95 11 6(0) (2)(9

21、) (2) (1)(12)如 下 例 中 11检 验 数 是 0， 经 过 调 整 ， 可 得 到 另 一 个 最 优 解 。 其 中 绿 色 是 非 基 变 量 检 验 数 ， 红 色 为 分 配 量 。 35 销 地产 地 B1 B2 B3 B4 产 量A1 7A2 4A3 9销 量 3 6 5 6 2011 4 431 377 82 10 6 0在 x 12、 x22、 x33、 x34中 任 选 一 个 变 量 作 为 基 变 量 ， 例 如 选 x34 例 ： 用 最 小 元 素 法 求 初 始 可 行 解 36 第 三 节 产 销 不 平 衡 的 运 输 问 题 及 其 求 解 方

22、 法表 上 作 业 法 是 以 产 销 平 衡 为 前 提 的 ： 1 1m ni ji ja b 实 际 中 ， 往 往 遇 到 产 销 不 平 衡 的 运 输 问 题1.产 大 于 销 （ 供 过 于 求 ） 1 1m ni ji ja b 2.销 大 于 产 （ 供 不 应 求 ）1 1m ni ji ja b 37 产 销 不 平 衡 运 输 问 题 向 产 销 平 衡 运 输 问 题 的 转 化产 大 于 销 的 运 输 问 题 ： 1 1m ni ji ja b 1 1 11min ( 1, 2,. ). . ( 1, 2,. )0, 1, 2,. , 1, 2,.m n ij i

23、ji jn ij ijm ij ji ijz c xx a i mst x b j nx i m j n 数 学 模 型 38 设 xi n+1 是 产 地 Ai 的 储 存 量 ， 化 成 标 准 形11 111 1min ( 1, 2,. ). . ( 1, 2,. , 1)0, 1, 2,. , 1, 2,. 1m n ij iji jn ij ijm ij ji ijz c xx a i mst x b j n nx i m j n 其 中, 11 1 10, 1,.i n m nn i ji jc i mb a b 引 入 虚 拟 的 销 地 (储 存 地 )（ 需 求 量 为 ）

24、， 并 令各 个 产 地 到 虚 拟 销 地 的 单 位 运 费 为 0。 1 1m ni ji ja b 39 产 小 于 销 的 运 输 问 题 ： 1 1m ni ji ja b 引 入 一 个 虚 拟 的 产 地 （ 产 量 等 于 ） ，并 令 该 虚 拟 产 地 到 各 销 地 的 单 位 运 费 为 0。1 1n mj ij ib a 40总 供 应 量 为 19千 吨 ， 而 总 需 求 量 为 15千 吨 例 2： A1、 A2、 A3三 个 蔬 菜 生 产 地 生 产 的 蔬 菜 主 要 供 应 B1、B2、 B3、 B4四 个 城 市 。 已 知 三 个 产 地 今 年

25、的 蔬 菜 产 量 预 计 分别 为 7千 吨 、 5千 吨 和 7千 吨 ； 四 个 城 市 今 年 的 蔬 菜 需 求 量 分 别为 2千 吨 、 3千 吨 、 4千 吨 和 6千 吨 ； 从 每 个 蔬 菜 产 地 平 均 运 输 1千 吨 蔬 菜 到 各 个 城 市 的 单 位 费 用 (万 元 )见 下 表 ， 你 能 否 替 他们 编 制 一 个 总 运 费 最 省 的 蔬 菜 调 运 方 案 ？ 单 位 运 费 B1 B2 B3 B4 供 应 量A 1 2 11 3 4 7A2 10 3 5 9 5A3 7 8 1 2 7需 求 量 2 3 4 6 41 需 求 地生 产 地 B

26、1 B2 B3 B4 B5 供 应 量A1 2 11 3 4 0 7A2 10 3 5 9 0 5A3 7 8 1 2 0 7需 求 量 2 3 4 6 400-2 2 043 08 2 57 233 4 32 223 87最 优 解 中 x 15=2, x25=2， 表 示 两 个 产 地 没 有 运 出 去 的 蔬 菜 量 。 42 假 如 例 2中 各 产 地 的 蔬 菜 总 产 量 不 是 19千 吨 ， 而 是12千 吨 ， 就 成 了 一 个 供 不 应 求 的 运 输 问 题 。 单 位 运 费 B1 B2 B3 B4 供 应 量A1 2 11 3 4 3A2 10 3 5 9

27、4A3 7 8 1 2 5需 求 量 2 3 4 6 单 位 运 费 B1 B2 B3 B4 供 应 量A1 2 11 3 4 4A2 10 3 5 9 3A3 7 8 1 2 5A 4 0 0 0 0 3需 求 量 2 3 4 6 引 入 一 个 虚 拟 产 地 43 例 3 设 有 三 个 化 肥 厂 供 应 四 个 地 区 的 农 用 化 肥 。 假 定 等 量 的化 肥 在 这 些 地 区 使 用 效 果 相 同 ， 已 知 各 化 肥 厂 年 产 量 ， 各 地区 年 需 要 量 及 从 各 个 化 肥 厂 到 各 地 区 单 位 化 肥 的 运 价 如 下 表所 示 ， 试 决 定

28、 使 总 运 费 最 省 的 化 肥 调 拨 方 案 。 需 求 地 区化 肥 厂 I II III IV 产 量（ 万 吨 ）A 16 13 22 17 50B 14 13 19 15 60C 19 20 23 - 50 最 低 需 求（ 万 吨 ） 30 70 0 10最 高 需 求（ 万 吨 ） 50 70 30 不 限 44 这 是 一 个 产 销 不 平 衡 的 运 输 问 题 ， 总 产 量 160万 吨 ， 四 个地 区 的 最 低 需 求 量 为 110万 吨 ， 最 高 需 求 为 无 限 。 根 据 现有 产 量 ， 第 四 个 地 区 每 年 最 多 能 分 配 到 60

29、万 吨 ， 这 样 最 高需 求 为 210万 吨 ， 大 于 总 产 量 。 为 了 求 得 平 衡 ， 在 产 销 平衡 表 中 增 加 一 个 假 想 的 化 肥 厂 D， 其 产 量 为 50万 吨 。 由 于各 个 地 区 的 需 求 量 包 含 两 部 分 ， 其 中 最 低 需 求 量 不 能 由 假想 的 化 肥 厂 D供 应 ， 令 运 价 为 M， 而 另 一 部 分 满 足 或 不 满 足均 可 以 ， 故 也 可 以 由 假 想 的 化 肥 厂 供 应 ， 令 相 应 运 价 为 0。把 需 求 是 两 种 情 况 的 看 成 两 个 地 区 ， 得 到 这 个 问 题

30、 的 产 销平 衡 表 。 45 需 求 地 区化 肥 厂 I I II III IV IV 产 量（ 万 吨 ）A 16 16 13 22 17 17 50B 14 14 13 19 15 15 60C 19 19 20 23 M M 50D M 0 M 0 M 0 50需 求 量（ 万 吨 ） 30 20 70 30 10 50 46 需 求 地 区化 肥 厂 I I II III IV IV 产 量（ 万 吨 ）A 50 50B 20 10 30 60C 30 20 0 50D 30 20 50需 求 量（ 万 吨 ） 30 20 70 30 10 50 根 据 表 上 作 业 法 可 以 求 得 这 个 问 题 的 最 优 方 案 47 作 业 ：v课 后 习 题 ：3.1 表 3-423.2 表 3-443.3 表 3-46、 3-483.4