《MBA运筹学》PPT课件

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

1、http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 1运 筹 学北 京 理 工 大 学管 理 与 经 济 学 院吴 祈 宗 教 授 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 2 1、 绪 论 2、 线 性 规 划 3、 运 输 问 题 4、 动 态 规 划 5、 图 与 网 络 分 析 6、 排 队 论 7、 教 学 日 历运 筹 学 目 录说 明 本 教 学 课 件 是 与 教 材 紧 密 配 合使 用 的 ， 教 材 为 ： 运 筹 学 杨 民 助 编 著西 安 交 通 大 学 出 版 社 ， 2000年 6月参 考 书 ： 运 筹 学 清 华 大

2、 学 出 版 社或 其 他 的 运 筹 学 方 面 本 科 教 材的 相 关 内 容下 面 所 标 注 的 页 号 ， 均 为 本课 程 教 材 的 页 号 。 例 如 ：p123 表 示 第 123页p31-34 表 示 从 第 31页 到 第 34页 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 3 绪 论 运 筹 学 （ Operational Research) 直 译 为 “ 运 作 研 究 ” 运 筹 学 是 运 用 科 学 的 方 法 （ 如 分 析 、 试 验 、量 化 等 ） 来 决 定 如 何 最 佳 地 运 营 和 设 计 各 种 系统 的 一 门

3、学 科 。 运 筹 学 对 经 济 管 理 系 统 中 的 人力 、 物 力 、 财 力 等 资 源 进 行 统 筹 安 排 ， 为 决 策者 提 供 有 依 据 的 最 优 方 案 ， 以 实 现 最 有 效 的 管理 。 运 筹 学 有 广 泛 应 用 （ 可 以 自 己 找 一 些 参 考 书 看 ） 运 筹 学 的 产 生 和 发 展 （ 可 以 自 己 找 一 些 参 考 书 看 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 4 运 筹 学 解 决 问 题 的 过 程1） 提 出 问 题 ： 认 清 问 题2） 寻 求 可 行 方 案 ： 建 模 、 求 解

4、3） 确 定 评 估 目 标 及 方 案 的 标 准 或 方 法 、 途 径4） 评 估 各 个 方 案 ： 解 的 检 验 、 灵 敏 性 分 析 等5） 选 择 最 优 方 案 ： 决 策6） 方 案 实 施 ： 回 到 实 践 中7） 后 评 估 ： 考 察 问 题 是 否 得 到 完 满 解 决1） 2） 3） ： 形 成 问 题 ； 4） 5） 分 析 问 题 ： 定 性 分析 与 定 量 分 析 。 构 成 决 策 。 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 5 运 筹 学 的 分 支 线 性 规 划 非 线 性 规 划 整 数 规 划 动 态 规 划

5、多 目 标 规 划 随 机 规 划 模 糊 规 划 等 图 与 网 络 理 论 存 储 论 排 队 论 决 策 论 对 策 论 排 序 与 统 筹 方 法 可 靠 性 理 论 等 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 6 运 筹 学 在 工 商 管 理 中 的 应 用 生 产 计 划 ： 生 产 作 业 的 计 划 、 日 程 表 的 编 排 、 合 理 下 料 、 配 料 问 题 、 物 料 管 理 等 库 存 管 理 ： 多 种 物 资 库 存 量 的 管 理 ， 库 存 方 式 、 库 存 量 等 运 输 问 题 ： 确 定 最 小 成 本 的 运 输 线

6、路 、 物 资 的 调 拨 、 运 输 工 具 的 调 度 以 及 建 厂 地 址 的 选 择 等 人 事 管 理 ： 对 人 员 的 需 求 和 使 用 的 预 测 ， 确 定 人 员 编 制 、 人 员 合 理 分 配 ， 建 立 人 才 评 价 体 系 等 市 场 营 销 ： 广 告 预 算 、 媒 介 选 择 、 定 价 、 产 品 开 发 与 销 售 计 划 制 定 等 财 务 和 会 计 ： 预 测 、 贷 款 、 成 本 分 析 、 定 价 、 证 券 管 理 、 现 金 管 理 等 * 设 备 维 修 、 更 新 ， 项 目 选 择 、 评 价 ， 工 程 优 化 设 计 与

7、管 理 等 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 7 运 筹 学 方 法 使 用 情 况 (美 1983)（ %） 0 10 20 30 40 50 60 70 统计 计算 机模 拟 网络 计划 线性 规划 排队论 非线 性规 划 动态 规划 对策论 从 不 使 用 有 时 使 用 经 常 使 用 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 801020304050 60 70 80 90 统计 计算 机模 拟 网络 计划 线性 规划 排队论 非线 性规 划 动态 规划 对策论 从 不 使 用 有 时 使 用 经 常 使 用 运 筹 学 方

8、 法 在 中 国 使 用 情 况 (随 机 抽 样 )（ %） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 9 运 筹 学 的 推 广 应 用 前 景 据 美 劳 工 局 1992年 统 计 预 测 : 运 筹 学 应 用 分 析 人 员 需 求 从 1990年 到 2005年 的 增 长 百 分 比 预 测 为 73%,增 长 速 度 排 到 各 项职 业 的 前 三 位 .结 论 : 运 筹 学 在 国 内 或 国 外 的 推 广 前 景 是 非 常 广 阔 的 工 商 企 业 对 运 筹 学 应 用 和 需 求 是 很 大 的 在 工 商 企 业 推 广 运 筹

9、学 方 面 有 大 量 的 工 作 要 做 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 10 学 习 运 筹 学 要 把 重 点 放 在 分 析 、 理 解 有 关 的 概 念 、 思 路 上 。 在 自 学 过 程中 ， 应 该 多 向 自 己 提 问 ， 如 一 个 方 法 的 实 质 是 什 么 ， 为 什 么 这 样 做 ， 怎么 做 等 。 自 学 时 要 掌 握 三 个 重 要 环 节 ： 1、 认 真 阅 读 教 材 和 参 考 资 料 ， 以 指 定 教 材 为 主 ， 同 时 参 考 其 他 有 关 书 籍 。 一 般 每 一 本 运筹 学 教 材 都

10、 有 自 己 的 特 点 ， 但 是 基 本 原 理 、 概 念 都 是 一 致 的 。 注 意 主 从 ， 参 考 资 料 会 帮 助你 开 阔 思 路 ， 使 学 习 深 入 。 但 是 ， 把 时 间 过 多 放 在 参 考 资 料 上 ， 会 导 致 思 路 分 散 ， 不 利 于学 好 。 2、 要 在 理 解 了 基 本 概 念 和 理 论 的 基 础 上 研 究 例 题 ， 注 意 例 题 是 为 了 帮 助 你 理 解 概 念 、 理 论的 。 作 业 练 习 的 主 要 作 用 也 是 这 样 ， 它 同 时 还 有 让 你 自 己 检 查 自 己 学 习 的 作 用 。 因

11、 此 ， 做题 要 有 信 心 ， 要 独 立 完 成 ， 不 要 怕 出 错 。 因 为 ， 整 个 课 程 是 一 个 整 体 ， 各 节 内 容 有 内 在 联系 ， 只 要 学 到 一 定 程 度 ， 知 识 融 会 贯 通 起 来 ， 你 做 题 的 正 确 性 自 己 就 有 判 断 。 3、 要 学 会 做 学 习 小 结 。 每 一 节 或 一 章 学 完 后 ， 必 须 学 会 用 精 炼 的 语 言 来 该 书 所 学 内 容 。 这样 ， 你 才 能 够 从 较 高 的 角 度 来 看 问 题 ， 更 深 刻 的 理 解 有 关 知 识 和 内 容 。 这 就 称 作 “

12、 把 书 读 薄 ” ， 若 能 够 结 合 自 己 参 考 大 量 文 献 后 的 深 入 理 解 ， 把 相 关 知 识 从 更 深 入 、 广 泛 的 角 度 进行 论 述 ， 则 称 之 为 “ 把 书 读 厚 ” 在 建 数 学 模 型 时 要 结 合 实 际 应 用 ， 要 学 会 用 计 算 机 软 件 解 决 问 题 。 如 何 学 习 运 筹 学 课 程 返 回 目 录 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 11各 章 节 的 重 点 、 难 点及 注 意 事 项 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 12 1、 线

13、 性 规 划线 性 规 划 模 型 ： 目 标 函 数 ： Max z = 50 x 1 + 100 x2 约 束 条 件 ： s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0*看 p 7-9 例 1-1， 1-2 例 1. 某 工 厂 在 计 划 期 内 要 安 排 甲 、 乙 两 种 产 品 的 生 产 ， 已 知 生 产 单 位 产 品 所 需 的 设 备 台 时及 A、 B两 种 原 材 料 的 消 耗 以 及 资 源 的 限 制 ， 如 下 表 ：问 题 ： 工 厂 应 分 别 生 产 多 少 单 位 甲 、 乙 产 品 才 能 使 工

14、厂 获 利 最 多 ？甲 乙 资 源 限 制设 备 1 1 300 台 时原 料 A 2 1 400 千 克原 料 B 0 1 250 千 克单 位 产 品 获 利 50 元 100 元 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 13 1、 线 性 规 划 （ 续 1.1）1. 1 线 性 规 划 的 概 念 线 性 规 划 的 组 成 ： 目 标 函 数 Max f 或 Min f 约 束 条 件 s.t. (subject to) 满 足 于 决 策 变 量 用 符 号 来 表 示 可 控 制 的 因 素 一 般 形 式 ( p10- p 11)目 标 函 数 ：

15、 Max （ Min） z = c1 x1 + c2 x2 + + cn xn 约 束 条 件 ： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1 a21 x1 + a22 x2 + + a2n xn （ =, ） b2 a m1 x1 + am2 x2 + + amn xn （ =, ） bm x1 ， x2 ， ， xn 0 标 准 形 式 ( p11- p 15 ， 例 1-3)目 标 函 数 ： Max z = c1 x1 + c2 x2 + + cn xn 约 束 条 件 ： s.t. a11 x1 + a12 x2 + + a1n xn = b1

16、 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ， x2 ， ， xn 0*练 习 ： p 68-70 习 题 1 1-1， 1-2 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 14 1、 线 性 规 划 （ 续 1.2）1. 2 线 性 规 划 问 题 解 的 概 念 及 性 质 熟 悉 下 列 一 些 解 的 概 念 （ p15-16） 可 行 解 、 可 行 解 集 （ 可 行 域 ） ， 最 优 解 、 最 优 值 ， 基 、 基 变 量 、 非 基 变 量 ， 基 本解 、

17、 基 本 可 行 解 ， 可 行 基 、 最 优 基 。 图 解 方 法 及 各 有 关 概 念 的 意 义 （ p16-20） 看 ： 图 解 法 步 骤 ， 例 1-4， 1-5， 1-6， 1-7， 1-8， 1-9 下 一 页 是 一 个 图 解 法 解 题 的 一 个 例 子 ， 右 图 中 的 阴 影 部 分 为 可 行 域 。 单 纯 形 法 的 理 论 基 础 （ p20-30） 1.2.3段 要 求 看 懂 ， 了 解 如 何 直 接 通 过 对 约 束 矩 阵 的 分 析 求 出 基 本 可 行 解 1.2.4, 1.2.5两 段 应 注 重 结 论 的 了 解 ， 如 单

18、 纯 形 法 思 想 和 关 于 线 性 规 划 解 的 四 个 定 理 ， 而 对 证 明 过 程 则 可 根 据 自 己 的 数 学 基 础 来 掌 握 ： 基 础 很 好 ， 可 要 求 掌 握 ； 否 则 ， 也 可 略 去 不 看 。*习 题 ： p70 习 题 1 1-3， 1-4 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 15 1、 线 性 规 划 （ 续 1.2）例 1.目 标 函 数 ： Max z = 50 x1 + 100 x2 约 束 条 件 ： s.t. x 1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C

19、) x1 0 (D) x2 0 (E)得 到 最 优 解 ： x1 = 50， x2 = 250 最 优 目 标 值 z = 27500 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 16 1、 线 性 规 划 （ 续 1.3）1. 3 单 纯 形 法 利 用 单 纯 形 表 的 方 法 求 解 线 性 规划 重 点 (p30-45 1.3.1, 1.3.2, 1.3.3) 此 项 内 容 是 本 章 的 重 点 ， 学 习 中 应注 意 掌 握 表 格 单 纯 形 法 求 解 线 性 规 划 问题 的 基 本 过 程 。 要 通 过 读 懂 教 材 内 容 以及 大 量

20、 练 习 来 掌 握 。 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 17 1、 线 性 规 划 （ 续 1.3） 表 格 单 纯 形 法 ( p40- p 45) 考 虑 ： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 a m1 x1 + am2 x2 + + amn xn bm x1 ， x2 ， ， xn 0 加 入 松 弛 变 量 ： Max z = c1 x1 + c2 x2 +

21、 + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ， x2 ， ， xn ， xn+1 ， ， xn+m 0 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 18 显 然 ， xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是 基 本 可 行 解 对 应 的 基 是 单 位 矩 阵 。以 下 是 初 始 单 纯 形 表 ： m

22、 m 其 中 ： f = - cn+i bi j = cj - cn+i aij 为 检 验 数 cn+i = 0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m 1、 线 性 规 划 （ 续 1.3） c1 cn cn+1 cn+mCB XB x1 xn xn+1 xn+m ic n+1 xn+1 b1 a11 a1n a1n+1 a1n+m 1cn+2 xn+2 b2 a21 a2n a2n+1 a2n+m 2 c n+m xn+m bm am1 amn amn+1 amn+m m-z f 1 n 0 0 h

23、ttp:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 19 1、 线 性 规 划 （ 续 1.3单 纯 形 法 解 题 例 ） 50 100 0 0 0CB XB x1 x2 x3 x4 x5 i0 x3 300 1 1 1 0 0 3000 x 4 400 2 1 0 1 0 4000 x5 250 0 (1) 0 0 1 250-z 0 50 100* 0 0 00 x 3 50 (1) 0 1 0 -1 500 x4 150 2 0 0 1 -1 75100 x2 250 0 1 0 0 1-z -25000 50* 0 0 0 -100 50 x1 50 1 0 1 0 -

24、10 x4 50 0 0 -2 1 1100 x2 250 0 1 0 0 1-z -27500 0 0 -50 0 -50 例 1。 化 标 准 形 式 ： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250 x1 , x2 , x3 , x4 , x5 0 最 优 解 x1 = 50 x2 = 250 x4 = 50（ 松 弛 标 量 ， 表 示 原 料 A有 50个 单 位 的 剩 余 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 20 注 意 ： 单

25、 纯 形 法 中 ， 1、 每 一 步 运 算 只 能 用 矩 阵 初 等 行 变 换 ； 2、 表 中 第 3列 的 数 总 应 保 持 非 负 （ 0） ； 3、 当 所 有 检 验 数 均 非 正 （ 0） 时 ， 得 到 最优 单 纯 形 表 。1、 线 性 规 划 （ 续 1.3） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 21 1、 线 性 规 划 （ 续 1.3） 一 般 情 况 的 处 理 及 注 意 事 项 的 强 调 （ p45-55） 1.3.4段 主 要 是 讨 论 初 始 基 本 可 行 解 不 明 显 时 ， 常 用 的 方 法 。要 弄

26、清 它 的 原 理 ， 并 通 过 例 1-14 例 1-17掌 握 这 些 方 法 ， 同时 进 一 步 熟 悉 用 单 纯 形 法 解 题 。考 虑 一 般 问 题 ： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a 21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ， x2 ， ， xn 0 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 22 1、 线 性 规

27、 划 （ 续 1.3） 大 M法 ： 引 入 人 工 变 量 xn+i 0 i = 1 , , m ; 充分 大 正 数 M 。 得 到 ， Max z = c1 x1 + c2 x2 + + cn xn + M xn+1 + + M xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x 1 ， x2 ， ， xn ， xn+1 ， ， xn+m 0显 然 ， xj = 0 j=1, , n

28、; xn+i = bi i =1 , , m 是 基 本 可 行 解 对 应 的 基 是 单 位 矩 阵 。 结 论 ： 若 得 到 的 最 优 解 满 足 xn+i = 0 i = 1 , , m 则 是 原 问题 的 最 优 解 ； 否 则 ， 原 问 题 无 可 行 解 。 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 23 1、 线 性 规 划 （ 续 1.3） 两 阶 段 法 ： 引 入 人 工 变 量 xn+i 0， i = 1 , , m； 构 造 ， Max z = - xn+1 - xn+2 - - xn+m s.t. a11 x1 + a12 x2 +

29、 + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ， x2 ， ， xn ， xn+1 ， ， xn+m 0 第 一 阶 段 求 解 上 述 问 题 ：显 然 ， x j = 0 j=1, , n ; xn+i = bi i =1 , , m 是 基 本 可 行 解 对 应 的 基 是 单 位 矩 阵 。 结 论 ： 若 得 到 的 最 优 解 满 足 xn+i = 0 i = 1 , , m 则 是 原 问题 的 基 本 可 行 解 ；

30、否 则 ， 原 问 题 无 可 行 解 。 得 到 原 问 题 的 基 本 可 行 解 后 ， 第 二 阶 段 求 解 原 问 题 。 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 24 1、 线 性 规 划 （ 续 1.3） 例 题 例 ： （ LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 0 大 M法 问 题 （ LP - M） Max z = 5 x1 +

31、 2 x2 + 3 x3 - x4 - M x5 - M x6 s.t. x 1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0 两 阶 段 法 ： 第 一 阶 段 问 题 （ LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x 1 , x2 , x3 ,

32、 x4 , x5 , x6 0 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 25 1、 线 性 规 划 （ 续 1.3） 大 M法 例5 2 3 -1 -M -M CB XB x1 x2 x3 x4 x5 x6 i-M x5 15 1 2 3 0 1 0 5-M x 6 20 2 1 (5) 0 0 1 4-1 x4 26 1 2 4 1 0 0 6.5-z 35M+26 3M+6 3M+4 8M+7 0 0 0-M x 5 3 -1/5 (7/5) 0 0 1 -3/5 15/73 x3 4 2/5 1/5 1 0 0 1/5 20-1 x4 10 -3/5 6/5

33、0 1 0 -4/5 25/3-z 3M-2 -M/5+16/5 7/5M+13/5 0 0 0 -8/5M-7/5 2 x2 15/7 -1/7 1 0 0 5/7 -3/73 x3 25/7 (3/7) 0 1 0 -1/7 2/7 25/3-1 x4 52/7 -3/7 0 0 1 -6/7 -2/7-z -53/7 25/7 0 0 0 -M-13/7 -M-2/7 2 x2 10/3 0 1 1/3 0 2/3 -1/35 x1 25/3 1 0 7/3 0 -1/3 2/3-1 x4 11 0 0 1 1 -1 0-z -112/3 0 0 -25/3 0 -M-2/3 -M+8/

34、3 大 M法 （ LP - M） 得 到 最 优 解 ： (25/3， 10/3， 0， 11) T 最 优 目 标 值 ： 112/3 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 26 1、 线 性 规 划 （ 续 1.3） 两 阶 段 法 例 0 0 0 0 -1 -1CB XB x1 x2 x3 x4 x5 x6 i-1 x5 15 1 2 3 0 1 0 5-1 x 6 20 2 1 (5) 0 0 1 40 x4 26 1 2 4 1 0 0 6.5-z 35 3 3 8 0 0 0-1 x 5 3 -1/5 (7/5) 0 0 1 -3/5 15/70 x3

35、 4 2/5 1/5 1 0 0 1/5 200 x4 10 -3/5 6/5 0 1 0 -4/5 25/3-z 3 -1/5 7/5 0 0 0 -8/5 0 x2 15/7 -1/7 1 0 0 5/7 -3/70 x3 25/7 3/7 0 1 0 -1/7 2/7 25/30 x4 52/7 -3/7 0 0 1 -6/7 -2/7-z 0 0 0 0 0 -1 -1 第 一 阶 段 （ LP - 1） 得 到 原 问 题 的 基 本 可 行 解 ： (0， 15/7， 25/7， 52/7) T http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 27 1、 线 性

36、 规 划 （ 续 1.3） 两 阶 段 法 例 5 2 3 -1CB XB x1 x2 x3 x4 i2 x2 15/7 -1/7 1 0 03 x 3 25/7 (3/7) 0 1 0 25/3-1 x4 52/7 -3/7 0 0 1-z -53/7 25/7 0 0 02 x 2 10/3 0 1 1/3 05 x1 25/3 1 0 7/3 0-1 x4 11 0 0 1 1-z -112/3 0 0 -25/3 0 第 二 阶 段 把 基 本 可 行 解 填 入 表 中 得 到 原 问 题 的 最 优 解 ： (25/3， 10/3， 0， 11) T 最 优 目 标 值 ： 112

37、/3 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 28 1、 线 性 规 划 （ 续 1.3）1.3.5 矩 阵 描 述 此 段 为 选 读 ， 有困 难 者 可 不 看 。 1.3.6 段 单 纯 形 迭 代 过 程 中 的 几 点 注意 事 项 是 对 有 关 内 容 的 强 调 和 补 充 ， 要认 真 学 习 、 理 解 。*习 题 ： p70-71 习 题 1 1-5， 1-6 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 29 1. 4 线 性 规 划 应 用 建 模 （ p55-68）本 节 介 绍 了 些 线 性 规 划 应 用 的

38、 例 子 ， 这 些 例 子 从 多 个 方 面 介 绍 建 模 对 未 来是 很 有 用 的 ， 应 认 真 对 待 。 除 了 教 材 上 的 例 子 之 外 ， 还 有 许 多 其 它 应 用 ：* 合 理 利 用 线 材 问 题 ： 如 何 下 料 使 用 材 最 少* 配 料 问 题 ： 在 原 料 供 应 量 的 限 制 下 如 何 获 取 最 大 利 润* 投 资 问 题 ： 从 投 资 项 目 中 选 取 方 案 ， 使 投 资 回 报 最 大* 产 品 生 产 计 划 ： 合 理 利 用 人 力 、 物 力 、 财 力 等 ， 使 获 利 最 大* 劳 动 力 安 排 ： 用

39、 最 少 的 劳 动 力 来 满 足 工 作 的 需 要* 运 输 问 题 ： 如 何 制 定 调 运 方 案 ， 使 总 运 费 最 小 *下 面 是 一 些 建 模 的 例 子 ， 有 兴 趣 者 ， 可 作 为 练 习 。 这 些 例 子 有 一 定 的 难 度 ， 做起 来 会 有 一 些 困 难 。 *习 题 ： p72-73 习 题 1 1-7， 1-8， 1-9， 1-10 1、 线 性 规 划 （ 续 1.4） 返 回 目 录 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 30 例 某 昼 夜 服 务 的 公 交 线 路 每 天 各 时 间 段 内 所 需

40、 司 机 和 乘 务 人员 数 如 下 ： 设 司 机 和 乘 务 人 员 分 别 在 各 时 间 段 一 开 始 时 上 班 ， 并 连 续工 作 八 小 时 ， 问 该 公 交 线 路 怎 样 安 排 司 机 和 乘 务 人 员 ， 既 能满 足 工 作 需 要 ， 又 配 备 最 少 司 机 和 乘 务 人 员 ?班 次 时 间 所 需 人 数1 6： 00 10： 00 60 2 10： 00 14： 00 703 14： 00 18： 00 604 18： 00 22： 00 505 22： 2： 00 20 6 2： 00 6： 00 30 例 ： 人 力 资 源 分 配 的 问

41、题 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 31 解 ： 设 xi 表 示 第 i班 次 时 开 始 上 班 的 司 机 和 乘 务 人员 数 ,这 样 我 们 建 立 如 下 的 数 学 模 型 。目 标 函 数 ： Min x1 + x2 + x3 + x4 + x5 + x6 约 束 条 件 ： s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x 1,x2,x3,x4,x5,x6 0 例 ： 人 力 资 源 分 配 的 问 题 （ 续 ） http:/ (海 量 营

42、销 管 理 培 训 资 料 下 载 ) 32 例 、 明 兴 公 司 生 产 甲 、 乙 、 丙 三 种 产 品 ， 都 需 要 经 过 铸造 、 机 加 工 和 装 配 三 个 车 间 。 甲 、 乙 两 种 产 品 的 铸 件 可 以 外包 协 作 ， 亦 可 以 自 行 生 产 ， 但 产 品 丙 必 须 本 厂 铸 造 才 能 保 证质 量 。 数 据 如 下 表 。 问 ： 公 司 为 了 获 得 最 大 利 润 ， 甲 、 乙 、丙 三 种 产 品 各 生 产 多 少 件 ？ 甲 、 乙 两 种 产 品 的 铸 造 中 ， 由 本公 司 铸 造 和 由 外 包 协 作 各 应 多

43、少 件 ？ 甲 乙 丙 资 源 限 制铸 造 工 时 (小 时 /件 ) 5 10 7 8000机 加 工 工 时 (小 时 /件 ) 6 4 8 12000装 配 工 时 (小 时 /件 ) 3 2 2 10000 自 产 铸 件 成 本 (元 /件 ) 3 5 4外 协 铸 件 成 本 (元 /件 ) 5 6 -机 加 工 成 本 (元 /件 ) 2 1 3装 配 成 本 (元 /件 ) 3 2 2 产 品 售 价 (元 /件 ) 23 18 16 例 ： 生 产 计 划 的 问 题 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 33 解 ： 设 x1,x2,x3 分

44、 别 为 三 道 工 序 都 由 本 公 司 加 工 的 甲 、 乙 、 丙三 种 产 品 的 件 数 ， x4,x5 分 别 为 由 外 协 铸 造 再 由 本 公 司 机 加工 和 装 配 的 甲 、 乙 两 种 产 品 的 件 数 。 求 xi 的 利 润 ： 利 润 = 售 价 - 各 成 本 之 和可 得 到 xi（ i=1,2,3,4,5） 的 利 润 分 别 为 15、 10、 7、 13、 9元 。这 样 我 们 建 立 如 下 的 数 学 模 型 。目 标 函 数 ： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 约 束 条 件 ： s.t. 5x1

45、 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x 1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0 例 ： 生 产 计 划 的 问 题 （ 续 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 34 例 、 永 久 机 械 厂 生 产 、 、 三 种 产 品 ， 均 要 经 过 A、 B 两道 工 序 加 工 。 假 设 有 两 种 规 格 的 设 备 A1、 A2能 完 成 A 工 序 ；有 三 种 规 格 的 设 备 B1、 B2、 B3能 完 成 B 工

46、序 。 可 在 A、 B的任 何 规 格 的 设 备 上 加 工 ； 可 在 任 意 规 格 的 A设 备 上 加 工 ，但 对 B工 序 ， 只 能 在 B1设 备 上 加 工 ； 只 能 在 A2与 B2设 备 上 加工 ； 数 据 如 下 表 。 问 ： 为 使 该 厂 获 得 最 大 利 润 ， 应 如 何 制 定产 品 加 工 方 案 ？ 产 品 单 件 工 时 设 备 设 备 的有 效 台 时 满 负 荷 时 的设 备 费 用A1 5 10 6000 300A 2 7 9 12 10000 321B1 6 8 4000 50B2 4 11 7000 783B 3 7 4000 20

47、0原 料 （ 元 /件 ） 0.25 0.35 0.50售 价 （ 元 /件 ） 1.25 2.00 2.80 例 ： 生 产 计 划 的 问 题 （ 续 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 35 解 ： 设 xijk 表 示 第 i 种 产 品 ， 在 第 j 种 工 序 上 的 第 k 种 设 备 上 加 工的 数 量 。 利 润 = （ 销 售 单 价 - 原 料 单 价 ） * 产 品 件 数 之 和 - （ 每 台 时 的设 备 费 用 *设 备 实 际 使 用 的 总 台 时 数 ） 之 和 。 这 样 我 们 建 立 如 下 的 数 学 模 型

48、 : Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t. 5x111 + 10 x211 6000 （ 设 备 A1 ） 7x112 + 9x212 + 12x312 10000 （ 设 备 A2 ） 6x 121 + 8x221 4000 （ 设 备 B1 ） 4x122 + 11x322 7000 （ 设 备 B2 ） 7x123 4000 （ 设 备 B3 ） x111+ x112- x121- x122- x123 = 0

49、 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） x211+ x212- x221 = 0 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） x312 - x322 = 0 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,3 例 ： 生 产 计 划 的 问 题 （ 续 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 36 例 、 某 工 厂 要 做 100套 钢 架 ， 每 套 用 长 为 2.9 m,2.1 m,1.5 m的圆 钢 各 一 根 。 已

50、 知 原 料 每 根 长 7.4 m， 问 ： 应 如 何 下 料 ， 可使 所 用 原 料 最 省 ？解 ： 设 计 下 列 5 种 下 料 方 案 方 案 1 方 案 2 方 案 3 方 案 4 方 案 5 方 案 6 方 案 7 方 案 82.9 m 1 2 0 1 0 1 0 02.1 m 0 0 2 2 1 1 3 01.5 m 3 1 2 0 3 1 0 4合 计 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 剩 余 料 头 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4假 设 x1,x2,x3,x4,x5 分 别 为 上 面 前 5 种 方 案 下

51、料 的 原 材 料 根数 。 这 样 我 们 建 立 如 下 的 数 学 模 型 。目 标 函 数 ： Min x1 + x2 + x3 + x4 + x5 约 束 条 件 ： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0 例 ： 套 裁 下 料 问 题 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 37 例 6 某 工 厂 要 用 三 种 原 料 1、 2、 3混 合 调 配 出 三 种 不同 规 格 的 产 品 甲 、 乙 、 丙 ， 数 据 如

52、下 表 。 问 ： 该 厂应 如 何 安 排 生 产 ， 使 利 润 收 入 为 最 大 ？ 产 品 名 称 规 格 要 求 单 价 （ 元 /kg）甲 原 材 料 1不 少 于 50%， 原 材 料 2不 超 过 25% 50乙 原 材 料 1不 少 于 25%， 原 材 料 2不 超 过 50% 35 丙 不 限 25原 材 料 名 称 每 天 最 多 供 应 量 单 价 （ 元 /kg） 1 100 652 100 253 60 35 例 ： 配 料 问 题 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 38 例 ： 配 料 问 题 （ 续 ）解 ： 设 xij 表

53、 示 第 i 种 （ 甲 、 乙 、 丙 ） 产 品 中 原 料 j 的 含量 。 这 样 我 们 建 立 数 学 模 型 时 ， 要 考 虑 ： 对 于 甲 ： x11， x12， x13； 对 于 乙 ： x21， x22， x23； 对 于 丙 ： x31， x32， x33； 对 于 原 料 1： x11， x21， x31； 对 于 原 料 2： x12， x22， x32； 对 于 原 料 3： x 13， x23， x33； 目 标 函 数 ： 利 润 最 大 ， 利 润 = 收 入 - 原 料 支 出 约 束 条 件 ： 规 格 要 求 4 个 ； 供 应 量 限 制 3 个

54、。 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 39 Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （ 原 材 料 1不 少 于 50%） -0.25x11+0.75x12 -0.25x13 0 （ 原 材 料 2不 超 过 25%） 0.75x21-0.25x22 -0.25x23 0 （ 原 材 料 1不 少 于 25%） -0.5 x21+0.5 x22 -0.5 x23 0 （ 原 材 料 2不 超 过 50%） x11+ x21 +

55、x31 100 (供 应 量 限 制 ） x12+ x22 + x32 100 (供 应 量 限 制 ） x 13+ x23 + x33 60 (供 应 量 限 制 ） xij 0 , i = 1,2,3; j = 1,2,3 例 ： 配 料 问 题 （ 续 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 40 例 8 某 部 门 现 有 资 金 200万 元 ， 今 后 五 年 内 考 虑 给 以 下 的 项 目 投 资 。 已 知 ： 项目 A： 从 第 一 年 到 第 五 年 每 年 年 初 都 可 投 资 ， 当 年 末 能 收 回 本 利 110%； 项 目

56、B： 从 第一 年 到 第 四 年 每 年 年 初 都 可 投 资 ， 次 年 末 能 收 回 本 利 125%， 但 规 定 每 年 最 大 投 资 额不 能 超 过 30万 元 ； 项 目 C： 需 在 第 三 年 年 初 投 资 ， 第 五 年 末 能 收 回 本 利 140%， 但 规定 最 大 投 资 额 不 能 超 过 80万 元 ； 项 目 D： 需 在 第 二 年 年 初 投 资 ， 第 五 年 末 能 收 回 本利 155%， 但 规 定 最 大 投 资 额 不 能 超 过 100万 元 ； 据 测 定 每 万 元 每 次 投 资 的 风 险 指 数 如 右 表 ：问 ：a）

57、 应 如 何 确 定 这 些 项 目 的 每 年 投 资 额 ， 使 得 第 五 年 年 末 拥 有 资 金 的 本 利 金 额 为 最大 ？b） 应 如 何 确 定 这 些 项 目 的 每 年 投 资 额 ， 使 得 第 五 年 年 末 拥 有 资 金 的 本 利 在 330万 元的 基 础 上 使 得 其 投 资 总 的 风 险 系 数 为 最 小 ？ 项 目 风 险 指 数 （ 次 /万 元 ）A 1B 3C 4D 5.5 解 ： 1） 确 定 决 策 变 量 ： 连 续 投 资 问 题 设 x ij ( i = 1 - 5， j = 1、 2、 3、 4)表 示 第 i 年 初 投 资

58、 于 A(j=1)、 B(j=2)、 C(j=3)、D(j=4)项 目 的 金 额 。 这 样 我 们 建 立 如 下 的 决 策 变 量 ： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24 例 ： 投 资 问 题 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 41 2） 约 束 条 件 ：第 一 年 ： A当 年 末 可 收 回 投 资 ， 故 第 一 年 年 初 应 把 全 部 资 金 投 出 去 ， 于 是 x11+ x12 = 200；第 二 年 ： B次 当 年 末 才 可 收 回 投 资 故 第 二 年

59、年 初 的 资 金 为 x11， 于 是 x21 + x22+ x24 = 1.1x11；第 三 年 ： 年 初 的 资 金 为 x21+x12， 于 是 x31 + x32+ x33 = 1.1x21+ 1.25x12；第 四 年 ： 年 初 的 资 金 为 x31+x22， 于 是 x41 + x42 = 1.1x31+ 1.25x22；第 五 年 ： 年 初 的 资 金 为 x41+x32， 于 是 x51 = 1.1x41+ 1.25x32； B、 C、 D的 投 资 限 制 ： xi2 30 ( I =1、 2、 3、 4 )， x33 80， x24 100 3） 目 标 函 数

60、及 模 型 ：a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x 31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( I =1、 2、 3、 4 )， x33 80， x24 100 xij 0 ( i = 1、 2、 3、 4、 5； j = 1、 2、 3、 4） b) Min f = (x11+x21+x31+x41+x51

61、)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； x i2 30 ( I =1、 2、 3、 4 )， x33 80， x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、 2、 3、 4、 5； j = 1、 2、 3、 4） 例 ： 投 资 问 题

62、（ 续 ） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 42 2、 线 性 规 划 问 题 的 进 一 步 研 究 （ 2.1）2. 1 对 偶 原 理1、 对 偶 问 题 ： 考 虑 前 文 例 1 若 设 备 和 原 料 都 用 于 外 协 加 工 ， 工 厂 收 取 加 工 费 。 试 问 ：设 备 工 时 和 原 料 A、 B 各 如 何 收 费 才 最 有 竞 争 力 ？ 设 y1 ， y2 ， y3 分 别 为 每 设 备 工 时 、 原 料 A、 B每 单 位 的 收 取 费 用Max z = 50 x1 + 100 x2 Min f = 300 y1 +

63、 400 y2 + 250 y3 s.t. x 1 + x2 300 s.t. y1 + 2 y2 + 50 2 x1 + x2 400 （ 不 少 于 甲 产 品 的 利 润 ） x2 250 y1 + y2 + y3 100 x1 , x2 0 y1, y2 , y3 0 http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 43 2、 对 偶 定 义 对 称 形 式 ： 互 为 对 偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ” 一 般 形 式 ： 若

64、一 个 问 题 的 某 约 束 为 等 式 ， 那 么 对 应 的 对 偶 问 题 的相 应 变 量 无 非 负 限 制 ； 反 之 ， 若 一 个 问 题 的 某 变 量 无 非 负限 制 ， 那 么 对 应 的 对 偶 问 题 的 相 应 约 束 为 等 式 。2、 线 性 规 划 问 题 的 进 一 步 研 究 （ 2.1） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 44 3、 对 偶 定 理 （ 原 问 题 与 对 偶 问 题 解 的 关 系 ）考 虑 （ LP） 和 （ DP）定 理 2-1 （ 弱 对 偶 定 理 ） 若 x, y 分 别 为 （ LP）

65、和 （ DP） 的 可 行解 ， 那 么 cT x bT y 。推 论 若 （ LP） 可 行 ， 那 么 （ LP） 无 有 限 最 优 解 的 充 分 必 要 条件 是 （ LD） 无 可 行 解 。定 理 2-2 （ 最 优 性 准 则 定 理 ） 若 x, y 分 别 为 （ LP） 和 （ DP） 的可 行 解 ， 且 cT x = bT y ， 那 么 x, y分 别 为 （ LP） 和 （ DP） 的最 优 解 。定 理 2-3 （ 主 对 偶 定 理 ） 若 （ LP） 和 （ DP） 均 可 行 ， 那 么（ LP） 和 （ DP） 均 有 最 优 解 ， 且 最 优 值 相

66、 等 。以 上 定 理 、 推 论 对 任 意 形 式 的 相 应 线 性 规 划 的 对 偶 均 有 效 *习 题 ： p 99 习 题 2 2-1 2、 线 性 规 划 问 题 的 进 一 步 研 究 （ 2.1） http:/ (海 量 营 销 管 理 培 训 资 料 下 载 ) 45 4、 影 子 价 格 是 一 个 向 量 ， 它 的 分 量 表 示 最 优 目标 值 随 相 应 资 源 数 量 变 化 的 变 化 率 。 若 x*, y* 分 别 为 （ LP） 和 （ DP） 的 最 优 解 ， 那 么 ， cT x* = bT y* 。 根 据 f = bT y* = b1y1* + b2y2* + + bmym* 可 知 f / bi = yi* yi* 表 示 bi 变 化 1个 单 位 对 目 标 f 产 生 的 影 响 ， 称 yi* 为 bi的 影 子 价 格 。注 意 ： 若 B 是 最 优 基 ， y * = (BT)-1 cB 为 影 子 价 格 向 量 。 2、 线 性 规 划 问 题 的 进 一 步 研 究 （ 2.1） http:/ (海 量 营