- 1、本文档共52页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
CAN-File-15-04-02-07-emp_lp_extension_2015_spring
割及割的容量 s-t 割(cut): 割集(cut set): 最大流-最小割定理(Max-Flow Min-Cut Theorem) 在任一网络中,最大流的流量等于最小割的容量. 由Ford与Fulkerson于1956年提出来的,是图论和网络流中的最重要结论之一! 有向图中去掉割集,则不存在从 s 到 t 的有向路;无向图中去掉割集,则不存在从 s 到 t 的路(即s 与 t 不连通) 前向弧集合 前向弧的容量之和,即 割的容量(capacity): 最大流-最小割定理的证明 流平衡方程: 设 是最大流问题的解 设 是对偶问题的解 令 易验证 是一个s – t 割,且 最短路问题(shortest path problem) 给定: 网络: 费用/权重/距离: 根节点(home or root): 问题:确定从 每一个节点出发到根节点的最短路(有向的) 根节点 5: 1→3 →5:5 2→5: 5 3→5: 1 4→3 →5:3 1 4 2 3 5 7 4 5 1 2 5 1 4 最短路的网络流问题表述 令 求解最小费用网络流问题 由最优树弧得到从 i 到 r 的最短路 最短路的长度为 1 4 2 3 5 7 4 5 1 2 5 1 4 动态规划(dynamic programming) Bellman方程、动态规划原理/最优性原理 令 vi = 从节点 i 到根节点 r 的最短时间 在网络文献中称为标号(label); 在动态规划的文献中称为值(value). 以下算法中使用的记号: 最优化原理(最优子结构性质):一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优策略的子策略总是最优的。 标号设置算法(label setting algorithm) Dijkstra算法,1959年,适用于弧的费用非负的问题 记号: Dijkstra算法: -当还有未完成的节点时,选择 vi 最小的节点, 记为 j. 将 j 添加到已完成节点集 - 对每个未完成的节点 i ,且有弧(i, j)将 i 和 j 连接起来: 是已完成的节点集(已经确定了标号的节点集) 是 在 i 之后要访问的节点 初始化: 迭代: 如果 置 原理:每次新扩展一个标号最小的节点,并更新与其相邻的点的距离。 Dijkstra 算法 根节点 5: 1→3 →5:5 2→5: 5 3→5: 1 4→3 →5:3 1 4 2 3 5 7 4 5 1 2 5 1 4 动态规划(dynamic programming) 是运筹学的一个分支,是求解最优决策过程(decision process) 的数学方法。 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优性原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。 1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。 最优控制(optimal control ) 是现代控制理论的核心,它研究的主要问题是:在满足一定约束条件下,寻求最优控制策略,使得性能指标取极大值或极小值 。 方法描述:对一个受控的动力学系统或运动过程,从一类允许的控制方案中找出一个最优的控制方案,使系统的运动在由某个初始状态转移到指定的目标状态的同时,其性能指标值为最优 。 典型例子 确定一个最优控制方式使空间飞行器由一个轨道转换到另一轨道过程中燃料消耗最少。 选择一个温度的调节规律和相应的原料配比使化工反应过程的产量最大。 制定一项最合理的人口政策使人口发展过程中老化指数、抚养指数和劳动力指数等为最优。 最优控制(续) 是 20 世纪 50 年代中期在空间技术的推动下开始形成和发展起来的 。 开创性工作是美国学者贝尔曼1957年提出的动态规划和前苏联学者庞特里亚金1958年提出的极大值原理。 先期工作应该追
文档评论(0)