运筹学4课件.ppt

树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 树与图的最小树 课堂练习： 树与图的最小树 最短路问题 如何用最短的线路将三部电话连起来？ 此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。 最短路问题 最短路问题 问题描述： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 最短路问题 例6.4 渡河游戏 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。 最短路问题 定义： 1）人—M（Man），狼—W（Wolf）， 羊—G（Goat）， 草—H（Hay） 2） 点—— vi 表示河岸的状态 3） 边—— ek 表示由状态 vi 经一次渡河到状态 vj 4） 权——边 ek 上的权定为 1 最短路问题 状态说明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G) 最短路问题 求最短路有两种算法: 最短路问题 狄克斯屈拉(Dijkstra)标号算法的基本思路： 若序列{ vs,v1…..vn-1,vn }是从vs到vt间的最短路，则序列{ vs,v1…..vn-1 } 必为从vs 到vn-1的最短路。 最短路问题 求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) 距离为dij 最短路问题 例6.5 求下图v1到v7的最短路长及最短路线 最短路问题 从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。 最短路问题 例6.6 求下图v1到各点的最短距离及最短路线。 最短路问题 课堂练习： 1. 用Dijkstra算法求下图从v1到v6的最短距离及路线。 最短路问题 2. 求从v1到v8的最短路径 最短路问题 最短路问题 3. 求下图中v1点到另外任意一点的最短路径 最短路问题 最短路问题 最短路问题 算法适用条件： Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。 最短路问题 最短路问题的应用： 例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 最短路问题 解：这是一个求无向图的最短路的问题。 最短路问题 例6.8 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知： 设备每年年初的价格表 最短路问题 设备维修费如下表 最短路问题 把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。 最短路问题 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1→v3→v6和 v1→v4→v6 网络的最大流 如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。 网络的最大流 基本概念： 1. 容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。 网络的最大流 2. 网络的最大流 是指网络中从发点到收点之间允许通过的最大流量。 网络的最大流 网络的最大流 网络的最大流 网络的最大流 定理2 在网络中s→t的最大流量等于它的最小割集的容量， 即：