动态规划及其应用.ppt

《动态规划及其应用.ppt》由会员分享，可在线阅读，更多相关《动态规划及其应用.ppt（92页珍藏版）》请在三一办公上搜索。

1、1,物流运筹学方法,缪兴锋 教授/高级工程师联系方法：634378 E-mail:wuliuxitong 广东轻工职业技术学院2013,2,第四章 动态规划及其应用,【学习目标】知识目标 1.了解动态规划的作用与意义以及在实际中的应用 2.掌握动态规划的基本方法以及动态规划的建模 3.掌握动态规划是规划论的一个重要分支，理解它与传统的解题不同方法；4.掌握动态规划的顺序及逆序解法。,3,能力目标1.能够结合实际情况建立动态规划模型，把一个复杂的问题，划分为一系列小问题，以便通过解这些小问题来求得全部问题的解决 2.能够应用顺序及逆序解法求解简单的投资分配问题、货物配装问题、最短路径问题以及生产

2、与存储问题,4,【项目导入】,机械挖掘金矿问题 两个金矿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.运筹学的

3、产生是不是属于偶然现象？2.运筹学与物流的结合应用中间有什么必然联系？,5,动态规划是解决多阶段决策过程最优化问题的一种方法。该方法在工程技术、企业管理、物流规划与管理以及军事等部门都有广泛的应用，并取得了显著的效果。在物流管理中，动态规划可以解决最优路径问题、生产计划与库存、资源分配问题、装载排序、投资及生产过程的最优控制等问题。它的独特解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。动态规划的优点是可把一个N维优化问题化成N个一维优化问题求解；求得最优解以后，可得所有子问题的最优解。动态规划的缺点是没有统一的处理方法，不同的问题具有不同的模型，采用不同的求解方法，而且求解

4、技巧要求比较高；状态变量维数不能太高，一般情况下变量维数小于10。,6,任务一：动态规划问题概述,动态规划是把多阶段决策问题作为研究对象。所谓多阶段决策是指可将问题求解的全过程划分为若干个互相联系的阶段(即将问题划分为许多个互相联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。在决策过程中，往往前一个阶段的决策要影响到后一阶段的决策，从而影响整个过程。这类把一个问题划分成若干个相互联系的阶段并选取其最优策略的问题就是多阶段决策问题。,7,一、动态规划问题提出,1951年，美国数学家贝尔曼（RBellman，19201984）研究了一类多阶段决策问题的

5、特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上，他于1957年出版了动态规划这一名著。本章将简要介绍动态规划的思想方法及其应用。由于动态规划与“时间”关系很密切，随着时间过程的发展而决定各阶段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时间”因素，将问题看成多阶段的决策过程即可。,动态规划解决问题的基本思路：把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这种“分而治之，逐步调整”的方法，在一些比较难以解决的复杂问题中已经显示出优越性。在经济管理决策中，有些管理决策

6、问题可以按时序或空间演变划分成多个阶段，呈现出明显的阶段性；于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题；原有问题的求解就化为逐个求解几个简单的阶段子问题；每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。,9,二、动态规划的基本概念,动态规划数学模型由阶段、状态、决策与策略、状态转移方程及指标函数等5个要素组成。为了理解动态规划的解题思路，,10,1.动态规划决策过程划分,根据多阶段决策过程的时间参量是离散的还是连续的，动态规划过程可分为：离散决策过程与连续决策过程；根据决策过程的演变是确定性的还是随机性的，可分为：确定性、随机性的决策过程。

7、这样组合起来就有离散确定性、离散随机性、连续确定性、连续随机性 四种决策过程模型。有些决策过程的阶段数是固定的，称为定期的决策过程，有些决策过程的阶段数是不固定的或可以有无限多阶段数，分别称为不定期或无期的决策过程。,11,例4.1 线性规划问题,max f(X1,X2)8 X1 9 X2,s.t,这个问题的求解很简单，直观处理便可以找出最这个问题的求解很简单，直观处理便可以找出最优解，因为目标函数为X1，X2的线性函数，且系数均为正值，X2的系数比X1的系数大，所以最优解中的X2 的取值要尽量大，X1 取值要相对较小，再分析约束条件，得：X10，X2 6 目标函数最优值为：Fmax f(X1

8、，X2)54。,12,运用动态规划的方法来处理这个问题,从形式上我们把问题分解为两个子问题，每次只考虑一个变量。第一阶段，从形式上考虑X1，由约束条件（3.2）知,第一阶段的X1的取值范围应为：04X112，其对目标函数的贡献为R18X1。当第一阶段X1形式取值确定后，在下一阶段X2的变化范围是：02 X2 124X1在此基础上，在形式上考虑X2，它对目标函数的贡献为R29X2。,13,上面只是形式上考虑X1和X2，并没有说它们具体取何值，下面用回代过程来求解。求解过程与分析过程相反，即把第二阶段作为计算的第一步。,S.t,第一步：把X1的取值作为参数，考虑子问题 max f19X2,这个问题

9、当X2取最大值时目标函数达到极大，因此最优解 为:X262X1目标函数值为：F1Maxf19（62X1）,14,第二步：考虑子问题,Maxf28X1 F1 8X19（62X1）5410X1,S.t.,这个问题当X1取最小值时目标函数达到极大，因此最优解为：X10目标函数值为：F2Max f254。把X10 代入第一步中的 X2的表达式,得：X26这个结果与前面直观处理计算是一致的。,15,2.动态规划的基本概念,1）阶段(stage)为能应用动态规划方法，首先必须根据实际问题所处的时间、空间或其他条件，把所研究的问题恰当地划分成若干个相互联系的阶段。用k1，2，n，表示阶段序号，把k 称为阶段

10、变量。如例1分为二个阶段，则n2，k1，2。,16,2）状态(state),各阶段开始的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用Yk表示第k阶段的状态变量。上例中记约束条件的右端的12为初始状态,即Y0 12.它是第一阶段的输入状态。Y1Y04X1为第一阶段的输出状态，也是第二阶段的输入状态。Y2Y12X1为第二阶段的输出状态。Y2实际上相当于一般规划中的松弛变量。,17,动态规划中的状态具有如下性质：,在一个阶段中，可以有若干个状态，第k 段所有状态构成的集合，称为第k段状态集，记为Yk y k。当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响。即：过

11、程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。,18,3）决策（decision）,所谓决策，是指对某一阶段活动初从给定的状态出发，决策者面临若干个不同的行为方案或途径作出的一种选择。由于实际问题千变万化，因而决策可以有形形色色的不同含义，很难言简而概全。但无论如何，有一点则是肯定的，就是每段的决策都取决于该段的状态，它要随状态的变化而变化。用xk 表示第 k 段的决策，称之为第 k 段决策变量；由于决策随状态而变，所以决策变量 xk是状态变量Yk的函数，记为xkxk(Yk)。决策变量的取值一般都要受到一定

12、条件的限制，我们把第k段决策变量的允许取值范围称为第k 段允许决策集合，记为Xk(Yk)，于是xk(Yk)Xk(Yk).,19,4）状态转移方程,能否成功地应用动态规划方法，重要条件之一，就是所设状态变量和决策变量必须满足：Yk和Xk，的取值一经确定，则下一段状态变量Yk+1的取值规律也能随之确定，就是说，Yk+1与Yk和Xk之间必须能够建立一种明确的数量对应关系。在动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k段的状态Yk，则第k+1段的状态Yk+1由公式：Yk+1=Tk（YK，Xk+1）确定 这种明确的数量关系称为状态转移方程。,20,5）策略(policy),在多阶段决策

13、过程中，每一阶段均有一个决策，依序组合成一个全过程的决策序列，称为全过程策略，简称策略，记为p1(y1)，有：p1(y1)=x1(y1)，x2(y2)，,xn(yn)，简记p1=x1，x2，,xn 从过程的某个阶段开始到最终阶段结束称为后部子过程。从第k阶段开始的后部子策略称为第k子过程策略。pk(yk)=xk(yk)，xk+1(yk+1),，xn(yn)，简记pk=xk，xk+1，,xn每一阶段有若干状态，每个状态又有若干个不同的决策，即有许多策略可供选择。全体策略构成允许策略集合Pk(yk)。能使预期目标达到最优效果的策略称为最优策略P*k，构成最优策略的各决策称为相应阶段的最优决策x*k

14、。,21,6）指标函数,指标函数有阶段的指标函数和过程的指标函数之分。阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策效果的优劣的数量指标，称为阶段指标函数Vk，阶段指标是状态变量和相应决策变量的函数，即 Vk=Vk(Yk,xk)。过程的指标函数是指从第k阶段的状态Yk出发到最后阶段结束，各阶段绩效综合起来反映这个后部子过程的绩效，称为过程指标函数，记为Vk,n。Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。即 Vk,n=Vk,n(yk，xk,yk+1，xk+1,yn),22,根据实际问题的性质，指标函数Vk,n 可以是各个阶段指标的和或积。最优指数函数是指对从状态yk

15、出发某一确定状态选取最优策略后得到的指标函数值，是对应某一最优子策略的某种效益度量。（这个度量值可以是产量、成本、距离等）。对应于从状态Yk 出发的最优子策略的效益值记作fk(Yk),于是有 fk(Yk)=optVk,n=opt vk(yk,xk)+fk+1(yk+1)其中，opt 表示最优化，根据具体含义 可以求最大（max）或求最小（min）。,23,三、动态规划算法的基本步骤,设计一个标准的动态规划算法,通常可按以下几个步骤进行：1划分阶段：按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性)，否则问题就无法用动态规划求解。2选择状态

16、：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。,24,3确定决策并写出状态转移方程：之所以把这两步放在一起，因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。4写出规划方程(包括边界条件)，动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。,25,动态规划方法的基本思路总结如下,将多阶段决策过程划分阶段，恰当地选取

17、状态变量、决策变量，定义最优指标函数，从而把问题化成一簇同类型的子问题，然后逐个求解。求解时从边界条件开始，逆过程方向行进，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。,26,任务二：最短路径问题,动态规划是将最初的问题分解为许多更容易解决的子问题。在【例题4.2】图4-1中的最短路问题中，我们把要建立的这些子问题定义为一个4阶段的动态规划问题。在解决这个问题之前，我们先给出一条重要的原理贝尔曼最优化原理。,27,任务1：最短路径问题,若某一点在最优路径上，那么从这一点到终点的最短路径也在最优路径上。解决最短路径问题

18、的动态规划方法主要是将每一个节点看成是在最优路径上，然后做出相应的计算。,28,一、贝尔曼最优化原理,一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，今后诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。这个原理是动态规划的理论基础。应用动态规划思想方法解决一般多阶段决策问题时，其求解过程如下：把实际问题适当地划分成n 个阶段，阶段变量为k(k=1,2,n)；在每个阶段k 确定状态变量Sk及此阶段可能的状态集合Sk；,29,30,二、最短路径问题的基本算法,【例4.2】各城市间的交通线及距离如下图4-1所示，某物流公司进行货物配送要从城市1 到城市10

19、，问应选择什么路线，可使运输成本最低？,31,应用逆序递推算法图解,解：这是一个典型的多阶段决策问题，由于所选运货路线会有若干个不同选法，配送运输成本就不同，这就将物流求运输成本问题转化为求最短路径问题。第一种求解方法：穷举法 从城市1 到城市10共有 C31 C31 C21 C11=18条不同路径；每条路径做3次加法，要求出最短路线需要作54次加法，17次比较运算，当问题的段数很多，各段的状态也很多时，这种方法的计算量会大大增加，甚至使得求优成为不可能。,32,第二种求解方法：逆序递推算法,这种方法是从过程的最后一段开始，用逆序递推算方法求解。逐步求出各段各点到终点城市10的最短路线，最后求

20、得城市1到城市10的最短路线。用d（Yk，uk）表示由状态Yk点出发，采用决策uk到达下一阶段Yk+1点时的两点距离。本案例从城市1到城市10 共分4个状态。,33,逆序递推算法,第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有两条路线，取其中最短的即：,则由城市5到终点10最短距离为7，路径为：5810，相应决策为 u*3(5)=8。,34,则由城市6到终点10最短距离为5，路径为：6910，相应决策为u*3(6)=9

21、。,则由城市7到终点10最短距离为5，路径为：7810，相应决策为u*3(7)=8。,35,第3步，k=2，是具有三个初始状态2，3，4，要经过两个中途站才能到达终点的三级决策问题。由于第3段各点5，6，7，到终点10的最段距离f3（5），f3（6），f3（7）已知，所以，若求城市2到10的最短距离，只需以此为基础，分别加上城市2与5，6，7的一段距离，取其短者即可。,则由城市2到终点10最短距离为6，路径为：26910，相应决策为u*2(2)=6。,36,同理有,相应决策为：u*2(3)=7。,相应决策为：u*2(4)=6。,37,第4步，k=1，只有一个状态点1，则,则由城市1到终点10最

22、短距离为17，决策为u*1(1)=2。,再按计算顺序反推可得最优决策序列 uk，即u*1(1)=2，u*2(2)=6，u*3(6)=9，u*4(9)=10 货物运输最优路线为：城市1城市2 城市6 城市9城市10。,38,第三种求解方法：WINQSB 软件求解法,第一步：打开“动态规划-DP.EXE”软件界面，点击(Stagecoach,最短路径）输入标题，城市数目，如下图。,39,第二步：输入城市之间的距离数，如下图。,40,第三步：点击 Solve and Analyze，如下图。,41,三、定价问题,【例4.3】某厂要确定一种新产品在今后五年内的价格，并已拟定只在5，6，7，8元这四种单

23、价中进行选择。据预测，今后五年不同价格下每年盈利（万元）如表1所示，但是各相邻年度价格增减不得超过1元。问今后五年内每年定价各为多少，可预期五年总利润最大？,42,解：用标号法求解，逆序递推,（1）求最长路线，最后结果如图。,43,求解过程：,（1）定价问题是求最长路线问题，因而函数基本方程为取最大值而非最小值；（2）最短路线问题，始点和终点均为固定，而定价问题则始点和终点均不固定，因此最后在始端还要再决策一次。由,确定第一年定价为8元，从而最优定价策略为：,45,结论：,即：前两年定价为8元，以后逐年降低1元，这样能使今后五年预期盈利最大，为38万元；最短路线问题每个点到下面相邻几个点的距离

24、一般不等；定价问题则均相等（即某年、某价格下的预计盈利额）；这里的定价问题实际上是一种特殊的最优路线问题。,46,【例4.3】,某厂估计某一种新产品未来四年内每年在不同价格下的期望利润（万元)如下表所示。如果相邻两年间价格调整幅度：（1）不超过2元；（2）不超过4元；（3）无任何限制；试就这三种情况分别确定各年最优定价？,47,表2,48,解：（1）不超过2元的最优定价策略,最优定价策略为：,49,解：（2）不超过4元,最优定价策略为：,50,解：（3）无任何限制,最优定价策略为：,51,四、动态规划的要点,动态规划提供了一种优秀的决策思想：战略上追求全局优化，战术上稳扎稳打、步步为营。深刻地

25、揭示了局部与全局的统一关系。动态规划在实际中得到广泛应用，如何应用于背包问题，资源分配问题、生产与存储问题、设备更新问题等。另外，需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同的问题模型各异，需要具体问题，具体分析求解。,52,任务三：旅游背包问题,旅游背包问题在物流方面表现为货物配装问题，如储运仓库（或货运车站）整装零担车内装有多种货物，要把各个客户所需要的零担货物组成整车，通过铁路运往各地，货车装载能力一定，如何配装实现价值最大化。,53,一、旅游背包问题数学模型,背包问题用动态规划方法求解只有一个约束条件（一维背包问题）的整数规划最优解，即背包只有重量或体积限制

26、。设数学模型为：,S.t.,55,二、背包问题逆序法求解,【例4-3】假设有4种货物A、B、C、D，其中A有2件，每件重6t，B有1件，每件重20t，C有3件，每件重11t，D有2件，每件19t，如表4-3所示。货车车厢的载重量上限为50t。如何配装，才能充分利用车辆的装载能力。,表4-3 四种货物资料,56,解：,1、阶段的划分和计算 货物配装可以设定：装入一种货物看做一个阶段，把货物配装问题化为动态规划问题。本例题4种货物配装过程划分为四个阶段。采用逆推法，第1阶段分析装入货物D的数量。把货物D的件数折算成重量，用G1表示，共2件，每件重量为19t。,57,第1阶段的状态有三种：0、19和

27、38。输入状态为车辆可能的载重能力，此时状态为W=50。对于3种决策：G1=0、19、38，有3个余量：W-G1=50、31、12。见表4-4。本阶段的余量将作为第2阶段的“输入状态”。,表4-4 第1阶段计算表,58,第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阶段计算表,59,第2阶段的余量作为第3阶段的输入状态，继续分析，结果见表4-6。,表4-6 第3

28、阶段计算表,60,第4阶段决策，见表4-7,61,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，达到满载，充分利用了货车的装载能力,62,另外，在第3阶段计算表中，也出现了一个余量为0的项，对应的G3=20，W

29、=20；再查第2阶段计算表，余量为20，对应的G2=11，W=31；再查第1阶段计算表，余项31，对应G1=19。这样，也得出另一组最优解为 G3=20 G2=11 G1=19对于两组最优解，可根据实际情况进行选择，例如可以优先选用第一组最优解，因为它使A，D两种货物全部配装。,63,三、背包问题计算机软件求解方法,【例5】已知1吨集装箱最大载重量800kg，有5种物品各10件，单位物品重量和价值见表4-8，求如何装载价值最大？,表4-8 单位物品重量和价值,64,用WinQSB软件求解步骤如下：调用子程序DP，新建问题。在图4-3中选择第二项，输入标题和物品数。,65,输入数据。按照表4-9

30、的形式输入数据，第1列为物品名称，第2列为物品限量和集装箱限量，第3列为单位物品重量，第4列为物品价值函数。,66,求解。点击菜单栏 Solve and Analyze Solve the Problem，得到表4-10的结果。,由表4-10可以看出，表示5种物品分别装载10、9、4、0及10件，总价值1365（元），集装箱还有5kg的剩余能力。,67,任务四：生产与存储问题,企业一年中的产品生产往往是分期分批生产的。企业组织每批产品的生产，都要花费一些生产准备费和存贮费用。若某一时期增大生产批量则可减少生产批次，从而降低生产成本。与此同时，批量大了，必然增加库存而使存贮费用增加。在企业产品的

31、生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题，也是物流中的生产与存储问题。,68,一、生产与存储问题数学模型,70,二、生产与存储问题动态规划的数学模型,71,三、生产与存储问题逆序法求解,例6 某工厂与用户签订了4个月的交货合同如表所示,该厂生产能力为每月5万件，该厂仓库的存货能力为4万件。已知生产费用为c=1千元/万件，在进行生产的月份，工厂要支出固定费用b=2千元，每月仓库保管费用h=0.2千元/万件/月。假定开始时及4月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？,72,动

32、态规划的数学模型,每个月为一个阶段，即阶段变量 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 开始到最后阶段采用

33、最优生产策略实现的最低生产费用;,73,逆序求解 K=4,d4=2，4月末无库存则y5=0，状态转移方程 y5=y4+x4 d4，则 y4=d4 x4=2 x4x40,则y4=2 x4=0,1,2y40,则x4=2 y4=0,1,2,74,d3=3，0y4 2，状态转移方程 y4=y3+x3 d3，则 0 y3+x3 d3 2，即 3 y3+x4 50y34，则y3=0,1,2,3,4生产能力限制 0 x3 5，则x3=0,1,2,3,4,5,4月在库存量为s4下的最低生产成本,k=3,75,k=2,d2=2，0y3 4，状态转移方程 y3=y2+x2 d2，则 0 y2+x2 d2 4，即

34、2 y2+x2 6y1=0，则 y2=y1+x1 d1=x1 3；x1 5，则y2 2生产能力限制 0 x2 5，则 x2=0,1,2,3,4,5,3月在库存量为y3下的最低生产成本,76,k=1,2月在库存量为y2下的最低生产成本,0,14.8,5,d1=3，y1=0，状态转移方程则y2=y1+x1 d1=x1 3；y20，则 x1 3，生产能力限制 x1 5，则3 x1 5，x1=3,4,5,77,顺序递推，得出结论,第1月生产5万件y2=y1+x1 d1=0+5-3=2，第2月不生产y3=y2+x2 d2=2+0-2=0，第3月生产5万件y4=y3+x3 d3=0+5-3=2，第4月不生

35、产,78,用运筹学软件求解,第一步：,79,第二步：,80,第三步：,81,第四步：,82,第五步：,83,生产与存储问题计算机求解方法,【例7】：一个工厂生产某种产品，16月份生产成本和产量需求量的变化情况如表4-16所示。每批生产准备成本为=3000元，月底交货。分别求下列两种情形6个月总成本最小的生产方案。1)1月底存储量为零，仓库容量为=50件，不允许缺货及生产能力无限制。2)1月初存储量有20件产品，仓储容量为=40件，不允许缺货，生产能力见表4-16。,84,表4-16 生产与存储成本控制问题数据,85,第 1问求解:,调用子程序DP，新建问题。在图4-4中选择第三项，输入标题和月

36、数。,86,输入数据。按照表4-16的形式输入数据到表4-17中。表 4-17 生产成本与产品需求量变化的数据,表4-17中 第1列为月份数；第2列为各期的需求量；第3列为各期的生产能力，第 问生产能力无限制，输入；第4 列为存储容量限制=50；第5 列为生产时的固定成本；第6列为变动成本函数，是产量、是存量、是缺货量。,87,求解。点击菜单栏 Solve and Analyze Solve the Problem，得到表4-18的结果。,由表4-18的结果得：最优生产策略是第 1、3、5月份分别生产50、75、70件，总成本为12381元。,88,第2问求解:,在表4-17中，最后一行初始存

37、储量(Initial Inventory)改为“20”，修改第3列为各期的生产能力，修改第4 列为存储容量限制=40，如表4-19所示。,表 4-19 成本与产品需求量变化的数据,求解。点击菜单栏 Solve and Analyze Solve the Problem，得到表4-20果。,表4-20生产与存储安排方案,由表4-20果得：最优生产策略是第 2、3、4、6月份分别生产50、50、35及40件，总成本为 14831.5元。如果要求第6个月末存储量为10，则将第6个月的需求量加10即可。,90,动态规划小结,建模步骤 对问题进行阶段划分，确定阶段变量k确定状态变量yk确定决策变量xk、允许决策集合Xk(yk)写出状态转移方程yk+1=Tk(yk,xk)写出指标函数的基本递推方程明确边界条件,91,动态规划解题思路：,阶段1,阶段2,阶段k,阶段k+1,阶段n,状态S1,决策x1,状态S2,v1,决策x2,状态S3,v2,决策xk,状态Sk+1,vk,决策xk+1,vk+1,决策xn,vn,寻求最优解的方向,92,谢 谢,