《运筹学课程07-动态规划》由会员分享，可在线阅读，更多相关《运筹学课程07-动态规划（110页珍藏版）》请在金锄头文库上搜索。
1、动态规划,Dynamic Programming,不要过河拆桥追求全局最优, 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例,本章内容,一、多阶段决策过程的最优化,示例1（工厂生产安排）：某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负
2、荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。,设有数量为y的某种资源，将它分别投入两种生产方式A和B，已知收益函数分别是g(x)和h(x)，x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产，A、B的回收率分别为a和b（ 0a1，0b1 ），问：对总数量为y的资源进行n个阶段的生产，应如何分配每个阶段投入A、B的资源数量，才能使总收益最大？,推广：多阶段资源分配问题,示例2（设备更新问题）：,一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效
3、益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。,一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。,示例3 （连续生产过程的控制问题）：,示例4、最短路径问题,给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。,1,2,3,4,5,6,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,
4、F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,示例5（生产与存储问题）：某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产j个单位产品的费用如下：每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。,每个月视为一个阶段，,每个阶段都须决定生产几个、库存几个,上一个阶段的决策直接影响下一个阶段的决策,由于航天飞机的运动的环境是不断变化的，因此就要根据航天
5、飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,示例6（航天飞机飞行控制问题）：,10,所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策均确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。,1,2,n,状态,决策,状态,决
6、策,状态,状态,决策,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,某些线性规划、非线性规划等静态规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,DP是上个世纪五十年代贝尔曼(B.E.Bellman)为代表 的研究成果，属于现代控制理论的一部分。其最优化原理， 可归结为一个递推公式。,注意：动态规划是求解某类多阶段决策问题的一种方法，是考察问题的一种途径，不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,动态规划思想示例：,B,C,B
7、,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,以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从 A到E的最短路径问题。,第四阶段：两个始点 和 ，终点只有一个；,分析得知：从 和 到E的最短路径唯一。,第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题：分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路
8、为C3-D1-E。,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。,第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：最后，可以得到：从A到E的最短路径为A B4 C3 D1 E,以上计算过程及结果，可用下图表示，可以看到，以上方法不
9、仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。,B,C,B,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,二、动态规划的基本概念和基本原理,基本概念1、阶段：把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。,2、状态：
10、表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量。,一个数一组数一个向量,状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。,3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。,描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。,系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。,4、多阶段决策过程,可以在各个
11、阶段进行决策，去控制过程发展的多段过程；,其发展是通过一系列的状态转移来实现的；,图示如下：,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,其状态转移方程如下（一般形式）,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。,动态规划中能 处理的状态转移 方程的形式。,状态具有无后效性的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这
12、个阶段以后过程的发展不受这个阶段以前各段状态的影响；,过程的过去历史只能通过当前的状态去影响它未来的发展；,状态变量要满足无后效性的要求；,5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。,6、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。,7、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，
13、应具有可分离性，并满足递推关系。,小结:,指标函数形式:,和、,积,无后效性,可递推,原过程的一个后部子过程：,原过程的一个后部子过程的策略：,对于任意给定的k（1 kn），从第k段到第n段的过程称为原过程的一个后部子过程,最优策略,解多阶段决策过程问题，求出,f1(s1),从 k 到终点最优策略 子策略的最优目标函数值,问题分成4个阶段：,k=1，2，3，4,线路：,线路：,k=1：,k=3：,阶段,状态,第一阶段的状态：,第二阶段的状态：,sk,s4,Sk =sk,S3 =s3,=5，6，7,注：n个阶段的决策过程有个n+1状态变量,sn+1表示sn演变的结果,S5 =10,决策,决策,可
14、取值为：5，6，7,=5，6，7,允许决策集合,策略,最短路问题：,策略,= 行进方案,如 ,允许策略集合,最优策略：使整个问题达到最优效果的策略,策略： ,最优策略=最短的行进路线,策略, , , ,最短路问题：,原过程的一个策略：, ,后部子过程的策略, ,后部子过程的策略,后部子过程的策略,or ,每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。,k=1，2，3，4,阶段,第k阶段的状态变量sk,S1=0，,S2=0,1,2,3，,S3
15、=0,1,2,3，,S4=0,1,2,3,=第k个月月初的库存量,（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为,=2,3,4,5,=2,3,4,5,=0,1,2,3,=3,一个策略=一个生产方案,2，5，0，4,2，3，2，4,费用：21（千元）,费用：23（千元）,最优策略：,使总费用最小的生产方案,最优化原理（基本原理）作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的当前状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。,对最短路问题：,最短路问题的基本方程：,k=4,3,2,1,从最后一阶段开始，用由后向前的方法，求出各点到终点的 最短路线，最后，求得由起点到终点的最短路线。,
