[交通运输]第五章 动态规划.ppt

动态规划最优性原理和递推方程 例1 （最短路问题）在线路网络图中，从A到E有一批货物需要调运。图上数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。 基本方程 从上面的例子不难看出，对于最短路 问题，有如下递推关系： 基本方程 一般情况下，多阶段决策问题存在下 面的递推关系： *是运算符号，大多数取“+”或“×”； 其中“opt”是最优（optimization）的缩写，可根据题意取min或max。 为此递推关系的边界条件，一般，当*取“+”时，C=0；当*取“×”时，C=1。 基本方程 动态规划方法的基本思想： 首先将问题的过程分为几个相互联系的阶段，恰当地选取状态变量、决策变量、阶段指标函数、过程指标函数和最优值函数，从而把一个大问题化成一族同类型的小问题，然后逐个求解。 求解从边界条件开始，逆（或顺）过程的行进方向，从而逐步可求得各段的最优决策或最优决策关于状态变量的表达式，以及相应的最优值或最优值函数的表达式，在每个子问题的求解中均利用了它前面子问题的最优化结果，依次进行，最后一个子问题所得的最优值就是整个问题的最优值。 建立动态规划数学模型的步骤 一般来说，利用动态规划求解实际问 题需先建立问题的动态模型，具体步 骤如下： 1.将问题按时间或空间次序划分成若 干阶段。有些问题不具有时空次序， 也可以人为地引进时空次序，划分阶 段。 2.正确选择状态变量xk这一步是形成 动态模型的关键，状态变量是动态规 划模型中的最重要的参数。一般来 说，状态变量应具有一下三个特征： 建立动态规划数学模型的步骤 （1）要能够用描述决策过程的演变特征。 （2）要满足无后效性。如果某阶段状态确定后，则在这个阶段以后的过程发展不受这个阶段以前各阶段状态的影响。 （3）递推性（确定性决策过程）。即由K阶段的状态变量xk和决策变量uk可以计算出k+1阶段的状态变量xk+1。 3.确定决策变量uk及允许决策变量集合Dk（xk）。 建立动态规划数学模型的步骤 4.写出状态转移方程。根据状态变量 之间的递推关系，写出状态转移函数：xk+1=T(xk,uk(xk))。 5.建立阶段指数函数和过程指标函数，要求过程指标函数满足以下条件： （1）过程指标函数Rk，n应该可以表示为xk,uk,Rk+1 ,n的函数，记为： 表示出Rk，n 和Rk+1 ,n 之间的递推关系。 （2）函数 对于变量Rk+1 ,n是严格单调。 建立动态规划数学模型的步骤 6.建立动态规划基本方程 例2 某厂新购某种机床125台。据估计，这种 设备5年后将被其它设备所取代。此机床 如在高负荷状态下工作，年损坏率1/2， 年利润为10万元；如在低负荷状态下工 作，年损坏率为1/5，年利润为6万元。 问应如何安排这些机床的生产负荷，才 能使5年内获得最大利润。 一维资源分配问题 设有某种资源（例如电、煤等）可用 于n项活动，假设资源的数量为a，已 知用于第i项活动的资源数为xi时，可 以得到收益gi(xi),i=1、2…n。试确定 资源的分配方案使总收益最大。 该问题的数学模型可以表示为 一维资源分配问题 例1某公司拟将5万元资金投放下属的 A,B，C三个企业，各企业，各企业在 获得资金后的收益如下表所示，试确 定总收益最大的投资分配方案（投资 数以百万元计） gk(xk) 例5 （资源分配问题）某公司有资金10万元，拟投资于3个项目，已知对第i个项目投资xi万元，收益为g i (xi)，问应如何分配资金可使总收益最大？其中， 解：阶段k=1,2, 3 决策变量uk ：第k个项目的投资额 状态变量sk ：在第k阶段时可以用于投资 第k到第3个项目的资金数 阶段指标函数Vk,n ：第k阶段可分配的资金数为sk时，第k至第3个项目的最大总收益 状态转移方程： sk+1 = sk -uk 一维资源分配问题 用逆序解法解 k=3时 k=2时 令 由 解得 极大值只可能在[0,s2]端点取得，f2(0)= f2(s2)=9s2 一维资源分配问题 k=1时 同理可求出u1=s1-1是极小点 最优投资方案为全部资金投于第三个项目，可得最大收益200万元。 一维资源分配问题 例8某工厂生产并销售某种产品，已知今后四个月市场需 求预测如表7-7，又每月生产j单位产品费用为： C(j)= 0(j=0) 3+j(j=1,2,…，6)(千元) 每月库存j单位产品的费用为E(j)=0.5j(千元)，该厂 最大库存容量为3单位，每月最大生产能力为6单位，计 划开始和计划期末库存量都是零。试制定四个月的生产 计划，在满