动态规划法求解生产与存储问题

由天下分享时间：2024/9/17 4:42:24 加入收藏我要投稿点赞

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

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解

创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。

动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。二·动态规划法基本概念

一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段

阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=….n.表示。

1. 状态

状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。

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

根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策

当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（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.状态转移方程