网络优化

null 网 络 分 析 网 络 分 析马建华运筹学课件网络分析网络分析图与子图 图的连通与割集 树与支撑树 最小树 最短有向路 最大流 最小费用流 最大对集运筹学课件图 与 子 图图 与 子 图图与网络 无向图的基本概念 网络的基本概念 关联矩阵和邻接矩阵 关联矩阵 邻接矩阵 主要结论 子图 运筹学课件网络分析无 向 图 的 基 本 概 念 无 向 图 的 基 本 概 念 无向图G：一个有序二元组(N,E),记为G=(N,E) G的点集合： （例如：图（1）中的 N=（1，2，3，4，5）是一个无向图 的点的集合） G的边集合：E={eij}且eij={ni,nj}为 图（1）无序二元组 eij的端点：有eij={ni,nj}，则称ni和nj 为eij的端点，且称eij 连接点 ni和nj 圈：两个端点重合为一点的边 （例如图（1）中的e11） 孤立点：不与任何边关联的点 （例如图（1）中的n5） 续（1）续（1）关联：一条边的端点称为这条边的关联 邻接：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的 有限图：点和边都是有限集合的图 空图：没有任何边的图 平凡图：只有一个点的图 简单图：既没有圈也没有两条边连接同一对点的图 续（2）续（2）完全图：每一对点之间均有一条边相连的图 二分图 G=(N,E)：存在的一个二分划(S,T)，使得G的每 条边有一个端点在S中，另一个端点在T中 完全二分图 G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图 简单图G的补图 :与G有相同顶点集合的简单图， 且 中的两个点相邻当且仅当它们在G中 不相邻返回网 络 的 基 本 概 念网 络 的 基 本 概 念运筹学课件♂有向图G：一个有序二员组(N,A)，记为G=(N,A) G的弧集合：A={aij}且aij={ni,nj}为有序二元组 ， 若aij={ni,nj}，则称aij从ni连向nj， ni称为aij的尾， nj为 aij的头，ni称为nj的先辈，nj称为 ni的后继 有向图G的基本图：对于G的每条弧用一条边代替后得到的无向图 （有向）网络G：对（有向）图G的每条边（弧）都赋予一个实数， 并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络 关 联 矩 阵关 联 矩 阵运筹学课件关 联 矩 阵 示 例关 联 矩 阵 示 例图（7）的关联矩阵是 图（8）的关联矩阵是 返回邻 接 矩 阵邻 接 矩 阵邻 接 矩 阵 示 例邻 接 矩 阵 示 例图（7）的邻接矩阵是 图（8）的邻接矩阵是 返回主 要 结 论主 要 结 论运筹学课件网络分析♂子 图子 图运筹学课件网络分析♂图的连通与割集 图的连通与割集  图的连通 无向图 有向图 图的割集   概 念 主要结论 ♂运筹学课件网络分析无 向 图 的 路无 向 图 的 路运筹学课件网络分析图G中路：一个点和边交替序列 (ni,eij,nj,…,nk,ekl,nl)， 简单路：边不重的路 初级路：点不重的路 回路：在G中，一条至少包含一个边并且ni=nl的{ ni,nl}路 简单回路：边不重的回路 初级回路：点不重的回路 连 通 性连 通 性点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连通的 连通分支：G的极大连通子图 命题6.2.1 设 G有p个连通分支，则G的邻接矩阵可以表示成分块矩阵 返回有 向 路有 向 路运筹学课件有向图G中的一条有向路：个点和弧的交错序列 (ni,aij,nj,…,nk,akl,nl)，记为(ni,nl)有向路 简单有向路：弧不重的有向路 初级有向路：点不重的有向路 有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路 简单有向回路：弧不重的有向回路 初级有向回路：点不重的有向回路 点i和点j是强连通的：G中存在一条(i,j)有向路，也存在一条(j,i)有向路 G是强连通的：G中任意两点都是强连通的 G的强连通分支：G的极大连通子图 命题6.2.2 设G有p个强连通分支，则G的邻接矩阵可以表示成如下形式：返回强连通性割 集割 集运筹学课件♂割 集 的 性 质割 集 的 性 质运筹学课件网络分析♂树 与 支 撑 树树 与 支 撑 树树及其基本性质 概念及符号 基本性质 支撑树及其基本性质 概念及符号 基本性质 ♂运筹学课件网络分析概 念 及 符 号概 念 及 符 号♂运筹学课件网络分析树 的 基 本 性 质树 的 基 本 性 质♂运筹学课件网络分析概 念 及 符 号概 念 及 符 号♂运筹学课件网络分析支 撑 树 的 基 本 性 质支 撑 树 的 基 本 性 质♂运筹学课件网络分析最 小 树最 小 树最小树及其性质 求最小树的Kruskal算法 算法步骤 算例 算法复杂性 Dijkstra算法 算法步骤 算例 算法复杂性 Scilab实现♂运筹学课件网络分析最 小 支 撑 树 最 小 支 撑 树 ♂运筹学课件算 法 步 骤 算 法 步 骤 运筹学课件♂算 例 算 例 运筹学课件网络分析计 算 的 迭 代 过 程 计 算 的 迭 代 过 程 运筹学课件网络分析♂算 法 复 杂 性 算 法 复 杂 性 运筹学课件网络分析♂算 法 步 骤 算 法 步 骤 运筹学课件网络分析♂算 例 算 例 运筹学课件网络分析计 算 的 迭 代 过 程 计 算 的 迭 代 过 程 运筹学课件网络分析♂算 法 复 杂 性 算 法 复 杂 性 运筹学课件网络分析♂Scilab 实 现Scilab 实 现用Scilab语句求解下列网络的最小树 1 3 2 4 2 4 2 4Scilab 命 令 及 结 果Scilab 命 令 及 结 果clear tail=[1 1 2 2 2 3 3 4]; head=[2 3 3 4 5 4 5 5]; g=make_graph('g',0,5,tail,head); //制图 weight=[1 2 2 4 3 4 4 2]; //权向量 g('edge_weight')=weight; t = min_weight_tree(g) //用Scilab命令求解 t = ! 1. 2. 8. 5. ! //结果 返回最短有向路最短有向路最短有向路方程 求最短有向路的Dijkstral算法 算法步骤 算例 算法复杂性 Scilab实现♂运筹学课件网络分析最 短 有 向 路 方 程最 短 有 向 路 方 程♂运筹学课件算 法 步 骤 算 法 步 骤 运筹学课件♂算 例 算 例 运筹学课件计算的迭代过程 计算的迭代过程 运筹学课件网络分析♂算 法 复 杂 性 算 法 复 杂 性 运筹学课件网络分析♂Scilab 实 现Scilab 实 现 用Scilab语言求解上述算例所示网络的最短有向路 Scilab语句： tail=[1 1 1 2 2 3 4 4 5 5 6];  head=[2 4 6 3 4 6 3 5 2 3 5];  g=make_graph('g',1,6,tail,head); //制图  weight=[5 3 4 3 2 2 7 5 4 1 6]; //权重  g('edge_weight')=weight; //将权重赋给已制的图   [p,lp] = shortest_path(1,6,g) //用Scilab命令求解点1和点6之间的最短有向路结 果结 果 lp =  1. p =  3. //结果   [p,lp] = shortest_path(1,5,g) //用Scilab命令求解点1和点5之间的最短有向路 lp =  2. p = ! 2. 8. ! //结果 返回最 大 流最 大 流最大流最小割定理 基本概念 主要结论 最大流算法 算法步骤 算例 算法复杂性 Scilab实现♂运筹学课件网络分析基 本 概 念基 本 概 念♂运筹学课件主 要 定 理主 要 定 理运筹学课件网络分析算 法 步 骤 算 法 步 骤 运筹学课件算 例 算 例 运筹学课件计 算 的 迭 代 过 程 计 算 的 迭 代 过 程 运筹学课件网络分析♂算 法 复 杂 性 算 法 复 杂 性 运筹学课件♂Scilab 实 现Scilab 实 现用Scilab语言求解以上算例所示网络的最大流 Scilab语句： clear  tail=[1 1 2 2 3 3 4 5 5 5];  head=[2 3 3 4 4 5 6 2 4 6];  g=make_graph('g',1,6,tail,head); //制图  maxcap=[8 2 6 5 5 8 9 3 6 7]; //容量  g('edge_max_cap')=maxcap; //将容量赋给已制的图   [v,phi,flag] = max_flow(1,6,g) //用Scilab语句求解最大流 结 果结 果flag =  1. phi = ! 8. 2. 3. 5. 4. 1. 9. 0. 0. 1. ! v =  10.返回最 小 费 用 流最 小 费 用 流最小费用流算法 规划形式 算法步骤 算例 算法复杂性 最特殊的最小费用流－－运输问题 规划形式 算法步骤 算例 Scilab实现♂运筹学课件问 题问 题♂运筹学课件网络分析线 性 规 划 形 式线 性 规 划 形 式运筹学课件网络分析对 偶 规 划对 偶 规 划运筹学课件网络分析♂算 法 步 骤 算 法 步 骤 运筹学课件♂算 例 算 例 运筹学课件网络分析计算的迭代过程（1） 计算的迭代过程（1） 运筹学课件网络分析 1，2，0 3,4,0 1,2,0 3,1,0 1,2,0(+s,2)(+s,2)(+a,2)计算的迭代过程（2）计算的迭代过程（2） 1,2,2 3,4,0 1,2,2 3,1,0 1,2,2 (+s,2)(+a,2)(+b,2)(-b,1)(+s,1)计算的迭代过程（3）计算的迭代过程（3）返回(-b,1)(+s,1)(+a,1)算法复杂性 算法复杂性 运筹学课件网络分析♂Scilab 实 现Scilab 实 现用Scilab语言求解以上算例所示网络的最小费用流 Scilab语句： clear tail=[1 1 2 2 3]; head=[2 3 3 4 4];  g=make_graph('g',1,4,tail,head);  cost=[1 3 1 3 1];  max_cap=[2 1 2 4 2];续续g('edge_cost')=cost;  g('edge_max_cap')=max_cap;  demd=[-3,0,0,3];  g('node_demand')=demd;  [c,phi,flag] = min_lcost_flow2(g) 结 果结 果flag =   1. phi =  ! 2. 1. 1. 1. 2. ! c =   11. 返回运 输 问 题运 输 问 题运筹学课件网络分析对 偶 规 划对 偶 规 划运筹学课件网络分析♂算 法 步 骤算 法 步 骤运筹学课件♂算例 算例 运筹学课件网络分析求如图所示运输问题的最优解 -45-20-30-30355040 8 6 9 9 9 12 13 7 14 9 16 5 迭 代 过 程 迭 代 过 程 运筹学课件网络分析 15 20 30 20 10 30 初始原可行解 续（1）续（1）86121014对偶解检验数null续（2）续（2） 15- 20 30+ 20- 10 30调整原始可行解续（3）续（3）03666101对偶解检验数续（4）续（4） 20- 45 15+ 5 10- 30调整原始可行解续（5）续（5）03366102对偶解检验数 返回最 大 对 集最 大 对 集二分图对集 基本概念 主要定理 二分图的最大基数对集 基本思想 算法步骤 算例 算法复杂性 Scilab实现 二分图的最大权对集－－分派问题 规划形式 算法步骤 算例 Scilab实现 ♂运筹学课件网络分析基 本 概 念基 本 概 念♂运筹学课件网络分析主 要 定 理主 要 定 理运筹学课件网络分析♂基 本 思 想基 本 思 想运筹学课件网络分析♂算 法 步 骤 算 法 步 骤 运筹学课件网络分析♂算 例 算 例 运筹学课件网络分析求下图a所示的二分图G的最大基数对集，若初始解如下图b所示 a b 迭 代 过 程（1）迭 代 过 程（1）运筹学课件31333333517810标号 增广路 标号 增广路 迭 代 过 程（2）迭 代 过 程（2） 标号 增广路 1257108返回算 法 复 杂 性 算 法 复 杂 性 运筹学课件♂Scilab 实 现Scilab 实 现用Scilab语言求解以上算例所示网络的最大基数对集 Scilab语句： clear  tail=[1 2 2 3 3 3 3 4 5 5 5];  head=[7 7 8 6 8 9 10 10 7 8 10];  g=make_graph('g',0,10,tail,head); //制图   [card,match] = best_match(g) //用Scilab命令求解 结 果结 果match = ! 7. 8. 6. 10. 0. 3. 1. 2. 0. 4. ! card = 4. 返回分 派 问 题分 派 问 题运筹学课件对 偶 规 划对 偶 规 划运筹学课件网络分析♂算 法 步 骤 算 法 步 骤 运筹学课件♂算 例 算 例 运筹学课件网络分析 1 2 3 2 2 1 3 2 4 2 3求如图所示的二分网络中的最大权对集 计算的迭代过程 （1）计算的迭代过程 （1）运筹学课件网络分析 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 2 4 1 0 2 1 2 1 3 1 2 2 3 2 标号 标号 =4 =1 =1 标号 标号 增广路计算的迭代过程（2）计算的迭代过程（2） 3 3 3 4 3 3 3 4 0 0 0 0 0 0 0 0 2 3 2 3 1 3 4 3 0 0 1 1 2 0 2 1 标号 标号 标号 标号 增广路 =3 =1 =1计算的迭代过程（3）计算的迭代过程（3） =1 =1 =2 4 4 4 4 2 3 2 3 0 1 0 0 1 1 0 0 1 3 4 3 1 1 1 0 1 0 1 1 标号 标号 标号 标号 增广路计算的迭代过程（4）计算的迭代过程（4） =1 =1 =1 1 返回 2 3 3 2 3 0 1 0 0 1 1 2 4 0 0 1 0 标号 标号 3Scilab 实 现Scilab 实 现用Scilab语言求解上述算例中所示二分网络的最大权对集 Scilab语句： Clear  ta=[9,9,9,9,1,1,2,2,2,3,3,3,4,4,4,5,6,7,8];  hea=[1,2,3,4,5,6,5,6,7,5,6,8,6,7,8,10,10,10,10];  n=10;  g=make_graph('foo',1,n,ta,head); //制图  maxed=ones(1,19);  g('edge_max_cap')=maxed;  cost=[0,0,0,0,4,3,2,3,3,4,2,3,1,3,2,0,0,0,0];  g('edge_cost')=cost;  demd=[0,0,0,0,0,0,0,0,-4,4];  g('node_demand')=demd;  [c,phi,flag] = min_lcost_flow2(g)返回结 果结 果 flag =   1. phi =   column 1 to 11  ! 1. 1. 1. 1. 1. 0. 0. 0. 1. 0. 0. !   column 12 to 19  ! 1. 1. 0. 0. 1. 1. 1. 1. ! c =   11. 返回