1、HuBei University of Technology湖北工业大学第 5章 动态规划实际经济社会活动中，许多问题从时间或空间上带有一定的 “阶段逻辑 ”，从而形成了多阶段的决策问题。动态规划是求解多阶段决策问题的最优化数学方法。一个决策问题可分解成若干个相互联系的阶段，每个阶段有若干种方案可供选择。决策的任务是在每个阶段选择一个适当的方案，从而使整个问题取得最优效果。动态规划将复杂的多阶段决策问题分解为一系列简单的单阶段决策问题 , 通过解一系列小问题达到求解整个问题目的。动态规划的各个决策阶段不但要考虑本阶段的决策目标 , 还要兼顾整个决策过程的整体目标 , 从而实现整体最优决策。5.
2、1 多阶段决策问题多阶段决策问题 ：是指将一类活动过程分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。策略 ：每个阶段的决策确定后，得到的一个决策序列。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。HuBei University of Technology湖北工业大学第 5章 动态规划5.1 多阶段决策问题例 1：基建投资问题。一家公司有三个工厂，每个工厂都需要进行扩建。公司用于扩建的资金总共为 7万元，各工厂的投资方案及扩建后预期可获得的利润如表所示。厂名 方案 1 方案 2 方案 3 方案 4投 资 数 利 润
3、 投 资 数 利 润 投 资 数 利 润 投 资 数 利 润一厂 0 0 1 5 2 8 3 10二厂 0 0 1 3 3 9 4 11三厂 0 0 2 7 3 11 4 13公司要确定对各厂投资多少，使公司的总利润达到最大？每个工厂都有几种投资方案，对每个工厂作出一项决策，共要做出三项决策。将每个工厂看成一个阶段，就是一个多阶段的决策问题。HuBei University of Technology湖北工业大学第 5章 动态规划5.1 多阶段决策问题例 2：最短路线问题。假设从 A到 E地要铺设一条管道，其中要经过若干个中间点。两点之间连线上的数字表示两地之间的距离。选择一条铺设管道的路线，
4、使总长度最短。将整个路程分为 A、 B、 C、 D四个阶段，是一个以空间位置为特征的多阶段决策问题。B2B1B3AC1C2C3D2D1E35776 952 3834653943HuBei University of Technology湖北工业大学第 5章 动态规划5.1 多阶段决策问题例 3：机器负荷分配问题。某种机器可以在高低两种不同的负荷下生产。在高负荷下生产时，产品的年产量 g 和投入生产的机器数量 u1 的关系为：g = g( u1 )此时，机器的年完好率为 a ，即如果年初完好机器的数量为 u ，到年终时完好的机器为 au ， 0 a 1。在低负荷下生产时，产品的年产量 h 和投入
5、生产的机器数量 u2 的关系为：h = h( u2 )相应的机器年完好率为 b ， 0 b 1。设开始生产时完好机器的数量为 s ，制定一个五年计划，在每年开始时，决定如何分配完好机器在不同负荷下生产的数量，使五年内产品的总产量达到最高。将每年分配的情况看作一个阶段，共有 5个阶段，是一个以时间为特征的多阶段决策问题。HuBei University of Technology湖北工业大学第 5章 动态规划5.1 多阶段决策问题在多阶段决策问题中，各个阶段采取的决策与时间有关，随着时间的发展而决定各时段的决策，产生一个决策序列，这就具有了 “动态 ”的含义，所以把处理这类以时间为划分阶段的动态
6、问题的方法称为动态规划方法。在实际中也有许多不包含时间因素的一类 “静态 ”决策问题，其本质是一次决策问题，是非动态决策问题，但是也可人为地引入阶段的概念当作多阶段决策问 题，应用动态规划方法加以解决。5.2 动态规划的基本概念阶段（ stage） ：把一个复杂决策问题按时间或空间特征分解为若干个相互联系的阶段，以便能按一定的次序求解。描述阶段的变量称为阶段变量，用下标 k 表示。状态（ state） ：每个阶段有若干状态， 表示某一阶段决策面临的条件或所处位置及运动特征的量。描述状态的变量称为状态变量， k 阶段的状态特征用状态变量 sk 或 xk描述HuBei University of
7、Technology湖北工业大学第 5章 动态规划状态有起始、中间、最终状态之分，每一阶段的全部状态构成该阶段的状态集合 Sk或 Xk，并有 skSk或 xkXk 。每个阶段的状态分为初始状态和终止状态，或称输入状态和输出状态，阶段的初始状态记作 xk ，终止状态记为 xk+1 。5.2 动态规划的基本概念决策（ decision） ：确定系统过程发展的方案（选择）。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。描述决策的量为决策变量，决策变量可用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以 uk= uk( xk )，表示第 k 阶段状态处于 x
8、k 时的决策变量。决策变量的取值有一定的允许范围，称为允许决策集合。决策变量 uk( xk ) 的允许决策集合用 Dk( xk ) 表示， uk(xk) Dk(xk)允许决策集合是决策的约束条件。策略（ policy） ：按顺序排列的决策组成的集合，也称为决策序列。策略有全过程策略和 k子策略之分。HuBei University of Technology湖北工业大学第 5章 动态规划5.2 动态规划的基本概念全过程策略 ：指具有 n个阶段的全部过程，由依次进行的 n个阶段决策构成的决策序列，简称策略，表示为： p1,n(x1)= u1(x1), u2(x2), , un(xn) k子策略
9、：从 k阶段到第 n阶段，依次进行的阶段决策构成的决策序列称为 k子策略，表示为： pk,n(xk)= uk(xk), uk+1(xk+1), , un(xn) 当 k=1时的 k子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，不同决策组合就构成了许多可供选择的决策序列（策略），由它们组成的集合，称之允许策略集合，记作 P 。从允许策略集中，找出具有最优效果的策略称为最优策略。状态转移方程 ：确定决策过程由一个状态到另一个状态的演变过程。系统由 k阶段的状态 xk 转移到了阶段 k+1的状态 xk+1 ，记为： xk+1 = Tk( xk, uk )即 xk+1的值由
10、阶段 k的状态 xk 和决策 uk(xk)来确定。该式称为多阶段决策过程的状态转移方程， Tk为状态转移函数。HuBei University of Technology湖北工业大学第 5章 动态规划5.2 动态规划的基本概念指标函数 ：用来衡量策略或子策略或决策的效果的数量指标，称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是费用、成本、产值、利润、产量、距离、时间等函数。阶段指标函数（阶段效应） ：用 vk=vk,( xk, uk )表示，指第 k段处于 xk状态且所作决策为 uk(xk)时的指标，它就是第 k段指标函数。过程指标函数（目标函数）
11、 ：用 Vk, n =Vk, n ( xk, uk, xk+1, uk+1, , xn, un, xn+1)表示，指从状态 xk出发到过程最终，当采取某种子策略时的指标。过程指标函数不仅跟当前状态 xk有关，还跟该子过程策略 pk, n(xk)有关。在实际应用中往往表示为过程指标函数，该函数 Vk, n通常是描述所实现的全过程或 k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数 vk累积形成的，适于用动态规划求解的问题（阶段可分性）。k子过程的目标函数可表示为： 表示某种运算，可以是加法、乘法、除法等。HuBei University of Technology湖北工业大学第 5章
12、动态规划5.2 动态规划的基本概念多阶段决策问题中，常见的目标函数形式有：1.取各阶段指标之和，即 :2.取各阶段指标的乘积，即：考虑到动态规划问题应满足递推关系，上式可写成：上式可写成：最优值函数 ：指标函数达到最优值，记为 fk( xk )。表示从第 k阶段的状态 xk到第n阶段的终止状态过程，采取最优策略所得到的指标函数值。HuBei University of Technology湖北工业大学第 5章 动态规划5.2 动态规划的基本概念例 ：最短路线问题B2B1B3AC1C2D3D2D1E3214513224 5531 1333从 A到 E全过程分为四个阶段：第一阶段：第二阶段：第三阶段：第四阶段：每个阶段都有一个起始点 初始状态每个阶段都要作一个选择 决策一个阶段的决策不仅影响到本阶段的效果，还影响到下一阶段初始状态，从而影响此后过程。从 A到 E共有 3231=18条不同路线，即从 18种不同方案中选择最佳路线。设第一、二、三阶段最佳路线决策的结果分别为则从 到 的路径是从 B 到 E 所有路径中最短路径。
