西交《运筹学》重要知识点解析和例题分析第六部分.doc

奥鹏远程教育中心助学服务部 运筹学重要知识点解析和例题分析第六部分一图的基本概念定义一个图G是指一个二元组(V(G),E(G)，即图是由点及点之间的联线所组成。其中: 1）图中的点称为图的顶点(vertex)，记为：v2）图中的连线称为图的边(edge)，记为：，是边 e 的端点。3）图中带箭头的连线称为图的弧(arc)，记为：，是弧 a 的端点。 要研究某些对象间的二元关系时，就可以借助于图进行研究分类 无向图：点集V和边集E构成的图称为无向图(undirected graph)，记为： G(V，E) 若这种二元关系是对称的，则可以用无向图进行研究 有向图：点集V和弧集A构成的图称为有向图(directed graph) ，记为：D(V，A) 若这种二元关系是非对称的，则可以用有向图进行研究 有限图: 若一个图的顶点集和边集都是有限集，则称为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.图的特点：1 图反映对象之间关系的一种工具，与几何图形不同。2 图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。3 图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任意性。4 图的表示不唯一。如：以下两个图都可以描述“七桥问题”。点(vertex)的概念1 端点：若e =u，v E，则称u，v 是 e 的端点。2 点的次：以点 v 为端点的边的个数称为点 v 的次，记为：。在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为或 dG(v).在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d -(v). 称= d+(v)+d -(v)为顶点v的度或次数3 奇点：次为奇数的点。4 偶点：次为偶数的点。5 孤立点：次为零的点。6 悬挂点：次为1的点。定理 推论 任何图中奇点的个数为偶数链(chain)的概念1 链：一个点、边的交替的连续序列称为链，记为。2 圈(cycle)：若链的，即起点终点，则称为圈。3 初等链（圈）：若链（圈）中各点均不同，则称为初等链（圈） 。4 简单链（圈） ：若链（圈）中各边均不同，则称为间单链（圈） 。圈一定是链，链不一定是圈路PATHv 路(path)：顶点和边均互不相同的一条途径。v 若在有向图中的一个链中每条弧的方向一致，则称为路。（无向图中的路与链概念一致。）v 回路(circuit)：若路的第一个点与最后一个点相同，则称为回路。v 连通性:点i和j点是连通的：G中存在一条（i，j）路G是连通的：G中任意两点都是连通的eaugybwdxfcv例 在右边的无向图中：途径或链：迹或简单链：路或路径：圈或回路：v4e5v1e2v3v2e3e4e6e1在右边的有向图中： 链 不是路 链 且是路 链 是回路连通图简单图(simple graph)：一个无环、无多重边的图称为间单图。多重图(multiple graph)：一个无环，但有多重边的图称为多重图。连通图(connected graph)：若图中任何两点间至少有一条链，则称为连通图 。否则，为不连通图。连通分图：非连通图的每个连通部分称为该图的连通分图。基础图：去掉有向图中所有弧上的箭头，得到的图称为原有向图的基础图。图G(V, E)是多重图图G(V, E)为不连通图但G(V, E)是G的连通分图其中：Vv1, v2, v3, v4Ee1, e2, e3, e4, e5, e6, e7v1v2v3v4e1e2e3e4e5e6e7e8v5v6v7二树（tree）1、树的定义树：一个无圈的连通图称为树。2、树的性质（1） 设图G(V, E)是一个树，点数P(G) 2，则 G 中至少有两个悬挂点。（2） 图G(V，E)是一个树G不含圈，且恰有p-1条边（p是点数）。（3） 图G(V，E)一个树 G 是连通图，且q(G)p(G)1 （q是边数）。（4） 图G(V，E)是树 任意两个顶点之间恰有一条链。图的支撑树(spanning tree)1 支撑子图：设图G(V，E)，图G(V，E)的VV，E E，则称G是G的一个支撑子图。 图G(V，E)的点集与图G(V，E)的点集相同，VV，但图G(V，E)的边集仅是图G(V，E)的子集E E。2 支 撑 树：设图T(V，E)是图G(V，E)的支撑子图，如果T(V，E)是一个树，则称 T 是 G 的一个支撑树。特点边少、点不少。最小树(minimum spanning tree)问题（1） 最小树定义如果T(V，E)是 G 的一个支撑树，称 T 中所有边的权之和为支撑树T的权，记为W（T），即：若支撑树T* 的权W（T*）是G的所有支撑树的权中最小者， 则称T* 是G 的最小支撑树（最小树）， 即：W（T*） min W(T)。（2）求最小树的算法（minimum spanning tree algorithm）1） 破圈法：在图G中任取一个圈，从圈中去掉权数最大的边，对余下的图重复这个 步骤， 直到G中不含圈为止，即可得到 G 的一个最小树。避圈法是一种选边的过程，其步骤如下：1. 从网络D中任选一点，找出与相关联的权最小的边，得第二个顶点；2. 把顶点集V分为互补的两部分，其中三最短路问题最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.1) 求赋权图中从给定点到其余顶点的最短路.2) 求赋权图中任意两点间的最短路.定义 1) 若H是赋权图G的一个子图，则称H的各边的权和为H的权. 类似地，若P(u,v)是赋权图G中从u到v的路,称称为路P的权2) 在赋权图G中，从顶点u到顶点v的具有最小权的路P*(u,v)，称为u到v的最短路3) 把赋权图G中一条路的权称为它的长，把(u,v) 路的最小权称为u和v之间的距离，并记作 d(u,v). 给定一个赋权有向图D ( V，A ) ,对每一条弧，相应地有权，又有两点,设 p 是 D 中从到的一条路，路 p 的权是 p 中所有弧的权之和,记为最短路问题就是求从到的路中一条权最小的路 p*:最短路问题的算法 下面仅介绍在一个赋权有向图中寻求最短路的方法双标号法（Dijkstra算法），它是在1959年提出来的。目前公认，在所有的权时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点到任意一个点的最短路。方法：标号法（Dijkstra，1959）给每点标号。其中为至的最短距，为最短路上的前一点。标号法步骤：四 最大流问题 流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。网络赋权图，记D=（V，E，C），其中为边上的权。网络分析主要内容最小部分树、最短路、最大流。1. 问题 已知网络D=（V，A，C），其中V为顶点集，A为弧集，为容量集，为弧上的容量。现D上要通过一个流，其中为弧上的流量。问应如何安排流量可使D上通过的总流量v最大？例如：v4v2vsv1vtv32131453252. 数学模型。3. 基本概念与定理2）可增值链（增广链）（3） 截集与截量截量：截集上的容量和，记为 截集上的流量和相应于截集的反向弧上流量和（4） 流量与截量的关系最大流最小割定理：（5） 最大流的判别条件4. 解法步骤：五网络计划图网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。工 序ij持续时间工程名称或代号箭尾事项箭头事项在网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图： 工序之间的关系v 紧前工序：紧排在本工作之前的工作；且开始或完成后，才能开始本工作。v 紧后工序：紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。v 虚工序：不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻辑关系。网络图的要求v 相邻节点只能是一个工序的相关事项；v 网络图中不能有缺口和回路绘制工程网络图1）顺序：按工序先后从左至右；2）图中弧（箭线）：表示工序； 顶点（结点）：表示相邻工序的时间分界点，称事项，用i表示。 相邻弧：表示工序前后衔接关系，称紧前（后）工序；3）要求：图中不得有缺口、回路和多重边。缺口：多个始点或多个终点的现象。（应当只有一个始点和终点）处理方法：增加虚工序。回路：方向一致的闭合链。多重边：两点间有多于一条的边。AB处理方法：增加虚工序。网络计划图的时间参数计算网络图中工作的时间参数。它们是：v 工作持续时间(D)； v 工作最早开始时间（ES）； v 工作最早完成时间（EF）；v 工作最迟开始时间（LS）；v 工作最迟完成时间（LF）；v 工作总时差（TF）；v 工作自由时差（FF）。工作持续时间(D)作业时间 单时估计法（定额法）v 每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间； v 工作持续时间：Q 工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；R 可投入人力和设备的数量；S 每人或每台设备每工作班能完成的工作量；n 每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。 三时估计法在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。最可能时间。在正常条件下，完成工作所需要时间。记作m。悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值： 工作最早开始时间ES和工作最早完成时间EF。工作的最早开始时间ES是紧前工序最早结束时间。ES=TE（i）， EF=ES+。工作最迟开始时间LS与工作最迟完成时间LF。工作的最迟完成时间LF是工作在不影响工期下最迟结束时间。LF=TL（j） LS=LF-TL(j)。最后一项工作的最迟完成时间LF等于其最早完成时间EF。网络时间的图示法1. 节点时间（事件时间）事件最早可能发生时间TE：顺向求和取大事件最迟必须发生时间TL：反向求差取小事件最早可能发生时间Te事件最迟必须发生时间TlxyiMax(+)ji箭尾事项箭头事项A（D）tijabcdMin(-)ji箭尾事项箭头事项A（D）tijabcda+tijdad-tij工序ALFLSESEF开始完成可能必须最早最迟2.工序时间3.工作时差：指工作有机动时间。 工作总时差TF（i-j） 在不影响工期的前提下，工作所具有的机动时间ji箭尾事项箭头事项A（D）tijabcd总时差为零的工序即关键工序a+tijdad-tij工序ALS-ES=LF-EF（2）工作单时差EF（i-j）在不影响其紧后工作最早开始的前提下，工序最早可能完工时间所具有机动时间（3）工作自由时差FF（i-j）在不影响其紧后工作的最迟开始的前提下，工作所具有机动时间六、工序时间不确定的工程计划网络问题 （计划评审技术PERT）。网络优化v 时间优化缩短工程工期问题v 时间资源优化工程的时间费用分析缩短工程工期保证工程质量，同时不增加人力物力的前提下，尽量缩短工期。做法： （1）确定关键路线明确关键工序，设法缩短关键工序的时间；（2）在非关键工序上挖掘潜力；（3）多采用平行作业和交叉作业；（4）注意关键路线的变化七：例题分析v1v3v2v5v4v6v7252463112424例1： 要在5个城市架设电话线，使城镇之间能够通话两镇直接连接，每两个城镇之间的架设电话线的造价如下图所示，各边上的数字为造价（ 单位：万元 ）。问：应如何架线，可使总造价最小？v1v3v2v5v4v6v7252463112424解：1 破圈法：2 避圈法：v1v3v2v5v4v6v7252463112424总造价：W(T*)22112210 （万元）v4v2vsv1vtv3（3，3）（2，2）（4，3）（5，1）（2，1）（5，3）22（3，0）（1，1）（1，1）00例2： 用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量=1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截例3：为筹建某餐馆，需制定计划。