运筹学：第8章 动态规划

1、2021/4/19,1,运筹学OPERATIONS RESEARCH,2021/4/19,2,第八章 动态规划,多阶段决策最优化问题举例 基本概念、基本方程与最优化原理 离散确定性动态规划求解 离散随机性动态规划求解 一般数学规划模型的动态规划解法,2021/4/19,3,1多阶段决策过程最优化问题举例,例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E 的最短路径。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,2021/4/19,4,用穷举法的计算量:

2、如果从A到E的站点有k个，除A、E之外每站有3个位 置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法 以及3k-12-1次比较。随着 k 的值增加时，需要 进行的加法和比较的次数将迅速增加； 例如 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。 若用1亿次/秒的计算机计算需要约508天。,2021/4/19,5,讨论： 1、以上求从A到E的最短路径问题，可以转化为四个 性质完全相同，但规模较小的子问题，即分别从 Di 、Ci、Bi、A到E的最短路径问题。 第四阶段：两个始点D1和D2，终

3、点只有一个； 表-1 分析得知：从D1和D2到E的最短路径唯一。,2021/4/19,6,第三阶段：有三个始点C1，C2，C3，终点有D1，D2， 对始点和终点进行分析和讨论分别求C1，C2，C3到 D1，D2 的最短路径问题： 表-2 分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。,2021/4/19,7,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 表-3 分析得知：如果经过B1，则走B1-

4、C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。,2021/4/19,8,第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对 始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的 最短路径问题： 表10-4 最后，可以得到： 从A到E的最短路径为A B4 C3 D1 E,2021/4/19,9,以上计算过程及结果，可用图2表示，可以看到，以 上方法不仅得到了从A到D的最短路径，同时，也得 到了从图中任一点到E的最短路径。 以上过程，仅用了22次加法，计算效率远高于穷举 法。,B,C,B

5、,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,2021/4/19,10,例2 资源分配问题 设有某种机器数台，用于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的；A、B两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最大? 假设第k年年初完好机器数是SK，用于A生产的机器数是XK，则用于B生产的机器数是（SK- XK）； 用于A工作的设备的完好率是：a%，用于B工作的设备

6、的完好率是：b%。则下一年初的完好机器数是 SK+1= a% XK+ b% （SK- XK） 第k年的收益： h(XK)+ g(SK- XK),2021/4/19,11,例3 背包问题 设有n种物品，每一种物品数量无限。第i种物品每 件重量为wi公斤，每件价值ci元。现有一只可装载重 量为W公斤的背包，求各种物品应各取多少件放入背 包，使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第I 种物品装入背包的件数（i =1, 2, , n），背包 中物品的总价值为z，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2,

7、, xn0 且为整数。,2021/4/19,12,动态规划是用来解决多阶段决策过程最优化的一种方法。 多阶段决策：是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态相互联系 而又相互区别的各个阶段； 每个阶段都要进行决策,目的是使整个过程的决策达到最优效果 多阶段决策求解思路： 将多阶段决策问题（n阶段）分解成n个具有递推关系的单阶段决策问题，进行正推或逆推计算。,2021/4/19,13,2.1 基本概念 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。(顺序编号法、逆序编号法） 2、状态sk：反应前一阶段决策的结果，又是本阶段作决策的依据和出发点（能确定

8、地表示决策过程当前特征的量）。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。,2基本概念、基本方程与最优化原理,2021/4/19,14,3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体 4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。,2021/4/19,15,5、状态转移方程: Sk+1=Tk(Sk, Xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,6、阶段指标函数Vk(Sk, Xk)：从

9、状态Sk出发，选择决策Xk所产生的第k阶段指标。 过程指标函数Vk,n(Sk；Xk, Xk+1, Xn)：从状态Sk出发，选择决策Xk, Xk+1, , Xn所产生的过程指标。,2021/4/19,16,动态规划要求过程指标具有可分离性，即 Vk,n(sk, xk, xk+1, , xn) = Vk(sk, xk)+Vk+1(sk+1, xk+1, , xn) 称指标具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn) 称指标具有可乘性。 2.2 基本方程 最优指标函数fk(sk)：从状态sk出发，对所有的策略P

10、k,n，过程指标Vk,n的最优值，即,2021/4/19,17,对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。 对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。,2021/4/19,18,2.3 最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是

11、最优的。,2021/4/19,19,例1 某警卫部门共有9支巡逻队，负责三个要害部位A、B、C的警卫巡逻。每个部位分别可派出24支巡逻队，并且由于派出的队伍数量不同，各部位预期的损失有差别，详见下表。各部位应各分派多少支巡逻队可是预期的总损失最小。请用动态规划方法求解。,3离散确定性动态规划模型求解,部位,巡逻队数,2021/4/19,20,解：设将向三个部位A，B，C派巡逻队作为三个阶段，K=1， 2，3。 决策变量 表示向第K个部位派遣的巡逻队数。 状态变量 表示第K个阶段时可供派遣的巡逻队数量。 状态转移方程： 阶段指标函数： 派遣 支巡逻队时第K阶段产生的预期损失； 过程指标函数： 第

12、K阶段到第3阶段的预期损失。 最优指标函数：,2021/4/19,21,逆序解法：边界条件 当K=3时，给C派巡逻队， ，,2021/4/19,22,当K=2时，给B派巡逻队，,2021/4/19,23,当K=1时，给A派巡逻队，,最优方案： A派3支巡逻队，B派4支巡逻队，C派2支巡逻队； 或：A派4支巡逻队，B派3支巡逻队，C派2支巡逻队,2021/4/19,24,解2：顺序解法 设将向三个部位A，B，C派巡逻队作为三个阶段，K=1，2，3。 决策变量 表示向第K个部位派遣的巡逻队数。 状态变量 表示前K-1个阶段可派遣的巡逻队数量。 状态转移方程： ， 阶段指标函数： 派遣 支巡逻队时第

13、K阶段产生的预期损失； 最优指标函数：前K个阶段的最优目标,2021/4/19,25,顺序解法： 边界条件 当K=1时，给A派巡逻队， ，,2021/4/19,26,当K=2时，给B派巡逻队，,2021/4/19,27,当K=3时，给C派巡逻队，,最优方案： A派3支巡逻队，B派4支巡逻队，C派2支巡逻队； 或：A派4支巡逻队，B派3支巡逻队，C派2支巡逻队,2021/4/19,28,例2 资源分配问题 (P208例5） 假设第k年年初完好机器数是SK，用于A生产的机器数是XK，则用于B生产的机器数是（SK - XK）； 用于A工作的设备的完好率是： ，用于B工作的设备的完好率是：0.9。则下

14、一年初的完好机器数是 SK+1= XK+0.9（SK- XK） 第k年的收益： 10XK+ 7(SK- XK),边界条件：,2021/4/19,29,逆序解法：边界条件 当K=3时，第三年初分配机器 台生产A， 台生产B ，,当K=2时，第二年初分配机器 台生产A， 台生产B，,2021/4/19,30,当K=1时，第1年初分配机器 台生产A， 台生产B ，,最优方案： 第一年所有机器100台用于生产B， 第二年初完好机器90台； 第二年所有机器90台用于生产A， 第三年初完好机器60台； 第三年所有机器60台用于生产A， 第四年初完好机器40台。,2021/4/19,31,4离散随机动态规划

15、模型求解,随机动态规划：状态转移规律不定，在给定的状态和决策下，下一阶段到达的状态是具有确定概率分布的随机变量。,第k+1阶段 可能状态,Pi：在决策Xk下出现状态i的概率,Ci：在决策Xk下出现状态i时的指标函数,2021/4/19,32,随机动态规划中，对指标函数进行优化时，要根据各阶段的期望效益进行优化。 基本方程改写为：,例：P210，例6 解：阶段变量K， 每月投产一批作为一个阶段，K=1，2，3。 状态变量 ：表示第K阶段所拥有的合格样品数，有两种可能状态。 表示有一台以上的合格品； 表示没有一台合格品。,2021/4/19,33,决策变量 ：表示第K个阶段决定投产的数量。,状态转

16、移律：,阶段指标函数：,最优指标函数 ：表示第K阶段在 状态下， 做决策 时，到最后一个阶段的最小期望费用。,2021/4/19,34,易知：,2021/4/19,35,逆序解法：边界条件 当K=3时，第三阶段之后的最小期望费用,2021/4/19,36,当K=2时，第二阶段之后的最小期望费用,2021/4/19,37,当K=1时，第一阶段之后的最小期望费用,最优方案： 第一期投产3台；第二期投产3台；第三期投产4台。最小期望费用796。,2021/4/19,38,5一般数学规划模型的动态规划解法,用动态规划的方法求解一般数学规划模型思想： 将取定每个变量的值作为一个阶段，则有n个变量的数学规划问题，可看作是有n 个阶段的多阶