数学建模-网-络-优-化.ppt

该【数学建模-网-络-优-化 】是由【utuhlwwue61571】上传分享，文档一共【43】页，该文档可以免费在线阅读，需要了解更多关于【数学建模-网-络-优-化 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。网 络 优 化
模 型 与 算 法
Network Optimization: Models & Algorithms
清华大学数学科学系 谢金星
/~jxie
2004年7月~8月 ---- 江西 庐山
1
What is Network Optimization?
Typical Models & Algorithms
Minimum Spanning Tree (最小(生成)树)
Minimum Arborescence (最小树形图)
Shortest Path (最短路)
Maximum Flow (最大流)
Minimum Cost Flow (最小费用流)
Matching (匹配)
……
Some Modeling Examples
Outline
#2022
2
网 络 优 化 简 介
网络：网络社会 ---- 计算机信息网络？
电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等
网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益
3
图论：
图的性质
组合数学
组合优化
网络(Network)：数学模型、数学结构 ---- 图
优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案
网 络 优 化 简 介
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。
网络优化：
与图论有联系，也有区别（侧重点不同）
网络优化就是研究与（赋权）图有关的最优化问题
与（赋权）图有关的优化问题
4
Optimization Tree
http://www-/
5
网 络 优 化 简 介
谢金星 、邢文训，《网络优化》 ，清华大学出版社，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.
主要参考书：
01
或《网络规划》（Network Programming)
《网络优化》或《网络流》（Network Flows)
02
网络优化模型
网络优化算法及其复杂性
6
图与网络 – 基本概念
图G=(V，A)，其中顶点集V=
弧集A=
弧
7
例： 公路连接问题
某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？
网络优化问题的例子
1
1
3
2
5
4
6
3
8
5
2
4
7
最小(生成)树
也称为
最小(支撑)树
8
例： 二维矩阵数据存贮问题
某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小. 其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.
R1
R3
R2
R4
C13
C12
C24
最小树
网络优化问题的例子
9
“直接方式”：总经理直接传达；
“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.
如何决定传达信息的途径？
信息传播是有向的，有一个“根”。
信息传播途径（忽略方向时）是一棵树。
以上结构称为树形图，上面这样一类问题称为最小树形图问题.
例： 信息传播
最小树形图 – 例
10