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