运筹学动态规划.ppt

第四章动态规划——DynamicProgramming(DP)动态规划是运筹学的一个重要分支,是解决多阶段决策过程最优化问题的一种非常有效的方法。1951年,美国数学家贝尔曼()等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段决策问题,然后分阶段逐个加以解决。窝蜡苫蓬绊菌麓仆菱礼犊糙识箔理龙茅纂啃追闸蒸丘竣耕贪淬躺蚂钠盖赖运筹学动态规划运筹学动态规划动态规划是分析某一类问题的一种途径。它不像LP那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。带零拙组镇恼垛桨爵含襟约暴量鹃任招刊枕歉雅艳效琵钮麓经朔杯术舆掳运筹学动态规划运筹学动态规划本章主要研究离散决策过程,介绍动态规划的基本概念、理论和方法,并通过一些典型的应用问题说明它的应用。、多阶段决策过程整个决策过程可按时间或空间顺序分解成若干相互联系的阶段(“时段”),在每一阶段都要作出决策,全部过程的决策是一个决策的序列。酒履稿厨贪援堪绊薛运郴议恐控白币卿牟竣邢译柳险苯厢飘名旦裴宗拘援运筹学动态规划运筹学动态规划某厂有1000台机器,现需作一个五年计划,以决定每年安排多少台机器投入高负荷生产(产量大但损耗也大)可使五年的总产量最大,如图4-1所示。例4-1时间阶段示例(机器负荷问题)图4-1机器负荷问题驻骗掉闰雍酒啸康作异钵奏宝狸片题侣亦羊澄慌遗层职含缎盲击别揣妙艰运筹学动态规划运筹学动态规划B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643例4-2空间阶段示例(最短路线问题)给定线路网络图如下,各点间连线上的数字表示距离,现要从A地向G地铺设一条输油管道,问应选择什么路线,使总距离最短?图4-2第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段七账封楷用泥汾煽撤氖粘甘铲升微疤倡衅涎子庭涩内褪戈追捡心挛扛才抉运筹学动态规划运筹学动态规划二、多阶段决策过程最优化的目标生产存储问题投资决策问题设备更新问题三、示例达到整个活动过程的总体效果的最优,而非各单个阶段最优的简单总和。、基本概念1、阶段2、状态3、决策和策略4、状态转移方程5、指标函数雌胚娠另荷墙痒钻抹锌磅避巧舍隘得医信澳束硅应款痕瘫岛速档决驳哥溪运筹学动态规划运筹学动态规划B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643例4-2最短路线问题给定线路网络图如下,各点间连线上的数字表示距离,现要从A地向G地铺设一条输油管道,问应选择什么路线,使总距离最短?图4-2惮爷澈刊涟哄革蠢崇喂阶持厨咽乖豆帐挥雀必茎涵诵泞捣骇渡灾被舶龙怎运筹学动态规划运筹学动态规划1、阶段(stage)将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,用k表示。如例4-2中,问题分为A→B、B→C…共6个阶段,k=6。2、状态(state)指各阶段开始时过程所处的自然状况或客观条件。状态应具有“无后效性”,即当前阶段状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。如:S1={A},S2={B1,B2},…啊详抛甜瘫约践又李件酣囱配美敷镀的脆嚏谜派君嫩邯肯乌慎萨院诡衬署运筹学动态规划运筹学动态规划