1、动态规划动态规划DP（Dynamic Programming）动态规划是现代企业管理中一种重要的决策方法，它是解决多阶段决策过程最优化的一种数学方法。动态规划大约产生于五十年代，1951年美国数学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段问题。然后逐个加以解决。同时，他提出了解决这类问题的最优原理，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法-动态规划。动态规划的方法，在工程技术、企业管理、军事等部门都有广泛的应用。在企业管理中，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排
2、序问题、设备更新问题、生产过程最优控制问题。需要特别强调的是：动态规划是求解一类问题的方法，是考察问题的一种途径，而不是一种特殊的算法。因而不像线性规划那样有一个标准的数学表达式和明确定义的一组规则。故需要有丰富的想象去建模，创造性地去求解。一、多段决策问题的提出一、多段决策问题的提出例1生产与存储问题某工厂每季度需供应市场一定数量的产品（600，700，500，1200），未销售完的产品存入仓库（每件每季度1元），现要制定生产计划，在满足市场需求的条件下，使一年的生产与存储费用最少。生产费用为：件数的平方成正比，比例系数为0.005。这是一个求最小值的四阶段决策问题，根据题意可知；生产量是决
3、策变量，库存量是反映当前每季度产品库存的客观状态，为状态变量。设第k季度生产的产品数为ku，第k季度的库存量为kS，第k季度的销售量为kq，由此得出三个变量之间的关系为：)4,3,2,1(1kquSSkkkk 假设年初和年底无存货，即01S，05S。由题中给定的条件可得全过程目标管理函数为：4121)005.0(kkkSuf 我们的目标就是求最优的生产决策序列，即全年中每季度的最优生产量4321,uuuu，使在满足市场需求的条件下，使一年的总费用最少，由此得本问题的数学模型为：0000505114121,SSquSS)Su.(fkkkkkkk例2最短路问题设有一辆汽车由A城到B城，中间可经过V
4、1到V8城市，各城市的交通路线及距离如下图所示，问应选择哪一条路线，可使总距离最短。可将上述最短路问题看成是四个阶段的决策问题，第一阶段为 A 到 V1,V2,V3,第二阶段为 V1,V2,V3到 V4,V5,V6,第三阶段为 V4,V5,V6到 V7,V8,第四阶段为 V7,V8到 B。在第一阶段，A 为起点，终点有 V1,V2,V3三个，此时走的路线有三种选择，若选择走到 V2。在第二阶段，在从 V2出发，可供选择的终点集合 V4,V5,V6，同理递推下去，可看到：各个阶段的决策不同，走的路线就不同，总的距离就不同。故此问题的要求是：在各个阶段选区一个恰当的决策，有这些决策组成的决策序列所
5、决定的一条路线，其总路程最短。由上述例题可知，在实际生产、科学试验、经济活动的过程中，有一类活动的过程，由于其特殊性。可将该过程分为若干个相联系的阶段，在每个阶段都要做出决策，全部过程的决策就形成一个决策序列决策序列，每一个阶段的决策有许多种方案选择，从而形成多种决策策略，在这些决策策略中选择一个最优的策略，使在预定的标准下达到最好效果，这就是多阶段决策问题。二、多阶段决策的有关概念二、多阶段决策的有关概念(1)阶段；把所给问题的过程，按照过程的时间、空间等的自然特征，恰当的分为若干个相互联系的阶段，以便能按一定的次序去求解，描述阶段的变量称为阶段变量，用k表示。例如例 1 中可分为四个联系的
6、阶段，4,3,2,1k(2)状 态；表 示 每 个 阶 段 开 始 时 所 处 的 自 然 状 况 或客 观 条 件，描 述 了 研 究 问 题 过 程 的 状 况，在 例1 中，状 态 就 是 每 个 阶 段 开 始 时 的 库 存，它 既 是 前 一 阶 段 的结 果，又 是 后 一 阶 段 的 开 始。通 常 一 个 阶 段 有 若 干 个状 态。描 述 状 态 的 变 量 称 为 状 态 变 量，常 用kS表 示 第k阶 段 的 状 态 变 量。例 1 中01S，05S表 示 状 态 变量1S，5S的 值 为0，而432,SSS的 取 值 可 能 有 多 种情 况。状 态 应 具 有
7、无 后 效 性 的 特 点：如 果 某 阶 段 的 状态 给 定 以 后，则 在 这 阶 段 以 后 过 程 的 发 展 不 受 这 阶 段以 前 各 阶 段 状 态 的 影 响。(3)决策；当过程出于某一阶段的某个状态时，可以做出不同的选择、决定，从而决定下一个阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。通常用)(kkSu 表示第k阶段状态处于kS时的决策变量。(4)策略；策略是一个决策序列。由过程的第k阶段开始到 中止 状态 的过程，称 为问题 的后 部子 过程（或k子过程），将 后 部 子 过 程 的 决 策 按 顺 序 排 列 成 的 决 策 函 数)(,),(),(1
8、1nnkkkkSuSuSu称为k子过程策略，记为)(,knkSp，当1k时，此决策函数称为全过程的策略，在实际问题中，策略有一定的范围，此范围称为允许策略集合，从允许策略集合中找出达到最优效果的策略就是我们的目标，该策略称为最优策略。(5)状态 转移 方程；状态 转移 方 程就 是确 定过 程由一 个 状 态 到 另 一 个 状 态 的 变 化，如 果 给 定 第k阶 段 的状 态kS，决策 为)(kkSu，则 第1k阶 段的状 态1kS为：)(,(1kkkkSuSLS 称 为 状 态 转 移 方 程，反 映 了 相 邻 状 态 变 量 间 的 关系。(6)指标函数和最优值函数；用来衡量所实现
9、过程优劣的一种数量函数。它定义在全过程和后部子过程上，常用nkfk,2,1,表示，指标函数应具有可分离性，递推性。指标函数的最优值称为最优值函数。三、动态规划的基本思想和基三、动态规划的基本思想和基本方程本方程以最短路线为例介绍动态规划的思想。常识告诉我们，最短路线有一个重要特点：如果由起点A经过B,C,D,E,F点到达终点G是一条最短的路线，则由点B出发经过C,D,E,F点到达终点G的这条子路线。就必然是从点B出发到达终点的所有可能选择的不同路线中最短的一条。此特点可用反正发来证明。根据最短路线这一特点，我们就得到了寻找最短路线的方法，假设已求得从点B出发到达终点的最短路线，再选择从A到B两
10、点间的一条最短路线，就求得了从起点A到终点G的一条最短路线。那么，如何求从点B出发到达终点的最短路线呢，再假设已求得从点C出发到达终点的最短路线，再选择从B到C两点间的一条最短路线，就求得了从起点B到终点G的一条最短路线。以这样的思路，只要能求出F到G的最短路，就可以求出E到G的最短路，从而递推的求出，D,C,B,A到G的最短路。所以动态规划方法就是从终点逐段向始点方向寻找最优解的一种方法，即就是从最后一段开始，用由后向前逐步递推的方法，求出各点到G点的最短路线，最后求得有A点到G点的最短路线。下面按照动态规划的方法求解例 2 中最短路问题.从最后一段开始，有后向前逐步递推至 A 点。当4k时
11、，由 V7到终点 B 只有一条路线，故4)(74Vf，同理，3)(84Vf 当3k时，出发点有 V4,V5,V6,三个，若从 V4,出发则有两种选择 V7,V8,一是到 V7,另一是到 V8,因此 7735)(),(743)(),(min)(8484747443VfVVdVfVVdVf 其相应的决策为743)(VVu，说明，由 V4,出发到终点的最短距离为 7，最短路线为：V4,V7,B 同理，从 V5,V6,出发，有 5732)(),(1046)(),(min)(8485747553VfVVdVfVVdVf 其相应的决策为853)(VVu，5633)(),(541)(),(min)(8486
12、747663VfVVdVfVVdVf 其相应的决策为763)(VVu 当2k时，出发点有 V1,V2,V3，若从 V1,出发则有三种选择 V4,V5,V6,一是到 V4,另一是到 V5,还有一是到 V6,因此 91055)(),(954)(),(1376)(),(min)(63615351434112VfVVdVfVVdVfVVdVf，其相应的决策为512)(VVu111156)(),(1257)(),(1578)(),(min)(63625352434222VfVVdVfVVdVfVVdVf，其相应的决策为622)(VVu 131459)(),(1358)(),(1477)(),(min)(
13、63635353434332VfVVdVfVVdVfVVdVf，其相应的决策为532)(VVu当1k时，出发点为 A,终点有三种选择：V1,V2,V3，1718135)(),(20119)(),(1798)(),(min)(3232221211VfVAdVfVAdVfVAdAf，其相应的决策为11)(VAu 于是从 A 到 B 的最短距离为 17。求得的最优决策函数序列为：11)(VAu，512)(VVu，853)(VVu，BVu)(84。从上面的计算可以看出，在求解中利用了 k 阶段与 k+1阶段之间的递推关系：1,1,0)()(),()(1111minnnkSfSfuSgSfnnkkkkU
14、kkk其中),(kkuSg是kS状态下ku的选择方式。称这一递推关系式为动态规划基本方程。四、动态规划的最优性原理四、动态规划的最优性原理（R.Bellman原理）原理）“作为整个过程的最优策略具有这样作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余对前面的决策所形成的状态而言，余下的决策必须构成最优策略。下的决策必须构成最优策略。”简言简言之，一个最优策略的子策略总是最优之，一个最优策略的子策略总是最优的。的。五、解法举例五、解法举例 现利用动态规划的基本方程求解例1中的生产与存储问题。当4k时，有 42444
15、005.0)(SuSf 由于05S，由状态方程得04445quSS 从 而 当 第 四 阶 段 的 状 态4S给 定 以 后，其 决 策 为：44441200SSqu 其指标函数的最优值为：2444244005.0117200)1200(005.0SSSSf当3k时，有)005.0117200005.0(min)(005.0(min)(244323443233333SSSuSfSuSfuu 由于，500333334uSquSS，则)500(005.0)500(117200005.0(min)(005.0(min)(23333323443233333uSuSSuSfSuSfuu 现假设3S给定的
16、情况下，确定最优决策3u，使指标函数)(33Sf最小。根据极值原理；0)(333duSdf 得到决策值为：335.0800Su 其指标函数的最优值为：23330025.077550SSf 当2k时，有)0025.077550005.0(min)(005.0(min)(233222332222222SSSuSfSuSfuu 由于，700222223uSquSS，则 )700(0025.0)700(77550005.0(min)(005.0(min)(22222222332222222uSuSSuSfSuSfuu现假设2S给定的情况下，确定最优决策2u，使指标函数)(22Sf最小。根据极值原理；0
17、)(222duSdf 得到决策值为：225.0700Su 其指标函数的最优值为：22223005.0610000SSf 当1k时，)3005.0610000005.0(min)(005.0(min)(222121122121111SSSuSfSuSfuu 由于，600111112uSquSS，则)600(3005.0)600(610000005.0(min)3005.0610000005.0(min)(005.0(min)(211111211222121122121111uSuSSuSSSuSfSuSfuuu现假设1S给定的情况下，确定最优决策1u，使指标函数)(11Sf最小。根据极值原理；0
18、)(111duSdf 得到决策值为：1141600Su 其指标函数的最优值为：21114005.0511800SSf 注意到01S，回代就可以求出决策序列和指标函数的最优值，从而得到本问题的最终解：90030080007000600044332211uSuSuSuS 一年内的生产与库存的总费用为：11800)(11Sf元。若按每季度的订货量生产，即取4,3,2,1,kqukk，则由该问题的数学模型可求得：127001f元，一年内多耗费 900 元。2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106
19、104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f52242511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=51124211411
20、13DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121
21、213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D
22、1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(
23、f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2
24、(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C12511214106104131112396581052C1C3D1AB1B3B2D2
25、EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB2C1D1E六、动态规划的应用
