数学模型动态规划

.PAGE.动态规划动态规划<dynamicprogramming>是运筹学的一个重要分支,它是解决多阶段决策问题的一种有效的数量化方法．动态规划是由美国学者贝尔曼<R．Bellman等人所创立的．1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理,并给出了许多实际问题的解法．1957年贝尔曼发表了《动态规划》一书,标志着运筹学这一重要分支的诞生．§1动态规划的概念与原理一、动态规划的基本概念引例:最短路线问题美国黑金石油公司〔TheBlackGoldPetroleumCompany最近在阿拉斯加〔Alaska的北斯洛波〔NorthSlope发现了大的石油储量。为了大规模开发这一油田,首先必须建立相应的输运网络,使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站〔结点C与装运港〔结点P1、P2、P3之间需要若干个中间站,中间站之间的联通情况如图1所示,图中线段上的数字代表两站之间的距离〔单位：10千米。试确定一最佳的输运线路,使原油的输送距离最短。解：最短路线有一个重要性质,即如果由起点A经过B点和C点到达终点D是一条最短路线,则由B点经C点到达终点D一定是B到D的最短路〔贝尔曼最优化原理。此性质用反证法很容易证明,因为如果不是这样,则从B点到D点有另一条距离更短的路线存在,不妨假设为B—P—D；从而可知路线A—B—P—D比原路线A—B—C—D距离短,这与原路线A—B—C—D是最短路线相矛盾,性质得证。根据最短路线的这一性质,寻找最短路线的方法就是从最后阶段开始,由后向前逐步递推求出各点到终点的最短路线,最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法,将此过程划分为4个阶段,即阶段变量；取过程在各阶段所处的位置为状态变量,按逆序算法求解。CCP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4图1当时：由结点M31到达目的地有两条路线可以选择,即选择P1或P2；故：选择P2由结点M32到达目的地有三条路线可以选择,即选择P1、P2或P3；故：选择P2由结点M33到达目的地也有三条路线可以选择,即选择P1、P2或P3；故：选择P3由结点M34到达目的地有两条路线可以选择,即选择P2或P3；故：选择P2当时：由结点M21到达下一阶段有三条路线可以选择,即选择M31、M32或M33；故：选择M32由结点M22到达下一阶段也有三条路线可以选择,即选择M31、M32或M33；故：选择M32或M33由结点M23到达下一阶段也有三条路线可以选择,即选择M32、M33或M34；故：选择M33或M34当时：由结点M11到达下一阶段有两条路线可以选择,即选择M21或M22；故：选择M22由结点M12到达下一阶段也有两条路线可以选择,即选择M22或M23；故：选择M22当时：由结点C到达下一阶段有两条路线可以选择,即选择M11或M12；故：选择M11从而通过顺序〔计算的反顺序追踪〔黑体标示可以得到两条最佳的输运线路：C—M11—M22—M32—P2；C—M11—M22—M33—P3。最短的输送距离是280千米。一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。1、阶段阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量,常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的,但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用表示。2、状态状态〔state表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量〔statevariable。变量允许取值的范围称允许状态集合<setofadmissiblestates>。用表示第阶段的状态变量,它可以是一个数或一个向量。用表示第阶段的允许状态集合。个阶段的决策过程有个状态变量,表示演变的结果。根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。3决策当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策〔decision,在最优控制问题中也称为控制〔control。描述决策的变量称决策变量〔decisionvariable,变量允许取值的范围称允许决策集合〔setofadmissibledecisions。用表示第阶段处于状态时的决策变量,它是的函数,用表示的允许决策集合。决策变量简称决策。4策略决策组成的序列称为策略〔policy。由初始状态开始的全过程的策略记作,即.由第阶段的状态开始到终止状态的后部子过程的策略记作,即,.类似地,由第到第阶段的子过程的策略记作.可供选择的策略有一定的范围,称为允许策略集合<setofadmissiblepolicies>,用表示。5.状态转移方程在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便完全确定。用状态转移方程〔equationofstatetransition表示这种演变规律,写作〔16.指标函数和最优值函数指标函数<objectivefunction>是衡量过程优劣的数量指标,它是定义在全过程和所有后部子过程上的数量函数,用表示,。指标函数应具有可分离性,即可表为的函数,记为并且函数对于变量是严格单调的。过程在第阶段的阶段指标取决于状态和决策,用表示。指标函数由组成,常见的形式有：阶段指标之和,即,阶段指标之积,即,阶段指标之极大〔或极小,即.这些形式下第到第阶段子过程的指标函数为。根据状态转移方程指标函数还可以表示为状态和策略的函数,即。在给定时指标函数对的最优值称为最优值函数〔optimalvaluefunction,记为,即,其中可根据具体情况取或。7最优策略和最优轨线使指标函数达到最优值的策略是从开始的后部子过程的最优策略,记作。是全过程的最优策略,简称最优策略〔optimalpolicy。从初始状态出发,过程按照和状态转移方程演变所经历的状态序列称最优轨线〔optimaltrajectory。二、基本方程：对于阶段的动态规划问题,在求子过程上的最优指标函数时,子过程与子过程有如下递推关系：〔2在上述方程中,当为加法时取；当为乘法时,取。三、最优化原理动态规划的最优化原理是美国学者R．Bellman首先提出的,其表述如下："作为整个过程的最优策略应具有这样的性质,无论过去的状态和决策如何,对于前面的决策所形成的状态而言,余下的诸决策必须构成最优策略"．也就是说最优策略的任一子策略都是最优的．最优化原理还阐述这样一个事实,对全过程的任一状态点,我们不考虑以前的决策,只保证以后的决策是最优的。显然,由于k的任意性〔k=1,2,…,n就保证了全过程的决策是最优的．最优化原理为动态规划从最后阶段的优化开始,逐步向前一阶段优化扩展直至第一阶段,从而达到全程优化的方法奠定了理论基础．§2动态规划模型的建立与求解根据动态规划的概念不难看出,在用动态规划方法解决实际问题时,必须首先明确本问题中的阶段、状态、决策、策略以及考察指标,并建立状态转移方程,然后根据k阶段最优指标的大小找出与之对应的最优子策略,直至找出问题的最优解．我们把找出实际问题中的阶段、状态、决策、策略以及考察指标,并建立状态转移方程这一过程称为建立动态规划模型．应该说建立动态规划模型是解决动态规划问题的第一步,也是非常重要的一步．模型建立的是否简捷、准确,直接关系到问题最优解的筛选及准确性,因此,建立动态规划模型是十分重要的．其步骤可归纳如下：〔1将所要解决的问题恰当地划分为若干阶段,经常是按事物发展的时间和空间来划分不同阶段,各阶段的首尾要互相衔接；〔2正确地选择状态变量,确定它在每一阶段的取值范围；这一步是形成动态模型的关键,状态变量是动态规划模型中最重要的参数。一般来说,状态变量应该具有以下三个特征：①要能够用来描述决策过程的演变特征；②满足无后效性,即若某阶段状态已经给定后,则以后过程的进展不受以前各个状态的影响,也就是说,过去的历史只通过当前的状态去影响未来的发展；③递推性,即由k阶段的状态变量及决策变量可以计算出阶段的状态变量〔3选择决策变量,确定允许决策集合。〔4正确写出状态转移方程〔5建立指标函数,一般用描述阶段效应,表示从阶段的最优子策略函数.〔6建立动态规划基本方程。对每一对,计算不同指标值．把这些指标值进行比较取出最优的一个,所谓最优是根据实际问题的需要确定指标值的最大者或最小者,即在动态规划基本方程中,,都是已知函数,最优子策略与之间是递推关系,要求出及需要先求出,这就决定了用在动态规划基本方程求最优策略是逆着阶段的顺序进行的,由k=n,n–1,…2,1将上式依次逐步递推,直至全过程的优化结束,即可求出动态规划问题的最优策略及最优指标值．称为动态规划的逆序算法。第三节动态规划方法应用一、机器负荷分配问题例1：某厂新购某种机床125台,据估计,这种设备5年后将被其他设备所代替,此机床如在高负荷状态下工作,年损坏率为,年利润为10万元；如在低负荷状态下工作,年损坏率为,年利润为6万元；问应该如何安排这些机床的生产负荷,才能使5年内获得最大的利润？解：以年为阶段,k=1,2,3,4,5取k年初完好的机床数为状态变量,以k年初投入高负荷运行的机床数为决策变量,则低负荷运行的机床数为,于是状态转移方程为：以利润为目标函数,则k年利润为：记表示从年至5年末的最大总利润。则动态规划基本方程为：下面具体求解注意到动态规划基本方程所以时当时当时当时当时即第一年到第5年末的最大利润为。在按与计算过程相反的顺序推回去,可得最优计划为年份k完好机床数高负荷机床数低负荷机床数第一年1250125第二年1000100第三年80080第四年64640第五年32320即前三年全部低负荷运转,后两年全部高负荷运转,最大利润为2790万元。二、资源分配问题所谓资源分配问题,就是将一定数量的一种或若干种资源〔如原材料、机器设备、资金、劳动力等恰当地分配给若干个使用者,以使资源得到最有效地利用。1、一维分配问题设有某种资源可用于项活动,假设资源的数量为,已知用于第项活动的资源数为时,可以得到的收益为,试确定资源的分配方案使收益最大？该问题的数学模型可以表示为当为线性函数时,该问题是线性规划问题,当为非线性函数时,该问题是非线性规划问题,如果采用非线性规划求解,比较麻烦。可以将它看成多阶段决策问题,利用动态规划求解。在应用动态规划方法处理这一类问题时,提出将资源分配给每项活动的过程看成一个阶段,每个阶段都要确定对一种活动的资源投放量,这时,状态变量可以选择阶段初所拥有的资源量,即是要在第项到第项活动间分配的资源量。决策变量选择对活动的资源投放量,决策变量的允许集合为。在选取上述状态变量和决策变量的情况下,状态转移方程为：去投放资源时的收益为指标函数,则为阶段效益指标。记表示从阶段至阶段的最大总利润。则动态规划基本方程为：例2：某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造,各工厂获得投资后年利润将有相应的增长,增长额如表1所示。试确定500万元资本的分配方案,以使公司总的年利润增长额最大。表1投资额100万元200万元300万元400万元500万元甲307090120130乙50100110110110丙4060110120120解：将问题按工厂分为三个阶段,设状态变量〔代表从第个工厂到第3个工厂的投资额,决策变量代表第个工厂的投资额。于是有状态转移方程为、允许决策集合和递推关系式：当时：于是有表2,表中表示第三个阶段的最优决策。表2〔单位：百万元01234501234500.40.61.11.21.2当时：于是有表3。表3〔单位：百万元u2x201234500+00010+0.40.5+00.5120+0.60.5+0.41.0+01.0230+1.10.5+0.61.0+0.41.1+01.4240+1.20.5+1.11.0+0.61.1+0.41.1+01.61,250+1.20.5+1.21.0+1.11.1+0.61.1+0.41.1+02.12当时：于是有表4。表4u1x101234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10,2然后按计算表格的顺序反推算,可知最优分配方案有两个：〔1甲工厂投资200万元,乙工厂投资200万元,丙工厂投资100万元；〔2甲工厂没有投资,乙工厂投资200万元,丙工厂投资300万元。按最优分配方案分配投资〔资源,年利润将增长210万元。这个例于是决策变量取离散值的一类分配问题,在实际问题中,相类似的问题还有销售店的布局〔分配问题、设备或人力资源的分配问题等。2、二维分配问题〔1设数量分别为的两种资源分配给个使用者,求总收益最大的分配方案该问题的数学模型可以表示为〔2二维分配问题的解法1、逐次逼近法由于①设②③轮转若干步,直到满足精确度要求。2、拉格郎日乘子法〔1估计一个拉格郎日乘子〔2用动态规划法解一维问题若解不唯一,假设共有个〔3计算〔4判断①若存在②若③若④若三、存贮控制问题在动态规划模型中,以时期为阶段,取各时期初的库存量为状态变量;取各阶段的产量<或采购量>为决策变量,在确定决策变量时一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产或采购费用。例3：某工厂要制定今后四个时期某产品的生产计划,估计今后四个时期内市场对该产品的需求如下表时期k1234需求量dk2324假设该厂生产每批产品的固定费用为2千元,若不生产为0；每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每个时期最大生产能力所允许的生产批量不超过5个单位；最大库存量为4个单位；假设开始时库存量为1个单位,要求第四期末库存在2个单位。试问该厂应如何