《动态规划及其应用》PPT课件.ppt

广东轻工职业技术学院 SHUFESHUFE 物流运筹学方法 缪兴锋 教授/高级工程师 联系方法：634378 E-mail: wuliuxitong 163.com 广东轻工职业技术学院 2013 1 广东轻工职业技术学院 SHUFESHUFE 第四章 动态规划及其应用 【学习目标】 知识目标 1.了解动态规划的作用与意义以及在实际中的应用 2.掌握动态规划的基本方法以及动态规划的建模 3.掌握动态规划是规划论的一个重要分支，理解它与 传统的解题不同方法； 4.掌握动态规划的顺序及逆序解法。 2 广东轻工职业技术学院 SHUFESHUFE 能力目标 1. 能够结合实际情况建立动态规划模型 ，把一个复杂的 问题，划分为一系列小问题，以便通过解这些小问题来 求得全部问题的解决 2. 能够应用顺序及逆序解法求解简单的投资分配问题、 货物配装问题、最短路径问题以及生产与存储问题 3 广东轻工职业技术学院 SHUFESHUFE 【项目导入】 机械挖掘金矿问题 两个金矿A,B分别有存储量x，y，现有一部开矿机器。 如果开采金矿A，则以概率P1得储量x的r1倍（0 r11），并且 机器没有损坏，可以继续再去开采金矿A或B。同时又以概率1- P1 宣告失败，机器报废，也得不到金子； 如果把这部开矿机器用以开采金矿B，则以概率P2得到储量y的 r2倍（0r21），并且机器没有损坏，可以继续再去开采金矿A或 B，同时又以概率1- P2宣告失败，机器报废，也得不到金子。 把机器用于开采金矿A或者B，如果机器没有损坏，将继续把机 器用于开采金矿A或者B，直到机器损坏，问应该如何选择开矿的 序列使获得金子的期望值最大。 讨论题： 1. 运筹学的产生是不是属于偶然现象？ 2. 运筹学与物流的结合应用中间有什么必然联系？ 4 广东轻工职业技术学院 SHUFESHUFE 动态规划是解决多阶段决策过程最优化问题的一种方法。 该方法在工程技术、企业管理、物流规划与管理以及军事等部门都 有广泛的应用，并取得了显著的效果。 在物流管理中，动态规划可以解决最优路径问题、生产计划与库存 、资源分配问题、装载排序、投资及生产过程的最优控制等问题。 它的独特解题思路，在处理某些优化问题时，比线性规划或非线性 规划方法更有效。 动态规划的优点是可把一个N维优化问题化成N个一维优化问题求 解；求得最优解以后，可得所有子问题的最优解。 动态规划的缺点是没有统一的处理方法，不同的问题具有不同的模 型，采用不同的求解方法，而且求解技巧要求比较高；状态变量维 数不能太高，一般情况下变量维数小于10。 5 广东轻工职业技术学院 SHUFESHUFE 任务一：动态规划问题概述 v动态规划是把多阶段决策问题作为研究对象。 v所谓多阶段决策是指可将问题求解的全过程划分 为若干个互相联系的阶段 (即将问题划分为许多个 互相联系的子问题)，在它的每一阶段都需要作出 决策，并且在一个阶段的决策确定以后再转移到 下一个阶段。 v在决策过程中，往往前一个阶段的决策要影响到 后一阶段的决策，从而影响整个过程。 v这类把一个问题划分成若干个相互联系的阶段并 选取其最优策略的问题就是多阶段决策问题。 6 广东轻工职业技术学院 SHUFESHUFE 一、动态规划问题提出 1951年，美国数学家贝尔曼（RBellman，19201984） 研究了一类多阶段决策问题的特征，提出了解决这类问 题的基本原理。在研究、解决了某些实际问题的基础上 ，他于1957年出版了动态规划这一名著。本章将简 要介绍动态规划的思想方法及其应用。 由于动态规划与“时间”关系很密切，随着时间过程的发 展而决定各阶段的决策，产生一个决策序列，这就是“动 态”的意思。 然而它也可以处理与时间无关的静态问题，只要在问题 中人为地引入“时间”因素，将问题看成多阶段的决策过 程即可。 7 动态规划解决问题的基本思路：把整体比较复杂的大问 题划分成一系列较易于解决的小问题，通过逐个求解， 最终取得整体最优解。 这种“分而治之，逐步调整”的方法，在一些比较难以解 决的复杂问题中已经显示出优越性。 在经济管理决策中，有些管理决策问题可以按时序或空 间演变划分成多个阶段 ，呈现出明显的阶段性； 于是可把这类决策问题分解成几个相互联系的阶段，每 个阶段即为一个子问题； 原有问题的求解就化为逐个求解几个简单的阶段子问题 ； 每个阶段的决策一旦确定，整个决策过程也随之确定， 此类问题称为多阶段决策问题。 8 广东轻工职业技术学院 SHUFESHUFE 二、动态规划的基本概念 动态规划数学模型由阶段、状态、决策与策略、 状态转移方程及指标函数等5个要素组成。 为了理解动态规划的解题思路， 9 广东轻工职业技术学院 SHUFESHUFE 1.动态规划决策过程划分 q根据多阶段决策过程的时间参量是离散的还是连 续的，动态规划过程可分为：离散决策过程与连 续决策过程； q根据决策过程的演变是确定性的还是随机性的， 可分为：确定性、随机性的决策过程。 q这样组合起来就有离散确定性、离散随机性、连 续确定性、连续随机性 四种决策过程模型。 q有些决策过程的阶段数是固定的，称为定期的决 策过程， q有些决策过程的阶段数是不固定的或可以有无限 多阶段数，分别称为不定期或无期的决策过程。 10 广东轻工职业技术学院 SHUFESHUFE 例4.1 线性规划问题 max f (X1,X2)8 X1 9 X2 s.t v 这个问题的求解很简单，直观处理便可以找出最这个 问题的求解很简单，直观处理便可以找出最优解，因为目 标函数为X1， X2的线性函数，且系数均为正值， X2的系 数比X1的系数大，所以最优解中的X2 的取值要尽量大， X1 取值要相对较小，再分析约束条件，得： v X10， X2 6 v 目标函数最优值为： v Fmax f(X1， X2) 54。 4X12X2 12 X10，X20 3.1 3.2 11 广东轻工职业技术学院 SHUFESHUFE 运用动态规划的方法来处理这个问题 q从形式上我们把问题分解为两个子问题，每次只考虑一 个变量。 q第一阶段，从形式上考虑X1，由约束条件（3.2）知,第一 阶段的X1的取值范围应为：04X112， q其对目标函数的贡献为R18X1。 q当第一阶段X1形式取值确定后，在下一阶段X2的变化范 围是： 02 X2 124X1 q在此基础上，在形式上考虑X2 ，它对目标函数的贡献为 R29X2。 12 广东轻工职业技术学院 SHUFESHUFE q上面只是形式上考虑X1和X2，并没有说它们具体取何值 ，下面用回代过程来求解。 q 求解过程与分析过程相反，即把第二阶段作为计算的第 一步。 S.t 第一步：把X1的取值作为参数，考虑子问题 max f19X2 2X2124X1 X20 v这个问题当X2取最大值时目标函数达到极大，因此最优解 为: X262X1 v目标函数值为： F1Maxf19（62X1） 13 广东轻工职业技术学院 SHUFESHUFE 第二步：考虑子问题 qMaxf28X1 F1 8X19（62X1）5410X1 4X112 X10 S.t. v这个问题当X1取最小值时目标函数达到极大，因此最优 解为：X10 v目标函数值为：F2Max f254。 v把X10 代入第一步中的 X2的表达式,得：X26 v这个结果与前面直观处理计算是一致的。 14 广东轻工职业技术学院 SHUFESHUFE 2.动态规划的基本概念 1）阶段 (stage) 为能应用动态规划方法，首先必须根据实际问题所处的 时间、空间或其他条件，把所研究的问题恰当地划分成 若干个相互联系的阶段。 用k1，2，n，表示阶段序号，把k 称为阶段变 量。如例1分为二个阶段，则n2，k1，2。 15 广东轻工职业技术学院 SHUFESHUFE 2） 状态 (state) v各阶段开始的客观条件叫做状态。描述各阶段状态的变 量称为状态变量，常用Yk表示第k阶段的状态变量。 v上例中记约束条件的右端的12为初始状态,即Y0 12. v它是第一阶段的输入状态。 vY1Y04X1 v为第一阶段的输出状态，也是第二阶段的输入状态。 vY2Y12X1 v为第二阶段的输出状态。Y2实际上相当于一般规划中的 松弛变量。 16 广东轻工职业技术学院 SHUFESHUFE 动态规划中的状态具有如下性质： v在一个阶段中，可以有若干个状态，第k 段所有状态 构成的集合，称为第k段状态集，记为Yk y k 。 v当某阶段状态给定以后，在这阶段以后的过程的发展 不受这段以前各段状态的影响。 v即：过程的过去历史只能通过当前状态去影响它未来 的发展，这称为无后效性。 v如果所选定的变量不具备无后效性，就不能作为状态 变量来构造动态规划模型。 17 广东轻工职业技术学院 SHUFESHUFE 3）决策（decision） v所谓决策，是指对某一阶段活动初从给定的状态出发，决策 者面临若干个不同的行为方案或途径作出的一种选择。 v 由于实际问题千变万化，因而决策可以有形形色色的不同含 义，很难言简而概全。 v 但无论如何，有一点则是肯定的，就是每段的决策都取决于 该段的状态，它要随状态的变化而变化。 v 用xk 表示第 k 段的决策，称之为第 k 段决策变量；由于决策 随状态而变，所以决策变量 xk是状态变量Yk的函数， 记为xkxk (Yk)。 v 决策变量的取值一般都要受到一定条件的限制，我们把第k段 决策变量的允许取值范围称为第k 段允许决策集合， 记为Xk(Yk)，于是xk (Yk) Xk(Yk) . 18 广东轻工职业技术学院 SHUFESHUFE 4）状态转移方程 能否成功地应用动态规划方法，重要条件之一，就是所设状 态变量和决策变量必须满足： Yk和Xk，的取值一经确定，则下一段状态变量Yk+1的取值规 律也能随之确定， 就是说，Yk+1与Yk和Xk之间必须能够建立一种明确的数量对 应关系。 在动态规划中本阶段的状态往往是上一阶段的决策结果。 如果给定了第k段的状态Yk ，则第k+1段的状态Yk+1由公式 ： Yk+1 = Tk（YK，Xk+1） 确定 这种明确的数量关系称为状态转移方程。 19 广东轻工职业技术学院 SHUFESHUFE 5）策略 (policy) v 在多阶段决策过程中，每一阶段均有一个决策，依序组合成 一个全过程的决策序列，称为全过程策略，简称策略，记为 p1(y1)，有： p1(y1) =x1(y1)，x2(y2)，, xn(yn)， 简记p1 =x1，x2，, xn v 从过程的某个阶段开始到最终阶段结束称为后部子过程。从 第k阶段开始的后部子策略称为第k子过程策略。 pk(yk) =xk(yk)，xk+1(yk+1),，xn(yn) ， 简记pk=xk，xk+1，, xn v 每一阶段有若干状态，每个状态又有若干个不同的决策，即 有许多策略可供选择。全体策略构成允许策略集合Pk(yk)。 v 能使预期目标达到最优效果的策略称为最优策略P*k， v 构成最优策略的各决策称为相应阶段的最优决策x*k。 20 广东轻工职业技术学院 SHUFESHUFE 6）指标函数 指标函数有阶段的指标函数和过程的指标函数之分。 阶段的指标函数是对应某一阶段状态和从该状态出发的一个 阶段的决策效果的优劣的数量指标，称为阶段指标函数Vk ， 阶段指标是状态变量和相应决策变量的函数， 即 Vk = Vk (Yk , xk )。 过程的指标函数是指从第k阶段的状态Yk出发到最后阶段 结束，各阶段绩效综合起来反映这个后部子过程的绩效，称 为过程指标函数，记为Vk,n 。 Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。 即 Vk,n = Vk,n (yk，xk , yk+1，xk+1 , yn) 21 广东轻工职业技术学院 SHUFESHUFE 根据实际问题的性质，指标函数Vk,n 可以是各个阶段指 标的和或积。 最优指数函数是指对从状态yk出发某一确定状态选取最 优策略后得到的指标函数值，是对应某一最优子策略的 某种效益度量。 （这个度量值可以是产量、成本、距离等）。 对应于从状态Yk 出发的最优子策略的效益值记作fk(Yk), 于是有 fk(Yk) = optVk,n = opt vk(yk , xk ) + fk+1(yk+1) 其中，opt 表示最优化，根据具体含义 可以求最大（max）或求最小（min）。 22 广东轻工职业技术学院 SHUFESHUFE 三、动态规划算法的基本步骤 设计一个标准的动态规划算法,通常可按以下几个步骤进 行： 1划分阶段：按照问题的时间或空间特征, 把问题分为 若干个阶段。注意这若干个阶段一定要是有序的或者是 可排序的(即无后向性)，否则问题就无法用动态规划求解 。 2选择状态：将问题发展到各个阶段时所处于的各种客 观情况用不同的状态表示出来。当然，状态的选择要满 足无后效性。 23 广东轻工职业技术学院 SHUFESHUFE 3确定决策并写出状态转移方程：之所以把这两步放在 一起，因为决策和状态转移有着天然的联系，状态转移 就是根据上一阶段的状态和决策来导出本阶段的状态。 所以,如果我们确定了决策, 状态转移方程也就写出来了 。但事实上,我们常常是反过来做, 根据相邻两段的各状 态之间的关系来确定决策。 4写出规划方程(包括边界条件)，动态规划的基本方程 是规划方程的通用形式化表达式。一般说来，只要阶段 、状态、决策和状态转移确定了，这一步还是比较简单 的。 24 广东轻工职业技术学院 SHUFESHUFE 动态规划方法的基本思路总结如下 将多阶段决策过程划分阶段，恰当地选取状态 变量、决策变量，定义最优指标函数，从而把问题 化成一簇同类型的子问题，然后逐个求解。 求解时从边界条件开始，逆过程方向行进，逐 段递推寻优。在每一个子问题求解时，都要使用它 前面已求出的子问题的最优结果，最后一个子问题 的最优解，就是整个问题的最优解。 25 广东轻工职业技术学院 SHUFESHUFE 任务二：最短路径问题 动态规划是将最初的问题分解为许多更容易解决的子问 题。 在【例题4.2】图4-1中的最短路问题中，我们把要建立的 这些子问题定义为一个4阶段的动态规划问题。 在解决这个问题之前，我们先给出一条重要的原理 贝尔曼最优化原理。 26 广东轻工职业技术学院 SHUFESHUFE 任务1：最短路径问题 若某一点在最优路径上，那么从这一点到 终点的最短路径也在最优路径上。解决最 短路径问题的动态规划方法主要是将每一 个节点看成是在最优路径上，然后做出相 应的计算。 27 广东轻工职业技术学院 SHUFESHUFE 一、贝尔曼最优化原理 一个过程的最优策略具有这样的性质，即无论其初始状 态和初始决策如何，今后诸决策对以第一个决策所形成 的状态作为初始状态的过程而言，必须构成最优策略。 这个原理是动态规划的理论基础。 应用动态规划思想方法解决一般多阶段决策问题时，其 求解过程如下： 把实际问题适当地划分成n 个阶段，阶段变量为k (k=1,2,n)； 在每个阶段k 确定状态变量Sk及此阶段可能的状态集 合Sk； 28 广东轻工职业技术学院 SHUFESHUFE 29 广东轻工职业技术学院 SHUFESHUFE 二、最短路径问题的基本算法 【例4.2】 各城市间的交通线及距离如下图4-1所示，某 物流公司进行货物配送要从城市1 到城市10，问应选择 什么路线，可使运输成本最低？ 30 广东轻工职业技术学院 SHUFESHUFE 应用逆序递推算法图解 v解： 这是一个典型的多阶段决策问题，由于所选运货路 线会有若干个不同选法，配送运输成本就不同，这就将 物流求运输成本问题转化为求最短路径问题。 v第一种求解方法：穷举法 v 从城市1 到城市10共有 C31 C31 C21 C11 =18条不同 路径； v 每条路径做3次加法，要求出最短路线需要作54次加法 ，17次比较运算， v 当问题的段数很多，各段的状态也很多时，这种方法 的计算量会大大增加，甚至使得求优成为不可能。 31 广东轻工职业技术学院 SHUFESHUFE 第二种求解方法：逆序递推算法 这种方法是从过程的最后一段开始，用逆序递推算方法 求解。 逐步求出各段各点到终点城市10的最短路线，最后求得 城市1到城市10的最短路线。 用d（Yk，uk）表示由状态Yk点出发，采用决策uk到达 下一阶段Yk+1点时的两点距离。 本案例从城市1到城市10 共分4个状态。 32 广东轻工职业技术学院 SHUFESHUFE 逆序递推算法 v 第1步，从k=4开始，状态变量Y4取两种状态8，9，到点 10的路长分别为4，3，即f4（8）=4，f4（9）=3。 第2步，k=3，状态变量Y3取三个值5，6，7，是经过一个中途 点到达终点10的两级决策问题，从城市5到10有两条路线，取其 中最短的即： f3（5）= min d(5,8)+f4（8） d(5,9)+f4（9） = min 3 + 4 5 + 3 = 7 v 则由城市5到终点10最短距离为7，路径为： 5810， v 相应决策为 u*3(5)=8。 33 广东轻工职业技术学院 SHUFESHUFE v则由城市6到终点10最短距离为5，路径为：6910， v相应决策为u*3(6)=9。 f3（6）= min d(6,8)+f4（8） d(6,9)+f4（9） = min 6 + 4 2 + 3 = 5 f3（7）= min d(7,8)+f4（8） d(7,9)+f4（9） = min 1 + 4 3 + 3 = 5 v则由城市7到终点10最短距离为5，路径为：7810， v相应决策为u*3(7)=8。 34 广东轻工职业技术学院 SHUFESHUFE 第3步，k=2，是具有三个初始状态2，3，4，要经过两个中途 站才能到达终点的三级决策问题。 由于第3段各点5，6，7，到终点10的最段距离f3 （5），f3 （6 ），f3（7）已知， 所以，若求城市2到10的最短距离，只需以此为基础，分别加 上城市2与5，6，7的一段距离，取其短者即可。 f2（2）= min d(2,5)+f3（5） d(2,6)+f3（6） d(2,7)+f3（7） = min 6 + 7 4 + 5 5 + 5 = 9 v 则由城市2到终点10最短距离为6，路径为： 26910， v 相应决策为u*2(2)=6。 35 广东轻工职业技术学院 SHUFESHUFE 同理有 相应决策为 ：u*2(3)=7。 f2（3）= min d(3,5)+f3（5） d(3,6)+f3（6） d(3,7)+f3（7） = min 8 + 7 7 + 5 6 + 5 = 11 f2（4）= min d(4,5)+f3（5） d(4,6)+f3（6） d(4,7)+f3（7） = min 7 + 7 8 + 5 9 + 5 = 11 相应决策为 ：u*2(4)=6。 36 广东轻工职业技术学院 SHUFESHUFE 第4步， k=1，只有一个状态点1，则 v则由城市1到终点10最短距离为17，决策为u*1(1)=2。 f1（1）= min d(1,2)+f2（5） d(1,3)+f2（3） d(1,4)+f2（4） = min 8 + 9 9+ 11 5 + 13 = 17 v 再按计算顺序反推可得最优决策序列 uk，即 u*1(1)=2， u*2(2)=6， u*3(6)=9， u*4(9)=10 v 货物运输最优路线为： 城市1城市2 城市6 城市9城市10。 37 广东轻工职业技术学院 SHUFESHUFE 第三种求解方法： WINQSB 软件求解法 第一步：打开 “动态规划-DP.EXE”软件界面，点击 (Stagecoach,最短路径）输入标题，城市数目，如下图。 38 广东轻工职业技术学院 SHUFESHUFE 第二步：输入城市之间的距离数，如下图。 39 广东轻工职业技术学院 SHUFESHUFE 第三步：点击 Solve and Analyze ，如下图。 40 广东轻工职业技术学院 SHUFESHUFE 三、定价问题 【 例4.3】某厂要确定 一种新产品在今后五年 内的价格，并已拟定只 在5，6，7，8元这四种 单价中进行选择。据预 测，今后五年不同价格 下每年盈利（万元）如 表1所示，但是各相邻年 度价格增减不得超过1元 。问今后五年内每年定 价各为多少，可预期五 年总利润最大？ 41 广东轻工职业技术学院 SHUFESHUFE 解：用标号法求解，逆序递推 （1）求最长路线，最后结果如图。 42 广东轻工职业技术学院 SHUFESHUFE 求解过程： 43 （1）定价问题是求最长路线问题，因而函数基本方程为 取最大值而非最小值； （2）最短路线问题，始点和终点均为固定，而定价问题 则始点和终点均不固定，因此最后在始端还要再决策一 次。由 确定第一年定价为8元，从而最优定价策略为： 44 广东轻工职业技术学院 SHUFESHUFE 结论： 即：前两年定价为8元，以后逐年降低1元，这样能使今 后五年预期盈利最大，为38万元； 最短路线问题每个点到下面相邻几个点的距离一般不等 ；定价问题则均相等（即某年、某价格下的预计盈利额 ）； 这里的定价问题实际上是一种特殊的最优路线问题。 45 广东轻工职业技术学院 SHUFESHUFE 【例4.3】 某厂估计某一种新产品未来四年内每年在不同价格下的 期望利润（万元)如下表所示。如果相邻两年间价格调整 幅度： （1）不超过2元； （2）不超过4元； （3）无任何限制； 试就这三种情况分别确定各年最优定价？ 46 广东轻工职业技术学院 SHUFESHUFE 表2 47 广东轻工职业技术学院 SHUFESHUFE 解 ：（1）不超过2元的最优定价策略 最优定价策略为： 48 广东轻工职业技术学院 SHUFESHUFE 解： （2）不超过4元 最优定价策略为： 49 广东轻工职业技术学院 SHUFESHUFE 解： （3）无任何限制 最优定价策略为： 50 广东轻工职业技术学院 SHUFESHUFE 四、动态规划的要点 动态规划提供了一种优秀的决策思想：战略上追求全 局优化，战术上稳扎稳打、步步为营。 深刻地揭示了局部与全局的统一关系。 动态规划在实际中得到广泛应用，如何应用于背包问 题，资源分配问题、生产与存储问题、设备更新问题等 。 另外，需要指出的是：动态规划是一种求解思路，注 重决策过程，而不是一种算法，不同的问题模型各异， 需要具体问题，具体分析求解。 51 广东轻工职业技术学院 SHUFESHUFE 任务三：旅游背包问题 旅游背包问题在物流方面表现为货物配装问题，如 储运仓库（或货运车站）整装零担车内装有多种货 物，要把各个客户所需要的零担货物组成整车，通 过铁路运往各地，货车装载能力一定，如何配装实 现价值最大化。 52 广东轻工职业技术学院 SHUFESHUFE 一、旅游背包问题数学模型 背包问题用动态规划方法求解只有一个约束条件（一维背包 问题）的整数规划最优解，即背包只有重量或体积限制。 设数学模型为： S.t. 53 54 广东轻工职业技术学院 SHUFESHUFE 二、背包问题逆序法求解 【例4-3】 假设有4种货物A、B、C、D，其中A有2件， 每件重6t，B有1件，每件重20t，C有3件，每件重11t，D 有2件，每件19t，如表4-3所示。货车车厢的载重量上限 为50t。如何配装，才能充分利用车辆的装载能力。 表4-3 四种货物资料 货物种类 ABCD 件数/件2132 每件重量/t6201119 55 广东轻工职业技术学院 SHUFESHUFE 解： 1、阶段的划分和计算 货物配装可以设定：装入一种货物看做一个阶 段，把货物配装问题化为动态规划问题。本例 题4种货物配装过程划分为四个阶段。 采用逆推法，第1阶段分析装入货物D的数量。 把货物D的件数折算成重量，用G1表示，共2件 ，每件重量为19t。 56 广东轻工职业技术学院 SHUFESHUFE 第1阶段的状态有三种：0、19和38。输入状态 为车辆可能的载重能力，此时状态为W=50。 对于3种决策：G1=0、19、38，有3个余量： W-G1 = 50、31、12。 见表4-4。 本阶段的余量将作为第2阶段的“输入状态”。 表4-4 第1阶段计算表 阶段1输 入状态 决策：装入货物D的重 量（按件折算） 最优方案 01938余量状态 505031121238 57 广东轻工职业技术学院 SHUFESHUFE 第2阶段决策时分析装入货物C的数量，用G2表示。 此阶段的输入状态时第1阶段的3个余量，即W=50、31、12。 因为每件货物C重量为11，共3件，所以决策有4种状态可供分 析，即G2=0、11、22、33。 本阶段的余量为WG2=50、39、28、17、31， 见表4-5。 表4-5 第2阶段计算表 阶段2输入 状态 决策：装入货物C的重量 （按件折算） 最优方案 0112233余量状态 50503928171733 3131209-922 12121-111 58 广东轻工职业技术学院 SHUFESHUFE 第2阶段的余量作为第3阶段的输入状态，继续分析，结果 见表4-6。 表4-6 第3阶段计算表 阶段3输入状态 决策：装入货物B的重量 （按件折算） 最优方案 020余量状态 5050303020 3939191920 28288820 1717-170 3131111120 20200020 99-90 1212-120 59 广东轻工职业技术学院 SHUFESHUFE 第4阶段决策，见表4-7 阶段1输入状态决策：装入货物A的重量（按件折算）最优方案 0612余量状态 505044383812 303024181812 393933272713 1919137712 282822161612 882-26 1717115512 313125191912 1111556 2020148812 993-36 12 12 60012 60 广东轻工职业技术学院 SHUFESHUFE 2、寻求最优解 在第4阶段计算中，余量WG4最小值为0，G4=12对应的W值为12 ；第4阶段W只对应于第3阶段的余量WG3，对应余项WG3=12 的G3=0，它们对应的W值分别为12；查第2阶段计算表，余项为12 时，G2=0，W=12；再查第1阶段计算表，余项为12 时，G1=38。 寻找过程表述为： G4= 12 G3=0 G2=0 G1=38 即把A货物12t（2件）和D货物38t（2件）配装成一车。这就是所求 的最优解。配装重量是50t，达到满载，充分利用了货车的装载能 力 61 广东轻工职业技术学院 SHUFESHUFE 另外，在第3阶段计算表中，也出现了一个余量为0的项 ，对应的G3=20，W=20；再查第2阶段计算表，余量为 20，对应的G2=11，W=31；再查第1阶段计算表，余项 31，对应G1=19。 这样，也得出另一组最优解为 G3=20 G2=11 G1=19 对于两组最优解，可根据实际情况进行选择，例如可以 优先选用第一组最优解，因为它使A，D两种货物全部配 装。 62 广东轻工职业技术学院 SHUFESHUFE 三、背包问题计算机软件求解方法 【例5】 已知1吨集装箱最大载重量800kg，有5种物品各10件 ，单位物品重量和价值见表4-8，求如何装载价值最大？ 表4-8 单位物品重量和价值 物品 12345 物品限量（件）1010101010 单位物品重量（kg）2015406030 单位物品价值（元）4025607050 63 广东轻工职业技术学院 SHUFESHUFE 用WinQSB软件求解步骤如下： 调用子程序DP，新建问题。在图4-3中选择第二项，输入 标题和物品数。 64 广东轻工职业技术学院 SHUFESHUFE 输入数据。按照表4-9的形式输入数据，第1列为物品名称 ，第2列为物品限量和集装箱限量，第3列为单位物品重量， 第4列为物品价值函数。 65 广东轻工职业技术学院 SHUFESHUFE 求解。点击菜单栏 Solve and Analyze Solve the Problem ，得到表4-10的结果。 由表4-10可以看出，表示5种物品分别装载10、9、4、0及 10件，总价值1365（元），集装箱还有5kg的剩余能力。 66 广东轻工职业技术学院 SHUFESHUFE 任务四： 生产与存储问题 企业一年中的产品生产往往是分期分批生产的。 企业组织每批产品的生产，都要花费一些生产准备费和 存贮费用。若某一时期增大生产批量则可减少生产批次 ，从而降低生产成本。 与此同时，批量大了，必然增加库存而使存贮费用增加 。 在企业产品的生产成本、存贮费用、市场需求量确定的 情况下，正确计划各时期的生产量，既满足市场需求， 又使总支出最少，这是一个多阶段决策问题，也是物流 中的生产与存储问题。 67 广东轻工职业技术学院 SHUFESHUFE 一、生产与存储问题数学模型 68 69 广东轻工职业技术学院 SHUFESHUFE 二、生产与存储问题动态规划的数学模型 70 广东轻工职业技术学院 SHUFESHUFE 三、生产与存储问题逆序法求解 例6 某工厂与用户签订了4个月的交货合同如表所示 该厂生产能力为每月5万件，该厂仓库的存货能力为4万件 。 已知生产费用为c=1千元/万件，在进行生产的月份，工厂 要支出固定费用b=2千元，每月仓库保管费用h=0.2千元/万件 /月。 假定开始时及4月底交货后无存货，试问应在每月各生产 多少件产品，才能满足交货任务，又使总费用最小？ 月1234 需求量dk( 万件) 3232 71 广东轻工职业技术学院 SHUFESHUFE 动态规划的数学模型 每个月为一个阶段，即阶段变量 k=1,2,3,4分别表示这四个月; 状态变量yk 表示第k 月初的产品库存量，0 yk 4; 决策变量xk 表示第k月的生产量 ， 允许决策集合Xk (yk)= xk 0 xk 5; 状态转移方程为 yk+1 = yk + xk dk ; 阶段指标vk(yk, xk) 表示第k 月的费用 ：本月若不安排生产，则仅需 支出保管费；本月若安排生产，则需支出生产费用和固定费，同时还 需交付保管费。 当xk =0时， vk(yk, xk)=h yk =0.2yk 当xk 0时， vk(yk, xk)=b+cxk+hyk =2+xk +0.2yk 最优指数函数fk(yk)表示第k阶段从yk 开始到最后阶段采用最优生产 策略实现的最低生产费用; 72 广东轻工职业技术学院 SHUFESHUFE 逆序求解 K=4 x4 y4 v4 (y4, x4)=0.2 y4 v4 (y4, x4)=2+ x4+0.2 y4 f3 (y3) x3* 0 1 2 012 - -4 -3.2- 0.4- 4 3.2 0.4 2 1 0 d4=2， 4月末无库存则y5=0， 状态转移方程 y5= y4+ x4 d4 ，则 y4= d4 x4 = 2 x4 x40,则y4 = 2 x4 = 0,1,2 y40,则x4 = 2 y4 = 0,1,2 73 广东轻工职业技术学院 SHUFESHUFE x3 y3 0.2 y3 + f4(y4)v3 (y3, x3)+f4(y4) =2+ x3+0.2 y3 + f4(y4) f3 (y3) x3* 0 1 2 3 4 012345 7.4 6.6 5.8 4.6 4.2 5 4 3 0 0 -9.09.27.4 -- -- - 44.2- d3=3， 0y4 2， 状态转移方程 y4= y3+ x3 d3 ，则 0 y3+ x3 d3 2，即 3 y3+ x4 5 0y34， 则y3 = 0,1,2,3,4 生产能力限制 0x3 5，则x3 = 0,1,2,3,4,5 4月在库存量为s4下的 最低生产成本 k=3 74 广东轻工职业技术学院 SHUFESHUFE k=2 x2 y2 0.2 y2 + f3(y3)v2 (y2, x2)+f3(y3) =2+ x2+0.2 y2 + f3(y3) f2 (y2) x2* 0 1 2 012345 11. 4 10. 6 7.8 2 1 0 -11. 4 11. 6 11. 8 11.6 -10. 6 10. 8 11. 0 10. 8 11.2 7.810. 0 10. 2 10. 0 10. 4 - vd2=2， 0y3 4， 状态转移方程 y3= y2+ x2 d2 ，则 0 y2+ x2 d2 4，即 2 y2+ x2 6 vy1=0， 则 y2 = y1+ x1 d1 = x1 3； x1 5， 则y2 2 v生产能力限制 0x2 5， 则 x2 = 0,1,2,3,4,5 3月在库存量为y3下的最 低生产成本 75 广东轻工职业技术学院 SHUFESHUFE k=1 x1 y1 v1 (y1, x1)+f2(y2) =2+ x2+0.2 y2 + f2(y2) f1 (y1)x1* 345 2月在库存量为y2下的 最低生产成本 0 14.85 16. 4 16. 6 14. 8 d1=3， y1=0，状态转移方程则y2 = y1+ x1 d1 = x1 3； y20，则 x1 3， 生产能力限制 x1 5，则3 x1 5 ，x1 = 3,4,5 76 广东轻工职业技术学院 SHUFESHUFE 顺序递推，得出结论 第1月生产5万件 y2 = y1+ x1 d1 =0+5-3=2，第2月不生产 y3 = y2+ x2 d2 =2+0-2=0，第3月生产5万