第8章动态规划

1、u8-1 引例引例u8-2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理 8-1 引例引例一、最短路线问题：一、最短路线问题： 如图为一线路网路，现在要铺设从地点如图为一线路网路，现在要铺设从地点A到地点到地点E的的铁路，中间需要经过铁路，中间需要经过3个点，第个点，第1个点可以是个点可以是B1， B2 ， B3 中中的某一个点，第的某一个点，第2个点可以是个点可以是C1，C2，C3中的一个点，等中的一个点，等等。各点之间，若能铺设铁路则在图中以连线表示，连线等。各点之间，若能铺设铁路则在图中以连线表示，连线上的数字表示两点间的距离。要求选择一条上的数字表示两点间的距离。要求选择一

2、条A至至E的最短的最短铺设线路。铺设线路。AB1B2B3C1C2C3D1D2E364774565342365344个阶段进行决策个阶段进行决策:第第1阶段：从阶段：从A出发，终点可选择出发，终点可选择B1或或B2或或B3；第第2阶段：从阶段：从B1出发（如果第出发（如果第1阶段的决策导致终点为阶段的决策导致终点为B1)终点可选择终点可选择C1或或C2；或从；或从B2出发，终点可选择出发，终点可选择C1 ， C2，C3；或从；或从B3出发，出发，终点可选择终点可选择C2，C3。这样继续下去，直到第。这样继续下去，直到第4阶段达到阶段达到E。本例共有本例共有12条不同的线路条不同的线路,比较它们的

3、长度比较它们的长度,最短线路为：最短线路为：A B3 C2 D1 EAB1B2B3C1C2C3D1D2E364774565342365338-2 动态动态规划的基本概念和基本原理规划的基本概念和基本原理一、动态规划的基本概念一、动态规划的基本概念(一一)阶段阶段 把一个复杂决策问题按时间或空间特征分解为若把一个复杂决策问题按时间或空间特征分解为若干干(n)(n)个相互联系的阶段个相互联系的阶段(stage), (stage), 以便按顺序求解以便按顺序求解; ; 阶段变量描述当前所处的阶段位置，一般用下标阶段变量描述当前所处的阶段位置，一般用下标 k k 表示表示; ; (二二)状态和状态变量

4、状态和状态变量 每阶段有若干状态每阶段有若干状态(state), (state), 表示某一阶段决策面临表示某一阶段决策面临的条件或所处位置及运动特征的量的条件或所处位置及运动特征的量, ,称为状态。反映状态称为状态。反映状态变化的量叫作状态变量。变化的量叫作状态变量。 k k 阶段的状态特征可用状态变阶段的状态特征可用状态变量量 S Sk k 描述描述; ;和和 所谓决策就是确定系统过程发展的方案，决策的所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从给定阶段状态出实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。发对下一阶段状态作出的选择。

5、 用以描述决策变化的量称之决策变量，和状态变量一用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描样，决策变量可以用一个数，一组数或一向量来描述也可以是状态变量的函数，记以述也可以是状态变量的函数，记以 ，表示于，表示于 k 阶段状态阶段状态 sk 时的决策变量时的决策变量( )kkkuu s 状态转移确定从一个状态到另一个状态的转移过程状态转移确定从一个状态到另一个状态的转移过程, 由状态转移方程描述由状态转移方程描述: sk+1 = T (sk, uk); 状态转移方程在大多数情况下可以由数学公式表达状态转移方程在大多数情况下可以由数学公式表达, 如

6、如: sk+1 = sk + uk； 用来衡量策略或子策略或决策的效果的某种数量指标，用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。效用，等等。55111()()0()min / max(,()()4,3,2,1kkkkkkkkkkkkuUsfsfsgsusfusk二、动态规划的基本原理二、动

7、态规划的基本原理l整个过程的最优策略应具有这样的性质整个过程的最优策略应具有这样的性质: 无论过无论过去的状态和决策如何去的状态和决策如何, 对前面的决策所形成的状态对前面的决策所形成的状态而言而言, 后续的诸决策必须构成最优策略；后续的诸决策必须构成最优策略；l上一条成立的条件是损益递推函数严格单调。上一条成立的条件是损益递推函数严格单调。 1. 将问题按时间或空间划分为满足递推关系的若干阶段将问题按时间或空间划分为满足递推关系的若干阶段, 对非时序问题可人为地引入对非时序问题可人为地引入“时段时段”概念概念; 2. 正确选择状态变量正确选择状态变量 sk, 满足满足:可知性可知性: 正确描

8、述动态过程演变正确描述动态过程演变, 可直接或间接确定状态可直接或间接确定状态变量的值变量的值;无后效性无后效性: 后面的决策与前面的决策无关后面的决策与前面的决策无关;3. 确定决策变量确定决策变量uk(或或xk)以及允许决策集合以及允许决策集合Dk;4. 写出状态转移方程写出状态转移方程 sk+1 = T (sk , dk);5. 决策变量的取值范围决策变量的取值范围6. 写出损益函数的递推关系写出损益函数的递推关系, 应满足应满足:a) 是定义在所有阶段上的数量函数；是定义在所有阶段上的数量函数；b) 具有可分离性，并满足递推关系；具有可分离性，并满足递推关系；c) 损益函数应严格单调。

9、损益函数应严格单调。 卡车的最大运货重量为卡车的最大运货重量为 12 吨吨, 容积为容积为 10 立立方米方米, 现有现有A , B 两种货物两种货物, 重量分别为重量分别为 3 吨和吨和 4 吨吨, 体积分别为体积分别为 1 和和 5 立方米立方米, 运费分别为运费分别为 2 和和 3 元元, 如何装载使所得运费最大。如何装载使所得运费最大。 由资源条件可知最多可装载由资源条件可知最多可装载 4 件件 A 或或 2 件件 B。l阶段可按货物种类划分阶段可按货物种类划分, k = 1, 2l每阶段剩余的载货能力每阶段剩余的载货能力(重量与容积重量与容积)为该阶段的为该阶段的状态状态, 状态变量

10、状态变量 sk = (s1k, s2k);l决策变量决策变量 xk 表示表示 k 阶段资源的占用量阶段资源的占用量;l状态转移方程状态转移方程: sk+1= sk-akxk , ak=(a1k, a2k)l损益函数为损益函数为: fk(sk)=maxckxk+fk+1(sk+1)求解求解lk = 2f2(12, 10) = maxx2=0,1,2f1(12,10), 3+ f1(8, 5), 6+f2(4, 0) = max 8, 3+4, 6+0 = 8k = 1f1(12,10) = maxx1 4 2x1 = 8f1( 8, 5) = maxx1 2 2x1 = 4f1( 4, 0) =

11、 0 为保证设备可靠运行为保证设备可靠运行, 一些关键部件往往由多个器件一些关键部件往往由多个器件并联运行并联运行, 如果器件如果器件 i 的失效概率为的失效概率为 pi, 则则 xi 个器件并联个器件并联工作的可靠性为工作的可靠性为(1 - pixi), 假定每个器件的采购费用为假定每个器件的采购费用为 ci, 在满足总采购费用不超过预算限制在满足总采购费用不超过预算限制 C 的前提下的前提下, 使设备使设备可靠性最高的规划问题可以描述为可靠性最高的规划问题可以描述为:该问题为整数非线性规划，可以用动态规该问题为整数非线性规划，可以用动态规划求解，设关键器件数划求解，设关键器件数n = 3，

12、总费用为，总费用为120万元。器件的单价与可靠性如下表：万元。器件的单价与可靠性如下表：器件号器件号i 单价单价(万元万元) 失效概率失效概率pi阶段与器件挂钩，第阶段与器件挂钩，第 i 阶段仅考虑器件阶段仅考虑器件 i 的的采购数量采购数量;si 表示表示 i 阶段可使用的采购费用阶段可使用的采购费用;xi 表示表示 i 阶段决定购买阶段决定购买 i 器件的数量；器件的数量；状态转移方程状态转移方程: si+1 = si - ci xi；递推损益函数递推损益函数:fi(si) = max ( 1 - pixi ) fi+1(si+1)。i = 1f1(120) = max1 x1 3 0.9f2(90), 0.99f2(60), 0.999f2(30) = max 0.9 0.84*, 0.99 0.4, 0.999 0 = 0.756i = 2f2(90) = max 0.8f3(75) , 0.96f3(60) , 0.992f3(45) , 0.9984f3(30) = max 0.8 0.875 , 0.96 0.875* , 0.992 0.75 , 0.9984 0.5 = 0.84 f2