物流运筹学——动态规划.ppt

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