第三章运输问题

第五章动态规划---DynamicProgramming2005年9月龙子泉概述一、动态规划的提出–动态规划是1951年由美国学者R.Bellman等人在解决所谓多阶段决策问题时提出的一种优化方法，从此，动态规划成为运筹学的一个重要分支。该方法在进行多阶段决策时，先将问题变换成一系列相互联系的单阶段问题，当解决了这一系列单阶段问题之后，在“最优性原理”的基础上，就可以解决整个多阶段决策问题。二、动态规划的有效性–DP在工程技术、企业管理和军事等方面多有着广泛的应用。–企业管理方面的最短路问题、生产与库存问题、资源分配问题、排序问题、设备更新问题等；–工程技术方面的水库优化调度问题、电力系统经济调度问题等。–许多问题用动态规划方法解决，比其他常用方法如线性规划或非线性规划等方法更为有效。特别是对于离散的问题，由于目标函数或约束条件难以用解析的方式表达时，此时，动态规划方法就成为非常有效的工具。三、动态规划的分类–动态规划模型的分类一般根据其状态的性质或多少来分类。而状态有离散的和连续的、有确定的和随机的、有一维的和多维的。离散确定型离散随机型连续确定型连续随机型一维动态规划模型多维动态规划模型2005年9月龙子泉一、多阶段决策过程–在生产决策中，若某一活动过程可以分为若干相互联系的阶段，每一阶段又需要作出决策，从而使整个过程达到最好的活动效果。–这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。第一节多阶段决策过程及其问题举例二、多阶段决策问题举例例5.1最短路问题如图5—2，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用、时间等），试求一条由A到E的线路，使总距离为最短（或费用最小、时间最少等）。B1AC1B2C3ED1C4C2D3D23531686673583384232图5—2例5.2生产与存储问题–假设某厂某车间每月底都要供应总装车间一定数量的部件，但由于生产条件的变化，该车间每月生产单位部件所耗费的工时不同，各月份的生产量于当月的月底以前，全部要存入仓库以备后用。已知总装车间各个月份的需求量以及在加工车间生产该部件每单位数量所需工时如表5—1所示–设库存容量H=9，开始时库存量为2，期终库存量为0，现要求制定一个半年逐月生产计划，使得既满足需求和库存容量的限制，又使总耗费的工时最少。月份k0123456月需求量dk0853274单位工时ak1118131720102005年9月龙子泉一、动态规划的基本概念（1）阶段–对于多阶段决策问题，按问题的特点可将其划分为若干个相互联系的阶段，阶段就是问题所处的地段或时段。描述阶段的变量称为阶段变量，通常用k表示。例5.1中，阶段为问题所处的地段，且k=1，2，3，4；例5.2中，阶段为问题所处的时段（月），且k=0，1，…，6；第二节动态规划的基本概念与基本方程（2）状态–状态就是在各阶段开始时问题的自然状况–描述过程状态的变量称为状态变量。通常用Sk表示第k阶段的状态集合，用sk表示第k阶段的某一具体的状态。结合例1、例2说明–动态规划状态必须满足两个条件：①能描述问题的过程②满足无后效性–所谓无后效性是指如果某阶段的状态给定以后，则在这阶段以后过程的发展不受这阶段以前各状态的影响，即过程的过去历史只能通过当前的状态去影响它的未来的发展，当前的状态是以往历史的一个总结。（3）决策–决策表示当过程处于某一阶段的某一状态时，为确定下一阶段的某一状态所作出的决定或者选择–描述决策的变量称为决策变量。通常用uk（sk）表示第k阶段在状态为sk时所作出的决策，用Dk（sk）表示第k阶段在状态为sk处所有可行决策构成的决策集合，显然有uk（sk）∈Dk（sk）；举例（4）状态转移方程–描述相邻两阶段状态与决策相互关系的方程称为状态转移方程。状态转移方程的一般形式可描述为sk+1=Tk（sk，uk），Tk称为状态转移函数；举例（5）策略–对于n阶段决策问题，从初始状态出发到终段状态的全过程中，每阶段的决策uk（sk）（k=1，2，…，n）所构成的决策序列就称为一个整体策略，简称策略。记为：p1，n（s1）=｛u1（s1），u2（s2），…，un（sn）｝–另外，称下式所描述的为后部k段子策略pk，n（sk）=｛uk（sk），uk+1（sk+1），…，un（sn）｝–称下式所描述的为前部k段子策略p1，k（s1）=｛u1（s1），u1（s1），…，uk（sk）｝–在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。允许策略集合中使问题达到最优效果的策略称为最优策略–结合例1、例2说明（6）指标函数–把描述问题优劣的数量指标与问题策略或子策略关系的函数称为指标函数。即，衡量问题的优劣必须有数量指标，而该数量指标可以是定义在问题策略或子策略上的函数，通常用Vk，n表示。即Vk，n=Vk，n(pk，n(sk))k=1，2，…，n–对于动态规划模型来说，指标函数应满足可分离性，即可以描述成sk、uk、Vk+1，n的函数。记为Vk，n(pk，n(sk))=φk[sk，uk，Vk+1，n(pk+1，n(sk+1))]（6）指标函数–动态规划的指标函数的形式一般有如下两种–①阶段指标和的形式，即过程或子过程的指标为各阶段指标的和，用公式描述如下:–②阶段指标积的形式，即过程或子过程的指标为各阶段指标的积–其中，vj（sj，uj）表示j阶段在状态为sj作出决策为uj时的指标，即所谓的阶段指标–推导两种形式的可分离性nk,nk,nkjjjj=kV(p(s))=v(s,u)nk,nk,nkjjjj=kV(p(s))=v(s,u)2005年9月龙子泉–20世纪50年代，R.Bellman等人根据研究多阶段决策问题的成果，提出了最优性原理，该原理作为动态规划的理论基础，解决了很多类型决策过程最优化问题。–动态规划规划的最优性原理描述如下：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，一个最优策略的子策略总是最优的二、动态规划最优性原理2005年9月龙子泉–根据DP原理，有DP方程形式三、动态规划基本方程Kkkkkkkkk+1k+1uD(s)n+1n+1f(s)=optv(s,u)f(s)k=n,n-1,...,1f(s)=0–式中，⊕为乘子，根据指标函数的形式分别取“+”和“×”–OPT根据问题的目标取“min”或“max”–用例1说明DP方程的含义–从DP基本概念和基本方程可归纳出动态规划的基本思想：①动态规划方法的关键在于正确地写出基本的递推关系式（基本方程）。要做到这一点，必须首先将问题的过程划分成若干个相互联系的阶段，正确地选择问题的状态变量和决策变量以及定义指标函数的具体形式，从而将一个大问题化成一簇同类型的子问题，然后逐个求解。②在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。③在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线2005年9月龙子泉一、动态规划方法解题步骤1．建立问题的动态规划模型包括划分阶段、选择问题的状态变量与决策变量、写出状态转移方程、描述问题的指标函数、列出问题的动态规划方程。2．递推计算即按第一步所描述的动态规划方程分阶段逐一计算，若问题是离散的，则，每阶段的每一个状态都要计算。3．寻找最优策略以第二步递推计算的结果为基础，以状态转移方程为纽带，按与递推计算相反的方向寻找最优策略。第三节动态规划方法解题例5.3用动态规划方法求解例1所描述的最短路问题。1．建立问题的动态规划模型①阶段：按地段划分阶段，则k=1，2，3，4；②状态：各阶段初的起始位置，用sk表示；③决策：各阶段在给定状态sk条件下的路径选择，用uk（sk）表示；④状态转移方程：sk+1=uk（sk）⑤指标函数：衡量问题优劣的数量指标为距离，指标函数的形式为各阶段指标的和，即Vk,n(=∑nj=kv(sj,uj)，其中vj（sj，uj）分别标注在图中的相应线段上。⑥动态规划方程：Kkkkkkkkk+1k+1uD(s)n+1n+1f(s)=minv(s,u)+f(s)k=4,3,2,1f(s)=02.递推计算逐步计算（板书）3.寻优板书2005年9月龙子泉二、顺序解法与逆序解法–从问题的最后阶段逐步向前进行的，因此称为动态规划的逆序解法。–某些问题的递推计算可以从前向后进行，即所谓的动态规划顺序解法。–假定阶段序数k和状态变量sk的定义不变，而uk表示第k阶段在状态为sk+1时向前作出的决定。这样问题的状态转移方程可以描述为如下形式sk=Tk‘（sk+1，uk）–动态规划顺序解法的基本方程为'Kkk+1kk+1kk+1kk-1kuD(s)01f(s)=optv(s,u)+f(s)k=1,2,...,nf(s)=02005年9月龙子泉三、静态规划的动态规划解法–对于某些静态规划问题，引入时间的因素，把它看作是按阶段进行的一个动态规划问题，这就使得动态规划成为求解一些简单的线性规划或非线性规划的有效方法。。–例5.4用动态规划发求解下列静态规划问题2123123123maxz=xxxx+x+x=c(c0)x,xx?0–解：①按变量划分阶段，即k=1，2，3；②x1、x2、x3仍然为决策变量；③状态变量为s3=x3，s2=x2+x3，s1=x1+x2+x3=c；④在上述定义的基础上，状态转移方程为：sk+1=sk－xk；⑤指标函数的形式为：其中v1(s1，x1)=x1，v2(s2，x2)=x22、v3(s3，x3)=x3；–⑥动态规划方程为–递推计算逐步板书nk,njjjj=kV=v(s,x)kkkkkkkkk+1k+1xD(s)44f(s)=maxv(s,x)f(s)k=3,2,1f(s)=1–例5.5用动态规划法求解下列静态规划问题–用动态规划法求解下列静态规划问题–递推计算和寻优逐步板书222123123123maxF=4x-x+2x+123x+2x+x9x,x,x?022212312312341maxF=y-y+2y+1294y+y+y9y,y,y?02005年9月龙子泉第四节动态规划应用一、资源分配问题（一）一维资源分配问题–问题描述设有某种资源,总数量为a,用于生产n种产品(或用于n种生产),若分配数量xi用于第i种产品,其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？–该问题的静态规划数学模型为njjj=1njj=1jmaxz=g(x)x=ax0j=1,...,n–当gi(xi)均为非线性函数时，上述问题为NLP问题，此时，若n较大时，用非线性规划方法求解很困难。–可将其看成一个多阶段决策问题，利用DP的递推关系来求解。当gi(xi)无具体解析式时，用DP方法求解更显其优越。–该问题的动态规划模型为–阶段：按生产划分阶段，k=1，…，n；–状态变量：sk表示可用于分配给第k至第n阶段（生产）的资源数量；–决策变量：xk表示可用于分配给第k阶段(生产)的资源数量；–状态转移方程：sk+1=sk－xk–允许决策集合：Dk(sk)=｛xk|0≤xk≤sk｝k=1，…，n-1；–动态规划方程kknnkkkkk+1k+10xsnnnnx=sf(s)=maxg(x)+f(s)k=n,...,1f(s)=maxg(x)–例5.6某公司现有资源A五个单位，可分配给所属甲、乙、丙三个分公司。各分公司获得不同数量的资源A可为总公司获得不同的利润，具体数据如表5—2所示。问如何分配资源A给各分公司，使总公司利润最大分公司资源A甲乙丙0123450457