清华大学：网络优化模型与算法（PPT讲稿）Network Optimization - Models & Algorithms（数学科学系：谢金星）

网络优化 模型与算法 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/

网络优化简介 网络优化模型 网络优化算法及其复杂性 主要参考书: 谢金星、邢文训,《网络优化》,清华大学出版社,2000 年8月;2003年9月。 Ahuja.R.K. Magnanti T L. Orlin J.B. Network Flows Theory, Algorithms, and Applications. Prentice Hall, 1993 Englewood Clifts, New Jersey 《网络优化》或《网络流》( Network Flows) 或《网络规划》( Network Programming)

6 网 络 优 化 简 介 主要参考书： • 谢金星 、邢文训，《网络优化》，清华大学出版社，2000 年8月；2003年9月。 • Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993: Englewood Cliffs, New Jersey. 网络优化模型 网络优化算法及其复杂性 《网络优化》或《网络流》（Network Flows) 或《网络规划》（Network Programming)

图上 与网络-基本概念 4 图G=(V,A),其中顶点集V{v12V23,4,v5} 弧集A={a12a2,a32a4,a3,a6} 弧a1 (V2,v3)

7 图与网络 – 基本概念 5 a 1 a 1 v 2 v 3 a 3 v 4 a 4 v 5 v 2 a 6 a 图G=(V，A)，其中顶点集V= 弧集A= 弧 { , , , , } 1 2 3 4 5 v v v v v { , , , , , } a1 a2 a3 a4 a5 a6 ( , ) 1 1 2 a = v v ( , ) 2 1 2 a = v v ( , ) 3 2 3 a = v v ( , ) 4 3 4 a = v v ( , ) 5 4 1 a = v v ( , ) 6 3 3 a = v v

网络优化问题的例子 例:公路连接问题 某一地区有若干个主要城市,现准备修建高速公路 把这些城市连接起来,使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市假 定已经知道了任意两个城市之间修建高速公路的成 本,那么应如何决定在哪些城市间修建高速公路, 使得总成本最小? 最小(生成树 4 也称为 最小(支撑)树 2

8 例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路 把这些城市连接起来， 使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市. 假 定已经知道了任意两个城市之间修建高速公路的成 本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？ 网络优化问题的例子 1 1 3 2 4 5 6 3 8 5 2 4 7 最小(生成)树 也称为 最小(支撑)树

网络优化问题的例子 例:二维矩阵数据存贮问题 某些蛋白质的氨基酸序列差异不多,如果用二维矩阵 的每一行记录一种蛋白质氨基酸序列,行与行之间的 差异很小.其中一种方法是只存贮其中一行作为参照行, 再存贮行与行之间的一部分差异信息,使得我们可以 在需要时根据参照行生成所有其它行的元素 RI 最 12 24 树 R3 R2 R4

9 例： 二维矩阵数据存贮问题 某些蛋白质的氨基酸序列差异不多，如果用二维矩阵 的每一行记录一种蛋白质氨基酸序列，行与行之间的 差异很小. 其中一种方法是只存贮其中一行作为参照行， 再存贮行与行之间的一部分差异信息，使得我们可以 在需要时根据参照行生成所有其它行的元素. R1 R3 R2 R4 C13 C12 C24 最 小 树 网络优化问题的例子

最小树形图 例 例:信息传播 “直接方式”:总经理直接传达; “接力方式”:总经理只给某些部门经理打电话,而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理,依此类推,最后将信息传达到所有部门经理 如何决定传达信息的途径? √信息传播是有向的,有一个“根”。 √信息传播途径(忽略方向时)是一棵树。 以上结构称为树形图,上面这样一类问题称为最小树形图问题

10 ➢“直接方式”：总经理直接传达； ➢“接力方式”：总经理只给某些部门经理打电话，而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？ ✓ 信息传播是有向的，有一个“根”。 ✓ 信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例： 信息传播 最小树形图 – 例