图与网络优化概要.ppt

第*页 W( f (2) ) 图 f (1) (3) (2) (6) (-1) (4) (-2) (-1) (-4) v1 vs v3 vt v2 最短路：vs-v2-v3-vt 流量调整量θ=3 (2,0) (5,5) (8,5) (4,0) (7,7) (10,2) (10,0) 图 e f (2),v( f (2))=7 v1 vs v2 v3 vt 第*页 (8,8) (10,3) (4,3) (2,0) (7,7) (10,2) (5,5) 图 g f (3),v( f (3))=10 v1 vs v2 v3 vt b( f (3))=2*4+8*1+5*2+ 3*3+ 3*2+ 7*1=48 第*页 (-1) (3) (2) (6) (-1) (4) (-2) (-4) W( f (3) ) 图 h (-2) (-3) v1 vs v2 v3 vt 最短路：vs-v1-v2-v3-vt 流量调整量θ=1 (8,8) (10,3) (4,3) (2,0) (7,7) (10,2) (5,5) 图 g f (3),v( f (3))=10 v1 vs v2 v3 vt 第*页 (8,8) (10,4) (4,4) (2,0) (7,7) (10,3) (5,4) 图 i f (4),v ( f(4)) =11 v1 vs v2 v3 vt b( f (4))=3*4+8*1+4*2+ 4*3+ 4*2+ 7*1=55 第*页 (-1) (3) (-2) (6) (-1) (4) (2) (-4) W( f (4) ) 图 j (-2) (-3) v1 vs v2 v3 vt 第*页 (8,8) (10,4) (4,4) (2,0) (7,7) (10,3) (5,4) 图 i f (4),v ( f(4)) =11 v1 vs v2 v3 vt b( f (4))=3*4+8*1+4*2+ 4*3+ 4*2+ 7*1=55 第*页 应用案例——预搅拌混凝土公司的物料运送方案 某混凝土公司负责提供一个建筑工地的预搅拌混凝土，运送方式以整车配送。由于运输的混凝土是粉尘污染物质，所以有关部门规定了该公司在路段上每天的最高运输往返辆次。每车每个往返计算流量1车。搅拌站与施工地点之间的运输网络以及各条的路径的容量（车/天）和单车成本（百元）见下图。请为该公司制定以下运输方案： （1）公司的最小费用最大流是多少？最小费用是多少？如何安排运输路线？ （2）公司如果必须运送10车，则此时最小费用是多少？如何安排运输路线？ A1 A2 A3 S T (容量，费用) (10，4) (8，1) (7，1) (5，2) (10，3) (2，6) (4，2) 第7章 图与网络优化 7.1 图论概述 7.2 图的基本概念 7.3 最小树问题 7.4 最短路问题 7.5 网络最大流问题 7.6 最小费用最大流问题 7.7 中国邮递员问题 第*页 7.7 中国邮递员问题 中国邮递员问题的图论表达：给定一个连通图，在每边ei上赋予一个非负权值w(ei)，要求一个圈（未必是简单圈），过每边至少一次，并使圈的总权最小。 第*页 7.7 中国邮递员问题 欧拉链：给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这个链为欧拉链。 欧拉圈：若存在一个简单圈，过每边一次，且仅一次，则称这个圈为欧拉圈。 欧拉图：一个图若有欧拉圈，则为欧拉图。 显然，一个图若能一笔画出，这个图必是欧拉图。 第*页 7.7 中国邮递员问题 定理：连通多重图G有欧拉圈，当且仅当G中无奇点。 推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点。 第*页 7.7 中国邮递员问题 若中国邮递员问题所给出的街道图没有奇点，那么沿着欧拉回路走，肯定是每条街道走过一次且仅一次，他走的路程就是一条最短路线。 若有奇点，则必须在某些街道上重复一次或多次。 中国邮递员问题可以叙述为在一个有奇点的图中，要求增加一些多重边，使新图不含奇点，并且所加多重边的总权最小。 第*页 7.7 中国邮递员问题 中国邮递员问题的求解方法：奇偶点图上作业法 第一步：确定第一个可行方案 根据任何一个图中，奇点个数必为偶数。我们可以将图中的奇点配成对。对每一对奇点之间的链上增加多重边，可使新图中必无奇点。 第*页 7.7 中国邮递员问题 第二步：调整可行方案，使重复边总权下降 （1）在最优方案中，图的每一边上最多有一条重复边。 （2）在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半。 第*页 7.7 中国邮递员问题 第三步：判断最优方案 若每一可行方案满足上述（1）和（2），则该方案即为最优方案；否则，对方案继续调整，直到（1）和（2）满足为止。 第*页