运筹学动态规划PPT.ppt

动态规划
(Dynamicprogramming)动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。
需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；多阶段决策问题的典型例子：
1.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au,0<a<1。3.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。5.最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。（一）、基本概念
1、阶段：
把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。
描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。
3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。图示如下：如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。
小结:解多阶段决策过程问题，求出
1、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.
（三）、建立动态规划模型的步骤
1、划分阶段
划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。
2、正确选择状态变量
选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。
3、确定决策变量及允许决策集合
通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。4、确定状态转移方程
根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。
5、确定阶段指标函数和最优指标函数，建立动态规划基本方程
阶段指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。
例一、从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？解：整个计算过程分三个阶段，从最后一个阶段开始。
d(B1,C1)+f1(C1)3+1
f2(B1)=mind(B1,C2)+f1(C2)=min3+3
d(B1,C3)+f1(C3)1+4
4
=min6=4
5
d(B2,C1)+f1(C1)2+1
f2(B2)=mind(B2,C2)+f1(C2)=min3+3
d(B2,C3)+f1(C3)1+4
3
=min6=3
5第三阶段（A→B）：A到B有二条路线。A练习1：k=5，出发点E1、E2、E3k=4，u1(A)=B1求从A到E的最短路径现有数量为a（万元）的资金，计划分配给n个工厂,用于扩大再生产。
假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。
问题是如何确定各工厂的资金数，使得总的利润为最大。令：fk(x)=以数量为x的资金分配给前k个工厂，所得到的最大利润值。
用动态规划求解，就是求fn(a)的问题。如果a是以万元为