2014年数模主要培训_图论及模型.ppt

* 所谓最大流问题就是在容量网络中,寻找流量最大的可行流. 实际问题中,一个网络会出现下面两种情况： ⑴ 发点和收点都不止一个. 解决的方法是再虚设一个发点vs和一个收点vt ,发点vs到所有原发点边的容量都设为无穷大, 所有原收点到收点vt 边的容量都设为无穷大. ⑵ 网络中除了边有容量外,点也有容量. 解决的方法是将所有有容量的点分成两个点,如点v有容量Cv ,将点v分成两个点v和v,令 C(vv ) = Cv . 最小费用流问题 * 这里我们要进一步探讨不仅要使网上的流达到最大,或者达到要求的预定值,而且还要使运输流的费用是最小的,这就是最小费用流问题. 最小费用流问题的一般提法： 已知网络G = (V, E, C ),每条边vivj∈E 除了已给容量Cij外,还给出了单位流量的费用bij(≥0). 所谓最小费用流问题就是求一个总流量已知的可行流 f ={ f ij }使得总费用 最小. * 特别地,当要求 f 为最大流时, 即为最小费用最大流问题. 设网络G = (V, E, C), 取初始可行流 f 为零流, 求解最小费用流问题的迭代步骤： ① 构造有向赋权图Gf =(V, Ef , F),对于任意的vivj∈E,Ef ,F 的定义如下： 当 f ij = 0时,vivj∈Ef ,F(vivj )= bij ; 当 f ij = Cij时,vjvi∈Ef ,F(vjvi )= - bij ; 当0＜ f ij＜Cij时,vivj∈Ef ,F(vivj )= bij ,vjvi∈Ef , F(vjvi ) = - bij . 然后转向②. * ② 求出含有负权的有向赋权图Gf =(V, Ef , F)中发点vs到收点vt的最短路? ,若最短路 ? 存在转向③; 否则f是所求的最小费用最大流,停止. ③ 增流. vivj与?相同, vivj与?相反. 令? = min {?ij|vivj∈? }, 重新定义流 f ={ f ij}为 其它情况不变. 如果Wf 大于或等于预定的流量值,则适当减少? 值,使Wf 等于预定的流量值,那么 f 是所求的最小费用流, 停止; 否则转向①. * 下面介绍求解有向赋权图G = (V, E, F )中含有负权的最短路的Ford算法. 设边的权vivj为wij , v1到vi的路长记为? (i ). Ford算法的迭代步骤： ① 赋初值 ? (1)=0,? (i )=∞,i = 2, 3, … , n . ② 更新 ? (i ),i = 2, 3, … , n . ? (i )= min{? (i ),min{? ( j ) + wji | j≠i }}. ③ 若所有的? (i )都无变化,停止;否则转向②. 在算法的每一步,? (i )都是从v1到vi的最短路长度的上界. 若不存在负长回路,则从v1到vi的最短路长度是? (i )的下界,经过n - 1次迭代后? (i )将保持不变. 若在第n次迭代后? (i )仍在变化时, 说明存在负长回路. 7、关键路径问题（拓扑排序） * 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？ PT(Potentialtask graph)图 * 在PT(Potentialtask graph)图中,用结点表示工序,如果工序 i 完成之后工序 j 才能启动,则图中有一条有向边(i , j ),其长度wi 表示工序 i 所需的时间. 这种图必定不存在有向回路,否则某些工序将在自身完成之后才能开始,这显然不符合实际情况. 在PT图中增加两个虚拟结点v0和vn ,使所有仅为始点的结点都直接与v0联结,v0为新增边的始点,这些新增边的权都设为0; 使所有仅为终点的结点都直接与vn联结,vn为新增边的终点. 这样得到的图G仍然不存在有向回路. 2、最短路径算法 * 定义1 设P(u, v) 是赋权图G = (V, E , F) 中从点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记 则称F (P)为路径P(u, v) 的权或长度(距离). 定义2 若P0 (