动态规划(完整)

【数学建模】数学模型总结 吴翔

1 四类基本模型

1 优化模型

1.1 数学规划模型

线性规划、整数线性规划、非线性规划、多目标规划、动态规划。

1.2 微分方程组模型

阻滞增长模型、SARS传播模型。

1.3 图论与网络优化问题

最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。

1.4 概率模型

决策模型、随机存储模型、随机人口模型、报童问题、Markov链模型。

1.5 组合优化经典问题

 多维背包问题(MKP)

背包问题：n个物品，对物品i，体积为iw，背包容量为W。如何将尽可能多的物品装入背包。

多维背包问题：n个物品，对物品i，价值为ip，体积为iw，背包容量为W。如何选取物品装入背包，是背包中物品的总价值最大。

多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP难问题。

 二维指派问题(QAP)

工作指派问题：n个工作可以由n个工人分别完成。工人i完成工作j的时间为ijd。如何安排使总工作时间最小。

二维指派问题（常以机器布局问题为例）：n台机器要布置在n个地方，机器i与k之间的物流量为ikf，位置j与l之间的距离为jld，如何布置使费用最小。

二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。

 旅行商问题(TSP)

旅行商问题：有n个城市，城市i与j之间的距离为ijd，找一条经过n个城【数学建模】数学模型总结 吴翔

2 市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。

 车辆路径问题(VRP)

车辆路径问题（也称车辆计划）：已知n个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。

《运筹学》习题答案

一、单选题

1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）B

A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络

2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）B

A.非线性问题的线性化技巧 B.静态问题的动态处理

C.引入虚拟产地或者销地 D.引入人工变量

3.静态问题的动态处理最常用的方法是？B

A.非线性问题的线性化技巧 B.人为的引入时段

C.引入虚拟产地或者销地 D.网络建模

4.串联系统可靠性问题动态规划模型的特点是（ ）D

A.状态变量的选取 B.决策变量的选取

C.有虚拟产地或者销地 D.目标函数取乘积形式

5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C

A.降低的 B.不增不减的 C.增加的 D.难以估计的

6.最小枝权树算法是从已接接点出发，把( )的接点连接上C

A.最远 B.较远 C.最近 D.较近

7.在箭线式网络固中，( )的说法是错误的。D

A.结点不占用时间也不消耗资源

B.结点表示前接活动的完成和后续活动的开始

C.箭线代表活动

D.结点的最早出现时间和最迟出现时间是同一个时间

8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C

A.1200 B.1400 C.1300 D.1700

9.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（ ）。D

A.最短路线—定通过A点 B.最短路线一定通过B点

C.最短路线一定通过C点 D.不能判断最短路线通过哪一点

10.在一棵树中，如果在某两点间加上条边，则图一定( )A

A.存在一个圈 B.存在两个圈 C.存在三个圈 D.不含圈

01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >=

Wi ), f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

Pi表示第i件物品的价值。

决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？

题目描述：

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

name weight value 1 2 3 4 5 6 7 8 9 10

a 2 6 0 6 6 9 9 12 12 15 15

15

b 2 3 0 3 3 6 6 9 9 9 10 11

c 6 5 0 0 0 6 6 6 6 6 10 11

d 5 4 0 0 0 6 6 6 6 6 10 10

e 4 6 0 0 0 6 6 6 6 6 6 6

只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。

首先要明确这张表是至底向上，从左到右生成的。

为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。

对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。

同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？

根据01背包的状态转换方程，需要考察两个值，

一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；

DP⼊门（2）——DAG上的动态规划

有向⽆环图（DAG,Directed Acyclic Graph）上的动态规划是学习动态规划的基础。很多问题都可以转化为DAG上的最长路、最短路或路径

计数问题。

⼀、DAG模型

【嵌套矩形问题】

问题：有n个矩形，每个矩形可以⽤两个整数a、b描述，表⽰它的长和宽。矩形X(a , b)可以嵌套在矩形Y(c , d)中当且仅当a

b

了最后⼀个之外，每个矩形都可以嵌套在下⼀个矩形内。如果有多解，矩形编号的字典序应尽量⼩。

分析：矩形之间的“可嵌套”关系是⼀个典型的⼆元关系（我的理解是两个矩形之间存在关系），⼆元关系可以⽤图来建模。如果矩形X可以

嵌套在矩形Y⾥，就从X到Y连⼀条有向边。这个有向图必然是⽆环的，因为⼀个矩形⽆法直接或间接地嵌套在⾃⼰内部。换句话说，它是⼀

个DAG。这样，所要求的便是DAG上的最长路径。

【硬币问题】

问题：有n种硬币，⾯值分别为V1, V2, ..., Vn，每种都有⽆限多。给定⾮负整数S，可以选⽤多少个硬币，使得⾯值之和恰好为S？输出硬币

数⽬的最⼩值和最⼤值。1 <= n <= 100, 0 <= S <= 10000, 1 <= Vi <= S。

分析：此问题尽管看上去和嵌套矩形问题很不⼀样，但本题的本质也是DAG上的路径问题。将每种⾯值看作⼀个点，表⽰“还需要凑⾜的⾯

值”，则初始状态为S，⽬标状态为0。若当前在状态 i，每使⽤⼀个硬币 j，状态便转移到i - Vj 。

补充：这个模型和上⼀题类似，但也有⼀些明显地不同之处：上题并没有确定路径的起点和终点（可以把任意矩形放在第⼀个和最后⼀

个），⽽本题的起点必须为S，终点必须为0 。点固定之后“最短路”才是有意义的。在上题中，最短序列显然是空（如果不允许空，就是单个

矩形，不管怎样都是平凡的），⽽本题的最短路径却不容易确定。

⼆、最长路及其字典序（嵌套矩形）

如何求DAG中不固定起点的最长路径呢？

仿照数字三⾓形的做法，设d（i）表⽰从结点 i 出发的最长路长度，应该如何写状态转移⽅程呢？第⼀步只能⾛到它的相邻点，因此：