有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了五 座金矿，并且这五座金矿在地图上排成一条直线，国王知道这个消息后非常 高兴，他希望能够把这些金子都挖出来造福国民，首先他把这些金矿按照在 地图上的位置从北至南进行编号，依次为1、2、3、4、5，然后他命令他的 手下去对每一座金矿进行勘测，以便知道挖取每一座金矿需要多少人力以及 每座金矿能够挖出多少金子，然后动员国民都来挖金子。 补充1：挖每一座金矿需要的人数是固定的，多一个人少一个人都不行。国王知 道每个金矿各需要多少人手，金矿i需要的人数为pi。 补充2：每一座金矿所挖出来的金子数是固定的，当第i座金矿有pi 人去挖的话， 就一定能恰好挖出gi个金子。否则一个金子都挖不出来。 补充3：开采一座金矿的人完成开采工作后，他们不会再次去开采其它金矿，因 此一个人最多只能使用一次。 补充4：国王在全国范围内仅招募到了50000名愿意为了国家去挖金子的人，因 此这些人可能不够把所有的金子都挖出来，但国王希望挖到的金子越多越好。 补充5：有很多人拿到这个题后的第一反应就是对每一个金矿求出平均每个人能 挖出多少金子，然后从高到低进行选择，这里要强调这种方法是错的，如果 你也是这样想的，请考虑背包模型，当有一个背包的容量为10，共有3个物 品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两 个物品，总价值是12，但明显最大值是后两个物品组成的15。

运筹学——动态规划 樊保强 数学与统计科学学院 鲁东大学

第一讲 引入

一、动态规划(Dynamic Programming DP) 动态规划的主要创始人是美国数学家贝 尔曼（Richard Bellman）。20世纪40 年代末50年代初，当时在兰德公司从事 研究工作的贝尔曼首先提出了动态规划 的概念。1951年贝尔曼提出了动态规划 中解决多阶段决策问题的最优化原理， 并给出了许多实际问题的解法。1957年 贝尔曼出版了他的第一部著作《动态规 划》，标志着运筹学这一重要分支的诞 生。该著作成为当时唯一的进一步研究 和应用动态规划的理论源泉。1961年贝 尔曼出版了他的第二部著作，并于1962 年同杜瑞佛思合作出版了第三部著作。 R. Bellman. Dynamic Programming. Princeton University Press. N.J. 1957.

一、动态规划 在贝尔曼及其助手们致力于发展和推广这一技术的同 时，其他一些学者也对动态规划的发展作了巨大的贡 献，其中最值得一提的是爱尔思和梅特顿。爱尔思先 后于1961年和1964年出版了两部关于动态规划的著作， 并于1964年同尼母霍思尔、威尔德一道创建了处理分 支、循环性多阶段决策系统的一般性理论。梅特顿提 出了许多对动态规划后来发展有着重要意义的基础性 观点，并且对明晰动态规划路径的数学性质作出了巨 大的贡献。 目前约有100多部关于DP的英文书籍。 http://gen.lib.rus.ec/search.php?req=dynamic+programming&o pen=0&view=simple&column=def

一、动态规划-最短路问题-01 下图给出了从起点A(V1)到终点E(V10)之间各点对间的距离。求A到E的最短路径。 10 v2 v7 5 13 v5 8 2 6 7 8 8 v1 v3 v8 v10 10 12 5 5 13 v6 4 8 v4 v9 11 第1阶段 第2阶段 第3阶段 第4阶段 阶段： 第5阶段 状态： v1 v2, v3, v4 v5, v6 v7, v8, v9 v10

一、动态规划-最短路问题-02 Min{2+5,8+8,6+4}=7 17 5 10 v2 v7 5 7 2 13 v5 8 2 6 14 19 10 12 5 5 13 v6 4 8 12 v4 v9 11 20 4 第1阶段 第2阶段 第3阶段 第4阶段 阶段： 第5阶段

一、动态规划-基本特征-01 问题具有多阶段决策的特征: 阶段可按时间划分，也可按空 间划分。 每一阶段都有相应的“状态”与之对应 每一阶段的某个状态都面临若干个决策，选择不同的决策 将会导致下一阶段不同的状态，同时，不同的决策将会导 致这一阶段不同的目标函数值 每一阶段的最优解问题可以递归地归结为下一阶段各个可 能状态的最优解问题，各子问题与原问题具有完全相同的 结构。 注：动态规划解决问题的关键将问题归结为一个递推过程， 建立一个递推的指标函数求最优解。这种递推归结的过程， 称为“不变嵌入”。

一、动态规划-基本特征-02 状态具有无后效性: 当某阶段状态确定后，此阶段以 后过程的发展不受此阶段以前各阶段状态的影响。

一、动态规划-基本原理 作为整个过程的最优策略具有如下的性质：不管在 此最优策略上的某个状态以前的状态和决策如何， 对该状态来说，以后的所有决策必定构成最优子策 略。也就是说最优策略的任一子策略都是最优的。 对最短路问题来说即为从最短路上的任一点到终点 的部分道路（最短路上的子路）也一定是从该点到 终点的最短路（最短子路）。 注：基本原理一方面说明原问题的最优解中包含了子问题的最优解，另 一方面给出了一种求解问题的思路，将一个难以直接解决的大问题， 分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结 果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个 击破，分而治之，即分治法，是一种解决最优化问题的算法策略。

一、动态规划-基本方程-01 如果用穷举法，则从A到E一共有3×3×2＝18条不同的路径，逐个计算每条路径的长度，总共需要进行4×18＝72次加法计算；对18条路径的成本做两两比较，找出其中最短的一条，总共要进行18－1＝17次比较。 前面求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。 记从Bi (i=1, 2, 3) 到E的最短路径为f(Bi)，则从A到E的最短距离f(A)可以表示为：

同样，计算f(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1、C2、C3到E的最短路径问题f(Ci) (i=1, 2, 3)；而求f(Ci)又可以归结为求f(D1)和f(D2)这两个子问题。从右图可以看出，在这个问题中，f(D1)和f(D2)是已知的，它们分别是： f(D1)=5，f(D2)=2 因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下： 即 f(C1)=8 如果到达C1，则下一站应到达D1； f(C2)=7 如果到达C2，则下一站应到达D2； f(C3)=12 如果到达C3，则下一站应到达D2。

由此，可以计算f(Bi)： 即 f(B1)=20 如果到达B1，则下一站应到达C1； f(B2)=14 如果到达B2，则下一站应到达C1；

一、动态规划-基本方程-04 由此，可以计算f(A)： 所以，从A到E的最短路径为A→B2→C1→D1→E，即按此路线，运输成本最低。 计算过程及结果，可用图5.3表示，可以看到，以上方法不仅得到了从A到E的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了18次加法，11次比较，计算效率高于穷举法。

一、动态规划-基本方程-05 对于n阶段的动态规划问题，在求子过程上的最优指 标函数时，k子过程与k+1子过程有如下递推关系：

Thanks

第二讲 动态规划初步

二、动态规划-01 1.动态规划是解决多阶段决策过程最优化问题的一种理论和方法。它是一种解决问题的思路，而不是一种算法。因此，在应用动态规划方法求解多阶段决策问题时，要对具体问题进行具体分析。 2.动态规划问题的模型分为离散确定性的动态规划模型、连续确定性的动态规划模型、离散随机性的动态规划模型和连续随机性的动态规划模型四大类。 3.动态规划的基本概念有阶段与阶段变量，状态与状态变量，决策与决策变量，策略与最优策略，状态转移方程以及指标函数与最优指标函数等。它们是分析动态规划问题，建立动态规划模型，求解模型和解决实际问题的基础。 4.动态规划问题的基本方程为： Ludong University 2019/4/15

二、动态规划-02 5.给一个实际问题建立动态规划模型时，必须做到： （1）将问题的过程划分成恰当的阶段； （2）正确选择状态变量sk，使它既能描述过程的演变，又要满足无后效性； （3）确定决策变量uk(sk)及每阶段的允许决策集合Dk(sk)； （4）正确写出状态转移方程； （5）正确写出指标函数Vkn的关系式。 6.动态规划问题的求解方法主要有逆序解法和顺序解法，两者无本质的区别。 一般将问题分成几个阶段，从最后一段开始，用由后向前逐步递推的方法来求解问题，我们称为逆序解法；反之从起点到终点则为顺序解法。当初始状态给定时，用逆序解法；当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。 Ludong University 2019/4/15

三、动态规划-案例 在前一节有关动态规划基本概念、基本原理和模型的阐述中，我们已经基本了解了最短路径问题的动态规划解法。下面我们接着介绍几个动态规划应用的实际例子。 生产计划问题 资源分配问题 配载问题 存储问题 维修问题

四、生产计划问题 设某公司要制订一项n个阶段的生产计划，已知其初始库存为零，每阶段生产此产品的数量有上限（为m）的限制，且社会对此产品的需求量已知，公司保证供应，在n阶段终结时的库存为零。试制订一个总成本（包括生产成本和储存成本）最小的计划。 阶段数N=n； 状态变量sk：第k阶段结束时的产品库存量； 决策变量uk：第k阶段产品的生产量； 状态转移方程：sk＝sk-1＋uk－ak，其中ak为第k阶段产品的需求量； 阶段效益：dk(sk, uk)＝ck(uk)＋hk(uk)，其中ck(uk)为第k阶段的生产费用，hk(uk)为第k阶段的存储费用； 最优值函数：fk(sk) ：表示从第1阶段到第k阶段生产与库存的最小总费用。 Ludong University 2019/4/15

2019/4/15 四、生产计划问题（续） 设某公司要制订一项n个阶段的生产计划，已知其初始库存为零，每阶段生产此产品的数量有上限（为m）的限制，且社会对此产品的需求量已知，公司保证供应，在n阶段终结时的库存为零。试制订一个总成本（包括生产成本和储存成本）最小的计划。 阶段数N=n； 状态变量sk：第k阶段结束时的产品库存量； 决策变量uk：第k阶段产品的生产量； 状态转移方程：sk＝sk-1＋uk－ak，其中ak为第k阶段产品的需求量； 阶段效益：dk(sk, uk)＝ck(uk)＋hk(uk)，其中ck(uk)为第k阶段的生产费用，hk(uk)为第k阶段的存储费用； 最优值函数：fk(sk) ：表示从第k阶段到计算期末生产与库存的最小总费用。 逆序递推关系式为： 其中 。 Ludong University 2019/4/15

五、资源分配问题 资源分配问题就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，或投资于几家企业，以获得最大的效益。 设有m种资源，总量分别为bi(i=1,2,…,m)，用于生产n种产品，若用uij代表用于生产第j种产品的第i种资源的数量(j=1,2,…,n)，则生产第j种产品的收益是其所使用的各种资源数量的函数，即gj=f(u1j,u2j,…, umj)。由于总收益是n种产品收益之和，此问题可用如下静态模型加以描述： 当gj是线性函数时，该模型是LP模型；当gj是非线性函数时，该模型是MP模型。此模型用LP或MP来求解都将是非常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。 Ludong University 2019/4/15

五、资源分配问题（续） 资源分配问题就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，或投资于几家企业，以获得最大的效益。 这里只考虑一维资源的分配问题，设状态变量sk表示分配于从第k个阶段至过程最终（第n个阶段）的资源数量，即第k个阶段初资源的拥有量；决策变量uk表示第k个阶段资源的分配量。 状态转移律： sk+1=sk-uk 允许决策集合： Dk(sk)={uk|0≤uk≤sk} 最优指标函数（动态规划的逆序递推关系式）： 利用这一递推关系式，最后求得的f1(s1)即为所求问题的最大总收益。 Ludong University 2019/4/15

六、资源分配问题 某公司拟将5台叉车设备发给3个物流中心，各部门用这种设备后产生的盈利如下表所示，问如何分配这五台设备才能使得盈利最大？ 设备台数 甲 乙 丙 1 2 3 4 5 7 9 12 13 10 11 6 Ludong University 2019/4/15

六、资源分配问题-求解 某公司拟将5台叉车设备发给3个物流中心，各部门用这种设备后产生的盈利如下表所示，问如何分配这五台设备才能使得盈利最大？ 设状态变量sk表示分配于从第k个阶段至过程最终（第n个阶段）的资源数量，即第k个阶段初资源的拥有量；决策变量uk表示第k个阶段资源的分配量。 状态转移律： sk+1=sk-uk 允许决策集合： Dk(sk)={uk|0≤uk≤sk} 最优指标函数（动态规划的逆序递推关系式）： 其中sk+1=sk-uk。 利用这一递推关系式，最后求得的f1(5)即为所求问题的最大盈利。 Ludong University 2019/4/15

六、资源分配问题-求解（续） 某公司拟将5台叉车设备发给3个物流中心，各部门用这种设备后产生的盈利如下表所示，问如何分配这五台设备才能使得盈利最大？ 设状态变量sk表示分配于从第1个至第k个阶段的资源数量，即第k个阶段末资源的使用量；决策变量uk表示第k个阶段资源的分配量。 状态转移律： sk=sk-1+uk 允许决策集合： Dk(sk)={uk|0≤uk≤sk} 最优指标函数（动态规划的顺序递推关系式）： 其中sk=sk-1+uk。 利用这一递推关系式，最后求得的f3(0)即为所求问题的最大盈利。 Ludong University 2019/4/15

七、配货问题 有一辆最大货运量为13t、最大容量为10件的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？ 货物编号I 1 2 3 单位重量（t） 6 单位价值ci (万元) 4 5 8 设状态变量xk和yk分表表示从第k个阶段至过程最终（第n个阶段）的最大货运量和最大容量；决策变量uk表示第k个阶段的装载第k个货物的数量。 状态转移： xk+1=xk-uk， yk+1=yk-vk 允许决策集合： Dk(xk,yk)={uk|0≤ akuk≤xk,0≤ bkuk≤yk} 最优指标函数（动态规划的逆序递推关系式）： Ludong University 2019/4/15

八、资源分配问题 设有6万元资金用于4个仓库的扩建，已知每个仓库的利润增长额同投资额的大小有关，见下表。问应如何确定对这4个仓库的投资额，使总利润增长额最大？(表内数据是利润额gi(xj))。 投资额(j) 仓库(i) 100 200 300 400 500 600 1 20 42 60 75 85 90 2 15 45 57 65 70 73 3 18 39 61 78 95 4 28 47 74 80 Ludong University 2019/4/15

八、资源分配问题-求解 设有6万元资金用于4个仓库的扩建，已知每个仓库的利润增长额同投资额的大小有关，见下表。问应如何确定对这4个仓库的投资额，使总利润增长额最大？(表内数据是利润额gi(xj)) 设状态变量sk表示分配于从第k个仓库至最后一个仓库的资金数，即第k个阶段初资金总数；决策变量xk表示第k个仓库资金的分配额度。 状态转移律： sk+1=sk-xk 允许决策集合： Dk(sk)={xk|0≤xk≤sk} 最优指标函数（动态规划的逆序递推关系式）： 其中sk+1=sk-xk。 利用这一递推关系式，最后求得的f1(60000)即为所求问题的最大盈利。 Ludong University 2019/4/15

九、维修问题 某港口新设备的年效益及年均维修费、更新费用如下表所示。试确定今后5年内的更新策略，使总收益最大。 单位：万元 役龄(年） 项目 1 2 3 4 5 效益rk(t) 4.5 3.75 2.5 维修费uk(t) 0.5 1.5 更新费ck(t) Ludong University 2019/4/15

案例 有一个牧场，开始时有200头牲畜，场主在每年初需要 作出决策：要卖出多少头，继续饲养多少头。已知一 年间饲养和繁殖的结果：年末头数是年初的1.4倍。每 头每年的饲养费用是300元（以年初头数计），如果卖 出，每头价格p与卖出头数u的关系是 P=2000-0.2u, 0 ≤u ≤10000 现场主需要做一个5年决策计划，使总收入最大。