Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on Augmented Forest Structure

摘要

The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented forest structure,then augments flows on the negative cost graphs until the optimal revolution is gained Bottleneck structure is presented after analyzing the augmented forest structure.The negative cost augmented graphs are constructed with the bottleneck structure.The arcs that block the negative cost augmented graph are the elements of the bottleneck.The bottleneck analysis for the generalized circulation problem,the minimum circulation problem and the circulation problem are discussed respectively as the basal problems,then that for MCPGN is achieved.An example is presented at the end.