线性规划-图与网络分析

1、图与网络是专门研究图的理论图与网络是专门研究图的理论 图论中的图是用点和边（弧）来反图论中的图是用点和边（弧）来反映系统中各对象之间相互关联的关系，映系统中各对象之间相互关联的关系，它与几何图、工程图是不一样的，图中它与几何图、工程图是不一样的，图中点的相对位置、点与点之间连线的长短点的相对位置、点与点之间连线的长短曲直，对于反映对象之间的关系并不是曲直，对于反映对象之间的关系并不是重要的。重要的。 简单图与多重图例：5、路：简单路（边不同）；、路：简单路（边不同）； 初等路（点也不同）初等路（点也不同）. 圈（回路）：圈（回路）：连通图与非连通图连通图与非连通图（1）指边或弧的有关数量指标。

2、根据实指边或弧的有关数量指标。根据实 际背景可赋予不同含义，如距离、时间、际背景可赋予不同含义，如距离、时间、 费用、容量等。费用、容量等。（3）指定了指定了的的的的 。包括无向网络、有向网络、混合。包括无向网络、有向网络、混合 网络。网络。（2）图图G中点、边中点、边(弧弧) 以及边（弧）上的以及边（弧）上的 权的总体，称为赋权图。权的总体，称为赋权图。(1) 、权矩阵(2)、关联矩阵(3)、相邻矩阵V3V4V6无向图有向图V4连通图连通图树树练习题练习题1：下图中：下图中1表示某生产队的水源地，表示某生产队的水源地，其它图形表示水稻田，用堤埂分割为很多小其它图形表示水稻田，用堤埂分割为很多

3、小块。为了用水灌溉，需要挖开一些堤埂。问块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少堤埂，才能使水浇灌到每小块最少挖开多少堤埂，才能使水浇灌到每小块稻田。稻田。 123456789101112将水源地及每小块稻田各用一个点来表示，边表示它们之间有堤埂相连，那么连接这些点的树图的边数即为至少要挖开的堤埂数。在任一图G=（V，E）中，当点集V确定后，树图是G中边数最少的连通图。练习题2：如图所示，有一菜园被田埂分割为6块，现菜园各块均灌溉了水，问至少需要打通多少田埂才能把所有的水排放掉？ 若将树作为图的一个子图来考虑若将树作为图的一个子图来考虑例：连通图G支撑子图1是一个树支撑子图2是一个树

4、支撑子图3是一个树支撑子图4是一个树支撑子图5是一个树TijwTWmin*)(步骤：步骤：1、先任取一个圈，从圈中去掉一条权最大的边，若在同一个、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最大边，则任选其中的一条边去掉。圈中有几条都是权最大边，则任选其中的一条边去掉。2、在余下的子图中，重复上述步骤，直至没有圈为止。、在余下的子图中，重复上述步骤，直至没有圈为止。避圈法：开始选一条最小权的边，在以后的每一步中，避圈法：开始选一条最小权的边，在以后的每一步中，总从未被选取的边中选一条权最小的边，并使之与已总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，如果

5、同时有几条都是最小权的边，选取的边不构成圈，如果同时有几条都是最小权的边，则可从中任选一条。则可从中任选一条。23464524练习练习1：上图表示：上图表示5个村庄的线路图，每边旁的数个村庄的线路图，每边旁的数字表示村庄之间线路的长度，现要求沿线路架设字表示村庄之间线路的长度，现要求沿线路架设有线广播线，不仅使各村都能听到有线广播，而有线广播线，不仅使各村都能听到有线广播，而且使广播线总长度最短。且使广播线总长度最短。v1331728541034v7v6v5v4v2v3224234423v1331723v7v6v5v4v2v3答案：答案：11，19PijwPWmin*)(管道铺设、线路安排、管

6、道铺设、线路安排、 厂区布局、设备更新等。厂区布局、设备更新等。网络中所有的弧权均网络中所有的弧权均 ，即，即 。0ijw ： 标号标号 P P（固定标号或永久性标号）（固定标号或永久性标号）从始点到该标号点的最短路权。从始点到该标号点的最短路权。 标号标号 T T（临时性标号）（临时性标号）从始点到该标号点的最短路权从始点到该标号点的最短路权。jjlvpvT11)(),(min jv s svj jv Avvj),(1 jv 第二步：考虑满足条件第二步：考虑满足条件 的所有点的所有点 ； 具有具有T 标号，即标号，即 ， 为为T 标号点集。标号点集。 修改修改 的的T标号为标号为 ，并，并将

7、结果仍记为将结果仍记为T(vj)0)(1vp 第一步：始点标上固定标号第一步：始点标上固定标号 ,其余各其余各点标临时性标号点标临时性标号 T(vj)= , j 1;第三步：若网络图中已无第三步：若网络图中已无T标号点，停止标号点，停止计算。否则计算。否则,令令 , 然后将然后将 的的T 标号改成标号改成P 标号标号 ，转入第，转入第二步。二步。此时，要注意将第二步中的此时，要注意将第二步中的 改为改为 。 1v 0jv )()(min0jsvjvTvTj 0jv 1v 4v1v2v3v4v7v6v8456475541v59674v1v2v3v4v6v5v722561413412步骤步骤 考察

8、点考察点 T标号点集标号点集 标标 号（号（ 表表P标号）标号）1v1v2，v7v1 v2 v3 v4 v5 v6 v7 0 - - - - - - 0+20+5 2 5 - - - - 23456v2v3v4v5v6v3，v7v4，v7v5，v6，v7v5，v72+22+42+6 4 6 8 - -4+14+3 5 8 7 - 5+45+1 5+4 8 6 96+2 8 8v78+18反向追踪，得到最优路线：反向追踪，得到最优路线：v1 v2 v3 v4 v6 v7v5若先把若先把v7的标号改为永久性标号，的标号改为永久性标号，该怎麽继续作下去？该怎麽继续作下去？56v6v7v5，v7v5v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9 5127563425527313571练习1：求1275634231351(0)(2)(3)(4)(7)(8)(13)1275634223351(0)(2)(3)(4)(7)(8)(13)5273121344784