企业运筹学--动态规划讲义bvuu.pptx

《企业运筹学--动态规划讲义bvuu.pptx》由会员分享，可在线阅读，更多相关《企业运筹学--动态规划讲义bvuu.pptx（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学动态规划动态规划的概念与模型l 静态决策 一次性决策l 动态决策 多阶段决策决策x1x2Zu输入 决策输出决策效应第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多段决策过程T1x1x2r1u1T2x3r2u2Tkxkxk+!rkukTnxnxn+1rnun n个决策子问题K 称为阶段变量xk描述k阶段初的状态，称为状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。具有无后效性的多段决策过程 Xk+1=Tk(xk,uk)系统从k阶段往后的决策只与k

2、阶段系统的状态xk有关,而与系统以前的决策无关，则称为具有无后效性的多段决策过程。T1x1x2r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1 rn(xn,un)un(xn)K 后部子过程多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1rn(xn,un)un(xn)动态规划模型Opt 表示求优Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合。Uk是 一 个 集 合，表 示k阶 段决 策 可 能 取 值 的 范

3、围，称 为决 策 允 许 集 合，一 般 来 说 对于 不 同 状 态，可 以 作 的 决 策的 范 围 是 不 同 的。因 此 决 策允许集合一般写为Uk(xk)。动态规划的建模 动态规划建模确定阶段与阶段变量明确状态变量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标。动态规划的建模确定阶段与阶段变量阶 段 的 划 分 一 般 是 按 照 决 策 进 行 的 时 间 或 空 间 上 的 先 后 顺序 划 分 的，阶 段 数 等 于 多 段 决 策 过 程 中 从 开 始 到 结 束 所 需要作出决策的数目，阶段变量用k表示。明确状态变量和状态可能集合。状 态

4、 变 量 必 须 包 含 在 给 定 的 阶 段 上 确 定 全 部 允 许 决 策 所 需要 的 信 息。状 态 变 量 的 确 定 决 定 了 整 个 决 策 过 程 是 不 是 具有 无 后 效 性，因 而 也 决 定 着 能 不 能 用 动 态 规 划 方 法 来 求 解。状 态 可 能 集 是 关 于 状 态 的 约 束 条 件，因 此 为 了 求 解 必 须 正确地确定状态可能集。动态规划的建模确定决策变量和决策允许集合。与 静 态 问 题 相 同，决 策 变 量 应 能 够 反 映 对 问 题 所 作 的 决 策，决 策 变 量 也 应 有 其 相 应 的 约 束 条 件，在 建

5、 模 时 应 明 确 决 策允许集合Uk(xk)。确定状态转移方程。系 统k阶 段 从 状 态xk出 发 作 了 决 策uk(xk)之 后 的 结 果 之 一 是系 统 状 态 的 转 移，这 一 结 果 直 接 影 响 系 统 往 后 的 决 策 过 程，因 此 必 须 明 确 状 态 的 转 移 过 程，即 根 据 问 题 的 内 在 关 系，明确xk+1=Tk(xk,uk)中的函数Tk（）。动态规划的建模明确阶段效应和目标。阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须明确rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的

6、，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。动态规划解的概念多 段 决 策 过 程 中 所 要 求 解 的 是，从 起 始 状 态x1开 始，进 行一系列的决策，使目标R 达到最优最优目标值 R*最优策略 使得目标达到最优的决策序列。最优路线 在采取最优策略时，系统从x1开始所经过的状态序列求解动态规划模型 找到最优策略、最优路线和最优目标值。动态规划最优性原理多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态

7、又是后一阶段的初始状态阶 段 最 优 决 策 不 能 只 从 本 阶 段 的 效 应 出 发，必 须 通 盘 考 虑，整体规划。阶 段k的 最 优 决 策 不 应 该 只 是 本 阶 段 效 应 的 最 优，而 必 须是 本 阶 段 及 其 所 有 后 续 阶 段 的 总 体 最 优，即 关 于 整 个k后部子过程的最优决策。动态规划最优性原理最优性原理“最 优 策 略 具 有 的 基 本 性 质 是：无 论 初 始 状 态 和 初 始 决策 如 何，对 于 前 面 决 策 所 造 成 的 某 一 状 态 而 言，下 余 的 决策序列必构成最优策略”。AMB动态规划最优性原理最优性原理的含意

8、最 优 策 略 的 任 何 一 部 分 子 策 略，也 是 相 应 初 始 状 态 的最优策略。每个最优策略只能由最优子策略构成。显 然，对 于 具 有 无 后 效 性 的 多 段 决 策 过 程 而 言，如 果 按 照k后 部 子 过 程 最 优 的 原 则 来 求 各 阶 段 状 态 的 最 优 决 策，那么 这 样 构 成 的 最 优 决 策 序 列 或 策 略 一 定 具 有 最 优 性 原 理 所提示的性质。贝尔曼函数贝尔曼函数fk(xk)：在 阶 段k从 初 始 状 态xk出 发，执 行 最 优 决 策 序 列 或 策略，到 达 过 程 终 点 时，整 个k-子 过 程 中 的 目

9、 标 函 数 取 值，称为条件最优目标函数，亦称贝尔曼函数。条件最优策略 多段决策过程的任一阶段状态xk的最优策略 处于条件xk时的最优策略。条件最优决策 构成条件最优策略的决策贝尔曼函数条件最优目标函数值fk(xk)执行条件最优策略时的目标函数值条件最优路线 执行条件最优策略时的阶段状态序列贝尔曼函数条件最优k-子策略 系统从xk出发，在k-后部子过程中的最优策略k-子过程条件最优目标函数 fk(xk)是从xk出发系统在k-后部子过程中的最优目标值，多段决策问题所求解的最优目标函数值 R*=opt f1(x1*)动态规划基本方程 fk(xk)与fk 1(xk 1)之间的递推关系动态规划方法的

10、依据是最优性原理动态规划基本方程设 在 阶 段k的 状 态xk执 行 了 任 意 选 定 决 策uk后 的 状 态 是xk+1=Tk(xk,uk)。这 时k-后 部 子 过 程 就 缩 小 为k+1 后 部 子 过 程。根 据 最 优 性 原 理，对k+1 后 部 子 过 程 应 采 取 最 优 策 略，由于无后效性，k后部子过程的目标函数值为 动态规划基本方程动态规划基本方程动态规划方法基本原理动态规划方法基本原理 rk(xk,uk)和xk+1=Tk(xk,uk)都是已知的函数求fk(xk)需要首先求关于xk的所有k+1 段状态xk+1的fk+1(xk+1)逆序地求出条件最优目标函数值集合和

11、条件最优决策集合状态xk+1是由前面阶段的状态决定的用 问 题 给 定 的 初 始 条 件，即 可 顺 序 地 求 出 整 个 多 段 决 策 问 题的最优目标函数值、最优策略和最优路线。动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n 时，动态规划基本方程是 边界条件k=n 时的动态规划基本方程成为 动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n 1时，动态规划的基本方程是所有的fn(xn)都已经求出，因此可以根据xn=Tn-1(xn-1,un-1)就阶段n-1 每个可能状态xn-1Xn-1求条件最优决策及相应的条件最

12、优目标函数值fn 1(xn 1)动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=1 时，动态规划的基本方程是所有的f2(x2)都已经求出，因此可以根据x2=T1(x1,u1)就阶段1每个可能状态x1X1求条件最优决策及相应的条件最优目标函数值f1(x1)动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合动态规划问题求解的一般步骤 顺序地求出最优目标值、最优策略和最优路线若x1已知，则阶段1的条件最优决策就是阶段1的关于整个过程的最优决策若x1未知 动态规划问题求解的一般步骤顺序地求出最优目标值、最优策略和最优路线 动态规划四大要素、

13、一个方程五个关键因素 四大要素、一个方程：状态变量及其可能集合决策变量及其允许集合状态转移方程阶段效应动态规划基本方程：动态规划应用举例-定步数问题例41 某 旅 行 者 希 望 从s 地 起 到t 地，其 间 的 道 路 系 统 如 图47所 示，图 上 圆 圈 表 示 途 径 的 地 方，称 为 节 点，连 结 两 地的 箭 线 表 示 道 路，其 上 的 数 字 表 示 该 段 道 路 长 度，箭 头 表示通行的方向。试求s 到t 的最短路。a dbetc fs9757845646547图4-7动态规划应用举例-定步数问题a dbetc fs9757845646547第一阶段 第二阶段

14、第三阶段划分阶段 k=1,2,3 代表三个阶段动态规划应用举例-定步数问题a dbetc fs9757845646547状态变量xk取为k 阶段所在地，则有：动态规划应用举例-定步数问题a dbetc fs9757845646547k 阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点。动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0对3阶段所有可能的状态X3=d,e,f 计算f3()如下动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计算如下t/t F3()U3()

15、def5+07+04+0574tttr3(x3,u3)+f4(x4)f3(x3)u3(x3)动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集a dbetc fs9757845646547475动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a,b,c 计算f2()如下动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a,b,c 计算f2()如下动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计算如下d/d e/e f/f F2()U2()abc7

16、+55+54+56+75+74+46+48109fddf2(x2)u2(x2)r2(x2,u2)+f3(x3)动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集a dbetc fs97578456465474759108动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对1阶段所有可能的状态X1=s 计算f1()如下a/a b/b c/c F2()U2()s 9+8 8+10 7+9 16 c动态规划应用举例-定步数问题顺序求最优策略、最优路线和最优目标函数值动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集a dbetc fs975784

17、5646547475910816动态规划应用举例-不定步数问题a cb ds t69 5 2448423图4-8例42 用f(i)表示I 节点到t 节点的最短距离，则根据动态规划原理，应该有：动态规划应用举例-不定步数问题a cb ds t69 5 2448423图4-8例42 可用迭代的方法来实现求解。迭代可以针对f()来进行，称为函数迭代法也可以针对策略u(i)(i=s,a,b,c,d)进行，称为策略迭代法不定步数问题-函数迭代法 函数迭代法步骤选定一初始函数f1(i)然后用递推关系求fk(i)fk(i)为 从i 点 出 发 走k 步 到t 的 最 短 距 离，若 对 于 某 个k，有fk

18、+1(i)=fk(i)，对 所 有 节 点i 成 立，则fk()即 为 条 件 最 优 目 标 函数，求解结束。否则重复上述过程，直至最优。不定步数问题-函数迭代法a cb ds t69 5 2448423图4-8例42 取不定步数问题-函数迭代法例42 不定步数问题-函数迭代法例42 s a b c d tf1()2 4 0f2()8 4 2 4 0f3()12 8 4 2 4 0f4()12 8 4 2 4 0不定步数问题-策略迭代法策略迭代法步骤：1 给每个点i 选择一个下一步到达的点u0(i)，i=s,a,b,c,d 取k=0 2 由 算出fk(i)3 由解出则已经最优,否则继续计算

19、若不定步数问题-策略迭代法a cb ds t69 5 2448423图4-8例42 取不定步数问题-策略迭代法例42 不定步数问题-策略迭代法a cb ds t69 5 2448423图4-8例42 不定步数问题-策略迭代法不定步数问题-策略迭代法x u0f0u1f1u2s a 18 b 12 ba d 9 c 8 cb d 8 c 4 cc t 2 t 2 td t 4 t 4 tt 0 0资源分配问题 资源的多元分配 设有某种资源，总量为M，可以投入n 种生产活动。已知用于活动k 的资源为uk时的收益是gk(uk)，问应如何分配资源，使n 种生产活动的总收益最大。这种问题就是资源的多元分配

20、问题。资源分配问题 资源的多元分配 如 果 将n 种 活 动 作 为 一 个 互 相 衔 接 的 整 体，对 一 种 活 动 的 资源 分 配 作 为 一 个 阶 段，每 个 阶 段 确 定 对 一 种 活 动 的 资 源 投放量。则该问题成为一个多段决策问题。状 态 变 量xk的 选 取 原 则 是 要 能 够 据 此 确 定 决 策uk，以 及 满 足状态转移方程所要求的无后效性。在 资 源 分 配 问 题 中，决 策 变 量 选 为 对 活 动k 的 资 源 投 放 量，因 此 状 态 变 量 可 以 选 择 为 阶 段k 初 所 拥 有 的 资 源 量，即 将 要在第k 种到第n 种活

21、动间分配的资源量。资源的多元分配 关于状态变量xk的约束条件是 0 xkM关于决策变量uk的约束条件是 0ukxk 状态转移方程为 xk+1=xk-uk 显然它满足无后效性要求。阶段效应为对活动k 投放资源uk时的收益，rk(xk,uk)=gk(uk)目标函数是为n 种活动投放资源后的总收益动态规划基本方程资源的多元分配 例43 某 公 司 拟 将50万 元 资 金 投 放 下 属A、B、C 三 个 部 门，各 部 门 在 获 得 资 金 后 的 收 益 如 表 所 示，用 动 态 规 划 方 法 求总收益最大的投资分配方案（投资数以10万元为单位）。投放资金（万元）0 10 20 30 40

22、 50收益（万元）A 0 15 20 25 28 30B 0 0 10 25 45 70C 0 10 20 30 40 50资源的多元分配 解 该 问 题 可 以 作 为 三 段 决 策 过 程。对A、B、C 三 个 部 门 分配 资 金 分 别 形 成1，2，3三 个 阶 段。xk表 示 给 部 门k 分 配 资金 时 拥 有 的 资 金 数。uk表 示 给 部 门k 分 配 的 资 金 数（以10万元 为 单 位）。状 态 转 移 方 程 是xk+1=xk-uk。阶 段 效 应 如 表 所示。目标函数是阶段效应求和。投放资金（万元）0 10 20 30 40 50收益（万元）A 0 15

23、20 25 28 30B 0 0 10 25 45 70C 0 10 20 30 40 50资源的多元分配 首先逆序求条件最优目标函数值集合和条件最优决策集合。从 表 可 知g3()是 单 调 递 增 的 函 数，因 此，当u3=x3时 达 到 最大。即：资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。x3g3f3U30 0 0 01 10 10 12 20 20 23 30 30 34 40 40 45 50 50 5资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。k=2 时，0 x25 0u2x

24、2 资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。k=2 时，0 x25 0u2x2 0/x21/x2-1 2/x2-2 3/x2-3 4/x2-4 5/x2-5 f2()U20 0+0 0 01 0+10 0+0 10 02 0+20 0+10 10+0 20 03 0+30 0+20 10+10 25+0 30 04 0+40 0+30 10+20 25+10 45+0 45 45 0+50 0+40 10+30 25+20 45+10 70+0 70 5资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。当k=1 时，有x1=5，0u1x1=5 资源的多元分

25、配 逆序求条件最优目标函数值集合和条件最优决策集合。当k=1 时，有x1=5，0u1x1=5 0/5 1/4 2/3 3/2 4/1 5/0 f1()U15 0+70 15+45 20+30 25+20 28+10 30+0 70 0资源的多元分配 顺序求最优目标函数值和最优策略、最优路线0/5 1/4 2/3 3/2 4/1 5/0 f1()U15 0+70 15+45 20+30 25+20 28+10 30+0 70 0资源的多段分配 将 一 种 有 消 耗 性 的 资 源，多 阶 段 地 在 多 种 不 同 的 生 产 活 动 中投 放 的 问 题 称 为 资 源 的 多 段 分 配

26、问 题，下 面 讨 论 其 中 包 含 有两个生产活动的简单情况。设 有 某 种 资 源，初 始 的 拥 有 量 是M。计 划 在A，B 两 个 生 产 部门 连 续 使 用n 个 阶 段。已 知 在 部 门A 投 入 资 源uA时 的 阶 段 收 益是g(uA)，在 部 门B 投 入 资 源uB时 的 阶 段 收 益 是h(uB)。又 资 源在 生 产 中 将 有 部 分 消 耗，已 知 每 生 产 一 个 阶 段 后 部 门A，B 中的 资 源 完 好 率 分 别 为a和b，0(a,b)1。求n 阶 段 间 总 收 益 最大的资源分配计划。资源的多段分配 n 段决策过程状态变量xk为阶段k

27、 初拥有的资源量，0 xkM，x1=M决 策 变 量 选 为 阶 段k 在 部 门A 的 资 源 投 放 量，即uA=uk，这 里 显然有uB=xk-uk，决策变量的约束条件是 0ukxk即最多将所拥有的资源都投入部门A，其时uB=0阶 段k 末 部 站A 的 剩 余 资 源auk，部 门B 中 则 为b(xk-uk)，因 此 状态转移方程xk+1=T(xk,uk)是 xk+1=auk+b(xk-uk)满足无后效性阶段效应rk(xk,uk)即阶段收益rk(xk,uk)=g(uk)+h(xk-uk)目标函数是n 个阶段的总收益，即阶段效应求和。资源的多段分配 例44 今 有1000台 机 床，要

28、 投 放 到A、B 两 个 生 产 部 门，计 划连 续 使 用3年。已 知 对A 部 门 投 入uA台 机 器 时 的 年 收 益 是g(uA)=4(uA)2（元），机 器 完 好 率a=0.5，相 应 的B 部 门 的 年 收 益 是h(uB)=2(uB)2（元），完 好 率b=0.9。试 求 使3年 间 总 收 益 最 大的年度机器分配方案。解 以 每 年 作 为 一 个 阶 段，设 状 态 变 量 和 决 策 变 量 都 是 连 续 取值 的。K 阶 段 状 态 变 量xk取 为 该 年 度 初 完 好 的 设 备 数，决 策 变量取为该年度投入A 活动的设备数，则有 0 xk1000

29、，0ukxk状态转移方程为：xk+1=0.5uk+0.9(xk-uk)资源的多段分配 例44解 以 每 年 作 为 一 个 阶 段，设 状 态 变 量 和 决 策 变 量 都 是 连 续 取值 的。K 阶 段 状 态 变 量xk取 为 该 年 度 初 完 好 的 设 备 数，决 策 变量取为该年度投入A 活动的设备数，则有 0 xk1000，0ukxk状态转移方程为：xk+1=0.5uk+0.9(xk-uk)动态规划基本方程资源的多段分配 逆序求条件最优目标函数值fk(xk)和条件最优决策k=3 时，0u3x3，注意到f4(x4)=0，有 k=2 时，0u2x2，有 资源的多段分配 逆序求条件

30、最优目标函数值fk(xk)和条件最优决策k=1 时，0u1x1，x2=0.5u1+0.9(x1-u1)，f2(x2)串联系统可靠性问题 系 统 可 靠 性 是 指 系 统 在 规 定 的 条 件 下 能 正 常 工 作 的 概 率，它 是 管 理 和 工 程技术设计中经常要研究的问题。这 儿 要 研 究 的 是 串 联 系 统 可 靠 性 问 题。例 如 某 种 仪 器 设 备 由N 个 部 件 串 联构成，凡其中有一个部件出现故障，则整个系统便不能正常工作。为 了 提 高 系 统 工 作 的 可 靠 性，一 种 方 法 是 可 以 在 每 个 部 件 上 装 有 主 要 元 件的相同性能的备

31、用件，并且带有备用元件自动投入装置。自 然 备 用 元 件 越 多，系 统 的 可 靠 性 越 高，但 也 会 相 应 增 加 系 统 重 量、体 积和费用，有时也会降低工作精度。因 此，在 成 本、重 量、体 积 等 一 定 的 条 件 限 制 下，应 如 何 选 择 各 部 件 的 备用元件数，使得整个系统的可靠性最大，就可以归结为一个动态规划问题。串联系统可靠性问题 例45 某 电 气 设 备 由 三 个 部 件 串 联 而 成，为 提 高 该 种 设 备 在 指 定 工 作 条件 下 正 常 工 作 的 可 靠 性，需 在 每 个 部 件 上 安 装 一 个、两 个 或 三 个 主 要

32、 元 件的 相 同 备 件。假 设 对 部 件i(i=1，2，3)配 备j 个 备 件 后 的 可 靠 性Rij和 所 需 费用cij均 已 知，如 表 所 示，若 可 用 的 总 资 金 数 量 为1万 元，问 如 何 配 备 各 部件的备用元件数，才能使该设备在给定工作条件下的可靠性最大？备件数部件j=1 j=2 j=3Ci1（千元)Ri1Ci2（千元）Ri2Ci3（千元）Ri31 1 0.90 3 0.94 5 0.962 3 0.75 5 0.88 6 0.973 2 0.80 3 0.92 4 0.99串联系统可靠性问题 例45 解 以 给 不 同 的 部 件 决 定 备 件 作 为

33、 不 同 的 阶 段，则 该问题是3阶段决策问题设 状 态 变 量xk表 示 从 第k 个 部 件 到 第3个 部 件 允 许 使 用 的 总 费用（k=1,2,3）决策变量uk为第k 部件配备的备用元件数（k=1，2，3）。则 据 题 意 有：x1=10 千 元，且 每 个 部 件 都 最 少 有 一 个 备 件，即uk1，若 令sk表 示 为 保 障 以 后 各 部 件 均 能 获 得 一 个 备 件 所 需 的资金数，则应有：串联系统可靠性问题 例45且据此可得：s1=6，s2=5，s3=2。从而可知：对uk有 即 当 期 所 耗 资 金 加 上k+1 期 往 后 所 用 资 金sk+1

34、不 超 过 当 前 拥 有资金数。串联系统可靠性问题 例45根 据 上 述 分 析 可 以 写 出 各 阶 段 的 状 态 可 能 集 合 和 决 策 允 许 集合如下：x1=10 X29，7，5 X32，3，4，5，6 U11，2，3U2(9)1，2，3 U2(7)1，2 U2(5)1 U3(2)1 U3(3)1，2 U3(4)1，2，3 U3(5)1，2，3 U3(6)1，2，3串联系统可靠性问题 例45状态转移方程为：阶段效应为 目标函数为是阶段效应乘积的形式 若以fk(xk)表示在阶段k 拥有资金xk时采用最优决策序列所得的k 阶段往后的系统的可靠性，则动态规划基本方程为：串联系统可靠

35、性问题 例451/x3-2 2/x3-3 3/x3-4 f3()U32 0.81 0.8 13 0.81 0.921 0.92 24 0.81 0.921 0.991 0.99 36 0.81 0.921 0.991 0.99 3串联系统可靠性问题 例451/x2-3 2/x2-5 3/x2-6 f2()U29 0.750.99 0.80.99 0.970.92 0.8924 37 0.750.99 0.80.8 0.7425 15 0.750.8 0.6 11/x3-2 2/x3-3 3/x3-4 f3()U32 0.81 0.8 13 0.81 0.921 0.92 24 0.81 0.9

36、21 0.991 0.99 36 0.81 0.921 0.991 0.99 3串联系统可靠性问题例451/x2-3 2/x2-5 3/x2-6 f2()U29 0.750.99 0.80.99 0.970.92 0.8924 37 0.750.99 0.80.8 0.7425 15 0.750.8 0.6 11/9 2/7 3/5 f1()U110 0.90.8924 0.940.7425 0.960.6 0.80316 1 生产库存问题 l 生产计划周期分为n个阶段，即k=1n；l 已知最初库存量为x1；l 阶段需求量为dk；l 单位产品的消耗费用为Lk；l 单位产品的阶段库存费用为hk；

37、l 仓库容量为Mk；l 阶段生产能力为Bk；l 生产的准备费用为：生产库存问题 问 应 如 何 安 排 各 阶 段 产 量，使 计 划 期 总 费 用 最 小。这 里 状 态 变 量xk应 选 为 阶 段k的 初 始 库 存 量，计 划初 期 的 库 存 量x1是 已 知 的，末 期 的 库 存 量 通 常 也 是给 定 的，为 简 单 起 见 这 里 假 定xn+1=0，于 是 问 题 是始端末端固定的问题。关于状态xk的约束条件是l 即阶段k的库存既不能超过库存容量，也不应超过阶段k至阶段n的需求总量（dk+dk+1+dn），否则将与xn+1=0 的假设相违背。库容量限制以后需求缺口本期需

38、求缺口生产库存问题 决 策 变 量uk选 为 阶 段k的 生 产 量。阶 段 产 量 要 在 不 超 过 生产 能 力Bk的 条 件 下，充 分 满 足 该 阶 段 的 需 求dk，同 时 还要 满 足 计 划 末 期 的 库 存 量 为0的 要 求。因 此 关 于 决 策 变量的约束条件就是 期末库存=期初库存+生产量-本期需求生产库存问题 阶段k的生产费用是 库存费用按阶段k末期的库存量xk+1计算 生产库存问题举例 l 例45 求 解 生 产 库 存 问 题。已 知 其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计 划 周 期 末 期的库存量为0），Bk6，d

39、1=3，d2=4，d3=3。生产库存问题举例 l 例45 求 解 生 产 库 存 问 题。已 知 其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计 划 周 期 末 期的库存量为0），Bk6，d1=3，d2=4，d3=3。生产库存问题举例 l 例45 求 解 生 产 库 存 问 题。已 知 其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计 划 周 期 末 期的库存量为0），Bk6，d1=3，d2=4，d3=3。生产库存问题举例 0 1 2 3 f3()U30 14 14 31 12 12 22 10 10 13 0 0 0生产库存问题举例

40、0 1 2 3 4 5 6 f2()U20 16+14 19.5+12 23+10 30 41 14+14 17.5+12 21+10 24.5+0 24.5 62 12+14 15.5+12 19+10 22.5+0 22.5 53 10+14 13.5+12 17+10 20.5+0 20.5 44 0+14 11.5+12 15+10 18.5+0 14 0生产库存问题举例 2 3 4 5 6 f!()u11 12+30 15.5+24.5 19+22.5 22.5+20.5 26+14 40 3或6生产库存问题举例 2 3 4 5 6 f!()u11 12+30 15.5+24.5 1

41、9+22.5 22.5+20.5 26+14 40 3或6二维背包问题 l 背 包 问 题 的 特 征 类 似 于 往 旅 行 背 包 里 面 装 用 品 的 问 题，要求 在 旅 行 袋 容 积 和 或 载 重 量 的 限 制 下，所 装 物 品 的 总 价值 最 大。这 一 类 问 题 在 海 运、航 运 以 及 航 天 等 领 域 都 有 应用。l 若 只 考 虑 重 量 或 体 积 限 制，则 称 为 一 维 背 包 问 题，若 同 时考虑重量和体积限制，则称为二维背包问题。l 考 虑 有N 种 物 品 需 要 装 船。第i 种 物 品 单 位 的 重 量 为i，单件 体 积 为i，而

42、 价 值 为pi。最 大 的 装 载 重 量 为W，最 大 体 积为V。现 在 要 确 定 在 不 超 过 船 的 最 大 载 重 量 和 最 大 体 积（不 考 虑 货 物 形 状）的 条 件 下，使 所 载 物 品 价 值 最 大 的 装载方案。二维背包问题 l 例46 已 知 货 物 的 单 位 重 量i，单 位 体 积i及 价值pi如 表 所 示，船 的 最 大 载 重 能 力 为W 5，最 大装载体积为V 8，求最优装载方案。i iipi1 1 2 302 3 4 803 2 3 65二维背包问题 l 例46 W5，V 8解 该 问 题 中 有 三 种 物 品 需 要 装 载，因 此

43、 可 以 作 为 三段决策问题，每阶段为一个物品决定装船的数量。k 阶 段 系 统 的 状 态 为 在 给 第k 物 品 决 定 装 载 数 量 时，船 上 还 剩 余 的 载 重 能 力xk和 剩 余 体 积yk，因 此 状 态变量是二维的，记为（xk,yk）。有0 xk5，0yk8决策变量uk表示装载第k 种物品的数量。二维背包问题 l 例46 W5，V 8解 状态转移方程为：xk+1=xk-ukk yk+1=yk-ukk阶段效应为 rk(xk,yk,uk)=pkuk各阶段的状态可能集与决策允许集为：二维背包问题 解 状态转移方程为：xk+1=xk-ukk yk+1=yk-ukk二维背包问

44、题 解 当k 3时，由f4(x4,y4)=0 0/(x3,y3)1/(x3-2,y3-3)2/(x3-4,y3-6)f3()u3（5，8）00 650 265 0 130 2（4，6）00 650 265 0 130 2（3，4）00 650 65 1（2，2）00 0 0（1，0）00 0 0（2，4）00 650 65 1（1，2）00 0 0（0，0）00 0 0二维背包问题 解 当k 2时，由f3(x3,y3)已知 0/(x2,y2)1/(x2-2,y2-4)f2()u2（5，8）0130 8065 145 1（4，6）0130 800 130 0（3，4）065 800 80 1（2

45、，2）00 0 0（1，0）00 0 0二维背包问题 解 当k 1时，W=5,V=8 0/(5,8)1/(4,6)2/(3,4)3/(2,2)4/(1,0)f1()u1（5，8）0145 30130 6080 900 1200 160 1设备更新问题 设备更新问题的一般提法随着使用年限的增加，设备性能会变差，故障会增加，需要维修或更新。设备使用时间愈长，积累效益愈高，但随着设备陈旧，维修使用费用也会提高，而且，设备使用年限愈久，处理价格愈低，更新费用也要增加。因此，处于某个阶段的各种设备，总是面临着保留还是更新的问题，这个问题应该从整个计划期间的总回收额，而不应从局部的某个阶段的回收额来考虑。

46、由于每个阶段都面临着保留还是更新的两种选择，因此，它是一个多阶段的决策过程，可以用动态规划方法求解。设备更新问题 今有一设备更新问题如下：已知 n为计算设备回收额的总期数；t 为某个阶段的设备役龄；(t)为从役龄为t 的设备得到的阶段收益；(t)为役龄为t 的设备的阶段使用费用；s(t)是役龄为t 的设备的处理价格；p为新设备的购置价格；求n期内使回收额最大的设备更新政策。设备更新问题 状态变量选为设备的役龄t，即xk=t，决策只有两种可能，即保留或更新，记为K（保留）或P（更新）。状态转移方程 相应的阶段效应即阶段的回收额也有两种可能设备更新问题 例47 假定n6年，新设备购买价格为10万元

47、。役龄为t 时的设备使用效益(t)，使用费用(t)和处理价格s(t)如下表所示 T 0 1 2 3 4 5 6(t)万元 27 26 26 24 22 20 18(t)万元 15 15 16 16 17 17 18s(t)万元 6 5 5 4 4 3 2设备更新问题 T 0 1 2 3 4 5 6(t)万元 27 26 26 24 22 20 18(t)万元 15 15 16 16 17 17 18s(t)万元 6 5 5 4 4 3 2(t)-(t)12 11 10 8 5 3 0s(t)+2 8 7 7 6 6 5 4设备更新问题 t 0 1 2 3 4 5 6(t)-(t)12 11 1

48、0 8 5 3 0s(t)+2 8 7 7 6 6 5 4t 0 1 2 3 4 5 6f6(t)12 11 10 8 6 5 4设备更新问题 t 0 1 2 3 4 5 6(t)-(t)12 11 10 8 5 3 0s(t)+2 8 7 7 6 6 5 4t 0 1 2 3 4 5 6f6(t)12 11 10 8 6 5 4f5(t)23 21 18 17 17 16 15(t)-(t)+f6(t+1)23 21 18 14 10 7s(t)+2+11 19 18 18 17 17 16 15设备更新问题 t 0 1 2 3 4 5 6(t)-(t)12 11 10 8 5 3 0s(t

49、)+2 8 7 7 6 6 5 4t 0 1 2 3 4 5 6f6(t)12 11 10 8 6 5 4f5(t)23 21 18 17 17 16 15(t)-(t)+f5(t+1)33 29 27 25 21 18s(t)+2+11 29 28 28 27 27 26 25设备更新问题 t 0 1 2 3 4 5 6f6(t)12 11 10 8 6 5 4f5(t)23 21 18 17 17 16 15f4(t)33 29 28 27 27 26 25f3(t)41 39 37 35 35 34 33f2(t)51 48 46 45 45 44 43f1(t)60 57 55 54 54 53 52第一年役龄为一的产品的更新方案设备更新问题 t 0 1 2 3 4 5 6f6(t)12 11 10 8 6 5 4f5(t)23 21 18 17 17 16 15f4(t)33 29 28 27 27 26 25f3(t)41 39 37 35 35 34 33f2(t)51 48 46 45 45 44 43f1(t)60 57 55 54 54 53 52第一年役龄为4的产品的更新方案习题 P177 4-5 4-6