Computation - Operations Research Models and Methods

Computation

Mathematical Programming

Network Programming

Example Problem

Constructing the Network

Solving the Problem


Network Flow

Network Flow Programming

This important class of linear programming models has the advantage that elements of a problem can be described by a picture rather than a series of algebraic expressions as for the general linear programming model. Even if a particular problem cannot entirely be expressed as a network flow problem, very often major components of the problem can be expressed as a network. For an "almost" network model, the problem can be described using this model construct, and the worksheet or the Solver model modified to incorporate nonstandard features.

A network is a collection of nodes and arcs. Flow enters and leaves at the nodes and passes through the arcs. Generally there are lower and upper bounds on arc flows. Each arc has a unit cost and the arc cost is the flow multiplied by the unit cost. The goal is to find the flow that minimizes total cost.

Each arc has a gain factor that multiplies the flow entering the arc to obtain the flow that leaves the arc. A network with all gains equal to 1 is called a pure network. If some gains are other than 1, the network is called a generalized network.