当前位置:首页 > 商业/管理/HR > 信息化管理 > 数学建模案例分析最优化方法建模6动态规划模型举例
§6动态规划模型举例以上讨论的优化问题属于静态的,即不必考虑时间的变化,建立的模型——线性规划、非线性规划、整数规划等,都属于静态规划。多阶段决策属于动态优化问题,即在每个阶段(通常以时间或空间为标志)根据过程的演变情况确定一个决策,使全过程的某个指标达到最优。例如:(1)化工生产过程中包含一系列的过程设备,如反应器、蒸馏塔、吸收器等,前一设备的输出为后一设备的输入。因此,应该如何控制生产过程中各个设备的输入和输出,使总产量最大。(2)发射一枚导弹去击中运动的目标,由于目标的行动是不断改变的,因此应当如何根据目标运动的情况,不断地决定导弹飞行的方向和速度,使之最快地命中目标。(3)汽车刚买来时故障少、耗油低,出车时间长,处理价值和经济效益高。随着使用时间的增加则变得故障多,油耗高,维修费用增加,经济效益差。使用时间俞长,处理价值也俞低。另外,每次更新都要付出更新费用。因此,应当如何决定它每年的使用时间,使总的效益最佳。动态规划模型是解决这类问题的有力工具,下面介绍相关的基本概念及其数学描述。(1)阶段整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段,描述阶段的变量称为阶段变量,记为k。(2)状态状态表示每个阶段开始时所处的自然状况或客观条件,它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用kx表示第k阶段的状态变量。n个阶段的决策过程有1n个状态。用动态规划方法解决多阶段决策问题时,要求整个过程具有无后效性。即:如果某阶段的状态给定,则此阶段以后过程的发展不受以前状态的影响,未来状态只依赖于当前状态。(3)决策某一阶段的状态确定后,可以作出各种选择从而演变到下一阶段某一状态,这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用)(kkxu表示第k阶段处于状态kx时的决策变量,它是kx的函数,用)(kkxD表示kx的允许决策集合。(4)策略一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k阶段的状态kx开始到终止状态的后部子过程的策略记为)}(,),(),({)(11nnkkkkkkxuxuxuxp。在实际问题中,可供选择的策略有一定范围,称为允许策略集合。其中达到最优效果的策略称为最优策略。(5)状态转移方程如果第k个阶段状态变量为kx,作出的决策为ku,那么第1k阶段的状态变量1kx也被完全确定。用状态转移方程表示这种演变规律,写作(1kkTxkx,)ku(6)最优值函数指标函数是系统执行某一策略所产生结果的数量表示,是用来衡量策略优劣的数量指标,它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。下面的方程在动态规划逆序求解中起着本质的作用。1,,1,),,(,0)()],())(,([min)(11111)(nnkuxTxxfxfxuxvxfkkkknnkkkkkkxDukkkkk称此为动态规划逆序求解的基本方程(贝尔曼方程)。可以把建立动态规划模型归纳成以下几个步骤:(1)将问题恰当地划分为若干个阶段;(2)正确选择状态变量,使它既能描述过程的演变,又满足无后效性;(3)规定决策变量,确定每个阶段的允许决策集合;(4)写出状态转移方程;(5)确定各阶段各种决策的阶段指标,列出计算各阶段最优后部策略指标的基本方程。下面结合具体例子阐述建立动态规划模型的思路。例13生产计划问题。公司要对某产品制定n周的生产计划,产品每周的需求量、生产和贮存费用、生产能力的限制、初始库存量等都是已知的,试在满足需求的条件下,确定每周的生产量,使n周的总费用最少。决策变量是第k周的生产量,记作),,2,1(nkuk。已知下列数据及函数关系:第k周的需求量kd:第k周产量为ku时的生产费为)(kkuc;第k周初贮存量为kx时这一周的贮存费为)(kkxh;第k周的生产能力限制为kU;初始(0k)及终结(nk)时贮存量均为零。按照最短路问题的思路,设从第k周初贮存量为kx到(n周末)过程结束的最小费用函数为)(kkxf,则下列逆向递推公式成立。0)(1,2,,)]()()([min)(11110nnkkkkkkkkUukkxfnkXxxfxhucxfkk,(1)而kx与1kx满足012,,111nkkkkxxnkduxx,,(2)这里贮存量kx是状态变量,(2)式给出了相邻阶段的状态在决策变量作用下的转移规律,称为状态转移规律。在用(1)式计算时,kx的取值范围——允许状态集合kX由(2)式及允许决策集合)0(kkUu决定。在实际问题中,为简单起见,生产费用常取)(kkuc,0ku;kkkcuauc)(,0ku,其中c是单位产品生产费,而a是生产准备费。贮存费用常取kkkhxxh)(,h是单位产品(一周的)贮存费。最优方程(1)和状态转移方程(2)构成了这个多阶段决策问题的动态规划模型。实际上,多阶段决策问题有时也可用静态规划方法求解,如例2的生产计划问题。例14资源分配问题。总量为1m的资源A和总量为2m的资源B同时分配给n个用户,已知第k用户利用数量ku的资源A和数量kv的资源B时,产生的效益为),(kkkvug,问如何分配现有资源使总效益最大。这本来是个典型的静态规划问题:nkkkkvugZMax1),((1)nkkkumuts110,..(2)nkkkvmv120,(3)但是当kg比较复杂及n较大时,用非线性规划求解是困难的,特别是,若kg是用表格或图形给出而无解析表达式时,则难以求解。而这种情况下,将其转化为动态规划,是一种可行的方法。资源A,B每分配给一个用户划分为一个阶段,分配给第k用户的数量是二维决策变量),(kkvu,而把向第k用户分配之前,分配者手中掌握的资源数量作为二维状态变量,记作),(kkyx,这样,状态转移方程应为kkkkkkvyyuxx11(4)最优值函数),(kkkyxf定义为将数量),(kkyx的资源分配给第k至第n用户时能获得的最大效益,它满足最优方程0)0,0(1,2,,,0,0)],,(),([max),(12111100nkkkkkkkkyvxukkkfnkmymxyxfvugyxfkkkk(5)对于由(4),(5)式构成的动态规划模型,不需要),(kkkvug,),(kkkyxf的解析表达式,完全可以求数值解。例15系统可靠性问题。一个系统由若干部件串联而成,只要有一个部件故障,系统就不能正常运行。为提高系统的可靠性,每个部件都装置备用件,一旦原部件故障,备用件就自动进入系统。显然,备用件越多,系统可靠性越高,但费用也越大,那么在一定的总费用限制下,如何配置各部件的备用件,使系统的可靠性最高呢?设系统有n个部件,当部件k装置ku个备用件时,这个部件正常工作的概率为)(kkup。而每个备用件的费用为kc,另外设总费用不应超过C。这个优化问题的目标函数是系统正常运行的概率,它等于n个串联部件正常工作的概率的乘积。约束条件是备用件费用之和不应超过C,决策变量是各部件的备用件数量,于是问题归结为nkkkupZMax1)((1)nkkkkuCucts1,..为非负整数(2)这个非线性规划转化为动态规划求解比较方便。按照对n个部件装置备用件的次序划分阶段,决策变量仍为部件k的备用件数量ku,而状态变量选取装配部件k之前所容许使用的费用,记作kx,于是状态转移方程为kkkkucxx1(3)最优值函数)(kkxf定义为状态kx下,由部件k到部件n组成的子系统的最大正常工作概率,它满足)]()([)(11)(kkkkxUukkxfupMaxxfkkk(4)],/c,0[{)(kkxuuxUkkkk且为正整数},12,0,,,nkCxk1)(11nnxf(5)注意,这个动态规划模型的最优方程(4)中,阶段指标)(kkup与最优值函数)(11kkxf之间的关系是相乘,而不是例13~15中的相加,这是由“两事件之交的概率等于两事件概率之积”这一性质决定的。与此相应,最优值函数的初始条件1)(11nnxf等于1。例16任务均衡问题。一批任务由若干设备完成,问题是如何均衡地向每个设备分配各项任务,使这批任务尽早地完成。例如一高层(设N层)办公大楼有n部性能相同的电梯,为了在早高峰期间尽快地将乘客送到各层的办公室,决定各部电梯分段运行,即每部电梯服务一定的层段。假定根据统计资料,已知一部电梯从第i层次开始服务j层所需要的时间为ijt,问如何安排这些电梯服务的层段,使送完全部乘客的时间最短。按照由下而上安排电梯服务层次的序号划分阶段nk,,2,1。第k部电梯(即第k阶段)开始服务的层次为状态kx,它服务的层数为决策ku,满足kkkuxx1(1)当ixk,juk时,已知第k部电梯服务的时间为ijkkktuxv),(。因为对于第lk,两部电梯而言,总的服务时间为)],(),,([lllkkkuxvuxvMax,所以最优值函数)(kkxf(即从第k部到第n部电梯总的最短服务时间)满足)]}(),,({max[min)(11)(kkkkkxUukkxfuxvxfkkk}1)(,,2,1|{)(knxNuuxUkkkkk1,2,,,,3,2nkNxk(2)0)1(1nfn(3)这里我们假定每部电梯至少服务1层,且从第2层起开始服务。应用动态规划方法求解多阶段决策问题分为两个步骤。第一是应用动态规划基本方程,逆序地求出条件最优目标函数值集合和条件最优决策集合。第二是顺序地求出最优决策序列。下面以一个例子加以说明。例17机器负荷分配问题。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时,每台机器生产产品的年产量为7吨,年折损率7.0a(即若年初完好的机器有u台,则年终完好的机器数为au台),在低负荷下生产时,每台机器生产产品的年产量为5吨,年折损率9.0b。若开始时完好的机器数有10001x台,要求制定一个三年计划,在每年开始时,决定如何重新分配在两种不同的负荷下生产的完好机器数,使在三年内产品的总产量达到最大。设第k年初完好的机器数为kx,分配给高负荷下生产的机器数为ku,即在低负荷下生产的机器数为kx-ku。这里ku、kx可取非负实数,如7.0kx表示第k年度一台机器正常工作时间只占7.0。于是第1k年初完好的机器数kkkkkkuxuxux2.09.0)(9.07.01第k年度的产量kkkkkkkkuxuxuuxv25)(57),(设三年总产量为V,则问题即求解下面的线性规划问题:31)25(kkkuxVMax1000..1xts3,2,1,0,2.09.01kxuuxxkkkkk现用动态规划来解。本题要求的是已知第一年度初拥有的完好机器数10001x台,用最优方案到第三年度末这段期间的产品产量,将它记为)(11xf。为此先求:已知第j年度初拥有的完好机器数jx,用最优方案到第三年末这段期间的产品产量,将它记为3,2),(jxfjj,列出动态规划的基本方程0)(3,2,1,2.09.0)](),([)(441110xfkuxxxfuxvMaxxfkkkkkkkkxukkkk求解过程如下:)](),([)(4433303333xfuxvMaxxfxu(1)即)52()(3303333xuMaxxfxu,得最优解3*3xu,从而3337)(xxf。)](),([)(3322202222xfuxvMaxxfxu(2)即)]2.09.0(752[)(222202222uxxuMaxxfxu)3.116.0(22022xuMaxxu,得最优解2*2xu,从而2229.1
本文标题:数学建模案例分析最优化方法建模6动态规划模型举例
链接地址:https://www.777doc.com/doc-2426940 .html