经济学动态规划.pptx

教学要求：教学要求：了解了解动态规划的基本思想掌握掌握一维离散动态规划的建模和求解方法应用会运用动态规划方法解决一些基本应用问题。第一节动态规划原理和模型第一节动态规划原理和模型 在生产和经营活动中，经常遇到这样的问题，它们包含若干个相互联系的阶段，而且，在每一阶段都要做出决策，一个阶段的决策除影响该阶段本身的效果之外，还影响到下一阶段的起始状态，从而影响到整个过程的效果最优 因此不但要考虑这一阶段，还要把它看成是整个过程决策链中的一个链环，这种过程称为多阶段决策过程，如企业在生产过程中，由于需求是随时间变化的，因此为了获得全年的最佳效益，就要逐月或逐季度地根据库存和需求决定生产计划。动态规则是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子(单）决策问题。而每一个子决策问题都有多种选择 当一个子决策问题确定以后，将影响另一个子决策问题 从而影响到整个问题的决策第一节动态规划原理和模型第一节动态规划原理和模型例例1、最小费用问题：、最小费用问题：某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如下图所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段4311344461697812553第一节动态规划原理和模型第一节动态规划原理和模型一、动态规则的实例例例2、机器负荷分配问题、机器负荷分配问题：年初完好机器数为u台，其中有u1台用于高负荷生产，产品的年产量为s1=g(u1)，年终完好机器数为au1(a称完好率,0a1)，另外有u2台机器用于低负荷生产，产品的年产量为s2=g(u2)，年终完好机器数为bu2(0b0时，c(x)=3+2x。每月最多生产4个单位，每月的需求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用 划分阶段划分阶段 将三个月分为三个阶段，每个月为一个阶段 状态变量状态变量 sk表示第k个月初的库存数 决策变量决策变量 xk表示第k月生产的单位数 建立状态转移方程建立状态转移方程 ，其中 为一随机需求量或为1或为2 最优指标函数最优指标函数 fk(sk)表示第k个月初的库存是时，第k个月至第3个月内的最小期望费用。第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用设备更新问题设备更新问题在企业中，经常遇到设备陈旧或部分损坏需要更新的问题。从经济上分析，一种设备应该使用多少年后进行更新最合算。这就是要研究的问题。一般来说，一台新设备出故障少，维护费用低，带来的经济效益就高；随着使用年限的增加，新设备逐渐变旧，维护费用增加，效用降低。在适当的时候，就要卖掉旧设备，购买新设备。当然，设备越旧越不值钱，购买新设备又需要一定数额的购买费，这就是设备的更新决策问题。现有一台效益函数为r(t)的设备，其维修费用为u(t)，更新费用为c(t)，需要在n 年内的每年年初做出决策，是继续使用旧设备还是更新一台新设备，使n年总效益最大？第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用l rk(t)：在第k年设备已使用过t年，再使用1年的效益l uk(t)：在第k年设备已使用过t年，再使用1年的维修费用l ck(t)：在第k年卖掉一台已使用过t年的设备，买进一台新设备的更新费用l a：折扣因子，表示一年以后的单位收入价值相当于现在的a单位l fk(t)：已使用了t年的旧设备，从第k年开始在以后继续使用到规定的第n年未知几年内的总回收额第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用 划分阶段划分阶段 k表示计划使用该设备的年限数 状态变量状态变量 sk表示第k年初，设备已使用过的年数 决策变量决策变量 xk表示第k年初更新，还是继续使用旧设备，分别用R和K表示。建立状态转移方程建立状态转移方程 动态规划的基本方程动态规划的基本方程第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用p资源分配问题资源分配问题p将一种或多种有限的资源，分配给若干个使用者，而使目标达到最优p设有一原料，总量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其产生的效益为ri(xi)。问如何分配，才能使生产n种产品的总收入最大？。第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用 划分阶段划分阶段 将n种产品按1,2,n的序号排列,每种产品为一个阶段,分为n个阶段,k=1,2,n.状态变量状态变量 sk表示分配给第k个产品至第n 种产品的资源数。决策变量决策变量 xk表示分配给第k个产品的资源数。建立状态转移方程建立状态转移方程 sk+1=sk-xk 最优指标函数最优指标函数 fk(sk)表示在拥有资源sk，分配给第k种产品至第n 种产品所得到的最大总收入。基本方程基本方程 确定边界条件确定边界条件 因为在第1阶段时的资源为总资源，到第n+1阶段时资源已分配完毕，所以 so=a，sn+1=0,fn+1(sn+1)=0.第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用p复合系统可靠性问题复合系统可靠性问题p若某种机器的工作系统有N个部件组成，只要有一个部件失灵，整个系统就不能正常工作。这些部件的正常工作关系为串接关系，为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并且设计了备用件自动投入装置。显然，备用元件越多，整个系统正常工作的可靠性越大。但备用元件多了，整个系统的成本、重量、体积均相应加大，工作精度也降低。因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使整个系统的工作可靠性最大？第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用设部件i上装有zi个备用元件时，它正常工作的概率是pi(zi)。因此，整个系统正常工作的可靠性，可以用它的正常工作的概率来衡量。即设部件i的一个备用元件的费用为ci，重量为wi，要求整个系统所装备用元件的总费用不超过C，总重量不超过W第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用 Xk表示由第k个到第n个部件所容许使用的总费用 Yk表示由第k个到第n个部件所容许使用的总重量 Xk+1=xk-zkck Yk+1=yk-zkwk 允许决策集合 动态规划基本方程第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用例例4。排序问题。排序问题：有5个零件需要在A、B两台机床上加工，每个零件都必须经过先A后B的加工顺序，加工时间如下表，问应如何安排加工顺序，使总的加工时间最少？零件号机床A机床B136272347453574第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用两台机器的最优排序规则：(1)找出a1,a2,an,b1,b2,bn中最小值(2)若最小者为ai，则工件i应排在第一位，并从工件集中去掉ai(3)若最小者为bi，则工件i 应排在最后一位，将工件i从工件集中去掉(4)对余下的工件重复上述操作，直到工件集为空为止第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用零件号 机床A机床B136272347453574排序前：t=3+6=9(1)t=9+1=10t=10+2=12(2)t=12+2=14t=14+5=19(2)(5)t=19+2=21t=21+3=24(2)t=24+2+4=30第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用零件号 机床A机床B136347574453272排序后：t=3+4=7t=7+2=9t=9+5=14t=14+2=16t=16+3=19(6)t=19+1=20t=20+3=23t=23+3+2=28(2)(5)(2)(3)(1)(3)第三节动态规划在经济和管理中的应用第三节动态规划在经济和管理中的应用