in the construction of efficient algorithms for their solution.

The motivation for taking advantage of their

existing computer technology. Historically, the first of these special structures to be analyzed was the trans-
portation problem, which is a particular type of network problem. The development of an efficient solution
procedure for this problem resulted in the first widespread application of linear programming to problems of
industrial logistics. More recently, the development of algorithms to efficiently solve particular large-scale

extremely efficient and permit the solution of network models so large that they would be impossible to solve
by ordinary linear-programming procedures. Their efficiency stems from the fact that a pivot operation for

and updating the usual tableau at each iteration. Further, an added benefit of these algorithms is that the

A common scenario of a network-flow problem arising in industrial logistics concerns the distribution of a

points reflecting warehouses or distribution centers. Further, there may be capacity restrictions that limit

A numerical example of a network-flow problem is given in Fig 8.1. The nodes are represented by
Figure 8.1 exhibits several additional characteristics of network flow problems. First, a flow capacity is
assigned to each arc, and second, a per-unit cost is specified for shipping along each arc. These characteristics
are shown next to each arc. Thus, the flow on arc 2–4 must be between 0 and 4 units, and each unit of flow
’s in the figure have been used to denote unlimited flow capacity on arcs 2–3

The objective is to find the minimum-cost flow pattern to fulfill demands from the source nodes. Such
minimum-cost flow

The first five equations are flow-balance equations at the nodes. They state the conservation-of-flow law,

equation for each node in the network. The flow variables 1 coefficients in these

Minimum-cost flow problem.

1 coefficient,
1 coefficient, corresponding to

developing specialized, efficient algorithms.

unit of flow across an arc. For example,

minimum-cost flow

The summations are taken only over the arcs in the network. That is, the first summation in the th flow-

are contained in the network and represents the total cost of sending flow over the network. The
equation is interpreted as above: it states that the flow out of node minus the flow into
is the upper bound on arc flow and may be
is the lower bound on arc flow and is often taken to be zero, as in the

There are a number of interesting special cases of the minimum-cost flow model that have received a great
deal of attention. This section introduces several of these models, since they have had a significant impact
on the development of a general network theory. In particular, algorithms designed for these specific models
have motivated solution procedures for the more general minimum-cost flow problem.
The transportation problem is a network-flow model without intermediate locations. To formulate the problem,
let us define the following terms:

Later we will return to this point, indicating what to do when this supply–demand balance is not satisfied. If
we define the decision variables as:

Usually Eq. (3) is written with positive coefficients and righthand sides by multiplying through by minus one.
denotes the flow from source 1 to destination 1, although these are two distinct

Though the transportation model has been cast in terms of material flow from sources to destinations, the
we can find the optimal assignment by solving the optimization problem:

The first set of constraints shows that each person is to be assigned to exactly one job and the second set of

each destination (job). As we shall see, network-flow problems have integer solutions, and therefore formal
specification of integrality constraints is unnecessary. Consequently, application of the simplex method, or
most network-flow algorithms, will solve such integer problems directly.

For the maximal flow problem, we wish to send as much material as possible from a specified node
, to another specified node . No costs are associated with flow. If
denotes the flow from node

for the flow

Let us introduce a fictitious arc

units of flow from node
The situation is modeled as finding the maximum flow from node 1, the lake, to node 6, the reservoir, in the

The numbers next to the arcs indicate the maximum flow capacity (in 100,000 gallons/day) in that section

(or travel time, or cost, etc.) associated with each arc, find a path through the network from a

a network, that results in very efficient solution procedures. (In Chapter 11 on dynamic programming, we

more complex situations, such as the subproblems in applying decomposition to traffic-assignment problems

We can interpret the shortest-path problem as a network-flow problem very easily. We simply want to send
one unit of flow from the source to the sink at minimum cost. At the source, there is a net supply of one unit;
at the sink, there is a net demand of one unit; and at all other nodes there is no net inflow or outflow.
As an elementary illustration, consider the example given in Fig. 8.4, where we wish to find the shortest

For the network specified in Fig. 8.4, the linear-programming tableau is given in Tableau 1.

highway; in large maintenance projects, such as those encountered in nuclear plants or oil refineries; and

product. All these projects consist of a well specified collection of tasks that should be executed in a certain
prescribed sequence. CPM provides a methodology to define the interrelationships among the tasks, and to
does not have predecessors; and a ‘‘finish’’ task, which has, as immediate predecessors,

Roofing

programming problem. First, we define the decision variables

immediate predecessor. Obviously, they cannot start until task 3 is finished; therefore, they should have the

For our example, these precedence relationships define the linear program given in Tableau E8.2.

We do not yet have a network flow problem; the constraints of (5) do not satisfy our restriction that each
column have only a plus-one and a minus-one coefficient in the constraints. However, this

with the constraint of (5) that has a minus one as a coefficient for and a plus one as a coefficient of
Now we note that each column of (6) has only one plus-one coefficient and one minus-one coefficient, and

side has only a plus one and a minus one, we have flow equations for sending one unit of flow from node 1 to
node 6. The network corresponding to these flow equations is given in Fig. 8.6; this network clearly maintains

number of sequencing constraints prescribed in the task definition of Table 8.4. since only six earliest starting

Network-flow models are more prevalent than one might expect, since many models not cast naturally as
(7) and (8) merely define the amount

reflect smelting and casting capacity,

1 coefficient and once with a 1 coefficient. It can be stated

as a network, however, by making a number of changes. Suppose, first, that we rearrange all the constraints

defined by (8). Let us also multiply the constraints of (9) by

1 coefficient and once in the equations of

1 coefficient; each variable 1 coefficient and
1 coefficient. Consequently, except for the variables

1 coefficient and once in the equations of

1 coefficient, so appending this constraint to the previous formulation gives the desired network

The network representation is shown Fig. 8.7. As usual, each equation in the model defines a node in the

network-flow problems, as in this example, but instead might show that the problem has a substantial network
Ultimately in this chapter we want to develop an efficient algorithm for the general minimum-cost flow problem

problem will then carry over to the more general minimum-cost flow problem in a straightforward manner.
Historically, the transportation problem was one of the first special structures of linear programming for
which an efficient special-purpose algorithm was developed. In fact, special-purpose algorithms have been
a finite number of steps, a termination condition arises. The effectiveness of an algorithm depends upon its
efficiency in attaining the termination condition.

in the final column are the supplies available at the source nodes and those in the bottom row are the demands
in the tableau denote the flow allocation
and the corresponding cost per unit of flow is

In order to apply the simplex method to the transportation problem, we must first determine a basic feasible

example in Section 8.2, the last equation can be formed by summing the first three equations and subtracting

demand at destination 1 is not, we next fulfill the remaining demand at destination 1 from that available at
for this final allocation because we have assumed that the total supply equals the total demand, that is,

array, it starts with the upper leftmost corner (the northwest corner) and assigns the maximum possible flow
allocation to that cell. Then it moves to the right, if there is any remaining supply in the first row, or to the
next lower cell, if there is any remaining demand in the first column, and assigns the maximum possible flow

we have exhausted all the supply and satisfied all the demand.
There are many other methods that have been used to find an initial basis for starting the transportation

It should be pointed out that any comparison among procedures for finding an initial basis should be
, including both finding the initial basis

The two procedures for finding an initial basic feasible solution resulted in different bases; however, both

nodes in the network. Further, each basis is a subnetwork that satisfies the following two properties:

A subnetwork that satisfies these two properties is called a

simplex method very efficient. Suppose you were told that a feasible basis consists of arcs 1–1, 2–1, 2–2, 2–4,
the unfulfilled demand at destination 1 from 45 to 10 units. The end node and its connecting arc are then

Because it is so common to find the transportation problem written with 1 coefficients for the variables
the transportation problem efficiently. The algorithm will proceed as follows: after a basic feasible solution

(16), once one of the simplex multipliers has been specified, the remaining values of

method. The simplex multipliers associated with this basis are easily determined by first arbitrarily setting

chosen and set to any finite value, positive or negative, to initiate the determination.
Once we have determined the simplex multipliers, we can then easily find the reduced costs for all

not yield an optimal solution. We, therefore, need to find an improved solution.
, maintaining all other nonbasic variables equal to zero, the flows

can be increased corresponds to the smallest value of a flow on this loop from which

form for the current basic solution is convenient to use for computations, but the justification of its use is
. The flow

portation problems efficiently. There are three steps to the approach:

1. finding an initial basic feasible solution;