九网络优化模型.ppt

目录 图与网络 树 最短路问题 最大流问题 最小费用流问题 顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、次的基本概念 一、树：连通且不含环的无向图 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中vi表示7个学院办公室，图中的边为可能联网的途径，边上的所赋的权数为这条路线的长度，单位为百米，请设计一个网络能联系7个学院办公室，并使总的线路长度为最短 图与网络 树 最短路问题 最大流问题 最小费用流问题 结点i表示第i年的年初，当ij时，弧(i,j)表示第i年年初购买一辆新车并一直用到第j年年初。弧的长度cij表示：如果第i年年初购买一辆新车并这辆车在第j年年初卖掉更换一辆新新，从第i年年初到第j年年初期间总的净费用，于是有cij=(i,i+1,..j-1年的维护费用）＋（第i年年初购买新车的费用）－（第j 年年初该车的交易费用） 图与网络 树 最短路问题 最大流问题 最小费用流问题 最大流量问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出发点到收点的最大流量 例：某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如图所示，由于　管理的直径的变化，它的各段管道(vi,vj)的流量（容量）cij也是不一样的，cij的单位为万加仑/小时，如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运行多少加仑石油？ 设弧(vi,vj)上流量为fij，网络上总的流量为F，则有 目标函数：max F=f12+f14 约束条件： f12=f23+f14 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fij ≤cij fij≥0 i=1,2,,,6 j=2,3,,,,7 最大流问题网络图论的解法 1、对网络上弧的容量的表示作改进，对条一条弧(vi,vj)的容量用一对数据cij,0标在弧(vi,vj)上，以cij靠近vi点，0靠近vj点，表示从vi到vj容许通过的容量为cij，而从vj到vi容许通过的容量为0，这样可能省云弧的方向 求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每条弧顺流方向的容量都大于零，如果不存在这样的路，则已求得最大流 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf (3)在这条路上，减少每条弧的顺流容量pf，同时增加这些弧的逆流容量pf,返回步骤（1） 由于所选路不一样，计算过程也不一样，但最终结果是一样的，为了使算法快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路 第一次迭代 选择路为v1-v4-v7，弧（v4,v7)的顺流容量为2，决定pf=2，改进网络流量 第二次迭代 选择路为v1-v2-v5－v7，弧（v2,v5)的顺流容量c35=3，决定pf=3，改进网络流量 第三次迭代 选择路为v1-v4-v6－v7，弧（v4,v6)的顺流容量c46=1，决定pf=1，改进网络流量 第四次迭代 选择路为v1-v4-v3－v6 －v7 ，弧（v3,v6)的顺流容量c36=2，决定pf=2，改进网络流量 第五次迭代 选择路为v1-v2-v3－v5 －v7 ，弧（v2,v3)的顺流容量c23=2，决定pf=2，改进网络流量 网络图中，逆流就是流过每条路径的流量 增广链 用Excel求解最大流和最小费用最大流问题 最小费用最大流问题的Excel电子表格求解 例1，一个邮递员应选择怎样的送信路线，使得他走完所负责的全部街道后，回到邮局，所走的路程最短（不重复或少重复） 例2　“七桥问题”哥尼斯堡（现叫加里宁格勒）有一条河，河中有二个岛，河上有七座桥，数学家欧拉证明了从一点出发，经过每座桥一次且仅一次，再回到原出发点是办不到的。这就所谓的一笔画问题 一笔画问题 （1）欧拉图：图中每个顶点的次均为偶数的图 （2）欧拉链：经过图中G的每一条边仅一次的链 以下两种图可以一笔画出 （1）每个顶点的次均为偶数的图，画时可以从任一点出发 （2）有且仅有两个奇点的图，画时必须从其中一个奇点出发，在另一个奇点结束 除以上两种情形，其图一律不能一笔画出 在例1中，由于每个顶点的次均为偶数，所以可以一笔画出，也即邮递员可以一次走完所有街道，最后回到邮局，可任选一个点为出发点。 可以把七桥问题看作为如下图的一笔画问题。 由于d(A)=3,d(B)=3,d(C)=5,d(D)=3，即度为奇数的个数为4，所以不能一笔画出，也即不能一次走完七座桥。 试确定以下图能否一笔画出？ 第五节 最小费用流问题 1 3 2 7 4 5 6 8 9