网络优化模型与算法谢金星.ppt课件

网网 络络 优优 化化模模 型型 与与 算算 法法 Network Optimization:Models&Algorithms清华大学数学科学系 谢金星Email: http:/ -江西 庐山1网 络 优 化Network OptimizationOutlineWhat is Network Optimization?Typical Models&Algorithms Minimum Spanning Tree(最小(生成)树)Minimum Arborescence (最小树形图)Shortest Path (最短路)Maximum Flow (最大流)Minimum Cost Flow (最小费用流)Matching (匹配)Some Modeling Examples2OutlineWhat is Network Optimiz网网 络络 优优 化化 简简 介介 网络：网络社会-计算机信息网络？电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等网络优化就是研究如何有效地计划、管理和控制网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益网络系统，使之发挥最大的社会和经济效益 3网 络 优 化 简 介 网络：网络社会-网网 络络 优优 化化 简简 介介 网络网络(Network)：数学模型、数学结构：数学模型、数学结构-图图 优化优化(Optimization):从若干可能的方案中寻求某从若干可能的方案中寻求某种意义下的最优方案种意义下的最优方案 与图论有联系，也有区别（侧重点不同）与图论有联系，也有区别（侧重点不同）网络优化就是研究与（赋权）图有关的最优化问题网络优化就是研究与（赋权）图有关的最优化问题图论：图论：图的性质图的性质 网络优化网络优化：与（赋权）图有关的优化问题与（赋权）图有关的优化问题组合数学组合数学组合优化组合优化4网 络 优 化 简 介 网络(Network)：数学模Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/5Optimization Tree 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.网络优化模型网络优化模型网络优化算法及其复杂性网络优化算法及其复杂性网络优化或网络流（网络优化或网络流（Network Flows)或网络规划（或网络规划（Network Programming)6网 络 优 化 简 介主要参考书：网络优化模型网络优图与网络图与网络 基本概基本概念念图G=(V，A)，其中顶点集V=弧集A=弧7图与网络 基本概念图G=(V，A)，其中顶点集V=例：例：公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，把这些城市连接起来，使得从其中任何一个城市使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市都可以经高速公路直接或间接到达另一个城市.假假定已经知道了任意两个城市之间修建高速公路的成定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？使得总成本最小？网络优化问题的例子网络优化问题的例子 1132546385247最小最小(生成生成)树树也称为也称为最小最小(支撑支撑)树树8例：公路连接问题网络优化问题的例子 11325463852例例：二维矩阵二维矩阵数据存贮问题数据存贮问题某某些些蛋蛋白白质质的的氨氨基基酸酸序序列列差差异异不不多多，如如果果用用二二维维矩矩阵阵的的每每一一行行记记录录一一种种蛋蛋白白质质氨氨基基酸酸序序列列，行行与与行行之之间间的的差差异异很很小小.其其中中一一种种方方法法是是只只存存贮贮其其中中一一行行作作为为参参照照行行，再再存存贮贮行行与与行行之之间间的的一一部部分分差差异异信信息息，使使得得我我们们可以在需要时根据参照行生成所有其它行的元素可以在需要时根据参照行生成所有其它行的元素.R1R3R2R4C13C12C24最最小小树树网络优化问题的例子网络优化问题的例子 9例：二维矩阵数据存贮问题R1R3R2R4C13C12C24“直接方式直接方式”：总经理直接传达；：总经理直接传达；“接接力力方方式式”：总总经经理理只只给给某某些些部部门门经经理理打打电电话话，而而让让这这些些得得到到信信息息的的部部门门经经理理打打电电话话将将信信息息进进一一步步传传达达给给其其他他某某些些部部门经理，依此类推，最后将信息传达到所有部门经理门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？如何决定传达信息的途径？信息传播是有向的，有一个信息传播是有向的，有一个“根根”。信息传播途径（忽略方向时）是一棵树。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：例：信息传播信息传播最小树形图 例10“直接方式”：总经理直接传达；信息传播是有向的，有一个“根例例 最短路问题（最短路问题（SPP-Shortest Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路乙地的最短路.网络优化问题的例子网络优化问题的例子 A A F F 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 11例 最短路问题（SPP-Shortest Path Prob例：计划评审技术例：计划评审技术,即即PERT(Project Evaluation&PERT(Project Evaluation&Review Technique),Review Technique),又称网络计划技术或统筹法又称网络计划技术或统筹法)大型复杂工程项目大型复杂工程项目(Project)(Project)往往被分成许多子项目往往被分成许多子项目,子项目之子项目之间有一定的先后顺序间有一定的先后顺序(偏序偏序)要求要求,每一子项目需要一定的时间每一子项目需要一定的时间完成完成.PERT.PERT网络的每条弧表示一个子项目网络的每条弧表示一个子项目,如果以弧长表示每一如果以弧长表示每一子项目需要的时间子项目需要的时间,则最早完工时间对应于网络中的最长路则最早完工时间对应于网络中的最长路(关关键路线键路线).).工程上所谓的关键路线法工程上所谓的关键路线法(CPM:Critical Path(CPM:Critical Path Method)Method)基本上也是计划评审技术的一部分基本上也是计划评审技术的一部分.项目网络不含圈（其最长路问题和最短路问题都是可解的）项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始开始)A)A F(F(结束结束)5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 12例：计划评审技术,即PERT(Project Evalua例：最大流例：最大流/最小费用流最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限车量有上限.从甲地到乙地的每天最多能通车多少辆从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本考虑每条路上的通行成本,如何确定某个车队的具体行如何确定某个车队的具体行车路线车路线,使总成本最小使总成本最小?(甲甲)A)A F (F (乙乙)5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 13例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天例：例：运输问题运输问题(Transportation Problem)某某种种原原材材料料有有M个个产产地地，现现在在需需要要将将原原材材料料从从产产地地运运往往N个个使使用用这这些些原原材材料料的的工工厂厂.假假定定M个个产产地地的的产产量量和和N家家工工厂厂的的需需要要量量已已知知，单单位位产产品品从从任任一一产产地地到到任任一一工工厂厂的的的的运运费费已已知，那么如何安排运输方案可以使总运输成本最低？知，那么如何安排运输方案可以使总运输成本最低？网络优化问题的例子网络优化问题的例子 ST特殊的最小费特殊的最小费用流问题用流问题（二部图（二部图,|S|=M,|T|=N）14例：运输问题(Transportation Problem例：例：指派问题指派问题(Assignment Problem)一家公司经理准备安排一家公司经理准备安排N名员工去完成名员工去完成N项任务，每人一项项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的所获得的回报是不同的.如何分配工作方案可以使总回报最如何分配工作方案可以使总回报最大？大？网络优化问题的例子网络优化问题的例子 ST特殊的最小特殊的最小费用流问题费用流问题（二部图，（二部图，|S|=|T|=N）15例：指派问题(Assignment Problem)网络优最小费用流模型的特例及扩展最小费用流模型的特例及扩展 最 小 费 用 流 问 题指 派问 题运 输问 题最大流问题最短路问题带 增 益 的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭义模型 广义模型 凸规划 16最小费用流模型的特例及扩展 最 小 费 用 流 问 题指例：匹配例：匹配问题问题(Matching Problem)在一次有在一次有m个大学毕业生和个大学毕业生和n家公司参加的供需见面会上，家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作公司愿意接收若干毕业生中的一人到公司工作.那么，最后那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？在这次供需见面会上找到工作？网络优化问题的例子网络优化问题的例子 二部基数二部基数/赋权匹配赋权匹配17例：匹配问题(Matching Problem)网络优化问题破圈法破圈法-复杂度高复杂度高避圈法避圈法-贪婪算法贪婪算法(Greedy Algorithm)Kruskal 算法（算法（1956）Prim 算法（算法（1957）：即：即“边割法边割法”Dijkstra算法（算法（1959）Sollin 算法算法（1961）最小（生成）树算法最小（生成）树算法18破圈法-复杂度高最小（生成）树算法18最小树形图算法：最小树形图算法：朱朱(永津永津)-刘刘(振宏振宏)算法（算法（1965）最大分枝最大分枝算法：算法：Edmons算法（算法（1968）基本思想：收缩基本思想：收缩 展开展开 19最小树形图算法：朱(永津)-刘(振宏)算法（1965）最大n无圈网络：拓扑排序无圈网络：拓扑排序 +动态规划动态规划圈的检测圈的检测n正费用网络：正费用网络：Dijkstra算法（算法（1959）n一般网络，单一起点（或终点）一般网络，单一起点（或终点）Bellman-Ford算法算法(1956)：O(mn)n一般网络，所有点对一般网络，所有点对Floyd-Warshall算法算法(1962)：O(n3)n负圈检测负圈检测最短路最短路算法：标号设定算法：标号设定/修正算法修正算法20无圈网络：拓扑排序 +动态规划最短路算法：标号设定/修正n增广路算法增广路算法Ford-Fulkerson标号算法标号算法(1956)最大容量增广路算法最大容量增广路算法容量变尺度算法容量变尺度算法最短增广路算法：最短增广路算法：O(n2m)n预流推进算法预流推进算法最高标号预流推进算法最高标号预流推进算法：O(n2m1/2)最大流最大流算法算法实际计算效率高21增广路算法最大流算法实际计算效率高21n消圈算法消圈算法n最小费用路算法最小费用路算法n原始原始-对偶算法对偶算法Ford和和Forkerson(1957,1962)n瑕疵算法瑕疵算法(Out-Of-Kilter Algorithm)n松弛松弛(Relaxation)算法算法n网络单纯形算法网络单纯形算法最小费用流最小费用流算法算法实际计算效率高22消圈算法最小费用流算法实际计算效率高22n二部基数匹配二部基数匹配增广路算法：增广路算法：O(mn)简单网络上的最大流算法：简单网络上的最大流算法：O(mn1/2)n一般基数匹配一般基数匹配“花花”算法算法:O(n3)n二部赋权匹配（指派问题）二部赋权匹配（指派问题）最小费用流算法（如匈牙利算法）最小费用流算法（如匈牙利算法）:O(n3)n一般赋权匹配一般赋权匹配原始原始-对偶算法对偶算法:O(n3)匹配匹配算法算法23二部基数匹配匹配算法23网络优化的评注许多实际问题可以直接用网络优化建模许多实际问题可能用到网络优化建模许多实际问题是网络优化的变种网络优化问题通常可以用整数规划建模24网络优化的评注许多实际问题可以直接用网络优化建模24西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400401450451500运价202326293225西气东送（钢管运输）问题（CUMCM-2000B)A132西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)二次规划（常用解法）二次规划（常用解法）最小费用流问题？最小费用流问题？（清华大学队，获网易杯）（清华大学队，获网易杯）线性模型（网络规模较大，有现成算法）线性模型（网络规模较大，有现成算法）非线性模型（网络规模较小，需要自己设计算法）非线性模型（网络规模较小，需要自己设计算法）基本问题基本问题-最小运费矩阵的计算最小运费矩阵的计算两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法26西气东送（钢管运输）问题（CUMCM-2000B)二次规划铁路公路混合运输最短路问题铁路公路混合运输最短路问题 最小运费矩阵算法（四川大学最小运费矩阵算法（四川大学/清华大学等队）清华大学等队）Dijkstra算法算法 或或 Floyd-Warshall算法算法铁路最短路问题铁路最短路问题最短路最短路 =铁路最小运费矩阵铁路最小运费矩阵公路最短路问题公路最短路问题最短路最短路 =公路最小运费矩阵公路最小运费矩阵铁路铁路/公路混合运输最短路问题公路混合运输最短路问题铁路铁路/公路混合运输网络公路混合运输网络最短路最短路 =铁路铁路/公路混合运输最小运费矩阵公路混合运输最小运费矩阵27铁路公路混合运输最短路问题 最小运费矩阵算法（四川大学/清例：中国例：中国邮递员问题(CPP-Chinese Postman Problem)一一名名邮邮递递员员负负责责投投递递某某个个街街区区的的邮邮件件.如如何何设设计计一一条条最最短短的的投投递递路路线线(从从邮邮局局出出发发，经经过过投投递递区区内内每每条条街街道道至至少少一一次次，最最后后返返回回邮邮局局)？由由于于这这一一问问题题是是我我国国学学者者管管梅梅谷谷教教授授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题.网络优化问题的其他例子网络优化问题的其他例子 单向？双向？风向？28例：中国邮递员问题(CPP-Chinese Postman 例：例：旅行商问题旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品.如何为他如何为他(她她)设计设计一条最短的旅行路线一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，从驻地出发，经过每个城市恰好一次，最后返回驻地最后返回驻地)？这一问题的研究历史十分悠久，通常称之？这一问题的研究历史十分悠久，通常称之为旅行商问题为旅行商问题.网络优化问题的例子网络优化问题的例子 BACDEFGHI29例：旅行商问题(TSP-Traveling Salesman灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展30灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展3例：例：套汇（套汇（Arbitrage）问题）问题 在外汇市场上，将在外汇市场上，将1单位的某种货币通过多次兑单位的某种货币通过多次兑换，获得多于换，获得多于1单位的同种货币，称为套汇。如：单位的同种货币，称为套汇。如：1单位的单位的A货币货币(兑换兑换)46.4单位单位B货币货币1单位的单位的B货币货币(兑换兑换)2.5单位单位C货币货币 1单位的单位的C货币货币(兑换兑换)0.0091单位单位A货币货币 则则:1单位的单位的A货币货币 (通过三次兑换获得通过三次兑换获得)46.42.50.0091=1.0556单位单位A货币货币网络优化问题的例子网络优化问题的例子 可以可以变成成检测负圈的圈的问题问题现在假设给定了若干种货币及其两两之间的兑现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到换率，请你帮助找到一种一种套汇方式（或判定该外汇市套汇方式（或判定该外汇市场上不存在套汇的可能）。场上不存在套汇的可能）。31例：套汇（Arbitrage）问题网络优化问题的例子 可以变套汇套汇:46.42.50.0091=1.0556 1两边取倒数两边取倒数(乘积乘积1)，再取对数（求和，再取对数（求和0）可以变成检测负圈的问题可以变成检测负圈的问题套汇（套汇（Arbitrage）问题）问题化乘积为求和化乘积为求和的技的技术，也常用于，也常用于“可靠性可靠性问题问题”可能是完全有向图；可能是完全有向图；弧上的权就是汇率的倒数的对数值！弧上的权就是汇率的倒数的对数值！32套汇:46.42.50.0091=1.0556例：例：逃生路线问题逃生路线问题n*n网格节点上有网格节点上有m个房间，逃到边上节点就算逃生成功个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？如何规划逃生路线，使这些路线互不相交？网络优化问题的例子网络优化问题的例子 可以可以变成成最大流问题最大流问题逃生逃生成功成功没有没有逃逃生生路线路线33例：逃生路线问题网络优化问题的例子 可以变成最大流问题逃生成m个房间是供应节点（源，供应量为）个房间是供应节点（源，供应量为）只有边上节点可以是吸收节点（汇，吸收量为只有边上节点可以是吸收节点（汇，吸收量为）多源多汇，容易变成单源单汇多源多汇，容易变成单源单汇每条边容量为每条边容量为每个节点容量为（通过增加节点和边，变成边容量）每个节点容量为（通过增加节点和边，变成边容量）逃生路线问题逃生路线问题变成成最大流问题最大流问题逃生逃生成功成功没有没有逃逃生生路线路线其他目其他目标？34m个房间是供应节点（源，供应量为）逃生路线问题变成最大流问例：例：空间实验问题空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。的，而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验的已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，以公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润利润=总报酬总费用）。总报酬总费用）。网络优化问题的例子网络优化问题的例子 可以可以变成成最大流问题最大流问题35例：空间实验问题网络优化问题的例子 可以变成最大流问题35空间实验问题空间实验问题最大流最大流(最小割最小割)问题问题设备 实验n个实验(报酬pi)m类设备(成本ci)12m12ncipist计划有限割有限割的容量：ST36空间实验问题最大流(最小割)问题设备 实验n个实验例例:学生分区学生分区问题问题假设某个城市分为假设某个城市分为L个区个区,每个区有若干男孩和若干女孩需每个区有若干男孩和若干女孩需要上学要上学.假设每个区有一所小学假设每个区有一所小学,每所小学所能容纳的学生总数已每所小学所能容纳的学生总数已知知,并且按照规定并且按照规定,每所小学所能容纳的男孩和女孩比例不每所小学所能容纳的男孩和女孩比例不能太大或太小能太大或太小.假设每两个区之间的路程已知假设每两个区之间的路程已知(同一区内认为路程近似为同一区内认为路程近似为0),如何为需要上学的小孩分配学校如何为需要上学的小孩分配学校,使得所有小孩上学所使得所有小孩上学所走的总路程最少走的总路程最少?网络优化问题的例子网络优化问题的例子 可以可以变成成最小费用流最小费用流的的问题问题37例:学生分区问题网络优化问题的例子 可以变成最小费用流的L=2为例：为例：bi 男孩；男孩；gi 女孩；女孩；ui 学校容量学校容量(p,q)男孩比例上下限；男孩比例上下限；dij距离距离学学生生分分区区问问题题最小费用最小费用流问题流问题b1b2g1g2(0,u1)(0,u2)t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)费用为38L=2为例：bi 男孩；gi 女孩；ui 学校容量学生分例例:一一类排序排序(Scheduling)问题问题某车间接受了某车间接受了p项不同的加工任务，要求在车间的项不同的加工任务，要求在车间的q台完全台完全相同的机器上加工相同的机器上加工每项任务所需要的加工时间是相同的，且只需要在其中的每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工，每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，加且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断工中不能间断每台机器在同一时刻不能加工两项或两项以上的任务每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时，如果第从当前时刻开始计时，如果第 j 项任务的完工时间为项任务的完工时间为tj，则该车间的信誉损失为则该车间的信誉损失为cj(tj)（假设该函数为增函数）（假设该函数为增函数）车间希望制订一个加工计划，使总的信誉损失最小车间希望制订一个加工计划，使总的信誉损失最小网络优化问题的例子网络优化问题的例子 可以可以变成成最小费用流最小费用流的的问题问题39例:一类排序(Scheduling)问题网络优化问题的例一类排序一类排序(Scheduling)问题问题12p12r111-q-q-q p个工件；q台机器;加工时间ac1(a)c1(2a)c1(ra)c2(a)c2(2a)cp(2a)c2(ra)cp(a)cp(ra)每台机器加工的工件数：r=p/q(不妨设为整数)工件加工位置变成成最小费用流最小费用流的的问题问题40一类排序(Scheduling)问题111-qp个工件；c1网络优化问题的例子网络优化问题的例子 例例 稳定婚配问题稳定婚配问题(Stable Marriage Problem)假假设设有有n个个男男人人和和n个个女女人人,每每人人都都希希望望从从n个个异异性性中中选选择择一一位位自自己己的的配配偶偶.假假设设每每人人都都对对n个个异异性性根根据据自自己己的的偏偏好好进进行行了了排排序序,以以此此作作为为选选择择配配偶偶的的基基础础.当当给给定定一一种种婚婚配配方方案案(即即给给每每人人指指定定一一个个配配偶偶)后后,如如果果存存在在一一个个男男人人和和一一个个女女人人不不是是互互为为配配偶偶,但但该该男男人人喜喜欢欢该该女女人人胜胜过过其其配配偶偶,且且该该女女人人喜喜欢欢该该男男人人也也胜胜过过其其配配偶偶,则则该该婚婚配配方方案案称称为为不不稳稳定定的的.安安排排稳稳定定的的婚婚配配方方案案的的问题称为问题称为稳定婚配问题稳定婚配问题。二部完美匹配二部完美匹配存在性？算法？其他目标41网络优化问题的例子 例 稳定婚配问题(Stable MarrMCM中的一些网络优化问题 1999 1999 扫雪雪车问题问题1991 Steiner1991 Steiner树问题树问题1994 1994 通讯网络问题通讯网络问题2000 2000 无线信道分配问题无线信道分配问题?42MCM中的一些网络优化问题 1999 扫雪车问题42Thats all.Any Questions?Thank you for your attendance!最后，祝大家在数学建模活动中不断提高综合素质，在数学建模竞赛中取得更好的成绩！43Thats all.Any Questions?