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

动态规划（生产和存储问题）

一、动态规划法的发展及其研究内容

动态规划是运筹学的一个分支，是求解决策过程最优化的数

学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在

研究多阶段决策过程的优化问题时，提出了著名的最优化原

理，把多阶段问题转化为一系列的单阶段问题，逐个求解

创立了解决这类过程优化问题的新方法——动态规划。1957

年出版的他的名著《DynamicProggramming》，这是该领域

的第一本著作。

动态规划问世以来，在经济管理·生产调度·工程技术

和最优控制等方面得到了广泛的应用。例如最短路线·库存

管理·资源分配·设备更新·组合·排序·装载等问题，采

用动态规划法求解比用其他方法更为简便。

二、动态规划法基本概念

一个多阶段决策过程最优化问题的动态规划模型通常包

括以下几个要素：

1．阶段

阶段（stage）是对整个过程的自然划分。通常根据时间顺

序或是空间特征来划分阶段，对于与时间，空间无关的“静

态”优化问题，可以根据其自然特征，人为的赋予“时段”

概念，将静态问题动态化，以便按阶段的顺序解优化问题。

表示。.n.…k=1.2阶段变量一般用．

1.状态

状态(state)是我们所研究的问题（也叫系统）在过个阶段

的初始状态或客观条件。它应能描述过程的特征并且具有无

后效性，即当某阶段的状态给定时，这个阶段以后的过程的

演变与该阶段以前各阶段的状态无关。通常还要求状态是可

以直接或者是间接可以观测的。描述状态的变量称为状态变

量（StateVirable）用s表示，状态变量的取值集合称为

状态集合，用S表示。变量允许取值的范围称为允许状态集

合(setofadmissblestates).用x(k)表示第k阶段的状

态变量，它可以是一个数或者是一个向量。用X(k)表示第k

阶段的允许状态集合。

n个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演

变的结果。

根据演变过程的具体情况，状态变量可以是离散的或是连续

的。为了计算方便有时将连续变量离散化，为了分析的方便

有时又将离散的变量视为连续的。

2．决策

当一个阶段的状态确定后，可以做出各种选择从而演变到下

一阶段的某个状态，这种选择手段称为决策（decision），

在最优控制问题中也称为控制（control）描述决策的变量

称为决策变量（decisionvirable）。of

set（合集策决许允为称围范的值取许允量变．阶段处于k。

用表示第admissbledecisions）的函数，用x(k)的决策变

量，它是x(k)阶段。决策变量简称合示表x(k)的允许决策

集决策。4.策略。由初始状态决策组成的系列称为策略

（policy）.

x1开始的全过程的策略记作.

开始到终止状态的后部子k由第阶段的状态x(k),

过程的策略,n-;k=2,…1.

称为允许策略集合可供选择的策略有一定的范围，,

用,polices（setofadmissble）等表示。5.状态转移

方程一旦某阶段的状态和决策为已知，在确定性过程中，

state下阶段的状态偏完全可以确定。（用状态转移方程

transferequations）表示这种演变规律，写作：

阶段指标函数6.时，当执行了决策x(k)，对于k阶段的状

态阶段的局部利k除带来系统状态的转移之外，还产生第

stage益，它是总效益的一部分，称为阶段指标函数（.

，记作effectivefuction）7.过程指标函数用来衡量策略

或者是子策略执行效果的数量指标称为，它定义在所过程指

标函数（processeffectivefuction）后部子过程上，常

用用表示，即有k,n.

…k=1,2,时，就是全过程指标函数。当k=1也就被和子策

略那么给定，如果状态x(k)的函数，记为：确定了，所以

是x(k)和常见的过程指标函数是连和形式或连积形式：

8.最优指标函数的最优值称为过程指标函数f(x(k).，记

为）fuctioneffective(optimum最优指标函数．

它表示，采取了最优子策略

之后，后部子过程所获得的总效益，表