1图与网络基本概念.pptVIP

* 网 络 优 化 第 1 章 概 论 （第1讲） Network Optimization 江西财经大学 数学与管理工程系 何明 办公室：综合楼 Email:siming800@126.com 网 络 优 化 简 介 网络：一般理解 ---- 计算机信息网络 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益 网 络 优 化 简 介 网络：数学模型、数学结构 ---- 图 从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为（最）优化 (Optimization) 问题 运筹学（Operations Research - OR） 广义：管理科学(OR/MS)、系统科学/工程、 工业工程(IE)、运作管理(OM) 狭义：运筹数学 - 最优化 连续优化：数学规划（线性规划、非线性规划）、非光滑优化、全局优化等 离散优化：组合优化、网络优化、整数规划等 不确定规划：随机规划、模糊规划等 网络优化就是研究与（赋权）图有关的最优化问题 例1.1 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ 1.1网络优化问题的例子 例1.2 最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路. 例1.3 运输问题(Transportation Problem) 某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂. 假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？ 1.1网络优化问题的例子 例1.4 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回 报最大？ 例1.5 中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件. 如何为他(她)设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国复旦大学 管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题. 1.1网络优化问题的例子 例1.6 旅行商问题/货郎（担）问题 (TSP-Traveling Salesman Problem) 一名推销员准备前往若干城市推销产品. 如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题. 1.1网络优化问题的例子 例 稳定婚配问题(Stable Marriage Problem) 假设有n个男人和n个女人, 每人都希望从n个异性中选择一位自己的配偶. 假设每人都对n个异性根据自己的偏好进行了排序, 以此作为选择配偶的基础. 当给定一种婚配方案(即给每人指定一个配偶)后, 如果存在一个男人和一个女人不是互为配偶, 但该男人喜欢该女人胜过其配偶, 且该女人喜欢该男人也胜过其配偶, 则该婚配方案称为不稳定的. 安排稳定的婚配方案的问题称为稳定婚配问题。 1.1网络优化问题的例子 《网络优化》：《网络流》（Network Flows) 特点： （1）与图形有关，或易于用图形方式表示 （2）优化问题：从若干可能的安排或方案中寻求某种意义下的最优安排或方案 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)，V(G)中的每一个元素称为该图的一个顶点(Vertex)或节点(Node)； A(G)称为图G的弧集(Arc Set)，A(G)中的每一个元素(即V(G)