Network Flow Programming

DISTRIBUTION EXAMPLE

Pure Network Model

Linear Programming Model

Solving the Model

Variable External Flows

A Generalized Network Model

Side Constraints

Vocabulary

SPECIAL CASES

Transportation Problem

Assignment Problem

Shortest Path Problem

Maximum Flow Problem

OTHER EXAMPLES

A Transportation Problem with Costs of Manufacture and Revenue at Sale

Multiperiod Operation

Transformation of Flow

Restrictions and Costs on Nodes

Convex Costs and Concave Revenues

Undirected Edges

Elimination of Arc Lower Bounds

Return to Modeling Home Page

 

The term network flow program describes a type of model that is a special case of the more general linear program. The class of network flow programs includes such problems as the transportation problem, the assignment problem, the shortest path problem, the maximum flow problem, the pure minimum cost flow problem, and the generalized minimum cost flow problem. It is an important class because many aspects of actual situations are readily recognized as networks and the representation of the model is much more compact than the general linear program. When a situation can be entirely modeled as a network, very efficient algorithms exist for the solution of the optimization problem, many times more efficient than linear programming in the utilization of computer time and space resources.