动态规划(生产和存储问题).docx

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