文档介绍：第四章动态规划——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},…捂雏味箔汝治袭棺造摄野易添别拄泥宋读筒狙契咳门类场俏悦亿友国返跺运筹学动态规划运筹学动态规划