运筹学(图与网络分析).ppt

运筹学Operations Research 西安理工大学工商管理学院 我们在实际生活、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。 例 某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其中，点v1，v2，…，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。 基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最小费用最大流问题。这些问题的数学模型实际上大都是线性规划问题，但使用线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。 例 某石油公司建有一个可以把石油从采地输送到不同销售点的管道网络，如下图。由于管道的直径变化，使得各段管道（vi, vj）的最大通过能力（容量）cij也是不一样的，cij的单位为万加仑/小时。要求我们制定一个输送方案，将石油从v1输送到v6，使得输送的石油达到最大 避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边； 加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n－1条边）。 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 1 8 v1 v2 v3 v4 v5 v6 4 3 5 2 1 Min C(T)=15 求最小树的方法：避圈法和破圈法 破圈法：任取一圈，去掉圈中最长边，直到无圈。 v1 v2 v3 v4 v5 v6 4 3 5 2 1 5 v1 v2 v3 v4 v5 v6 8 4 3 7 5 2 6 1 8 v1 v2 v3 v4 v5 v6 4 3 5 2 1 得到最小树： Min C(T)=15 ●根树及其应用 定义 有向树：若一个有向图是一棵树，则称这个有向图为有向树。 定义 若有向树T恰有一个结点的入次为0，其余各点入次均为1，则称T为根树。 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 入次为0的点，称为根 出次为0的点，称为叶 其它顶点，称为分枝点 根到某顶点vi的道路长度，称为vi点的层次。 定义 在根树T中，若每个顶点的出次小于或等于m，则称T为m叉树。 若每个顶点的出次恰好等于m或零，则称T为完全m叉树。 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 当m=2时，称为二叉树、完全二叉树。 v1 v2 v3 v4 v5 v6 v7 记二叉树各叶子的权为pi，根到各叶子的距离（层次）为 li 二叉树的总权数： v1 v2 v3 v4 v5 v6 v7 最优二叉树：满足总权最小的二叉树称为最优二叉树。 霍夫曼（D A Huffman)给出了一个求最优二叉树的算法，又称霍夫曼树。 例：最优检索问题 用计算机进行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算次数最小？ 算法步骤： 1.将s个叶子按权由小至大排序； 2.将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2；将新的分枝点作为一个叶子，合并，… 解：构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15. 步骤如下： 1.将5个叶子按权由小到大排序：5，10，15，20，50 2.找出二个最小权的叶子，合并成一个分枝点，其权为15； 依次，继续。 10 30 15 20 50 50 100 总权为： 5 15 1 2 3 4 分检过程是：先把A类50万册从总数中分检出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D、C分检出来。 A A B B E E D C D N Y N Y N Y N Y 8.3最短路问题 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩阵算法。 最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 渡河问题 一老汉带了一只