管理运筹学动态规划

第六章动态规划第一节：现实中的动态规划问题第二节：动态规划基本概念第三节：动态规划的基本方法第四节：配载问题第五节：生产和库存控制问题第六节：资源分配问题第七节：动态规划应用多式联运是一种以实现货物整体运输最优化为目标的联合运输组织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水路运输）二、集装箱的中转过程有很好的衔接三、集装箱运量不可以分割，在某两个特定的地点之间，只能选择一种运输方式四、集装箱运量对运输价格及运输时间没有明显的影响五、集装箱运输能力几乎不受限制六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。通常情况下，多式联运组织优化问题具有如下几个方面的特点：ZH物流公司是一家大型的集装箱多式联运经营企业，在成都设有内陆集装箱货运站（CFS），经营成都——上海间集装箱货物运输服务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将2个20英尺的集装箱从成都运往上海，运输路线为成都-郑州-南京-上海，要求在货物起运后25-30小时之内到达目的地。成都-郑州郑州-南京南京-上海公路运输1474704349铁路运输1353695303水路运输//392运输方式铁路运输公路运输水路运输运载工具速度(km/h)7010036运输方式铁路运输公路运输水路运输中转时间(h)7318如何制定运输方式组合优化方案使在满足客户需求的条件下降低集装箱运输总成本？5…S’k+1……S2多阶段决策问题阶段、决策、策略动态规划的基本特性（多阶段决策问题的基本特性）SkSk+1SnTS’nQ=S1反证法容易得证。若{S1,…,Sk,Sk+1,…,Sn,T}全程最优则{Sk+1,…,Sn,T}子程最优动态规划方法的基本思路最短路问题1234340476117811阶段A124374632441514633334A3B1QA2B2B3TC1C2——标号法三、决策是指人们对某一阶段活动中各种不同的行为或方案或途径等的一种选择。用xk表示第k段的决策，称为第k段决策变量。由于决策随状态而变,所以决策变量xk是状态变量sk的函数,记为xk=xk(sk)动态规划的基本概念一、阶段把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，…，n表示阶段序号，称为阶段变量。二、状态状态表示某段的初始条件。用sk表示第k段的状态，称为第k段状态变量。sk∈SkkkkkxsDs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的累积效应。常用函数：fk(sk,xk)=vi(si,xi)ni=kfk(sk,xk)=vi(si,xi)ni=k积函数和函数七、最优解(1)最优指标函数fk*(sk)=opt{fk(sk,pk(sk))},k=1,2,…,npk∈Pk(2)最优策略能使上式成立的子策略pk*称为最优子策略，记为pk*(sk)={xk*(sk),…,xn*(sn)}特别当k=1时,称为最优策略，记为p1*(s1)={x1*(s1),…,xk*(sk),…,xn*(sn)}(3)最优决策构成最优策略的决策称为最优决策，记为xk*。(4)最优值：最优策略对应的最优指标f*111一、最优化原理作为一个全过程最优策略具有这样的性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。二、函数基本方程f*n+1(sn+1)=0f*k(sk)=opt{vk(sk,xk)+fk+1*(sk+1)}xk∈Xkf*n+1(sn+1)=1f*k(sk)=opt{vk(sk,xk)×fk+1*(sk+1)}xk∈Xk和积k=n,n-1,…,2,1k=n,n-1,…,2,112三、基本步骤1°建立模型(1)划分阶段，设定k(2)设定状态变量sk(3)设定决策变量xk(4)建立状态转移方程(5)确定指标函数vk，fk*(6)建立函数基本方程2°递推(逆推)求解3°得出(顺推)结论sabcfedhgt2511214610134121139658105287125220141919k=44fg4dgt=5k=334334,35minmin92,ddgfgfdddhfh=83ddgk=2k=1d1(s)=bd1(s)=bd2(b)=dd3(d)=gd4(g)=t最优策略：p1(s1)={s,b,d,g,t｝最优值：f*1(s)=1914Ndnd1dNs1Nsns1ns1s0s……阶段N阶段n阶段115今有一辆载货量为6t的载货车，现有3种需要运输的货物，均可用此载货车装运。若已知这3种货物每一种的质量和运输例如下表所示。在载货量许可的条件下，每车装载每一种货物的件数不限，应如何搭配这3种货物，才能使每车装载货物的利润最大？货物种类每件质量（t）每件运输利润（百元）12823133418该问题中的货车可以看做是一个背包，需运载的货物为要装入背包的物品。该问题可以看作是一个3阶段的动态规划问题。步骤1，划分阶段。设每装一种货物为一个阶段，k=1,2,3。步骤2，确定状态变量。设状态变量为可用于装载第k种至第n种货物的装载量。160,1,2,3,4,5,62,3kssk1）确定决策变量。设决策变量表示第k种货物的装载件数2）状态转移方程为3）阶段指标函数。第k阶段装载件货物时所创的利润。4）函数的基本方程为0,1,,1,2,3kkkkksxDxkw1kkkksswxkkvx10,1,,6441,2,30kkkkkkkkkkkkxDssfsoptvxfswxkfs33333333330,10,1,,64,180,1,,60,1,,0,14max18xswvssxfsxk=3时阶段01k=301234560—0—0—0—0180180180000181818000011101230123x3s318x3f3x4sk=2时33222222223220,1,20,1,,63,130,1,,60,1,,0,1,23max133xswvssxfsxfsx阶段012k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+000013181826000100201204502x2s2322133xfsx2f2x3sk=1时11111111112110,1,2,362,860,1,,0,1,2,32max82xswvssxfsxfsx阶段0123k=160+268+1816+024+0260，16,41x1s121182xfsx1f1x2s11fs=26阶段01k=301234560—0—0—0—0180180180000181818000011101230123x3s318x3f3x4s阶段012k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+000013181826000100201204502x2s2322133xfsx2f2x3s阶段0123k=160+268+1816+024+0260，16,41x1s121182xfsx1f1x2s1230,2,0xxx1231,0,1xxx21用动态规划解决持续三个月生产的问题。问题的数据见下表每个月当成一个阶段来进行计算求解。还要注意到该问题在实现优化的每个阶段都必须满足三个约束条件：（1）最终库存量必须小于等于仓库容量；（2）每阶段的生产量不能超过生产能力；（3）初始库存量加上生产量必须大于等于需求量。能力单位成本月需求生产存储生产持有1月232$175$302月323150303月33220040一月的初始库存为1单位22--第k阶段的需求量；--第k阶段的生产能力；--第k阶段结束时的存储能力；--第k阶段生产单位产品的费用；--第k阶段单位产品的库存持有成本kDkPkWkCkH步骤1：划分阶段。把每个月看成一个阶段，倒序命名各个时期。即阶段1对应3月，阶段2对应2月，阶段3对应1月。步骤2：确定状态变量。设为状态变量，表示第k阶段的开始的库存量。由于1月份初始库存为1单位，故。另外定义，表示为第3阶段末的库存量。ks31s0s步骤3：确定决策变量。设为决策变量，表示第k阶段的生产量。且必须满足如下三个约束条件：kxkkkkkkkkkkkkkWDsxWDsxkDsxPx3,2,1　　　　　　　　　　　23步骤4：状态转移方程。步骤5：指标函数。第k阶段的指标函数是第k阶段的生产成本（包括生产费用与贮存费用）。步骤6：函数基本方程3,2,11kDxsskkkkkv3,2,100,kxDsHxDxsHxCxsvkkkkkkkkkkkkkk　　　　　　若　若03,2,1,min00110sfksfxsvsfkkkkkPxkkkk第一阶段：即从3月份开始正向计算。k=1时，问题可以如下表示：12040240340200,min11111111sxxsxxsv5..11xsts31x311xs1x111,xsv1s1x11sf01230———60036001——40064024002—200440680120030240480—00第二阶段：k=2时，该阶段的子问题可以表示为：2x222,xsv2s2x22sf0120————M1——300+60029002—150+600330+400273022211222112211min,1503031803090vsxfsxsxfsxsfs622xs22x322xs第三阶段：k=3时，该阶段的子问题可以表示为：3x333,xsv3s3x33sf01231—175+M380+9001185+730212802233223332233360302053030175,minsfsxsfxsxsfxsv433xs33x233xs1x111,xsv1s1x11sf01230———60036001——40064024002—200440680120030240480—002x222,xsv2s2x22sf0120————M1——300+60029002—150+600330+40027303x333,xsv3s