动态规划生产和存储问题.doc

动态规划(生产和存储问题)一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。,提出了著名的最优化原理,把多阶段问题转化为一系列的单阶段问题,逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《DynamicProggramming》,这是该领域的第一本著作。动态规划问世以来,在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题,采用动态规划法求解比用其他方法更为简便。二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素:(stage)是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段,对于与时间,空间无关的“静态”优化问题,可以根据其自然特征,人为的赋予“时段”概念,将静态问题动态化,以便按阶段的顺序解优化问题。表示。.n.…k=(state)是我们所研究的问题(也叫系统)在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性,即当某阶段的状态给定时,这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量(StateVirable)用s表示,状态变量的取值集合称为状态集合,用S表示。变量允许取值的范围称为允许状态集合(setofadmissblestates).用x(k)表示第k阶段的状态变量,它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。n个阶段的决策过程有n+1个状态变量,x(n+1)是x(n)的演变的结果。根据演变过程的具体情况,状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化,为了分析的方便有时又将离散的变量视为连续的。,可以做出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策(decision),在最优控制问题中也称为控制(control)描述决策的变量称为决策变量(decisionvirable)。ofset(。用表示第admissbledecisions)的函数,用x(k)的决策变量,它是x(k)阶段。决策变量简称合示表x(k)的允许决策集决策。。由初始状态决策组成的系列称为策略(policy).(k),过程的策略,n-;k=2,…,,用,polices(setofadmissble)等表示。,在确定性过程中,state下阶段的状态偏完全可以确定。(用状态转移方程transferequations)表示这种演变规律,写作:,当执行了决策x(k),对于k阶段的状态阶段的局部利k除带来系统状态的转移之外,还产生第stage益,它是总效益的一部分,称为阶段指标函数(.,记作effectivefuction),它定义在所过程指标函数(processeffectivefuction)后部子过程上,常用用表示,即有k,n.…k=1,2,时,就是全过程指标函数。当k=1也就被和子策略那么给定,如果状态x(k)的函数,记为:确定了,所以是x(k)和常见的过程指标函数是连和形式或连积形式:(x(k).,记为)fuctioneffective(,采取了最优子策略之后,后部子过程所获得的总效益,表示为:中式可以根据具体问意为最优化,optimizationopt是的缩写,min或题去max三·动态规划法的最优性原理和基本函数方程“作为整个在动态规划中起核心作用的是最优性原理:过程的最优策略具有这样的性质,无论过去的状态和决策如何,相对于前面决策所形成的状态而言,余下的决策系列必须构成最优子策略。”动态规划解法的关键在于给出一种递推关系,一般把这种关系称为基本函数方程,注意到无后效性,最优指标函数为以后不x(n+1)是整个决策过程的终止状态,当k=n时,由于再做出决策,因此,这样就得到了可以用来递推的基本函数方程:f(x(n+1))=,可以得到乘法形式的基本函数方程:f(x(n+1))=、建立动态规划模型的基本步骤阶段;;;