运筹基础课程 9

1Lecture8

DynamicProgrammingSchoolofBusinessAdministrationHunanUniversityLecturer:E-mail:

2LectureOutlineWhat’sDynamicProgramming？SolutionMethodofDPApplicationsofDP31.什么是动态规划?

动态规划是1951年美国学者贝尔曼(Bellman)等在解决多阶段决策问题时提出。该方法在进行多阶段决策时，先将问题变成一系列相互联系的单阶段问题，在解决了这些单阶段问题后，在最优性原理基础上解决多阶段决策问题。4TheApplicationsof

DynamicProgramming最优路径问题资源分配问题生产计划、排序问题、库存问题生产过程的最优控制投资问题装载问题5多阶段决策问题

多阶段决策过程是指这样一类特殊的活动过程，它们可按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。1n2状态决策状态决策状态…状态决策状态6Aprototypeexample

例1：最短路径问题

如图所示，要从①地到⑩地，如何走才能使总路程最短，最短路程是多少？53123456798102474363244114633347BasicConceptsofDP阶段(Stage)状态(State)决策(Decision)策略(Strategy)状态转移方程(StateTransformationFunction)指标函数(ReturnFunction)8BasicConceptsofDP(1)阶段(Stage)将所给定问题的决策过程，按时间或空间特征分解成若干个相互联系的阶段，以便表示决策顺序的时段序列。

阶段变量k，按顺序对划分后的阶段编号。kDiscreteContinuouskCertainUncertain第一阶段第二阶段第三阶段第四阶段例如

前面最短路径问题可看成四个阶段的问题

k＝1，2，3，4123456798102474363244114633345310BasicConceptsofDP(2)状态(State)

各阶段开始时的自然状况或客观条件。状态变量sk：第k阶段的具体状态。状态集和(状态空间)Sk：各阶段所有状态组成的集合，或状态变量的取值范围。

第一阶段第二阶段第三阶段第四阶段例如S1={1},S2={2,3,4},S3={5,6,7},S4={8,9}123456798102474363244114633345312动态规划中状态的特性可以描述决策过程状态确定后，整个问题的决策过程也就确定了无后效性当某阶段状态给定以后，该阶段以后的过程的发展不受该段以前各段状态的影响13动态规划的基本概念(3)决策(Decision)

当某一阶段状态确定以后，就可做出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量。

uk(sk)：表示第k阶段，当状态为sk时的决策变量。

Dk(sk)：表示第k阶段，在状态sk时，允许决策集合。Dk(sk)={uk(sk)}第一阶段第二阶段第三阶段第四阶段例如D1(1)=?{2,3,4}D3(6)=?{8,9}表示在第1阶段状态1时选择下一状态为2u1(1)=2,表示什么？123456798102474363244114633345315动态规划的基本概念

称pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}为k段子策略(4)策略(Strategy)

对n阶段决策问题，各阶段决策确定后，整个问题的决策序列构成一整体策略，记作：p1,n(s1)={u1(s1),u2(s2),…,un(sn)}第一阶段第二阶段第三阶段第四阶段例如图中红色路径所示即为一整体策略，可表示为p1,4(1)={3,7,9,10}对该策略,从2阶段状态3开始的子策略是什么？p2,4(3)={7,9,10}123456798102474363244114633345317(5)状态转移方程(StateTransformationFunction)

给定了第k段的状态sk

，决策uk(sk)

，则第k+1段的状态sk+1由以下函数确定。

sk+1=Tk(

sk，uk)状态转移方程：第k阶段到第k+1阶段的转移规律动态规划的基本概念第一阶段第二阶段第三阶段第四阶段例如该问题的状态转移方程为：

sk+1=uk(sk)123456798102474363244114633345319(6)指标函数(ReturnFunction)用于衡量所选定策略优劣的数量指标,可以是收益、成本、距离、产量等，一般记作V

。例如，Vk,n(sk,pk,n)表示在第k段，状态为sk，采用策略pk,n时，后部k段子策略的优劣程度。指标函数的最优值称为最优函数，记作fk(sk),它表示从第k阶段的状态sk出发，采用最优策略达到终点的指标函数值。动态规划的基本概念第一阶段第二阶段第三阶段第四阶段例如该问题用距离来度量策略的好坏例如，V2,4(3,{7,9,10})=？f2(3)表示？本问题求从①到⑩的最短路径，其实就是求？12345679810247436324411463334534+3+4=11从阶段2的状态3开始到终点的最短路径值f1(1)21动态规划的求解——以最短路径问题为例5312345679810247436324411463334一个重要性质12345679810如图所示，假设红色路径（①－②－⑥－⑧－⑩）是从①到⑩点的最短路径，则从②到⑩点的最短路径必定是②－⑥－⑧－⑩Bellman最优性原理：

作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的所有决策必须构成最优策略。最优策略的子策略仍然是最优的。第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453采取逆推的方式在第4阶段

f4(8)=3f4(9)=4340第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453在第3阶段

344760第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453在第2阶段

3447611780第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453在第1阶段

344761178110最后，通过顺序追踪，得到3条最优路线1234567981024743632441146333453路线1：1－3－5－8－10路线2：1－4－5－8－10路线3：1－4－6－9－10344761178110

刚才求解的关键是在各个阶段都用到了第k段和第k+1段的如下关系：它由一个递推关系式(recurrencerelation)和边界条件(boundarycondition)组成，称为动态规划的基本方程回顾292.动态规划求解方法

(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而将问题化成一族同类型的子问题(2)求解时从边界条件开始，逆(顺)过程行进方法，逐段递推寻优。每个子问题求解时都要用到前面已求出的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解(3)动态规划的基本方程是递推求解的根据，其一般形式为：30动态规划建模要点分析题意，识别问题的多阶段特性，按时间或空间先后顺序划分满足递推关系的若干阶段，对非时序的静态问题要人为地赋予“时段”概念正确地选择状态变量，使其具备前述的两个必要性质根据状态变量与决策变量的含义，正确写出状态转移方程，或转移规则根据题意明确指标函数Vk,n，最优指标函数fk(sk)以及k阶段指标vk(sk,uk)的含义31逆序递推与顺序递推

上述最短路径问题的递推过程是从最后阶段开始的，是一种逆推(Backward)的方式。事实上，某些问题的递推可以从前往后采用顺推(Forward)的方式求解。这时,状态转移方程是由sk+1,uk去决定sk

sk=Tk’(sk+1,uk)

同时，第k阶段的允许决策集合也要相应改变指标函数也需换成:uk(sk+1)=sk第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453f0(1)=0第1阶段

1112430第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453第2阶段

3,442,3,42437480第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453第3阶段

56243748870第一阶段第二阶段第三阶段第四阶段1234567981024743632441146333453第4阶段

8,987243748110最后，通过逆序追踪，得到3条最优路线1234567981024743632441146333453路线1：1－3－5－8－10路线2：1－4－5－8－10路线3：1－4－6－9－108774824311373.动态规划的应用——资源分配问题

设有某种资源，数量为a,用于生产n种产品，若分配数量xi用于第i种产品，其收益为gi(xi)。如何分配使总收益最大？该问题的静态规划模型为阶段划分假设对各资源分配有先后顺序，即先分给产品1，然后分给产品2…从而把问题人为划成n个阶段状态变量sk：可用于分配给第k至第n阶段(产品)的资源数量决策变量xk：分配给第k阶段(即第k个产品)的资源数量状态转移方程sk＋1＝sk-xk允许决策集合Dk(sk)＝{xk|0≤xk≤sk}指标函数最优值函数fk(sk)：可用资源sk时，分配第k到第n项产品所得最大收益基本方程例1：某部门根据国家计划，拟将某种设备5台分配给甲、乙、丙三个工厂，各工厂获得设备后盈利将如表所示，问如何分配总的盈利最大？设备台数工厂121113512111241111936107245310000丙乙甲盈利sk表示为分配给第k个工厂到第n个工厂的设备台数。xk表示分配给第k个工厂的设备台数。pk(xk)表示将xk台设备分配到第k个工厂所得的盈利值。fk(sk)表示sk台设备分配给第k个工厂至第n个工厂时所得的最大盈利值。递推关系式为：

解：将3个工厂看成3个阶段，甲、乙、丙依次编号为1、2、3。从最后一个阶段开始倒推，先看第3阶段因为只有一个工厂未分配，显然将所有剩余设备全分给它盈利最大s3的状态集合为{0,1,2,3,4,5}计算如表所示512125412x124311xx11326xxx6214xxxx4100xxxxx00543210

s3x3*f3(s3)p3(x3)x3第二阶段把s2(s2=0,1,2,3,4,5)台设备分配给工厂乙和丙时，则对每个s2值,有最优的分配方案，使最大盈利值为：22111+011+411+610+115+120+1251,216x11+011+410+65+110+124214xx11+010+45+60+113210xxx10+05+40+6215xxxx5+00+4100xxxxx0+00543210s2x2*f2(s2)p2(x2)+f3(s2-x2)x2第一阶段把s1(s1=5)台设备分配给工厂甲、乙、丙最大盈利值为：0,22113+012+59+107+143+160+215543210s1x1*f1(5)p1(x1)+f2(5-x1)x144动态规划的应用——生产存储问题例2：某工厂对一种产品制定今后4个时期的生产计划，据估计在今后4个时期，市场对该产品的需求量如表所示。假定该厂每批产品固定成本为3，若不生产就为0，每单位产品成本为1，每个时期生产能力所允许的最大批量不超过6单位，每期末未售出的产品，每单位需支付存储费0.5。假定在第1个时期的初始库存量为0，第4个时期末的库存量也为0。如何安排生产，才能在满足市场需要前提下使总成本最小？4232需求量dk4321时期k阶段划分按4个时期划分为4个阶段，即k=1,2,3,4决策变量第k期的产量xk状态变量第k期开始时的库存量sk指标函数状态转移方程sk+1＝sk＋xk-dk

Vk,n＝vk(sk,xk)+…+vn(sn,xn)

基本方程其中表示库存量为sk，从k阶段至n阶段的最小总费用。第k+1阶段最大可能存储量递推计算：当k=4时，该阶段最大可能存储量是4可能状态当k=3时，该阶段最大可能存储量是6可行状态49当k=2时，该阶段最大可能存储量是4可能状态50当k=1时，有可能状态51寻优k=1s1=0k=2s2=s1+x1-d1=0+5-2=3k=3s3=s2+x2-d2=3+0-3=0k=4s4=s3+x3-d3=0+6-2=4动态规划的应用——一维背包问题52有一个背包最大允许载重量为W，现有n种物品可装入，物品i的重量为wi，价值为ci(i=1,2,…,n)。试问应该如何装包，使得在不超过允许载重的前提下，总价值最大。设xi表示第i种物品的装入数量，其整数规划模型如下。阶段划分按可装入物品的n种类型划分为n个阶段，即k=1,2,…,n决策变量第k种物品的数量(件数)xk状态变量第k阶段还可以装载的重量sk指标函数状态转移方程sk+1＝sk-wkxk

Vk,n＝vk(sk,xk)+…+vn(sn,xn)

基本方程其中表示剩余载重量为sk，从k阶段至n阶段的最大总价值。55例3：某一背包的最大允许载重量为10，有3种物品，其重量分别为3、2、5，价值分别为60、40、60,如何装包,才能使背包总价值最大？递推计算：当k=4时，f4(s4)=0当k=3时，递推方程为56s3D3(s3)

60x3

x3*0,1,2,3,400050016016001601700160180016019001601100016021202当k=2时，递推方程为57s2D2(s2)s340x2+f3(s2-2x2)x2*0000+0=001010+0=00201200+0=040+0=401301310+0=040+0=40140124200+0=040+0=4080+0=80250125310+0=040+0=4080+0=8026012364200+60=6040+0=4080+0=80120+0=12037012375