管理运筹学动态规划课件

第六章第六章 动态规划动态规划第六章 动态规划 第一节：现实中的动态规划问题第一节：现实中的动态规划问题 第二节：动态规划基本概念第二节：动态规划基本概念 第三节：动态规划的基本方法第三节：动态规划的基本方法 第四节：配载问题第四节：配载问题 第五节：生产和库存控制问题第五节：生产和库存控制问题 第六节：资源分配问题第六节：资源分配问题 第七节：动态规划应用第七节：动态规划应用 第一节：现实中的动态规划问题 多式联运多式联运是一种以实现货物整体运输最优化为目标的联合运输组是一种以实现货物整体运输最优化为目标的联合运输组织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装有机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。用、时间和运输质量。第一节：现实中的动态规划问题第一节：现实中的动态规划问题第一节：现实中的动态规划问题第一节：现实中的动态规划问题一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水路运输）路运输）二、集装箱的中转过程有很好的衔接二、集装箱的中转过程有很好的衔接三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种运输方式运输方式四、集装箱运量对运输价格及运输时间没有明显的影响四、集装箱运量对运输价格及运输时间没有明显的影响五、集装箱运输能力几乎不受限制五、集装箱运输能力几乎不受限制六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。通常情况下，多式联运组织优化问题具有如下几个方面的特点：通常情况下，多式联运组织优化问题具有如下几个方面的特点：多式联运是一种以实现货物整体运输最优化为 ZH ZH物流公司是一家大型的集装箱多式联运经营企业，在成都物流公司是一家大型的集装箱多式联运经营企业，在成都设有内陆集装箱货运站（设有内陆集装箱货运站（CFSCFS），经营成都），经营成都上海间集装箱货物运输服上海间集装箱货物运输服务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将将2 2个个2020英尺的集装箱从成都运往上海，运输路线为成都英尺的集装箱从成都运往上海，运输路线为成都-郑州郑州-南京南京-上上海，要求在货物起运后海，要求在货物起运后25-3025-30小时之内到达目的地。小时之内到达目的地。第一节：现实中的动态规划问题第一节：现实中的动态规划问题第一节：现实中的动态规划问题第一节：现实中的动态规划问题成都-郑州郑州-南京南京-上海公路运输1474704349铁路运输1353695303水路运输/392运输方式铁路运输公路运输水路运输运载工具速度(km/h)7010036运输方式铁路运输公路运输水路运输中转时间(h)7318如何制定如何制定运输方式运输方式组合优化组合优化方案使在方案使在满足客户满足客户需求的条需求的条件下降低件下降低集装箱运集装箱运输总成本输总成本？ZH物流公司是一家大型的集装箱多式5 Sk+1S2多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题 阶段、决策、策略阶段、决策、策略动态规划的动态规划的动态规划的动态规划的基本特性（基本特性（基本特性（基本特性（多阶段决策问题的多阶段决策问题的基本特性）基本特性）基本特性）基本特性）第二节第二节 动态规划基本概念动态规划基本概念SkSk+1SnTSnQ =S1反证法反证法反证法反证法容易得证。容易得证。若若 S1,Sk,Sk+1,Sn,T 全程最优全程最优则则 Sk+1,Sn,T 子程最子程最优优5 Sk+1S2多阶段决策问题第二节 动态规划基本概动态规划动态规划方法方法方法方法的的基本思路基本思路基本思路基本思路最短路问题最短路问题1 12 23 34 4340476117811阶段阶段阶段阶段A124374632441514633334A3B1QA2B2B3TC1 C2 标号法标号法标号法标号法动态规划方法的基本思路最短路问题12343404761178三、决策三、决策 是指人们对某一阶段活动中各种不同的是指人们对某一阶段活动中各种不同的行为行为或或方案方案或或途径途径等的等的一种一种选择选择选择选择。用用xk表示第表示第k段的决策，称为第段的决策，称为第k段段决策变量决策变量。由于决策随状态由于决策随状态而变而变,所以决策变量所以决策变量xk是状态变量是状态变量sk的函数的函数,记为记为 xk=xk(sk)动态规划的动态规划的动态规划的动态规划的基本概念基本概念基本概念基本概念一一、阶段阶段 把所研究的问题恰当的划分成若干个相互联系的阶段。用把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，n 表示阶段序号，称为表示阶段序号，称为阶段变量阶段变量。二、状态二、状态 状态表示某段的初始条件。用状态表示某段的初始条件。用sk表示第表示第k段的状态，称为第段的状态，称为第k段段状态变量状态变量。skSkk阶段的允许决策集合阶段的允许决策集合三、决策动态规划的基本概念skSkk阶段的允许决策集合8 四、状态转移方程四、状态转移方程 sk+1与与sk,xk之间必须能够建立一种明确的数量对应关系，记为之间必须能够建立一种明确的数量对应关系，记为Tk(sk,xk),即有即有 sk+1=Tk(sk,xk)这种明确的数量关系称为这种明确的数量关系称为状态转移方程状态转移方程。五、策略五、策略 由各阶段决策由各阶段决策xk构成的决策序列构成的决策序列,称为称为全过程策略全过程策略全过程策略全过程策略,简称简称策略策略,记为记为p1(s1),有有 p1(s1)=x1(s1),x2(s2),xn(sn)pk(sk)=xk(sk),xk+1(sk+1),xn(sn)Pk称为称为第第第第k k子过程策略子过程策略子过程策略子过程策略，简称，简称子策略子策略。P1而而8 四、状态转移方程 五、策略P1而9 六、指标函数六、指标函数 (1)阶段指标函数阶段指标函数 用用vk(sk,xk)表示第表示第k段处于段处于sk状态且所作决策为状态且所作决策为xk时的指标，则它就是时的指标，则它就是第第k k段指标函数段指标函数，简记为，简记为vk。P1 (2)过程指标函数过程指标函数 用用fk(sk,xk)表示表示第第k k子过程的指标函数子过程的指标函数。它是各它是各vk的累积效应。的累积效应。常用函数常用函数常用函数常用函数：fk(sk,xk)=vi(si,xi)n i=kfk(sk,xk)=vi(si,xi)ni=k积函数积函数积函数积函数和函数和函数和函数和函数9 六、指标函数P1 (2)过程指标函数fk(s 七七、最优解最优解 (1)最优指标函数最优指标函数 f fk k*(s sk k)=opt fk(sk,pk(sk),k=1,2,n pk Pk (2)最优策略最优策略 能使上式成立的子策略能使上式成立的子策略p pk k*称为称为最优子策略最优子策略最优子策略最优子策略，记为，记为 p pk k*(s sk k)=xk*(sk),xn*(sn)特别当特别当k=1时时,称为称为最优策略最优策略最优策略最优策略，记为，记为 p p1 1*(s s1 1)=x1*(s1),xk*(sk),xn*(sn)(3)最优决策最优决策 构成最优策略的决策构成最优策略的决策称为称为最优决策最优决策最优决策最优决策，记为，记为x xk k*。(4)最优值最优值：最优策略对应的最优指标最优策略对应的最优指标 f f *1 1 七、最优解11第三节第三节 动态规划的基本方法动态规划的基本方法一一、最优化原理最优化原理 作为一个作为一个全过程最优策略全过程最优策略具有这样的具有这样的性质性质性质性质：无论过去的状态和决策如何，对前面所形成的状态而言，无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略余下的诸决策必构成最优策略余下的诸决策必构成最优策略余下的诸决策必构成最优策略。二、函数基本方程二、函数基本方程 f*n+1(sn+1)=0 f*k(sk)=opt vk(sk,xk)+fk+1*(sk+1)x xk k X Xk k f*n+1(sn+1)=1 f*k(sk)=opt vk(sk,xk)fk+1*(sk+1)x xk k X Xk k和和和和积积积积k=n,n-1,2,1k=n,n-1,2,111第三节 动态规划的基本方法一、最优化原理和积k=n,12第三节第三节 动态规划的基本方法动态规划的基本方法三、基本步骤三、基本步骤1 1建立模型建立模型 (1)划分阶段，设定划分阶段，设定 k k (2)设定状态变量设定状态变量 s sk k (3)设定决策变量设定决策变量 xk k (4)建立建立状态转移方程状态转移方程状态转移方程状态转移方程 (5)确定指标函数确定指标函数 v vk k，fk k*(6)建立建立函数基本方程函数基本方程函数基本方程函数基本方程22递推递推(逆逆逆逆推推)求解求解33得出得出(顺顺顺顺推推)结论结论12第三节 动态规划的基本方法三、基本步骤sabcfedhgt2511214610134121139658105287125220141919k=4=5 k=3=8k=2k=1d1(s)=bd1(s)=bd2(b)=dd3(d)=gd4(g)=t最优策略：最优策略：p1(s1)=s,b,d,g,t最优值：最优值：f*1(s)=19sabcfedhgt2511214610134121139614 阶段N阶段n阶段114 阶段N阶段n阶段115第四节第四节 配载问题配载问题 今有一辆载货量为今有一辆载货量为6t6t的载货车，现有的载货车，现有3 3种需要运输的种需要运输的货物，均可用此载货车装运。若已知这货物，均可用此载货车装运。若已知这3 3种货物每一种的质种货物每一种的质量和运输例如下表所示。在载货量许可的条件下，每车装量和运输例如下表所示。在载货量许可的条件下，每车装载每一种货物的件数不限，应如何搭配这载每一种货物的件数不限，应如何搭配这3 3种货物，才能使种货物，才能使每车装载货物的利润最大？每车装载货物的利润最大？货物种物种类每件每件质量（量（t）每件运每件运输利利润（百元）（百元）12823133418 该问题中的货车可以看做是一个背包，需运载的货物为要该问题中的货车可以看做是一个背包，需运载的货物为要装入背包的物品。装入背包的物品。该问题可以看作是一个该问题可以看作是一个3阶段的动态规划问题。阶段的动态规划问题。15第四节 配载问题 今有一辆载货量为6t的载货步骤步骤1 1，划分阶段。设每装一种货物为一个阶段，划分阶段。设每装一种货物为一个阶段，k k=1,2,3=1,2,3。步骤步骤2 2，确定状态变量。设状态变量为，确定状态变量。设状态变量为 可用于装载第可用于装载第k k种至第种至第n n种货物种货物的装载量。的装载量。1 1）确定决策变量。设决策变量表示第确定决策变量。设决策变量表示第k k种货物的装载件数种货物的装载件数 2 2）状态转移方程为状态转移方程为 3 3）阶段指标函数。第阶段指标函数。第k k阶段装载阶段装载 件货物时所创的利润件货物时所创的利润 。4 4）函数的基本方程为函数的基本方程为步骤1，划分阶段。设每装一种货物为一个阶段，k=1,2,3。k=3时时 阶段 0 1 k=301234560 0 0 0 0 180 180 18000018181800001110123012k=3时 0 k=2时时 阶段 0 1 2 k=201234560+0 0+0 0+0 0+0 13+0 0+18 13+0 0+18 13+0 0+18 13+0 26+00001318182600010020120450k=2时 k=1时时 阶段 0 1 2 3 k=160+26 8+18 16+0 24+0260，16,4=26k=1时 阶段 阶段 0 1 k=301234560 0 0 0 0 180 180 18000018181800001110123012 阶段 0 1 2 k=201234560+0 0+0 0+0 0+0 13+0 0+18 13+0 0+18 13+0 0+18 13+0 26+00001318182600010020120450 阶段 0 1 2 3 k=160+26 8+18 16+0 24+0260，1 6,4 0 121第五节第五节 配载问题配载问题用动态规划解决持续三个月生产的问题。问题的数据见下表每个月当成一个阶段来进行计算求解。还要注意到该问题在实每个月当成一个阶段来进行计算求解。还要注意到该问题在实现优化的每个阶段都必须满足三个约束条件：现优化的每个阶段都必须满足三个约束条件：（1）最终库存量必须小于等于仓库容量；）最终库存量必须小于等于仓库容量；（2）每阶段的生产量不能超过生产能力；）每阶段的生产量不能超过生产能力；（3）初始库存量加上生产量必须大于等于需求量。）初始库存量加上生产量必须大于等于需求量。能力单位成本月需求生产存储生产持有1月232$175$302月323150303月33220040一月的初始库存为1单位21第五节 配载问题用动态规划解决持续三个月生产的问题。问22-第k阶段的需求量；-第k阶段的生产能力；-第k阶段结束时的存储能力；-第k阶段生产单位产品的费用；-第k阶段单位产品的库存持有成本步骤1：划分阶段。把每个月看成一个阶段，倒序命名各个时期。即阶段1对应3月，阶段2对应2月，阶段3对应1月。步骤2：确定状态变量。设 为状态变量，表示第k阶段的开始的库存量。由于1月份初始库存为1单位，故 。另外定义 ，表示为第3阶段末的库存量。步骤3：确定决策变量。设 为决策变量，表示第k阶段的生产量。且必须满足如下三个约束条件：22-第k阶段的需求量；步骤1：划分阶段。把每个月看成23步骤4：状态转移方程。步骤5：指标函数。第k阶段的指标函数 是第k阶段的生产成本（包括生产费用与贮存费用）。步骤6：函数基本方程23步骤4：状态转移方程。步骤5：指标函数。第k阶段的指标函第一阶段：即从3月份开始正向计算。k=1时，问题可以如下表示：0 1 2 3 0 600 3 600 1 400 640 2 400 2 200 440 680 1 200 3 0 240 480 0 0 第一阶段：即从3月份开始正向计算。k=1时，问题可以如下表示第二阶段：k=2时，该阶段的子问题可以表示为：0 1 2 0 M 1 300+600 2 900 2 150+600 330+400 2 730 第二阶段：k=2时，该阶段的子问题可以表示为：第三阶段：k=3时，该阶段的子问题可以表示为：0 1 2 3 1 175+M 380+900 1185+730 2 1280 第三阶段：k=3时，该阶段的子问题可以表示为：0 1 2 3 0 600 3 600 1 400 640 2 400 2 200 440 680 1 200 3 0 240 480 0 0 0 1 2 0 M 1 300+600 2 900 2 150+600 330+400 2 730 0 1 2 3 1 175+M 380+900 1185+730 2 1280 月份 初始库存生产量销售量月末库存生 产成本持有成本总成本一月1221$350$30$380二月12303000300三月03306000600总计$1250$30$1280最优策略 29第六节资源分配问题第六节资源分配问题资源分配问题:是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳动力等），分配给若干用户，而使目标函数最优。设有某一种原料，总量为M，拟用来进行n种生产活动。若分配数量为 的原料用于第i种生产活动，其收益为 ，应该如何分配，才能使n种生产活动的总收益最大？静态规划模型为：29第六节资源分配问题资源分配问题:是指将供应量有限的一种或30用动态规划方法求解此类问题时，一般地，将n种活动作为一个互相衔接的整体，由于要确定分配给每种活动的资源数，因此通常以把资源分配给一个或几个使用者的过程作为一个阶段，每个阶段都要确定分配给一种活动的资源量，并要先对n种活动指定分配的阶段序号。在资源分配中，由于将阶段联系在一起的是所有生产活动都在争取的资源，因此，状态变量就要按照资源的分配来确定。故把第k阶段的状态变量 定义为第k阶段初所拥有的资源量，即将要在第k种活动到第n种活动间分配的资源量。这样，我们在确定第k阶段的资源分配时就无需考虑以前的资源分配情况。决策变量 就定义为对第k种活动的资源投放量，即对第k种活动的资源分配量。30用动态规划方法求解此类问题时，一般地，将n种活动作为一个31某船舶总公司拟将5亿元资金投放到下属A、B、C三个船厂，各船厂在获得资金后的收益如表所示。试用动态规划方法求使总收益最大的投资分配方案。A、B、C三个船厂分别编号为1，2，3，对A、B、C三个船厂分配资金分别形成1,2,3三个阶段，即该问题可作为三阶段决策过程。k=1,2,3。k=1时时，将资金分给1,2,3三个船厂；k=2时时，将资金分给2,3两个船厂；k=3时时，将资金分给3船厂。31某船舶总公司拟将5亿元资金投放到下属A、B、C三个船厂，32K=3时，考虑将资金分给船厂C，k=3012345013791001234532K=3时，考虑将资金分给船厂C，00033k=2时，考虑将资金分给船厂B、C，012345k=201234500+10+30+70+90+104+04+14+34+74+96+06+16+36+78+08+18+39+09+19+004681113012311,233k=2时，考虑将资金分给船厂B、C，012345034k=1时，考虑将资金分给船厂A、B、C 012345k=150+13 3+115+87+68+49+014134k=1时，考虑将资金分给船厂A、B、C 01234535k=1时，也可以 012345k=101234500+40+60+80+110+133+03+43+63+83+115+05+45+65+87+07+47+68+08+49+0047911140011,20,1,2,31若总投资额为3亿元35k=1时，也可以 0123450000若总投资额为336第七节第七节 动态规划应动态规划应用用第一节的集装箱多式联运优化问题进行求解表示所有节点城市的个数表示i城市可选运输方式集合，1-公路、2-铁路、3-水运表示集装箱多式联运中货物运输总量表示i城市到j城市k运输方式的单位距离的运价表示i城市到j城市k运输方式的距离表示i城市到j城市k运输方式的速度表示i城市k运输方式转换为l方式的中转费用表示i城市k运输方式转换为l方式的中转时间36第七节 动态规划应用第一节的集装箱多式联运优化问题进373738约束式（4）是确保运输的连续性。i-1i+1i分成三种情况来讨论均为1，则也为1一个为0，一个1，则必须为0均为0，则也为038约束式（4）是确保运输的连续性。i-1i+1i分成三种情39模型基于动态规划的基本算法程序设计如下：步骤1：令每两个城市之间的运输过程为动态规划中的一个阶段步骤2：选择货物到达城市的运输方式为该阶段的状态变量如：第2阶段的到达方式有公路、铁路，则设计一个3n的状态矩阵，矩阵的第k列表示第k个阶段的状态变量构造的列向量（没有的话，用MATLAB中特有的常量 填充）如：一个3阶段的问题，各阶段的可达状态集合分别为1,1，3，1，2，3，则该问题需输入的状态变量矩阵为步骤3：确定决策变量和状态转移方程。在此例中，令从每一城市出发时所选择的运输方式作为该阶段的决策变量 状态转移方程将状态矩阵作为动态规划程序的一个输入变量。39模型基于动态规划的基本算法程序设计如下：步骤1：令每两个40步骤4：删除不满足时间强约束的可选择方案，这也是与在一般情况下运用动态规划求解问题的区别所在。由于在模型中我们限定了多式联运总时间必须在顾客要求的范围 之内，因此在进行选择最优方案之前应该先排除不满足时间要求的方案。步骤5：由边界条件开始,求出在该阶段状态为的指标函数值，选取其中的最优值作为该阶段状态为时所有允许决策下时的最优值，求出最优决策并进行替换存储。直到最后求出得到问题的指标函数最优值。步骤6：由k=1开始，按照与前一步骤相反的顺序推算，记录推算结果，则可得到每阶段及全局的最优路径及最优解，存储结果并输出。40步骤4：删除不满足时间强约束的可选择方案，这也是与在一般41按照上述算法设计的思路所设计的解法程序主要由以下子程序组成：（1）主函数function p_opt,fval,tw=dyn(x,tm,tn，SubObjFun,TransFun,ObjFun)，输入状态变量矩阵和顾客要求的时间约束，输出的变量为全局最优策略组(p_opt)、最优指标函数值(fval)、完成该运输任务所需要的时间(tw)。（2）阶段指标计算子函数function tmp00=SubObjFun(ii,x,u)，输入阶段数(ii)、状态(x)、决策值(u)，输出的变量为处于该阶段时，某一状态和决策条件下所需的一阶段成本tmp00，供主函数运行时调用。（3）状态转移计算子函数 function tmp40=TransFun(ii,x,u),输入阶段数(ii)、状态(x)、决策值(u)，返回处于该阶段某一状态和决策条件时下一阶段将处的状态值tmp40。（4）第k阶段至最后阶段指标函数子函数 function tmp80=ObjFun(tmp00,f_opt),输入阶段指标值(tmp00)和后一阶段至最后阶段指标值(f_opt)，输出值为该阶段至最后阶段指标值。41按照上述算法设计的思路所设计的解法程序主要由以下子程序组42集装箱多式联运各种运输方式的成本情况表成都-郑州郑州-南京南京-上海公路运输8.178.789.98铁路运输3.323.795.05水路运输/1.94成本(美元/km.TEU)42集装箱多式联运各种运输方式的成本情况表公路运输8.17843 将上述参数输入到优化算法程序中，得到最优的运输方式组合策略为：成都（公路）郑州（公路）南京（铁路）上海。此时的最小运输成本为39631美元,完成运输任务所需要的时间为29.11小时。如果对运输时间的要求放宽至起运后40-50小时之内到达即可，此时再次对该问题求解，得到的最优策略组合变为：成都（铁路）郑州（铁路）南京（水路）上海。此时的最小运输成本为15826美元,完成运输任务所需要的时间为46.96小时。43 将上述参数输入到优化算法程序中，得到最优的运输方