文档介绍：第五章_物流运筹学——动态规划
第五章动态规划
动态规划问题
动态规划的基本概念
动态规划模型的建立与求解
动态规划在物流管理中的应用举例
知识目标
了解动态规划在实际中的应用;
理解动态规划的基本思想;
掌握动态规划的建模;
掌握动态规划的顺序及逆序解法。
技能目标
能够结合实际情况建立动态规划模型;
能够应用顺序及逆序解法求解动态规划模型。
第一节动态规划问题
动态规划是把多阶段决策问题作为研究对象。
所谓多阶段决策问题,是指可将问题求解的全过程划分为若干个互相联系的阶段(即将问题划分为许多个互相联系的子问题),在它的每一阶段都需要作出决策,并且在一个阶段的决策确定以后再转移到下一个阶段。往往前一个阶段的决策要影响到后一阶段的决策,从而影响整个过程。把一个问题划分成若干个相互联系的阶段选取其最优策略,这类问题就是多阶段决策问题。
多阶段决策问题很多,现举出物流管理中的几个例子。
【例5-1】(生产与存储问题)工厂在3个季度中
安排某种产品的生产计划。若该季度生产此种产
品(吨),则成本为元。若当季生产的
产品未销售掉,则进库,季末需付存储费,每吨
产品每季的存储费为1元。现估计3个季度对该产
品的需求量分别为100吨,110吨和120吨,
又设第一季度初及第三季度末库存量为零。假设
每个季度产品的生产量不受限制,试问如何安排
3个季度的生产计划,使产品的生产成本和存储
费总和最低?
【例5-2】(载货问题)现有载重量为20吨的卡车,装载3种不同的货物。已知这3种货物的单件重量和装载收费如表5-1所示,又规定货物2和货物3都至多装两件。问如何装载这3种货物,可使该车一次运输的货物收费最多?
6
5
5
4
4
3
收费(元)
重量(吨)
货物
表5-1 货物的单件重量和装载收费表
【例5-3】(仪器置换问题)某化学工厂可用,,
三种不同仪器中的任一套去完成一项试验,每做完一次试验后,如果下次仍用原来的仪器,则需要对该仪器进行检查整修而中断试验;如果下次换用另外一套仪器,则需拆装仪器,也要中断试验。假定一次试验时间比任何一套仪器的整修时间都长,因此一套仪器换下来隔一次再重新使用时,不会由于整修而影响试验,设仪器换成仪器所需中断试验的时间如表5-2所示。现要做四次试验,问应如何安排使用仪器的顺序,使总的中断试验的时间最短?
表5-2 设仪器换成仪器所需中断试验的时间
8
5
6
3
10
12
9
2
14
9
10
1
仪器
3
2
1
仪器
【例5-4】(机器负荷问题)设某机器可以在高、
低两种不同的负荷下进行生产。若年初有台
机器在高负荷下进行生产,则产品年产量,
机器的年折损率;若年初有台机器在低
负荷下进行生产,则产品年产量,机器的
年折损率。若初始时有性能正常的机器1000
台,要求制定机器负荷的四年分配计划,确定每年
年初分配正常机器在不同负荷下工作的台数,使四
年内产品总产量最大。
第二节动态规划的基本概念
阶段(stage):将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序去求每阶段的解,常用表示阶段变量。
的编号方法有两种:顺序编号法,即从初始阶段编号,往后编号逐渐增大;逆序编号法,令最后一个阶段编号为1,往前编号逐渐增大,例5-5中。从到可分为: 到(有三种选择, , ),从
到( 有两种选择, ),再从到三个阶段。因此。
基本概念
状态(state):各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量,常用
表示第阶段的状态变量,状态变量的取值集合称为状态集合,用表示。
动态规划中的状态应具有如下性质:当某阶段状态给定后,在这阶段以后过程的发展不受这阶段以前各段状态的影响。也就是说,当前的状态是过去历史的一个完整总结,过程的过去历史只能通过当前状态去影响它未来的发展,这称为无后效性。如果所选定的变量不具备无后效性,就不能作为状态变量来构造动态规划模型。
决策(decision):当各阶段的状态取定以后,就可以作出不同的决策(或选择),从而确定下一阶段的状态,这种决定称为决策。表示决策的变量,称为决策变量,常用表示第阶段状态为时的决策变量。在实际问题中,决策变量的取值往往限制在一定范围内,称此范围为允许决策集合,常用表示第阶段从状态出发的允许决策集合,显然有。
策略(policy):各阶段决策确定后,整个问题的决策序列就构成一个策略。用
表示。对每个实际问题,可供选择的策略
有一定范围,称为允许策略集合,记作
。使整个问题达到最优的策略就是最优策略。
状态转