管理运筹学课件第9章-动态规划.ppt

第9章动态规划 管理运筹学课件 2 2020 4 1 教学目标与要求 教学目标 1 理解下列基本概念 状态变量 决策变量 策略 状态转移方程 指标函数和最优值函数2 理解动态规划的基本方程和最优化原理3 理解动态规划模型建立过程5 掌握顺序算法与逆序算法解题方法 知识结构 管理运筹学课件 3 2020 4 1 引例 马车驿站问题 E E D1D2 D1D2 D1D2 D1D2 C2C3C4 C1C2C3 1 D1 E 1 D2 E 2 C4 D1C4 D2 2 C3 D1C3 D2 2 C2 D1C2 D2 2 C1 D1C1 D2 3 B2 C2B2 C3B2 C4 3 B1 C1B1 C2B1 C3 B1B2 2 A B1A B2 A 一共有2 3 2 1 12条不同的路线 f E 0 f D1 2 f D2 1 f C1 8 f C2 5 f C3 4 f C1 5 f B1 8 f B2 11 f A 13 回顾分析过程 1 将分析对象划分成4阶段 2 每阶段始点状态与终点状态有关 而不考虑始终点状态如何形成 无记忆性 3 每阶段各始点状态为终点状态与始点至终点距离之和的最小值 状态转移 这种最优化方法称为动态规划 由美国数学家贝尔曼等人于20世纪50年代创立 管理运筹学课件 4 2020 4 1 本章主要内容 9 1动态规划的概念和原理9 1 1动态规划的基本概念9 1 2动态规划的最优化原理9 2动态规划的模型和求解9 2 1动态规划模型的建立9 2 2动态规划问题的解法9 3应用举例案例1资源分配问题案例2设备负荷问题案例3生产库存问题案例4背包问题本章小结 管理运筹学课件 5 2020 4 1 9 1 1动态规划的基本概念 1 阶段 把所给问题的过程 恰当地分为若干个相互联系的阶段 以便能按一定的次序去求解 描述阶段的变量称为阶段变量 常用k表示 导入案例 中k 1 2 3 4 2 状态变量 每个阶段开始所处的自然状况或客观条件 用点集表示 如引例 第1阶段的状态就是起点A 记为s1 A 第2阶段有2个状态 B1 B2 记为s2 B1 B2 第3阶段有4个状态 C1 C2 C3 C4 记为s3 C1 C2 C3 C4 第4阶段有2个状态 D1 D2 记为s4 D1 D2 3 决策变量 在某一阶段的某个状态时的不同选择 如引例中B1状态下有3种选择 B1 C1 B1 C2 B1 C3这3种选择构成了允许决策的集合 不同状态下允许决策的集合也不同 故决策变量是状态变量的函数 即xk sk D sk 4 策略按顺序排列的决策组成的集合 由过程的第k阶段开始到终止状态为止的过程 或k子过程 k子过程的策略称子策略 记为Pk n sk 即Pk n sk xk sk xk 1 sk 1 xn sn 当k 1时 即为全过程的一个策略 如引例中 D E 即4到5过程起始有2个状态 D1和D2 因此有P4 5 D1 E D2 E 5 状态转移方程确定过程是由一个状态到另一个状态的演变过程 第k阶段状态变量值给定后 如果确定决策变量 第k 1阶段状态变量值就完全确定 即 sk 1 T sk xk 如引例中 若对A B1 A B2选择了A B1 则s2 5 B1到C有3种选择 B1 C1 B1 C2 B1 C3 若选择了B1 C2 则s3 s2 d B1 C2 8 6 指标函数用来衡量所实现过程优劣的一种数量指标 其基本方程有加法和乘法两种形式 通常加法形式用的较多 其公式为 7 边界条件起始或终止条件 管理运筹学课件 6 2020 4 1 5 1 2动态规划的基本原理 最优化原理 Optimalityprinciple 最优策略具备这样的性质 无论初始状态与初始决策如何 以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言 必然构成最优策策略 通俗地说 最优策略的子策略也是最优的 例如 在导入案例中 最优策略是A B1 C2 D1 E 最短距离为13 其子策略 B1 C2 D1 E C2 D1 E D1 E也是最优的 依据这一原理 从后往前推各阶段最优子过程 从而得到全程最优过程 设f i 表示从点i到终点E的最短距离 d i j 表示点i j之间的距离 显然f E 0 为该问题的边界条件 k 4 决策 D1 E k 3 决策 D2 E 决策 C1 D1 决策 C2 D1 k 2 决策 C3 D2 决策 C4 D2 决策 B1 C2 决策 B2 C3 k 1 决策 A B1 最短路线 A B1 C2 D1 E最短路长 13 管理运筹学课件 7 2020 4 1 5 1 2动态规划的最优化原理 管理运筹学课件 8 2020 4 1 9 2 1动态规划模型的建立 解把生产第k种产品看成是第k阶段 划分为n个阶段 设sk表示第k阶段初资源可用量 状态变量 xk表示分配给第k阶段资源的数量 决策变量 显然有 允许决策集合sk 1 sk xk 状态转移方程 s1 a 边界条件 指标函数 若fk sk 表示数量为sk资源分配给第k种产品时 从第k阶段到第n阶段总收益 则有 管理运筹学课件 9 2020 4 1 9 2 1动态规划模型的建立 指标函数通常有两种形式 加法形式和乘法形式 管理运筹学课件 10 2020 4 1 9 2 2动态规划问题的解法 逆序法 最优值函数f k 从k阶段到E的最短距离 阶段指标函数 即该阶段选择不同路线的距离 从后向前推 S1 A S2 B1 B2 S3 C1 C2 C3 C4 S4 D1 D2 S5 E f5 E 0同理f4 D1 2 f4 D2 1同理f3 C2 5 f3 C3 4 f3 c4 5同理f2 B2 11 管理运筹学课件 11 2020 4 1 9 2 2动态规划问题的解法 顺序法 最优值函数f k 从A到k阶段的最短距离 阶段指标函数 即该阶段选择不同路线的距离 从前向后推 S0 A S1 B1 B2 S2 C1 C2 C3 C4 S3 D1 D2 S4 E 最优值函数 f0 A 0f1 B1 5 f2 B2 3f2 C1 7 f3 C2 8 f3 C3 10 f3 c4 9f3 D1 11 f4 D2 13 管理运筹学课件 12 2020 4 1 案例1资源分配问题 5台设备分配给3个工厂 盈利表如下 如何分配可使获利最大 分析3个工厂看成3个阶段 阶段变量k k 1 2 3 状态变量sk表示为分配给第k个工厂至第n个工厂的设备台数 决策变量xk表示分配给第k个工厂的设备台数 则有sk 1 sk xk Pk xk 表示为xk台设备分配到第k个工厂所得赢利值 fk sk 表示为台设备分配给第k个工厂至第n个工厂所得到的最大赢利值 则有 k 3 k 2 k 1 方案一 1 2 2 方案二 2 1 2 方案三 2 2 1 方案四 3 2 0 管理运筹学课件 14 2020 4 1 案例2设备负荷问题 某种机器可在高低两种不同的负荷下进行生产 设机器在高负荷下生产的产量函数为g 9x 其中x为投入生产的机器数量 季度完好率为a 0 65 在低负荷下生产的产量函数为h 4y 其中y为投入生产的机器数量 季度完好率为b 0 95 设资源拥有量100 解4季度看成4阶段sk第k季初拥有完好机器数xk第k季分配给高负荷机器数 则低负荷分配数sk xk下季度初完好机器数sk 1 0 65xk 0 95 sk xk 第k季产量vk 6xk 4 sk xk 管理运筹学课件 15 2020 4 1 k 4 f4是x4的增函数 故最大值解为x4 s4 相应地有f4 s4 9s4 k 3 f3是x3的增函数 故最大值解为x3 s3 相应地有f3 s3 14 85s3 管理运筹学课件 16 2020 4 1 k 2 f2是x2的增函数 故最大值解为x2 s2 相应地有f2 s2 18 6525s2 k 1 f1是x1的减函数 故最大值解为x1 0 相应地有f1 s1 21 719875s1 2172 反向推算 由s1 100 x1 0 知s2 95 x2 95 s3 61 75 x3 61 75 s4 40 14 x4 40 14 s5 26 09 即第1季度设备100 全部分配给低负荷 第2季度初完好设备为95 全部分配给高负荷 第3季度完好设备为61 75 全部分配给高负荷 第4季度完好设备为40 14 全部分配给高负荷 全年结束后 设备完好率为26 09 最大产量2172 管理运筹学课件 17 2020 4 1 Lingo程序 model sets JD 1 4 s x v 定义状态变量 决策变量和指标函数 ZB 1 5 f 定义最优值函数 endsetsf 5 0 初始化最优值函数 s 1 100 初始化状态变量 for jd x s 决策变量取值限制 for jd k k lt 4 s k 1 0 65 x k 0 95 s k x k 状态转移方程 for jd k v k 9 x k 4 s k x k 指标函数表达式 for zb k k lt 5 f k v k f k 1 基本方程 max f 1 目标 end 管理运筹学课件 18 2020 4 1 案例3生产库存问题 管理运筹学课件 19 2020 4 1 案例3生产库存问题 管理运筹学课件 20 2020 4 1 案例3生产库存问题 管理运筹学课件 21 2020 4 1 案例3生产库存问题 逆推 f5 26 5 s5 0 x5 0或3 s4 3 x4 6 s4 0 x4 0 s3 1 s3 4 x3 0或3 x3 6 s2 3 s2 0 s2 0 x2 6 x2 0 x2 0 s1 0 x1 2 s1 3 x1 5 s1 3 x1 5 管理运筹学课件 22 2020 4 1 案例4背包问题 管理运筹学课件 23 2020 4 1 案例4背包问题 管理运筹学课件 24 2020 4 1 案例4背包问题 最优方案 依次装2 1 0个最大价值 13 管理运筹学课件 25 2020 4 1 本章小结 本章介绍了动态规划的基本概念 基本原理和几种典型的应用问题 要求1 理解动态规划的核心概念状态与状态变量 决策与决策变量 策略 状态转移方程 指标函数和最优值函数 2 理解动态规划的最优化原理