hu-6网络流4与优化2课时.pptVIP

* * 第 五 章 网 络 问 题 §5.1 最大流问题 所谓最大流问题，简单的说，就是在一定的条件下，使网络系统中的某种流的流量达到最大的问题。 最大流问题具有以下特征: （1）网络中所有流起源于一个叫做源的结点； （2）所有的流终止于一个叫做收点的结点； （3）通过每一条弧的流只允许沿着弧的箭头方向流动； （4）目标是使得从源到收点的总流量最大。 最大流问题可以归结为一个线性规划问题，设 表示第I个结点流向第j个结点的最大允许流量（容量），如果没有线路到达，则容量为0；设 表 示第I个结点流向第j个结点的流量，如果没有线路到达，则流量为0，因此最大流问题可以归结为如下线性规划问题： 例5.1 (P56) §5.2 最小费用流问题 最小费用流是指对于给定的流通网络图，例如在一个由道路网络构成的交通网络中，每一条弧（道路）都有一定的容量（通过能力）和权（单位费用），在流量既定的条件下，从某一结点（地方）到另一结点（地方）走怎样的路线才能使费用达到最小。 最小费用流问题具有以下特征： (1) 网络中所有流起源于一个叫做源的结点； (2) 所有的流终止于一个叫做收点的结点； (3) 通过每一条弧的流只允许沿着弧的箭头方向流动,通过弧的最大流量取决于该弧的容量； （4）网络中有足够的弧提供足够容量，使得所有在源中产生的流都能够到达收点； （5）在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比。 （6）目标是使得从源到收点的总费用最小。 最小费用问题可以归结为一个线性规划问题，设 表示第I个结点流向第j个结点的最大允许流量（容量），如果没有线路到达，则容量为0；设 表示第I个结点流向第j个结点的单位费用；设 表示第I个结点流向第j个结点的流量，如果没有线路到达或没有流量通过，则流量为0；要求从第1个结点达到第n个结点的流量为k,那么最小费用流问题可以归结为如下线性规划问题： 例2：P69 2(1) §5.3 最短路程问题 最短路问题是求给定网络上任意两点之间的最短距离及所走的路线。 最短路问题可以化为线性规划问题来求解。 最短路问题具有以下特征： （1）在网络中选择一条路，起始于某源点，终止于目的地； （2）连接两个结点的连线叫做无向弧（允许任一个方向行进），有向弧（只允许沿着一个方向行进）； （3）和每条弧相关的一个非负数，叫做该弧的长度或权； （4）目标是寻找从源点到目的地的最短路。 1、有向赋权网络图的最短路程问题 如果在赋权网络图中规定两个结点之间弧的方向，称为有向赋权网络图。 设路径矩阵的元素 只能取0或1，其中1表示从第I个结点到第j个结点是有通路的，0表示从第I个结点到第j个结点是没有通路的。 设路程矩阵的元素 表示第I个结点通向第j个结点的路程。 设工作表的元素 只能取0或1，其中1表示从第I个结点到第j个结点在最短路程上，0表示从第I个结点到第j个结点不在最短路程上。 最短路问题可以归结为如下线性规划问题： 例题：P70 3(1) 3、混合赋权网络图的最短路问题 如果在赋权网络图中，既有有向弧又有无向弧，则称为混合赋权网络图。 混合赋权网络图的求解方法与无向赋权网络图的求解方法完全一样。 §5.4 关键路线技术 关键路线技术也称为网络计划技术。关键路线技术指的是一套用于计划和控制项目实施的图形技术。 关键路线技术用网络图形描述出一项工程的全貌，并提示要将注意力集中在关键路线上，因为它决定了项目的完成时间。关键路线技术是管理中工作计划编制的有效工具，是一种安排时间的方法。 应用该技术的项目必须具有如下特点： （1）工作或任务可以明确定义，它们的完成标志着项目的结束； （2）工作或任务相互独立，即它们可分别开始、结束和实施； （3）工作或任务有一定的顺序，它们必须按顺序依次完成。 应用关键路线技术可分为三个基本阶段： (1) 绘制计划网络图： 如例5.6，图中的弧（连线）表示工序，弧上的数字表示工序完成所需要的时间；结点表示某些活动的完成和另一些