一类有损耗网络最大流问题的模型与算法

Model and Algorithm for the Maximun Flow on a Loss Network

由于阻力及其它因素的存在,网络流在实际中往往是有损耗的.建立了有损耗网络最大流的模型,并依据其流递远递减的特性设计了算法.以各弧还需要的流的消耗量为权值构造一赋权图,找出一条增流链,分配发点以合适的流量,并调整增流链上各弧的流量和赋权有向图上各弧的权值.反复迭代,直到各边流量都饱和或初始量被分配完毕,此时,收点的输入量达到最大值.最后通过实例验证了其正确性.

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.