网络优化简介 网络优化模型 网络优化算法及其复杂性 主要参考书: 谢金星、邢文训,《网络优化》,清华大学出版社,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 ➢“直接方式”：总经理直接传达； ➢“接力方式”：总经理只给某些部门经理打电话，而让这 些得到信息的部门经理打电话将信息进一步传达给其他某些 部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？ ✓ 信息传播是有向的，有一个“根”。 ✓ 信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例： 信息传播 最小树形图 – 例