第三讲动态规划高级运筹学课件

第三讲动态规划高级运筹学课件1第1页，共52页，2023年，2月20日，星期一§4.1动态规划的基本概念和最优化原理一、引例（最短路问题）

假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。AB1B2B3C1C2C3D1D2E243746324265346333342第2页，共52页，2023年，2月20日，星期一

将该问题划分为4个阶段的决策问题，即第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：A→B1→C2→D3→E

其长度为12。显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：3第3页，共52页，2023年，2月20日，星期一第四阶段，由D1到E只有一条路线，其长度f4（D1）=3，同理f4（D2）=4。第三阶段，由Cj到Di分别均有两种选择，即，决策点为D1,决策点为D1，决策点为D24第4页，共52页，2023年，2月20日，星期一第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2

决策点为C1或C2决策点为C2

5第5页，共52页，2023年，2月20日，星期一第一阶段，由A到B，有三种选择，即：决策点为B3f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即A→B3→C2→D2→E

上述最短路线问题的计算过程，也可借助于图形直观的表示出来：6第6页，共52页，2023年，2月20日，星期一

图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。从引例的求解过程可以得到以下启示：

①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。

AB1B2B3C1C2C3D1D2E24374632426534633334346769911127第7页，共52页，2023年，2月20日，星期一

所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：

②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。④决策过程是与阶段发展过程逆向而行。8第8页，共52页，2023年，2月20日，星期一

二、多阶段决策问题的典型例子：企业在生产过程中，由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划。某种机器，可以在高、低两种负荷下生产。高负荷下生产的产量多，但每生产一个阶段后机器的完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产，问应该如何决定各阶段中机器的使用，使整个计划期内的总产量最大。某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。9第9页，共52页，2023年，2月20日，星期一三、动态规划方法的特点

优点：①许多问题用动态规划研究求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学无用武之地，而动态规划成为得力工具；②某些情况下，用动态规划处理不仅能作定性描述分析，且可利用计算机给出求其数值解的方法。

缺点：①没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要的引导作用。②“维数障碍”：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。10第10页，共52页，2023年，2月20日，星期一§4.2动态规划的基本概念一、动态规划的基本要素

1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k表示。如引例可划分为4个阶段求解，k=1，2，3，4。

2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。（1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用Sk表示第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。如引例中11第11页，共52页，2023年，2月20日，星期一

（2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。常用dk(Sk)表示第k阶段处于状态Sk时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用Dk(Sk)表示。显然dk（Sk）∈Dk(Sk)。如在引例的第二阶段中，若从B1出发，D2（B1）={B1C1,B1C2,B1C3}如果决定选取B1C2，则d2（B1）=B1C2。12第12页，共52页，2023年，2月20日，星期一称可供选择策略的范围，为允许策略集，用P表示。动态规划方法就是要从允许策略集P中找出最优策略P1n*。

4、策略与子策略。策略是一个决策序列的集合。当k=1时，P1n（S1）={d1(s1),d2(s2),…,dn(sn)}就称为全过程的一个策略，简称策略，简记为P1n(S1).

称Pk,n(Sk)={dk(sk),dk+1(sk+1),…,dn(sn)}为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为Pk,n(Sk)5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用Sk+1=Tk(Sk,dk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。13第13页，共52页，2023年，2月20日，星期一6、阶段指标、指标函数和最优指标函数（1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用vk(Sk,dk)表示第k阶段的阶段指标。在不同的问题中，其含义不同。它可以是距离、利润、成本等。在引例中，用dk=vk(Sk,dk)表示在第k阶段由点Sk到点Sk+1=dk(Sk)距离。如d2(B3,C1)=6。14第14页，共52页，2023年，2月20日，星期一（2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为Vk,n(Sk,Pk,n).Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1)k=1,2,…,n。构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。常见的指标函数的形式有：①

②15第15页，共52页，2023年，2月20日，星期一（3）最优指标函数fk(Sk),表示从第k阶段的状态Sk开始采用最优子策略P*k,n，到第n阶段终止时所得到的指标函数值。即fk(Sk)=OptVk,n(Sk,dk,…Sn+1)

其中Opt是最优化（Optimum）的缩写，可根据题意取max或min。在引例中，指标函数Vk,n表示在第k阶段由点Sk至终点E的距离。fk(sk)表示第k阶段点Sk到终点E的最短距离。f2(B1)=11表示从第2阶段中的点B1到点E的最短距离。

16第16页，共52页，2023年，2月20日，星期一7、基本方程（递推关系式）从引例求A到E的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系一般地，若则有若17第17页，共52页，2023年，2月20日，星期一

1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化性。二、动态规划的基本思想与最优化原理18第18页，共52页，2023年，2月20日，星期一

2、最优化原理动态规划方法基于R·Bellman等人提出的最优化原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策略的子策略总是最优的”。但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性的充要条件。由此可见，基本方程是动态规划理论与方法的基础。§4.3动态规划模型的建立与求解一、构成动态规划模型的条件19第19页，共52页，2023年，2月20日，星期一

应用动态规划解决问题时必须首先建立动态规划模型，再用逆序或顺序算法求解。写一个问题的动态规划模型一般包含以下6个步骤：（1）阶段划分k=1,2,…,n

（2）确定状态变量sk

（3）确定决策变量dk

（4）确定状态转移方程sk+1=f(sk,dk)或sk-1=f(sk,dk)

（5）确定阶段指标V(sk,dk)

（6）确定基本递推方程或20第20页，共52页，2023年，2月20日，星期一二、求解动态规划模型的方法1、在已知初始状态S1下，采用逆序解法：（反向递归）

按上图示意的求解方法称为逆序法。例如引例的求解，就是把A看作始端，E为终端，规定从A到E为过程的行进方向，而寻优则是从E到A逆过程进行，所以是采用了逆序法。阶段1s1d1(s1)v1(s1,d1)阶段2s2d2(s2)v2(s2,d2)…阶段kskdk(sk)vk(sk,dk)阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段nsndn(sn)vn(sn,dn)…vk,nfk(sk)=optVk,n寻优方向21第21页，共52页，2023年，2月20日，星期一2、在已知终止状态Sn下，采用顺序解法（正向递归）

如果我们把引例中E看作始端，A为终端，规定从E到A过程为行进方向，而寻优则是从A到E过程进行求解的方法称为顺序法。其示意图如下：

逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。…阶段1s0d1(s1)v1(s1,d1)阶段2s1d2(s2)v2(s2,d2)阶段kdk(sk)vk(sk,dk)阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段ndn(sn)vn(sn,dn)…vk,nfk(sk)=optV1,k寻优方向sksn22第22页，共52页，2023年，2月20日，星期一3、两种解法在建模时的区别如下表所示23第23页，共52页，2023年，2月20日，星期一案例1

某商店在未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为1000件，每月中旬订购商品，并于下月初取到订货。据估计，今后四个月这种商品的购价和售价如下表所示。假定商店在1月初开始经销时仓库已存有该种商品500件，每月市场需求不限，问应如何计划每个月的订购与销售量，使这四个月的总利润最大（不考虑仓库的存储费用）？月份k购价pk售价qk110122993111341517解：首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初的库存量，且s1=50024第24页，共52页，2023年，2月20日，星期一（3）决策变量xk表示第k月的订货量，yk表示第k月的销售量；（4）状态转移方程sk+1=sk+xk-yk,（5）指标函数表示第k月的利润V(sk,xk,yk)=qkyk-pkxk（6）基本方程为其逆序计算过程见课本P10425第25页，共52页，2023年，2月20日，星期一解：当K=4时，根据基本递推方程显然，y4*=s4,x4*=0为最优决策，这时，f4(s4)=17s4当K=3时，这是一个线性规划问题，解得最优解为y3*=s3,x3*=H，f3(s3)=13s3+6H26第26页，共52页，2023年，2月20日，星期一当K=2时，得最优解为y2*=s2,x2*=H，f2(s2)=9s2+10H当K=1时，得最优解为y1*=s1,x1*=0，f1(s1)=12s1+10H将s1=500,H=1000代入上式，并按计算顺序反推，得：x1*=0，y1*=s1=500x2*=H=1000，y2*=s2=s1+x1*-y1*=0x3*=H=1000，y2*=s3=s2+x2*-y2*=1000x4*=0，y4*=s4=s3+x3*-y3*=100027第27页，共52页，2023年，2月20日，星期一案例2

P118练习4.4

某工厂有100台机器，拟分四期使用，在每一期都有两种生产任务。据经验，若把x1台机器投入第一种生产任务，则在本期结束时将有1/3x1台机器损坏报废，剩下的机器全部投入第二种生产任务，则有1/10的机器在期未损坏报废。如果干第一种生产任务时每台机器可获得利润10，干第二种生产任务时每台机器可获利润7，问应怎样分配使用机器以使四期的总利润最大（期未剩下的完好机器数量不限）？解：1、首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初可用于分配的机器数，且s1=100（3）决策变量xk表示第k阶段分配于干第一种任务的机器数，则干第二种任务的机器数为sk-xk28第28页，共52页，2023年，2月20日，星期一（4）状态转移方程sk+1=2/3xk+9/10（sk-xk）=9/10sk-7/30xk,（5）阶段指标表示第k期的利润V(sk,xk)=10xk+7（sk-xk）=3xk+7sk（6）基本方程为：2、用逆序算法求解（见习题集P104）当K=4时，根据基本递推方程最优解为x4*=s4,f4(s4)=10s429第29页，共52页，2023年，2月20日，星期一当K=3时，最优解为x3*=s3,f3(s3)=50s3/3当K=2时，最优解为x2*=0,f2(s2)=22s230第30页，共52页，2023年，2月20日，星期一P106案例3

某厂在未来3个月连续生产某种产品。每月初开始生产，月产量为x，生产成本为x2，库存费为每月每单位1元。假如3个月的需求量预测为：b1=100,b2=110,b3=120，且初始存货s0=0，第三个月的期未存货s3=0，问应如何安排生产使总成本最小？当K=1时，最优解为x1*=0,f1(s1)=134s1/5=2680逆顺序回推，得x1*=0，s1=100x2*=0，s2=9s1/10-7x1*/30=90x3*=s3=81，s3=9s2/10-7x2*/30=81x4*=s4=54，s4=9s3/10-7x3*/30=5431第31页，共52页，2023年，2月20日，星期一解法1：建立用逆序算法求解的动态规划模型（1）阶段：K=1，2，3（2）状态变量：SK表示第K月初的库存，且已知S1=0，S4=0（3）决策变量：XK表示第K月的生产量（4）状态转移方程：Sk+1=Sk+Xk-bk，表示第K+1月初的库存等于第K月的库存加上该月的生产量再减去该月的需求量。（5）指标函数：Vk(Sk,Xk)=Xk2+Sk，表示第K月的总费用（生产成本加上库存费）（6）基本递推方程：可用逆序得法进行求解。32第32页，共52页，2023年，2月20日，星期一解法2：建立用顺序算法求解的动态规划模型（1）阶段：K=1，2，3（2）状态变量：SK表示第K月末的库存，且已知S0=0，S3=0（3）决策变量：XK表示第K月的生产量（4）状态转移方程：Sk-1=Sk-Xk+bk，表示第K-1月初的库存等于第K月的库存减去该月的生产量再加上该月的需求量。（5）指标函数：Vk(Sk,Xk)=Xk2+Sk，表示第K月的总费用（生产成本加上库存费）（6）基本递推方程：可用顺序得法进行求解，详细求解过程见课本P106。33第33页，共52页，2023年，2月20日，星期一当K=1时当K=2时利用微分求极值的方法,得34第34页，共52页，2023年，2月20日，星期一当K=3时利用微分求极值的方法,得按计算顺序反推,得最优解为:35第35页，共52页，2023年，2月20日，星期一案例3（生产存贮问题）某工厂与购货单位签订的供货合同如下表。该厂每月最大产量为4百件，仓库的存货能力为3百件。已知每一百件货物的生产费为一万元。在生产的月份，每批产品的生产准备费为4千元，仓库保管费为每一百件货物每月一千元。假定1月初开始时及6月底交货后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？月份123456交货量（百件）125321解：1、建立动态规划模型（1）阶段划分：k=1，2，3，4，5，6（2）状态变量sk表示第k月初的库存量，s1=0（3）决策变量dk表示第k月的计划生产量表示第月的合同交货量36第36页，共52页，2023年，2月20日，星期一（4）状态转移方程：（5）第k月的总费用包括生产费和库存费（6）基本递推方程2、用逆序算法求解当k=6时，s6+d6-1=s7=0,所以s6+d6=1f6(s6)=min{v6(s6,d6)}

当s6=0,d6=1,f6(s6)=14

当s6=1,d6=0,f6(s6)=137第37页，共52页，2023年，2月20日，星期一当k=5时，s5+d5-2=s6,所以请对照课本P108表4.6结果。38第38页，共52页，2023年，2月20日，星期一当k=4时，s4+d4-3=s5,所以39第39页，共52页，2023年，2月20日，星期一求解结果对照课本P108表4.7结果。余下求解结果参看课本P108，所求最优决策结果如下表：月初存货量

sk最优生产量

dk月底存货量

sk+104130214503303210140第40页，共52页，2023年，2月20日，星期一案例4

（背包问题）某工厂生产三种产品，各种产品重量与利润的关系下表所示。现将此三种产品运往市场出售，运输能力总重量不超过6吨，问如何安排使运输总利润最大？种类重量（吨/件）利润（元/件）12802418033130解：其实本例是一个整数规划问题，其整数规划模型如下但是由于整数规划的求解需用分枝定界法求解，计算量非常大，因而在此我们选用动态规划方法来解。41第41页，共52页，2023年，2月20日，星期一1、建立动态规划模型（在此用的是逆序算法求解，与课本不同）（1）阶段划分：k=1,2,3，把装载一种产品看成一个阶段（2）状态变量sk表示第k阶段初可用于装载产品的总容量量，s1=6（3）决策变量dk表示第k阶段装载第k种货物的件数。（4）状态转移方程：其中ak表示第k种货物的单件重量（6）基本递推方程（5）指标函数：vk(sk,dk)表示装载第k种货物dk件所得的利润，即v1(s1,d1)=80d1,v2(s2,d2)=180d2,v3(s3,d3)=130d342第42页，共52页，2023年，2月20日，星期一2、用逆序法求解。其结果如下表s3d3f3(s3)d3*000*01000200030101301401013015010130160120130260*243第43页，共52页，2023年，2月20日，星期一其计算结果如下表s2d2s3f3(s3)f2(s2)d2*00000010100020200030313013014014013000+130180+0*1501511301800+130180+01601622601800+260*180+0044第44页，共52页，2023年，2月20日，星期一其计算结果如下表s1d1s2f2(s2)f1(s1)d1*601236420260180000+260*80+180*160+0240+001按计算次序反推，得到最优解有两个：（1）x1=0,x2=0,x3=2；（2）x1=1,x2=1,x3=0；45第45页，共52页，2023年，2月20日，星期一案例5（一维资源分配问题）某公司拟将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配到的投资额有关。各工厂在获得不同的投资额时所能增加的利润如下表。问应如何分配这些资金，使公司总的利润增长额最大？

投资工厂0102030102.541020358.530269解：这是一个静态问题，通过将对三个工厂的投资看成三个阶段化为一个多阶段的动态问题。1、建立动态规划模型（1）阶段划分：k=1,2,3，把对每个工厂的投资看成一个阶段（2）状态变量sk表示第k阶段初可用于投资的投资总额，s1=346第46页，共52页，2023年，2月20日，星期一（3）决策变量dk表示第k阶段对第k个工厂的投资额。（4）状态转移方程：（5）阶段指标vk(sk,dk)表示对k第个工厂投资dk后所增加的利润，其值为表中数据。（6）基本递推方程2、用逆序算法求解。