运筹学第六章动态规划

第六章动态规划第66页第六章动态规划主要内容：1、动态规划的基本概念2、动态规划的最优性原理和基本方程3、动态规划的模型及其应用重点与难点：动态规划的状态转移方程、基本方程；动态规划的建模思路与方法；运用递推原理确定最优解的方法与技巧。要求：理解动态规划的基本概念，掌握动态规划的建模步骤和求解方法，能够创造性地建立数学模型，并能运用动态规划方法解决实际问题。§1动态规划的基本概念例1最短线路问题。给定一个运输网络（如图），两点之间的数字表示两点间的距离，试求一条从A0到A4的运输线路，使总距离为最短?1、阶段对于一给定的多阶段过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用K表示。1）阶段数固定的问题称为定期多阶段决策问题；如例1，可分为四个阶段。2）阶段数不固定的问题称为不定期多阶段决策问题。如2、状态状态表示某阶段的出发位置。它既是某阶段过程演变的起点，又是前一阶段决策的结果。例1中，第一阶段有一种状态即A0点，第二阶段有三个状态，即点集合{A1，B1，C1}，一般第K阶段的状态就是第K阶段所有始点的集合。描述过程状态的变量称为状态变量。第K阶段的状态变量，记为kx。3、决策决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决A0A1B1C1A20B2C2B3A30A4020403070503020404010501040603030303040BACDE472426211第六章动态规划第67页定称为决策。描述决策的变量称为决策变量，常用)(kkxu表示处于状态kx时的决策变量，它是状态变量的函数。如：21AB，记为212ABU决策变量可取值的全体，称为允许决策集合。常用kkxD表示状态kx的允许决策集合。如：22212,,CBABD，2212,CAAD4、策略全过程的各个阶段上所选择的决策组成的全体称之为全过程策略，记为nP,1。若43210AAAAA为一决策，则全过程策略442211,1,,,xuxuxuPn由过程的第K阶段开始到终止状态为止的过程，称为问题的后子过程（或K子过程）。其决策函数序列)(,),(),(11nnkkkkxuxuxu称为k子过程策略，简称子策略，记为)(,knkxp。即)(,),(),()(11,nnkkkkknkxuxuxuxp在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用P表示。从允许策略集合中找出达到最优效果的策略称为最优策略。5、状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。它描述了由K阶段到K+1阶段的状态转移规律，称之为状态转移方程，记为kkkkuxTx,1。6、指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数，常用nkV,表示。即nkxuxuxVVnkkkknknk,,2,1,,,,,111,,动态规划的指标函数，应具有可分离性，并满足递推关系。即nkkknkVuxV,!,,,过程和它的任一子过程的指标是它所包含的各阶段的指标和，即nkjjjjnkuxVV,,指标函数具有可加性其中jjjuxV,表示第j阶段的阶段指标上式可写成：1111,,,,,nkkkkkknkxuxVuxVV由于给定了过程的初始状态及策略，则指标函数也随之确定，所以指标函数是初始状态和策略的函数，记为knkknkxPxV,,,，knkxP,——子策略上式也可写成nkknkkkknkknkPxVuxVpxV,11,1,,,,,第六章动态规划第68页指标函数的最优值，称为最优值函数，记为kkxf，即1,,,,nkknkkkxuxoptVxf1,,1,,,11nnkxfuxVoptkkkkkxDukkk§2基本定理和基本方程一、最优性原理——作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优策略的子策略总是最优的。这是动态规划的理论基础。在例1中，如果43210ABABA是40AA到的最短路线，则4321ABAB一定是由B1到A4的最短路线。二、基本方程kkkknnkkkkkxDukkuxTxxfnnkxfuxVoptxfkkk,01,,1,,,11111其中边界条件—§3动态规划的模型及求解因为动态规划没有一个标准的数学表达式，所以建立动态规划的模型比它的计算更为困难。一、建立模型的步骤（1）选择阶段变量K按时间或空间的先后顺序将问题划分为满足某种递推关系的若干阶段。（2）选择状态变量kx状态变量应满足可知性和无后效性。可知性是指过程的各阶段状态变量的取值，都能直接或间接的确定；无后效性是指如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。通常选择随递推关系累计的量或按某种规律变化的量作为状态变量。（3）选择决策变量ku（4）写出状态转移方程式（5）列出动态规划的基本方程二、逆序解法与顺序解法动态规划的求解有两种基本方法：逆序解法（后向动态规划方法）、顺序解法（前向动态规划方法）。使用上述两种方法求解时，除了求解的行进方向不同外，在建模时要注意以下区别：1、状态转移方式不同逆序解法中第k段的输入状态为kx,决策为ku，输出状态为1kx，即第k+1阶段的状态，所以状态转移方程为：第六章动态规划第69页)(,1kkkkuxTx，阶段指标为),(kkkuxv。顺序解法中第k段的输入状态为1kx,决策为ku，输出状态为kx，所以状态转移方程为：)(,1kkkkuxTx，阶段指标为),(1kkkuxv。2、指标函数的定义不同逆序解法中，最优指标函数)(kkxf表示第k段从状态kx出发，到终点后部子过程最优效益值。)(11xf是整体最优函数值。顺序解法中，最优指标函数)(1kkxf表示第k段时从起点到状态1kx的前部子过程最优效益值。)(1nnxf是整体最优函数值。3、基本方程形式不同（1）当指标函数为阶段指标和形式，逆序解法中，nkjjjjnkuxvV),(,，则基本方程为：01,,1,,,1111nnkkkkkDukkxfnnkxfuxVoptxfkk顺序解法中，kjjjjkuxvV11,1),(，基本方程为：0,,2,1,,10111xfnkxfuxVoptxfkkkkkDukkkk（2）当指标函数为阶段指标积形式，逆序解法中，nkjjjjnkuxvV),(,，则基本方程为：11,,1,,,1111nnkkkkkDukkxfnnkxfuxVoptxfkk顺序解法中，nkjjjjkuxvV),(1,1，基本方程为：1,,2,1,,10111xfnkxfuxVoptxfkkkkkDukkkk例1解：A0A1B1C1A20B2C2B3A30A4020403070503020404010501040603030303040k=1k=2k=3k=4第六章动态规划第70页当k=4时，334,BAx434434ABDAAD055xf4434,min344uxVAfADU4343:30,minAAAAV优决策最4434,min344uxVBfBDU4343:40,minABABV最优决策当k=3时,2223,,CBAx33232323,BACDBDAD443223,min233xfUAVAfADU34323432,,,minBfBAVAfAAV32:404040,3010minAA最优决策443223,min233xfUBVBfBDU34323432,,,minBfBBVAfABV32:7040303060minBB最优决策，443223233minxfUCVCfCDU44323432,,,minBfBCVAfACV32:604030,3030minAC最优决策当k=2时,1112,,CBAx2212,CAAD1,2,3,40,min5511kxfxfuxVxfkkkkxDukkkkk第六章动态规划第71页2221212,,CBACDBD332112,min122xfuAVAfADu23212321,,,minCfCAVAfAAV2121:1106050,4070minCAAA最优决策332112,min122xfuBVBfBDu23212312321,,2,,,minCfCBVBfBBVAfABV21706040,7020,4030minAB最优决策：332212,min122xfUCVCfCDU232123212321,,,,,minCfCCVBfBCVAfACV2121:806050,7010,4040minBCAC最优决策当k=1时，1110101,,CBAADAx221001,min011xfuAVAfADu121012101210,,,,,minCfCAVBfBAVAfAAV1010:1108030,7040,11020minCABA最优决策40AA的最短距离为110，最短路为：43210AAABA43210AAACA43210ABBCA例2多阶段资源分配问题有1000台机器生产A、B两种产品，用Y台机器生产A产品，可获得收入5Y，用Y台机器生产B产品，可获得收入4Y，一年后，生产A产品的机器完好率为0.8，生产B产品的机器完好率为0.9，问五年内如何安排生产A、B两种产品，使得总收入最大？解：设k表示年度kx为第k年初完好机器数（亦即第k-1年未完好机器数）ku为第k年安排生产A产品的机器数（生产B产品的机器数为kkux）第六章动态规划第72页则允许决策集合kkkkkxuuxD0状态转移方程为kkkkkkuxuxux1.09.09.08.01基本方程为1,2,3,4,5045max,max661111kxfxfuxuxfuxVxfkkkkkxDukkkkxDukkkkkkkk其中kkkuxx1.09.01当k=5时,6655505545max55xfuxuxfxu555054max55xuxxu最优决策5*5xu，即第五年所有设备都用于生产A产品。当k=4时5544404445max44xfuxuxfxu544054max44xuxxu444401.09.054max44u