第六章-运筹学图与网络优化.ppt

第六章图与网络优化 第六章图与网络优化 第1节图的基本概念第2节树第3节最短路问题第4节网络最大流问题 第1节图的基本概念 例1 我国北京 上海等十个城市间的铁路交通图如下图所示 第1节图的基本概念 例2 有甲 乙 丙 丁 戊五个球队 他们之间的比赛情况如下图所示 第1节图的基本概念 一 图的基本概念图 由一些点及一些点之间的连线组成 边 两点之间不带箭头的连线 弧 两点之间带箭头的连线 无向图 由点及边组成 有向图 由点及弧组成 第1节图的基本概念 图例 第1节图的基本概念 二 无向图的基本概念端点 两个点vi vj属于V 边 vi vj 属于E 称vi vj是边的端点 关连边 边 vi vj 是点vi及点vj的关连边 环 边的两个端点相同 多重边 两个点之间多于一条的边 简单图 不含环和多重边的无向图 多重图 不含环 但含有多重边的无向图 第1节图的基本概念 次 以点vi为端点的边的个数 悬挂点 次为1的点 悬挂边 连结悬挂点的边 奇点 次为奇数的点 偶点 次为偶数的点 孤立点 次为零的点 第1节图的基本概念 图例 不连通图 第1节图的基本概念 三 无向图的基本性质任何无向图中 顶点次数的总和等于边数的2倍 任何无向图中 次为奇数的顶点必为偶数个 第1节图的基本概念 四 有向图的基本概念基础图 去掉有向图中所有弧上的箭头得到的无向图 始点 终点 弧 vi vj 中 称vi为弧的始点 vj为弧的终点 第1节图的基本概念 五 图的综合概念 一 无向图链 圈 第1节图的基本概念 初等链 链中没有重复的点 初等圈 圈中没有重复的点 简单链 链中没有重复的边 简单圈 圈中没有重复的边 第1节图的基本概念 图例 问 v1 v2 v3 v4 v5 v3 v6 v7 v1 v2 v3 v6 v7 v1 v2 v3 v4 v1 v4 v1 v2 v3 v5 v7 v6 v3 v4 v1 v2 v3 v5 v4 v3 v4 v1 第1节图的基本概念 二 有向图链 路 第1节图的基本概念 回路 初等路 路中没有重复的点 初等回路 回路中没有重复的点 第1节图的基本概念 图例 问 v3 a3 v2 a5 v4 a6 v5 a8 v3 v1 a2 v3 a4 v4 a7 v6 v1 a2 v3 a8 v5 a10 v6 v1 a2 v3 a4 v4 a6 v5 a8 v3 第2节树 一 树的概念连通图 无向图中任意两点间至少有一条链相连 不连通图 连通分图 不连通图中每个连通的部分 树 连通且不含圈的无向图 第2节树 二 树的性质任何树中必然存在次为1的点 1 树中次为1的点称为树叶 2 树中次大于1的点称为分枝点树的点有n个 则该树的边必有 n 1 条 任何具有n个点 n 1 条边的连通图必是树 树中任意两点之间有且只有唯一一条链 从一个树中去掉任一条边 则余下的图必是不连通图 在树中不相邻的两个点之间添上一条边 则必得到一个圈 反之再从该圈中任意去掉一条边 则必得到一个树 第2节树 图例 第2节树 三 支撑树支撑子图 支撑树 如果图G的支撑子图是一个树T 则称树T是图G的一个支撑树 支撑树的性质 图G有支撑树的充分必要条件是图G是连通图 第2节树 图例 支撑子图 第2节树 四 最小支撑树赋权图 最小支撑树 第2节树 最小支撑树的求解方法方法一 避圈法基本做法 首先选一条最小权的边 以后每一步中 总从未被选取的边中选一条权最小的边 并使之与已选取的边不构成圈 每一步中 如果有两条或两条以上最小权的边 则任选一条 第2节树 例3 某工厂内联结六个车间的道路网如下图所示 已知每条道路的长 要求沿道路架设联结六个车间的电话线网 使电话线的总长最小 第2节树 方法二 破圈法基本做法 任取一个圈 从圈中去掉一条权最大的边 如果有两条或两条以上最大权的边 则任去一条 在余下图中重复这个步骤 一直到得到一个不含圈的图为止 破圈法求解例3 习题6 1 习题6 1 分别用避圈法和破圈法求下述图的最小支撑树 1 2 第3节最短路问题 一 最短路的含义 第3节最短路问题 例4 某单行线交通网如下图所示 每弧旁的数字表示通过这条单行线所需要的费用 现在某人要从v1出发 通过这个交通网到v8去 求使总费用最小的旅行路线 第3节最短路问题 二 最短路问题的求解方法 一 Dijkstra方法适用条件 无负权 ij 0 的最短路问题基本思路 第3节最短路问题 基本解法 标号采用两种标号 T Temporary 标号和P Permanent 标号 T标号为临时标号 P标号为固定标号 给vi点一个P标号时 表示从vs到vi的最短路权 vi点的标号不再改变 给vi点一个T标号时 表示从vs到vi的最短路权的上界 凡没有得到P标号的点都有T标号 方法的每一步就是把某一点的T标号改为P标号 当终点vt点得到P标号时 计算结束 第3节最短路问题 具体步骤 第一 给vs标上P标号P vs 0 其余各点为T标号 T vj 第二 若vi是刚标上P标号的点 选取所有与vi有关联的弧 vi vj 中的vj点 且vj点为T标号 去修改vj点的T标号 第三 比较所有具有T标号的点 把最小的T标号值所对应的点改为P标号 即 如果存在两个或两个以上的最小T标号 则同时改为P标号 若所有点都获得P标号 停止计算 除去从vs到vj之间无路可走 即T vj P vj 否则转入第二 Dijkstra方法求解例4 第3节最短路问题 例5 用Dijkstra方法求解下图中从v1到v8的最短路 习题6 2 习题6 2 用Dijkstra方法求解下列各图从v1到v7的最短路 1 习题6 2 2 第3节最短路问题 二 赋权无向图的最短 路 问题的求解方法赋权无向图G V E 边 vi vj 表示既可以从vi到达vj 也可以从vj到达vi 所以边 vi vj 可以看作是两条弧 vi vj 和 vj vi 且它们具有相同的权 ij 第3节最短路问题 例6 计算下图所示赋权无向图中v1到v7的最短 路 第3节最短路问题 小结 对于赋权无向图G V E 从始点vs到各个点的最短 路 即为最短链 Dijkstra方法不仅适用于赋权有向图D 也适用于赋权无向图G Dijkstra方法直接给出某点 设为vs 到其他所有点的最短路 不能直接给出赋权图上任意两点间的最短路 Dijkstra方法只适用于全部权为非负情况 如果某权为负 则算法失效 第3节最短路问题 例7 求下图中从vs到v1的最短路 权为负数 习题6 3 习题6 3 用Dijkstra方法求解下图从v1到v9的最短 路 第3节最短路问题 三 最短路问题的应用设备更新问题 第3节最短路问题 例10 某工厂使用一台设备 每年年初工厂都要作出决定 如果继续使用旧的 要付维修费 若购买一台新设备 要付购买费 试制定一个5年的更新计划 使总支出最少 已知设备在各年的购买费 及不同机器役龄时的维修费如下表所示 第3节最短路问题 例10 解 转化为最短路问题点vi表示第i年年初购进一台新设备弧 vi vj 表示第i年年初购进的设备一直使用到第j年年初权 ij表示第i年年初购进设备 一直使用到第j年年初所需支付的购买 维修的全部费用 第3节最短路问题 最短路问题图示 第4节网络最大流问题 例11 已知联结某产品产地v1和销地v6的交通网 如下图所示 每一弧 vi vj 代表从vi到vj的运输线 产品经过这条弧由vi输送到vj 弧旁的数字表示这条运输线的最大通过能力 产品经过交通网从v1输送到v6 要求制定一个运输方案 使从v1运输到v6的产品数量最多 网络 流量最大 习题6 4 第4节网络最大流问题 一 基本概念和性质发点 收点 中间点 容量 网络 有向图D V A D的每条弧 vi vj 上有非负数cij称为弧的容量 在V中指定一点称为发点 记为vs 另一点称为收点 记为vt 其余点称为中间点 这样的D称为一个网络 记作D V A C 流 流量 定义在网络D中的弧集合A上的一个函数f fij 称为流 称fij为弧 vi vj 上的流量 流的性质 每个弧上的流量不超过该弧的容量 中间点的净输出量为零 第4节网络最大流问题 可行流 满足下述条件的流f称为可行流 记作v f 1 容量限制条件 对网络D中每条弧 vi vj 有0 fij cij 2 平衡条件 中间点每条弧vi 流出量与流入量相等发点vs 收点vt 从点vs流出的量等于点vt流入的量可行流的性质 可行流总是存在的 零流 网络D中所有弧的流量fij 0的可行流 第4节网络最大流问题 可行流 第4节网络最大流问题 最大流问题 在网络D中 求流量最大的可行流 记作v f 饱和弧 非饱和弧 零流弧 非零流弧 1 饱和弧 网络D中fij cij的弧 2 非饱和弧 网络D中fij cij的弧 3 零流弧 网络D中fij 0的弧 4 非零流弧 网络D中fij 0的弧 第4节网络最大流问题 链 网络D中联结发点vs和收点vt的一条链 定义链的方向是从vs到vt 1 前向弧 弧的方向与链的方向一致 2 后向弧 弧的方向与链的方向相反增广链 f是一个可行流 是从vs到vt的一条链 若满足则称 为从vs到vt关于f的增广链 增广链的实际意义 沿着链 从vs到vt输送的流还有潜力可挖 即可以把流量提高 定理 可行流f 是最大流的充分必要条件是不存在从vs到vt关于f 的增广链 第4节网络最大流问题 根据例11所描述的问题 找出链 v1 v2 v3 v4 v5 v6 的前向弧和后向弧 链 第4节网络最大流问题 根据例11所描述的问题 给出一个运输方案 如下图所示 试说明链 v1 v2 v3 v4 v5 v6 是否为增广链 增广链 第4节网络最大流问题 二 求解方法 标号法解题过程 从一个可行流f出发 1 标号过程 通过标号寻找增广链 2 调整过程 沿增广链调整f以增加流量基本解法 标号点 用vj 表示 表示vj点标号是从哪一点得到的 用vi表示 表示vj点与 之间的关系 用 或 表示 第4节网络最大流问题 具体步骤 一 标号过程第一 给vs标上 0 则vs是标号未检查点 其余各点都是未标号点 第二 取标号未检查点vi 对所有未标号点vj有 1 若在弧 vi vj 上 fij cij 则给vj标上 vi 2 若在弧 vk vi 上 fki 0 则给vk标上 vi 则vj vk 成为标号未检查点 而vi成为标号已检查点 在vi标号下面划一横线重复1 2 直至vt被标上号 则得到一条从vs到vt的增广链 转入调整过程 第三 若所有标号都已检查过 而标号过程进行不下去时 则停止计算 此时获得的可行流为最大流f 第4节网络最大流问题 二 调整过程第一 按照vt及其它各点标号的第一个部分反向追踪 找出增广链 第二 则获得新的可行流 重复标号过程 调整