运筹学图与网络分析.ppt

1、a，第一，五章图论和网络分析，图的基本概念，网络分析，最小支撑树问题最短路径问题网络最大流问题，a，2，图论起源：哥白尼堡七桥问题，问题：一个散步者从哪个陆地出发，可以过七桥，并且每桥只有一次，最后是出发点结论：每个节点关联的边数是双位数、a、3、1图的基本概念，由点和边组成，标记为G=(V，e )，其中V=(v1，v2，vn )为节点的集合，E=(e1，e2，em )为边的集合。 点表示研究对象，边表示研究对象间的特定关系，1 .图、p14、a、4、图、无向图、G=(V，e )、有向图、D=(V，a )、例1 :哥白尼堡桥问题的图是无向图。 的双曲正切值。2、图分类、a、5、示例、图1、a、

2、6、图2、a、7、3、网络链接和网络链接、环和环、网络链接、点和点相交的系列、路、点和弧相交的系列、电路、起点=终点的路、无向图：网络链接和路的点不同4、连通图，G1是不连通图，G2是连通图，例如，a、9、5、支撑子图，如果图G=(V，e )和G=(V，e )，V=V，则将g称为g的支撑子图。G2是G1的支持子格拉夫，例如，a、1.0，G2是G1的子格拉夫，例如，a、1.1、6、权利图(网络)，图的各边具有表示一定的实际意义的权重，被称为权利图。 标记为D=(V，a，c )。 例如：a，1.2，2最小支撑树问题，本节的主要内容：树，支撑树，最小支撑树：a，1.3，树：无圈连通图，标记为t。 一

3、、树的概念和性质、树的性质： (1)树的任意两点之间只有一条链(2)树中除了一条边的情况下，树不连通，因此树连通图，并且具有最小边数的图形(3)在树中不相邻的两点之间增加一条边，正好旋转一圈(3) 如果a、1.4、一个图G=(V，e )的支持子图T=(V，e )构成树，则t被称为g的支持树，也被称为生成树。 二、图支撑木、例、a、1.5、例某处新建5处居民点，拟修建道路连接5处，可测量该道路并按图铺设。 就像五个居住地有道路相连一样，至少要铺几条路？ 解：为了实现图的支撑树问题，这个问题总共需要铺设4条路。 用图的支持树的应用例，a，1.6，破轮法求出下图的1个生成树。 求、a、1.7、最小支

4、持树：网络支持树，将其权利最小化。 三、最小支持树问题，算法1 (破丸法): 在给定权利的连通图中查找圈，去除圈中权重最大的边1条(如果2条以上的边是权重最大的边，则任意去除1条): 如果多馀的图中不包含圈，则计算结束不然的话，我回答。a、1.8、例子中的最小支撑树、解：5、5.5、v1、v2、v3、v4、v5、3.5、7.5、4、2、3、a、1.9、算法2 (回避法):从某一点开始，将边按权重从小到大的顺序添加到图中，如果出现轮廓，则向其中的最大边a、2.0、最小生成树的例子：某6个城市间的公路网络如图所示，要求沿已知长度的道路连接6个城市的电话线网络，电话线的总长最短。a、2.1、v1、v

5、2、v3、v4、V5、1、4、2、3、1、3、5、2、a、2.2，向居民区提供瓦斯气体，如图所示，铺设各用户点的瓦斯气体管道设计最经济的瓦斯气体管路，寻求必要的总费用。 练习、a、2.3、现有瓦斯气体工作站a，向居民区提供瓦斯气体，并如图所示，用图上的数字表示铺设各个用户点的瓦斯气体管道所需的费用(单位：万元)。 设计最经济的瓦斯气体管路，寻求必要的总费用。a，2.4，例如现在有瓦斯气体站a，向居民区提供瓦斯气体，居民区各用户所在的地方用图表示，用图上的数字表示铺设各用户点的瓦斯气体管道所需费用(单位：万元)。 设计最经济的瓦斯气体管路，寻求必要的总费用。a、2.5，例如现在有瓦斯气体站a，向

6、居民区提供瓦斯气体，居民区各用户所在的地方如图所示，铺设各用户点的瓦斯气体管道所需费用(单位：万元)如图上数字所示。 设计最经济的瓦斯气体管路，寻求必要的总费用。a、2.6，例如现在有瓦斯气体站a，向居民区提供瓦斯气体，居民区各用户所在的地方如图所示，铺设各用户点的瓦斯气体管道所需费用(单位：万元)如图上数字所示。 设计最经济的瓦斯气体管路，寻求必要的总费用。a、2.7，例如现在有瓦斯气体站a，向居民区提供瓦斯气体，居民区各用户所在的地方如图所示，铺设各用户点的瓦斯气体管道所需费用(单位：万元)如图上数字所示。 设计最经济的瓦斯气体管路，寻求必要的总费用。 a，2.8，例如现在有瓦斯气体站a，

7、向居民区提供瓦斯气体，居民区各用户所在的地方用图表示，用图上的数字表示铺设各用户点的煤气管道所需费用(单位：万元)。 设计最经济的瓦斯气体管路，寻求必要的总费用。 这是最经济的瓦斯气体管道，所需的总费用是2.5万元、a、2.9、3最短路径问题，最短路径问题是在一个网络(赋权图)中寻找从起点到某个节点的最短路径。 现在求出从1到6的距离最短的路径。 a，3.0，基本思想：从起点vs开始，依次对各节点vj附加标签条dj，vi，其中，dj是从起点vs到vj的最短距离，vi是该最短路径上的前一个节点将vjVB全部考虑在内，其中viVA、vjVB选择离起点v1的距离最短的(mindicij)vvvvj，

8、向vj附加标签条，(4)在终点vn附加dn，vi之前反复进行(2)、(3)，则dn为v1 vn的最短距离，向相反方向(1)在起点v1上全部考虑0、v1、0、v1、v1、(3)这样的边vi、vvvvjvb，在其中选择距起点v1的距离最短的(mindicij)vvvvvj，对vvj附加标签条，(4)在终点vn上附加dn、vi为止(1)起点v1为0，v1，3，v1，a，3.4，0，v1，1，v1，5，v3，a，3.5，0，v 1，1，v 1，3，v 1，5，v 3，6，v2，a，3.6，0，v 1，v 1，v 1，3 v 1、1、v 1、3、v 1、5、v 3、6、v 2、9、v5、1.0、v5、a

9、、3.8、0、v 1、1、v 1、3、v 1、5、v 3、6、v 2、9、v5、1.0、v5、1.2、v5，此时终点v9已经是1.2、v5 v1，1，v1，3，v 1，5，v 3，6，v 2，9，v5，1.0，v 5，1.2，v 5，v 1到v9的最短距离为v1v3v5v9，最短距离为1.2，p119，a，4.0，练习：使用直方图算法，与下图的v 1到V8的最短距离a、4.1、伊卡斯线路：1. v1- v2- v4- V6- V8.v1- v2- v4 v7- V8的最短长度：在1.2、a、4.2、教室练习的无向图的情况下，求出从网络中的v1到V7的最短长度。 没有a，4.3，教室练习的方向图

10、的情况下，v1，v1，v2，v4，v5，v6，v 7，2，5，5，7，1，3，0，v 1，2，v 1，3，v 1，4，v2/v 4，7，v 3，8，v 5，1.3，5 没有教室练习的方向图的情况下回答(2)、v1、v2、v3、v4、v5、v6、v 7、2、5、3、5、7、5、7、1、3、0、v1、2、v1、3、v1、4、v2/v4,7、7、v3 所以工厂必须决定每年年初设备是否更新。 在购买设备时，如果要继续使用每年必须支付购买费用的旧设备，必须支付修理和运转费用。计划期间(5年)内的年购买费、修理费和运营费如表所示，工厂制定今后5年的设备更新计划，听取包括购买费、修理费和运营费在内的总费用最

11、小化的方案。a、4.6、最短路模型的应用设备更新问题，分析：节点： V=v1、v6、vi表示第I年，弧： A=(vi，vj )表示第I年开始购买，第j年开始使用i=1，5； j=2，6，表示权利cij: i年初j年初的费用，即cij=i年初购买费(j-i )年的修理费、通道：更新战略。 例如，v1-v2-v6表示第1年购入并利用第2年的更新，到第5年年末为止持续利用的更新战略、a、4.7、最短路的模型的应用设备的更新问题：0、v1、v1、1.6、v1、2.2、v1、3.0、v1、5.3、V6 解1.6、2.2、3.0、4.1、1.7、2.3、3.1、1.7 23，18，建模：可以求出v1-v4

12、-v6这两个最佳更新策略。 v1-v4-v6在第一年购买设备，第五年底的V1-v3-v6在第一年购买设备，第三年更新，到第五年底的最佳费用为5.3，a， 在4.9中，计划期间(5年)内的年购买费、修理费和运营费如表所示，工厂制定今后5年的设备更新计划，询问为了包含购买费、修理费而采用哪个方案，练习：设备更新问题、a、5.0、2.8、v4、v5、v6、2.3 2.5、2.6、2.9、3.0、4.2、6.0、8.5、3.2、44、62、33、45、30、a、51，算法的基本思路和步骤：首先，将任意点vi设定为任意点vj。 假定在没有弧的点之间存在有权利的弧。 从v1到vj的最短路径是从v1沿着该路

13、径到某一点vi，并且从弧(vi，vj )继续到vj。 从v1到vi的这条路也必然是从v1到vi的所有路中最短路的。 设P1j表示从v1到vj的最短路径长度，P1i表示从v1到vi的最短路径长度，则有下式：(Ford法(逐次近似法) (权重为负)、a、5.2、开始时用从v1到vj的直接距离作初始解。 从第二阶段，使用递归式：求出，进入第t阶段，成为从v1到各点的最短路长。 停止运算，从a、5.3、例：第二步骤开始，使用递归式，从a、5.5、第二步骤开始，使用递归式，为了求出从a、5.6、v1到各点的最短路，从d(vs， 如果vj )已知，则求出点vk以使得d(vs，vk) wkj=d(vs，vj

14、 )，并且接下来的(vk，vj )； 看到d(vs，vk )，求出d(vs，vi) wik=d(vs，vk )依次类推到达的点vi。 以这种方式，从vs到vj的最短短路是(vs，vi，vk，vj )，d(v1，v8)=6，并且d(v1，v6) w68=(-1) 7，因为v6是d(v1，v3) w36=d(v1，v6)，所以v3是d(v1，v6)。a、5.9、4网络最大流量问题，引用例：下图为v1V6的交通网络，权利代表对应的运输路线的最大通过能力，制定方案，使v1V6的运输产品数量最多。 其中v是顶点定径套，a是圆弧定径套，C=cij是容量定径套，cij是圆弧(vi，vj )上的容量。 在现在

15、的d阶段通过流程f=fij。 在此，fij是弧(vi，vj )上的流程。 问题：如何安排产水量fij使d上通过的总产水量v最大？ 一、一般提法、a、6.1、二、最大流问题的数学模型、max v=v(f )、容量限制、平衡限制、P125、满足上述所有限制条件的流成为可能的流。a、6.2、(1)容量条件：每个电弧(vi、vj)A都有0 fij cij。 (2)平衡条件：关于着火温度vs，关于着火温度vt，关于中间点，存在可执行流程f的产水量(着火温度的净喷出量或着火温度的净输入量)，1、将满足以下条件的流程f称为可执行流程： 3、基本概念和定理、a、6.3、可执行流程的特征： (1)容量条件(2)一个中间点的流入量和径流量的代数和为零。 (运输的作用) (3)出发点的总径流量和点的总流入量一定相等。 网络上的可执行流总是存在的。例如，零流v(f)=0是可以满足上述条件的流。 网络系统中的最大流问题是求可在给定网络上执行的流f并使其流v(f )达到最大值。 在a、6.4、可执行的流程中，将fijcij的弧称为饱和弧，将fijcij的弧称为非饱和弧，将fij0的弧称为零流弧。 2、饱和弧和零流弧，a、6.5、f是可能的流动，u是从vs到vt的链，u=顺方向弧，u-=逆方向弧。 如果u中弧不饱和，且u-中弧不为零，则u被称为关于f的扩展链。 显然，图中的扩展链路包括一条或多条、