第三章运输问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2005年9月 龙子泉,第五章 动态规划,-,Dynamic Programming,概 述,一、动态规划的提出,动态规划是1951年由美国学者R.Bellman等人在解决所谓多阶段决策问题时提出的一种优化方法，从此，动态规划成为运筹学的一个重要分支。该方法在进行多阶段决策时，先将问题变换成一系列相互联系的单阶段问题，当解决了这一系列单阶段问题之后，在“最优性原理”的基础上，就可以解决整个多阶段决策问题。,二、动态规划的有效性,DP在工程技术、企业管理和军事等方面多有着广泛的应用。,企业管理方面的最短路问题、生产与库存问题、资源分配问题、排序问题、设备更新问题等；,工程技术方面的水库优化调度问题、电力系统经济调度问题等。,许多问题用动态规划方法解决，比其他常用方法如线性规划或非线性规划等方法更为有效。特别是对于离散的问题，由于目标函数或约束条件难以用解析的方式表达时，此时，动态规划方法就成为非常有效的工具。,三、动态规划的分类,动态规划模型的分类一般根据其状态的性质或多少来分类。而状态有离散的和连续的、有确定的和随机的、有一维的和多维的。,离散确定型,离散随机型,连续确定型,连续随机型,一维动态规划模型,多维动态规划模型,一、多阶段决策过程,在生产决策中，若某一活动过程可以分为若干相互联系的阶段，每一阶段又需要作出决策，从而使整个过程达到最好的活动效果。,这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为,多阶段决策过程,，这种问题就称为,多阶段决策问题,。,第一节 多阶段决策过程及其问题举例,二、多阶段决策问题举例,例5.1 最短路问题,如图52，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用、时间等），试求一条由A到E的线路，使总距离为最短（或费用最小、时间最少等）。,B,1,A,C,1,B,2,C,3,E,D,1,C,4,C,2,D,3,D,2,3,5,3,1,6,8,6,6,7,3,5,8,3,3,8,4,2,3,2,图52,例5.2 生产与存储问题,假设某厂某车间每月底都要供应总装车间一定数量的部件，但由于生产条件的变化，该车间每月生产单位部件所耗费的工时不同，各月份的生产量于当月的月底以前，全部要存入仓库以备后用。已知总装车间各个月份的需求量以及在加工车间生产该部件每单位数量所需工时如表51所示,设库存容量H=9，开始时库存量为2，期终库存量为0，现要求制定一个半年逐月生产计划，使得既满足需求和库存容量的限制，又使总耗费的工时最少,。,月 份 k,0,1,2,3,4,5,6,月需求量 d,k,0,8,5,3,2,7,4,单位工时 a,k,11,18,13,17,20,10,一、动态规划的基本概念,（1）阶段,对于多阶段决策问题，按问题的特点可将其划分为若干个相互联系的阶段，阶段就是问题所处的地段或时段。描述阶段的变量称为阶段变量，通常用k表示。例5.1中，阶段为问题所处的地段，且k=1，2，3，4；例5.2中，阶段为问题所处的时段（月），且k=0，1，6；,第二节,动态规划的基本概念与基本方程,（2）状态,状态,就是在各阶段开始时问题的自然状况,描述过程状态的变量称为状态变量。通常用S,k,表示第k阶段的状态集合，用s,k,表示第k阶段的某一具体的状态。,结合例1、例2说明,动态规划状态必须满足两个条件：,能描述问题的过程,满足,无后效性,所谓无,后效性,是指如果某阶段的状态给定以后，则在这阶段以后过程的发展不受这阶段以前各状态的影响，即过程的过去历史只能通过当前的状态去影响它的未来的发展，当前的状态是以往历史的一个总结。,（3）决策,决策表示当过程处于某一阶段的某一状态时，为确定下一阶段的某一状态所作出的决定或者选择,描述决策的变量称为决策变量。通常用,u,k,（,s,k,）表示第k阶段在状态为s,k,时所作出的决策，用D,k,（s,k,）表示第k阶段在状态为s,k,处所有可行决策构成的决策集合，显然有,u,k,（,s,k,）D,k,（s,k,）；,举例,（4）状态转移方程,描述相邻两阶段状态与决策相互关系的方程称为,状态转移方程,。状态转移方程的一般形式可描述为s,k+1,=T,k,（s,k,，u,k,），T,k,称为状态转移函数；,举例,（5）策略,对于n阶段决策问题，从初始状态出发到终段状态的全过程中，每阶段的决策u,k,（s,k,）（k=1，2，n）所构成的决策序列就称为一个,整体策略,，简称,策略,。记为：,p,1，n,（s,1,）=u,1,（s,1,），u,2,（s,2,），u,n,（s,n,）,另外，称下式所描述的为,后部k段子策略,p,k，n,（s,k,）=u,k,（s,k,），u,k+1,（s,k+1,），u,n,（s,n,）,称下式所描述的为,前部k段子策略,p,1，k,（s,1,）=u,1,（s,1,），u,1,（s,1,），u,k,（s,k,）,在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。允许策略集合中使问题达到最优效果的策略称为,最优策略,结合例1、例2 说明,（6）指标函数,把描述问题优劣的数量指标与问题策略或子策略关系的函数称为,指标函数,。即，衡量问题的优劣必须有数量指标，而该数量指标可以是定义在问题策略或子策略上的函数，通常用V,k，n,表示。即,V,k，n,=V,k，n,(p,k，n,(s,k,)k=1，2，n,对于动态规划模型来说，指标函数应满足,可分离性,，即可以描述成s,k,、u,k,、V,k+1，n,的函数。记为,V,k，n,(p,k，n,(s,k,)=,k,s,k,，u,k,，V,k+1，n,(p,k+1，n,(s,k+1,),（6）指标函数,动态规划的指标函数的形式一般有如下两种,阶段指标和的形式，即过程或子过程的指标为各阶段指标的和，用公式描述如下:,阶段指标积的形式，即过程或子过程的指标为各阶段指标的积,其中，v,j,（s,j,，u,j,）表示j阶段在状态为s,j,作出决策为u,j,时的指标，即所谓的,阶段指标,推导两种形式的可分离性,20世纪50年代，R.Bellman 等人根据研究多阶段决策问题的成果，提出了最优性原理，该原理作为动态规划的理论基础，解决了很多类型决策过程最优化问题。,动态规划规划的,最优性原理,描述如下：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”,简言之，一个最优策略的子策略总是最优的,二、动态规划最优性原理,根据DP原理，有DP方程形式,三、动态规划基本方程,式中，为乘子，根据指标函数的形式分别取“+”和“”,OPT,根据问题的目标取“,min”,或“,max”,用例1说明,DP,方程的含义,从DP基本概念和基本方程可归纳出动态规划的,基本思想,：,动态规划方法的关键在于正确地写出基本的递推关系式（基本方程）。要做到这一点，必须首先将问题的过程划分成若干个相互联系的阶段，正确地选择问题的状态变量和决策变量以及定义指标函数的具体形式，从而将一个大问题化成一簇同类型的子问题，然后逐个求解。,在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。,在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线,一、动态规划方法解题步骤,1建立问题的动态规划模型,包括划分阶段、选择问题的状态变量与决策变量、写出状态转移方程、描述问题的指标函数、列出问题的动态规划方程。,2递推计算,即按第一步所描述的动态规划方程分阶段逐一计算，若问题是离散的，则，每阶段的每一个状态都要计算。,3寻找最优策略,以第二步递推计算的结果为基础，以状态转移方程为纽带，按与递推计算相反的方向寻找最优策略。,第三节,动态规划方法解题,例5.3 用动态规划方法求解例1所描述的最短路问题。,1建立问题的动态规划模型,阶段：按地段划分阶段，则k=1，2，3，4；,状态：各阶段初的起始位置，用s,k,表示；,决策：各阶段在给定状态s,k,条件下的路径选择，用u,k,（s,k,）表示；,状态转移方程：s,k+1,=u,k,（s,k,）,指标函数：衡量问题优劣的数量指标为距离，指标函数的形式为各阶段指标的和，即V,k,n,(=,n,j=k,v(s,j,u,j,)，其中v,j,（s,j,，u,j,）分别标注在图中的相应线段上。,动态规划方程：,2.递推计算,逐步计算（板书）,3.寻优,板书,二、顺序解法与逆序解法,从问题的最后阶段逐步向前进行的，因此称为动态规划的逆序解法。,某些问题的递推计算可以从前向后进行，即所谓的动态规划顺序解法。,假定阶段序数,k,和状态变量,s,k,的定义不变，而,u,k,表示第,k,阶段在状态为,s,k,+1,时向前作出的决定。这样问题的状态转移方程可以描述为如下形式,s,k,=,T,k,（,s,k,+1,，,u,k,）,动态规划顺序解法的基本方程为,三、静态规划的动态规划解法,对于某些静态规划问题，引入时间的因素，把它看作是按阶段进行的一个动态规划问题，这就使得动态规划成为求解一些简单的线性规划或非线性规划的有效方法。,例5.4 用动态规划发求解下列静态规划问题,解：,按变量划分阶段，即,k=1，2，3；,x,1,、,x,2,、,x,3,仍然为决策变量；,状态变量为,s,3,=,x,3,，,s,2,=,x,2,+,x,3,，,s,1,=,x,1,+,x,2,+,x,3,=,c,；,在上述定义的基础上，状态转移方程为：,s,k,+1,=,s,k,x,k,；,指标函数的形式为：,其中,v,1,(s,1,，x,1,)=x,1,，v,2,(s,2,，x,2,)=x,2,2,、v,3,(s,3,，x,3,)=x,3,；,动态规划方程为,递推计算,逐步板书,例5.5 用动态规划法求解下列静态规划问题,用动态规划法求解下列静态规划问题,递推计算和寻优,逐步板书,第四节 动态规划应用,一、资源分配问题,（一）一维资源分配问题,问题描述 设有某种资源,总数量为a,用于生产n种产品(或用于n种生产),若分配数量x,i,用于第i种产品,其收益为g,i,(x,i,)问应如何分配，才能使生产n种产品的总收入最大？,该问题的静态规划数学模型为,当g,i,(x,i,)均为非线性函数时，上述问题为NLP问题，此时，若n较大时，用非线性规划方法求解很困难。,可将其看成一个多阶段决策问题，利用DP的递推关系来求解。当g,i,(x,i,)无具体解析式时，用DP方法求解更显其优越。,该问题的动态规划模型为,阶段,：按生产划分阶段，k=1，n；,状态变量,：s,k,表示可用于分配给第k至第n阶段（生产）的资源数量；,决策变量,：x,k,表示可用于分配给第k阶段(生产)的资源数量；,状态转移方程,：s,k+1,=s,k,x,k,允许决策集合,：D,k,(s,k,)=x,k,|0 x,k,s,k,k=1，n-1；,动态规划方程,例5.6,某公司现有资源A五个单位，可分配给所属甲、乙、丙三个分公司。各分公司获得不同数量的资源A可为总公司获得不同的利润，具体数据如表52所示。问如何分配资源A给各分公司，使总公司利润最大,分公司,资源,A,甲,乙,丙,0,1,2,3,4,5,0,45,70,90,105,120,0,20,45,75,110,150,0,50,70,80,100,130,解：,（1）建立其动态规划数学模型,阶段：按分公司划分阶段，k=1，2，3（分别代表分公司甲、乙、丙）；,状态变量：s,k,表示可用于分配给第k至第3阶段（分公司）的资源A的数量；,决策变量：x,k,表示可用于分配给第k阶段的资源A的数量；,状态转移方程：s,k+1,=s,k