《管理运筹学》06-动态规划.ppt

第六章 动态规划,第一节：现实中的动态规划问题 第二节：动态规划基本概念 第三节：动态规划的基本方法 第四节：配载问题 第五节：生产和库存控制问题 第六节：资源分配问题 第七节：动态规划应用,多式联运是一种以实现货物整体运输最优化为目标的联合运输组织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。,第一节：现实中的动态规划问题,一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水路运输）二、集装箱的中转过程有很好的衔接三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种运输方式四、集装箱运量对运输价格及运输时间没有明显的影响五、集装箱运输能力几乎不受限制六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。,通常情况下，多式联运组织优化问题具有如下几个方面的特点：,ZH物流公司是一家大型的集装箱多式联运经营企业，在成都设有内陆集装箱货运站（CFS），经营成都上海间集装箱货物运输服务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将2个20英尺的集装箱从成都运往上海，运输路线为成都-郑州-南京-上海，要求在货物起运后25-30小时之内到达目的地。,第一节：现实中的动态规划问题,如何制定运输方式组合优化方案使在满足客户需求的条件下降低集装箱运输总成本？,5,Sk+1,S2,多阶段决策问题 阶段、决策、策略动态规划的基本特性（多阶段决策问题的基本特性）,第二节 动态规划基本概念,Sk,Sk+1,Sn,T,Sn,Q=S1,反证法容易得证。,若 S1,Sk,Sk+1,Sn,T 全程最优,则 Sk+1,Sn,T 子程最优,动态规划方法的基本思路,最短路问题,1,2,3,4,3,4,0,4,7,6,11,7,8,11,阶段,标号法,三、决策 是指人们对某一阶段活动中各种不同的行为或方案或途径等的一种选择。用xk表示第k段的决策，称为第k段决策变量。由于决策随状态而变,所以决策变量xk是状态变量sk的函数,记为 xk=xk(sk),动态规划的基本概念一、阶段 把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，n 表示阶段序号，称为阶段变量。二、状态 状态表示某段的初始条件。用sk表示第k段的状态，称为第k段状态变量。,skSk,k阶段的允许决策集合,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子过程策略，简称子策略。,P1,而,9,六、指标函数(1)阶段指标函数 用vk(sk,xk)表示第k段处于sk状态且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。,P1,(2)过程指标函数 用fk(sk,xk)表示第k子过程的指标函数。它是各vk的累积效应。常用函数：,积函数,和函数,七、最优解(1)最优指标函数 fk*(sk)=opt fk(sk,pk(sk),k=1,2,n pkPk(2)最优策略 能使上式成立的子策略pk*称为最优子策略，记为 pk*(sk)=xk*(sk),xn*(sn)特别当k=1时,称为最优策略，记为 p1*(s1)=x1*(s1),xk*(sk),xn*(sn)(3)最优决策 构成最优策略的决策称为最优决策，记为xk*。(4)最优值：最优策略对应的最优指标 f*1,11,第三节 动态规划的基本方法,一、最优化原理 作为一个全过程最优策略具有这样的性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。二、函数基本方程 f*n+1(sn+1)=0 f*k(sk)=opt vk(sk,xk)+fk+1*(sk+1)xkXk f*n+1(sn+1)=1 f*k(sk)=opt vk(sk,xk)fk+1*(sk+1)xkXk,和,积,k=n,n-1,2,1,k=n,n-1,2,1,12,第三节 动态规划的基本方法,三、基本步骤1建立模型(1)划分阶段，设定 k(2)设定状态变量 sk(3)设定决策变量 xk(4)建立状态转移方程(5)确定指标函数 vk，fk*(6)建立函数基本方程2递推(逆推)求解3得出(顺推)结论,s,a,b,c,f,e,d,h,g,t,2,5,1,12,14,6,10,13,4,12,11,3,9,6,5,8,10,5,2,8,7,12,5,2,20,14,19,19,k=4,=5,k=3,=8,k=2,k=1,d1(s)=b,d1(s)=b,d2(b)=d,d3(d)=g,d4(g)=t,最优策略：p1(s1)=s,b,d,g,t,最优值：f*1(s)=19,14,15,第四节 配载问题,今有一辆载货量为6t的载货车，现有3种需要运输的货物，均可用此载货车装运。若已知这3种货物每一种的质量和运输例如下表所示。在载货量许可的条件下，每车装载每一种货物的件数不限，应如何搭配这3种货物，才能使每车装载货物的利润最大？,该问题中的货车可以看做是一个背包，需运载的货物为要装入背包的物品。该问题可以看作是一个3阶段的动态规划问题。,步骤1，划分阶段。设每装一种货物为一个阶段，k=1,2,3。步骤2，确定状态变量。设状态变量为 可用于装载第k种至第n种货物的装载量。,1）确定决策变量。设决策变量表示第k种货物的装载件数 2）状态转移方程为 3）阶段指标函数。第k阶段装载 件货物时所创的利润。4）函数的基本方程为,k=3时,k=2时,k=1时,=26,21,第五节 配载问题,用动态规划解决持续三个月生产的问题。问题的数据见下表,每个月当成一个阶段来进行计算求解。还要注意到该问题在实现优化的每个阶段都必须满足三个约束条件：（1）最终库存量必须小于等于仓库容量；（2）每阶段的生产量不能超过生产能力；（3）初始库存量加上生产量必须大于等于需求量。,22,-第k阶段的需求量；-第k阶段的生产能力；-第k阶段结束时的存储能力；-第k阶段生产单位产品的费用；-第k阶段单位产品的库存持有成本,步骤1：划分阶段。把每个月看成一个阶段，倒序命名各个时期。即阶段1对应3月，阶段2对应2月，阶段3对应1月。,步骤2：确定状态变量。设 为状态变量，表示第k阶段的开始的库存量。由于1月份初始库存为1单位，故。另外定义，表示为第3阶段末的库存量。,步骤3：确定决策变量。设 为决策变量，表示第k阶段的生产量。且必须满足如下三个约束条件：,23,步骤4：状态转移方程。,步骤5：指标函数。第k阶段的指标函数 是第k阶段的生产成本（包括生产费用与贮存费用）。,步骤6：函数基本方程,第一阶段：即从3月份开始正向计算。k=1时，问题可以如下表示：,第二阶段：k=2时，该阶段的子问题可以表示为：,第三阶段：k=3时，该阶段的子问题可以表示为：,最优策略,29,第六节资源分配问题,资源分配问题:是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳动力等），分配给若干用户，而使目标函数最优。设有某一种原料，总量为M，拟用来进行n种生产活动。若分配数量为 的原料用于第i种生产活动，其收益为，应该如何分配，才能使n种生产活动的总收益最大？静态规划模型为：,30,用动态规划方法求解此类问题时，一般地，将n种活动作为一个互相衔接的整体，由于要确定分配给每种活动的资源数，因此通常以把资源分配给一个或几个使用者的过程作为一个阶段，每个阶段都要确定分配给一种活动的资源量，并要先对n种活动指定分配的阶段序号。在资源分配中，由于将阶段联系在一起的是所有生产活动都在争取的资源，因此，状态变量就要按照资源的分配来确定。故把第k阶段的状态变量 定义为第k阶段初所拥有的资源量，即将要在第k种活动到第n种活动间分配的资源量。这样，我们在确定第k阶段的资源分配时就无需考虑以前的资源分配情况。决策变量 就定义为对第k种活动的资源投放量，即对第k种活动的资源分配量。,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船厂。,32,K=3时，考虑将资金分给船厂C，,33,k=2时，考虑将资金分给船厂B、C，,34,k=1时，考虑将资金分给船厂A、B、C,35,k=1时，也可以,若总投资额为3亿元,36,第七节 动态规划应用,第一节的集装箱多式联运优化问题进行求解,表示所有节点城市的个数,表示i城市可选运输方式集合，1-公路、2-铁路、3-水运,表示集装箱多式联运中货物运输总量,表示i城市到j城市k运输方式的单位距离的运价,表示i城市到j城市k运输方式的距离,表示i城市到j城市k运输方式的速度,表示i城市k运输方式转换为l方式的中转费用,表示i城市k运输方式转换为l方式的中转时间,37,38,约束式（4）是确保运输的连续性。,i-1,i+1,i,分成三种情况来讨论,均为1，则,也为1,一个为0，一个1，则,必须为0,均为0，则,也为0,39,模型基于动态规划的基本算法程序设计如下：,步骤1：令每两个城市之间的运输过程为动态规划中的一个阶段,步骤2：选择货物到达城市的运输方式为该阶段的状态变量,如：第2阶段的到达方式有公路、铁路，则,设计一个3n的状态矩阵，矩阵的第k列表示第k个阶段的状态变量构造的列向量（没有的话，用MATLAB中特有的常量 填充）,如：一个3阶段的问题，各阶段的可达状态集合分别为1,1，3，1，2，3，则该问题需输入的状态变量矩阵为,步骤3：确定决策变量和状态转移方程。在此例中，令从每一城市出发时所选择的运输方式作为该阶段的决策变量 状态转移方程,将状态矩阵作为动态规划程序的一个输入变量。,40,步骤4：删除不满足时间强约束的可选择方案，这也是与在一般情况下运用动态规划求解问题的区别所在。由于在模型中我们限定了多式联运总时间必须在顾客要求的范围 之内，因此在进行选择最优方案之前应该先排除不满足时间要求的方案。,步骤5：由边界条件,开始,求出在该阶段状态为,的指标函数值，选取其中的最优值作为该阶段状态为,时所有允许决策下,时的最优值，,求出最优决策,并进行替换存储。,直到最后求出,得到问题的指标函数最优值。,步骤6：由k=1开始，按照与前一步骤相反的顺序推算，记录推算结果，则可得到每阶段及全局的最优路径及最优解，存储结果并输出。,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)，输出值为该阶段至最后阶段指标值。,42,集装箱多式联运各种运输方式的成本情况表,成本(美元/km.TEU),43,将上述参数输入到优化算法程序中，得到最优的运输方式组合策略为：成都（公路）郑州（公路）南京（铁路）上海。此时的最小运输成本为39631美元,完成运输任务所需要的时间为29.11小时。如果对运输时间的要求放宽至起运后40-50小时之内到达即可，此时再次对该问题求解，得到的最优策略组合变为：成都（铁路）郑州（铁路）南京（水路）上海。此时的最小运输成本为15826美元,完成运输任务所需要的时间为46.96小时。,