| 一类有损耗网络最大流问题的模型与算法 |
| |
| 引用本文： | 颉栋栋,李方豫,盖宇仙,贾晓秋.一类有损耗网络最大流问题的模型与算法[J].兰州铁道学院学报,2007,26(1):132-134,148. |
| |
| 作者姓名： | 颉栋栋 李方豫 盖宇仙 贾晓秋 |
| |
| 作者单位： | 兰州交通大学交通运输学院 甘肃兰州730070(颉栋栋，李方豫，盖宇仙)，西南交通大学交通运输学院 四川成都610031(贾晓秋) |
| |
| 摘 要： | 由于阻力及其它因素的存在,网络流在实际中往往是有损耗的.建立了有损耗网络最大流的模型,并依据其流递远递减的特性设计了算法.以各弧还需要的流的消耗量为权值构造一赋权图,找出一条增流链,分配发点以合适的流量,并调整增流链上各弧的流量和赋权有向图上各弧的权值.反复迭代,直到各边流量都饱和或初始量被分配完毕,此时,收点的输入量达到最大值.最后通过实例验证了其正确性.
|
| 关 键 词： | 损耗 网络 最大流 最短路 |
| 文章编号： | 1001-4373（2007）01-0132-03 |
| 修稿时间： | 2006-04-18 |
Model and Algorithm for the Maximun Flow on a Loss Network |
| |
| Xie Dongdong,Li Fangyu,Gai Yuxian,Jia Xiaoqiu.Model and Algorithm for the Maximun Flow on a Loss Network[J].Journal of Lanzhou Railway University,2007,26(1):132-134,148. |
| |
| Authors: | Xie Dongdong Li Fangyu Gai Yuxian Jia Xiaoqiu |
| |
| Institution: | 1. School of Traffic and Transportation Engineering, Lanzhou Jiaotong University, Lanzhou 730070,China; 2. School of Traffic and Transportation Engineering,Southwest Jiaotong University,Chengdu 610031,China |
| |
| Abstract: | Due to resistance and other factors,flow value on some networks is decreasing.In this paper,a model for a type of such problems is formed and the algorithm is also designed for its speciality.Firstly,a graph weighted by flow needed lossing value is created and a chain flow of which need increasing is got.A proper flow is distributed to the start,then flow via the following points of this chain and weights of arcs of the weighted graph are changed.Such iterative is going on till the saturation of each flow and the completed distribution of the given flow are took place.Meanwhile,the total flow going to the termination reach a maximum.This method finally proves correct by a given example. |
| |
| Keywords: | loss network maximum flow the shortest path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
