求解网络最小流问题的图单纯形算法

堵塞是以人为主体的运输网络在随机流动情况下经常发生的一种现象。所谓网络最小流是指一个运输网络发生最严重堵塞情况下的最大流量，它是设计运输网络，特别是紧急疏散网络的一个重要参数。本文在网络堵塞流研究的基础上，根据网络最小流是饱和流的特点，从组合优化角度定义了网络最小流问题，并提出了求解网络最小流的图单纯形算法，文中详细介绍了实施这种图单纯形算法的基本理论和步骤，并用实例进行了说明。

Graph Simplex Algorithm for Solving Minimal Flow Problem of a Network

Blockage is a kind of phenomenon, happened frequently in a transport network in which human beings are the moving subjects. The minimal flow of a network defined in this paper means the maximal flow through the network in the most seriously blocked situation. It is an important parameter in designing a transport network, especially an emergency evacuation network. In this paper the combinatorial optimization model of the minimal flow problem is presented on the concept of saturated flow of a network which is defined for the research work on the blocking flow theory, and a practical method called Graph Simplex Algorithm is developed to solve the minimal flow problem with an example in detail.