《网络优化-谢金星01》由会员分享，可在线阅读，更多相关《网络优化-谢金星01（76页珍藏版）》请在金锄头文库上搜索。
1、网 络 优 化 第 1 章 概 论 （第1讲）Network Optimization清华大学数学科学系 谢金星办公室：理科楼1308# （电话：62787812）Email: http:/ 络 优 化 简 介网络：网络社会 - 计算机信息网络？电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制 网络系统，使之发挥最大的社会和经济效益 2网 络 优 化 简 介 网络：数学模型、数学结构 - 图从若干可能的安排或方案中寻求某种意义下的最优安排或方 案，数学上把这种问题称为（最）优化 (Optimization) 问题 运筹学（Opera
2、tions Research - OR）的一个分支网络优化就是研究与（赋权）图有关的最优化问题研究生专业数学本科专业数学数学 与应用数学信息 与计算科学基础数学应用数学计算数学概率论与数理统计运筹学与控制论3Operations Research and Management Science (OR/MS) The professional disciplines that deal with the application of information technology for informed decision-making Provide rational bases for dec
3、ision making by seeking to understand and structure complex situations and to use this understanding to predict system behavior and improve system performance. Much of this work is done using analytical and numerical techniques to develop and manipulate mathematical and computer models of organizati
4、onal systems composed of people, machines, and procedures. The field is closely related to several other fields in the “decision sciences“ - applied mathematics, computer science, economics, industrial engineering, and systems engineering. From http:/www.informs.org/Join/Orms.html4建 立 OR/MS 理 论 模 型
5、的 一 般 步 骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用Applied Mathematics Mathematical Modeling:Motivation,Formulation,Solution,Validation“源”远“流”长5运筹学（Operations Research - OR）n广义：管理科学/决策科学 (MS/DS)、系统科学/工程 (SS/SE)、工业工程(IE)、运 作管理(OM)n狭义：运筹数学 - 最优化、 对策论、排队论等 连续优化：数学规划（线性规划、非 线性规划）、非光滑优化、全局优化等 离散优化：组合优化、网络优化、整 数规划等 不确定
6、规划：随机规划、模糊规划等OMOR/MS /DSSS/SEIE/EMn网络优化也是计算机科学的入门课程之一6Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/7网 络 优 化 简 介教材：谢金星 、邢文训，网络优化 ，清华大学出版社 ，2000年8月；2003年9月。参考书：Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993: Englewood C
7、liffs, New Jersey. 教学资源： 网络学堂; http:/ - 50%左右 考试 - 50%左右如何学习？认真看书、完成习题(有些习题难度较大)助教: 王振波 内容：网络优化模型、算法及其复杂性对象：数学、计算机科学、管理科学、工程科学等8例1.1 公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些 城市连接起来， 使得从其中任何一个城市都可以经高速公 路直接或间接到达另一个城市. 假定已经知道了任意两个城 市之间修建高速公路的成本，那么应如何决定在哪些城市 间修建高速公路，使得总成本最小？ 1.1网络优化问题的例子 例1.2 最短路问题（SPP-Shortest
8、Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运 往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车 路线，这名司机应选择哪条线路呢？假设货柜车的运行速 度是恒定的，那么这一问题相当于需要找到一条从甲地到 乙地的最短路. 9例1.3 运输问题(Transportation Problem)某种原材料有M个产地，现在需要将原材料从产地运往N个 使用这些原材料的工厂. 假定M个产地的产量和N家工厂的 需要量已知，单位产品从任一产地到任一工厂的的运费已 知，那么如何安排运输方案可以使总运输成本最低？ 1.1网络优化问题的例子 例1.4 指派问题(Assignment
9、Problem)一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时 所获得的回报是不同的. 如何分配工作方案可以使总回 报最 大？ 10例1.5 中国邮递员问题邮递员问题 (CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件. 如何为他(她)设计 一条最短的投递路线(从邮局出发，经过投递区内每条街道 至少一次，最后返回邮局)？由于这一问题是我国复旦大学 管梅谷教授1960年首先提出的，所以国际上称之为中国邮 递员问题. 1.1网络优化问题的例子 例1.6 旅行商问题问题 /货郎（担）问题(TSP-Tr
10、aveling Salesman Problem)一名推销员准备前往若干城市推销产品. 如何为他(她)设 计一条最短的旅行路线(从驻地出发，经过每个城市恰好一 次，最后返回驻地)？这一问题的研究历史十分悠久，通常 称之为旅行商问题. 111.1网络优化问题的例子 例 稳定婚配问题(Stable Marriage Problem)假设有n个男人和n个女人, 每人都希望从n个异性中选择一位 自己的配偶. 假设每人都对n个异性根据自己的偏好进行了排 序, 以此作为选择配偶的基础. 当给定一种婚配方案(即给每人 指定一个配偶)后, 如果存在一个男人和一个女人不是互为配偶 , 但该男人喜欢该女人胜过其配
11、偶, 且该女人喜欢该男人也胜 过其配偶, 则该婚配方案称为不稳定的. 安排稳定的婚配方案 的问题称为稳定婚配问题。121.1网络优化问题的例子 网络优化或网络流（Network Flows)或网络规划（Network Programming)特点： （1）与图形有关，或易于用图 形方式表示（2）优化问题：从若干可能的 安排或方案中寻求某种意义下 的最优安排或方案131.2 图与网络 定义 定义1.1 一个有向图(Directed Graph 或 Digraph) G是由一个 非空有限集合V(G)和V(G)中某些元素的有序对集合A(G)构成 的二元组，记为有向图G=(V(G)，A(G). 其中V
12、(G) 称为图G的 顶点集(Vertex Set)或节点集(Node Set)，V(G)中的每一个元 素称为该图的一个顶点(Vertex)或节点(Node)； A(G)称为图G 的弧集(Arc Set)，A(G)中的每一个元素(即V(G)中某两个元素 的有序对) 称为该图的一条从到的弧 (Arc). 在不引起混淆的 情况下，记号V(G)和A(G)中也可以省略G，即分别记顶点集 、弧集为V和A，而记有向图G=（V，A）.如果对有向图G中的每条弧赋予一个或多个实数，得 到的有向图称为赋权有向图或有向网络, 简称为网络 (Network). 141.2 图与网络 例图G=(V，A)，其中顶点集V=
13、弧集A= 弧15弧的端点(Endpoint)，尾(Tail)，头(Head)；顶点相邻(Adjacent)，邻居(Neighbor)；弧与顶点关联 (Incident)，出弧(Outgoing Arc)，入 弧(Incoming Arc)；弧相邻 (Adjacent)；环 (Loop)，孤立点(Isolated Vertex)；图的阶(Order) 顶点的度（Degree），出度，入度，奇点，偶点 没有环、且没有多重弧的图称为简单图(Simple Graph)1.2 图与网络 基本概念161.2 图与网络 子 图称为G的子图 (Subgraph) 图的支撑子图 (Spanning Subgra
14、ph，又称生成子图)是包含G 的所有顶点的子图（顶点、弧）导出子图(Induced Subgraph) 图的导出子图是唯一的；图的支撑子图一般是不唯一的 有向图中的途径(Walk)是该图的一些顶点 和弧所组成的子图，这些顶点与弧可以交错排列成 点弧序列 其中 或 如果该序列中的所有弧都指向同一方向，即 ， 则该途径称为有向途径(Directed Walk). 171.2 图与网络 路、圈 有向图中的路 (Path)是该图的不包含重复顶点的途径. 方向与路的起点到终点的方向一致的弧称为路 的前向弧(Forward Arc)；否则称为后向弧或反 向弧(Backward Arc). P,P+,P-
15、有向图中的有向路(Directed Path)是该图的不包含重 复顶点的有向途径，即不包含反向弧的路. 有向图的圈(Cycle) 是起点和终点重合，且不含其他重 复顶点的途径. C,C+,C- 有向图中的有向圈(Directed Cycle)是该图的不包含反 向弧的圈. 不包含有向圈的图称为无圈图(Acyclic Graph). 181.2 图与网络 路、圈 对于有向图中的两个顶点，如果在图中至少存在一条路 把它们连接起来，则称这两个顶点是连通的(Connected). 如果图中任意两个顶点都是连通的，则称该图为连通的 (Connected)；否则称为不连通的(Disconnected). 不连通图可以分解成一些连通分支的并，而连通图只有一个连通分支 .
