《运筹学复习》PPT课件

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

1、运 筹 学 复 习 1、 线 性 规 划 的 基 本 概 念2、 单 纯 形 法 和 对 偶 单 纯 形 法3、 对 偶 线 性 规 划4、 运 输 问 题5、 目 标 规 划6、 整 数 规 划7、 网 络 最 大 流 问 题8、 网 络 最 短 路 径 问 题 第 一 章 线 性 规 划 模 型 和 单 纯 形 法q线 性 规 划 问 题 一 般 模 型目 标 函 数 ： max， min约 束 条 件 ： ,=,变 量 符 号 ： 0, unr, 0q线 性 规 划 的 标 准 形 式目 标 函 数 ： min约 束 条 件 ： =变 量 符 号 ： 0 unr,0)(X b),(AX.

2、t.s XCzmax(min) T 0X bAX.t.s XCzmin T q 非 标 准 形 式 转 化 为 标 准 形 式 极 大 化 目 标 函 数 转 化 为 极 小 化 ：目 标 函 数 系 数 变 号 约 束 条 件 是 不 等 式 转 化 为 等 式 ：“ ”约 束 加 上 松 弛 变 量 “ ”约 束 减 去 松 弛 变 量 变 量 没 有 符 号 限 制 转 化 为 变 量 非 负 ：没 有 符 号 限 制 的 变 量 用 两 个 非 负 变 量 的 差 表 示例 如 :max z=3x1+4x2-2x3+5x4s.t 4x1-x2+2x3-x4=4 x1+x2+3x3-x4

3、14 -2x1+3x2-x3+2x43 x10,x22,x30,x4:unr 线 性 规 划 的 图 解 画 约 束 直 线 确 定 满 足 约 束 条 件 的 半 平 面 所 有 半 平 面 的 交 集 凸 多 边 形 线 性 规 划 的可 行 域 画 两 条 目 标 函 数 等 值 线 确 定 目 标 函 数 优 化 的 方 向 平 行 移 动 目 标 函 数 等 值 线 得 到 线 性 规 划 的 最 优 解 q线 性 规 划 问 题 的 概 念基 ： 设 标 准 形 式 的 LP问 题 的 约 束 方 程 组 的 秩 为 M， B是 系 数 矩阵 A中 的 M阶 满 秩 子 矩 阵 ，

4、 则 称 B是 该 LP问 题 的 一 个 基 。基 变 量 ： B中 的 每 一 个 列 向 量 成 为 基 向 量 ， 对 应 的 变 量 为 基 变量 ， 共 有 M个 。非 基 变 量 ： B以 外 的 列 向 量 称 为 非 基 向 量 ， 对 应 变 量 成 为 非 基变 量 ， 共 有 N-M个 。基 础 解 ： 对 应 基 B， 令 所 有 的 非 基 变 量 为 零 ， 求 解 约 束 方 程 组AX=b， 可 惟 一 得 出 基 变 量 的 一 组 值 ， 这 样 得 到 的 N个 变量 的 一 组 解 成 为 一 个 “ 基 础 解 ” 。基 础 可 行 解 ： 如 果

5、一 个 基 础 解 中 的 所 有 变 量 都 大 于 或 等 于 0， 则称 这 个 基 础 解 为 “ 基 础 可 行 解 ” 。退 化 解 ： 基 解 中 的 非 零 分 量 的 个 数 小 于 M个 时 ， 即 某 个 基 变 量为 零 时 ， 此 时 为 退 化 解 。q线 性 规 划 的 基 本 定 理 线 性 规 划 的 基 础 可 行 解 就 是 可 行 域 的 极 点 。 线 性 规 划 的 基 本 概 念min z=x1+2x2s.t. x1+x2 4 (1) -x1+x22 (2) x2 5 (3) x1, x2 0 O ABCD EF G 41234 1 2 3 x1x

6、2 x3=0 x4=0 x2=0 x1=0 x5=0引 进 松 弛 变 量 x3, x4, x5min z=x 1+2x2s.t. x1+x2+x3 =4 -x1+x2 -x4 =2 x2 +x5=5 x1, x2 x3, x4, x50 基 础 解 O A B C D E F GB E F四 边 形 B E F G基 础 可 行 解可 行 域目 标 函 数 等 值 线 .最 优 解 B5 G qA不 是 可 行 解 ， 是 由 于 变 量 （ ） 0。qC不 是 可 行 解 ， 是 由 于 变 量 （ ） 0， 则 xn+i=0如 果 xn+i0， 则 wi=0边 际 利 润 大 于 0的

7、资 源 ， 在 最 优 生 产 计 划 条 件 下 没 有 剩 余wm+jxj=0 如 果 wm+j0， 则 xj=0如 果 xj0， 则 wm+j=0最 优 生 产 计 划 条 件 下 有 剩 余 的 资 源 ， 其 边 际 利 润 等 于 0 差 额 成 本 大 于 0（ 机 会 成 本 大 于 利 润 ） 的 产 品 ， 不 安 排 生 产安 排 生 产 的 产 品 ， 差 额 成 本 等 于 0（ 机 会 成 本 等 于 利 润 ） q灵 敏 度 分 析 主 要 分 析 当 所 给 问 题 数 据 改 变 时 ， 原 有 解 的 可 行 性 和 最 有 优 性有 何 变 化 。v目 标

8、 函 数 中 系 数 的 变 化v约 束 条 件 右 端 常 数 的 变 化v约 束 条 件 左 端 系 数 的 变 化v引 入 新 的 变 量v引 入 新 的 约 束 利 用 对 偶 单 纯 形 法 求 解 Min z=4x1+6x2+18x3 S.t x1+ 3x3 3 x2+2x3 5 x1,x2,x3 0 第 三 章 运 输 问 题q 运 输 问 题 的 模 型q运 输 问 题 的 表 格 表 示1 2 3 4 6 7 5 31 x11 x12 x13 x14 148 4 2 72 x21 x22 x23 x24 275 9 10 63 x 31 x32 x33 x34 1922 13

9、 12 13 q 运 输 表 中 一 个 基 必 须 具 备 的 特 点1、 一 个 基 应 占 表 中 的 m+n-1格2、 构 成 基 的 同 行 同 列 格 子 不 能 构 成 闭 回 路3、 一 个 基 在 表 中 所 占 的 格 子 应 包 括 表 的 每 行 和 每 列q初 始 基 可 行 解 的 求 法v西 北 角 法v最 小 元 素 法q最 优 解 的 获 得 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210运 输 问 题 1 2 3 41 12 9 11 14 1202 7 15 13 8 2

10、303 10 6 5 4 180125 85 110 210125 1050 85 350 180 030300 753575 0750 0用 最 小 元 素 法 得 到 一 个 初 始 基 础 可 行 解 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7求 非 基 变 量 x11的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7 -8求 非

11、基 变 量 x14的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7 -8-4求 非 基 变 量 x22的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7 -8-6-7求 非 基 变 量 x31的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 11

12、0 210125 85 180303575-7 -8-4-7 +1求 非 基 变 量 x32的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7 -8-4-7 +1 +4求 非 基 变 量 x33的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2303 10 6 5 4 180125 85 110 210125 85 180303575-7 -8-6-7 +1 +4x 33=75进 基 ， x23=0离 基 ， x24=30+

13、75=105， x34=180-75=105 确 定 进 基 变 量 和 离 基 变 量 1 2 3 41 12 9 11 14 1202 7 15 13 8 2301053 10 6 5 4 18075125 85 110 210125 85 10535-3求 非 基 变 量 x11的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2301053 10 6 5 4 18075125 85 110 210125 85 10535-3 -4求 非 基 变 量 x14的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 23010

14、53 10 6 5 4 18075125 85 110 210125 85 10535-3 -4-8求 非 基 变 量 x22的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2301053 10 6 5 4 18075125 85 110 210125 85 10535-6 -4-4-8求 非 基 变 量 x23的 检 验 数 1 2 3 41 12 9 11 14 1202 7 15 13 8 2301053 10 6 5 4 18075125 85 110 210125 85 10535-5 -4-4-7 -8求 非 基 变 量 x31的 检 验 数

15、1 2 3 41 12 9 11 14 1202 7 15 13 8 2301053 10 6 5 4 18075125 85 110 210125 85 10535-5 -4-4-7 -3-8得 到 最 优 解 ： x 12=85, x13=35, x21=125, x24=105, x33=75, x34=105 min z = 3660 求 非 基 变 量 x32的 检 验 数 q不 平 衡 运 输 问 题v发 大 于 收 ， 则 虚 设 收 地 ， 运 价 为 零v发 小 于 收 ， 则 虚 设 发 地 ， 运 价 为 零q灵 敏 度 分 析v基 变 量 的 运 价 调 整v非 基 变

16、 量 的 运 价 调 整 物 流 配 送 案 例 腾 飞 电 子 仪 器 厂 在 大 连 和 广 州 有 两 个 分 厂 生 产 同 一 种 仪 器 。 大 连分 厂 每 月 生 产 400台 广 州 分 厂 每 月 生 产 600台 。 该 公 司 在 上 海 和天 津 有 两 个 物 流 配 送 服 务 网 点 ， 负 责 对 南 京 、 济 南 、 南 昌 、 青 岛四 个 城 市 的 仪 器 进 行 配 送 供 应 。 另 外 ， 因 为 大 连 距 离 青 岛 较 近 ，公 司 同 意 大 连 分 厂 向 青 岛 直 接 供 货 。 这 些 城 市 间 的 每 台 仪 器 的 运输

17、费 用 标 在 两 个 城 市 间 的 弧 上 ， 单 位 为 百 元 。 公 司 应 该 如 何 调 运仪 器 可 使 总 运 输 费 用 最 低 ? 广 州600 南 昌350天 津 南 京200济 南150大 连400 青 岛300上 海2 446 362 561433 多 工 厂 模 型 一 家 公 司 有 A和 B两 个 工 厂 ,每 个 工厂 生 产 两 种 同 样 的 产 品 ,一 种 是 普 通的 ,每 件 利 润 10元 ;一 种 是 精 制 的 ,每件 利 润 15元 .两 厂 采 用 相 同 的 加 工 工艺 :研 磨 和 抛 光 .A厂 每 周 的 研 磨 能 力为 8

18、0小 时 ,抛 光 能 力 为 60小 时 ; B厂每 周 的 研 磨 能 力 为 60小 时 ,抛 光 能 力为 75小 时 .两 厂 生 产 各 类 单 位 产 品 所需 的 研 磨 和 抛 光 工 时 (以 小 时 计 )如表 所 示 .另 外 ,每 类 每 件 产 品 都 消 耗 4公 斤 的 原 材 料 ,该 公 司 每 周 可 获 得 原材 料 120公 斤 .问 :应 该 如 何 制 定 生 产 计 划 ? 工 厂 A B产 品 普 通 精 制 普 通 精 制研 磨 4 2 5 3抛 光 2 5 5 6 分 析 先 假 定 每 周 分 配 原 料 给 A厂 75公 斤 ,B厂 4

19、5公 斤 .设 x1为 A厂 的普 通 产 品 产 量 ;x2为 A厂 的 精 制 产 品 产 量 ;x3为 B厂 的 普 通 产 品 产量 ;x4为 B厂 的 精 制 产 品 产 量 . A厂 模 型 : Maxz=10 x1+15x2 S.t 4x1+4x2 75 (原 料 A) 4x1+2x2 80(研 磨 A) 2x1+5x2 60(抛 光 A) X1,x2 0 最 优 解 :(11.25,7.5,利 润 225) 剩 余 20小 时 的 研 磨 时 间 B厂 模 型 : Maxz=10 x3+15x4 S.t 4x3+4x4 45 (原 料 B) 5x3+3x4 60(研 磨 B)

20、5x3+6x4 75(抛 光 B) X3,x4 0 最 优 解 :(11.25,3.75,利 润 168.5) 剩 余 26.25小 时 的 研 磨 时 间 和 7.5小 时 的 抛 光 工 时 . 假 设 建 立 一 个 公 司 模 型 ,让 模 型 去 确 定 原 材 料 的 分 配 : Max z=10 x1+15x2+10 x3+15x4 S.t 4x1+4x2+4x3+4x4 120 4x1+2x2 80 2x1+5x2 60 5x3+3x4 60 5x3+6x4 75 x1,x2,x3,x4 0 最 优 解 : X1=9.17,x2=8.33,x4=12.5, z=404.15 多

21、 周 期 动 态 生 产 计 划 问 题 考 虑 某 厂 配 套 生 产 产 品 问 题 .今 年 头 四 个 月 收 到的 订 单 数 量 分 别 为 3000,4500,3500和 5000件 .该厂 正 常 生 产 每 月 可 生 产 产 品 3000件 ,利 用 加 班 还可 生 产 1500件 .正 常 生 产 成 本 为 每 件 5000元 ,加班 生 产 还 要 追 加 1500元 的 成 本 ,库 存 成 本 为 每 件每 月 200元 .问 该 厂 如 何 组 织 生 产 才 能 使 生 产 成本 最 低 ? 第 五 章 目 标 规 划q概 念v偏 差 变 量 ： 实 际 值

22、 与 目 标 值 之 间 差 距 的 变 量 表 示 ， 通 常 以di+ di-表 示 ， 分 别 为 正 、 负 偏 差 变 量 ， 且 有 di+ 0、 di- 0， di+ di- =0 v优 先 因 子 ： 描 述 问 题 中 目 标 重 要 性 程 度 的 差 别 ， 一 般 用 pi表 示 ， 通 常 i值 越 小 ， 代 表 的 优 先 程 度 越 高 。v目 标 约 束 ： 用 来 描 述 允 许 对 给 定 目 标 值 有 一 定 偏 离 程 度 的限 制 条 件 。 q目 标 规 划 模 型 的 特 点1、 引 进 正 负 偏 差 变 量 2、 模 型 中 必 须 有 目

23、 标 约 束 3、 目 标 函 数 为 偏 差 变 量 的 表 达 式 4、 以 优 先 级 因 子 描 述 目 标 的 重 要 性 程 度q目 标 规 划 的 解 法 单 纯 形 法 ： 按 单 纯 形 法 求 解 一 搬 目 标 规 划 问 题 的 满 意 解 。 求 解 时需 按 优 先 级 的 顺 序 进 行 逐 步 优 化 。v 各 目 标 具 有 相 同 等 级 的 目 标 规 划v 各 目 标 具 有 不 同 优 先 等 级 的 目 标 规 划v 各 目 标 具 有 赋 权 优 先 等 级 的 目 标 规 划 第 六 章 整 数 规 划q 整 数 规 划 的 基 本 概 念v 变

24、 量 的 取 值 为 整 数 的 LP问 题 为 整 数 规 划 问 题 。q 整 数 规 划 的 一 般 模 型q 整 数 规 划 的 解 法v 割 平 面 法 （ 纯 整 数 规 划 ）v 分 支 定 界 法 人 力 资 源 安 排 某 超 市 物 流 配 送 中 心 ， 星期 六 有 4个 装 卸 工 人 当 班 要分 别 指 派 他 们 去 完 成 4项 不 同的 装 卸 工 作 每 人 做 各 项 工作 所 取 得 的 利 润 如 下 表 所示 应 如 何 合 理 地 指 派 这 4人的 工 作 ， 才 能 使 配 送 中 心 获得 的 利 润 最 大 。 任 务人 员 A B C

25、D甲 66 69 72 75乙 70 74 73 86丙 77 68 67 70丁 78 72 74 68 v 点 与 （ 有 向 ） 边 每 一 条 边 和 两 个 节 点 关 联 ， 一 条 边 可 以 用两 个 节 点 的 标 号 表 示 （ i， j）jiv路 径 （ Path） 前 后 相 继 并 且 方 向 相 同 的 边 序 列 P=(1,2),(2,3),(3,4) 4231 4231v网 络 由 点 和 边 组 成第 七 章 网 络 规 划q 图 的 基 本 概 念 v连 通 图 任 意 两 个 节 点 之 间 至 少 有 一 条链 的 图 称 为 连 通 图 2 4 3 5

26、1v圈 (Cycle) 起 点 和 终 点 重 合 的 链 称 为 圈 =(1,2),(2,4),(3,4),(1,3) 圈 中 各 条 边 方 向 不 一 定 相 同 4231v树 (Tree) 无 圈 的 连 通 图 称 为 树 树 中 只 与 一 条 边 关 联 的 节 点 称为 悬 挂 节 点 v 回 路 （ Circuit） 起 点 和 终 点 重 合 的 路 径 称 为 回 路 =(1,2),(2,4),(4,1) 回 路 中 各 条 边 方 向 相 同 4231v 链 （ Chain） 前 后 相 继 并 且 方 向 不 一 定 相 同 的 边 序列 称 为 链 C=(1,2),

27、(3,2),(3,4) 4231 q 树 的 性 质v任 何 树 至 少 有 一 个 悬 挂 节 点 2 4 3 51 2 4 3 51 2 4 3 51v如 果 树 的 节 点 个 数 为 m， 则 边 的 个数 为 m-1v树 中 任 意 两 个 节 点 之 间 只 有 唯 一的 一 条 链v在 树 的 任 意 两 个 不 相 邻 的 节 点 之间 增 加 一 条 边 ， 则 形 成 唯 一 的 圈 q 最 小 支 撑 树v由 网 络 的 所 有 节 点 （ m个 ） 和网 络 的 m-1条 边 组 成 的 树 称 为 网 络的 支 撑 树 ， 构 成 支 撑 树 的 各 边 赋权 之 和

28、 最 小 的 为 最 小 支 撑 树 。 4231 4 231 4231 42314231 42314231 q 最 小 支 撑 树 的 算 法vKruskal算 法vPrim算 法q最 短 路 问 题 vD氏 算 法q最 短 链 问 题q网 络 上 的 最 大 流 问 题q最 小 割 集 1 2 543 6 7最 大 流 问 题3 611 2 7 43 84 7 125 uij求 从 1到 7的 最 大 流 1 2 543 6 73 611 2 7 43 84 7 125 uij检 查 每 一 条 边 不 饱 和 的 方 向 ， 用 表 示x=0 x=0 x=0 x=0 x=0 x=0 x=

29、0 x=0 x=0 x=0 x=0 x=0 D=minD12, D26, D 67=min3,6,12=3 D=minD13, D35, D 57=min11,4,5=41 2 543 6 73 611 2 7 43 84 7 125 uij寻 找 从 1到 7的 不 饱 和 链 ， 用 表 示 ， 求 出每 一 条 不 饱 和 链 的 间 隙 Dx=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0D=3 D=6 D=12D=11 D=4 D=5 1 2 543 6 73 611 2 7 43 84 7 125 uij增 加 不 饱 和 链 的 流 量

30、检 查 每 一 条 边 不 饱 和 的 方 向 ， 用 表 示x=3 x=3x=4 x=0 x=0 x=0 x=0 x=0 x=3x=4x=4 x=0f=7 f=7 寻 找 从 1到 7的 不 饱 和 链 ， 用 表 示 ， 求 出每 一 条 不 饱 和 链 的 间 隙 D1 2 543 6 73 611 2 7 43 84 7 125 uijx=3 x=3x=4 x=0 x=0 x=0 x=0 x=0 x=3x=4x=4 x=0D=7f=7 f=7 D=minD 13, D34, D 46 , D 67=min7,3,4,8=3D=3 D=4 D=9 1 2 543 6 73 611 2 7

31、 43 84 7 125 uij增 加 不 饱 和 链 的 流 量检 查 每 一 条 边 不 饱 和 的 方 向 ， 用 表 示x=3 x=3x=7 x=0 x=0 x=3x=3 x=0 x=6x=4x=4 x=0f=10 f=10 寻 找 从 1到 7的 不 饱 和 链 ， 用 表 示 ， 求 出每 一 条 不 饱 和 链 的 间 隙 D1 2 543 6 73 611 2 7 43 84 7 125 uijx=3 x=3x=7 x=0 x=0 x=3x=3 x=0 x=6x=4x=4 x=0f=10 f=10 D=minD 13, D32, D 26 , D 67=min4,2,3,6=2

32、D=4 D=2 D=3 D=6 增 加 不 饱 和 链 的 流 量检 查 每 一 条 边 不 饱 和 的 方 向 ， 用 表 示1 2 543 6 73 611 2 7 43 84 7 125 uijx=3 x=5x=9 x=2 x=0 x=3x=3 x=0 x=8x=4x=4 x=0f=12 f=12 寻 找 从 1到 7的 不 饱 和 链1 2 543 6 73 611 2 7 43 84 7 125 uijx=3 x=5x=9 x=2 x=0 x=3x=3 x=0 x=8x=4x=4 x=0f=12 f=12已 不 存 在 从 1到 7的 不 饱 和 链 。 获 得 最 大 流 ， f=

33、12X=1,3， X=2,4,5,6,7最 小 割 集 为 (1,2),(3,2),(3,4),(3,5)， 用 表 示最 小 割 集 的 容 量 为 u 12+u32+u34+u35=3+2+3+4=12 1 234 567 82 63 95847 610 411 7126最 短 路 径 问 题求 1到 8的 最 短 路 径 1 234 567 82 63 95847 610 411 7126w1=0X=1min0+2,0+6,0+3=min2,6,3=2， w2=2 1 234 567 82 63 95847 610 411 7126w1=0X=1,2min2+9,2+5,2+4,0+6,

34、0+3=min11,7,6,6,3=3， w4=3w2=2 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2,4min2+9,2+5,2+4,0+6,3+7,3+6,3+10=min11,7,6,6,10,9,13=5， w3=6w4=3 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2,3,4min2+9,2+5,6+8,3+6,3+10=min11,7,14,9,13=7， w6=7w4=3w3=6 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2

35、,3,4,6min2+9,7+4,7+11,3+10=min11,11,18,13=11， w5=11w4=3w3=6 w6=7 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2,3,4,5,6min11+12,7+7,7+11,3+10=min23,14,18,13=13， w7=13w4=3w3=6 w6=7w5=11 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2,3,4,6,7min11+12,7+7,13+6=min23,14,19=14， w8=14w4=3w3=6 w6=7w5=11

36、w7=13 1 234 567 82 63 95847 610 411 7126w1=0 w2=2X=1,2,3,4,6,7,8min11+12,7+7,13+6=min23,14,19=14， w8=14w4=3w3=6 w6=7w5=11w7=13 w8=14 1 234 567 82 63 95847 610 411 7126w1=0 w2=2w4=3w3=6 w6=7w5=11w7=13 w8=14从 1到 8的 最 短 路 径 为 14， 最 短 路 径 为 12 6 8从 1到 其 他 节 点 的 最 短 路 径 如 上 图 红 线 所 示 ， 其 中 到 3和5的 最 短 路 径

37、 有 两 条 。 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2一 、 最 短 路 径 问 题求 从 A到 E的 最 短 路 径 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f5(E)=0 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D1)=5 f5(E)=0505)E(f)ED(d)D(f 5114 + 251 121410 6 10413 1112 3965810 52C1C3 D

38、1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f4(D1)=5202)E(f)ED(d)D(f 5224 + 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C1)=8 f4(D1)=5 112421 141113 DC8118min29 53min )D(f)D,C( )D(f)D,C(min)C(f + + 最 优 决 策 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0

39、f3(C2)=7 f4(D1)=5f3(C1)=8 222422 141223 DC7711min25 56min )D(f)D,C( )D(f)D,C(min)C(f + + 最 优 决 策 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f3(C1)=8f3(C2)=7 232423 141333 DC121213min210 58min )D(f)D,C( )D(f)D,C(min)C(f + + 最 优 决 策 251 121410 6 10413 11

40、12 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B1)=20 f3(C2)=7f3(C1)=8 11 3331 2321 131112 CB 20222120min1210 714 812min)C(f)C,B( )C(f)C,B( )C(f)C,B(min)B(f + +最 优 决 策 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B2)=14 f3(C2

41、)=7f3(C1)=8f2(B1)=21 12 3332 2322 131222 CB 14161714min124 710 86min)C(f)C,B( )C(f)C,B( )C(f)C,B(min)B(f + +最 优 决 策 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14 23 3333 2323 131332 CB 19231921min1211 712 813mi

42、n)C(f)C,B( )C(f)C,B( )C(f)C,B(min)B(f + +最 优 决 策 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C2)=7f3(C1)=8f1(A)=19 f2(B2)=14f2(B1)=21 2 323 222 1211 BA 19201923min191 145 212min)B(f)B,A( )B(f)B,A( )B(f)B,A(min)A(f + +最 优 决 策 251 121410 6 10

43、413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C2)=7f3(C1)=8f1(A)=19 f2(B2)=14f2(B1)=21状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态A （ A， B 2） B2 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C

44、2)=7f3(C1)=8f1(A)=19 f2(B2)=14f2(B1)=21状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态A （ A， B 2） B2 （ B2， C1） C1 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C2)=7f3(C1)=8f1(A)=19 f2(B2)=14f2(B1)=21状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状

45、态 最 优 决 策 状 态A （ A， B 2） B2 （ B2， C1） C1 （ C1， D1） D1 251 121410 6 10413 1112 3965810 52C1C3 D1A B1B3B2 D2 EC2 f4(D2)=2 f5(E)=0f3(C3)=12 f4(D1)=5f2(B3)=19 f3(C2)=7f3(C1)=8f1(A)=19 f2(B2)=14f2(B1)=21状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态 最 优 决 策 状 态A （ A， B 2） B2 （ B2， C1） C1 （ C1， D1） D1 （ D1， E） E

46、从 A到 E的 最 短 路 径 为 19， 路 线 为 AB 2C1 D1 E 资 源 分 配 问 题 4台 设 备 ， 分 配 给 A、 B、 C三 个 工 厂 ， 每 个 工 厂 分 配 到不 同 数 量 的 设 备 所 能 产 生 的 效 益 （ 万 吨 ） 如 下 表 所 示 。 求设 备 的 最 优 分 配 方 案 ， 使 总 效 益 最 大 。设 备台 数 产 生 的 效 益 （ 万 吨 ）工 厂 A 工 厂 B 工 厂 C0 0 0 01 15 12 92 28 28 273 40 42 474 50 55 53 动 态 规 划 模 型 工 厂 A 工 厂 B 工 厂 C k=1

47、 k=2 k=3 k=4状 态 变 量 xk： 尚 未分 配 的 设 备 台 数 x2 x3 x4决 策 变 量 dk： 每 个 工厂 分 配 的 设 备 台 数 d1 d2 d3x 2=x1-d1阶 段 k x1 x3=x2-d2 x4=x3-d3决 策 允 许 集 合 Dk(xk)：分 配 台 数 dk的 范 围 0d1 x1 0d2 x2 0d3 x3状 态 转 移 方 程 Dk(xk)： 状 态 如何 随 上 一 状 态 以 及 决 策 变 化阶 段 指 标 Vk(xk,dk)： 每 个工 厂 分 配 设 备 产 生 的 效 益 v1(x1,d1) v2(x2,d2) v3(x3,d3

48、)最 优 指 标 函 数 fk(xk) fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终 端 条 件 fn(xn) f4(x4)=0 x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) d3*0 0 0 0 0+0=0 0 01 0 1 0 0+0=0 9 11 0 9 9+0=9*2 0 2 0 0+0=0 27 21 1 9 9+0=92 0 27 27+0=27*3 0 3 0 0+0=0 47 31 2 9 9+0=92 1 27 27+0=273 0 47 47+0=47* 4 0 4 0 0+0=0 53 41 3 9 9+0

49、=92 2 27 27+0=273 1 47 47+0=474 0 53 53+0=53* x3 f3(x3) d3*0 0 01 9 12 27 23 47 34 53 4f3(x3) f4(x4)x4 f4(x4)0 01 02 03 04 0 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) d2*0 0 0 0 0+0=0 0 01 0 1 0 0+9=9 12 11 0 12 12+0=12*2 0 2 0 0+27=27 28 21 1 12 12+9=212 0 28 28+0=28*3 0 3 0 0+47=47* 47 01 2 1

50、2 12+27=392 1 28 28+9=373 0 42 42+0=42 4 0 4 0 0+53=53 59 11 3 12 12+47=59*2 2 28 28+27=553 1 42 42+9=514 0 55 55+0=55 x3 f3(x3) d3*0 0 01 9 12 27 23 47 34 53 4 f3(x3)x 2 f2(x2) d2*0 0 01 12 12 28 23 47 04 59 1f2(x2) f4(x4)=0 x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) d1*4 0 4 0 0+59=59 62 11 3

51、15 15+47=62*2 2 28 28+28=563 1 40 40+12=524 0 50 50+0=50 x1 f1(x1) d1*4 62 1x2 f2(x2) d2*0 0 01 12 12 28 23 47 04 59 1 x3 f3(x3) d3*0 0 01 9 12 27 23 47 34 53 4最 优 解 为 ：x 1=4, d1*=1x2=x1-d1=3, d2*=0 x3=x2-d2=3, d3*=3x4=x3-d3=0即工 厂 A分 配 1台 ， 工 厂 B不 分 配 ， 工 厂 C分 配 3台 ，最 大 效 益 为 62万 吨 ， 设 备 没 有 剩 余 。 背

52、 包 问 题一 艘 货 轮 载 重 量 为 1000吨 ， 装 载 以 下 三 种 货 物 ：货 物 A 货 物 B 货 物 C重 量 （ 吨 /件 ） 240 320 430价 值 （ 万 元 /件 ） 35 46 63单 位 重 量 价 值 0.146 0.144 0.147每 种 货 物 各 装 载 多 少 件 ， 使 一 船 货 物 价 值 最 高 。 x1 240吨 x2 320吨 x31000吨 0件 1000吨 0件 1000吨1件 680吨2件 360吨3件 40吨1件 760吨 0件 760吨1件 440吨2件 120吨2件 520吨 0件 520吨1件 200吨3件 280

53、吨 0件 280吨4件 40吨 0件 40吨 x1 x2 x31000 40 40280 120520 200760 2801000 3604405206807601000排 序列 举 各 阶 段 可 能 的 状 态 x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) d3*40 0 40 0 0+0=0 0 0120 0 120 0 0+0=0 0 0200 0 200 0 0+0=0 0 0280 0 280 0 0+0=0 0 0360 0 360 0 0+0=0 0 0440 0 440 0 0+0=0 63 11 10 63 63+0=63*

54、520 0 520 0 0+0=0 63 11 90 63 63+0=63*680 0 680 0 0+0=0 63 11 250 63 63+0=63* 760 0 760 0 0+0=0 63 11 330 63 63+0=63*1000 0 1000 0 0+0=0 126 21 570 63 63+0=632 140 126 126+0=126* x3 f3(x3) d3*40 0 0120 0 0200 0 0280 0 0360 0 0440 63 1520 63 1680 63 1760 63 11000 126 2f3(x3) f4(x4) 0 x2 D2(x2) x3 v2(

55、x2,d2) v2(x2,d2)+f3(x3) f2(x2) d2*40 0 40 0 0+0=0 0 0280 0 280 0 0+0=0 0 0520 0 520 0 0+63=63* 63 01 200 46 46+0=46760 0 760 0 0+63=63 109 11 440 46 46+63=109*2 120 92 92+0=921000 0 1000 0 0+126=126 138 31 680 46 46+63=1082 360 92 92+0=923 40 138 138+0=138* x 2 f2(x2) d2*40 0 0280 0 0520 63 0760 109

56、 11000 138 3f2(x2) x3 f3(x3) d3*40 0 0120 0 0200 0 0280 0 0360 0 0440 63 1520 63 1680 63 1760 63 11000 126 2 x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) d1*1000 0 1000 0 0+138=138 144 11 760 35 35+109=144*2 520 70 70+63=1333 280 105 105+0=1054 40 140 140+0=140*最 优 解 为 ：x1=1000， d1*=1， x2=x1-240d1*=760， d2*=1x 3=x2-320d2*=440， d3*=1， x4=x3-430d3*=10f1(x1)=f1(1000)=144即 货 物 A、 B、 C各 装 1件 ， 最 大 价 值 为 144万 元 。 货 轮 装 载 量 还 剩 余 10吨 。 x2 f2(x2) d2*40 0 0280 0 0520 63 0760 109 11000 138 3x 1 f1(x1) d1*1000 144 1