网络优化 模型与算法 Network Optimization: Models algorithms 2004年7月~8月--江西庐山 清华大学数学科学系谢金星 Email:xie(@math.tsinghua.edu.cn http://faculty.mathtsinghua.edu.cn/jxie
1 网 络 优 化 模 型 与 算 法 Network Optimization: Models & Algorithms 清华大学数学科学系 谢金星 Email:jxie@math.tsinghua.edu.cn http://faculty.math.tsinghua.edu.cn/~jxie 2004年7月~8月 ---- 江西 庐山
Outline What is Network Optimization? Typical Models algorithms Minimum Spanning Tree(最小(生成树) Minimum arborescence(最小树形图) Shortest path (最短路) Maximum flow (最大流) Minimum Cost flow(最小费用流) Matching (匹配 Some Modeling examples
2 Outline • What is Network Optimization? • Typical Models & Algorithms – Minimum Spanning Tree (最小(生成)树) – Minimum Arborescence (最小树形图) – Shortest Path (最短路) – Maximum Flow (最大流) – Minimum Cost Flow (最小费用流) – Matching (匹配) – …… • Some Modeling Examples
网络优化简介 网络:网络社会—-计算机信息网络? 电话通信网络 运输服务网络 能源和物质分派网络人际关系网络等等 网络优化就是研究如何有效地计划、管理和控制 网络系统,使之发挥最大的社会和经济效益
3 网 络 优 化 简 介 • 网络：网络社会 ---- 计算机信息网络？ 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制 网络系统，使之发挥最大的社会和经济效益
网络优化简介 优化( Optimization):从若干可能的方案中寻求某 种意义下的最优方案 网络( Network):数学模型、数学结构--图 网络优化就是研究与(赋权)图有关的最优化问题 与图论有联系,也有区别(侧重点不同) 图论: 网络优化: 图的性质 与(赋权)图有关的优化问题 组合数学 组合优化
4 网 络 优 化 简 介 • 网络(Network)：数学模型、数学结构 ---- 图 • 优化(Optimization) : 从若干可能的方案中寻求某 种意义下的最优方案 • 与图论有联系，也有区别（侧重点不同） • 网络优化就是研究与（赋权）图有关的最优化问题 图论： 图的性质 网络优化： 与（赋权）图有关的优化问题 组合数学 组合优化
Global Opi manon Nondifferentiable Optimizarion nonlinearly constrained Bound Least constrained Sai Liner Network Programming Programmining Stochastic Nonlinear Programming Equations Constrained regt Programming Unconstrained Discrete continnons optimization Optimization Tree http://www-fp.mcsanl.gov/otc/guide/optweb/
5 Optimization Tree http://www -fp.mcs.anl.gov/otc/Guide/OptWeb/