运筹学胡运权第三版第三章运输问题

本 章内 容 |运 输 问 题 及 其 数 学 模 型|用 表 上 作 业 法 求 解 运 输 问 题|运 输 问 题 的 进 一 步 讨 论|应 用 问 题 举 例 问 题 的 提 出 ： 一 般 的 运 输 问 题 就 是 要 解决 把 某 种 产 品 从 若 干 个 产 地 调运 到 若 干 个 销 地 ， 在 每 个 产 地的 供 应 量 与 每 个 销 地 的 需 求 量已 知 ， 并 知 道 各 地 之 间 的 运 输单 价 的 前 提 下 ， 如 何 确 定 一 个使 得 总 的 运 输 费 用 最 小 的 方 案 。 1.经 典 运 输 问 题 单 一 品 种 物资 的 运 输 调 度 问 题 由 产 地 Ai运 往 销 地 Bj的 物 品 数 量Ai到 Bj的 单 位 运 价 网 络 表 示 ：5,000 2,5006,000 B2(b2) B1(b1) B3(b3)Bn(bn) 销 地 产 地 A2(a2)Am(am)A1(a1) x22x23x21x11 x12x13x1nx2n xm3xm1 xm2xmn c11c12c13c1nc21c22c23c2ncm1cm2cm3cmn 如 果 运 输 问 题 的 总 产 量 等 于 其 总 销量 ， 即 有 则 称 该 运 输 问 题为 产 销 平 衡 运 输 问 题 ； 反 之 ， 称 产 销 不 平衡 运 输 问 题 。m ni ji=1 j=1a b 产 销 平 衡 运 输 问 题 的 数 学 模 型 可 表示 如 下 ： i=1 j=1n ij=1m ji=1minz= c= (i=1,2,.,m)s.t. = (j=1,2,.,n)0(i=1,2,.,m;j=1,2,.,n)m n ij ijijijij xx ax bx 二 、 运 输 问 题 数 学 模 型 的 特 点 ： 运 输 问 题 一 定 有 最 优 解 ； 基 变 量 的 个 数=m+n-11. 运 输 问 题 约 束 条 件 的 系 数 矩 阵 ：x1m x2m xm1 xmm 111 111 111 111111111 x11 x12 x21 x22 xm2 m行n行 |运 输 问 题 具 有 下 述 特 点 ：(1) 约 束 条 件 系 数 矩 阵 的 元 素 等于 0或 1；(2) 约 束 条 件 系 数 矩 阵 的 每 一 列有 两 个 非 零 元 素 ， 这 对 应 于 每一 个 变 量 在 前 m个 约 束 方 程 中出 现 一 次 ， 在 后 n个 约 束 方 程中 也 出 现 一 次 。 |对 产 销 平 衡 运 输 问 题 ， 除 上 述两 个 特 点 外 ， 还 有 以 下 特 点 ：(1) 所 有 结 构 约 束 条 件 都 是 等 式约 束 ；(2) 各 产 地 产 量 之 和 等 于 各 销 地销 量 之 和 。 例 1 某 部 门 有 3个 生 产 同 类 产 品 的 工 厂 (产 地 )， 生 产的 产 品 由 4个 销 售 点 (销 地 )出 售 ， 各 工 厂 的 生 产 量 、各 销 售 点 的 销 售 量 (假 定 单 位 均 为 t)以 及 各 工 厂 到各 销 售 点 的 单 位 运 价 (元 t)示 于 表 3-2中 ， 要 求 研究 产 品 如 何 调 运 才 能 使 总 运 费 最 小 ?表 3-2 销 地产 地 B1 B2 B3 B4 产 量A1 16A 2 10A3 22销 量 8 14 12 14 48428 125 410 113 9611 该 问 题 的 数 学 模 型 ：m n 11 12 13 14 21i=1 j=122 23 24 31 32 33 3411 12 13 1421 22 23 24 31 32 33 3411 21 3112 22 3213 23 3314 24 34minz = c 4 12 4 11 210 3 9 8 5 11 6=16=10=22=8s.t. =14=12=14ij iji x x x x x xx x x x x x xx x x xx x x xx x x xx x xx x xx x xx x xx 0 (i =1,2,.,m;j=1,2,.,n)j ， 12本 章内 容 | 运 输 问 题 及 其 数 学 模 型| 用 表 上 作 业 法 求 解 运 输 问 题| 运 输 问 题 的 进 一 步 讨 论| 应 用 问 题 举 例 一 、 表 上 作 业 法 的 基 本 思 想 和 步 骤 ：1.基 本 思 想 ： 同 单 纯 形 法 的 基 本 思想 基 本 可 行解 是 否 为 最 优 解换 基 结 束YN 2 用表上作业法求解运输问题 二 、 表 上 作 业 法 的 步 骤（ 1） 寻 找 初 始 基 可 行 解 ；最 小 元 素 法 、 西 北 角 法 、 沃 格 尔 法（ 2） 求 出 非 基 变 量 检 验 数 （ 空 格 检 验数 ） ， 判 断 是 否 为 最 优 解 ；闭 回 路 法 、 位 势 法（ 3） 换 基 改 进 ， 找 到 新 的 基 可 行 解闭 回 路 调 整 法（ 4 ） 重 复 （ 2） （ 3） 2 用表上作业法求解运输问题 1.最 小 元 素 法 从 运 价 最 小 的 格 开 始 ， 在 格内 的 右 下 角 标 上 允 许 取 得 的 最 大 数 。然 后 按 运 价 从 小 到 大 顺 序 填 数 。 若某 行 （ 列 ） 的 产 量 （ 销 量 ） 已 满 足 ，则 把 该 行 （ 列 ） 的 其 他 格 划 去 。 如此 进 行 下 去 ， 直 至 得 到 一 个 基 本 可行 解 。 销 地产 地 B1 B2 B3 B4 产 量A1 16A2 10A3 22销 量 8 14 12 14 48428 510 1112 34 6911 8 21014 8 61.最 小 元 素 法总 费 用 z= =10 4+6 11+8 2+2 3+14 5+8 6=246 3 4i=1 j=1cij ijx 寻找初始基可行解 2.西 北 角 法 从 西 北 角 （ 左 上 角 ） 格 开始 ， 在 格 内 的 右 下 角 标 上 允 许取 得 的 最 大 数 。 然 后 按 行 （ 列 ）标 下 一 格 的 数 。 若 某 行 （ 列 ）的 产 量 （ 销 量 ） 已 满 足 ， 则 把该 行 （ 列 ） 的 其 他 格 划 去 。 如此 进 行 下 去 ， 直 至 得 到 一 个 基本 可 行 解 。寻找初始基可行解 销 地产 地 B1 B2 B3 B4 产 量A1 16A2 10A3 22销 量 8 14 12 14 48428 510 1112 34 6911 8 46 148 82.西 北 角 法总 费 用 z= =8 4+8 12+6 10+4 3+8 11+14 6=372 3 4i=1 j=1cij ijx 寻找初始基可行解 3.沃 格 尔 法|罚 数 =次 小 费 用 -最 小 费 用|找 出 最 大 的 罚 数 行 或 列 所 对 应的 最 小 费 用 优 先 安 排 。|重 复 计 算 步 骤 1和 2 3.沃 格 尔 法 销 地产 地 B1 B2 B3 B4 产量 行 罚 数1 2 3 4 5A1 16A2 10A3 22销 量 8 14 12 14 48 列罚数 12345 4 1012 1134 691128 52 015 1 322 1 011 3 2114 88 1021 7 0622 012 42 总 费 用 z= =244 3 4i=1 j=1cij ijx寻找初始基可行解 最 优 性 检 验 就 是 检 查 所 得到 的 方 案 是 不 是 最 优 方 案 。 检查 的 方 法 与 单 纯 形 方 法 中 的 原理 相 同 ， 即 计 算 检 验 数 。 由 于目 标 要 求 极 小 ， 因 此 ， 当 所 有的 检 验 数 都 大 于 或 等 于 零 时 该调 运 方 案 就 是 最 优 方 案 ； 否 则就 不 是 最 优 ， 需 要 进 行 调 整 。下 面 介 绍 两 种 求 检 验 数 的 方 法 ：闭 回 路 法 和 对 偶 变 量 法 。 1.闭 回 路 法| 闭 回 路 ： 从 空 格 出 发 ， 遇 到 数字 格 可 以 旋 转 90度 ， 最 后 回 到 空格 所 构 成 的 回 路 ；| 原 理 ： 利 用 检 验 数 的 经 济 含 义 ；| 检 验 数 ： 非 基 变 量 增 加 一 个 单位 引 起 的 成 本 变 化 量 。| 当 所 有 非 基 变 量 的 检 验 数 均 大于 或 等 于 零 时 ， 现 行 的 调 运 方 案就 是 最 优 方 案 ， 因 为 此 时 对 现 行方 案 作 任 何 调 整 都 将 导 致 总 的 运输 费 用 增 加 。 | 闭 回 路 法 的 主 要 缺 点 是 ： 当 变量 个 数 较 多 时 ， 寻 找 闭 回 路 以 及计 算 两 方 面 都 会 产 生 困 难 。 销 地产 地 B1 B2 B3 B4 产 量A1 16A2 10A3 22销 量 8 14 12 14 481.闭 回 路 法 （ 结 合 最 小 元 素 法 的 初 始 解 ）428 125 410 113 96118 14 102 68检 验 数 11=c11-c21+c23-c13=4-2+3-4=1 24=c24-c14+c13-c23=9-11+4-3=-10,故 知 该最 小 元 素 法 的 解 不 是 最 优 解1 2110 12 -1 位 势 ： 设 对 应 基 变 量 xij的 m+n-1个 i、 j ，存 在 ui,vj 满 足 ui+vj=cij,i=1,2,.,m; j=1,2 , ,n称 这 些 ui , vj 为 该 基 本 可 行解 对 应 的 位 势 。2.对 偶 变 量 法 （ 位 势 法 ） 2.对 偶 变 量 法 （ 位 势 法 ）min Z = . .11 11 12 12 1n 1nm1 m1 m2 m2 mn mnc x + c x + +c x + +c x +c x + +c x. . . . . .11 12 1n 1 21 22 2n 2m1x +x + +x =ax +x + +x =a x + .m2 mn m11 21 m1 112 22 m2x + +x =ax + x + x =bx +x + x . . . . . . 21n 2n mn n ij =b x +x + x =b x 0 | 设 对 偶 变 量 向 量 为1 2 m 1 2 nY=(u ,u , .,u , v , v , .,v ). s.t. . i j iji ju +v ci=1,2, ,mj=1, ,nu,v 的 符 号 不 限m ni 1 j 1max z = i i j ja u b v 对 偶 规 划 为 检 验 数 ： 目 标 函 数 的 系 数 减 去 对 偶 变 量 之 和原 问 题 检 验 数 ： ij=cij-(ui+vj)特 别 对 于 m+n-1个 基 变 量 ， 有 ij=0 j = C j- CBB-1 Pj = Cj - Y Pj ij = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, ,um, v1, v2, ,vn) Pij = Cij - ( ui+ vj ) 当 xij 为 基 变 量 时 ij = Cij - ( ui+ vj )=0 由 此 ， 任 选 一 个 对 偶 变 量 为 0， 可 求出 其 余 所 有 的 ui， vj 。 再 根 据 ij = Cij - ( ui+ vj )求 出 所 有 非 基变 量 的 检 验 数 。解的最优性检验 销 地产 地 B1 B2 B3 B4 产量 uiA1 16 u1(1)A2 10 u2(0)A3 22 u3(-4)销 量 8 14 12 14 48vj v1(2) v2(9) v3(3) v4(10)428 125 410 113 9611表 3-9 1.增 加 一 位 势 列 和 位 势 行 并 计 算 位 势其 中 1 21 42 12 33 23 4u 4u 11u 2u 3u 5u 6vvvvvv 8 102 682 解的最优性检验 销 地产 地 B1 B2 B3 B4 产 量 uiA1 16 1A2 10 0A3 22 -4销 量 8 14 12 14 48vj 2 9 3 102.计 算 检 验 数 428 125 410 113 96111 2110 12 -1检 验 数 13=8-（ -4） -2=10； 24=9-10=-10,故 这 个 解 不是 最 优 解 （ +2）4.解 的 改 进 闭 回 路 调 整 法解的最优性检验 改 进 的 方 法 是 在 运 输 表 中 找 出 这 个 空格 对 应 的 闭 回 路 Lij， 在 满 足 所 有 约 束 条 件的 前 提 下 ， 使 xij尽 量 增 大 并 相 应 调 整 此 闭回 路 上 其 他 顶 点 的 运 输 量 ， 以 得 到 另 一 个更 好 的 基 可 行 解 。 销 地产 地 B1 B2 B3 B4 产量A1 10 6 16A2 8 2 10A3 14 8 22销 量 8 14 12 14 48表 3-11 428 125 410 113 9611（ -2）（ +2）（ -2） 5、 需 要 注 意 的 问 题 （ 一 ） 多 个 空 格 （ 非 基 变 量 ）的 检 验 数 为 负 ， 任 一 个 都 可 作 为换 入 变 量 。 一 般 ij0中 最 小 的 对应 变 量 作 为 换 入 变 量 。 （ 二 ） 最 优 解 时 ， 如 果 有 某非 基 变 量 的 检 验 数 为 0， 则 说 明该 运 输 问 题 有 无 穷 多 最 有 解 。 （ 三 ） 退 化 解 。解的最优性检验 本 章内 容 | 运 输 问 题 及 其 数 学 模 型| 用 表 上 作 业 法 求 解 运 输 问 题| 运 输 问 题 的 进 一 步 讨 论| 应 用 问 题 举 例 |产 销 不 平 衡 的 运 输 问 题|有 转 运 的 运 输 问 题 1.当 产 大 于 销 时 ， 即 nj jmi i ba 11 ijmi nj ij xcZ 1 11min111 , ( 1, 2,., ), ( 1, 2,., 1). . 0n ij ijm ij ji ij x a i mx b j ns t x 平 衡 后 的 数 学 模 型 为 ：加 入 假 想 销 地 （ 假 想 仓 库 ） ， 销 量为 ， 由 于 实 际 并 不 运送 ， 它 们 的 运 费 为 = 0；1 1 1m nn i ji jb a b i n+1c 2.当 销 大 于 产 时 ， 即 nj jmi i ba 11加 入 一 个 虚 设 的 产 地 去 生 产 不 足 的物 资 ； 它 的 产 量 为 1 1 1n mm j ij ia b a 接 收发 送 产 地 销 地 发 送量1 m m+1 m+n产地 1 x11 x1m x1,m+1 x1,m+n Q+a1 m xm1 xmn xm,m+1 xm,m+n Q+am销地 m+1 xm+1,1 xm+1,m xm+1,m+1 xm+1,m+n Q m+n x m+n,1 xm+n,m xm+n,m+1 xm+n,m+n Q接 收 量 Q Q Q+bm+1 Q+bm+n 表 3-15 有 转 运 输 问 题 的 运 输 表 表 3-16 有 转 运 输 问 题 的 运 价 表 接 收发 送 产 地 销 地 发送量1 m m+1 m+n产地 1 -c1 c1m c1,m+1 c1,m+n Q+a1 m c m1 -cm cm,m+1 cm,m+n Q+am销地 m+1 cm+1,1 cm+1,m -cm+1 cm+1,m+n Q m+n cm+n,1 cm+n,m cm+n,m+1 -cm+n Q接 收 量 Q Q Q+bm+1 Q+bm+n |例 5图 3-3示 出 了 一 个 运 输 系 统 ， 它 包 括 两 个 产 地 (和 )、 两 个 销 地 ( 和 )及 一 个 中 间 转 运 站 ( )，各 产 地 的 产 量 和 各 销 地 的 销 量 用 相 应 节 点 处 箭 线 旁 的 数 字 表 示 ， 节 点 连 线 上 的 数 字 表 示 其 间 的 运输 单 价 ， 节 点 旁 的 数 字 为 该 地 的 转 运 单 价 ， 试 确定 最 优 运 输 方 案 。 接 收发 送 产 地 转 运 销 地 发送量1 2 3 4 5产地 1 602 90转运 3 50销地 4 505 50接 收 量 50 50 50 80 702-35M632-355-4 5M2-14532M M456-5 表 3-17 接 收发 送 产 地 转 运 销 地 发送量1 2 3 4 5产地 1 50 10 602 50 20 20 90转运 3 30 20 50销地 4 50 505 50 50接 收 量 50 50 50 80 702-35M632-355-4 5M2-14532M M456-5 表 3-19 Z=c14x14+c25x25+c23x23+c33x33+c34x34 =2 10+4 20+2 20+3 20+5 20=300