运筹学第9章动态规划.

五动态规划第9章动态规划的基本方法第10章动态规划应用举例12动态规划•什么是动态规划–解决多阶段决策过程最优化的一种数学方法。•动态规划的形成–产生于20世纪50年代。1951年美国数学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法——动态规划。•动态规划的应用–在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果。3动态规划•动态规划在企业管理中的主要应用领域–最优路径问题–资源分配问题–生产调度问题–库存问题–装载问题–排序问题–设备更新问题–生产过程最优控制问题–等等动态规划是求解某类问题的一种方法，是考查问题的一种途径，而不是一种特殊算法(如线性规划是一种算法)。因而，它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。4动态规划•动态规划模型的分类–根据多阶段决策过程的时间参量是离散的还是连续变量，分为离散决策过程和连续决策过程。–根据决策过程的演变是确定性的还是随机性的，又可分为确定性决策过程和随机性决策过程。–组合起来可分为•离散确定性•离散随机性•连续确定性•连续随机性本书主要研究离散决策过程。5第9章动态规划的基本方法第1节多阶段决策过程及实例第2节动态规划的基本概念和基本方程第3节动态规划的最优性原理和最优性定理第4节动态规划和静态规划的关系6第1节多阶段决策过程及实例•多阶段决策过程–在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。7第1节多阶段决策过程及实例•例1最短路线问题给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)，试求一条由A到G的铺管线路，使总距离为最短(或总费用最小)。8第1节多阶段决策过程及实例例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au，0＜a＜1，在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为h=h(u2)相应的机器年完好率为b,0＜b＜1。假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。9第2节动态规划的基本概念和基本方程例1中求A到G的最短路线问题是动态规划中一个典型例子。现通过讨论它的解法，说明动态规划方法的基本思想，并阐述有关基本概念。由图8-2可知，从A点到G点可以分为6个阶段。在第一阶段，A为起点，终点有B1、B2两个，因而这时走的路线有两个选择，一是走到B1；一是走到B2，若选择走到B2的决策，则B2就是第一阶段决策的结果。它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，有一个可供选择的终点集合｛C2，C3，C4｝；若选择由B2走至C2，则C2就是第二阶段的终点，同时又是第三阶段的始点。递推下去可看到：各个阶段的决策不同，路线就不同。显然，当某阶段的始点给定后，会影响后面各阶段的行进路线和整个路线的长短，而后面各阶段路线的发展不受这点以前各阶段决策的影响。故此问题的要求是：在各个阶段上选则一个恰当的决策，使得由这些决策组成的一个决策序列所决定的一条路线是总路程最短的一条。102.1动态规划的基本概念•1．阶段–把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策的过程。如例1可分为6个阶段来求解，k分别等于1、2、3、4、5、6。112.1动态规划的基本概念•2．状态–状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素。在例1中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。通常一个阶段有若干个状态，第一阶段有一个状态就是点A，第二阶段有两个状态，即点集合｛B1，B2｝，一般第k阶段的状态就是第k阶段所有始点的集合。122.1动态规划的基本概念描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量(多维情形)来描述。常用Sk表示第k阶段的状态变量。如在例1中第三阶段有四个状态，则状态变量Sk可取四个值，即C1、C2、C3、C4。点集合｛C1，C2，C3，C4｝就称为第三阶段的可达状态集合。记为S3＝｛C1，C2，C3，C4｝。有时为了方便起见，将该阶段的状态编上号码1，2…这时也可记S3＝｛1，2，3，4｝。第k阶段的可达状态集合就记为Sk。马尔科夫性这里所说的状态应具有下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的一个总结。这个性质称为无后效性(即马尔科夫性)。132.1动态规划的基本概念3．决策决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决策的变量，称为决策变量。它可用一个数、一组数或一向量来描述。常用uk（sk）表示第k阶段当状态处于sk时的决策变量。它是状态变量的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk（sk）∈Dk(sk)。142.1动态规划的基本概念3．决策如在例1第二阶段中，若从状态B1出发，就可作出三种不同的决策，其允许决策集合D2(B1)＝｛C1，C2，C3｝，若选取的点为C2，则C2是状态B1在决策u2(B1)作用下的一个新的状态，记作u2(B1)=C2。152.1动态规划的基本概念(),,()kknnusus,()knkps,11()(),(),,()knkkkkknnpsususus1,1()nps1,11122()(),(),,()nnnpSususus4．策略策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为，即当k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为，即在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。从允许策略集合中找出达到最优效果的策略称为最优策略。162.1动态规划的基本概念1(,)kkkksTsu1()kkksus5．状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。若给定第k阶段状态变量的值，如果该段的决策变量uk一经确定，第k+1阶段的状态变量sk+1的值也就完全确定。即sk+1的值随sk和uk的值变化而变化。这种确定的对应关系，记为上式描述了由k阶段到k+1阶段的阶段的状态转移规律，称为状态转移方程。Tk称为状态转移函数。如例1中，状态转移方程为172.1动态规划的基本概念,,11(,,,,),1,2,,knknkkknVVsusskn6．指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。常用Vk,n表示，即对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可以表示为sk、uk、Vk+1,n的函数，记为在实际问题中很多指标函数都满足这个性质。)],,(,,[),,,,(11,111,nknkkkknkkknkssVusssusV182.1动态规划的基本概念,1(,,,)(,)nknkknjjjjkVsusvsu(,)jjjvsu,1(,,,)(,)nknkknjjjjkVsusvsu(1)过程和它的任一子过程的指标是它所包含的各阶段的指标的和。即其中表示第j阶段的阶段指标，这时上式可写成(2)过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。即这时就可写成常见的指标函数形式),,,(),(),,,(111,11,nkknkkkknkknksusVusvsusV),,,(),(),,,(111,11,nkknkkkknkknksusVusvsusV192.1动态规划的基本概念()kkfs,1,,()opt(,,,)knkkknkknuufsVsus指标函数的最优值，称为最优值函数，记为。它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即“opt”是最优化(optimization)的缩写，可根据题意而取min或max。202.2动态规划的基本思想和基本方程结合最短路线问题介绍动态规划方法的基本思想。生活中的常识告诉我们，最短路线有一个重要特性：如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达终点G的这条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如，在最短路线问题中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最短路线，则D1→E2→F2→G应该是由D1出发到G点的所有可能选择的不同路线中的最短路线。证明：（用反证法）如果不是这样，则从点P到G点有另一条距离更短的路线存在，把它和原来最短路线由A点到达P点的那部分连接起来，就会得到一条由A点到G点的新路线，它比原来那条最短路线的距离还要短些。这与假设矛盾，是不可能的。212.2动态规划的基本思想和基本方程根据最短路线这一特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到G点的最短路线，最后求得由A点到G点的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方下面按照动态规划的方法，将例1从最后一段开始计算，由后向前逐步推移至A点。222.2动态规划的基本思想和基本方程61()4fF62()3fF123,,EEE511615151262(,)()34()minmin7(,)()53dEFfFfEdEFfF11()suEF当k=6时，由F1到终点G只有一条路线，故。同理，当k=5时，出发点有三个。若从E1出发，则有两个选择①至F1，②至F2，则其相应的决策为11EFG这说明，由E1至终点G的最短距离为7，其最短路线是232.2动态规划的基本思想和基本方程521615252262(,)()54()minmin5(,)()23dEFfFfEdEFfF22()suEF53615353262(,1)()64()minmin9(,)()63dEFfFfEdEFfF532()uEF同理，从E2和E3出发，则有其相应的决策为且242.2动态规划的基本思想和基本方程414124242243432()7()()6()()8()fDuDEfDuDEfDuDE31311323213333234343()13()()10()()9()()12()fCuC