1动态规划1.1动态规划的发展及研究内容
动态规划（dynamicprogramming）是运筹学的一个分支，是求解决策过程（decisionprocess）最优化的数学方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优性原理（principleofoptimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《DynamicProgramming》，这是该领域的第一本著作。
例1最短路线问题
图1是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A到G距离最短（或费用最省）的路线。
例2生产计划问题
工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。
状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。
描述状态的变量称状态变量（statevariable）。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用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。
根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。描述决策的变量称决策变量（decisionvariable），变量允许取值的范围称允许决策集合（setofadmissibledecisions）。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示xk的允许决策集合。在例1中u2(B1)可取C1,C2或C3，可记作u2(1)=1,2,3，而U2(1)={1,2,3}。决策变量简称决策。
决策组成的序列称为策略（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,n1.
类似地，由第k到第j阶段的子过程的策略记作pkj(xk)={uk(xk),L,uj(xj)}.可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。
在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equationofstatetransition）表示这种演变规律，写作
xk+1=Tk(xk,uk),k=1,2,L,n.（1）
在例1中状态转移方程为xk+1=uk(xk)。
例3用lingo求解例1最短路线问题。
model:
TitleDynamicProgramming;
sets:
vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L;
road(vertex,vertex)/AB1,AB2,B1C1,B1C2,B1c3,B2C2,B2C3,B2C4,
C1D1,C1D2,C2D1,C2D2,C3D2,C3D3,C4D2,C4D3,
D1E1,D1E2,D2E2,D2E3,D3E2,D3E3,
E1F1,E1F2,E2F1,E2F2,E3F1,E3F2,F1G,F2G/:D;
endsets
data:
D=53136876
68353384
221233
35526643;
L=0,,,,,,,,,,,,,,,;
enddata
@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i)));
end
纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型：
（i）将过程划分成恰当的阶段。
（ii）正确选择状态变量xk，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合Xk。
（iii）选择决策变量uk，确定允许决策集合Uk(xk)。
（iv）写出状态转移方程。
（v）确定阶段指标vk(xk,uk)及指标函数Vkn的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。
（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。
建议大家平常多看一些关于关于建模的书籍和国赛的优秀论文，注意从中掌握什么模型适合处理什么类型的问题，多看优秀论文，借鉴写作格式，对某些问题的处理方法，以后遇到相似问题可以参考；
九层之台起于累土，千里之行始于足下，学习数模最重要的一定是打好基础，基础不牢地动山摇！
基础没有捷径，如果你想有人指导方向和学习内容，推荐参与今年的数维杯夏令，零基础入学、专家授课，参培学员获奖率达80％。不仅可以系统化深入学习建模，同时还在实战中进行训练；
扫码加群了解更多
最后就是建议大家要趁早提前准备、提前入门，积累经验增加综测分值，早日获得保研资格！