运筹学PPT完整版

《运筹学PPT完整版》由会员分享，可在线阅读，更多相关《运筹学PPT完整版（364页珍藏版）》请在装配图网上搜索。

1、 （ 1） 运 筹 学 简 述（ 2） 运 筹 学 的 主 要 内 容（ 3） 本 课 程 的 教 材 及 参 考 书（ 4） 本 课 程 的 特 点 和 要 求（ 5） 本 课 程 授 课 方 式 与 考 核 （ 6） 运 筹 学 在 工 商 管 理 中 的 应 用本 章 主 要 内 容 ： Page 3运 筹 学 （ Operations Research）系 统 工 程 的 最 重 要 的 理 论 基 础 之 一 ， 在 美 国 有 人 把 运筹 学 称 之 为 管 理 科 学 (Management Science)。 运 筹 学 所 研 究的 问 题 ， 可 简 单 地 归 结 为

2、一 句 话 ：“ 依 照 给 定 条 件 和 目 标 ， 从 众 多 方 案 中 选 择 最 佳 方 案 ”故 有 人 称 之 为 最 优 化 技 术 。 Page 4运 筹 学 的 历 史“运 作 研 究 (Operational Research)小 组 ” :解 决 复杂 的 战 略 和 战 术 问 题 。 例 如 ： 如 何 合 理 运 用 雷 达 有 效 地 对 付 德 军 德 空 袭 对 商 船 如 何 进 行 编 队 护 航 ， 使 船 队 遭 受 德 国 潜艇 攻 击 时 损 失 最 少 ；1. 在 各 种 情 况 下 如 何 调 整 反 潜 深 水 炸 弹 的 爆 炸 深度

3、， 才 能 增 加 对 德 国 潜 艇 的 杀 伤 力 等 。 Page 5 数 学 规 划 （ 线 性 规 划 、 整 数 规 划 、 目 标 规 划 、 动 态规 划 等 ） 图 论 存 储 论 排 队 论 对 策 论 排 序 与 统 筹 方 法 决 策 分 析 Page 6选 用 教 材 运 筹 学 基 础 及 应 用 胡 运 权 主 编 哈 工 大 出 版 社参 考 教 材 运 筹 学 教 程 胡 运 权 主 编 （ 第 2版 ） 清 华 出 版 社 管 理 运 筹 学 韩 伯 棠 主 编 （ 第 2版 ） 高 等 教 育 出 版社 运 筹 学 (修 订 版 ) 钱 颂 迪 主 编 清

4、 华 出 版 社 Page 7先 修 课 ： 高 等 数 学 ， 基 础 概 率 、 线 性 代 数特 点 ： 系 统 整 体 优 化 ； 多 学 科 的 配 合 ； 模 型 方 法 的 应 用运 筹 学 的 研 究 的 主 要 步 骤 ：真 实 系 统系 统 分 析问 题 描 述 模 型 建 立与 修 改 模 型 求 解与 检 验 结 果 分 析 与实 施数 据 准 备 Page 8学 科 总 成 绩平 时 成 绩（ 40 ）课 堂 考 勤 （ 50 ） 平 时 作 业（ 50 ） 期 末 成 绩（ 60 ）讲 授 为 主 ， 结 合 习 题 作 业 Page 9运 筹 学 在 工 商 管

5、理 中 的 应 用 涉 及 几 个 方 面 ： 生 产 计 划 运 输 问 题 人 事 管 理 库 存 管 理 市 场 营 销 财 务 和 会 计1.另 外 ， 还 应 用 于 设 备 维 修 、 更 新 和 可 靠 性 分 析 ， 项 目 的 选择 与 评 价 ， 工 程 优 化 设 计 等 。 Page 10Interface上 发 表 的 部 分 获 奖 项 目组 织 应 用 效 果联 合 航 空 公 司 在 满 足 乘 客 需 求 的 前 提 下 ， 以 最 低 成 本 进行 订 票 及 机 场 工 作 班 次 安 排 每 年 节 约 成 本 600万 美 元Citgo石 油 公 司

6、优 化 炼 油 程 序 及 产 品 供 应 、 配 送 和 营 销 每 年 节 约 成 本 7000万AT Page 26 0, 5 )(25 2 )( 7 )(5 00)(32max 543321 3321 53321 43321 543321 xxxxxx xxxx xxxxx xxxxx xxxxxxZ标 准 形 式 如 下 ： Page 274. 线 性 规 划 问 题 的 解 )3(,2,1,0 )2(),2,1(. )1(max 1 1 njx mibxats xcZjnj ijij nj jj 线 性 规 划 问 题求 解 线 性 规 划 问 题 ， 就 是 从 满 足 约 束

7、条 件 (2)、 (3)的 方 程 组中 找 出 一 个 解 ， 使 目 标 函 数 (1)达 到 最 大 值 。 Page 28 可 行 解 ： 满 足 约 束 条 件 、 的 解 为 可 行 解 。 所 有 可 行 解的 集 合 为 可 行 域 。 最 优 解 ： 使 目 标 函 数 达 到 最 大 值 的 可 行 解 。 基 ： 设 A为 约 束 条 件 的 m n阶 系 数 矩 阵 (m0 4010 换出行将3化为1 5/3 1 1801/3 0 1/310 11/330 3005/3 04/3乘以1/3后得到1 0 3/51/518 0 11/52/54 0 011 Page 48例

8、 1.9 用 单 纯 形 法 求 解 0 20531 15232. 2max 321 321 321 321 xxx xxx xxxts xxxZ 、解 ： 将 数 学 模 型 化 为 标 准 形 式 ： 5,2,1,0 20531 15232. 2max 5321 4321 321 jx xxxx xxxxts xxxZj不 难 看 出 x4、 x5可 作 为 初 始 基 变 量 ， 列 单 纯 形 表 计 算 。 Page 49cj 1 2 1 0 0 icB 基 变 量 b x1 x2 x3 x4 x50 x4 15 2 -3 2 1 00 x5 20 1/3 1 5 0 11 2 1

9、0 00 x 42 x2j 201/3 1 5 0 12075 3 0 17 1 31/3 09 02j 25601 1 0 17/3 1/3 125 0 1 28/9 -1/9 2/335/3 0 0 -98/9 -1/9 -7/3j Page 50学 习 要 点 ：1. 线 性 规 划 解 的 概 念 以 及 3个 基 本 定 理2. 熟 练 掌 握 单 纯 形 法 的 解 题 思 路 及 求 解 步 骤 Page 51人 工 变 量 法 ：前 面 讨 论 了 在 标 准 型 中 系 数 矩 阵 有 单 位 矩 阵 ， 很 容易 确 定 一 组 基 可 行 解 。 在 实 际 问 题 中

10、有 些 模 型 并 不 含 有 单位 矩 阵 ， 为 了 得 到 一 组 基 向 量 和 初 基 可 行 解 ， 在 约 束 条 件的 等 式 左 端 加 一 组 虚 拟 变 量 ， 得 到 一 组 基 变 量 。 这 种 人 为加 的 变 量 称 为 人 工 变 量 ， 构 成 的 可 行 基 称 为 人 工 基 ， 用 大M法 或 两 阶 段 法 求 解 ， 这 种 用 人 工 变 量 作 桥 梁 的 求 解 方 法称 为 人 工 变 量 法 。 Page 52例 1.10 用 大 M法 解 下 列 线 性 规 划 0 122 102 434 23max 321 321 321 321 3

11、21xxx xxx xxx xxx xxxZ 、解 ： 首 先 将 数 学 模 型 化 为 标 准 形 式 5,2,1,0 122 102 434 23max 321 5321 4321 321 jx xxx xxxx xxxx xxxZj 系 数 矩 阵 中 不 存 在单 位 矩 阵 ， 无 法 建立 初 始 单 纯 形 表 。 Page 53故 人 为 添 加 两 个 单 位 向 量 ， 得 到 人 工 变 量 单 纯 形 法 数 学 模 型 ： 7,2,1,0 122 102 434 23max 7321 5321 64321 76321 jx xxxx xxxx xxxxx MxMxx

12、xxZj 其 中 ： M是 一 个 很 大 的 抽 象 的 数 ， 不 需 要 给 出 具 体 的 数 值 ，可 以 理 解 为 它 能 大 于 给 定 的 任 何 一 个 确 定 数 值 ； 再 用 前 面 介绍 的 单 纯 形 法 求 解 该 模 型 ， 计 算 结 果 见 下 表 。 Page 54cj 3 2 -1 0 0 -M -MCB XB b x1 x2 x3 x4 x5 x6 x7 i0 x6 4 -4 3 1 -1 0 1 0 4-M x5 10 1 -1 2 0 1 0 0 5-M x7 1 2 -2 1 0 0 0 1 13-2M 2+M -1+2M -M0 x 6 3

13、-6 5 0 -1 0 1 3/5-M x5 8 -3 3 0 0 1 0 8/3-1 x3 1 2 -2 1 0 0 0 5-6M 5M 0 -M 0 02 x2 3/56/5 1 01/5 0 -M x5 31/5 3/5 0 0 3/5 1 31/3-1 x3 11/52/5 0 12/5 0 5 0 0 0 02 x 2 13 0 1 0 1 23 x1 31/3 1 0 0 1 5/3-1 x3 19/3 0 0 1 0 2/30 0 0 -5 -25/3 j j j j Page 55解 的 判 别 ：1） 唯 一 最 优 解 判 别 ： 最 优 表 中 所 有 非 基 变 量 的

14、 检 验 数 非 零 ,则 线 规 划 具 有 唯 一 最 优 解 。2） 多 重 最 优 解 判 别 ： 最 优 表 中 存 在 非 基 变 量 的 检 验 数 为 零 ,则 线 则 性 规 划 具 有 多 重 最 优 解 （ 或 无 穷 多 最 优 解 ） 。3） 无 界 解 判 别 ： 某 个 k0且 aik （ i=1， 2,m） 则 线 性规 划 具 有 无 界 解 。4） 无 可 行 解 的 判 断 ： 当 用 大 M单 纯 形 法 计 算 得 到 最 优 解 并且 存 在 Ri0时 ， 则 表 明 原 线 性 规 划 无 可 行 解 。5） 退 化 解 的 判 别 ： 存 在 某

15、 个 基 变 量 为 零 的 基 本 可 行 解 。 Page 56单 纯 性 法 小 结 :建立模型 个 数 取 值 右 端 项 等 式 或不 等 式 极 大 或 极 小 新 加 变 量系 数两个 三 个以 上 x j0 xj无约 束 xj 0 bi 0 bi mi 时 ， 企 业 愿 意购 进 这 种 资 源 ， 单 位 纯 利 为 yi* mi ， 则 有 利 可 图 ； 如 果 yi* mi 则 购 进 资 源 i， 可 获 单 位 纯 利 yi* mi 若 yi* mi则 转 让 资 源 i ， 可 获 单 位 纯 利 mi yi Page 993） 影 子 价 格 在 资 源 利

16、用 中 的 应 用根 据 对 偶 理 论 的 互 补 松 弛 性 定 理 :Y*Xs=0 , YsX*=0表 明 生 产 过 程 中 如 果 某 种 资 源 bi未 得 到 充 分 利 用 时 ， 该 种 资源 的 影 子 价 格 为 0； 若 当 资 源 资 源 的 影 子 价 格 不 为 0时 ， 表 明该 种 资 源 在 生 产 中 已 耗 费 完 。 Page 1004） 影 子 价 格 对 单 纯 形 表 计 算 的 解 释单 纯 形 表 中 的 检 验 数 mi iijjjBjj yacPBCc 11其 中 cj表 示 第 j种 产 品 的 价 格 ; 表 示 生 产 该 种 产

17、品 所消 耗 的 各 项 资 源 的 影 子 价 格 的 总 和 ,即 产 品 的 隐 含 成 本 。mi iijya1当 产 值 大 于 隐 含 成 本 时 ， 即 ， 表 明 生 产 该 项 产 品 有利 ， 可 在 计 划 中 安 排 ； 否 则 ， 用 这 些 资 源 生 产 别 的产 品 更 有 利 ， 不 在 生 产 中 安 排 该 产 品 。0j 0j Page 101 对 偶 单 纯 形 法 是 求 解 线 性 规 划 的 另 一 个 基 本 方 法 。 它是 根 据 对 偶 原 理 和 单 纯 形 法 原 理 而 设 计 出 来 的 ， 因 此 称 为对 偶 单 纯 形 法

18、。 不 要 简 单 理 解 为 是 求 解 对 偶 问 题 的 单 纯 形法 。 找 出 一 个 对 偶 问 题 的 可 行 基 ， 保 持 对 偶 问 题 为 可 行 解 的条 件 下 ， 判 断 X B是 否 可 行 （ XB为 非 负 ） ， 若 否 ， 通 过 变 换 基解 ， 直 到 找 到 原 问 题 基 可 行 解 （ 即 XB为 非 负 ） ， 这 时 原 问 题与 对 偶 问 题 同 时 达 到 可 行 解 ， 由 定 理 4可 得 最 优 解 。 Page 102找 出 一 个 DP的 可 行 基LP是 否 可 行（ XB 0）保 持 DP为 可 行 解 情 况 下 转 移

19、 到 LP的 另 一 个 基 本 解 最 优 解是否循环 结 束 Page 103例 2.9 用 对 偶 单 纯 形 法 求 解 ： )3.2.1(0 145 1232 1022 15129min 321 321 321 321jx xxx xxx xxx xxxZj解 :（ 1） 将 模 型 转 化 为 求 最 大 化 问 题 ， 约 束 方 程 化 为 等 式 求出 一 组 基 本 解 ， 因 为 对 偶 问 题 可 行 ， 即 全 部 检 验 数 0（ 求max问 题 ） 。 Page 104 0 14 5 12 32 10 22 15129max61 6321 5321 4321 32

20、1x xxxx xxxx xxxx xxxZcj -9 -12 -15 0 0 0 bcB xB x1 x2 x3 x4 x5 x60 x4 -2 -2 -1 1 0 0 -100 x5 -2 -3 -1 0 1 0 -120 x6 -1 -1 -5 0 0 1 -14 (-9/-1.-12/-1. -15/-5)j -9 -12 -15 0 0 0 0 i Page 105cj -9 -12 -15 0 0 0 bcB xB x1 x2 x3 x4 x5 x60 x4 -9/5 -9/5 0 1 0 -1/5 -36/50 x5 -9/5 -14/5 0 0 1 -1/5 -46/5-15

21、x3 1/5 1/5 1 0 0 -1/5 14/5 (-30/-9,-45/-14,-15/-1)-6 -9 0 0 0 -3 42 ic j -9 -12 -15 0 0 0 bcB xB x1 x2 x3 x4 x5 x60 x4 -9/14 0 0 1 -9/14 -1/14 -9/7-12 x2 9/14 1 0 0 -5/14 1/14 23/7 (-3/-9,-45/-9,-33/-1)-15 x3 1/14 0 1 0 1/14 -3/14 15/7-3/14 0 0 0 -45/14 -33/14 ij j Page 106cj -9 -12 -15 0 0 0cB xB x

22、1 x2 x3 x4 x5 x6 b-9 x1 1 0 0 -14/9 1 1/9 2-12 x2 0 1 0 1 -1 0 2-15 x 3 0 0 1 1/9 0 -2/9 20 0 0 -1/3 -3 -7/3j原 问 题 的 最 优 解 为 ： X*=（ 2 , 2 , 2 , 0 , 0 , 0） ， Z* =72 其 对 偶 问 题 的 最 优 解 为 ： Y*= （ 1/3 , 3 , 7/3） ， W*= 72 Page 107 对 偶 单 纯 形 法 应 注 意 的 问 题 ： 用 对 偶 单 纯 形 法 求 解 线 性 规 划 是 一 种 求 解 方 法 ， 而 不 是 去

23、 求 对 偶问 题 的 最 优 解 初 始 表 中 一 定 要 满 足 对 偶 问 题 可 行 ， 也 就 是 说 检 验 数 满 足 最 优 判别 准 则 最 小 比 值 中 的 绝 对 值 是 使 得 比 值 非 负 ， 在 极 小 化 问 题 j 0，分 母 a ij0 这 时 必 须 取 绝 对 值 。 在 极 大 化 问 题 中 ， j 0， 分 母aij0， 总 满 足 非 负 ， 这 时 绝 对 值 符 号 不 起 作 用 ， 可 以 去 掉 。 如在 本 例 中 将 目 标 函 数 写 成ijja这 里 j 0在 求 k时 就 可 以 不 带 绝 对 值 符 号 。 321 3

24、4max xxxz ijja Page 108 对 偶 单 纯 形 法 与 普 通 单 纯 形 法 的 换 基 顺 序 不 一 样 ， 普 通 单 纯 形 法是 先 确 定 进 基 变 量 后 确 定 出 基 变 量 ， 对 偶 单 纯 形 法 是 先 确 定 出 基 变量 后 确 定 进 基 变 量 ； 普 通 单 纯 形 法 的 最 小 比 值 是 其 目 的 是 保 证 下 一个 原 问 题 的 基 本 解 可 行 ， 对 偶 单 纯 形 法 的 最 小 比 值 是 0min ikikii aab其 目 的 是 保 证 下 一 个 对 偶 问 题 的 基 本 解 可 行 0|min lj

25、ljjj aa 对 偶 单 纯 形 法 在 确 定 出 基 变 量 时 ， 若 不 遵 循 规 则 ， 任 选 一 个 小 于 零 的 bi对 应 的 基 变 量 出 基 ， 不 影 响 计 算 结 果 ，只 是 迭 代 次 数 可 能 不 一 样 。 0|min iil bbb Page 109学 习 要 点 ：1. 线 性 规 划 解 的 概 念 以 及 3个 基 本 定 理2. 熟 练 掌 握 单 纯 形 法 的 解 题 思 路 及 求 解 步 骤 运 输 规 划 问 题 的 数 学 模 型 表 上 作 业 法 运 输 问 题 的 应 用 Page 111例 3.1 某 公 司 从 两

26、个 产 地 A1、 A2将 物 品 运 往 三 个 销 地 B1, B2, B3， 各 产 地 的 产 量 、 各 销 地 的 销 量 和 各 产 地 运 往 各 销 地 每 件物 品 的 运 费 如 下 表 所 示 ， 问 ： 应 如 何 调 运 可 使 总 运 输 费 用 最小 ？ B1 B2 B3 产 量A1 6 4 6 200A2 6 5 5 300销 量 150 150 200 Page 112解 ： 产 销 平 衡 问 题 ： 总 产 量 = 总 销 量 500 设 xij 为 从 产 地 Ai运 往 销 地 Bj的 运 输 量 ， 得 到 下 列 运 输 量表 ： B1 B2 B

27、3 产 量A1 x11 x12 x13 200A2 x 21 x22 x23 300销 量 150 150 200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3） Page 113运 输 问 题 的 一 般 形 式 ： 产 销 平 衡A1、 A2、 、 Am 表 示 某 物 资 的 m个 产 地 ； B1、 B2、 、

28、 Bn 表 示某 物 质 的 n个 销 地 ； ai 表 示 产 地 Ai的 产 量 ； bj 表 示 销 地 Bj 的 销 量 ； cij 表 示 把 物 资 从 产 地 Ai运 往 销 地 Bj的 单 位 运 价 。 设 xij 为 从 产 地 Ai运 往 销 地 Bj的 运 输 量 ， 得 到 下 列 一 般 运 输 量 问 题 的 模 型 ： mi nj ijij xcz 1 1min njmix njbx miaxts ij jmi ijnj iij ,1;,1,0 ,1 ,1. 11 Page 114变 化 ： 1） 有 时 目 标 函 数 求 最 大 。 如 求 利 润 最 大

29、或 营 业 额 最 大 等 ； 2） 当 某 些 运 输 线 路 上 的 能 力 有 限 制 时 ， 在 模 型 中 直 接 加 入约 束 条 件 （ 等 式 或 不 等 式 约 束 )； 3） 产 销 不 平 衡 时 ， 可 加 入 假 想 的 产 地 （ 销 大 于 产 时 ） 或 销地 （ 产 大 于 销 时 ） 。定 理 : 设 有 m个 产 地 n个 销 地 且 产 销 平 衡 的 运 输 问 题 ， 则 基 变量 数 为 m+n-1。 Page 115表 上 作 业 法 是 一 种 求 解 运 输 问 题 的 特 殊 方 法 ， 其 实 质 是 单 纯形 法 。步 骤 描 述 方

30、法第 一 步 求 初 始 基 行 可 行 解 （ 初 始 调 运 方 案 ） 最 小 元 素 法 、元 素 差 额 法 、第 二 步 求 检 验 数 并 判 断 是 否 得 到 最 优 解 当 非 基 变 量 的检 验 数 ij全 都 非 负 时 得 到 最 优 解 ， 若 存 在 检 验数 ij 0， 说 明 还 没 有 达 到 最 优 ， 转 第 三 步 。 闭 回 路 法 和 位势 法第 三 步 调 整 运 量 ， 即 换 基 ， 选 一 个 变 量 出 基 ， 对 原 运量 进 行 调 整 得 到 新 的 基 可 行 解 ， 转 入 第 二 步 Page 116例 3.2 某 运 输

31、资 料 如 下 表 所 示 ：单 位 销 地 运 价 产 地 产 量3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 64321 BBBB 321AAA问 ： 应 如 何 调 运 可 使 总 运 输 费 用 最 小 ？ Page 117解 ： 第 1步 求 初 始 方 案方 法 1： 最 小 元 素 法 基 本 思 想 是 就 近 供 应 ， 即 从 运 价 最 小 的 地 方 开 始 供 应 （ 调运 ） ， 然 后 次 小 ， 直 到 最 后 供 完 为 止 。B1 B2 B3 B4 产 量A 1 7A2 4A3 9销 量 3 6 5 63 11 3 101

32、9 27 4 10 583 416 33 Page 118总 的 运 输 费 (3 1)+(6 4) +(4 3) +(1 2)+(3 10)+(3 5)=86元元 素 差 额 法 对 最 小 元 素 法 进 行 了 改 进 ， 考 虑 到 产 地 到 销地 的 最 小 运 价 和 次 小 运 价 之 间 的 差 额 ， 如 果 差 额 很 大 ， 就 选最 小 运 价 先 调 运 ， 否 则 会 增 加 总 运 费 。 例 如 下 面 两 种 运 输 方案 。 8 5 102 1 2015 1515510总 运 费 是 z=10 8+5 2+15 1=105最 小 元 素 法 ： Page

33、1198 5 102 1 2015 15515 10总 运 费 z=10 5+15 2+5 1=85后 一 种 方 案 考 虑 到 C11与 C21之 间的 差 额 是 8 2=6， 如 果 不 先 调 运x21， 到 后 来 就 有 可 能 x110， 这样 会 使 总 运 费 增 加 较 大 ， 从 而 先调 运 x21， 再 是 x22， 其 次 是 x12用 元 素 差 额 法 求 得 的 基 本 可 行 解 更 接 近 最 优 解 ， 所以 也 称 为 近 似 方 案 。 Page 120方 法 2： Vogel法1） 从 运 价 表 中 分 别 计 算 出 各 行 和 各 列 的

34、最 小 运 费 和 次 最 小 运费 的 差 额 ， 并 填 入 该 表 的 最 右 列 和 最 下 行 。B1 B2 B3 B4 产 量A1 7A 2 4A3 9销 量 3 6 5 63 11 3 101 9 27 4 10 58 Page 1212） 再 从 差 值 最 大 的 行 或 列 中 找 出 最 小 运 价 确 定 供 需 关 系 和供 需 数 量 。 当 产 地 或 销 地 中 有 一 方 数 量 供 应 完 毕 或 得 到 满 足时 ， 划 去 运 价 表 中 对 应 的 行 或 列 。重 复 1)和 2)， 直 到 找 出 初 始 解 为 至 。B 1 B2 B3 B4 产

35、 量A1 7A2 4A3 9销 量 3 6 5 63 11 3 101 9 27 4 10 58 Page 122单 位 销 地 运 价 产 地 产 量 行 差 额3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6 列 差 额 4321 BBBB321AAA 711 352 15 Page 123单 位 销 地 运 价 产 地 产 量 行 差 额3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6列 差 额 4321 BBBB 321AAA 71352 753 Page 124单 位 销 地 运 价 产 地 产 量 行 差 额3 1

36、1 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6列 差 额 4321 BBBB 321AAA 1135 1536 312该 方 案 的 总 运 费 :(1 3) (4 6) (3 5) (2 10) (1 8) (3 5) 85元 Page 125求 出 一 组 基 可 行 解 后 ， 判 断 是 否 为 最 优 解 ， 仍 然 是 用 检验 数 来 判 断 ， 记 xij的 检 验 数 为 ij由 第 一 章 知 ， 求 最 小 值 的 运输 问 题 的 最 优 判 别 准 则 是 ：所 有 非 基 变 量 的 检 验 数 都 非 负 ， 则 运 输 方 案 最

37、优求 检 验 数 的 方 法 有 两 种 ： 闭 回 路 法 位 势 法 （ ） Page 126闭 回 路 的 概 念 , 132222111 jsisjsijijijiji xxxxxx 称 集 合 ),( 2121 互 不 相 同；其 中 ss jjjiii 为 一 个 闭 回 路 ， 集 合 中 的 变 量 称 为 回 路 的 顶 点 ， 相 邻 两 个 变量 的 连 线 为 闭 回 路 的 边 。 如 下 表 Page 127例 下 表 中 闭 回 路 的 变 量 集 合 是 x11,x12,x42,x43,x23,x25,x35, x31共有 8个 顶 点 ， 这 8个 顶 点 间

38、 用 水 平 或 垂 直 线 段 连 接 起 来 ， 组 成一 条 封 闭 的 回 路 。 B1 B2 B3 B4 B5A 1 X11 X12A2 X23 X25A3 X31 X35A4 X42 X43 一 条 回 路 中 的 顶 点 数 一 定 是 偶 数 ， 回 路 遇 到 顶 点 必 须 转 90度 与 另 一 顶 点 连 接 ， 表 3 3中 的 变 量 x 32及 x33不 是 闭 回 路 的 顶点 ， 只 是 连 线 的 交 点 。 Page 128闭 回 路 , 123233434111 xxxxxx B1 B2 B3A1 X11 X12A2A 3 X32 X33A4 X41 X

39、43例 如 变 量 组 不 能 构 成 一 条 闭 回 路 ，但 A中 包 含 有 闭 回 路 , 121131352521 xxxxxxA , 31352521 xxxx变 量 组 变 量 数 是 奇 数 ， 显 然 不 是闭 回 路 ， 也 不 含 有 闭 回 路 ； , 2111123233 xxxxxB Page 129用 位 势 法 对 初 始 方 案 进 行 最 优 性 检 验 ：1） 由 ij=Cij-（ Ui+Vj） 计 算 位 势 Ui ， Vj ， 因 对 基 变 量 而 言 有 ij=0， 即Cij-（ Ui+Vj） = 0， 令 U1=02）再由ij=Cij-（Ui+V

40、j）计算非基变量的检验数ijB1 B2 B3 B4 UiA 1A2A3Vj 3 11 3 101 9 27 4 10 5843 6 31 3 当 存 在 非 基变 量 的 检 验数 kl 0， 说明 现 行 方 案为 最 优 方 案 ，否 则 目 标 成本 还 可 以 进一 步 减 小 。 Page 130当 存 在 非 基 变 量 的 检 验 数 kl 0 且 kl =minij时 ， 令 Xkl 进基 。 从 表 中 知 可 选 X24进 基 。第 3步 确 定 换 入 基 的 变 量第 4步 确 定 换 出 基 的 变 量以 进 基 变 量 xik为 起 点 的 闭 回 路 中 ， 标

41、有 负 号 的 最 小 运 量 作 为调 整 量 ， 对 应 的 基 变 量 为 出 基 变 量 ， 并 打 上 “ ”以 示 换出 作 为 非 基 变 量 。 Page 131B1 B2 B3 B4 UiA1A2A 3Vj 3 111 97 43 6 13,1minmin 14,23 xx调 整 步 骤 为 ： 在 进 基 变 量 的 闭 回 路 中 标 有 正 号 的 变 量 加 上 调 整 量， 标 有 负 号 的 变 量 减 去 调 整 量 ， 其 余 变 量 不 变 ， 得 到 一 组 新 的基 可 行 解 。 然 后 求 所 有 非 基 变 量 的 检 验 数 重 新 检 验 。

42、Page 132当 所 有 非 基 变 量 的 检 验 数 均 非 负 时 ， 则 当 前 调 运 方 案 即 为 最优 方 案 ， 如 表 此 时 最 小 总 运 费 ：Z =(1 3) (4 6) (3 5) (2 10) (1 8) (3 5) 85元B1 B2 B3 B4 UiA1A2A 3Vj 3 11 3 101 9 27 4 10 5853 6 312 Page 133表 上 作 业 法 的 计 算 步 骤 ：分 析 实 际 问 题 列 出 产 销 平衡 表 及 单 位 运 价 表确 定 初 始 调 运 方 案 （ 最 小元 素 法 或 Vogel法 ）求 检 验 数 （ 位 势

43、 法 ） 所 有 检 验 数 0找 出 绝 对 值 最 大 的 负 检 验 数 ， 用 闭 合回 路 调 整 ， 得 到 新 的 调 运 方 案 得 到 最 优 方 案 ，算 出 总 运 价 Page 134（ 1） 若 运 输 问 题 的 某 一 基 可 行 解 有 多 个 非 基 变 量 的 检 验 数为 负 ， 在 继 续 迭 代 时 ， 取 它 们 中 任 一 变 量 为 换 入 变 量 均 可 使目 标 函 数 值 得 到 改 善 ， 但 通 常 取 ij0中 最 小 者 对 应 的 变 量 为换 入 变 量 。（ 2） 无 穷 多 最 优 解产 销 平 衡 的 运 输 问 题 必

44、定 存 最 优 解 。 如 果 非 基 变 量 的 ij0， 则 该 问 题 有 无 穷 多 最 优 解 。 Page 135 退 化 解 ： 表 格 中 一 般 要 有 (m+n-1)个 数 字 格 。 但 有 时 在 分 配 运 量时 则 需 要 同 时 划 去 一 行 和 一 列 ， 这 时 需 要 补 一 个 0， 以 保 证有 (m+n-1)个 数 字 格 作 为 基 变 量 。 一 般 可 在 划 去 的 行 和 列 的任 意 空 格 处 加 一 个 0即 可 。 利 用 进 基 变 量 的 闭 回 路 对 解 进 行 调 整 时 ， 标 有 负 号 的最 小 运 量 （ 超 过

45、2个 最 小 值 ） 作 为 调 整 量 ， 选 择 任 意 一 个 最小 运 量 对 应 的 基 变 量 作 为 出 基 变 量 ， 并 打 上 “ ”以 示 作 为非 基 变 量 。 Page 136 销 地产 地 B1 B2 B3 B4产量A1 16A 2 10A3 22销 量 8 14 12 1412 4 1148 3102 95 11 6(0) (2)(9) (2) (1)(12)如 下 例 中 11检 验 数 是 0， 经 过 调 整 ， 可 得 到 另 一 个 最 优 解 。 Page 137 销 地产 地 B1 B2 B3 B4产量A1 7A 2 4A3 9销 量 3 6 5

46、6 2011 4 431 377 82 10 6 0 在 x12、 x22、 x33、 x34中 任 选 一 个 变 量 作 为 基 变 量 ， 例 如 选 x34例 ： 用 最 小 元 素 法 求 初 始 可 行 解 Page 138目 标 函 数 求 利 润 最 大 或 营 业 额 最 大 等 问 题 。 mi nj ijijxCZ 1 1max njmix njbx miax ijmi jijnj iij ,2,1;,2,10 ,2,1 ,2,111 ， Page 139求 解 方 法 ：将 极 大 化 问 题 转 化 为 极 小 化 问 题 。 设 极 大 化 问 题 的 运价 表 为

47、 C ， 用 一 个 较 大 的 数 M（ Mmaxcij） 去 减 每 一 个 cij得 到 矩 阵 C， 其 中 C=（ M cij） 0,将 C作 为 极 小 化 问 题 的运 价 表 ， 用 表 上 用 业 法 求 出 最 优 解 。 Page 140例 3.3 下 列 矩 阵 C是 Ai（ I=1， 2， 3） 到 Bj的 吨 公 里 利 润 ,运 输部 门 如 何 安 排 运 输 方 案 使 总 利 润 最 大 . 销 地产 地 B1 B2 B3产量A1A 2A3销 量 ijijij ccccM 10,10max /22取 Page 141 销 地产 地 B1 B2 B3产量A1A

48、2A 3销 量得 到 新 的 最 小 化 运 输 问 题 ， 用 表 上 作 业 法 求 解 即 可 。 Page 142 当 总 产 量 与 总 销 量 不 相 等 时 ,称 为 不 平 衡 运 输 问 题 .这类 运 输 问 题 在 实 际 中 常 常 碰 到 ,它 的 求 解 方 法 是 将 不 平 衡 问题 化 为 平 衡 问 题 再 按 平 衡 问 题 求 解 。 当 产 大 于 销 时 ， 即 ： mi nj ji ba1 1数 学 模 型 为 ： mi nj ijijxcZ 1 1min njmix njbx miaxijmi jijnj iij ,2,1;,2,10 ,2,1

49、,2,111 ， Page 143由 于 总 产 量 大 于 总 销 量 ， 必 有 部 分 产 地 的 产 量 不 能 全 部 运 送 完 ，必 须 就 地 库 存 ， 即 每 个 产 地 设 一 个 仓 库 ， 假 设 该 仓 库 为 一 个 虚 拟销 地 Bn+1， bn+1作 为 一 个 虚 设 销 地 Bn+1的 销 量 (即 库 存 量 )。 各 产 地Ai到 Bn+1的 运 价 为 零 ， 即 Ci,n+1=0,（ i=1， ， m） 。 则 平 衡 问 题 的数 学 模 型 为 ： mi nj ijij xcZ 1 1min ,2,1,2,1,0 1,2,1 ,2,1111 j

50、mix njbx miax ijmi jijnj iij ； 具 体 求 解 时 ,只 在运 价 表 右 端 增 加一 列 Bn+1， 运 价为 零 ,销 量 为 bn+1即 可 Page 144 当 销 大 于 产 时 ， 即 ： mi nj ji ba1 1 mi nj ijijxCZ 1 1min ,2,1;,2,1,0 ,2,1 ,2,111 jmix njbx miax ijmi jij nj iij数 学 模 型 为 ： 由 于 总 销 量 大 于 总 产量 ,故 一 定 有 些 需 求 地不 完 全 满 足 ,这 时 虚 设一 个 产 地 Am+1， 产 量为 ： mi inj

51、j ab 11 Page 145销 大 于 产 化 为 平 衡 问 题 的 数 学 模 型 为 ： mi nj ijij xcZ 1 1min njmix njbx miaxijmi jijnj iji ,2,11,2,1,0 ,2,1 1,2,1111 ；具 体 计 算 时 ， 在 运 价 表 的 下 方 增 加 一 行 Am+1， 运 价 为 零 。 产量 为 am+1即 可 。 Page 146例 3.4 求 下 列 表 中 极 小 化 运 输 问 题 的 最 优 解 。 B1 B2 B3 B4 aiA1 5 9 2 3 60A2 - 4 7 8 40A3 3 6 4 2 30A4 4

52、8 10 11 50b j 20 60 35 45 180160 41 41 160180i j ji ba因 为 有 ： Page 147所 以 是 一 个 产 大 于 销 的 运 输 问 题 。 表 中 A2不 可 达 B1， 用 一 个很 大 的 正 数 M表 示 运 价 C21。 虚 设 一 个 销 量 为 b5=180-160=20，Ci5=0， i=1,2,3,4， 表 的 右 边 增 添 一 列 ， 得 到 新 的 运 价 表 。B1 B2 B3 B4 B5 aiA1 5 9 2 3 0 60A2 M 4 7 8 0 40A3 3 6 4 2 0 30A4 4 8 10 11 0

53、 50 bj 20 60 35 45 20 180 Page 148下 表 为 计 算 结 果 。 可 看 出 ： 产 地 A4还 有 20个 单 位 没 有 运 出 。B1 B2 B3 B4 B5 AiA1 35 25 60A2 40 40A3 10 20 30A4 20 10 20 50Bj 20 60 35 45 20 180 Page 1493. 生 产 与 储 存 问 题例 3.5 某 厂 按 合 同 规 定 须 于 当 年 每 个 季 度 末 分 别 提 供 10、 15、 25、20台 同 一 规 格 的 柴 油 机 。 已 知 该 厂 各 季 度 的 生 产 能 力 及 生 产

54、 每 台柴 油 机 的 成 本 如 右 表 。 如 果 生 产 出 来 的 柴 油 机 当 季 不 交 货 ， 每 台每 积 压 一 个 季 度 需 储 存 、 维 护 等 费 用 0.15万 元 。 试 求 在 完 成 合 同的 情 况 下 ， 使 该 厂 全 年 生 产 总 费 用 为 最 小 的 决 策 方 案 。季 度 生 产 能 力 /台 单 位 成 本 /万 元25 10.8 35 11.130 1110 11.3 Page 150解 ： 设 xij为 第 i 季 度 生 产 的 第 j 季 度 交 货 的 柴 油 机 数 目 ， 那么 应 满 足 ：交 货 ： x11 = 10

55、生 产 ： x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10把 第 i 季 度 生 产 的 柴 油 机 数 目 看 作 第 i 个 生 产 厂 的 产 量 ； 把 第 j 季度 交 货 的 柴 油 机 数 目 看 作 第 j 个 销 售 点 的 销 量 ； 设 cij是 第 i季 度 生产 的 第 j季 度 交 货 的 每 台 柴 油 机 的 实 际 成 本 ， 应 该 等 于 该 季 度 单

56、 位成 本 加 上 储 存 、 维 护 等 费 用 。 可 构 造 下 列 产 销 平 衡 问 题 ： Page 151 ji产 量10.8 10.95 11.1 11.25 25M 11.10 11.25 11.40 35M M 11.00 11.15 30M M M 11.30 10销 量 10 15 25 20 10070由 于 产 大 于 销 ， 加 上 一 个 虚 拟 的 销 地 D， 化 为 平 衡 问 题 ，即 可 应 用 表 上 作 业 法 求 解 。 Page 152该 问 题 的 数 学 模 型 ：Min f = 10.8 x11 +10.95 x12 +11.1 x13

57、+11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 jiD 产 量10.8 10.95 11.1 11.25 0 25M 11.10 11.25 11.40 0 35M M 11.00 11.15 0 30 M M M 11.30 0 10销 量 10 15 25 20 30 100100 Page 153 jiD 产 量10 15 0 250 5 30 3525 5 3010 10 销 量 10 15 25 20 30 100100最 优 生 产 决 策 如 下 表 ， 最 小 费 用 z 773万

58、 元 。 整 数 规 划 的 特 点 及 应 用 分 支 定 界 法 分 配 问 题 与 匈 牙 利 法 Page 155要 求 一 部 分 或 全 部 决 策 变 量 取 整 数 值 的 规 划 问 题 称 为整 数 规 划 。 不 考 虑 整 数 条 件 ， 由 余 下 的 目 标 函 数 和 约 束 条 件构 成 的 规 划 问 题 称 为 该 整 数 规 划 问 题 的 松 弛 问 题 。 若 该 松 弛问 题 是 一 个 线 性 规 划 ， 则 称 该 整 数 规 划 为 整 数 线 性 规 划 。整 数 线 性 规 划 数 学 模 型 的 一 般 形 式 ： 且 部 分 或 全 部

59、 为 整 数或 n)1.2(j 0 )2.1( )min(max1 1 jnj ijij nj jjx mibxa xcZZ Page 156 纯 整 数 线 性 规 划 ： 指 全 部 决 策 变 量 都 必 须 取 整 数 值 的 整 数线 性 规 划 。 混 合 整 数 线 性 规 划 ： 决 策 变 量 中 有 一 部 分 必 须 取 整 数 值 ，另 一 部 分 可 以 不 取 整 数 值 的 整 数 线 性 规 划 。 0-1型 整 数 线 性 规 划 ： 决 策 变 量 只 能 取 值 0或 1的 整 数 线 性 规划 。 Page 157例 4.1 工 厂 A1和 A2生 产

60、某 种 物 资 。 由 于 该 种 物 资 供 不 应 求 ， 故 需 要再 建 一 家 工 厂 。 相 应 的 建 厂 方 案 有 A3和 A4两 个 。 这 种 物 资 的 需 求 地有 B1,B2,B3,B4四 个 。 各 工 厂 年 生 产 能 力 、 各 地 年 需 求 量 、 各 厂 至 各需 求 地 的 单 位 物 资 运 费 cij， 见 下 表 ：B1 B2 B3 B4 年 生 产 能 力A1 2 9 3 4 400A2 8 3 5 7 600 A3 7 6 1 2 200A4 4 5 2 5 200年 需 求 量 350 400 300 150工 厂 A3或 A4开 工 后

61、 ， 每 年 的 生 产 费 用 估 计 分 别 为 1200万 或 1500万元 。 现 要 决 定 应 该 建 设 工 厂 A3还 是 A4， 才 能 使 今 后 每 年 的 总 费 用最 少 。 Page 158解 ： 这 是 一 个 物 资 运 输 问 题 ， 特 点 是 事 先 不 能 确 定 应 该 建 A3还 是 A4中 哪 一 个 ， 因 而 不 知 道 新 厂 投 产 后 的 实 际 生 产 物 资 。为 此 ， 引 入 0-1变 量 ： )2,1(01 iy i 若 不 建 工 厂若 建 工 厂再 设 xij为 由 Ai运 往 Bj的 物 资 数 量 ， 单 位 为 千 吨

62、 ； z表 示 总 费 用 ，单 位 万 元 。则 该 规 划 问 题 的 数 学 模 型 可 以 表 示 为 ： Page 159 )2,1(1,0 )4,3,2,1,(0 200200600400150300400 350. 15001200min 244434241 134333231 24232221 14131211 44342414 43332313 42322212 41312111 41 41 21 iy jix yxxxx yxxxx xxxx xxxx xxxx xxxx xxxx xxxxts yyxcz iij i j ijij 混 合 整 数 规 划 问 题 Page

63、 160例 4.2 现 有 资 金 总 额 为 B。 可 供 选 择 的 投 资 项 目 有 n个 ， 项 目j所 需 投 资 额 和 预 期 收 益 分 别 为 aj和 cj（ j 1,2,.,n） ， 此 外 由于 种 种 原 因 ， 有 三 个 附 加 条 件 ：n 若 选 择 项 目 1， 就 必 须 同 时 选 择 项 目 2。 反 之 不 一 定n 项 目 3和 4中 至 少 选 择 一 个 ；n 项 目 5,6,7中 恰 好 选 择 2个 。应 该 怎 样 选 择 投 资 项 目 ， 才 能 使 总 预 期 收 益 最 大 。 Page 161解 ： 对 每 个 投 资 项 目

64、都 有 被 选 择 和 不 被 选 择 两 种 可 能 ， 因 此分 别 用 0和 1表 示 ， 令 xj表 示 第 j个 项 目 的 决 策 选 择 ， 记 为 ：),.,2,1(01 njjjx j 不 投 资对 项 目 投 资对 项 目投 资 问 题 可 以 表 示 为 ： ）（或 者 nx xxx xx xx Bxats xczjnj jj nj jj ,2,1j10 21.max 765 43 121 1 Page 162例 4.3 指 派 问 题 或 分 配 问 题 。 人 事 部 门 欲 安 排 四 人 到 四 个 不同 岗 位 工 作 ， 每 个 岗 位 一 个 人 。 经 考

65、 核 四 人 在 不 同 岗 位 的 成绩 （ 百 分 制 ） 如 表 所 示 ， 如 何 安 排 他 们 的 工 作 使 总 成 绩 最 好 。 工 作人 员 A B C D甲 85 92 73 90乙 95 87 78 95 丙 82 83 79 90丁 86 90 80 88 Page 163设 工 作 时人 做不 分 配 第 工 作 时人 做分 配 第 ji jixij 01数 学 模 型 如 下 ： 44434241 343332312423 222114131211 88809086 907983829578 879590739285max xxxx xxxxxx xxxxxxZ

66、要 求 每 人 做 一 项 工 作 ， 约 束 条 件 为 ： 1111 44434241 34333231 24232221 14131211 xxxx xxxx xxxx xxxx Page 164每 项 工 作 只 能 安 排 一 人 ， 约 束 条 件 为 ： 1111 44342414 43332313 42322212 41312111 xxxx xxxx xxxx xxxx变 量 约 束 ： 4,3,2,110 jixij 、，或 Page 165 整 数 规 划 问 题 的 可 行 解 集 合 是 它 松 弛 问 题 可 行 解 集 合 的 一个 子 集 ， 任 意 两 个 可 行 解 的 凸 组 合 不 一 定 满 足 整 数 约 束 条 件 ，因 而 不 一 定 仍 为 可 行 解 。 整 数 规 划 问 题 的 可 行 解 一 定 是 它 的 松 弛 问 题 的 可 行 解 （ 反之 不 一 定 ） ， 但 其 最 优 解 的 目 标 函 数 值 不 会 优 于 后 者 最 优 解的 目 标 函 数 值 。 Page 166例 4.3 设 整 数 规 划 问 题