下载文档原格式
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
动态规划讲解大全含例题及答案动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。
例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。
我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。
基本模型多阶段决策过程的最优化问题。
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
动态规划例题动态规划是一种以最优化原理为基础的问题求解方法，通过拆分问题为若干阶段，每个阶段求解一个子问题，再逐步推导出整个问题的最优解。
例如，有一个背包能够承受一定的重量，现有一些物品，每个物品都有自己的重量和价值。
我们希望将物品放入背包中，使得背包的总价值最大。
这个问题可以用动态规划来解决。
首先，我们定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，容量为j的背包中所能放入的物品的最大价值。
那么，对于每一个物品，可以选择放入背包或者不放入背包。
如果选择放入背包，最大价值为dp[i-1][j-w[i]] + v[i]，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
如果选择不放入背包，最大价值为dp[i-1][j]。
因此，dp[i][j]的状态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j])。
基于这个状态转移方程，可以逐步求解从第1个物品到第n个物品的最大价值。
最终，dp[n][W]即为问题的最优解，其中W 表示背包的容量。
举个简单的例子，假设背包的容量为10，有3个物品，它们的重量分别为3、4、5，价值分别为4、5、6。
此时，可以得到如下的dp矩阵：0 0 0 0 0 0 0 0 0 0 00 0 0 4 4 4 4 4 4 4 40 0 0 4 5 5 9 9 9 9 90 0 0 4 5 5 9 10 10 14 14我们可以看到，dp[3][10]的最大价值为14，表示在前3个物品中，容量为10的背包中所能放入的物品的最大价值为14。
通过动态规划，我们可以有效地求解背包问题，得到物品放入背包的最优解。
这个例子只是动态规划的一个简单应用，实际上，动态规划可以解决各种复杂的问题，如最长公共子序列、最大子数组和、最大字段和等。
因此，学习动态规划是非常有意义的。
动态规划作业1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线?把A看作终点，该问题可分为4个阶段。
f k(S k)表示从第K阶段点S k到终点A的最短距离。
f4(B1)=20，f4(B2)=40，f4(B3)=30f3(C1)=min[d3(C1,B1)+ f4(B1), d3(C1,B2)+ f4(B2), d3(C1,B3)+ f4(B3) ]=70，U3(C1)= B2 或B3f3(C2)=40 ，U3(C2)= B3f3(C3)=80 ，U3(C3)= B1或B2 或B3f2(D1)=80 ，U2(D1)= C1f2(D2)=70 ，U2(D2)= C2f1(E)=110 ，U1(E)= D1或D2所以可以得到以下最短路线，E→D1→C1→B2 / B3→AE→D2→C2→B3→A2、习题4－2解：1)将问题按地区分为三个阶段，三个地区的编号分别为1、2、3；2)设Sk表示为分配给第k个地区到第n个地区的销售点数，Xk表示为分配给第k个地区的销售点数，S k＋1＝S k－X kPk(Xk)表示为Xk个销售点分到第k个地区所得的利润值fk(Sk)表示为Sk个销售点分配给第k个地区到第n个地区的最大利润值3)递推关系式：fk(Sk)＝max[ Pk(Xk)+ f k+1(S k－X k) ] k=3,2,1f4(S4)＝04）从最后一个阶段开始向前逆推计算第三阶段：设将S3个销售点（S3＝0,1,2,3,4）全部分配给第三个地区时，最大利润值为：f3(S3)＝max[P3(X3)] 其中X3＝S3＝0,1,2,3,4表1第二阶段：设将S2个销售点（S2＝0,1,2,3,4）分配给乙丙两个地区时，对每一个S2值，都有一种最优分配方案，使得最大盈利值为：f2(S2)＝max[ P2(X2)+ f3(S2－X2) ]其中，X2＝0,1,2,3,4表2第一阶段：设将S1个销售点（S1＝4）分配给三个地区时，则最大利润值为：f1(S1)＝max[ P1(X1)+ f2(4－X1) ]其中，X1＝0,1,2,3,4表3然后按计算表格的顺序反推，可知最优分配方案有两个：最大总利润为531）由X1*＝2，X2*＝1，X3*＝1。
1.用动态规划的逆序法求解下面问题:
⎩⎨
⎧=≥>=++⨯⨯=3,2,1,0)
0(..max 3213
2
21i x c c x x x t s x x x Z i
2.（运筹学书9.3） 某公司打算向它的三个营业区增设六个销售店，每个营业区至少增设一个。
从各区赚取的利润（单位为万元）与增设的销售店个数有关，其数据如下。
销售店增加数
A 区利润
B 区利润
C 区利润 0 100 200 150 1 200 210 160 2 280 220 170 3 330 225 180 4
340
230
200
试求各区应分配几个增设的销售店，才能使总利润最大？其值是多少？
3.（运筹学书9.4）某工厂有100台机器，拟分四个周期使用，在每一周期有两种生产任务。
据经验，把机器x 1台投入第一种生产任务，则在一个生产周期中将有x 1/3台机器作废；余下的机器全部投入第二种生产任务，则有1/10台机器作废。
如果干第一种生产任务每台机器可收益10，干第二种生产任务每台机器可收益7。
问怎样分配机器，使总收益最大？
4.（运筹学书 例2）机器负荷分配问题。
某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u 1，其中u 1为投入生产的机器数量，年完好率a=0.7；在低负荷下生产的产量函数为h=5y ，其中y 为投入生产的机器数量，年完好率为b=0.9。
假定开始生产时完好的机器数量s 1=1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。
如果s 6=500台，如何分配？。
动态规划作业1、1、设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线?把A看作终点，该问题可分为4个阶段。
f k(S k)表示从第K阶段点S k到终点A的最短距离。
f4(B1)=20，f4(B2)=40，f4(B3)=30f3(C1)=min[d3(C1,B1)+ f4(B1), d3(C1,B2)+ f4(B2), d3(C1,B3)+ f4(B3) ]=70，U3(C1)= B2 或B3f3(C2)=40 ，U3(C2)= B3f3(C3)=80 ，U3(C3)= B1或B2 或B3f2(D1)=80 ，U2(D1)= C1f2(D2)=70 ，U2(D2)= C2f1(E)=110 ，U1(E)= D1或D2所以可以得到以下最短路线，E→D1→C1→B2 / B3→AE→D2→C2→B3→A2、习题4－2解：1)将问题按地区分为三个阶段，三个地区的编号分别为1、2、3；2)设Sk表示为分配给第k个地区到第n个地区的销售点数，Xk表示为分配给第k个地区的销售点数，S k＋1＝S k－X kPk(Xk)表示为Xk个销售点分到第k个地区所得的利润值fk(Sk)表示为Sk个销售点分配给第k个地区到第n个地区的最大利润值3)递推关系式：fk(Sk)＝max[ Pk(Xk)+ f k+1(S k－X k) ] k=3,2,1f4(S4)＝04）从最后一个阶段开始向前逆推计算第三阶段：设将S3个销售点（S3＝0,1,2,3,4）全部分配给第三个地区时，最大利润值为：f3(S3)＝max[P3(X3)] 其中X3＝S3＝0,1,2,3,4表1第二阶段：设将S2个销售点（S2＝0,1,2,3,4）分配给乙丙两个地区时，对每一个S2值，都有一种最优分配方案，使得最大盈利值为：f2(S2)＝max[ P2(X2)+ f3(S2－X2) ]其中，X2＝0,1,2,3,4表2第一阶段：设将S1个销售点（S1＝4）分配给三个地区时，则最大利润值为：f1(S1)＝max[ P1(X1)+ f2(4－X1) ]其中，X1＝0,1,2,3,4表3然后按计算表格的顺序反推，可知最优分配方案有两个：最大总利润为531）由X1*＝2，X2*＝1，X3*＝1。
