《第七章运筹学动态规划》由会员分享，可在线阅读，更多相关《第七章运筹学动态规划（75页珍藏版）》请在金锄头文库上搜索。
1、第七章 动态规划最短路径问题资源分配问题生产计划与库存问题投资决策问题设备更新问题机器负荷分配问题1第五章 动态规划 动态规划Dynamic Programming 研究多阶段决策的最优化问题的方法。 多阶段决策问题含有一个描述过程时序过程时序或空间演变空间演变的阶段 变量，将复杂问题划分成若干阶段，根据“最优性原理”， 逐段解决而最终实现全局最优。 经济、管理、工业生产、工程技术等领域，许多问题可归 结为多阶段决策问题。 一些用线性规划、非线性规划处理有困难的问题，往往可 以用动态规划方便地求解。 动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提 出的。2贝尔曼贝尔曼( (
2、BallmanBallman) )最优化原理最优化原理作为整个过程的最优策略具有作为整个过程的最优策略具有 这样的性质，即无论过去的状态和这样的性质，即无论过去的状态和 决策如何，对前面的决策所形成的决策如何，对前面的决策所形成的 状态而言，余下的诸决策必须构成状态而言，余下的诸决策必须构成 最优策略。这就是说，不管引导到最优策略。这就是说，不管引导到 这个现时状态的头一个状态和决策这个现时状态的头一个状态和决策 是什么，所有的未来决策应是最优是什么，所有的未来决策应是最优 的。的。3第一节 多阶段决策过程的最优化 多阶段决策： 经济管理决策中，有些管理决策问题可以按时序时序或空间演空间演 变
3、变划分成多个阶段 ，呈现出明显的阶段性； 于是可把这类决策问题分解成几个相互联系的阶段，每个 阶段即为一个子问题； 原有问题的求解就化为逐个求解几个简单的阶段子问题； 每个阶段的决策一旦确定，整个决策过程也随之确定，此 类问题称为多阶段决策问题。 例如： 企业生产物流：可分为物料供应、生产制造、分销零售等 阶段。 最短路问题：可以按空间顺序划分阶段。一、 问题的提出 4第一节 多阶段决策过程的最优化 从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短) ？ 最短路问题 QTA1A2A3B1B2B3C1C12437 4 6 4 2 4 4 2 51 4633334生 产 商某 公 司出 口
4、 港进 口 港城 市阶段1阶段2阶段3阶段45第一节 多阶段决策过程的最优化 这是一个多阶段决策问题，它可分为四个阶段： 第一阶段：从Q(制造厂)到A(出口港)； 第二阶段：从A(出口港)到B(进口港)； 第三阶段：从B(进口港)到C(城市)； 第四阶段：从C(城市)到T(某公司)。 每个阶段选取的路线不同，对应从Q到T就有一系列不同 的运输路线: 从始点Q到终点T共有3321=18条不同路线 现在的问题是如何选择一条费用最小的路线？ 6第一节 多阶段决策过程的最优化 最短路的基本特征 从始点Q到终点T 的最短路径：Q A3 B1 C1T，则 从中点A3 到终点T 的最短路径必为： A3 B1
5、 C1T， 从中点B1 到终点T 的最短路径必为：B1 C1T，。 推广：从始点Q到终点T 的最短路径： Q S1 S2 Sk Sk+1 SnT，则 从中点Sk 到终点T 的最短路径必为： Sk Sk+1 SnT。三、 多阶段决策的基本特征 7第二节 动态规划的基本概念和基本原理 阶段(stage) 处理多阶段决策，需将全过程划为若干阶段，每个阶段进 行一次抉择。 各阶段按一定顺序联接在一起组成统一的整体。 用k表示阶段变量阶段变量。 阶段编号顺序编号逆序编号一、动态规划的基本概念 8第二节 动态规划的基本概念和基本原理 状态(state) 状态表示过程发展中某阶段的初始客观条件。 过程的发展
6、可以通过各阶段状态的演变来描述。 状态可用一个变量来描述，称为状态变量状态变量，用sk表示。 选取的状态变量必须满足无后效性无后效性。某阶段的状态给定后，则过程未来发展不受该阶段以前 各阶段状态的影响。 第 k 阶段可能有若干状态，用Sk 表示阶段k的状态集合， sk(i)表示第k阶段的第 i 个状态。9第二节 动态规划的基本概念和基本原理 决策(decision) 从上一阶段某状态演变到下一阶段某状态要作一次选择， 称为决策。 用变量uk(sk)表示第k阶段状态为sk时的决策，称为决策变决策变 量量，简记uk 决策变量的取值被限制在某一范围内，此范围称为允许决 策集合Uk(sk) 10第二节
7、 动态规划的基本概念和基本原理 策略(policy) 多阶段决策过程中，每一阶段均有一个决策，依序组合成 一个全过程的决策序列，称为全过程策略全过程策略。p1,n(s1)=u1(s1),u2(s2) , un(sn) ，简记p1,n =u1, u2, un 从过程的某个阶段开始到最终阶段结束称为后部子过程。 从第k阶段开始的后部子策略称为第第k k子过程策略子过程策略。pk,n(sk)=uk(sk), uk+1(sk+1) , un(sn) ，简记pk,n =uk, uk+1, un 每一阶段有若干状态,每个状态又有若干个不同的决策,即 有许多策略可供选择。全体策略构成允许策略集合Pk,n(s
8、k) 。 能使预期目标达到最优效果的策略称为最优策略P*k,n ， 构成最优策略的各决策称为相应阶段的最优决策u*k。11第二节 动态规划的基本概念和基本原理 状态转移方程 下一阶段状态sk+1 是本阶段状态变量sk 和决策变量uk的函数 ，即 sk+1 =T(sk, uk(sk) =T(sk, uk) 从状态sk出发到下一阶段状态sk+1的转移规律称为状态转移状态转移 方程方程。12第二节 动态规划的基本概念和基本原理 指标函数 用来衡量所选定策略优劣的数量指标称为指标函数。 用来衡量每一阶段决策效果的优劣的数量指标，称为阶段指标函数阶段指标函数dk，阶段指标是状态变量和相应决策变量的函数，
9、即dk = dk(sk , uk )。最短问题是运费或路程。对阶段的不同状态，采取不同的决策， 运费不同。 指标函数也可以是利润、成本、产量等。 从第k阶段的状态sk出发到最后阶段结束，各阶段绩效综合起来反映这 个后部子过程的绩效，称为过程指标函数过程指标函数，记为Vk,n。Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。即 Vk,n = Vk,n (sk , uk , sk+1 , uk+1 , sn)根据实际问题的性质，指标函数Vk,n 可以是各个阶段指标的和或积 。 从状态sk出发，选取最优策略所得的指标函数值称为最优指标函数值最优指标函数值 。 fk(sk)=optVk,n =
10、optdk(sk , uk ) + fk+1(sk+1) opt表示最优化，取最大max或最小min。 13第二节 动态规划的基本概念和基本原理 逆序算法：逆着阶段顺序的方向，由后向前推算。 把寻求最优策略看作连续递推过程，从最终阶段开始 ，逆着实际过程的进展方向逐段求解； 在每一阶段求解过程中都是其后部子过程最优策略的 基础上，再考虑本阶段的指标函数，求出本阶段的最 优策略； 直到第一阶段为止。二、动态规划方法的基本思想与基本原理 14第二节 动态规划的基本概念和基本原理阶段1阶段2阶段k阶段k+1阶段n状态S1决 策 u1状态S2d1决 策 u2状态S3d2决 策 uk状态Sk+1dk决
11、策 uk+1dk+1决 策 undn寻求最优解的方向152511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径162511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0172511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0182511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=51925112
12、14 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5202511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8212511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7222511214 106 104 131112396581052C1C
13、3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8232511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=20242511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(
14、B1)=20f2(B2)=14252511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20262511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状
15、态 最优决策 状态 最优决策 状态A （ A，B2） B2272511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1282511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决
