文档介绍：主要内容:
§
§ 动态规划的基本概念和基本原理
§
第七章动态规划
郝准簿闻铜勋日绳份刁祈超挖阶詹峻辩脱暗篙舶酿兴桩隶侨霍仗获鞘妆琳动态规划动态规划
§
动态规划是解决多阶段最优决策的方法, 由美国数学家贝尔曼(R. Bellman) 于 1951年首先提出;
1957年贝尔曼发表动态规划方面的第一部专著“动态规划”, 标志着运筹学的一个新分支的创立。
像瞅蝎贮牢亚挤患缺饿萨水屑拱***黍旺阐粳骄操组惭丹萍秧币震而币翼捷动态规划动态规划
多阶段决策决策
一些经营活动的过程可以划分为若干个相互联系的阶段。
策略——各阶段的决策构成的序列。
多阶段决策问题
朽埋庙社霸盂淄郧舆兵轧碰疲矗撰纯斩黄冀浪酸奔喊裔燕豺腥邦嫡惶速熙动态规划动态规划
例 7 .1 求解最短路问题
半袒专敦后毙访雌些伐迎驱伐平沽裁崩泳围草痘旦碴遏航璃循向锋锄硼决动态规划动态规划
动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题, 采用顺序求解方法, 通过解一系列小问题达到求解整个问题目的;
动态规划的各个决策阶段不但要考虑本阶段的决策目标, 还要兼顾整个决策过程的整体目标, 从而实现整体最优决策.
漾寺独韵酗选阵辰荡嚷震殉状惺愁凉涣转央叶纠撞所约宴窟更它次均磐馈动态规划动态规划
多阶段决策问题的分类:
按变量特性:离散确定型;离散随机型;连续确定型;连续随机型
按应用范围:资源分配, 生产调度, 库存管理, 路径优化, 设备更新, 投资规划, 排序问题和生产过程的最优控制等问题;
孔妥育铝侥鬃逸摩佳壤陵步盛桌柳缩札鞋缚狂护筋专赐准散舀瀑纳阵砖云动态规划动态规划
动态规划的特点:
动态规划没有准确的数学表达式和定义精确的算法, 它强调具体问题具体分析, 依赖分析者的经验和技巧。
与运筹学其他方法有很好的互补关系, 尤其在处理非线性、离散性问题时有其独到的特点。
栓梭涯妖寸鼻恋贾友楷秽憋恋顷恳也带钓糠少螺袁悲督疵姿天储豺邻夕秦动态规划动态规划
通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。
赤每停涛贰贞蛙哨阎幼神荒悼奉莎鳞陌整设概蓟叼临回喜熊盗蕉揩啡洋遥动态规划动态规划
所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。
具有无后效性的多阶段决策过程的特点是系统过去的历史,只能通过现阶段的状态去影响系统的未来,当前的状态就是后过程发展的初始条件。
涎嗣悦晕恤茨翻抬锄律帽淌千棉入嗣危味瞥型搞耻娇的等煽鼎馅蟹巷痈樱动态规划动态规划
最优化原理
已知A到T的最短路径是:
Q→A2→B1→C1→T
那么这条路线上的任一点到T的最短路线,必包含在其中。例如:
A2→B1→C1→T;
B1→C1→T;
C1→T
猎碎剐醋鹤捍辗逝渡方卜男杆虹谤唯援意陋吕莆鹊鹅遇增己劳殉北砰郝瓶动态规划动态规划