运筹学所有内容

《运筹学所有内容》由会员分享，可在线阅读，更多相关《运筹学所有内容（486页珍藏版）》请在装配图网上搜索。

1、 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7运 筹 学 （ Operations Research）系 统 工 程 的 最 重 要 的 理 论 基 础 之 一 ， 在 美 国 有 人 把 运 筹学 称 之 为 管 理 科 学 (Management Science)。 运 筹 学 所 研 究 的问 题 ， 可 简 单 地 归 结 为 一 句 话 ：“ 依 照 给 定 条 件 和 目 标 ， 从 众 多 方 案 中 选 择 最 佳 方 案 ”故 有 人 称 之 为 最 优 化 技 术 。 Page 8运 筹 学 的 历 史“ 运 作 研 究 (Operat

2、ional Research)小 组 ” :解 决 复杂 的 战 略 和 战 术 问 题 。 例 如 ：1. 如 何 合 理 运 用 雷 达 有 效 地 对 付 德 军 德 空 袭2. 对 商 船 如 何 进 行 编 队 护 航 ， 使 船 队 遭 受 德 国 潜艇 攻 击 时 损 失 最 少 ；3. 在 各 种 情 况 下 如 何 调 整 反 潜 深 水 炸 弹 的 爆 炸 深度 ， 才 能 增 加 对 德 国 潜 艇 的 杀 伤 力 等 。 Page 9 Page 10 Page 11数 学 规 划 （ 线 性 规 划 、 整 数 规 划 、 目 标 规 划 、 动 态规 划 等 ）图 论

3、存 储 论排 队 论对 策 论排 序 与 统 筹 方 法决 策 分 析 Page 12先 修 课 ： 高 等 数 学 ， 基 础 概 率 、 线 性 代 数特 点 ： 系 统 整 体 优 化 ； 多 学 科 的 配 合 ； 模 型 方 法 的 应 用运 筹 学 的 研 究 的 主 要 步 骤 ：真 实 系 统系 统 分 析问 题 描 述 模 型 建 立与 修 改 模 型 求 解与 检 验 结 果 分 析 与实 施数 据 准 备 Page 13 Page 14运 筹 学 在 工 商 管 理 中 的 应 用 涉 及 几 个 方 面 ：另 外 ， 还 应 用 于 设 备 维 修 、 更 新 和 可

4、靠 性 分 析 ， 项 目 的 选 择与 评 价 ， 工 程 优 化 设 计 等 。 Page 15Interface上 发 表 的 部 分 获 奖 项 目组 织 应 用 效 果联 合 航 空 公 司 在 满 足 乘 客 需 求 的 前 提 下 ， 以 最 低 成 本 进行 订 票 及 机 场 工 作 班 次 安 排 每 年 节 约 成 本 600万 美 元Citgo石 油 公 司 优 化 炼 油 程 序 及 产 品 供 应 、 配 送 和 营 销 每 年 节 约 成 本 7000万AT Page 31 0, 5 )(25 2 )( 7 )(5 00)(32max 543321 3321 53

5、321 43321 543321 xxxxxx xxxx xxxxx xxxxx xxxxxxZ标 准 形 式 如 下 ： Page 324. 线 性 规 划 问 题 的 解 )3(,2,1,0 )2(),2,1(. )1(max 1 1 njx mibxats xcZjnj ijij nj jj 线 性 规 划 问 题求 解 线 性 规 划 问 题 ， 就 是 从 满 足 约 束 条 件 (2)、 (3)的 方 程 组中 找 出 一 个 解 ， 使 目 标 函 数 (1)达 到 最 大 值 。 Page 33 可 行 解 ： 满 足 约 束 条 件 、 的 解 为 可 行 解 。 所 有 可

6、 行 解的 集 合 为 可 行 域 。 最 优 解 ： 使 目 标 函 数 达 到 最 大 值 的 可 行 解 。 基 ： 设 A为 约 束 条 件 的 m n阶 系 数 矩 阵 (m0 4010 换出行将 3化 为 1 5/3 1 1801/3 0 1/310 1 1/330 3005/3 0 4/3乘以1/3后得到 1 0 3/5 1/518 0 1 1/5 2/54 0 0 1 1 Page 53例 1.9 用 单 纯 形 法 求 解 0 20531 15232. 2max 321 321 321 321 xxx xxx xxxts xxxZ 、解 ： 将 数 学 模 型 化 为 标 准

7、 形 式 ： 5,2,1,0 20531 15232. 2max 5321 4321 321 jx xxxx xxxxts xxxZj不 难 看 出 x4、 x5可 作 为 初 始 基 变 量 ， 列 单 纯 形 表 计 算 。 Page 54cj 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 0 00 x 42 x2j 201/3 1 5 0 12075 3 0 17 1 31/3 0 9 0 2j 25601 1 0 17/3 1/3 125 0 1 28/9 -1/9 2/33

8、5/3 0 0 -98/9 -1/9 -7/3j Page 55学 习 要 点 ：1. 线 性 规 划 解 的 概 念 以 及 3个 基 本 定 理2. 熟 练 掌 握 单 纯 形 法 的 解 题 思 路 及 求 解 步 骤 Page 56人 工 变 量 法 ：前 面 讨 论 了 在 标 准 型 中 系 数 矩 阵 有 单 位 矩 阵 ， 很 容 易确 定 一 组 基 可 行 解 。 在 实 际 问 题 中 有 些 模 型 并 不 含 有 单 位矩 阵 ， 为 了 得 到 一 组 基 向 量 和 初 基 可 行 解 ， 在 约 束 条 件 的等 式 左 端 加 一 组 虚 拟 变 量 ， 得

9、到 一 组 基 变 量 。 这 种 人 为 加的 变 量 称 为 人 工 变 量 ， 构 成 的 可 行 基 称 为 人 工 基 ， 用 大 M法 或 两 阶 段 法 求 解 ， 这 种 用 人 工 变 量 作 桥 梁 的 求 解 方 法 称为 人 工 变 量 法 。 Page 57例 1.10 用 大 M法 解 下 列 线 性 规 划 0 122 102 434 23max 321 321 321 321 321xxx xxx xxx xxx xxxZ 、解 ： 首 先 将 数 学 模 型 化 为 标 准 形 式 5,2,1,0 122 102 434 23max 321 5321 4321

10、 321 jx xxx xxxx xxxx xxxZj 系 数 矩 阵 中 不 存 在单 位 矩 阵 ， 无 法 建立 初 始 单 纯 形 表 。 Page 58故 人 为 添 加 两 个 单 位 向 量 ， 得 到 人 工 变 量 单 纯 形 法 数 学 模 型 ： 7,2,1,0 122 102 434 23max 7321 5321 64321 76321 jx xxxx xxxx xxxxx MxMxxxxZj 其 中 ： M是 一 个 很 大 的 抽 象 的 数 ， 不 需 要 给 出 具 体 的 数 值 ，可 以 理 解 为 它 能 大 于 给 定 的 任 何 一 个 确 定 数

11、值 ； 再 用 前 面 介绍 的 单 纯 形 法 求 解 该 模 型 ， 计 算 结 果 见 下 表 。 Page 59cj 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 -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/5 6/5 1

12、0 1/5 0 -M x5 31/5 3/5 0 0 3/5 1 31/3-1 x3 11/5 2/5 0 1 2/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 60解 的 判 别 ：1） 唯 一 最 优 解 判 别 ： 最 优 表 中 所 有 非 基 变 量 的 检 验 数 非 零 ,则 线 规 划 具 有 唯 一 最 优 解 。2） 多 重 最 优 解 判 别 ： 最 优 表 中 存 在 非 基 变 量 的 检 验 数 为 零 ,则

13、线 则 性 规 划 具 有 多 重 最 优 解 （ 或 无 穷 多 最 优 解 ） 。3） 无 界 解 判 别 ： 某 个 k0且 aik （ i=1， 2,m） 则 线 性规 划 具 有 无 界 解 。4） 无 可 行 解 的 判 断 ： 当 用 大 M单 纯 形 法 计 算 得 到 最 优 解 并且 存 在 Ri0时 ， 则 表 明 原 线 性 规 划 无 可 行 解 。5） 退 化 解 的 判 别 ： 存 在 某 个 基 变 量 为 零 的 基 本 可 行 解 。 Page 61单 纯 性 法 小 结 :建立模型 个 数 取 值 右 端 项 等 式 或不 等 式 极 大 或 极 小 新

14、加 变 量系 数两个 三 个以 上 x j0 xj无约 束 xj 0 bi 0 bi mi 时 ， 企 业 愿 意购 进 这 种 资 源 ， 单 位 纯 利 为 yi* mi ， 则 有 利 可 图 ； 如 果 yi* mi 则 购 进 资 源 i， 可 获 单 位 纯 利 yi* mi 若 yi* mi则 转 让 资 源 i ， 可 获 单 位 纯 利 mi yi Page 1043） 影 子 价 格 在 资 源 利 用 中 的 应 用根 据 对 偶 理 论 的 互 补 松 弛 性 定 理 :Y*Xs=0 , YsX*=0表 明 生 产 过 程 中 如 果 某 种 资 源 bi未 得 到 充

15、 分 利 用 时 ， 该 种 资源 的 影 子 价 格 为 0； 若 当 资 源 资 源 的 影 子 价 格 不 为 0时 ， 表 明该 种 资 源 在 生 产 中 已 耗 费 完 。 Page 1054） 影 子 价 格 对 单 纯 形 表 计 算 的 解 释单 纯 形 表 中 的 检 验 数 mi iijjjBjj yacPBCc 11其 中 cj表 示 第 j种 产 品 的 价 格 ; 表 示 生 产 该 种 产 品 所消 耗 的 各 项 资 源 的 影 子 价 格 的 总 和 ,即 产 品 的 隐 含 成 本 。mi iijya1当 产 值 大 于 隐 含 成 本 时 ， 即 ， 表

16、明 生 产 该 项 产 品 有利 ， 可 在 计 划 中 安 排 ； 否 则 ， 用 这 些 资 源 生 产 别 的产 品 更 有 利 ， 不 在 生 产 中 安 排 该 产 品 。0j 0j Page 106 对 偶 单 纯 形 法 是 求 解 线 性 规 划 的 另 一 个 基 本 方 法 。 它是 根 据 对 偶 原 理 和 单 纯 形 法 原 理 而 设 计 出 来 的 ， 因 此 称 为对 偶 单 纯 形 法 。 不 要 简 单 理 解 为 是 求 解 对 偶 问 题 的 单 纯 形法 。 找 出 一 个 对 偶 问 题 的 可 行 基 ， 保 持 对 偶 问 题 为 可 行 解 的

17、条 件 下 ， 判 断 X B是 否 可 行 （ XB为 非 负 ） ， 若 否 ， 通 过 变 换 基解 ， 直 到 找 到 原 问 题 基 可 行 解 （ 即 XB为 非 负 ） ， 这 时 原 问 题与 对 偶 问 题 同 时 达 到 可 行 解 ， 由 定 理 4可 得 最 优 解 。 Page 107找 出 一 个 DP的 可 行 基LP是 否 可 行（ XB 0）保 持 DP为 可 行 解 情 况 下 转 移 到 LP的 另 一 个 基 本 解 最 优 解是否循环 结 束 Page 108例 2.9 用 对 偶 单 纯 形 法 求 解 ： )3.2.1(0 145 1232 102

18、2 15129min 321 321 321 321jx xxx xxx xxx xxxZj解 :（ 1） 将 模 型 转 化 为 求 最 大 化 问 题 ， 约 束 方 程 化 为 等 式 求出 一 组 基 本 解 ， 因 为 对 偶 问 题 可 行 ， 即 全 部 检 验 数 0（ 求max问 题 ） 。 Page 109 0 14 5 12 32 10 22 15129max61 6321 5321 4321 321x 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 -1

19、00 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 110cj -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 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

20、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 111cj -9 -12 -15 0 0 0cB xB x1 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

21、 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 112 对 偶 单 纯 形 法 应 注 意 的 问 题 ： 用 对 偶 单 纯 形 法 求 解 线 性 规 划 是 一 种 求 解 方 法 ， 而 不 是 去 求 对偶 问 题 的 最 优 解 初 始 表 中 一 定 要 满 足 对 偶 问 题 可 行 ， 也 就 是 说 检 验 数 满 足 最 优判 别 准 则 最 小 比 值 中

22、 的 绝 对 值 是 使 得 比 值 非 负 ， 在 极 小 化 问 题 j 0，分 母 a ij0 这 时 必 须 取 绝 对 值 。 在 极 大 化 问 题 中 ， j 0， 分 母aij0， 总 满 足 非 负 ， 这 时 绝 对 值 符 号 不 起 作 用 ， 可 以 去 掉 。 如在 本 例 中 将 目 标 函 数 写 成ijja这 里 j 0在 求 k时 就 可 以 不 带 绝 对 值 符 号 。 321 34max xxxz ijja Page 113 对 偶 单 纯 形 法 与 普 通 单 纯 形 法 的 换 基 顺 序 不 一 样 ， 普 通 单 纯 形 法是 先 确 定 进

23、 基 变 量 后 确 定 出 基 变 量 ， 对 偶 单 纯 形 法 是 先 确 定 出 基 变量 后 确 定 进 基 变 量 ； 普 通 单 纯 形 法 的 最 小 比 值 是 其 目 的 是 保 证 下 一个 原 问 题 的 基 本 解 可 行 ， 对 偶 单 纯 形 法 的 最 小 比 值 是 0min ikikii aab其 目 的 是 保 证 下 一 个 对 偶 问 题 的 基 本 解 可 行 0|min ljljjj aa 对 偶 单 纯 形 法 在 确 定 出 基 变 量 时 ， 若 不 遵 循 规 则 ， 任 选 一 个 小 于 零 的 bi对 应 的 基 变 量 出 基 ，

24、不 影 响 计 算 结 果 ，只 是 迭 代 次 数 可 能 不 一 样 。 0|min iil bbb Page 114学 习 要 点 ：1. 线 性 规 划 解 的 概 念 以 及 3个 基 本 定 理2. 熟 练 掌 握 单 纯 形 法 的 解 题 思 路 及 求 解 步 骤 运 输 规 划 问 题 的 数 学 模 型表 上 作 业 法运 输 问 题 的 应 用 Page 116例 3.1 某 公 司 从 两 个 产 地 A1、 A2将 物 品 运 往 三 个 销 地 B1, B2, B3， 各 产 地 的 产 量 、 各 销 地 的 销 量 和 各 产 地 运 往 各 销 地 每 件物

25、 品 的 运 费 如 下 表 所 示 ， 问 ： 应 如 何 调 运 可 使 总 运 输 费 用 最小 ？ B1 B2 B3 产 量A1 6 4 6 200A2 6 5 5 300销 量 150 150 200 Page 117解 ： 产 销 平 衡 问 题 ： 总 产 量 = 总 销 量 500 设 xij 为 从 产 地 Ai运 往 销 地 Bj的 运 输 量 ， 得 到 下 列 运 输 量表 ： B1 B2 B3 产 量A1 x11 x12 x13 200A2 x 21 x22 x23 300销 量 150 150 200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5

26、x22+ 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 118运 输 问 题 的 一 般 形 式 ： 产 销 平 衡A1、 A2、 、 Am 表 示 某 物 资 的 m个 产 地 ； B1、 B2、 、 Bn 表 示某 物 质 的 n个 销 地 ； ai 表 示 产 地 Ai的 产 量 ； bj 表 示 销 地 Bj 的 销 量 ； cij 表 示 把 物 资 从 产 地

27、 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 119变 化 ： 1） 有 时 目 标 函 数 求 最 大 。 如 求 利 润 最 大 或 营 业 额 最 大 等 ； 2） 当 某 些 运 输 线 路 上 的 能 力 有 限 制 时 ， 在 模 型 中 直 接 加 入约 束 条 件 （ 等 式 或 不 等

28、式 约 束 )； 3） 产 销 不 平 衡 时 ， 可 加 入 假 想 的 产 地 （ 销 大 于 产 时 ） 或 销地 （ 产 大 于 销 时 ） 。定 理 : 设 有 m个 产 地 n个 销 地 且 产 销 平 衡 的 运 输 问 题 ， 则 基 变量 数 为 m+n-1。 Page 120表 上 作 业 法 是 一 种 求 解 运 输 问 题 的 特 殊 方 法 ， 其 实 质 是 单 纯形 法 。步 骤 描 述 方 法第 一 步 求 初 始 基 行 可 行 解 （ 初 始 调 运 方 案 ） 最 小 元 素 法 、元 素 差 额 法 、第 二 步 求 检 验 数 并 判 断 是 否 得

29、 到 最 优 解 当 非 基 变 量 的检 验 数 ij全 都 非 负 时 得 到 最 优 解 ， 若 存 在 检 验数 ij 0， 说 明 还 没 有 达 到 最 优 ， 转 第 三 步 。 闭 回 路 法 和 位势 法第 三 步 调 整 运 量 ， 即 换 基 ， 选 一 个 变 量 出 基 ， 对 原 运量 进 行 调 整 得 到 新 的 基 可 行 解 ， 转 入 第 二 步 Page 121例 3.2 某 运 输 资 料 如 下 表 所 示 ：单 位 销 地 运 价 产 地 产 量3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 64321 BBBB 3

30、21AAA问 ： 应 如 何 调 运 可 使 总 运 输 费 用 最 小 ？ Page 122解 ： 第 1步 求 初 始 方 案方 法 1： 最 小 元 素 法 基 本 思 想 是 就 近 供 应 ， 即 从 运 价 最 小 的 地 方 开 始 供 应 （ 调运 ） ， 然 后 次 小 ， 直 到 最 后 供 完 为 止 。B1 B2 B3 B4 产 量A 1 7A2 4A3 9销 量 3 6 5 63 11 3 101 9 27 4 10 583 416 33 Page 123总 的 运 输 费 (3 1)+(6 4) +(4 3) +(1 2)+(3 10)+(3 5)=86元元 素 差

31、 额 法 对 最 小 元 素 法 进 行 了 改 进 ， 考 虑 到 产 地 到 销地 的 最 小 运 价 和 次 小 运 价 之 间 的 差 额 ， 如 果 差 额 很 大 ， 就 选最 小 运 价 先 调 运 ， 否 则 会 增 加 总 运 费 。 例 如 下 面 两 种 运 输 方案 。 8 5 102 1 2015 1515510总 运 费 是 z=10 8+5 2+15 1=105最 小 元 素 法 ： Page 1248 5 102 1 2015 15515 10总 运 费 z=10 5+15 2+5 1=85后 一 种 方 案 考 虑 到 C11与 C21之 间的 差 额 是 8

32、 2=6， 如 果 不 先 调 运x21， 到 后 来 就 有 可 能 x110， 这样 会 使 总 运 费 增 加 较 大 ， 从 而 先调 运 x21， 再 是 x22， 其 次 是 x12用 元 素 差 额 法 求 得 的 基 本 可 行 解 更 接 近 最 优 解 ， 所以 也 称 为 近 似 方 案 。 Page 125方 法 2： Vogel法1） 从 运 价 表 中 分 别 计 算 出 各 行 和 各 列 的 最 小 运 费 和 次 最 小 运费 的 差 额 ， 并 填 入 该 表 的 最 右 列 和 最 下 行 。B1 B2 B3 B4 产 量A1 7A 2 4A3 9销 量

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

34、 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6 列 差 额 4321 BBBB321AAA 711 352 15 Page 128单 位 销 地 运 价 产 地 产 量 行 差 额3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6列 差 额 4321 BBBB 321AAA 71352 75 3 Page 129单 位 销 地 运 价 产 地 产 量 行 差 额3 11 3 10 71 9 2 8 47 4 10 5 9销 量 3 6 5 6列 差 额 4321 BBBB 321AAA 1135 15 3 6 31 2该 方 案 的

35、总 运 费 :(1 3) (4 6) (3 5) (2 10) (1 8) (3 5) 85元 Page 130求 出 一 组 基 可 行 解 后 ， 判 断 是 否 为 最 优 解 ， 仍 然 是 用 检验 数 来 判 断 ， 记 xij的 检 验 数 为 ij由 第 一 章 知 ， 求 最 小 值 的 运输 问 题 的 最 优 判 别 准 则 是 ：所 有 非 基 变 量 的 检 验 数 都 非 负 ， 则 运 输 方 案 最 优求 检 验 数 的 方 法 有 两 种 ： 闭 回 路 法 位 势 法 （ ） Page 131闭 回 路 的 概 念 , 132222111 jsisjsiji

36、jijiji xxxxxx 称 集 合 ),( 2121 互 不 相 同；其 中 ss jjjiii 为 一 个 闭 回 路 ， 集 合 中 的 变 量 称 为 回 路 的 顶 点 ， 相 邻 两 个 变量 的 连 线 为 闭 回 路 的 边 。 如 下 表 Page 132例 下 表 中 闭 回 路 的 变 量 集 合 是 x11,x12,x42,x43,x23,x25,x35, x31共有 8个 顶 点 ， 这 8个 顶 点 间 用 水 平 或 垂 直 线 段 连 接 起 来 ， 组 成一 条 封 闭 的 回 路 。 B1 B2 B3 B4 B5A 1 X11 X12A2 X23 X25A

37、3 X31 X35A4 X42 X43 一 条 回 路 中 的 顶 点 数 一 定 是 偶 数 ， 回 路 遇 到 顶 点 必 须 转 90度 与 另 一 顶 点 连 接 ， 表 3 3中 的 变 量 x 32及 x33不 是 闭 回 路 的 顶点 ， 只 是 连 线 的 交 点 。 Page 133闭 回 路 , 123233434111 xxxxxx B1 B2 B3A1 X11 X12A2A 3 X32 X33A4 X41 X43例 如 变 量 组 不 能 构 成 一 条 闭 回 路 ，但 A中 包 含 有 闭 回 路 , 121131352521 xxxxxxA , 31352521

38、xxxx变 量 组 变 量 数 是 奇 数 ， 显 然 不 是闭 回 路 ， 也 不 含 有 闭 回 路 ； , 2111123233 xxxxxB Page 134用 位 势 法 对 初 始 方 案 进 行 最 优 性 检 验 ：1） 由 ij=Cij-（ Ui+Vj） 计 算 位 势 Ui ， Vj ， 因 对 基 变 量 而 言 有 ij=0， 即Cij-（ Ui+Vj） = 0， 令 U1=02） 再 由 ij=Cij-（ Ui+Vj） 计 算 非 基 变 量 的 检 验 数 ijB1 B2 B3 B4 UiA 1A2A3Vj 3 11 3 101 9 27 4 10 5843 6 3

39、1 3 当 存 在 非 基变 量 的 检 验数 kl 0， 说明 现 行 方 案为 最 优 方 案 ，否 则 目 标 成本 还 可 以 进一 步 减 小 。 Page 135当 存 在 非 基 变 量 的 检 验 数 kl 0 且 kl =minij时 ， 令 Xkl 进基 。 从 表 中 知 可 选 X24进 基 。第 3步 确 定 换 入 基 的 变 量第 4步 确 定 换 出 基 的 变 量以 进 基 变 量 xik为 起 点 的 闭 回 路 中 ， 标 有 负 号 的 最 小 运 量 作 为调 整 量 ， 对 应 的 基 变 量 为 出 基 变 量 ， 并 打 上 “ ”以 示 换出

40、作 为 非 基 变 量 。 Page 136B1 B2 B3 B4 UiA1A2A 3Vj 3 111 97 43 6 13,1minmin 14,23 xx调 整 步 骤 为 ： 在 进 基 变 量 的 闭 回 路 中 标 有 正 号 的 变 量 加 上 调 整 量， 标 有 负 号 的 变 量 减 去 调 整 量 ， 其 余 变 量 不 变 ， 得 到 一 组 新 的基 可 行 解 。 然 后 求 所 有 非 基 变 量 的 检 验 数 重 新 检 验 。 Page 137当 所 有 非 基 变 量 的 检 验 数 均 非 负 时 ， 则 当 前 调 运 方 案 即 为 最优 方 案 ，

41、如 表 此 时 最 小 总 运 费 ：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 138表 上 作 业 法 的 计 算 步 骤 ：分 析 实 际 问 题 列 出 产 销 平衡 表 及 单 位 运 价 表确 定 初 始 调 运 方 案 （ 最 小元 素 法 或 Vogel法 ）求 检 验 数 （ 位 势 法 ） 所 有 检 验 数 0找 出 绝 对 值 最 大 的 负 检 验 数 ， 用 闭 合回 路 调 整 ， 得 到 新 的 调

42、运 方 案 得 到 最 优 方 案 ，算 出 总 运 价 Page 139（ 1） 若 运 输 问 题 的 某 一 基 可 行 解 有 多 个 非 基 变 量 的 检 验 数为 负 ， 在 继 续 迭 代 时 ， 取 它 们 中 任 一 变 量 为 换 入 变 量 均 可 使目 标 函 数 值 得 到 改 善 ， 但 通 常 取 ij0中 最 小 者 对 应 的 变 量 为换 入 变 量 。（ 2） 无 穷 多 最 优 解产 销 平 衡 的 运 输 问 题 必 定 存 最 优 解 。 如 果 非 基 变 量 的 ij0， 则 该 问 题 有 无 穷 多 最 优 解 。 Page 140 退 化

43、 解 ： 表 格 中 一 般 要 有 (m+n-1)个 数 字 格 。 但 有 时 在 分 配 运 量时 则 需 要 同 时 划 去 一 行 和 一 列 ， 这 时 需 要 补 一 个 0， 以 保 证有 (m+n-1)个 数 字 格 作 为 基 变 量 。 一 般 可 在 划 去 的 行 和 列 的任 意 空 格 处 加 一 个 0即 可 。 利 用 进 基 变 量 的 闭 回 路 对 解 进 行 调 整 时 ， 标 有 负 号 的最 小 运 量 （ 超 过 2个 最 小 值 ） 作 为 调 整 量 ， 选 择 任 意 一 个 最小 运 量 对 应 的 基 变 量 作 为 出 基 变 量 ，

44、 并 打 上 “ ” 以 示 作 为非 基 变 量 。 Page 141 销 地产 地 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 142 销 地产 地 B1 B2 B3 B4 产 量A1 7A 2 4A3 9销 量 3 6 5 6 2011 4 431 377 82 10 6 0 在 x12、 x22、 x33、 x34中 任 选 一 个 变 量 作

45、 为 基 变 量 ， 例 如 选 x34例 ： 用 最 小 元 素 法 求 初 始 可 行 解 Page 143目 标 函 数 求 利 润 最 大 或 营 业 额 最 大 等 问 题 。 mi nj ijijxCZ 1 1max njmix njbx miax ijmi jijnj iij ,2,1;,2,10 ,2,1 ,2,111 ， Page 144求 解 方 法 ：将 极 大 化 问 题 转 化 为 极 小 化 问 题 。 设 极 大 化 问 题 的 运 价表 为 C ， 用 一 个 较 大 的 数 M（ Mmaxcij） 去 减 每 一 个 cij得到 矩 阵 C， 其 中 C=（

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

47、47当 总 产 量 与 总 销 量 不 相 等 时 ,称 为 不 平 衡 运 输 问 题 .这 类运 输 问 题 在 实 际 中 常 常 碰 到 ,它 的 求 解 方 法 是 将 不 平 衡 问 题化 为 平 衡 问 题 再 按 平 衡 问 题 求 解 。 当 产 大 于 销 时 ， 即 ： mi nj ji ba1 1数 学 模 型 为 ： mi nj ijijxcZ 1 1min njmix njbx miaxijmi jijnj iij ,2,1;,2,10 ,2,1 ,2,111 ， Page 148由 于 总 产 量 大 于 总 销 量 ， 必 有 部 分 产 地 的 产 量 不 能

48、 全 部 运 送 完 ，必 须 就 地 库 存 ， 即 每 个 产 地 设 一 个 仓 库 ， 假 设 该 仓 库 为 一 个 虚 拟销 地 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 jmix njbx miax ijmi jijnj iij ； 具 体 求 解 时 ,只 在运 价 表 右 端 增 加一

49、列 Bn+1， 运 价为 零 ,销 量 为 bn+1即 可 Page 149 当 销 大 于 产 时 ， 即 ： 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 j ab 11 Page 150销 大 于 产 化 为 平 衡 问 题 的 数 学 模 型 为 ： mi nj ijij

50、 xcZ 1 1min njmix njbx miaxijmi jijnj iji ,2,11,2,1,0 ,2,1 1,2,1111 ；具 体 计 算 时 ， 在 运 价 表 的 下 方 增 加 一 行 Am+1， 运 价 为 零 。 产量 为 am+1即 可 。 Page 151例 3.4 求 下 列 表 中 极 小 化 运 输 问 题 的 最 优 解 。 B1 B2 B3 B4 aiA1 5 9 2 3 60A2 - 4 7 8 40A3 3 6 4 2 30A4 4 8 10 11 50b j 20 60 35 45 180160 41 41 160180i j ji ba因 为 有

51、： Page 152所 以 是 一 个 产 大 于 销 的 运 输 问 题 。 表 中 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 50 bj 20 60 35 45 20 180 Page 153下 表 为 计 算 结 果 。 可 看 出 ： 产

52、地 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 1543. 生 产 与 储 存 问 题例 3.5 某 厂 按 合 同 规 定 须 于 当 年 每 个 季 度 末 分 别 提 供 10、 15、 25、20台 同 一 规 格 的 柴 油 机 。 已 知 该 厂 各 季 度 的 生 产 能 力 及 生 产 每 台柴 油 机 的 成 本 如 右 表 。 如 果 生 产 出 来 的 柴 油 机 当 季 不 交 货 ， 每 台每

53、 积 压 一 个 季 度 需 储 存 、 维 护 等 费 用 0.15万 元 。 试 求 在 完 成 合 同的 情 况 下 ， 使 该 厂 全 年 生 产 总 费 用 为 最 小 的 决 策 方 案 。季 度 生 产 能 力 /台 单 位 成 本 /万 元 25 10.8 35 11.1 30 11 10 11.3 Page 155解 ： 设 xij为 第 i 季 度 生 产 的 第 j 季 度 交 货 的 柴 油 机 数 目 ， 那么 应 满 足 ：交 货 ： x11 = 10 生 产 ： x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 +

54、 x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10把 第 i 季 度 生 产 的 柴 油 机 数 目 看 作 第 i 个 生 产 厂 的 产 量 ； 把 第 j 季度 交 货 的 柴 油 机 数 目 看 作 第 j 个 销 售 点 的 销 量 ； 设 cij是 第 i季 度 生产 的 第 j季 度 交 货 的 每 台 柴 油 机 的 实 际 成 本 ， 应 该 等 于 该 季 度 单 位成 本 加 上 储 存 、 维 护 等 费 用 。 可 构 造 下 列 产 销 平 衡 问 题 ： Page

55、156 ji 产 量 10.8 10.95 11.1 11.25 25 M 11.10 11.25 11.40 35 M M 11.00 11.15 30 M M M 11.30 10销 量 10 15 25 20 10070由 于 产 大 于 销 ， 加 上 一 个 虚 拟 的 销 地 D， 化 为 平 衡 问 题 ，即 可 应 用 表 上 作 业 法 求 解 。 Page 157该 问 题 的 数 学 模 型 ：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33

56、+11.15 x34 +11.3 x44 ji D 产 量 10.8 10.95 11.1 11.25 0 25 M 11.10 11.25 11.40 0 35 M M 11.00 11.15 0 30 M M M 11.30 0 10销 量 10 15 25 20 30 100100 Page 158 ji D 产 量 10 15 0 25 0 5 30 35 25 5 30 10 10 销 量 10 15 25 20 30 100100最 优 生 产 决 策 如 下 表 ， 最 小 费 用 z 773万 元 。 整 数 规 划 的 特 点 及 应 用分 支 定 界 法分 配 问 题 与

57、匈 牙 利 法 Page 160要 求 一 部 分 或 全 部 决 策 变 量 取 整 数 值 的 规 划 问 题 称 为 整数 规 划 。 不 考 虑 整 数 条 件 ， 由 余 下 的 目 标 函 数 和 约 束 条 件 构成 的 规 划 问 题 称 为 该 整 数 规 划 问 题 的 松 弛 问 题 。 若 该 松 弛 问题 是 一 个 线 性 规 划 ， 则 称 该 整 数 规 划 为 整 数 线 性 规 划 。整 数 线 性 规 划 数 学 模 型 的 一 般 形 式 ： 且 部 分 或 全 部 为 整 数或 n)1.2(j 0 )2.1( )min(max1 1 jnj ijij

58、nj jjx mibxa xcZZ Page 161 纯 整 数 线 性 规 划 ： 指 全 部 决 策 变 量 都 必 须 取 整 数 值 的 整 数线 性 规 划 。 混 合 整 数 线 性 规 划 ： 决 策 变 量 中 有 一 部 分 必 须 取 整 数 值 ，另 一 部 分 可 以 不 取 整 数 值 的 整 数 线 性 规 划 。 0-1型 整 数 线 性 规 划 ： 决 策 变 量 只 能 取 值 0或 1的 整 数 线 性规 划 。 Page 162例 4.1 工 厂 A1和 A2生 产 某 种 物 资 。 由 于 该 种 物 资 供 不 应 求 ， 故 需 要再 建 一 家

59、工 厂 。 相 应 的 建 厂 方 案 有 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开 工 后 ， 每 年 的 生 产 费 用 估 计 分 别 为 1200万 或 1500万元 。 现

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

61、 可 以 表 示 为 ： Page 164 )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 165例 4.2 现 有 资 金 总 额 为 B。 可 供 选 择 的 投 资 项 目

62、有 n个 ， 项 目j所 需 投 资 额 和 预 期 收 益 分 别 为 aj和 cj（ j 1,2,.,n） ， 此 外 由于 种 种 原 因 ， 有 三 个 附 加 条 件 ：应 该 怎 样 选 择 投 资 项 目 ， 才 能 使 总 预 期 收 益 最 大 。 Page 166解 ： 对 每 个 投 资 项 目 都 有 被 选 择 和 不 被 选 择 两 种 可 能 ， 因 此分 别 用 0和 1表 示 ， 令 xj表 示 第 j个 项 目 的 决 策 选 择 ， 记 为 ：),.,2,1(01 njjjx j 不 投 资对 项 目 投 资对 项 目投 资 问 题 可 以 表 示 为 ：

63、 ）（或 者 nx xxx xx xx Bxats xczjnj jj nj jj ,2,1j10 21.max 765 43 121 1 Page 167例 4.3 指 派 问 题 或 分 配 问 题 。 人 事 部 门 欲 安 排 四 人 到 四 个 不同 岗 位 工 作 ， 每 个 岗 位 一 个 人 。 经 考 核 四 人 在 不 同 岗 位 的 成绩 （ 百 分 制 ） 如 表 所 示 ， 如 何 安 排 他 们 的 工 作 使 总 成 绩 最 好 。 工 作人 员 A B C D甲 85 92 73 90乙 95 87 78 95 丙 82 83 79 90丁 86 90 80 8

64、8 Page 168设 工 作 时人 做不 分 配 第 工 作 时人 做分 配 第 ji jixij 01数 学 模 型 如 下 ： 44434241 343332312423 222114131211 88809086 907983829578 879590739285max xxxx xxxxxx xxxxxxZ 要 求 每 人 做 一 项 工 作 ， 约 束 条 件 为 ： 1111 44434241 34333231 24232221 14131211 xxxx xxxx xxxx xxxx Page 169每 项 工 作 只 能 安 排 一 人 ， 约 束 条 件 为 ： 1111

65、44342414 43332313 42322212 41312111 xxxx xxxx xxxx xxxx变 量 约 束 ： 4,3,2,110 jixij 、，或 Page 170 整 数 规 划 问 题 的 可 行 解 集 合 是 它 松 弛 问 题 可 行 解 集 合 的 一个 子 集 ， 任 意 两 个 可 行 解 的 凸 组 合 不 一 定 满 足 整 数 约 束 条 件 ，因 而 不 一 定 仍 为 可 行 解 。 整 数 规 划 问 题 的 可 行 解 一 定 是 它 的 松 弛 问 题 的 可 行 解 （ 反之 不 一 定 ） ， 但 其 最 优 解 的 目 标 函 数 值

66、 不 会 优 于 后 者 最 优 解的 目 标 函 数 值 。 Page 171例 4.3 设 整 数 规 划 问 题 如 下 且 为 整 数0, 136 51914max 21 21 21 21xx xx xx xxZ首 先 不 考 虑 整 数 约 束 ， 得 到 线 性 规 划 问 题 （ 一 般 称 为 松 弛 问题 ） 。 0, 136 51914max 21 21 21 21xx xx xx xxZ Page 172用 图 解 法 求 出 最 优 解 为 ： x1 3/2, x2 = 10/3， 且 有 Z = 29/6现 求 整 数 解 (最 优 解 ):如 用 舍入 取 整 法 可 得 到 4个 点 即 (1，3),(2， 3),(1， 4),(2， 4)。 显 然 ，它 们 都 不 可 能 是 整 数 规 划 的 最 优解 。 x 1x2 3 3(3/2,10/3)按 整 数 规 划 约 束 条 件 ， 其 可 行解 肯 定 在 线 性 规 划 问 题 的 可 行 域内 且 为 整 数 点 。 故 整 数 规 划 问 题的 可 行 解 集 是 一 个 有 限 集 ， 如