第七章动态规划方法建模
动态规划是由理查德·贝尔曼（Richard Bellman）所建立的，它是解最优化问题的一个特殊“技术”.我们这里用“技术”，是因为动态规划不是一个或一种特殊算法.
7.1动态规划的基本概念
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果.因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展.当各个阶段决策确定后，就组成了一个决策序列，因此也就决定了整个过程的一条活动路线.这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图7.1）就称为多阶段决策过程，也称序贯决策过程.这种问题就称为多阶段决策问题.
在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理.
涉及到动态规划，总会有下面几个概念：
7.1.1动态规划的基本概念
（１）阶段
把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解.描述阶段的变量称为阶段变量，常用k表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.
（２）状态
状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合.用一个变量i S 来描述在第i 个阶段的状态集合上的取值，此变量i S 称为状态变量（如7.2节中最短路问题中的i S ，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数λ）.
这里所说的状态是具体的属于某阶段的，它应具备下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的总结.这个性质称为无后效性，也称马尔可夫（Markov ）性.如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求.所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意到是否满足无后效性的要求.如果状态的某种规定方式可能导致不满足无后效性，则应适当地改变状态的规定方法，达到能使它满足无后效性的要求.
（３）决策
决策表示当过程处于某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策.在最优控制中也称为控制（只有它才是我们能够控制的）.描述决策的变量称为决策变量.它可以用一个数、一组数或一个向量来描述.常用
)(k k s u 表示第k 阶段当状态处于k s 时的决策变量，它是状态或状态变量的函数（可能是向
量值函数或多值函数）.在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合.常用)(k k s D 表示第k 阶段当状态处于k s 出发的允许决策集合，显然有
)()(k k k k s D s u ∈.例如，在最短路问题中，{}98726252,)()()(v v v D v D v D ===.
（４）策略
策略是一个按顺序排列的决策组成的集合.由过程的第k 阶段开始到终止状态为止的过程，称为问题的后部子过程.由每段的决策按顺序排列组成的决策函数序列称为子策略，记为
{})(,),(),()(11,n n k k k k k n k s u s u s u s p ++=
当1=k 时，此决策函数序列即为一个策略.
{})(,),(),()(2211,1n n k n s u s u s u s p =
在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合.从允许策略集合中找到达到最优效果的策略称为最优策略.
（５）状态转移方程
状态转移方程式确定过程有一个状态到另一个状态的演变过程.若给定第k 阶段状态
k s 和该阶段的决策变量)(k k s u ，则第1+k 阶段的状态1+k s 也就完全确定.即1+k s 的值随k
s 和)(k k s u 的值变化而变化.这种确定的对应关系，记为))(,(1k k k k k s u s T s =+，它描述了由
第k 阶段到第1+k 阶段的状态转移规律，称为状态转移方程.k T 称为状态转移函数.例如，在最短路问题中，状态转移方程为)(1k k k s u s =+.
（６）指标函数和最优值函数
用来衡量所实现过程优劣的数量指标，称为指标函数.它是定义在全过程和所有后部子过程上确定的函数.对于要构成动态规划模型的指标函数，应具有可分性，并满足递推关系（详见文献［５］），在实际问题中，很多指标函数都满足此性质.
指标函数的最优值，称为最优值函数.根据问题，取min 或max 之一.
在动态规划模型中，总会出现一个或一组递推关系，我们把它称为动态规划的基本方程. 7.1.2 动态规划方法的基本思想
现将动态规划方法的基本思想归纳如下：
一、动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件（基本方程）.要做到这一点，必须先将问题的整个过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解.即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解.
二、在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法.因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.
三、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优策略.
动态规划的理论基础叫做动态规划的最优化原理，它是这样描述的：
作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优策略.简言之，一个最优策略的子策略总是最优的.
动态规划的优劣： 优点：
（1）易于确定全局最优解.因为它求解的全是一维问题，所以容易确定. （2）能得到一族（全部的）最优解，有利于分析结果. （3）能利用经验，提高求解效率. 缺点：
（1）到目前为止，没有一个统一的标准模型可供应用.由于问题的不同，有时要将问题转化成满足条件（无后效性、目标函数的可分性）的多阶段决策过程是非常困难的，需要丰富的想象力和灵活的技巧.
（2）应用的局限性.“无后效性”条件的限制，降低了动态规划的通用性.
（3）在数值计算时，存在所谓的“维数灾难”.当阶段数目较多且每一阶段的允许状态也较多时，计算成本变得非常昂贵，有时使得计算不可能进行下去.在二维或三维动态规划
中，问题显得更加突出.
7.2最短路问题
问题：某人想进行一次旅行.他住在城市1，而希望到达城市10，见图7.2.这是一次长途的旅行，而且他还必须进行三次中间停留.对他旅行中的三个中间停留站的每一站，
都有两到三个不同的城市可供他选择.选择不同的中间站，旅行的花费是不同的.两城市之间的花费以及连接示于图7.2中.由于他希望为这次旅行付出的总花费达到最小，他将确定哪些城市作为他的中间站，显然，它可以用枚举法来解决此问题，总的可能的路线有18条（3×3×2＝18）.但问题肯定有更好的解法，下面我们用更好的方法来解决此问题.
我们从终点（城市10）逆序来分析这个问题.
第一步：若我们处在第3站，可通过城市8或城市9到达城市10.可用表7.2.1（1）说明：
表7.2.1（1）
第二步：现在假设在第2站，并问哪一条是到达城市10且花费最小的路径.若在城市5，最小花费是510，即（210＋380，230＋280）中的最小值，将选用路径5－9－10.同理，若在城市6，最小花费是660，即（350＋380，380＋280）中的最小值，将选择路径6－9－10.此结果列于表7.2.1（2）中.
表7.2.1（2）
第三步：假定处在第1站.用类似于第2站的分析方法进行分析，例如，由城市2到达城市10的最小花费是830＝min （320＋510，350＋660，400＋670）［括号中和式的第一项是由城市2到城市5、6、7的花费，第二项是城市5、6、7到城市10的最小花费，它可由表3－1（2）查到］，最小花费路径是2－5－9－10.第1站的所有计算结果有表7.2.1（3）给出.
表7.2.1（3）
第四步：假设处在城市1，这是起点.必须由城市1到城市2、3、4中的一个.最小花费的路径是那一条呢？应用表7.2.1（3）的结果和由城市1到城市2、3、4的花费，则可计算出全旅程的最小花费为：
min （300＋830，200＋860，350＋810）＝min （1130，1060，1160）＝1060 最小花费路径是：1－3－5－9－10.
上面的解决非常简单.它是基于这样的思考：不论现在处于那一个城市，从最后一个城市开始，将总是选择最优（最小花费）的路径.若在城市10（第4站），就留在那里.若在城市5（第3站），则从城市8或9到达城市10.如此继续下去，直到发现自己在城市1（第0站），并且顺序地找到了最小花费的解，以及实现最小花费的路径.应当注意，即使没有达到第0站，最优解将是什么样，也是清楚的.我们注意到，在第1站，最小费用将是由城市3到城市10的最小费用加上200.另外，如果他改变了他的愿望，并决定从任何其它城市起始，我们也知道最优解是什么.
上面的解法虽然简单，但它却富有启发性.一方面，在计算过程中，我们使用了已经计算出的数据，这大大的节约了计算成本；另一方面，我们得到了比我们预期多得多的信息，我们不仅仅解得了从城市1（起点）到城市10的最小费用路径，而且还得到了其它任何一个城市到达城市10的最小费用路径.显然，如果在原问题的旅行图前又增添了一些新的城市，我们已经计算出的数据仍然可以利用，并且进一步的计算不会比上面的计算更复杂.
下面我们将上面的解法步骤用符号表示，以期望得到更一般的形式.
用符号i v (10,,2,1 =i )表示10个城市.),(j i v v d 表示城市i v 到城市j v 的距离.如果城市i v 到城市j v 必须经过其它城市，则+∞=),(j i v v d .于是所有数据),(j i v v d 构成一个矩阵，即为
⎥⎥⎥
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
⎤
⎢⎢⎢⎢⎢⎢⎢⎢
⎢⎢⎢⎢⎢⎢⎣⎡∞
∞
∞
∞
∞
∞
∞
∞
∞∞∞∞∞∞∞∞∞∞∞
∞
∞∞∞∞∞∞∞∞∞
∞∞
∞
∞
∞
∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞=0280
3802800
40038023038002903502104002900
200410400380350025028035023021003003503202002503000
350410280350020040035032003203502003200)),((j i v v d 用i S 表示第i 站所有城市构成的集合.即{}10v S =，{}4321,,v v v S =，{}7652,,v v v S =，
{}983,v v S =，{}104v S =.用)(i k v f 表示从第k 站的城市i v 到目的地10v 的最小费用值.于
是上面的解题过程可由下面的递推公式完成：
{}⎪⎩
⎪
⎨⎧=+==∈-1,2,3,4,),()(min )(0)(1104k v v d v f v f v f i j j k S v i k k j (7.2.1) 当然，在每步极小化时，应记住极小值点i v ，这样才能确定最小费用路径.
显然，根据对称性，你还可以使用“顺推法”.与之对应，上面的过程称为“逆推法”.
7.3 背包问题
问题：有人在某地旅游结束后，决定购买一些“特产”，打算带回家，再卖给他的一些同事，指望得到一笔诚实无欺的利润.他知道在他的行李中最多只能带20㎏，才不会超重.他可以购买四种不同类型的特产，其特征如见表7.3.1.
表7.3.1
由于这些项目不可能分割包装，这就限制了只能取其整数倍.
根据第六章，此问题可以用整数线性规划来描述.设1x ，2x ，3x ，4x 表示准备带回家的各种特产的数量，则问题变为求解
4321210260160110max x x x x P +++= (7.3.1)
⎩⎨
⎧=≥≤+++)
4,3,2,1(020
4532..4321i x x x x x t s i 为整数 (7.3.2) 下面我们将用动态规划技术来解此问题.假设已知432,,x x x 的最优值，记为*
4*3*2,,x x x .若是这种情况，我们只需要解一个单变量问题，将*4
*3*2,,x x x 代入式(7.3.1)～(7.3.2)中，可得 )]210260160(110max[*
4*3*21x x x x +++ (7.3.3)
约束为
32021-≤x *
4
*3*245x x x -- (7.3.4) ,01≥x 为整数 (7.3.5)
由于*4*3*2210260160x x x ++是一个常数（若已知*
4
*3*2,,x x x 的值），则目标函数式(7.3.3)仅仅是
10
110max 1x x ≥ (7.3.6)
自然，*4*3*2,,x x x 是未知的.但是，我们知道*4
*3*2,,x x x 必须满足 20－3*
4
*3*245x x x -- (7.3.7) 否则的话，问题式(7.3.3)-(7.3.5)是无解的.若我们规定一个新的变量λ，通常称为状态变量，则可将式(7.3.4)写成为
λ≤12x (7.3.8)
其中，λ可为０，１，…，20中任何一个值，因为在这里实际上 *
4
*3*2,,x x x 是未知的. 现在来解由式(7.3.6)和式(7.3.8)给出的一维问题，即
10
110max 1x x ≥ （7.3.9）
约束为
)20,,1,0(21 =≤λλ
x (7.3.10)
对于每一个λ值，此问题是易于求解的.例如： 02,110max 11≤x x 得出0)0(*
1=x 42,110max 11≤x x 得出220)4(*1=x
若定义
10
1110max )(1x g x ≥≡λ (7.3.11)
则)(1λg 给出1110x 的最大值，并且)(*1λx 是给出极大值的1x 的值.)(1λg 和)(*
1λx 二者为λ
的函数，因此极大化将限制在λ的某些特定值上.若对全部的λ求解(7.3.9)，可得表7.3.2（1）：
表7.3.2（1）
考虑到，现在已经知道满足原问题(7.3.1)-(7.3.2)的约束的最优值)(*
1λx 是怎样地取决
于λ，以及怎样地取决于原问题的任一可能的限制.现在来考虑下述问题：
}160]110max {[max )(210
212x x g x x +≡≥≥λ (7.3.12)
约束为
2132x x -≤λ (7.3.13)
为什么要考虑式(7.3.12)和(7.3.13)形式的最优化问题呢？首先我们注意到，这个问题的所有可行解，也是原问题的可行解.其次，若λ固定于某些值上，则问题是单变量问题，这可从下面的一些论述看出.利用定义式(7.3.11)可看出，10
110max 1x x ≥在式(7.3.12)中是)3(21x g -λ.
所以，式(7.3.12)可写为
}160)3({max )(2210
22x x g g x +-≡≥λλ (7.3.14)
注意，对于固定的λ，式(7.3.14)是一个单变量最优化问题.然而，式(7.3.14)不是完全的.由式(7.3.13)和4321,,,x x x x 的非负性，可看出032≥-x λ，所以有
⎥⎦⎤
⎢⎣⎡≤≤302λx (7.3.15)
其中，[]的最大的整数小于等于a a ≡.于是可将式(7.3.14)写为
}160)3({max )(221]
3/[022x x g g x +-≡≤≤λλλ (7.3.16)
其中20,,2,1,0 =λ.
式(7.3.16)是相当重要的.首先，它是一个单变量最优化问题，易于求解；而且对于全部可能的)(1λg 值，在表7.3.1（1）中已经给出，求)3(21x g -λ只需查表7.3.1（1）就行.这样，利用式(7.3.16)和表7.3.1（1）可计算出)(2λg 的值.结果见表7.3.2（2）中.
表7.3.2（２）
同理，下面我们来考虑问题
}260]160)110max [(max {max )(3210
3123x x x g x x x ++≡≥≥≥λ (7.3.17)
约束为
321532x x x -≤+λ (7.3.18) 此外，若用式(7.3.12)给出的)(2λg ，式(7.3.17)可写为
}260)5({max )(3320
23x x g g x +-≡≥λλ (7.3.19)
并且，由于053≥-x λ，可获得类似于式(7.3.16)的形式，即
}260)5({max )(332]
5/[033x x g g x +-=≤≤λλλ (7.3.20)
其中20,,2,1,0 =λ.
现在可以用式(7.3.20)和表7.3.2（2）可求出)(3λg 的值.见表7.3.2（3）：
表7.3.2（3）
最后，我们来考察如下问题：
}210)4({max )(4430
44x x g g x +-≡≥λλ (7.3.21)
其中极大化是从0到
4
λ
之间的整数4x 上考虑的. 回到原问题，因为λ意味着允许携带物品的总重量，故此时只须求20=λ时的值，即
}210)420({max )20(4435
044x x g g x +-≡≤≤
利用表7.3.2（2）的值，可知道
}210)420({max )20(4435
044x x g g x +-≡≤≤
1100105010601070108010901100max 1050)0(840)4(630)8(420)12(210)16()20(max 5210)5420(4210)4420(3210)3420(2210)2420(1210)1420(0210)0420(max 333333333333=⎪⎪
⎪⎪⎭⎪⎪⎪⎪⎬⎫⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=⎪⎪⎪⎪⎭
⎪⎪⎪⎪⎬⎫⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧+++++=⎪⎪⎪⎪⎭⎪⎪⎪⎪⎬⎫⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧⨯+⨯-⨯+⨯-⨯+⨯-⨯+⨯-⨯+⨯-⨯+⨯-=g g g g g g g g g g g g .此
时，0)20(*4=x .我们已经得到了最优值1100*
=P 以及0*
4=x ，注意到)20(3*g P =，从表7.3.2（3）可知道0*3=x ，而且)20(2*g P =.同理，表7.3.2（2）告诉0*2=x 和)20(1*g P =.最后，在表7.3.1（1）中得到10*1=x .于是原问题的解为：
10*1=x ，0*2=x ，0*
3=x ， 0*4
=x ，1100*
=P . 在这个例子中，我们的解题方法有类似于上一节最短路问题求解的特征： (1)用解四个单变量的最优化问题，代替解一个四变量的最优化问题.
(2)就象最短路问题一样，我们先来处理一个变量（最短路问题中，先考虑最后1站），接着是两个变量，直到最后我们才处理了全部变量.
(3)尽管我们感兴趣的是20=λ的情形，但是除了最后一步仅是对20=λ求解外，我们对λ的全部可能的整数值（200≤≤λ），求解了问题.
如果用i w 和i p 分别表示第i 种物品的重量和获利（4,3,2,1=i ）.λ表示剩余下的用于携带物品的重量.)(λi g 表示用于携带物品的重量为λ时带第１～i 种物品的最大利润.则有下面的递推方程可表示上面的解题过程：
⎪⎪⎩
⎪
⎪⎨
⎧=+-===≤≤-≤≤4,3,2,1},)({max )(0)(4321,200100i x p x w g g g i x i i i i i x w i i i i λλλλλ）
，，，为整数（ (7.3.22) 用此方法解题，可以节约计算.
7.4 分割问题
问题：给定一个正数a ，将其分成n 个部分，使这n 部分的乘积最大. 下面我们用动态规划的方法来解决这个问题.注意到是未指定的.首先我们令
⎭
⎬⎫
⎩⎨⎧=≥==∑∏==n i x x x g i n
i i n
i i
n ,,2,1;0;max )(11 λλ 即)(λn g 表示任何一个正数λ分成n 部分，它们乘积的最大值.乘积的最大值)(λn g 可这样分解：它的第1部分为x ，且剩余的为分成1-n 部分时乘积的最大值.
第一步：考虑1=n 的情形（最简单的情形）.对于这个问题，即任何一个正数λ分成１部分，显然乘积的最大值为λ.因此，我们定义
λλ=)(1g (7.4.1) 第二步：考虑2=n 的情形.即将数λ分成乘积最大的２部分.设其中的一部分为x ，则另一部分为x -λ，于是
)(max )(102x xg g x -=≤≤λλλ
(7.4.2)
利用式(7.4.1)上式也可写成
)(max )(02x x g x -=≤≤λλλ
这是一个含参数的单变量最大化问题，可用数学分析的方法求最大化.对右端函数)
(x x -λ的变量x 求导数并令其导数等于０，就得到2λ
=x 时有最大值4
2
λ.因此我们求得了)(2λg 的
显式表达式：
4
)(2
2λλ=
g 且其第１部分为2
*
λ
=
x . (7.4.3) 第三步：考虑3=n 的情形.即将数λ分成乘积最大的３部分.设其中的一部分为x ，则剩余部分的和为x -λ，于是
)(max )(203x xg g x -=≤≤λλλ
(7.4.4)
利用式(7.4.1)上式也可写成
4/)(max )(203x x g x -=≤≤λλλ
这是一个含参数的单变量最大化问题，可用数学分析的方法求最大化.对右端函数
4/)(2x x -λ的变量x 求导数并令其导数等于０就得到3
λ
=
x 时有最大值3
)3
(λ.因此我们求
得了)(3λg 的显式表达式：
33)3()(λλ=g 且其第１部分为3
*λ
=x . (7.4.5)
第四步：根据(7.4.1)(7.4.3)(7.4.5)，现在我们猜测
n n n g )()(λλ= 且其第１部分为n
x λ
=*. (7.4.6) 下面用归纳法来证明.事实上，3,2,1=n 的情形已经证明.假设k n =时(7.4.6)成立.
第五步：当1+=k n 时，因为
)(max )(01x xg g k x k -=≤≤+λλλ
(7.4.7)
利用假设，则
k x k k
x
x g )(
max )(01-=≤≤+λλλ
这仍然是一个单变量的最优化问题.利用数学分析的知识可求得 11)1
(
)(+++=k k k g λ
λ 且其第１部分为1
*+=
k x λ
.
这样就完成了归纳法的证明.
最后：将a =λ代入式(7.4.6)，我们得到正数a 分割成n 部分时最大乘积为n
n
a )(且分
割的第一部分为
n a ，剩余部分为n a
n )1(-，将此部分分割成1-n 份，使得乘积最大的分割中第一部分为
n a n n a n =--1/)1(，又剩余了n
a
n )2(-，再将此部分分割成2-n 份，…，依次下去，我们会得到每一部分都是n
a
.于是，原问题就解决了.答案是：给定一个正数a ，将
其等分成n 个部分，这样n 部分的乘积最大.
我们仍然将上面的计算方法归结为下面的递推方程：
⎪⎪⎩⎪
⎪⎨
⎧-=-==>≤≤+1
,,2,1,)(max )()(001
1n k x xg g g k x k λλλλλλ (7.4.8) 值的注意的是，我们的方法当问题改变为如下时仍然有效：将一个正整数m 分割成n （n m ≥）个正整数使其乘积最大.但在每一步求解最优化时不能使用经典方法.建议读者动手做做.
7.5 简单的设备更新问题
一部用于化学处理的设备，特别易于遭到腐蚀的损坏，致使影响生产效率.设当用了t 年后，从运转中得到的净收入（扣除运转费用后），可用下式给出
⎪⎩
⎪⎨⎧
>≤≤--=)4(0)
40(2
12262t t t t I (7.5.1) 由式(7.5.1)可看出，这部设备在使用一定年限后应该淘汰.更新的价值为22，并且当它被更换后，它又有了五年的生产寿命.经常保持有一部已用了一年的设备在运转.若每年做一次决策，继续保持这部设备或更换它，那么采用什么策略会使一个规划期限内（五年）的总赢利为最大？
由于式子(7.5.1)给出了净收入，可看出，年赢利是收入与花费之差（即扣除运转费用）.由此，若保持这部现用设备，则赢利为
⎪⎩
⎪⎨⎧
>≤≤--=)4(0)
40(2
1226)(2t t t t t P (7.5.2) 而更换这部设备，赢利为
42226)(=-=t P (7.5.3)
由于这部设备已没有挽救的价值，所以从新设备中的净赢利不取决于所更新设备的使用年限.所以4)0(=P 为从新设备中第一年的赢利.现在让我们把问题公式化.
我们希望求出五个逐年决策的序列，即，保持)(K 或更换)(R ，使从五年运转中的赢利为最大.所以希望
∑=5
1
)
,()(max
j j R K t P j j (7.5.4)
其中，)(t P j 由式(7.5.2)或式(7.5.3)给出，哪一个由作出的决策来定.现在让我们来处理这个多级最佳化问题.若倒过来排各级的序号，则分析起来将方便些，即，第一级表示还剩下一年，因此从第五级开始.图7.3上表示了我们将采用的符号，对于时间)(j t ，将做出保持)(K 或更换)(R 的决策)(j d .若决策保持这个设备，可看出j t 可由下式给出
11+=+j j t t (7.5.5)
若更换这个设备，则1=j t .图7.4更详细地解释了上述记号与约定
.
现在假设剩下的运转时间为一年（最后一级）.定义
≡)(21t g 当设备使用了1t 年时，进入最后一个运转年，采取K 或R 时获得的最大赢利. 那么，很清楚有
{}
[])(max
)(2,211t P t g R K d ==
(7.5.6)
用式(7.5.6)的采样计算如下：
)
(5.154,)3(21)3(226max )3()
(5.234,)1(21)1(226max )1(2121K g K g =⎥⎦
⎤
⎢⎣⎡--==⎥⎦
⎤
⎢⎣⎡--=
表7.5.1中第一栏包含了，当设备还剩一年运转时间时，对不同使用期的设备全部计算. 表7.5.1
现在我们需要对还剩下两年或更多年运转期的设备，发展一种计算最大赢利的一般方法. 定义
≡+)(1j j t g 具有役令1+j t 的设备进入第j 运转年时采用K 或R 的最大赢利. 可由 )(1+j j t g 定义很清楚地给出
⎥⎦
⎤
⎢⎣⎡=∑=++j k k k R
K j j t P t g 11,1)(max )( (7.5.7)
应用最佳化原理、)(1+j j t g 定义和式(7.5.7),可得 {}
[]
)5,4,3,2()
()(max )(11,1=+=-+=+j t g t P t g j j j j R K d j j j (7.5.8)
现在用式(7.5.8)计算)(32t g .由式(7.5.5)知11+=+j j t t .一些采样计算为
⎩
⎨⎧++=)1()0()
2()1(max )1(112g P g P g
我们前面已经计算了)(21t g .由此得
)
(5.43)(5.275.234)
(5.4320)1(21)1(226max )1(22K R K g =⎪⎩⎪⎨⎧
=+=+--= 同理
)
(5.27)(5.275.234)
(5.2510)3(2
1)3(226max )
1()0()
4()3(max )3(2112R R K g P g P g =⎪⎩⎪⎨⎧=+=+--=⎩⎨
⎧++= 剩余的计算结果列表于7.5.1的各栏中.
现在我们能够回答原始的问题了.若目前有一运转了一年的设备，查表7－４中11=+j t 行的第五栏，由此可计算最佳的五年策略.可看出，最大的赢利为91，并保持这个设备一年.现在移到第四栏的第二行，应为现在设备已用了两年.可看出，最佳的策 仍是保持设备.现在移到第三栏第三行，则必需更换设备.若这样做，则移到了第二栏第一行.继续保持设备，并移到第一栏第二行.这条路径已描绘在表7.5.1中.可看出，最佳策略是)(KKRKK .这就是说，在运转的前两年我们保持设备，在第三年更换，然后继续保持两年.最大的赢利将为91.
当然，我们可以用这个算出来的表，来回答可能提出的其它问题.例如，假设我们希望在下一个五年里获得最大的赢利，起始点是使用了两年的设备.对于这种情况，存在有两种最佳的策略，得出相同的赢利为83.这些最佳策略是
)(K K R K K 或)(KRKKK
读者可通过表7－4绘出这些路径.当这两种策略得到相同的总赢利83时，若一个是考虑到
)(KKRKK 在五年周期中的前两年产生43.5的赢利，另一个)(KRKKK 在前两年中只产生
35.5，如果企求获得较多赢利越早越好（实际上常是这样），则第一个策略比第二个更好.
练习
１．用动态规划解下面问题：
（１）⎩⎨
⎧=≥=++++=3
,2,1;010
294max 3212
3
21i x x x x x x x z i （２）⎩⎨
⎧
=≥=++++=3
,2,1;010
294max 3212
3
21i x x x x x x x z i 是整数
（３）⎩⎨
⎧=≥=++=3,2,1;010max 3212
3
21i x x x x x x x z i （４）⎩⎨
⎧
=≥=++=3
,2,1;010
max 3212
3
21i x x x x x x x z i 是整数
２．某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可为国家提供的盈利如表7.5.2所示.
问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大.
３．某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如表7.5.3所示.
表7.5.3
假定该厂生产每批产品的固定成本为３千元，若不生产就为０；每单位产品成本为１千元；每个时期生产能力所允许的最大生产批量不超过６个单位；每个时期末未售出的产品，每单位需付存储费０.5千元.还假定在第一个时期的初始库存为０，第四个时期末的库存量也为０.试问该厂应如何安排各个时期的生产与库存，才能在满足市场需求的条件下，使总成本最小.
阅读材料
渡河问题
人、狼、鸡、米渡河问题：人、狼、鸡、米各一均要过河，船一只.船需要人划，另外至多还能载一物，而当人不在时，狼要吃鸡，鸡要吃米.问人、狼、鸡、米怎样过河才能无一损失？
这是一个有趣的数学游戏，问题比较简单，可用递推方法解决.但我们并不想这样做，我们希望更有意义的解决方案.
解法一：因为问题中出现了四种不同的元素，故我们期望用四维向量表示它们，即
（Man, Wolf, Cock, Rice）
又因为当河的一岸上的情形已知时，另一岸上的情形必然已知.故可用1或0表示是否
表中列出了所有可能的16种状态，当然，根据对称性，河的一岸还会出现另一岸的8种情形.这种向量的表示意义也很明确，如（1，0，1，1）表示人、鸡、米在该处，而狼在另一处，等等.根据题意，有些状态是不能允许的，就是表中用×标记的6种，因为这6种状态中会出现河的一岸一物被另一物所吃的情况.剩下的10种状态我们用○标记出，这些都是系统允许出现的，所以我们称为可取状态.
接下来的问题是如何表示船的一次运载.船上的状态也可以用前面的四维向量表示，例如，船上装有人（人必须在船上）和鸡表示为（1，0，1，0）.因为“船需要人划，另外至多还能载一物”，故船上只有4种可能状态：
（1，0，0，0），（1，1，0， 0），（1，0，1，0），（1，0，0，1）.
我们在这四个向量前面加上i )1(-表示第i 次渡河.这样我们可以通过加法运算来表示船的一次运载.例如：在状态（1，0，1，1）之下船运载了米，即
（1，0，1，1）＋1)1(-（1，0，0，1）＝（0，0，1，0）.
自然，由于问题的要求，运算的结果状态必须是可取状态.在上面的处理下，问题有了如下的的提法：
寻求一种齐数步的系统状态转移过程，使系统从初始状态（1，1，1，1）变换到状态（0，0，0，0）.如果没有这样的转移过程，或所有状态转移过程陷入循环状态，则问题无解.
具体解答过程为：
① ⎪⎪⎩⎪⎪⎨⎧⨯==⨯=⨯=-)0,1,1,0()1,0,0,1()1,0,1,0()0,1,0,1()1,1,0,0()0,0,1,1()1,1,1,0()0,0,0,1()1,1,1,1( ② ⎪⎪⎩⎪
⎪⎨⎧⨯⨯=⨯=⨯⨯==+)2,0,1,1()1,0,0,1(!)1,1,1,1()0,1,0,1()1,0,2,1()0,0,1,1()
1,0,1,1()0,0,0,1()1,0,1,0(
③⎪⎪⎩⎪
⎪⎨⎧=⨯⨯-==⨯=-)
0,0,1,0()1,0,0,1()1,1,1,0()0,1,0,1()1,0,0,0()0,0,1,1(!)1,0,1,0()0,0,0,1()1,0,1,1(
④⎪⎪⎪⎪⎪
⎩⎪⎪⎪⎪⎪⎨
⎧⎪⎪⎩⎪
⎪⎨⎧⨯==⨯⨯=⨯=+⎪⎪⎩⎪⎪⎨⎧⨯⨯==⨯=⨯=+!)1,0,1,1()1,0,0,1()0,1,1,1()0,1,0,1()0,0,2,1()0,0,1,1()0,0,1,1()0,0,0,1()00,1,0()2,0,0,1()1,0,0,1()1,1,0,1()0,1,0,1(!)1,0,1,1()0,0,1,1()1,0,0,1()0,0,0,1()1,0,0,0(
⑤⎪⎪⎪⎪⎪
⎩
⎪⎪⎪
⎪⎪⎨
⎧⎪⎪⎩⎪
⎪⎨⎧⨯⨯-=⨯==⨯=-⎪⎪⎩⎪⎪⎨⎧=⨯⨯=⨯⨯-=⨯=-)1,0,1,0()1,0,0,1(!)0,0,1,0()0,1,0,1()0,1,0,0()0,0,1,1()0,1,1,0()0,0,0,1()0,1,1,1()0,1,0,0()1,0,0,1()1,0,0,0()0,1,0,1()1,1,1,0()0,0,1,1()1,1,0,0()0,0,0,1()1,1,0,1(
⑥⎪⎪⎩⎪⎪⎨⎧⨯=⨯⨯=⨯==+!)1,1,0,1()1,0,0,1()0,2,0,1()0,1,0,1(!)0,1,1,1()0,0,1,1()0,1,0,1()0,0,0,1()0,1,0,0(⑦⎪⎪⎩⎪
⎪⎨⎧⨯
⨯-==⨯⨯-=⨯=-)1,1,0,0()1,0,0,1()0,0,0,0()0,1,0,1()0,1,1,0()0,0,1,1(1
)0,1,0,0()0,0,0,1()0,1,0,1(
上面过程中标记“×”的为不允许状态（或不可取状态），标记“××”的为不可能状态，标记“×！”的为虽然是可取状态但产生了循环的情形.
从上面的过程看出，经过7次状态转移，就能使状态从初始状态（1，1，1，1）变为（0，0，0，0），所以经过7次渡河就能全部安全过河.
解法二：此问题可用图解法求解.
将10个可取状态用10个点来表示，如果某一个可取状态可转移到达另一可取状态，则用一条边相连，否则，不连.这样就可以得到下图G （图7.5）：
其中，顶点a,b,c,d,e 分别表示状态（1，1，1，1）、（1，1，1，0）、（1，1，0，1）、（1，0，1，1）、（1，0，1，0），顶点f,g,h,i,j 分别表示状态（0，1，0，1）、（0，1，0，0）、（0，0，1，0）、（0，0，0，1）、（0，0，0，0）.
问题变为在图G （图7.5）中寻找一条从顶点a 到顶点j 的路径，每条路径就是问题的一个解.我们在图7.6中给出了从顶点a 到顶点j 的所有路径，有两条.这说明原问题有两个不同的解答.这两个解是等优的.
夫妻渡河问题：有三对夫妻要过河，船最多能载二人，由于封建意识严重，要求任意一位妻子不能在自己的丈夫不在场时与另外的男人在一起.问如何安排三对夫妻过河？
此问题是阿拉伯早期的一道趣味数学题，有多种解法.有些书中将此问题提为商仆渡河问题：三个商人各带一名仆人过河.商人已经知道，仆人密谋当仆人人数大于商人人数时，他们就杀人越货.渡河方案由商人安排，问怎样才能安全过河？
此问题与前面的人、狼、鸡、米渡河问题有相似之处，都是带约束条件的渡河问题，但此问题较复杂.我们用类似的方法来求解.
解法一：问题中出现了男子和女子两种元素，所以我们用二维向量（H,W ）来表示各种状态，当然，应满足30;
30≤≤≤≤W H .
一共有10种可取状态，他们是（0，0）、（0，1）、（0，2）、（0，3）、（3，0）、（3，1）、（3，2）、（3，3）、（1，1）、（2，2）.
状态转移用下面向量的加法实现，
),()1(n m j - 其中 ,3,2,1;21;2,1,0,=≤+≤=j n m n m
在以上假设下，问题转化为：寻求由初始状态（3，3）到达状态（0，0）的奇数步的转移过程.
此问题可用计算机编程求解.具体求解过程和前面的人、狼、鸡、米渡河问题的求解过程类似.请读者自己动手做做.
解法二：图解法
在H-W 平面坐标系中，以小圆点“。”
表示可取状态.在下面的运动规则之下： (1) 第奇数次运动向下或向左运动，
步数为2格； (2) 第偶数次运动向上或向右运动，
步数为1或2格；
(3) 每次运动必须落在可取状态上，即在“。”上运动. 寻求从初始状态A （3，3）到达状态O （0，0）的运动路径.
图7.7表示了图解法的一个可实现的运动过程.其中实线表示奇数次运动，虚线表示偶数
步运动.
此问题的答案为：经过11次状态转移，就能实现安全渡河.事实上，此问题共有四个不同的解答，读者不妨试寻找其它的解答.
数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）
4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5
状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：
《数学建模》课程教学大纲 课程编号： 90907011 学时：32 学分：2 适用专业：本科各专业 开课部门：各学院 一、课程的性质与任务 数学建模是研究如何将数学方法和计算机知识结合起来用于解决实际问题的一门边缘交叉学科，是集经典数学、现代数学和实际问题为一体的一门新型课程，是应用数学解决实际问题的重要手段和途径。本课程主要介绍初等模型、简单优化模型、微分方程模型、概率统计模型、数学规划模型等模型的基本建模方法及求解方法。 通过数学模型有关概念、特征的学习和数学模型应用实例的介绍，培养学生数学推导和简化分析能力，熟练运用计算机能力；培养学生联想、洞察能力,综合分析能力；培养学生应用数学方法解决实际问题的能力。 三、实践教学的基本要求 （无） 四、课程的基本教学内容及要求 第一章数学模型概述 1.教学内容 数学模型与数学建模、数学建模的基本方法和步骤、数学模型的特点和分类。 2.重点与难点 重点：数学模型与数学建模。 难点：数学建模的基本方法和步骤。
3.课程教学要求 了解数学模型与数学建模过程；了解数学建模竞赛规程；掌握几个简单的智力问题模型。 第二章初等模型 1.教学内容 双层玻璃窗的功效、动物的身长与体重。 2.重点与难点 重点：初等方法建模的思想与方法。 难点：初等方法建模的思想与方法。 3.课程教学要求 了解比例模型及其应用。 第三章简单的优化模型 1.教学内容 存贮模型、最优价格。 2.重点与难点 重点：存贮模型。 难点：存贮模型。 3.课程教学要求 掌握利用导数、微分方法建模的思想方法；能解决简单的经济批量问题和连续问题模型。 第四章数学规划模型 1.教学内容 线性规划建模、非线性规划建模，奶制品的生产与销售、接力队的选拔与选课策略、钢管和易拉罐下料。 2.重点与难点 重点：线性规划方法建模、非线性规划建模。 难点：非线性规划方法建模、Lingo软件的使用。 3.课程教学要求 掌握线性规划建模方法；了解对偶单纯形的经济意义；了解Lingo数学软件在解决规划问题中的作用。 第五章微分方程模型 1.教学内容 传染病模型、药物在体内的分布与排除、人口的预测和控制。 2.重点与难点 重点：微分方程方法建模。 难点：微分方程方法建模。 3.课程教学要求 掌握微分方程建模的基本方法；掌握用Matlab求解微分方程的方法。 第六章离散模型 1.教学内容
习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）
动态规划 内容要点： 1、动态规划的基本概念 2、各种动态规划问题建模与应用 动态规划是解决多阶段决策过程最优化问题的一种方法。 该方法是由美国数学家贝尔曼 等人在20世纪50年代提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。 在实际的决策问题中，由于涉及的参数比较多，往往需要将问题分成若干个阶段，对不同阶段采取不同的决策，从而使整个决策过程达到最优。显然，由于各个阶段的策略不同，对应的整个过程就可以有一系列不同的策略。动态规划是解决多阶段决策过程最优化的一种方法。这种方法并不困难得多阶段决策问题变换成一系列互相联系的比较容易的单阶段问题，解决了这一西里比较容易的单阶段问题，也就解决了困难得多阶段问题。优势阶段可以用时间表示，在各个时间段，采用不同决策，他随时间而变动，这就有动态的含义。同台规划就是要在时间的推移过程中，在每个时间段选择适
当的决策，以使整个系统达到最优。动态规划是把难解决的大问题分解为通常较为容易解决的子问题的一种解决问题的方法。由于它独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划更有效。特别是对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为了非常有用的工具。应该指出的是，动态规划师求解某类问题的一种求解方法，是考查问题的一种途径，而不是一种算法。因而，他不想线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。 动态规划是现代企业管理中的一个重要决策方法，我们着重利用微软Excel软件在“公式”和“规划求解”两方面的强大功能，对装在问题、生产经营问题、资金管理问题和资源分配问题等进行分析、建模和求解，解决了实际经营中的优化问题，迅速准确地得出决策结果。 （一）背包问题 背包问题可以抽象为这样一类问题：设有n种物品，每种物品有其重量及价值。同时有一个背包，最大装重为c，现从n种物品中选取若干件，使其总重量小于等于c，而总价值最大。背包问题等同于车、船、人造卫星等工具的最优装载问题，有广泛的实际意义。 1、一维背包问题
第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。
数学建模常用方法 数学建模是利用数学工具和方法来研究实际问题，并找到解决问题的最佳方法。常用的数学建模方法包括线性规划、非线性规划、动态规划、整数规划、图论、最优化理论等。 1. 线性规划（Linear Programming, LP）: 线性规划是一种在一定约束条件下寻找一组线性目标函数的最佳解的方法。常见的线性规划问题包括生产调度问题、资源分配问题等。 2. 非线性规划（Nonlinear Programming, NLP）: 非线性规划是指当目标函数或约束条件存在非线性关系时的最优化问题。非线性规划方法包括梯度方法、牛顿法、拟牛顿法等。 3. 动态规划（Dynamic Programming, DP）: 动态规划方法是一种通过将复杂的问题分解成多个子问题来求解最优解的方法。动态规划广泛应用于计划调度、资源配置、路径优化等领域。 4. 整数规划（Integer Programming, IP）: 整数规划是一种在线性规划的基础上，将变量限制为整数的最优化方法。整数规划常用于离散变量的问题，如设备配置、路径优化等。 5. 图论（Graph Theory）: 图论方法研究图结构和图运算的数学理论，常用于解决网络优化、路径规划等问题。常见的图论方法包括最短路径算法、最小生成树算法等。 6. 最优化理论（Optimization Theory）: 最优化理论是研究寻找最优解的数学方法和理论，包括凸优化、非凸优化、多目标优化等。最优化理论在优化问题建模中起到了重要的作用。
7. 离散数学方法（Discrete Mathematics）: 离散数学方法包括组 合数学、图论、概率论等，常用于解决离散变量或离散状态的问题。离散 数学方法在计算机科学、工程管理等领域应用广泛。 8. 概率统计方法（Probability and Statistics）: 概率统计方法 通过对已有数据进行分析和建模，提供了一种推断和预测的数学方法。概 率统计方法在决策分析、风险评估等领域起到了重要的作用。 9. 数值计算方法（Numerical Methods）: 数值计算方法是一种通过 数值逼近的方式求解数学问题的方法。常见的数值计算方法包括数值积分、数值求解微分方程等。 10. 仿真方法（Simulation）: 仿真方法通过构建系统模型，并进行 实验和模拟，来研究和预测系统的行为。仿真方法在工程设计、风险评估 等领域广泛应用。 总之，数学建模方法丰富多样，不同方法适用于不同类型的问题。在 实际建模过程中，通常需要结合实际问题的特点和要求选择合适的方法， 并进行适当的调整和优化，以达到最佳解决方案。
主要建模方法 1、类比法 建模一般在具体分析该实际问题的各个因素的基础上，通过联想、归纳对各因素进行分析，并且与已知模型比较，把未知关系化为已知关系，在不同的对象或完全不相关的对象中找出同样的或相似的关系，用已知模型的某些结论类比得到解决该“类似”问题的数学方法，最终建立起解决问题的模型 2、量纲分析 是在经验和实验的基础上，利用物理定律的量纲齐次性，确定各物理量之间的关系。 它是一种数学分析方法，通过量纲分析，可以正确地分析各变量之间的关系，简化实验和便于成果整理。 在国际单位制中，有七个基本量：质量、长度、时间、电流、温度、光强度和物质的量，它们的量纲分别为M、L、T、I、H、J和N，称为基本量纲。 量纲分析法常常用于定性地研究某些关系和性质，利用量纲齐次原则寻求物理量之间的关系，在数学建模过程中常常进行无量纲化，无量纲化是根据量纲分析思想，恰当地选择特征尺度将有量纲量化为无量纲量，从而达到减少参数、简化模型的效果。 3.差分法 差分法的数学思想是通过taylor级数展开等方法把控制方程中的导数用网格节点上的函数值的差商代替进行离散，从而建立以网格节点上的值为未知数的方程组，将微分问题转化为代数问题，是建立离散动态系统数学模型的有效方法。构造差分的方法有多种形式，目前主要采用的是泰勒级数展开方法。 其基本的差分表达式主要有以下几种形式：一阶向前差分、一阶向后差分、一阶中心差分和二阶中心差分等，其中前两种格式为一阶计算精度，后两种格式为二阶计算精度。通过对时间和空间这几种不同差分格式的组合，可以组合成不同的差分计算格式。 差分法的解题步骤为：建立微分方程；构造差分格式；求解差分方程；精度分析和检验 4、变分法 较少 5、图论法 数学建模中的图论方法是一种独特的方法，图论建模是指对一些抽象事物进行抽象、化简，并用图来描述事物特征及内在联系的过程。图论是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。因此，图论是研究自然科学、工程技术、经济问题、管理及其他社会问题的一个重要现代数学工具，更是成为了数学建模的一个必备工具 6、层次分析法 现在已广泛地应用在企业信用评级、经济管理规划、能源开发利用与资源分析、城市产业规划、企业管理、人才预测、科研管理、交通运输、水资源分析利用等方面。 层次分析法的基本步骤是：建立层次结构模型；构造成比较矩阵；计算权向量并做一致性检验 7.数据拟合法在建立数学模型时,实际问题有时仅给出一组数据，处理这类问题较简单易行
数学建模思想方法大全及方法适用范围数学建模是指运用数学方法和技巧解决实际问题的过程。不同的问题需要不同的建模方法和思想，下面是一些常用的数学建模思想方法及其适用范围。 1.数学规划方法：包括线性规划、整数规划、非线性规划等。适用于有约束条件的最优化问题，如资源分配、生产计划等。 2.动态规划方法：适用于具有最优子结构的问题，通过将问题划分为子问题，并利用子问题的最优解构建原问题的最优解。常用于路径规划、资源管理等。 3.随机过程方法：适用于具有随机特性的问题，如排队论、随机模拟等。常用于风险评估、金融风险管理等领域。 4.图论方法：适用于用图形表示问题的结构和关系的问题，如网络优化、旅行商问题等。 5.统计建模方法：包括回归分析、时间序列分析、方差分析等。适用于通过样本数据建立数学模型，分析和预测问题。 6.数据挖掘方法：包括聚类分析、关联规则挖掘、分类预测等。适用于从大规模数据中发现隐藏的模式和规律。 7.模糊综合评价方法：适用于多指标评价和决策问题，通过模糊数学的方法将主观和客观指标进行综合评价，辅助决策。 8.最优化方法：包括梯度下降法、遗传算法、模拟退火等。适用于求解无约束优化问题和非线性问题。
9.离散事件系统建模方法：适用于描述离散事件发展过程的问题，如物流调度、生产流程优化等。 10.时空建模方法：适用于描述时空变化和相互作用的问题，常用于交通流动、城市规划等领域。 11.复杂网络建模方法：适用于分析复杂系统中的网络结构和动态特性，如社交网络、生物网络等。 12.随机优化方法：将随机性引入传统的优化方法，如随机梯度下降法、遗传算法等。 以上是一些常用的数学建模思想方法及其适用范围，实际问题的建模过程中可以根据具体情况选择合适的方法，甚至可以综合运用多种方法。数学建模的关键在于将实际问题抽象为数学问题，并选择合适的数学工具进行求解。
。 例1差分方程——资金的时间价值 问题1:抵押贷款买房——从一则广告谈起 每家人家都希望有一套(甚至一栋)属于自己的住房，但又没有足够的资金一次买下，这就产生了贷款买房的问题。先看一下下面的广告(这是1991年1月1日某大城市晚报上登的一则广告)，任何人看了这则广告都会产生许多疑问，且不谈广告中没有谈住房面积、设施等等，人们关心的是：如果一次付款买这栋房要多少钱呢?银行贷款的利息是多少呢?为什么每个月要付1200元呢?是怎样算出来的?因为人们都知道，若知道了房价(一次付款买房的价格)，如果自己只能支付一部分款，那就要把其余的款项通过借贷方式来解决，只要知道利息，就应该可以算出五年还清每月要付多少钱才能按时还清贷款了，从而也就可以对是否要去买该广告中所说的房子作出决策了。现在我们来进行数学建模。由于本问题比较简单无需太多的抽象和简化。 a.明确变量、参数，显然下面的量是要考虑的： 需要借多少钱，用记； 月利率(贷款通常按复利计)用R记； 每月还多少钱用x记； 借期记为N个月。 b．建立变量之间的明确的数学关系。若用记第k个月时尚欠的款数，则一个月后(加上利息后)欠款，不过我们又还了x元所以总的欠款为 k=0，1，2，3， 而一开始的借款为。所以我们的数学模型可表述如下 (1) c. (1)的求解。由
(2) 这就是之间的显式关系。 d．针对广告中的情形我们来看(1)和(2)中哪些量是已知的。N=5年＝60个月，已知；每月还款x＝1200元，已知A。即一次性付款购买价减去70000元后剩下的要另外去借的款，并没有告诉你，此外银行贷款利率R也没告诉你，这造成了我们决策的困难。然而，由(2)可知60个月后还清，即，从而得 (3) A和x之间的关系式，如果我们已经知道银行(3)表示N＝60，x＝1200给定时0 A。例如，若R ＝0．01，则由(3)可算得的贷款利息R，就可以算出0 53946元。如果该房地产公司说一次性付款的房价大于70000十53946＝123946元的话，你就应自己去银行借款。事实上，利用图形计算器或Mathematica这样的 数学软件可把(3)的图形画出来，从而可以进行估算决策。以下我们进一步考虑下面两个问题。 注1问题1标题中“抵押贷款”的意思无非是银行伯你借了钱不还，因而要你用某种不动产(包括房子的产权)作抵押，即万一你还不出钱了，就没收你的不动产。例题1某高校一对年青夫妇为买房要用银行贷款60000元，月利率0．01，贷款期25年＝300月，这对夫妇希望知道每月要还多少钱，25年就可还清。假设这对夫妇每月可有节余900元，是否可以去买房呢?
数学建模案例分析--最优化方法建模6动态规划模型举例
§6 动态规划模型举例 以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型——线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如： （1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。 （2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命中目标。 （3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。
动态规划模型是解决这类问题的有力工具，下 面介绍相关的基本概念及其数学描述。 （1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，记为k 。 （2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用k x 表示第k 阶段的状态变量。n 个阶段的决策过程有1 n 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。 （3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用)(k k x u 表示第k 阶段处于状态k x 时的决策变量，它是k x 的函数， 用)(k k x D 表示k x 的允许决策集合。 （4）策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k 阶段的状态k x 开始到终止状态的后部子过程的策略记为
【摘要】在过去五十多年的进程中，动态规划在运筹学、控制论、管理科学等领域的发展中，都发挥了无可比拟的领军作用，动态规则是研究多阶段决策过程最优化的一种方法，在生产实践中有很大的实用价值，成为解决数学建模问题最常用的优化方法之一。 【关键词】动态规划；模型；应用 本文主要讨论动态规划模型的建立以及模型的应用。动态规划模型是求解决策过程最优化的数学方法，在生产实践中有很大的实用价值，本文采用数学建模的形式，将生活中的一些实际问题用数学模型表示出来，以生产―库存管理系统为例，并且根据动态规划模型的相关原理，查阅相关文献，用数学的语言提出解决办法，从而实现其为生产实践服务的目的。 1、国内外对本课题涉及问题的研究现状 动态规划发源于20世纪50年代左右，是目前用来解决多阶段决策过程最优化的一种方法。国内对动态规划的研究起步较晚，国外对此研究起源较早，且研究范围很广。根据了一类多阶段决策问题的特点，1951年，美国数学家理查德?贝尔曼提出了解决这类问题的“最优化原理”，由此，理查德?贝尔曼及学者将其应用于很多实际生活问题中，研究并解决问题，从而建立了运筹学的一个分支-动态规划。1957年，在美国普林斯顿大学，理查德?贝尔曼发表了第一本正式的著作。随后，理查德?贝尔曼与众多学者和科学工作者发表了一些列动态规划应用的著作，包括动态规划在资源理论、最佳控制论、经济学、工业工程、马尔柯夫变分法和管理科学过程中的应用。因此在国内外，动态规划的发展始终伴随着它的广泛应用而不断臻善的。 2、动态规划的优点 动态规划的核心思想是美国数学家理查德?贝尔曼提出的最优化原理，该原理产生了分阶段决策的方法。分阶段决策的方法是在整体最优化的基础之上建立的，在探寻某一阶段决策时，既要对局部的利益进行考虑，而且还应顾及到总体的最优。动态规划通过分阶段处理一个n维变量处理的复杂问题，将n维变量问题转化为求解n个单变量问题，将解决过程大大简化，节省了大量的计算量，这是一个典型的求解极值方法无法做到的。目前，动态规划几乎超越了所有的计算方法，特别是大大超越了经典的优化方法，它可以确定绝对（全局）最大或最小，而不是相对（局部）的极值，所以我们不再需要再担心的局部最大值或最小值的问题。动态规划的另一个特点是泛函方程的“嵌入”特性。动态规划方法不仅能求出整个过程的某一个特定的状态的一个值，同时也为后面子流程的所有可能出现状态的一族解。 3、动态规划建模在实际生活中的应用 下面举例说明动态规划在生产―库存管理系统的模型及求解。设每一个季度为一个阶段，并且取第k季度初具有的产品数为状态变量xk；取第k季度需要生产的产品数为决策变量uk；第k季度的销售量（订货量）为sk。显然由状态xk采取决策uk后的状态转移方程为：xk+1=xk+uk-skk=1，2，3，4 对现在的问题，效益就是费用，故阶段效益为d（xk，uk）=xk+0.005u2k 若用fk（xk）表示从状态xk出发，采用最优策略到第四季度结束时的最小费用，则有如下的模型： fk（xk）=min{xk+0.005uk2+fk+1（xk+1）}（uk≥sk-xk） f5（x5）=0，k=4，3，2，1 下面，我们用逆推算法求解以上模型。 1、先从最后一个季度k=4考虑起，即求： u4≥1200-x4时，f4（x4）=min{x4+0.005u42} 由x5=0和状态转移方程可得：0=x4+u4-s4=x4+u4-1200 从而得到u4=1200-x4，代入f4（x4）可得：f4（x4）=7200-11x4+0.005x42 2、再考虑k=3，即求u3≥500-x3时，f3（x3）=min{x3+0.005u32+f4（x4）}
《数学建模》课程教学大纲 英文名称：Mathematical Modeling 课程编号： 适用专业：理工科类（专科） 总学时数：30 学分： 2 一、课程的性质、目的与任务 本课程是联系数学与实际的桥梁，是数学在各个领域广泛应用的媒介。通过本课程的教学使学生了解利用数学理论和方法去分析和解决实际问题的全过程，提高他们分析问题和解决问题的能力，提高他们学习数学的兴趣和应用数学的意识与能力。 二、课程教学内容及要求 第一章建立数学模型（2学时） 1、教学内容 数学模型与数学建模、数学建模的基本方法和步骤、数学模型的特点和分类 2、重点、难点 重点：数学模型与数学建模 难点：数学建模的基本方法和步骤 3、教学基本要求 （1）了解数学模型与数学建模过程。 （2）了解数学建模竞赛规程。 （3）掌握几个简单的智力问题模型。 第二章初等模型（2学时） 1、教学内容 双层玻璃窗的功效、动物的身长与体重 2、重点、难点 重点：初等方法建模的思想与方法 难点：初等方法建模的思想与方法 3、教学基本要求 了解比例模型及其应用。 第三章简单的优化模型（2学时） 1、教学内容
存贮模型、最优价格 2、重点、难点 重点：存贮模型 难点：存贮模型 教学基本要求 （1）掌握利用导数、微分方法建模的思想方法。 （2）能解决简单的经济批量问题和连续问题模型。 第四章数学规划模型（4学时） 1、教学内容 线性规划建模、奶制品的生产与销售、接力队的选拔与选课策略、钢管和易拉罐下料 2、重点、难点 重点：线性规划方法建模 难点：线性规划方法建模、Lindo软件的使用。 3、教学基本要求 （1）掌握线性规划建模方法。 （2）了解对偶单纯形的经济意义。 （3）了解Lindo和Lingo数学软件在解决规划问题中的作用。 第五章微分方程模型（4学时） 1、教学内容 传染病模型、药物在体内的分布与排除、人口的预测和控制。 2、重点、难点 重点：微分方程方法建模 难点：微分方程方法建模。 3、教学基本要求 （1）掌握微分方程建模的基本方法。 （2）掌握用数值方法求解微分方程的方法。 第六章离散模型（4学时） 1、教学内容 层次分析模型、循环比赛的名次 2、重点、难点 重点：层次分析法建模
动态规划方法求解线性规划问题 动态规划是一种常用的优化方法，可以用来求解线性规划问题。线性规划是一 种数学建模方法，用于在给定的一组约束条件下，寻觅使目标函数最大（或者最小）的变量值。本文将介绍动态规划方法在解决线性规划问题中的应用。 一、线性规划问题的定义和形式 线性规划问题可以用下列形式来描述： 目标函数：max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙ 约束条件： a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂ ... aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ 其中，c₁、c₂、...、cₙ为目标函数的系数，x₁、x₂、...、xₙ为变量，a₁₁、 a₁₂、...、aₙₙ为约束条件的系数，b₁、b₂、...、bₙ为约束条件的常数。目标是 找到使目标函数最大（或者最小）的变量值。 二、动态规划方法求解线性规划问题的基本思想 动态规划方法可以将线性规划问题转化为一个多阶段决策问题，并通过递推的 方式求解最优解。具体步骤如下： 1. 将线性规划问题转化为标准形式：将不等式约束转化为等式约束，并引入松 弛变量。 2. 构建动态规划模型：定义状态和状态转移方程。
3. 初始化：确定初始状态和初始条件。 4. 递推求解：根据状态转移方程，逐步计算得到最优解。 5. 回溯得到最优解：根据递推过程中记录的状态，回溯得到最优解。 三、动态规划方法求解线性规划问题的具体步骤 1. 将线性规划问题转化为标准形式：将不等式约束转化为等式约束，并引入松 弛变量。 例如，将约束条件 a₁₁x₁ + a₁₂x₂ ≤ b₁转化为 a₁₁x₁ + a₁₂x₂ + x₃ = b₁，其中 x₃为松弛变量。 2. 构建动态规划模型：定义状态和状态转移方程。 定义状态：设 f(i,j) 表示前 i 个约束条件中，使得目标函数最大（或者最小）的 变量值。 状态转移方程：f(i,j) = max/min { f(i-1,j), f(i-1,j-aᵢ₋₁₁x₁ - aᵢ₋₁₂x₂) + cᵢ₋₁x₁ + cᵢ₋₁x₂ } 其中，f(i-1,j) 表示不使用第 i 个约束条件时的最优解，f(i-1,j-aᵢ₋₁₁x₁ - aᵢ₋₁₂x₂) + cᵢ₋₁x₁ + cᵢ₋₁x₂表示使用第 i 个约束条件时的最优解。 3. 初始化：确定初始状态和初始条件。 初始状态：f(0,j) = 0，表示没有约束条件时的最优解为 0。 初始条件：根据约束条件中的等式，确定初始变量值。 4. 递推求解：根据状态转移方程，逐步计算得到最优解。 从 i=1 开始，逐个计算 f(i,j) 的值，直到计算到 f(m,n) 为止。 5. 回溯得到最优解：根据递推过程中记录的状态，回溯得到最优解。
第七章动态规划常见疑问解答 1、动态规划是怎样产生的？ 1951年，R . Bellman 等人，根据某类多阶段序贯决策问题的特点，提出了著名的“最优性原理”。在这个原理的指导下，他将此类多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年，他的名著《动态规划》出版。 2、动态规划的基本概念有哪些？ 阶段、（阶段）状态、状态变量s i、状态集S i、决策、决策变量u i(s i)、决策集D i(s i)、状态转移方程、决策的指标函数、策略的指标函数、最优值函数等。 3、什么是阶段？ 动态规划的阶段指的是决策发生的时间或空间区隔。 4、如何划分动态规划问题的阶段？ 动态规划问题的阶段划分一般可依据决策发生的次数和每次决策发生并作用的时间段或空间段来定。 5、什么是（阶段）状态？ 状态既可以指一个阶段上作决策时所依据的自然状况和客观条件，又可以指一个阶段上所作决策后的结局状况，故一个阶段的状态常有首、末状态之分，以区别阶段上决策的出发点和结局状况。但，一般地，人们往往仅选择各阶段的首、末状态之一，作为各阶段的状态，所以，当谈到各阶段的状态时，要么都指的是各阶段的首状态，要么都指的是各阶段的末状态。 6、什么是（阶段）状态变量？
状态变量是对一个阶段上状态（多种）取值情形的描述。人们常用符号s k 表示第k个阶段上的状态变量，k= 1, 2, …, n. 7、什么是动态规划问题的维数？ 动态规划问题的维数即指的是各阶段上状态变量的维数。 8、各阶段上状态变量的维数是如何确定的？ 动态规划问题各阶段上的状态常常可能需要用几个属性才能描述清楚。如各个阶段上都要依据资源状态作出生产数量决策时，若生产资源有3种类型，则资源状态就必须用三种类型的资源，即三个属性来共同描述。相应地，资源状态变量就必须用三维向量表示各类资源的取值情形。因此，各阶段上状态变量的维数是由各阶段上状态的属性数确定的。 9、什么是动态规划问题的维数灾难？ 动态规划问题的维数即指的是各阶段上状态变量的维数。当状态变量的维数增加时，动态规划问题的计算量会呈指数倍增长，限制了人们用动态规划研究问题和解决问题的能力。故，人们把这种情形称为“维数灾难”。 10、* 化解动态规划问题的维数灾难，可以利用的思想是什么？ 人们一般采取了降维的办法，即通过一些特殊技巧或算法把一个高维的动态规划问题逐步分解为一些低维的动态规划问题，以此来减轻维数灾难。 11、什么是状态集？ 一个阶段上状态可有多种取值情形，各种取值情形的集合被称为该阶段上的状态集。人们常用符号S k表示第k个阶段上的状态集，k= 1, 2, …, n. 12、什么是（阶段）决策？ 决策是指依据某个阶段的某种状态，从各种可能的方案中作出选择。
实验项目五动态规划 实验学时：2 实验目的：动态规划（dynamic programming，DP）是解决多阶段决策问题的一种有效的数量化方法，难度比较大，技巧性也很强。Lindo/lingo 是求解动态规划比较常用的软件之一，通过本实验，掌握动态规划模型在Lindo/lingo 中的求解。 实验要求：1.掌握动态规划的建模步骤及方法； 2.掌握动态规划模型在Lindo/lingo 转化及求解； 3.学会动态规划的执行结果分析 实验内容及步骤： 例：如图5-1 所示，某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？ 图5-1 下面简单说明动态规划的求解建模过程，有助于下一步在Lindo/lingo中模型的表示，这是一个很重要的过程，建议读者不要跳过。 动态规划方法求解时注意事项： （1）动态规划的三个基本要素：阶段、状态、决策。其中最关键的是状态的描述，最难的也是状态的设计，它关系到算法的时间、空间复杂度，也跟实现的复杂度息息相关。 （2）动态规划的两个条件：最优子结构、无后效性，其中后效性往往容易被忽视。 （3）动态规划本质是用空间换时间，在有大量重叠子问题的时候其优势才能充分体现出来。
上例的求解过程如下： （1）阶段与阶段变量：先把问题从中间站B，C，D，E 用空间位置分成 5 个阶段，阶段用阶段变量k 来描述，k=1,表示第一阶段，k=2 表示 第二阶段，… （2）状态与状态变量：每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状 态S3 =｛C1 ,C2，C3，C4｝, 第四阶段有三个状态S4=｛D1, D2 , D3｝, … 描述过程状态的变量称为状态变量：用小写s1 ,s2 ,s3 …表示第一，第二，第三…阶段的状态变量。当处在状态C2 时，我们可记s3= C2 (3)决策与决策变量：如当处于C2 状态时，下一步怎么走？如何选择路线？即如何决策。是走向D1，还是走向D2？当过程处于某一阶段的某一状态时，可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定（或选择）叫决策。如选择D2，记u3（C 2）= D2 即当处于C2 状态时，下一步的决策为D2。 其中u k(s k) 表示第k 阶段当状态处于s k时的决策变量。 一般地，用D k(s k) 表示第k 阶段从状态s k出发的允许决策集合。如 D3(C2)=｛D1，D2｝显然，u k(s k) ∈D k(s k) 。 （4）策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列：u1(s1) ，u2(s2) ，u3(s3) ，u4(s4) ，u5(s5) 称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。 这里的最短路径成为最优策略。 动态规划就是在允许策略集中选最优策略。 （5）状态转移方程：是描述由第k 阶段到第k+1 阶段状态转移规律 的关系式。 s k+1=T k(s k,u k) 上例中状态转移方程为： s k+1=u k(s k) （6）指标函数与最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态s k出发，采用决策u k时的效益，用d k(s , u k) 表示。最优指标函数是指从第k阶段状态s k采用最优策略到过程终止时的最佳效益k 值，用f k(s k) 表示。例如：d（C2, D1）是指由C2 出发，下一阶段的决策是D1 的两点间的距离。即d（C2, D1）=4。f2(B1) 表示从B1 到F 的最短距离。整个问题即为f1(A) =？
动态规划的原理及应用 动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法——动态规划。 动态规划主要用于以时间划分阶段的动态过程优化问题，但一些与时间无关的静态规划如线性规划或非线性规划，人为引进时间因素后，把它们看成多阶段过程，也可用动态规划求解。 1．动态规划的基本理论 一．动态规划的术语 在研究现实的系统时，我们必须将系统具体的术语抽象为数学统一的术语。在此先简要介绍动态规划中的常用术语。 级：我们把系统顺序地向前发展划分为若干个阶段，称这些阶段为“级”。在离散动态规划中，“级”顺序的用自然整数编号，即1，2，…，n. 状态（λ）：用来描述、刻画级的特征。状态可以是单变量，也可以时向量。在此，我们假设研究的状态具有“无记忆性”，即当前与未来的收益仅决定于当前的状态，并不依赖于过去的状态和决策的历史。 状态空间（Λ）：由全部系统可能存在的状态变量所组成。
决策：在每一级，当状态给定后，往往可以做出不同的决定，从而确定下一级的状态，这种决定称为决策。描述决策的变量称为决策变量。对每个状态λ∈Λ，有一非空集X(λ)称为λ的决策集。决策变量x(λ)∈X（λ）。 变换：若过程在状态λ，选择决策x(λ)，可确定一个状态集T（λ，x(λ)）,过程将从λ移动到其中某个状态.T(λ,x(λ))称为变换函数，它确定过程从一个状态到另一个状态的演变。T（λ,x(λ)）可分为两种类型，即确定型和不确定型。确定型的T（λ,x(λ)）只含有一个元。不确定型指我们不能确切知道决策的结果，但作为某已知概率分布支配的变换结果，在每级状态和决策是确定的。这时，集函数T（λ,x(λ)）将包含多个元素。当T（λ,x(λ)）=0 时，过程终止。 策略：顺序排列的决策集，记为v。所有可能的策略集构成策略空间Γ。 收益：评价给定策略的目标函数r(λ，v)，它依赖于状态和策略。总收益是集收益s(λ,v)的某个组合（通常为集收益之和）。若T（λ,x(λ)）=0，则r(λ1，v1)= s(λ1,v1)；若T（λ,x(λ)）= λ2，则r(λ1，v)= s(λ1,v1)+ r(λ1，v2)。 二．序贯决策过程 动态规划的寻优过程可以有正序、逆序两种方式。当初始状态给定时，用逆序方式比较好，当终止状态给定时，用正序方式较好。 采用分级的序贯决策方法，把一个含有n个变量的问题转化为求解n个单变量问题。为了应用最优化原理，必须满足分级条件，即目标函数可分性和状态可分性。 目标函数可分性：