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

动态规划是求解某类问题的一种方法，而不是一种特殊算法，没有标准的数学表达式和明确定义的一组规则。

动态规划的基本概念有：

• 阶段：对整个过程的自然划分，阶段变量一般用 表示；

• 状态：每个阶段开始时过程所处的自然状况，用 表示第 阶段的状态变量，用 表示第 阶段的允许状态集合；

• 决策：一个阶段的状态确定后，作出各种选择从而演变到下一阶段的某个状态，用 ​ 表示第 ​ 阶段处于状态 ​ 时的决策变量，用 表示 的允许决策集合；

• 策略：决策组成的序列。由第 到第 ​ 阶段的子过程策略记

• 状态转移方程：表示状态和决策确定下一状态的演变规律，记

• 指标函数：衡量过程优劣的数量指标，记

• 最优值函数：使指标函数达到最优，记 其中 可取 或 。

03. 非线性规划

定义

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。

非线性规划目前还没有适于各种问题的一般算法。

非线性规划模型描述如：

其中 ，而 都是实值函数。

一般非线性规划只能得到局部最优解，不能保证是全局最优解。

规划中的变量 (部分或全部) 限制为整数时，称为整数规划。

若在线性规划模型中变量限制为整数，则称为整数线性规划。

分类：

• 变量全限制为整数时，称纯 (完全) 整数规划；
• 变量部分限制为整数时，称混合整数规划。

线性规划，就是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

线性规划由三部分组成：

• 决策变量
• 目标函数
• 约束条件

形式

编程中，线性规划的标准形式为：

其中 为 ​ 维列向量， 为适当维数的矩阵， 为适当维数的列向量。