吴世涵的博客
0%

【数学建模笔记 04】数学建模的动态规划

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划是求解某类问题的一种方法，而不是一种特殊算法，没有标准的数学表达式和明确定义的一组规则。本文主要介绍动态规划的定义、典型问题、最短路线问题、生产计划问题等内容。

04. 动态规划

定义

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

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

动态规划的基本概念有：

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

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

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

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

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

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

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

如果一个问题能用动态规划方法求解，可以按下列步骤建立动态规划的数学模型：

  1. 将过程划分成恰当的阶段；
  2. 正确选择状态变量 ，确定允许状态集合 ；
  3. 选择决策变量 ，确定允许决策集合 ；
  4. 写出状态转移方程；
  5. 确定阶段指标；
  6. 写出基本方程。

典型问题

最短路线问题

状态：各段的初始位置 ；

决策：各个状态出发的走向 ；

阶段指标：相邻两段状态间的距离 ；

指标函数：阶段指标之和；

最优值函数：由 ​ 出发到终点的最短距离。

于是有基本方程：

利用该模型就可以算出最短路线。

例子

对于下图

graph LR

A[A]
B1[B1]
B2[B2]
B3[B3]
C1[C1]
C2[C2]
D[D]

A --2--> B1
A --4--> B2
A --3--> B3

B1 --7--> C1
B1 --4--> C2
B2 --3--> C1
B2 --2--> C2
B3 --6--> C1
B3 --2--> C2

C1 --3--> D
C2 --4--> D

可将其阶段划分为 。

  • 时，有允许状态集合 ；
  • 时，有允许状态集合 ；
  • 时，有允许状态集合 ；
  • 时，有允许状态集合 ；

进行逆序求解，令

则有

于是有

  • 时：

  • ​ 时：

  • 时：

  • 时：

因此可得最短距离为 9，最短路径为

生产计划问题

阶段：自然时间；

状态：每阶段开始时的存储量 ；

决策：每个阶段的产量 ；

状态转移方程： 其中 为每个阶段的需求量；

阶段指标：阶段的生产成本和储存费之和，设每阶段开工成本为 ，生产单位数量产品成本为 ，每阶段单位数量产品储存费为 ，即 指标函数：阶段指标之和；

最优值函数：从状态 出发到过程终结的最小费用，即

其中 表示过程终结时允许的存储量。

根据上述模型可解。