动态规划及matlab实现

动态规划

动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

主要处理离散连续型问题，特点没有特定的算法，需要具体问题具体分析，无后效性马尔科夫性，系统从某个阶段后的发展仅与本阶段所处的状态和以后的决策所做的决策所决定，与之前的状态无关。具体问题是企业管理，资源分配，路径优化，排序问题，最优控制等。

步骤思路

1.将问题转化为动态规划类型的问题

2.划分阶段

3.确定状态（若干状态）

4.决策，决策变量（描述决策变化的量），允许决策集合（决策变量的一定允许取值范围，由约束条件决定）

5.策略和允许策略集合（决策序列）全过程策略，k部子策略

6.状态转移方式，从一个状态转移到另一个状态的转移的方式

7.状态转移方程，描述状态转移过程由状态转移方程描述

8.指标函数，描述决策效果的函数

阶段指标函数（阶段效应）：描述第k步处于某状态且做出某策略时的指标

过程指标函数（目标函数）：描述第k步处于某状态且做出某策略时，目前状态距离目标状态的多少

动态规划的最优性原理

无论过去的状态跟决策如何，对前面的决策所形成的状态而言，后续决策必须构成最优策略。

对于动态规划而言，重要的并不是所谓的模板，比较重要的是在动态规划中，推导的思维方式。在个人看来动态规划实际就是编程解决大量数据的决策问题的一种重要编程理念和编程思路。

在动态规划的思路即是反向确立后三次状态改变的两次决策量的最优决策，确定了该最优决策之后每次反向推导一步，穷举倒数第三次的不同决策所带来的状态变化量，与之前所得到的的最优决策量进行加成处理（可能加和也可能相减或相乘相除，具体视情况而定），将所得后三次决策的总决策量对比选取最优值，作为后四步的最优状态变化值。先前重复推导，最终得到该问题的最优策略。

例题及基本方程

【例1】最短路线问题

图 1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由 A 到G 距离最短（或费用最省）的路线。

【例2】生产计划问题

工厂生产某种产品，每单位（千件）的成本为 1（千元），每次开工的固定成本为 3（千元），工厂每季度的最大生产能力为 6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为 0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。

动态规划的基本概念和基本方程

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

1.1 阶段

阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k = 1,2,L,n 表示。在例 1 中由 A出发为 k = 1，由 Bi(i = 1,2) 出发为 k = 2 ，依此下去从 Fi(i =1,2) 出发为 k = 6 ，共n = 6个阶段。在例 2 中按照第一、二、三、四季度分为k = 1,2,3,4，共四个阶段。

1.2 状态

状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。

描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用 xk 表示第k 阶段的状态变量，它可以是一个数或一个向量。用 Xk 表示第 k 阶段的允许状态集合。在例 1 中 x2 可取 B1,B2 ，或将 Bi 定义为i(i = 1,2) ，则 x2 = 1或2 ，而 X2 = {1,2}。n 个阶段的决策过程有n +1个状态变量，xn+1表示 xn 演变的结果。在例 1 中 x7 取 G ，或定义为1，即 x7 = 1。

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

1.3 决策

当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用uk (xk )表示第k 阶段处于状态 xk 时的决策变量，它是 xk 的函数，用Uk (xk ) 表示 xk 的允许决策集合。在例 1 中u2 (B1 ) 可取C1,C2 或C3 ，可记作u2 (1) = 1,2,3，而U2 (1) = {1,2,3}。决策变量简称决策。

1.4 策略

决策组成的序列称为策略（policy）。由初始状态 x1 开始的全过程的策略记作p1n (x1 ) ，即

p1n (x1 ) = {u1 (x1 ),u2 (x2 ),L,un (xn )}. 由第k 阶段的状态 xk 开始到终止状态的后部子过程的策略记作 pkn (xk ) ，即pkn (xk ) = {uk (xk ),L,un (xn )}，k = 1,2,L, n −1.

类似地，由第k 到第 j 阶段的子过程的策略记作pkj(xk ) = {uk (xk ),L,u j(x j)}. 可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用P1n (x1 ),Pkn (xk ),Pkj(xk ) 表示。

1.5. 状态转移方程

在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作

xk +1 = Tk (xk ,uk ),k = 1,2,L,n. （1）

在例 1 中状态转移方程为 xk +1 = uk (xk ) 。

【例3】用 lingo 求解例 1 最短路线问题。

model:

Title Dynamic Programming;

sets:

vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L;

road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4,

C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3,

D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3,

E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D;

endsets

data:

D=5 3 1 3 6 8 7 6

6 8 3 5 3 3 8 4

2 2 1 2 3 3

3 5 5 2 6 6 4 3;

L=0,,,,,,,,,,,,,,,;

enddata

@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i)));

end

纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型：

（1）将过程划分成恰当的阶段。

（2）正确选择状态变量 xk ，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合 Xk 。

（3）选择决策变量uk ，确定允许决策集合Uk (xk ) 。

（4）写出状态转移方程。

（5）确定阶段指标vk (xk ,uk ) 及指标函数Vkn 的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。

（6）写出基本方程即最优值函数满足的递归方程，以及端点条件。

2024年第九届数维杯数学建模挑战赛

2024年上半年首场高含金量数模竞赛：2024年第九届数维杯竞赛正在火热报名中！该竞赛已成为数学建模行业内仅次于国赛和美赛后的又一项全国性数模竞赛，已被众多高校列为国家级二类竞赛，在国内高校中是作为国赛大型热身、保研、综合测评、创新奖学金等评定竞赛之一。

✨允许跨校组队+获奖50%+国赛热身+万元奖金等你拿。

部分高校加分文件

获奖证书

进群领取历年真题优秀论文福利及队友大赛通知

关注微信公众号【数模乐园】，尽快报名~

竞赛安排

报名截止时间：北京时间2024年5月10日06:00

竞赛开始时间：北京时间2024年5月10日08:00

竞赛结束时间：北京时间2024年5月13日09:00

竞赛结果公示时间：2024年7月中旬或之前

参赛对象

参赛对象为在校专科生、本科生、研究生，每组参赛人数为1-3人（指导老师不列入小组总人数中，没有指导老师可写无，有指导老师可真实填写），每名同学只能参加一个小组，允许跨校组队。

赛题类型

竞赛分为研究生组、本科生组、专科生组，竞赛题目共3道（A题、B题、C题）每个参赛队从三个赛题中任选一题作答，竞赛题目一般是来源于各行业并经过简化的实际问题。

参赛费用

注册费为100元/队，费用仅用于本次竞赛的各项开支。如果需要组委会提供详细的论文评价，需要再支付100元人民币的论文点评费。(即每个参赛队支付200元人民币)可以获得一篇针对你们队论文的详评！（包括对论文模型与写作的具体评价与分析，并对参赛队伍提出可行的修改建议，助其提高应对美赛的能力。）

奖项设置

本次竞赛共评出：

1、数维杯冠名奖：3队，采用视频答辩的形式，由高校和企业专家综合评审，颁发第九届“数维杯”大学生数学建模挑战赛冠名奖获奖证书、奖杯，并提供每队1000元奖金+免费参加2024第九届数维杯大学生数学建模夏令营（成都）+学会会员。

2、数维杯创新奖：14队，采用视频答辩的形式，由高校和企业专家综合评审，颁发第九届“数维杯”大学生数学建模挑战赛“创新奖”获奖证书，每队500元奖金。

3、全国一等奖：（约5%）+获奖证书+学会会员

4、全国二等奖：（约15%）+获奖证书+学会会员

5、全国三等奖：（约30%）+获奖证书+学会会员

6、优秀奖：（若干）（凡成功提交论文的队伍）+获奖电子版证书

7、优秀组织奖：可联系组委会申请协办并组织竞赛

8、优秀指导教师奖：指导该参赛队伍荣获二等奖及以上的可颁发优秀指导老师证书(在报名时请填写好指导老师信息）

9、优秀志愿者参与方式：根据志愿者评选结果颁发相应奖励

须知：一等奖以上（含一等奖）将有机会被推荐到国内学术期刊发表，并邀请参加2024第九届数维杯大学生数学建模夏令营（成都）。