运筹 动态规划05(08.10).ppt

第七章动态规划动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。该方法由美国数学家贝尔曼( )等人在 20世纪 50年代初提出的§ 7-1 多阶段决策问题多阶段决策问题例子: A BC 例 7-1 最短路径问题: 求图 7-1 中从 P到Q的最短路径。 63QFE PD 1012 22 74 63 54图 7-1 将问题可分为四个阶段, 第一阶段:从 P到A或 D; 第二阶段:从 A或D到B或 E; 第三阶段:从 B或E到C或 F; 第四阶段:从 C或F到Q。每个阶段都要作出一个决策, 决定向哪个点前进一步。各阶段的决策有机的联系着, 本阶段的决策影响着下一阶段的决策,以至于影响整体效果,决策者在做决策时,不应尽考虑本阶段最优,还应考虑对最终目标的影响。各阶段的决策形成一个决策序列,通常称之为一个策略,不同的策略,其效果也不同。现在的问题就是要在允许的策略中,求出 P到Q的距离最短的策略。例 7-2 机器负荷分配问题: 某种机器能在高低两种不同的负荷下工作,在高负荷下有台机器进行生产时,产品的产量,工作一年后完好的机器数为,在低负荷下有台机器进行生产时,产品的产量,工作一年后完好的机器数为。试制订一个五年计划,决定在每年年初如何分配完好的机器在两种不同负荷下生产的数量, 才能使在五年内产品的产量为最高? uus8? v vs5? 可将该问题按年划分为五个阶段:第一阶段即第一年; 第二阶段即第二年;第三阶段即第三年;第四阶段即第四年;第五阶段即第五年。设开始时完好机器数量为,第年能投入生产的机器数为,第年高负荷下工作的机器数为台,效益为,则。 1x k kx k ku kR kkkkkkkkkk xuuxuRuxxx ?????????0,)(58 ),( 1原问题就是确定, k=1,2,3,4,5, 使最大。 ku?? 51k kR 例 7-3 部件的生产计划问题: 某车间每月底要为下一个月提供出一定数量的部件给组装车间,各月份中生产这种部件所需工时不同,生产出来多余的部件可以存入库中,但库房的最高贮量为 H=9 , 求某 6 个月中每月生产多少部件,才能使消耗的总工时最少?最小工时是多少?各月的需求量与单位工时如下表: kd月份 123456 需求量 853274 单位工时 1********** ka k将该问题按月份划分为六个阶段, 为第月开始时的库存, 为第月的生产量。 ksk kuk 图7-2 Kkkkdus??? ks设为当第月开始时库为直至第 6 月止,生产部件累计工时的最小值,则。即为要求的最小工时。)( kksfk ks) ()( min )( 11???? kkkku kksfuasf k)( 11sf 例 7-4 原料分配问题: 利用已有的 12 吨原料制造 A,B 两种产品,已知每制造一吨 A 产品需要原料 4 吨,每制造一吨B 产品需要原料 2 吨,而两种产品在市场上的价格分别为每吨 8 千元和 1 万元,求如何安排生产计划能使总效益最大? 可将分配 A,B 两产品的产量看作两个阶段:第一阶段:确定生产 A 产品多少吨;第二阶段:确定生产 B 产品多少吨。求出使总效益最大的决策序列。例 7-5 人员派谴问题: 向三个售货员派谴四名推销员, 各区人数及效益如下表: 人数区域增加效益数 01234 123 000 161610 251714 302116 322217 问如何派谴人员能使总效益最高? 该问题可按区域分为三个阶段:第一阶段:确定向 1区派几名推销员;第二阶段:确定向 2区派几名推销员;第三阶段:确定向 3区派几名推销员。求出使总效益最大的策略。例 7-6 货物装载问题: 某海轮的总装载能力为千吨(不妨设千吨)需装载四种货物,规定海轮上每种货物不超过 2 件,各种货物的单位重量,单位运费如下表,问怎样装这些货物,才能使总运费最大? w 18 ,,1,0??w表 7-3 货物种类单位重量每件运费 1234 5134 9147 将该问题按四种货物分为四个阶段,第 k 阶段确定第 k 种货物的装运件数。设为第种货物的运费。求出使最大的装运策略。 kRk?? 41k kR §2 动态规划的基本概念与基本原理 动态规划的基本概念 ( Stage ) 将问题恰当地划分成若干相互联系的阶段,通常用作为阶段变量。 ( State Variable ) 描述过程状态的变量,可以用一个数,一组数或一个向量来描述,常用、表示第阶段的状态变量。 k kx k ks