Abstract: The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is
dis-cussed. The analysis is based on the network simplex algorithm, which gains negative
cost graphs by constructingaugmented 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 augmentedgraphs are constructed
with the bottleneck structure. The arcs that block the negative cost augmented graph arethe
elements of the bottleneck. The bottleneck analysis for the generalized circulation
problem, the minimum circu-lation problem and the circulation problem are discussed
respectively as the basal problems, then that for MCPGNis achieved. An example is presented
at the end.

Key words: bottleneck, augmented forest, minimum cost problem

摘要： The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is
dis-cussed. The analysis is based on the network simplex algorithm, which gains negative
cost graphs by constructingaugmented 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 augmentedgraphs are constructed
with the bottleneck structure. The arcs that block the negative cost augmented graph arethe
elements of the bottleneck. The bottleneck analysis for the generalized circulation
problem, the minimum circu-lation problem and the circulation problem are discussed
respectively as the basal problems, then that for MCPGNis achieved. An example is presented
at the end.

关键词: bottleneck;augmented forest;minimum cost problem