数学建模网络优化幻灯片.ppt

《数学建模网络优化幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模网络优化幻灯片.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数学建模网络优化1第1页，共42页，编辑于2022年，星期六OutlineWhat is Network Optimization?Typical Models&Algorithms Minimum Spanning Tree(最小(生成)树)Minimum Arborescence (最小树形图)Shortest Path (最短路)Maximum Flow (最大流)Minimum Cost Flow (最小费用流)Matching (匹配)Some Modeling Examples2第2页，共42页，编辑于2022年，星期六网网 络络 优优 化化 简简 介介 网络：网络社会-计算机信息

2、网络？电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等网络优化就是研究如何有效地计划、管理和控制网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益网络系统，使之发挥最大的社会和经济效益 3第3页，共42页，编辑于2022年，星期六网网 络络 优优 化化 简简 介介 网络网络(Network)：数学模型、数学结构：数学模型、数学结构-图图 优化优化(Optimization):从若干可能的方案中寻求某种意义从若干可能的方案中寻求某种意义下的最优方案下的最优方案 与图论有联系，也有区别（侧重点不同）与图论有联系，也有区别（侧重点不同）网络优化就是研究

3、与（赋权）图有关的最优化问题网络优化就是研究与（赋权）图有关的最优化问题图论：图论：图的性质图的性质 网络优化网络优化：与（赋权）图有关的优化问题与（赋权）图有关的优化问题组合数学组合数学组合优化组合优化4第4页，共42页，编辑于2022年，星期六Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/5第5页，共42页，编辑于2022年，星期六网网 络络 优优 化化 简简 介介主要参考书：主要参考书：谢金星谢金星、邢文训邢文训，网络优化网络优化，清华大学出版社，清华大学出版社，2000年年8月；月；2003年年9月。月。Ahuj

4、a,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第6页，共42页，编辑于2022年，星期六图与网络图与网络 基本概基本概念念图G=(V，A)，其中顶点集V=弧集A=弧7第7页，共42页，编辑于20

5、22年，星期六例：例：公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，这些城市连接起来，使得从其中任何一个城市都可以使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市经高速公路直接或间接到达另一个城市.假定已经知道假定已经知道了任意两个城市之间修建高速公路的成本，那么应如了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小何决定在哪些城市间修建高速公路，使得总成本最小？网络优化问题的例子网络优化问题的例子 1132546385247最小最小(生成生成)树树也

6、称为也称为最小最小(支撑支撑)树树8第8页，共42页，编辑于2022年，星期六例例：二维矩阵二维矩阵数据存贮问题数据存贮问题某某些些蛋蛋白白质质的的氨氨基基酸酸序序列列差差异异不不多多，如如果果用用二二维维矩矩阵阵的的每每一一行行记记录录一一种种蛋蛋白白质质氨氨基基酸酸序序列列，行行与与行行之之间间的的差差异异很很小小.其其中中一一种种方方法法是是只只存存贮贮其其中中一一行行作作为为参参照照行行，再再存存贮贮行行与与行行之之间间的的一一部部分分差差异异信信息息，使使得得我我们们可可以以在在需需要要时时根根据据参参照照行行生成所有其它行的元素生成所有其它行的元素.R1R3R2R4C13C12C2

7、4最最小小树树网络优化问题的例子网络优化问题的例子 9第9页，共42页，编辑于2022年，星期六“直接方式直接方式”：总经理直接传达；：总经理直接传达；“接接力力方方式式”：总总经经理理只只给给某某些些部部门门经经理理打打电电话话，而而让让这这些些得得到到信信息息的的部部门门经经理理打打电电话话将将信信息息进进一一步步传传达达给给其其他他某某些些部部门门经理，依此类推，最后将信息传达到所有部门经理经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径？如何决定传达信息的途径？信息传播是有向的，有一个信息传播是有向的，有一个“根根”。信息传播途径（忽略方向时）是一棵树。信息传播途径

8、（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：例：信息传播信息传播最小树形图 例10第10页，共42页，编辑于2022年，星期六例例 最短路问题（最短路问题（SPP-Shortest Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当

9、择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路于需要找到一条从甲地到乙地的最短路.网络优化问题的例子网络优化问题的例子 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第11页，共42页，编辑于2022年，星期六例：计划评审技术例：计划评审技术,即即PERT(Project Evaluation&PERT(Project Evaluation&Review Technique),Review Technique),又称网络计划技术或统筹法又称网络计划技术或统筹法)大型复杂

10、工程项目大型复杂工程项目(Project)(Project)往往被分成许多子项目往往被分成许多子项目,子项目之间有一定的子项目之间有一定的先后顺序先后顺序(偏序偏序)要求要求,每一子项目需要一定的时间完成每一子项目需要一定的时间完成.PERT.PERT网络的每条网络的每条弧表示一个子项目弧表示一个子项目,如果以弧长表示每一子项目需要的时间如果以弧长表示每一子项目需要的时间,则最早完工时则最早完工时间对应于网络中的最长路间对应于网络中的最长路(关键路线关键路线).).工程上所谓的关键路线法工程上所谓的关键路线法(CPM:(CPM:Critical Path Method)Critical Pat

11、h 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第12页，共42页，编辑于2022年，星期六例：最大流例：最大流/最小费用流最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限量有上限.从甲地到乙地的每天最多能通车多少辆从甲地到乙地的每天最多能通车多少辆?

12、考虑每条路上的通行成本考虑每条路上的通行成本,如何确定某个车队的具体行车路如何确定某个车队的具体行车路线线,使总成本最小使总成本最小?(甲甲)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第13页，共42页，编辑于2022年，星期六例：例：运输问题运输问题(Transportation Problem)某某种种原原材材料料有有M个个产产地地，现现在在需需要要将将原原材材料料从从产产地地运运往往N个个使使用用这这些些原原材材料料的的工工厂厂.假假定定M个个产产地地的的产产量量和和N家家工工厂厂的的需需要要量量

13、已已知知，单单位位产产品品从从任任一一产产地地到到任任一一工工厂厂的的的的运运费费已已知知，那那么么如如何何安安排排运运输方案可以使总运输成本最低？输方案可以使总运输成本最低？网络优化问题的例子网络优化问题的例子 ST特殊的最小费用特殊的最小费用流问题流问题（二部图（二部图,|S|=M,|T|=N）14第14页，共42页，编辑于2022年，星期六例：例：指派问题指派问题(Assignment Problem)一家公司经理准备安排一家公司经理准备安排N名员工去完成名员工去完成N项任务，每人一项项任务，每人一项.由由于各员工的特点不同，不同的员工去完成同一项任务时所获于各员工的特点不同，不同的员工

14、去完成同一项任务时所获得的回报是不同的得的回报是不同的.如何分配工作方案可以使总回报最大？如何分配工作方案可以使总回报最大？网络优化问题的例子网络优化问题的例子 ST特殊的最小特殊的最小费用流问题费用流问题（二部图，（二部图，|S|=|T|=N）15第15页，共42页，编辑于2022年，星期六最小费用流模型的特例及扩展最小费用流模型的特例及扩展 最 小 费 用 流 问 题指 派问 题运 输问 题最大流问题最短路问题带 增 益 的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭 义 模 型 广义模型 凸规划 16第16页，共42页，编辑于2022年，星期六例：匹配

15、例：匹配问题问题(Matching Problem)在一次有在一次有m个大学毕业生和个大学毕业生和n家公司参加的供需见面会上，每个毕家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生面会上招聘到员工）？如果每个毕业

16、生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？人可以在这次供需见面会上找到工作？网络优化问题的例子网络优化问题的例子 二部基数二部基数/赋权匹配赋权匹配17第17页，共42页，编辑于2022年，星期六破圈法破圈法-复杂度高复杂度高避圈法避圈法-贪婪算法贪婪算法(Greedy Algorithm)Kruskal 算法（算法（1956）Prim 算法（算法（1957）：即：即“边割法边割法”Dijkstra算法（算法（1959）Sollin 算法算法（1961）最小（生

17、成）树算法最小（生成）树算法18第18页，共42页，编辑于2022年，星期六最小树形图算法：最小树形图算法：朱朱(永津永津)-刘刘(振宏振宏)算法（算法（1965）最大分枝最大分枝算法：算法：Edmons算法（算法（1968）基本思想：收缩基本思想：收缩 展开展开 19第19页，共42页，编辑于2022年，星期六n无圈网络：拓扑排序无圈网络：拓扑排序 +动态规划动态规划圈的检测圈的检测n正费用网络：正费用网络：Dijkstra算法（算法（1959）n一般网络，单一起点（或终点）一般网络，单一起点（或终点）Bellman-Ford算法算法(1956)：O(mn)n一般网络，所有点对一般网络，所有

18、点对Floyd-Warshall算法算法(1962)：O(n3)n负圈检测负圈检测最短路最短路算法：标号设定算法：标号设定/修正算法修正算法20第20页，共42页，编辑于2022年，星期六n增广路算法增广路算法Ford-Fulkerson标号算法标号算法(1956)最大容量增广路算法最大容量增广路算法容量变尺度算法容量变尺度算法最短增广路算法：最短增广路算法：O(n2m)n预流推进算法预流推进算法最高标号预流推进算法最高标号预流推进算法：O(n2m1/2)最大流最大流算法算法实际计算效率高21第21页，共42页，编辑于2022年，星期六n消圈算法消圈算法n最小费用路算法最小费用路算法n原始原始

19、-对偶算法对偶算法Ford和和Forkerson(1957,1962)n瑕疵算法瑕疵算法(Out-Of-Kilter Algorithm)n松弛松弛(Relaxation)算法算法n网络单纯形算法网络单纯形算法最小费用流最小费用流算法算法实际计算效率高22第22页，共42页，编辑于2022年，星期六n二部基数匹配二部基数匹配增广路算法：增广路算法：O(mn)简单网络上的最大流算法：简单网络上的最大流算法：O(mn1/2)n一般基数匹配一般基数匹配“花花”算法算法:O(n3)n二部赋权匹配（指派问题）二部赋权匹配（指派问题）最小费用流算法（如匈牙利算法）最小费用流算法（如匈牙利算法）:O(n3)

20、n一般赋权匹配一般赋权匹配原始原始-对偶算法对偶算法:O(n3)匹配匹配算法算法23第23页，共42页，编辑于2022年，星期六网络优化的评注许多实际问题可以直接用网络优化建模许多实际问题可能用到网络优化建模许多实际问题是网络优化的变种网络优化问题通常可以用整数规划建模24第24页，共42页，编辑于2022年，星期六西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306019520272069

21、0520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400401450451500运价202326293225第25页，共42页，编辑于2022年，星期六西气东送（钢管运输）问题西气东送（钢管运输）问题（CUMCM-2000B)二次规划（常用解法）二次规划（常用解法）最小费用流问题？最小费用流问题？（清华大学队，获网易杯）（清华大学队，获网易杯）线性模型（网络规模较大，有现成算法）线性模型（网络规模较大，有现成算法）非线性模型（网络规

22、模较小，需要自己设计算法）非线性模型（网络规模较小，需要自己设计算法）基本问题基本问题-最小运费矩阵的计算最小运费矩阵的计算两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法26第26页，共42页，编辑于2022年，星期六铁路公路混合运输最短路问题铁路公路混合运输最短路问题 最小运费矩阵算法（四川大学最小运费矩阵算法（四川大学/清华大学等队）清华大学等队）Dijkstra算法算法 或或 Floyd-Warshall算法算法铁路最短路问题铁路最短路问题最短路最短路 =铁路最小运费矩阵铁路最小

23、运费矩阵公路最短路问题公路最短路问题最短路最短路 =公路最小运费矩阵公路最小运费矩阵铁路铁路/公路混合运输最短路问题公路混合运输最短路问题铁路铁路/公路混合运输网络公路混合运输网络最短路最短路 =铁路铁路/公路混合运输最小运费矩阵公路混合运输最小运费矩阵27第27页，共42页，编辑于2022年，星期六例：中国例：中国邮递员问题邮递员问题(CPP-Chinese Postman Problem)一一名名邮邮递递员员负负责责投投递递某某个个街街区区的的邮邮件件.如如何何设设计计一一条条最最短短的的投投递递路路线线(从从邮邮局局出出发发，经经过过投投递递区区内内每每条条街街道道至至少少一一次次，最最

24、后后返返回回邮邮局局)？由由于于这这一一问问题题是是我我国国学学者者管管梅梅谷谷教教授授19601960年年首首先先提提出出的的，所所以以国际上称之为中国邮递员问题国际上称之为中国邮递员问题.网络优化问题的其他例子网络优化问题的其他例子 单向？双向？风向？28第28页，共42页，编辑于2022年，星期六例：例：旅行商问题旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品.如何为他如何为他(她她)设计一条设计一条最短的旅行路线最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返从驻地出发，经过每个城市

25、恰好一次，最后返回驻地回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问？这一问题的研究历史十分悠久，通常称之为旅行商问题题.网络优化问题的例子网络优化问题的例子 BACDEFGHI29第29页，共42页，编辑于2022年，星期六灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展30第30页，共42页，编辑于2022年，星期六例：例：套汇（套汇（Arbitrage）问题）问题 在外汇市场上，将在外汇市场上，将1单位的某种货币通过多次兑换，获单位的某种货币通过多次兑换，获得多于得多于1单位的同种货币，称为套汇。如：单位的同种货币，称为套汇。如：1单位的单位的A货币货币(兑换兑换)4

26、6.4单位单位B货币货币1单位的单位的B货币货币(兑换兑换)2.5单位单位C货币货币 1单位的单位的C货币货币(兑换兑换)0.0091单位单位A货币货币 则则:1单位的单位的A货币货币 (通过三次兑换获得通过三次兑换获得)46.42.50.0091=1.0556单位单位A货币货币网络优化问题的例子网络优化问题的例子 可以可以变变成成检测负检测负圈的圈的问题问题现在假设给定了若干种货币及其两两之间的兑换现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到率，请你帮助找到一种一种套汇方式（或判定该外汇市场上套汇方式（或判定该外汇市场上不存在套汇的可能）。不存在套汇的可能）。31第31页，共4

27、2页，编辑于2022年，星期六套汇套汇:46.42.50.0091=1.0556 1两边取倒数两边取倒数(乘积乘积1)，再取对数（求和，再取对数（求和0）可以变成检测负圈的问题可以变成检测负圈的问题套汇（套汇（Arbitrage）问题）问题化乘积为求和化乘积为求和的技的技术术，也常用于，也常用于“可靠性可靠性问题问题”可能是完全有向图；可能是完全有向图；弧上的权就是汇率的倒数的对数值！弧上的权就是汇率的倒数的对数值！32第32页，共42页，编辑于2022年，星期六例：例：逃生路线问题逃生路线问题n*n网格节点上有网格节点上有m个房间，逃到边上节点就算逃生成功个房间，逃到边上节点就算逃生成功如何

28、规划逃生路线，使这些路线互不相交？如何规划逃生路线，使这些路线互不相交？网络优化问题的例子网络优化问题的例子 可以可以变变成成最大流问题最大流问题逃生逃生成功成功没有没有逃逃生生路线路线33第33页，共42页，编辑于2022年，星期六m个房间是供应节点（源，供应量为）个房间是供应节点（源，供应量为）只有边上节点可以是吸收节点（汇，吸收量为只有边上节点可以是吸收节点（汇，吸收量为）多源多汇，容易变成单源单汇多源多汇，容易变成单源单汇每条边容量为每条边容量为每个节点容量为（通过增加节点和边，变成边容量）每个节点容量为（通过增加节点和边，变成边容量）逃生路线问题逃生路线问题变变成成最大流问题最大流问

29、题逃生逃生成功成功没有没有逃逃生生路线路线其他目其他目标标？34第34页，共42页，编辑于2022年，星期六例：例：空间实验问题空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行中某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。外有些可能是不同的）。

30、已知完成每个实验后公司所得到的相应报酬（不同实验的报酬已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总总报酬总费用）。报酬总费用）。网络优化问题的例子网络优化问题的例子 可以可以变变成成最大流问题最大流问题35第35页

31、，共42页，编辑于2022年，星期六空间实验问题空间实验问题最大流最大流(最小割最小割)问题问题设备 实验n个实验(报酬pi)m类设备(成本ci)12m12ncipist计划有限割有限割的容量：ST36第36页，共42页，编辑于2022年，星期六例例:学生分区学生分区问题问题假设某个城市分为假设某个城市分为L个区个区,每个区有若干男孩和若干女孩需要每个区有若干男孩和若干女孩需要上学上学.假设每个区有一所小学假设每个区有一所小学,每所小学所能容纳的学生总数已知每所小学所能容纳的学生总数已知,并并且按照规定且按照规定,每所小学所能容纳的男孩和女孩比例不能太大或太每所小学所能容纳的男孩和女孩比例不能

32、太大或太小小.假设每两个区之间的路程已知假设每两个区之间的路程已知(同一区内认为路程近似为同一区内认为路程近似为0),如何为需要上学的小孩分配学校如何为需要上学的小孩分配学校,使得所有小孩上学所走的使得所有小孩上学所走的总路程最少总路程最少?网络优化问题的例子网络优化问题的例子 可以可以变变成成最小费用流最小费用流的的问题问题37第37页，共42页，编辑于2022年，星期六L=2为例：为例：bi 男孩；男孩；gi 女孩；女孩；ui 学校容量学校容量(p,q)男孩比例上下限；男孩比例上下限；dij距离距离学学生生分分区区问问题题最小费用流最小费用流问题问题b1b2g1g2(0,u1)(0,u2)

33、t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)费用为38第38页，共42页，编辑于2022年，星期六例例:一一类类排序排序(Scheduling)问题问题某车间接受了某车间接受了p项不同的加工任务，要求在车间的项不同的加工任务，要求在车间的q台完全相同台完全相同的机器上加工的机器上加工每项任务所需要的加工时间是相同的，且只需要在其中的任每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工，且每每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务

34、的加工都必须一次完成（即一旦开始加工，加工中不能间项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断断每台机器在同一时刻不能加工两项或两项以上的任务每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时，如果第从当前时刻开始计时，如果第 j 项任务的完工时间为项任务的完工时间为tj，则该车，则该车间的信誉损失为间的信誉损失为cj(tj)（假设该函数为增函数）（假设该函数为增函数）车间希望制订一个加工计划，使总的信誉损失最小车间希望制订一个加工计划，使总的信誉损失最小网络优化问题的例子网络优化问题的例子 可以可以变变成成最小费用流最小费用流的的问题问题39第39页，共42页，编

35、辑于2022年，星期六一类排序一类排序(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第40页，共42页，编辑于2022年，星期六网络优化问题的例子网络优化问题的例子 例例 稳定婚配问题稳定婚配问题(Stable Marriage Problem)假假设设有有n个个男男人人和和n个个女女人人,每每人人都都希希望望从从n个个异异性性中中选选择择一一

36、位位自自己己的的配配偶偶.假假设设每每人人都都对对n个个异异性性根根据据自自己己的的偏偏好好进进行行了了排排序序,以以此此作作为为选选择择配配偶偶的的基基础础.当当给给定定一一种种婚婚配配方方案案(即即给给每每人人指指定定一一个个配配偶偶)后后,如如果果存存在在一一个个男男人人和和一一个个女女人人不不是是互互为为配配偶偶,但但该该男男人人喜喜欢欢该该女女人人胜胜过过其其配配偶偶,且且该该女女人人喜喜欢欢该该男男人人也也胜胜过过其其配配偶偶,则则该该婚婚配配方方案案称称为为不不稳稳定定的的.安排稳定的婚配方案的问题称为安排稳定的婚配方案的问题称为稳定婚配问题稳定婚配问题。二部完美匹配二部完美匹配存在性？算法？其他目标41第41页，共42页，编辑于2022年，星期六MCM中的一些网络优化问题 1999 1999 扫扫雪雪车车问题问题1991 Steiner1991 Steiner树问题树问题1994 1994 通讯网络问题通讯网络问题2000 2000 无线信道分配问题无线信道分配问题?42第42页，共42页，编辑于2022年，星期六