第二部分动态规划（dymamic programming）
第三章动态规划。
动态规划是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如lp 单纯形法）。因此它不象lp 那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。
动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定性、离散随机性、连续确定性和连续随机性。
1动态规划的基本概念和最优化原理。
一、引例（最短路线问题）
上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由a 到e 的铺管线路，使总距离最短（或总费用最小）。
将该问题划分为4个阶段的决策问题，即第一阶段为从a 到b j （j=1，2，3），有三种决策方案可供选择；第二阶段为从b j 到c j （j=1,2,3），也有三种方案可供选择；第三阶段为从c j 到d j (j=1,2，有两种方案可供选择；第四阶段为从d j 到e ，只有一种方案选择。如果用完全枚举法，则可供选择的路线有3
3×2×1=18（条），将其一一比较才可找出最短路线：
a →b 1→c 2→d 3→e
其长度为15。
显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求a 到e 的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至a 点：
第四阶段，由d 1到e 只有一条路线，其长度f 4（d 1）=4，同理f 4（d 2）=3。 第三阶段，由c j 到d i 分别均有两种选择，即。
6+4*c 1d 1+f 4(d 1
f 3(c 1=min =10，决策点为d 1 =min (c d +f d 42128+3
c d +f 4(d 13+4*f 3(c 2=min 21=min 5+3=7, 决策点为d 1 (c d +f d 4222
c d +f 4(d 18+4
f 3(c 3=min 31=min =8，决策点为d 2 *
5+3c 3d 2+f 4(d 2
第二阶段，由b j 到c j 分别均有三种选择，即：
b 1c 1+f 3(c 11+10
min *=10，决策点为c (f 2(b 1=min b c +f c 222323+7
6+8b 3c 3+f 3(c 3
b 2c 2+f 3(c 18+10
min *=14，决策点为c 或c (f 2(b 2=min b c +f c 237+72232*
6+8b 3c 3+f 3(c 3b 3c 1+f 3(c 12+10
min *=11，决策点为c (f 2(b 3=min b c +f c 232324+7
6+8b 3c 3+f 3(c 3
第一阶段，由a 到b ，有三种选择，即：
ab 1+f 2(b 25+10*
min =15，决策点为b 1 (f 1(a =min ab +f b 2223+14
5+11ab 5+f 2(b 5
f 1(a=15说明从a 到e 的最短铺管线长为1，最短路线的确定可按计算顺序反推而得。即。
a →b 1→c 2→d 1→e
图中各点上方框的数，表示该点到e 的最短距离。图中双箭线表示从a 到e 的最短路线。
从引例的求解过程可以得到以下启示：
对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的多个阶段的决策问题。
所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：
在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要。
注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。
各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。
决策过程是与阶段发展过程逆向而行。 二、动态规划的基本概念。
1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k 表示。
如引例可划分为4个阶段求解，k=1，2，3，4。
2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。
1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用s k 表示第k 阶段的状态变量。
通常一个阶段有若干个状态。第k 阶段的状态就是该阶段所有始点的集合。如引例中。
s 1=，s 2=，s 3=，s 4=
2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。
在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点去规定状态变量，而要充分注意是否满足无后效性要求。
3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。
常用d k (sk 表示第k 阶段处于状态s k 时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用d k (sk 表示。显然d k （s k ）∈d k (sk 。
如在引例的第一阶段中，若从b 1出发，d 2（b 1）=，如果决定选取c 2，则d 2（b 1）=c2。
4、策略与子策略。策略是一个决策序列的集合。当k=1时，p in （s 1）=就称为全过程的一个策略，简称策略，简记为p in (s1.
称p k,n (sk = 为由第k 阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为p k,n (sk
称可供选择策略的范围，为允许策略集，用p 表示。 动态规划方法就是要从允许策略集p 中找出最优策略p in *。
5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用s k+1=tk (sk ,d k 表示。该方程描述了由第k 阶段到第k+1阶段的状态转移规律。
因此又称其为状态转移函数。
6、阶段指标、指标函数和最优指标函数。
1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用v k (sk ,d k 表示第k 阶段的阶段指标。
在不同的问题中，其含义不同。它可以是距离、利润、成本等。 在引例中，用d k =uk (sk ,d k 表示在第k 阶段由点s k 到点s k+1=dk (sk 距离。
如d 2(b3,c 1=2。
2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为v k,n (sk ,p k,n .
v k,n (sk ,p k,n =vk,n (sk ,d k ,s k+1, s n+1 k=1,2,,n 。
构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。 常见的指标函数的形式有： ①v k , n (s k , u k , s k +1 , s n +1=
v (sj j =k
n j =knj
d j =v k (s ku , d k +v k +1, k (s k +1, p k , n
v k , n (s k , u k , s k +1 , s n +1=∏u i (s j u j =v k (s ku , d k v k +1(s k +1, d k +1 s n +1 （3）最优指标函数f k (sk , 表示从第k 阶段的状态s k 开始采用最优子策略p*k,n ，到第n 阶段的终止时所得到的指标函数值。
即f k (sk =0ptvk,n (sk ,u k , s n+1
其中0pt 是最优化（0ptimiyation ）的缩写，可根据题意取max 或min 。 在引例中，指标函数v k,n 表示在第k 阶段由点s k 至终点e 的距离。f k (sk 表示第k 阶段点s k 到终e 的最短距离。
f 2(b1=10表示从第2阶段中的点b 1到点e 的最短距离。
7、基本方程（递推关系式）
从引例求a 到e 的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了k 阶段与k+1阶段之间的递推关系；
u k (s k , d k +f k +1(s k +1}f k (s k =min , f k (s k =0pt f k (s k =0pt {d k (s k ∈d k (s k , k =n , n -1, 1 f n +1(s n +1 =1(边界条件。
运筹学讲义
第六讲排队论。x y zx处填写表示相继到达间隔时间的分布 y处填写表示服务时间的分布 z处填写并列的服务台的数目c.c 1 单服务台，c 1 多服务台。表示相继到达间隔时间和服务时间的各种分布的符号 m 负指数分布。d 确定型。ek k阶爱尔朗分布。gi 一般相互独立的时间间隔的分布。g 一般服务...
运筹学讲义
第三讲整数规划。一 整数规划模型。12年，第一题，15分 一家公司打算在甲地 乙地或甲乙两地新建工厂，一地至多建一个工厂，并且在甲乙两地至多建一个仓库，仓库位置随工厂地点而定 即，如某地有工厂，该地可设仓库或不设仓库 但如该地不设工厂，则该地一定不设仓库 若总资本可用量为20 百万元 其他数据如下表...
运筹学讲义
第三部分图与网络分析。图与网络分析部分内容框架。图与网络的基本概念。图连通图。图的矩阵表示。树与最小树。最短路问题。图论在网络分析的应用最大流问题。最小费用最大流问题。第四章图与网络分析。1.图与网络的基本概念。一 图及其分类。本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有...