运筹学：05-动态规划

1、,动态规划,将货物从城市Q运到海港T，途中经过城市A、B、C，三个城市各有3、3、2个转运点，各点运费如图，求从Q到T的最优路线，使总运费最少。,最少费用运输问题,动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理 、 工程技术等方面的许多实际问题。,动态规划,动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。,动态规划,以“时间”角度可分成：

2、离散型和连续型 从信息确定与否可分成： 确定型和随机型 从目标函数的个数可分成： 单目标型和多目标型,动态规划模型的分类,多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,动态规划的基本原理,某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。,生产与存储问题,某公司现有资金Q亿元

3、，在今后5年内考虑给A、B、C、D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大。,投资决策问题,企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。,设备更新问题,现在某企业要决定一台设备未来8年的更新计划，已预测到第j年购买设备的价格为Kj，Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费用(j=1,28)，问应在哪年更新设备可使总费用最小。,设备更新问题,阶段 状态 决策和策略 状态转移 指标函数,动态规划的基本概念,如图是一个五座城

4、市的及其相连道路的交通图，线上的数字是对应的路长。问：应如何选择行驶路线，才能使从A、B、C、D各城市到E城市的行驶路程最短？,不定阶段最短路线问题,从图中可以看出，任意两座城市之间都有道路相通。我们把从一座城市直达另一座城市作为一个阶段。例从A城市到E城市的阶段数，少则一个，例从A城市直达E城市，多则无限（例从A城市通过其他B、C、D三城市循环到E城市）。为避免循环，加上约束条件：每个城市至多经过一次。,不定阶段最短路线问题,不定阶段最短路线问题,于是从A到达E的阶段数情形： 1、从A城市直达E城市，一个阶段。 2、从A城市通过其他B、C、D三城市之一到E城市，二个阶段。 3、从A城市通过其

5、他B、C、D三城市之二到E城市，三个阶段。 4、从A城市通过其他B、C、D三城市各一次到E城市，四个阶段。,不定阶段最短路线问题,不定阶段最短路线问题,W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。,最短上班路线问题,最短上班路线问题,将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用k表示阶段变量。,阶段（Stage）,上班路线问题：阶段,各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常

6、用sk表示第k阶段的状态变量，状态变量的取值集合称为状态集合，用Sk表示。,状态（State）,上班路线问题：状态集合,SA=A SB=B1, B2 SC=C1,C2,C3 SD=D1,D2,D3 SE=E1,E2,当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。,动态规划中的状态具有如下性质,当各段的状态确定以后，就可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量用dk(sk)表示，允许决策集合用

7、Dk(sk)表示。,决策和策略（Decision and Policy）,各个阶段决策确定后，整个问题的决策序列就构成一个策略，用 p1,n(d1,d2,dn) 表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用P表示。使整个问题达到最优效果的策略就是最优策略。,决策和策略（Decision and Policy）,状态B2决策变量dB(B2)取值：B2C2(2)，B2C3(1) 状态B2的决策集合：DB(B2)=B2C2(2)，B2C3(1) A到F的一个决策序列（策略）：PA,F=A,B1,C2,D2,E1,F,上班路线问题的决策、策略,动态规划中本阶段的状态往往是上一

8、阶段的决策结果。如果给定了第k段的状态Sk ，本阶段决策为dk(Sk) ，则第k+1段的状态Sk+1由公式： Sk+1=Tk（ Sk， dk）确定，称为状态转移方程。,状态转移方程,给定了第B阶段的状态B2，本阶段决策dk(Sk)是B2C3(1) 则第C阶段的状态SC ：SC=TB(B2, B2C3(1)=C3类似有： SC=TB(B1, B1C1(4)=C1,上班路线问题状态转移方程,用于衡量所选定策略优劣的数量指标称为指标函数。 阶段指标函数：vk(sk, dk(sk) 过程指标函数：fk(sk, pk(sk) 最优指标函数记为f*k(sk)。,指标函数,阶段指标函数：vB(sB,dB(s

9、B) ,当SB为B2，dB(B2)选择B2 C3，则该指标函数的取值是：vB(B2, dB(B2) = 1 过程指标函数：fB(sB,pB(sB)，当SB为B2时的取值与从B2到F的策略相关，其最优解f*B(B2)是策略为B2 C2 D2 E2 F的取值10。,上班路线问题状态转移方程,从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点E最短路线， 最后求出A点到E点的最短路线。,动态规划的基本思想,动态规划函数基本方程,机器负荷分配问题,设有 100 台同一规格的完好自动机床，每台机床全年在高负荷下工作可创利 9 万元，折损率为 0.75；在低负荷下工作可创利 6 万元，折损率

10、为 0.96。试拟定连续四年的分配计划，使总利润为最大。,机器负荷分配问题：动态模型,阶段：设k = 1，2，3，4 表示年度 状态：sk=第k年初（第 k-1 年末）拥有的全额机床当量台数（有效台年） 决策：xk = 第k年度分配于高负荷下工作的机床当量台数； 状态转移方程：sk+1=0.75xk+0.96(sk-xk)=0.96sk0.21xk 阶段指标函数：vk(sk,xk)=9xk+6(skxk)=3xk+6sk,最少费用运输问题,最少费用运输问题,最少费用运输问题,最少费用运输问题,最少费用运输问题,动态规划求解表,作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优的。,贝尔曼(Ba