管理运筹学动态规划课件.ppt

1、 第一节：现实中的动态规划问题第一节：现实中的动态规划问题 第二节：动态规划基本概念第二节：动态规划基本概念 第三节：动态规划的基本方法第三节：动态规划的基本方法 第四节：配载问题第四节：配载问题 第五节：生产和库存控制问题第五节：生产和库存控制问题 第六节：资源分配问题第六节：资源分配问题 第七节：动态规划应用第七节：动态规划应用 多式联运多式联运是一种以实现货物整体运输最优化为目标的联合运输组织是一种以实现货物整体运输最优化为目标的联合运输组织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有机地结合起来，构筑连续的

2、、综合性的一体化货物运输网络。在集装箱机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。、时间和运输质量。一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水路运输）路运输）二、集装箱的中转过程有很好的衔接二、集装箱的中转过程有很好的衔接三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种运输方式运输

3、方式四、集装箱运量对运输价格及运输时间没有明显的影响四、集装箱运量对运输价格及运输时间没有明显的影响五、集装箱运输能力几乎不受限制五、集装箱运输能力几乎不受限制六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。通常情况下，多式联运组织优化问题具有如下几个方面的特点：通常情况下，多式联运组织优化问题具有如下几个方面的特点：ZH ZH物流公司是一家大型的集装箱多式联运经营企业，在成都设有物流公司是一家大型的集装箱多式联运经营企业，在成都设有内陆集装箱货运站（内陆集装箱货运站（CFSCFS），经营成都），经营成都上海间集装箱货物运输服

4、务上海间集装箱货物运输服务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将2 2个个2020英尺的集装箱从成都运往上海，运输路线为成都英尺的集装箱从成都运往上海，运输路线为成都-郑州郑州-南京南京-上海，上海，要求在货物起运后要求在货物起运后25-3025-30小时之内到达目的地。小时之内到达目的地。成都-郑州郑州-南京南京-上海公路运输1474704349铁路运输1353695303水路运输/392运输方式铁路运输公路运输水路运输运载工具速度(km/h)7010036运输方式铁路运输公路运输水路运输中转时间(h)73

5、18如何制定如何制定运输方式运输方式组合优化组合优化方案使在方案使在满足客户满足客户需求的条需求的条件下降低件下降低集装箱运集装箱运输总成本？输总成本？5 Sk+1S2 阶段、决策、策略阶段、决策、策略多阶段决策问题的多阶段决策问题的SkSk+1SnTSnQ =S1容易得证。容易得证。若若 S1,Sk,Sk+1,Sn,T 全程最优全程最优则则 Sk+1,Sn,T 子程最优子程最优动态规划动态规划的的最短路问题最短路问题340476117811A124374632441514633334A3B1QA2B2B3TC1 C2 三、决策三、决策 是指人们对某一阶段活动中各种不同的是指人们对某一阶段活动

6、中各种不同的行为行为或或方案方案或或途径途径等的等的一种一种。用用xk表示第表示第k段的决策，称为第段的决策，称为第k段段决策变量决策变量。由于决策随状态由于决策随状态而变而变,所以决策变量所以决策变量xk是状态变量是状态变量sk的函数的函数,记为记为 xk=xk(sk)一一、阶段阶段 把所研究的问题恰当的划分成若干个相互联系的阶段。用把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，n 表示阶段序号，称为表示阶段序号，称为阶段变量阶段变量。二、状态二、状态 状态表示某段的初始条件。用状态表示某段的初始条件。用sk表示第表示第k段的状态，称为第段的状态，称为第k段段状态变量状态变量

7、。skSkkkkkxsDsk阶段的允许决策集合阶段的允许决策集合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称为称为

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 七七、最优解最优解 (1)最优指标函数最优指标函数 =opt fk(sk,pk

9、(sk),k=1,2,n pkPk (2)最优策略最优策略 能使上式成立的子策略能使上式成立的子策略称为称为，记为，记为 =xk*(sk),xn*(sn)特别当特别当k=1时时,称为称为，记为，记为 =x1*(s1),xk*(sk),xn*(sn)(3)最优决策最优决策 构成最优策略的决策构成最优策略的决策称为称为，记为，记为。(4)最优值最优值：最优策略对应的最优指标最优策略对应的最优指标 11一一、最优化原理最优化原理 作为一个作为一个全过程最优策略全过程最优策略具有这样的具有这样的：无论过去的状态和决策如何，对前面所形成的状态而言，无论过去的状态和决策如何，对前面所形成的状态而言，二、函

10、数基本方程二、函数基本方程 f*n+1(sn+1)=0 f*k(sk)=opt vk(sk,xk)+fk+1*(sk+1)f*n+1(sn+1)=1 f*k(sk)=opt vk(sk,xk)fk+1*(sk+1)k=n,n-1,2,1k=n,n-1,2,112三、基本步骤三、基本步骤1 1建立模型建立模型 (1)划分阶段，设定划分阶段，设定 k k (2)设定状态变量设定状态变量 s sk k (3)设定决策变量设定决策变量 xk k (4)建立建立 (5)确定指标函数确定指标函数 v vk k，fk k*(6)建立建立2 2递推递推(推推)求解求解3 3得出得出(推推)结论结论sabcfe

11、dhgt2511214610134121139658105287125220141919k=4 4fg 4dgt=5 k=3 34334,35minmin92,dd gfgfddd hfh=8 3ddgk=2k=1d1(s)=bd1(s)=bd2(b)=dd3(d)=gd4(g)=t最优策略：最优策略：p1(s1)=s,b,d,g,t最优值：最优值：f*1(s)=1914Ndnd1dNs1Nsns1ns1s0s 阶段N阶段n阶段115 今有一辆载货量为今有一辆载货量为6t 6t的载货车，现有的载货车，现有3 3种需要运输的货种需要运输的货物，均可用此载货车装运。若已知这物，均可用此载货车装运。

12、若已知这3 3种货物每一种的质种货物每一种的质量和运输例如下表所示。在载货量许可的条件下，每车装量和运输例如下表所示。在载货量许可的条件下，每车装载每一种货物的件数不限，应如何搭配这载每一种货物的件数不限，应如何搭配这3 3种货物，才能种货物，才能使每车装载货物的利润最大？使每车装载货物的利润最大？货物种类货物种类每件每件质量（质量（t）每件运输每件运输利润（利润（百元）百元）12823133418 该问题中的货车可以看做是一个背包，需运载的货物为要该问题中的货车可以看做是一个背包，需运载的货物为要装入背包的物品。装入背包的物品。该问题可以看作是一个该问题可以看作是一个3阶段的动态规划问题。阶

13、段的动态规划问题。步骤步骤1 1，划分阶段。设每装一种货物为一个阶段，划分阶段。设每装一种货物为一个阶段，k k=1,2,3=1,2,3。步骤步骤2 2，确定状态变量。设状态变量为，确定状态变量。设状态变量为 可用于装载第可用于装载第k k种至第种至第n n种货物种货物的装载量。的装载量。160,1,2,3,4,5,62,3kssk1 1）确定决策变量。设决策变量表示第确定决策变量。设决策变量表示第k k种货物的装载件数种货物的装载件数 2 2）状态转移方程为状态转移方程为 3 3）阶段指标函数。第阶段指标函数。第k k阶段装载阶段装载 件货物时所创的利润件货物时所创的利润 。4 4）函数的基

14、本方程为函数的基本方程为0,1,1,2,3kkkkksxDxkw1kkkkssw xkkv x 10,1,6441,2,30kkkkkkkkkkkkxDssfsoptv xfsw xkfs33333333330,10,1,64,1 80,1,60,1,0,14m a x1 8xswvssxfsxk=3时时 阶段 0 1 k=301234560 0 0 0 0 180 180 180000181818000011101230123x3s318x3f3x4sk=2时时33222222223220,1,20,1,63,130,1,60,1,0,1,23max133xswvssxfsxfsx 阶段 0

15、 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+000013181826000100201204502x2s2322133xfsx2f2x3sk=1时时 11111111112110,1,2,362,860,1,0,1,2,32max82xswvssxfsxfsx 阶段 0 1 2 3 k=160+26 8+18 16+0 24+0260，16,41x1s121182xfsx1f1x2s 11fs=26 阶段 0 1 k=301234560 0 0 0 0 180 180 1800001818180000

16、11101230123x3s318x3f3x4s 阶段 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+000013181826000100201204502x2s2322133xfsx2f2x3s 阶段 0 1 2 3 k=160+26 8+18 16+0 24+0260，1 6,41x1s121182xfsx1f1x2s1230,2,0 xxx1231,0,1xxx21用动态规划解决持续三个月生产的问题。问题的数据见下表每个月当成一个阶段来进行计算求解。还要注意到该问题在实每个月当成一个阶段来进行计

17、算求解。还要注意到该问题在实现优化的每个阶段都必须满足三个约束条件：现优化的每个阶段都必须满足三个约束条件：（1）最终库存量必须小于等于仓库容量；）最终库存量必须小于等于仓库容量；（2）每阶段的生产量不能超过生产能力；）每阶段的生产量不能超过生产能力；（3）初始库存量加上生产量必须大于等于需求量。）初始库存量加上生产量必须大于等于需求量。能力单位成本月需求生产存储生产持有1月232$175$302月323150303月33220040一月的初始库存为1单位22-第k阶段的需求量；-第k阶段的生产能力；-第k阶段结束时的存储能力；-第k阶段生产单位产品的费用；-第k阶段单位产品的库存持有成本kD

18、kPkWkCkH步骤1：划分阶段。把每个月看成一个阶段，倒序命名各个时期。即阶段1对应3月，阶段2对应2月，阶段3对应1月。步骤2：确定状态变量。设 为状态变量，表示第k阶段的开始的库存量。由于1月份初始库存为1单位，故 。另外定义 ，表示为第3阶段末的库存量。ks31s 0s步骤3：确定决策变量。设 为决策变量，表示第k阶段的生产量。且必须满足如下三个约束条件：kxkkkkkkkkkkkkkWDsxWDsxkDsxPx3,2,123步骤4：状态转移方程。步骤5：指标函数。第k阶段的指标函数 是第k阶段的生产成本（包括生产费用与贮存费用）。步骤6：函数基本方程3,2,11kDxsskkkkkv

19、3,2,100,kxDsHxDxsHxCxsvkkkkkkkkkkkkkk若若 03,2,1,min00110sfksfxsvsfkkkkkPxkkkk第一阶段：即从3月份开始正向计算。k=1时，问题可以如下表示：12040240340200,min11111111sxxsxxsv5.11 xsts31x311 xs 1x111,xsv1s1x 11sf 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 第二阶段：k=2时，该阶段的子问题可以表示为：2x222,xsv2s2x 22sf 0 1 2 0

20、 M 1 300+600 2 900 2 150+600 330+400 2 730 22211222112211min,1503031803090vsxfsxsxfsxsfs622 xs22x322 xs 第三阶段：k=3时，该阶段的子问题可以表示为：3x333,xsv3s3x 33sf 0 1 2 3 1 175+M 380+900 1185+730 2 1280 2233223332233360302053030175,minsfsxsfxsxsfxsv433 xs33x233 xs 1x111,xsv1s1x 11sf 0 1 2 3 0 600 3 600 1 400 640 2 4

21、00 2 200 440 680 1 200 3 0 240 480 0 0 2x222,xsv2s2x 22sf 0 1 2 0 M 1 300+600 2 900 2 150+600 330+400 2 730 3x333,xsv3s3x 33sf 0 1 2 3 1 175+M 380+900 1185+730 2 1280 月份 初始库存生产量销售量月末库存生 产成本持有成本总成本一月1221$350$30$380二月12303000300三月03306000600总计$1250$30$1280最优策略29资源分配问题:是指将供应量有限的一种或若干种资源（如原材料、资金、机器设备、劳动

22、力等），分配给若干用户，而使目标函数最优。设有某一种原料，总量为M，拟用来进行n种生产活动。若分配数量为 的原料用于第i种生产活动，其收益为 ，应该如何分配，才能使n种生产活动的总收益最大？静态规划模型为：ix iixg nixMxxxxgxgxginnn,2,10max21221130用动态规划方法求解此类问题时，一般地，将n种活动作为一个互相衔接的整体，由于要确定分配给每种活动的资源数，因此通常以把资源分配给一个或几个使用者的过程作为一个阶段，每个阶段都要确定分配给一种活动的资源量，并要先对n种活动指定分配的阶段序号。在资源分配中，由于将阶段联系在一起的是所有生产活动都在争取的资源，因此，

23、状态变量就要按照资源的分配来确定。故把第k阶段的状态变量 定义为第k阶段初所拥有的资源量，即将要在第k种活动到第n种活动间分配的资源量。这样，我们在确定第k阶段的资源分配时就无需考虑以前的资源分配情况。决策变量 就定义为对第k种活动的资源投放量，即对第k种活动的资源分配量。kskx kkkkkxgxsv,0,2,1min11110nnkkkksxkksfnksfxgsfkk31某船舶总公司拟将5亿元资金投放到下属A、B、C三个船厂，各船厂在获得资金后的收益如表所示。试用动态规划方法求使总收益最大的投资分配方案。A、B、C三个船厂分别编号为1，2，3，对A、B、C三个船厂分配资金分别形成1,2,

24、3三个阶段，即该问题可作为三阶段决策过程。k=1,2,3。k=1时时，将资金分给1,2,3三个船厂；k=2时时，将资金分给2,3两个船厂；k=3时时，将资金分给3船厂。32K=3时，考虑将资金分给船厂C，3330,50sxs 3344333333maxmaxxgsfxgsfxx k=301234501379100123453s 33fs3x33k=2时，考虑将资金分给船厂B、C，2222230,50,sxsxss 2232233222222maxmaxxsfxgsfxgsfxx 012345k=201234500+10+30+70+90+104+04+14+34+74+96+06+16+36+

25、78+08+18+39+09+19+004681113012311,22x2s 22322xsfxg 22sf2x34k=1时，考虑将资金分给船厂A、B、C5,1112sxss 2211111maxsfxgsfx 012345k=150+13 3+115+87+68+49+01411x1s 11211xsfxg 11sf1x 1451f 33,14,15321xxx35k=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,311x1s

26、 11211xsfxg 11sf1x若总投资额为3亿元 931f122331,22,00 xsxsx122332,11,00 xsxsx 36第一节的集装箱多式联运优化问题进行求解NiMQkjiC,klicklitkjid,kjiv,其他；种交通工具；选择第货物在城市ikjiMkNjikiX,2,1,01,，其他；种运输工具；种运输工具转换到第从第货物在城市ikliMlkNilkir,2,101表示所有节点城市的个数表示i城市可选运输方式集合，1-公路、2-铁路、3-水运表示集装箱多式联运中货物运输总量表示i城市到j城市k运输方式的单位距离的运价表示i城市到j城市k运输方式的距离表示i城市到j

27、城市k运输方式的速度表示i城市k运输方式转换为l方式的中转费用表示i城市k运输方式转换为l方式的中转时间37kliiklklikiikiikiiikkiicrQdCXZ1,1,1,1,min目标函数：）（；）（）（）（）（）（，）（约束条件：81,3,21,07,;1,3,21,0654,;1,3,223,2,1121,2,111,max1,1,1,1,min1,1,1,1,1,11,MkNiXMlkNirttrXvXdttrXvXdMlkNirXXNirNiXkiildildiikkliikkiikiikiikiildiikkliikkiikiikiikiikliliikiiklklikki

28、i38约束式（4）是确保运输的连续性。i-1i+1ikl分成三种情况来讨论kiiX,1liiX1,均为1，则klir也为1kliliikiirXX21,1kliliikiirXX21,1kiiX,1liiX1,一个为0，一个1，则klir必须为0kliliikiirXX21,1kiiX,1liiX1,均为0，则klir也为0kliliikiirXX21,139模型基于动态规划的基本算法程序设计如下：步骤1：令每两个城市之间的运输过程为动态规划中的一个阶段步骤2：选择货物到达城市的运输方式为该阶段的状态变量如：第2阶段的到达方式有公路、铁路，则 2,12S设计一个3n的状态矩阵，矩阵的第k列表示

29、第k个阶段的状态变量构造的列向量（没有的话，用MATLAB中特有的常量 填充）NaN如：一个3阶段的问题，各阶段的可达状态集合分别为1,1，3，1，2，3，则该问题需输入的状态变量矩阵为111233NaNNaNNaN步骤3：确定决策变量和状态转移方程。在此例中，令从每一城市出发时所选择的运输方式作为该阶段的决策变量 状态转移方程kx1kksx将状态矩阵作为动态规划程序的一个输入变量。40步骤4：删除不满足时间强约束的可选择方案，这也是与在一般情况下运用动态规划求解问题的区别所在。由于在模型中我们限定了多式联运总时间必须在顾客要求的范围 之内，因此在进行选择最优方案之前应该先排除不满足时间要求的

30、方案。maxmin,tt步骤5：由边界条件kn开始,求出在该阶段状态为ks的指标函数值，选取其中的最优值作为该阶段状态为时所有允许决策下ks时的最优值，求出最优决策 kksx并进行替换存储。直到最后求出 11sf得到问题的指标函数最优值。步骤6：由k=1开始，按照与前一步骤相反的顺序推算，记录推算结果，则可得到每阶段及全局的最优路径及最优解，存储结果并输出。41按照上述算法设计的思路所设计的解法程序主要由以下子程序组成：（1）主函数function p_opt,fval,tw=dyn(x,tm,tn，SubObjFun,TransFun,ObjFun)，输入状态变量矩阵和顾客要求的时间约束，输

31、出的变量为全局最优策略组(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 tmp

32、80=ObjFun(tmp00,f_opt),输入阶段指标值(tmp00)和后一阶段至最后阶段指标值(f_opt)，输出值为该阶段至最后阶段指标值。42集装箱多式联运各种运输方式的成本情况表成都-郑州郑州-南京南京-上海公路运输8.178.789.98铁路运输3.323.795.05水路运输/1.94成本(美元/km.TEU)43 将上述参数输入到优化算法程序中，得到最优的运输方式组合策略为：成都（公路）郑州（公路）南京（铁路）上海。此时的最小运输成本为39631美元,完成运输任务所需要的时间为29.11小时。如果对运输时间的要求放宽至起运后40-50小时之内到达即可，此时再次对该问题求解，得到的最优策略组合变为：成都（铁路）郑州（铁路）南京（水路）上海。此时的最小运输成本为15826美元,完成运输任务所需要的时间为46.96小时。