一章动态规划应用举例.ppt
《一章动态规划应用举例.ppt》由会员分享,可在线阅读,更多相关《一章动态规划应用举例.ppt(34页珍藏版)》请在三一文库上搜索。
1、第6章 动态规划应用举例,第1节 资源分配问题,1.1 一维资源分配问题,资源分配问题可描述如下:设有某种原料,总数量为a,分配给n个使用者。已知第i个使用者得到数量xi的该种资源,可创造的收益为gi(xi)。问应如何分配该资源,才能使总收益最大。,用动态规划法处理这种问题时,通常把给各个使用者分配资源的过程分别看成一个阶段,按使用者分成先后的n个阶段。即先给第1个使用者分配资源,为第一阶段;再给第2个使用者分配,为第二阶段;依此类推,最后给第n个使用者分配,为第n阶段。,按使用者划分为n个阶段,k=1,2,n; 取第k阶段初(给第k个使用者分配资源时)资源的剩余量sk为状态变量,s1=a;
2、取分配给第k个使用者的资源数量xk为决策变量,0xksk (k=1,2,n-1), xn= sn; 状态转移方程为sk+1=sk-xk; 指标函数为Vk,n=gj(xj); 基本方程为:,由于资源数量常常要求取整数,则状态变量和决策变量也就取整数,所以求解时常采用列表的形式。,例2 某工业部门根据国家计划安排,拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂,各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器,才能使各厂的总效益最大。,解:,分成3个阶段,k=1,2,3;,sk为状态变量,s1=5;,xk为决策变量,0xksk,x3=s3;,状态转移方程sk+1= sk-xk
3、;,当k=3时:,当k=2时:,当k=1时:,总效益最大为21万元,分配方案为:,(1)甲0台, 乙2台, 丙3台;(2)甲2台, 乙2台, 丙1台。,1.2 二维资源分配问题,二维资源分配问题可描述如下:设有两种原料,数量各为a和b,分配给n个使用者。已知第i个使用者得到两种资源的数量各为xi和yi时,可创造的收益为gi(xi, yi)。问应如何分配该资源,才能使总收益最大。,与一维资源分配问题类似,把给各个使用者分配资源的过程分别看成一个阶段,按使用者分成先后的n个阶段。由于要分配两种资源,所以状态变量要有两个,决策变量也要有两个。,按使用者划分为n个阶段,k=1,2,n; 取第k阶段初(
4、给第k个使用者分配资源时)两种资源各自的剩余量sk和tk为状态变量, s1=a, t1=b; 取分配给第k个使用者两种资源的数量xk和yk为决策变量,0xksk, 0xksk (k=1,n-1), xn= sn, yn= tn; 状态转移方程为:sk+1=sk-xk,tk+1=tk-yk; 指标函数为Vk,n=gj(xj,yj) ; 基本方程为:,虽然建模过程和一维资源分配问题没多大区别,但求解模型却极为困难。为此,需进行简化处理。,1. 拉格朗日乘数法,引入拉格朗日乘数,将二维问题化为,这是一个一维分配问题。取定为某一值,求解得 xi*=xi() , yi*=yi(xi(), )=yi(),
5、可证,若yi()=b,则对应的xi*, yi*就是原问题的最优解。否则,就用插值法调整的值,渐进地使yi()=b得到满足。,2. 逐次逼近法,逐次逼近法的做法是,先保持一个变量不变,对另一个变量求最优,然后交替地固定,以迭代的形式反复进行,直到满足某种要求为止。,先设x(0)=x1(0), x2(0), xn(0)为满足xi(0)=a的一个可行解,固定x在x(0),对y求解,则变为一维问题,用一维方法解得y(0)=y1(0), y2(0), yn(0),再固定y在y(0),对x求解一维问题,解得x(1)=x1(1), x2(1), xn(1),再固定x在x(1),对y求解一维问题。依次轮换下去
6、,得解序列x(k)、 y(k)。,由于gi(xi(0),yi(0)gi(xi(1),yi(0)gi(xi(1),yi(1),故函数值序列gi(xi(k),yi(k)是单调上升的,但不一定收敛到整体的最优解,一般只能收敛到某一局部最优解。因此,在实际计算时,可选择几个初始点xi(0)进行计算,然后从几个局部最优解中选出一个最好的。,3. 粗格子点法 (疏密法),先将0xa, 0yb分成网格,然后在格子点上进行计算。为了使计算可行,可先用少数格子点进行粗糙计算,在求出相应最优解后,再在最优解附近的小范围内进一步细分,求出在细分格子点上的最优解。继续细分下去,直至满足要求为止。,第2节 生产与存储问
7、题,2.1 生产计划问题,设某公司对某种产品要制定n个阶段的生产计划。已知它的初始库存为0,每阶段生产产品数量的上限为m;第k阶段,对该产品的需求量为dk,生产产品量为xk时的生产费用为ck(xk),开始时有库存量vk需要支付的存储费用为hk(vk);n阶段末的终了库存为0。问该公司应如何制定生产计划,从而使总成本最小。,用动态规划的方法:,状态转移方程为: vk+1= vk+xk-dk,k阶段的产品生产量xk为决策变量,则,k阶段开始时的库存量vk为状态变量, v1=0;,划分为n个决策阶段,k=1,2,.,n;,在求解生产计划问题时,常常需要先给出状态变量vk的取值范围,即确定可达状态集。
8、易推出:,例 某工厂要对一种产品制定今后四个时期的生产计划,据估计四个时期的需求量依次为2、3、2和4。假定该厂生产每批产品的固定成本为3万元,每单位产品的成本为1万元,若不生产就为0;每个时期生产能力的上限为6个单位,每单位产品存放每期的存储费用为0.5万元。还假定第一期开始时和第四期结束时的库存量都为0。试问该厂应如何安排各期的生产与库存,才能在满足需求的条件下,使总成本最小。,状态变量vk的可达状态集:,则有,v1=0,0v24,0v36,0v44。,k=4时:,k=3时:,k=2时:,k=2时:(续),k=1时:,于是得,总成本最小为20.5万元。,x1*=5, x2*=0, x3*=
9、6, x4*=0,再顺序递推出最优计划为:,即:第一个时期生产产品5个单位,第二个时期不安排生产,第三个时期生产产品6个单位,第四个时期不安排生产。,2.2 不确定性采购问题,某单位准备在以后的n个时期内采购一批物资。各时期的价格不是确定的,而是按照某种已知的概率分布取值。试制定采购策略,确定在哪一时期以什么价格采购,能使采购价的数学期望值最低。,这类问题也适合用动态规划法进行处理,下面通过实例加以说明。,例 某厂生产上须在近五周内采购一批原料,而估计在未来五周的价格有波动,其浮动价格和概率策得如下表。试确定该厂应在哪一周以什么价格购入,能使其采购价的数学期望值最小,并求出期望值。,解:,(1
10、)按采购周数分成5个阶段,k=1,2,5;,(2)取第k阶段(第k周)的实际价格yk为状态变量;,(4)用fk(yk)表示:前k-1周未采购,第k周状态为yk时,从第k周到第5周按最优策略所得到的采购价的期望值。即fk(yk)为最优值函数;,(5)用ykE表示:前k-1周未采购,从第k周到第5周按最优策略所得到的总的采购价的期望值。,显然,ykE=Efk (yk)=0.3fk(500)+0.3fk(600)+0.4fk(700),k=5时:,f5(500)=500, f5(600)=600, f5(700)=700 (x5*=1) y5E=0.3*500+0.3*600+0.4*700=610
11、,k=4时:,f4(500)=min500,610=500, (x4*=1), f4(600)=min600,610=600, (x4*=1), f4(700)=min700,610=610, (x4*=0), y4E=0.3*500+0.3*600+0.4*610=574,k=3时:,f3(500)=min500,574=500, (x3*=1), f3(600)=min600,574=574, (x3*=0), f3(700)=min700,574=574, (x3*=0), y3E=0.3*500+0.3*574+0.4*574=551.8,k=2时:,f2(500)=min500,55
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章动 规划 应用 举例
链接地址:https://www.31doc.com/p-2657133.html