动态规划模型举例.ppt

1 27 2020 1 6动态规划模型举例 1 27 2020 2 以上讨论的优化问题大多数属于静态的 即不必考虑时间的变化 建立的模型 线性规划 非线性规划 整数规划等 都属于静态规划 多阶段决策属于动态优化问题 即在每个阶段 通常以时间或空间为标志 要根据过程的演变情况确定一个决策 使全过程的某个指标达到最优 例如 1 化工生产过程中包含一系列的过程设备 如反应器 蒸馏塔 吸收器等 前一设备的输出为后一设备的输入 因此 应该如何控制生产过程中各个设备的输入和输出 使总产量最大 2 发射一枚导弹去击中运动的目标 由于目标的行动是不断改变的 因此应当如何根据目标运动的情况 不断地决定导弹飞行的方向和速度 使之最快地命中目标 1 27 2020 3 3 汽车刚买来时故障少 耗油低 出车时间长 处理价值和经济效益高 随着使用时间的增加则变得故障多 油耗高 维修费用增加 经济效益差 使用时间俞长 处理价值也俞低 另外 每次更新都要付出更新费用 因此 应当如何决定它的使用年限 使总的效益最佳 动态规划模型是解决这类问题的有力工具 下面结合具体例子阐述建立动态规划模型的思路 例13最短路问题 图2是一个线路网 连线上的数字表示两点之间的距离 或费用 寻找一条由A到G的路线 使距离最短 或费用最省 1 27 2020 4 解 用穷举法当然可以解决这个问题 不难算出 一共有48条从A到G的路线 用加法得到每条路线的长度后 再作比较即可找出最短路线 显然当路段很多时 计算工作量将是很大的 图 1 27 2020 5 用动态规划解决问题的思路 来源于生活中这样一个基本常识 如果已经找到由A到G的最短路线是A B1 C2 D1 E2 F2 G 图中粗线 记作L 那么当寻求L中的任何一点 如D1 到G的最短路时 它必然是L中的子路D1 E2 F2 G 记作L1 因为否则 若D1到G的最短路是另一条路线L2 则把A B1 C2 D1与L2连接起来 就会得到一条不同于L的从A到G的最短路 根据最短路的这一特性 我们可以从最后一段开始 用逐步向前递推的方法 依次求出路段上各点到G的最短路 最后得到A到G的最短路 1 27 2020 6 具体实施如下 从A到G要走6个路段 是一个6阶段决策问题 记k 1 2 6 用dk xk xk 1 表示第k段的点xk与第k 1段的点xk 1之间的 已知 距离 视k的不同 x分别代表A B F 用uk xk 表示在xk的决策 即从xk向哪一点走 则xk 1可以记作xk 1 uk xk 设xk到终点G的最短距离为fk xk 则k 6时 f F1 4 f F2 3 显然u F1 G u F2 G k 5时 f5 E1 min min 7表明E1到G的最短路是E1 F1 G 即E1的最优决策为u E1 1 27 2020 7 表明E2到G的最短路是E2 F2 G 即E2的最优决策为u5 E2 F2 同法计算出f5 E3 9 u5 E3 F2 1 27 2020 8 k 3时 k 2时 f2 B1 13 u2 B1 C2f2 B2 16 u2 B2 C3k 1时 f1 A 18 u1 A B1 于是从A到G的最短距离为f1 A 18 而最短路线则由A开始顺次找出最优决策来确定 即u1 A B1 u2 B1 C2 u3 C2 D1 u4 D1 E2 u5 E2 F2 u6 F2 G 最短路线为A B1 C2 D1 E2 F2 G 1 27 2020 9 不难看出 上述计算过程可以表示为如下的一般形式 1 其中D x 表示在x的允许决策集合 如D2 B1 C1 C2 C3 X表示第k段的允许状态集合 如X2 B1 B2 当按 1 式由k 6逆推至k 1时 就得到了最短距离 而最短路线由顺推的最优决策确定 在动态规划中f x 称最优值函数 1 式称最优方程 1 27 2020 10 需要指出 上例只是最短路问题的一种形式 实际问题中可以有多种形式 如 1 路线数目不定 如图3 求任一点 如B 到E的最短路线 不论它由几段组成 2 有向路网 如图4 求V1到V6的有向最短路 3 旅行商问题 如图3 求从A点出发 经每点一次又回到A点的最短路 图 图 1 27 2020 11 下面介绍动态规划相关的基本概念及其数学描述 1 阶段整个问题的解决可分为若干个相互联系的阶段依次进行 通常按时间或空间划分阶段 描述阶段的变量称为阶段变量 记为 2 状态状态表示每个阶段开始时所处的自然状况或客观条件 它描述了研究过程的状况 各阶段的状态通常用状态变量描述 常用表示第阶段的状态变量 个阶段的决策过程有个状态 用动态规划方法解决多阶段决策问题时 要求整个过程具有无后效性 即 如果某阶段的状态给定 则此阶段以后过程的发展不受以前状态的影响 未来状态只依赖于当前状态 1 27 2020 12 3 决策某一阶段的状态确定后 可以作出各种选择从而演变到下一阶段某一状态 这种选择手段称为决策 描述决策的变量称为决策变量 决策变量限制的取值范围称为允许决策集合 用表示第阶段处于状态时的决策变量 它是的函数 用表示的允许决策集合 4 策略一个由每个阶段的决策按顺序排列组成的集合称为策略 由第阶段的状态开始到终止状态的后部子过程的策略记为在实际问题中 可供选择的策略有一定范围 称为允许策略集合 其中达到最优效果的策略称为最优策略 1 27 2020 13 5 状态转移方程如果第个阶段状态变量为 作出的决策为 那么第阶段的状态变量也被完全确定 用状态转移方程表示这种演变规律 写作 6 最优值函数指标函数是系统执行某一策略所产生结果的数量表示 是用来衡量策略优劣的数量指标 它定义在全过程和所有后部子过程上 指标函数的最优值称为最优值函数 1 27 2020 14 下面方程在动态规划逆序求解中起着本质的作用 称此为动态规划逆序求解的基本方程 贝尔曼方程 可以把建立动态规划模型归纳成以下几个步骤 1 将问题恰当地划分为若干个阶段 2 正确选择状态变量 使它既能描述过程的演变 又满足无后效性 3 规定决策变量 确定每个阶段的允许决策集合 4 写出状态转移方程 5 确定各阶段各种决策的阶段指标 列出计算各阶段最优后部策略指标的基本方程 1 27 2020 15 例14生产计划问题 公司要对某产品制定n周的生产计划 产品每周的需求量 生产和贮存费用 生产能力的限制 初始库存量等都是已知的 试在满足需求的条件下 确定每周的生产量 使n周的总费用最少 解 决策变量是第k周的生产量 记作uk k 1 2 n 已知下列数据及函数关系 第k周的需求量dk 第k周产量为uk时的生产费ck uk 第k周初贮存量为xk时这一周的贮存费hk xk 第k周的生产能力限制Uk 初始 k 0 及终结 k n 时贮存量均为零 按照最短路问题的思路 设从第k周初贮存量为x到 n周末 过程结 1 27 2020 16 束的最小费用函数为f x 则下列逆向递推公式成立 1 而xk与xk 1满足 2 这里贮存量x是状态变量 2 式给出了相邻阶段的状态在决策变量作用下的转移规律 称为状态转移规律 在用 1 式计算时 xk的取值范围 允许状态集合Xk由 2 式及允许决策集合 0 uk Uk 决定 1 27 2020 17 在实际问题中 为简单起见 生产费用常ck uk 0 uk 0 ck uk a cuk uk 0 其中c是单位产品生产费 而a是生产准备费 贮存费用常取hk xk hxk h是单位产品 一周的 贮存费 最优方程 1 和状态转移方程 2 构成了这个多阶段决策问题的动态规划模型 实际上 多阶段决策问题有时也可用静态规划方法求解 如例2的生产计划问题 例15资源分配问题 总量为m1的资源A和总量为m2的资源B同时分配给n个用户 已知第k用户利用数量uk的资源A和数量v的资源B时 产生的效益为gk uk vk 问 1 27 2020 18 如何分配现有资源使总效益最大 解 这本来是个典型的静态规划问题 MaxZ 1 s t 2 3 但是当gk比较复杂及n较大时 用非线性规划求解是困难的 特别是 若gk是用表格或图形给出而无解析表达式时 则难以求解 而这种情况下 将其转化为 1 27 2020 19 动态规划 是一种可行的方法 资源A B每分配给一个用户划分为一个阶段 分配给第k用户的数量是二维决策变量 uk vk 而把向第k用户分配之前 分配者手中掌握的资源数量作为二维状态变量 记作 xk yk 这样 状态转移方程应为 4 1 27 2020 20 最优值函数fk xk yk 定义为将数量xk ky的资源分配给第k至第n用户时能获得的最大效益 它满足最优方程 5 对于由 4 5 式构成的动态规划模型 不需要gk fk的解析表达式 完全可以求数值解 1 27 2020 21 例16系统可靠性问题 一个系统由若干部件串联而成 只要有一个部件故障 系统就不能正常运行 为提高系统的可靠性 每个部件都装置备用件 一旦原部件故障 备用件就自动进入系统 显然 备用件越多 系统可靠性越高 但费用也越大 那么在一定的总费用限制下 如何配置各部件的备用件 使系统的可靠性最高呢 设系统有n个部件 当部件k装置uk个备用件时 这个部件正常工作的概率为Pk uk 而每个备用件的费用为ck 另外设总费用不应超过C 1 27 2020 22 解 这个优化问题的目标函数是系统正常运行的概率 它等于n个串联部件正常工作的概率的乘积 约束条件是备用件费用之和不应超过C 决策变量是各部件的备用件数量 于是问题归结为MaxZ 1 s t 2 这个非线性规划转化为动态规划求解比较方便 1 27 2020 23 按照对n个部件装置备用件的次序划分阶段 决策变量仍为部件k的备用件数量uk 而状态变量选取装配部件k之前所容许使用的费用 记作xk 于是状态转移方程为Xk 1 xk ckuk 3 最优值函数 k xk 定义为状态xk下 由部件 到部件 组成的子系统的最大正常工作效率 它满足 k xk 4 uk uk 0 1 5 1 27 2020 24 注意 这个动态规划模型的最优方程 4 中 阶段指标p与最优值函数 k 1之间的关系是相乘 而不是例13 15中的相加 这是由 两事件之交的概率等于两事件概率之积 这一性质决定的 与此相应 最优值函数的初始条件 n 1 xn 1 等于1 例17任务均衡问题 一批任务由若干设备完成 问题是如何均衡地向每个设备分配各项任务 使这批任务尽早地完成 例如一高层 设N层 办公大楼有n部性能相同的电梯 为了在早高峰期间尽快地将乘客送到各层的办公室 决定各部电梯分段运行 即每部电梯服务一定的层段 假定根据统计资料 已知一部电梯从第i层次开始服务j层所需要的时间为tij 问如何安排这些电梯服务的层段 使送完全部乘客的时间最短 1 27 2020 25 解 按照由下而上安排电梯服务层次的序号划分阶段k 1 2 n 第k部电梯 即第k阶段 开始服务的层次为状态xk 它服务的层数为决策uk 满足xk 1 xk uk 1 当x i u j时 已知第k部电梯服务的时间为vk xk uk tij 因为对于第k l两部电梯而言 总的服务时间为max vk xk uk vl xl ul 所以最优值函数fk xk 即从第k部到第n部电梯总的最短服务时间 满足 2 3 Nk n 2 1 2 1 27 2020 26 3 这里我们假定每部电梯至少服务1层 且从第2层起开始服务 从上述例子可以看出 建立多阶段决策问题的动态规划模型的主要步骤为 划分阶段 定义状态和决策 建立状态转移规律 方程 确定允许状态集合和允许决策集合 定义最优值函数 列出最优方程 包括终端条件 其中如何选定状态是关键的一步 状态应能描述过程的特征 可以直接或间接观测 并且具有无后效性 即当某阶段的状态给定时 过程以后的演变与该阶段以前的状态无关 1 27 2020 27 应用动态规划方法求解多阶段决策问题分为两个步骤 第一是应用动态规划基本方程 逆序地求出条件最优目标函数值集合和条件最优决策集合 第二是顺序地求出最优决策序列 下面以一个例子加以说明 例18机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产 在高负荷下生产时 每台机器生产产品的年产量为7吨 年折损率a 0 7 即若年初完好的机器有u台 则年终完好的机器数为au台 在低负荷下生产时 每台机器生产产品的年产量为5吨 年折损率b 0 9 若开始时完好的机器数 1000台 要求制定一个三年计划 在每年开始时 决定如何重新分配在两种不同的负荷下生产的完好机器数 使在三年内产品的总产量达到最大 1 27 2020 28 解 设第年初完好的机器数为 分配给高负荷下生产的机器数为 即在低负荷下生产的机器数为 这里 可取非负实数 如 0 7表示第年度一台机器正常工作时间只占0 7 于是第 1年初完好的机器数第年度的产量设三年总产量为 则问题即求解下面的线性规划问题 1 27 2020 29 现用动态规划来解 本题要求的是已知第一年度初拥有的完好机器数 1000台 用最优方案到第三年度末这段期间的产品产量 将它记为 为此先求 已知第年度初拥有的完好机器数 用最优方案到第三年末这段期间的产品产量 将它记为 列出动态规划的基本方程是求解过程如下 1 1 27 2020 30 即得最优解 从而 2 即 得最优解 从而 3 即 得最优解 从而 已知 1000 则原问题的最优值为 1 27 2020 31 顺序求出原问题的最优解为即第一年度应把年初全部完好机器投入低负荷生产 后两年每年应把年初全部完好机器投入高负荷生产 这样所得的三年总产量最高 为15710吨