yeah, I figured it was a bit over the top...
I'll put notes on all the cells to explain what each is doing and what is 'enterable'. Hopefully I'll get that done by the end of the holiday weekend here.
The minimum cost flow problem holds a central position among network optimization mod-
els, both because it encompasses such a broad class of applications and because it can be
solved extremely efficiently. Like the maximum flow problem, it considers flow through a
network with limited arc capacities. Like the shortest-path problem, it considers a cost (or
distance) for flow through an arc. Like the transportation problem or assignment problem of
Chap. 8, it can consider multiple sources (supply nodes) and multiple destinations (demand
nodes) for the flow, again with associated costs. In fact, all four of these previously studied
problems are special cases of the minimum cost flow problem,as we will demonstrate shortly.
The reason that the minimum cost flow problem can be solved so efficiently is that
it can be formulated as a linear programming problem so it can be solved by a stream-
lined version of the simplex method called the network simplex method. We describe this
algorithm in the next section.
The minimum cost flow problem is described below.
1. The network is a directedand connectednetwork.
2. At least oneof the nodes is a supply node.
3. At least oneof the other nodes is a demand node.
4. All the remaining nodes are transshipment nodes.
5. Flow through an arc is allowed only in the direction indicated by the arrowhead, where
the maximum amount of flow is given by the capacityof that arc. (If flow can occur in
both directions,this would be represented by a pair of arcs pointing in opposite directions.)
6. The network has enough arcs with sufficient capacity to enable all the flow generated
at the supply nodesto reach all the demand nodes.
7. The cost of the flow through each arc is proportionalto the amount of that flow, where
the cost per unit flow is known.
8. The objective is to minimize the total cost of sending the available supply through the
network to satisfy the given demand. (An alternative objective is to maximize the to-
tal profit from doing this.)
That sounds exactly what we're looking for, Redwalker - and the algorithm that solves it 'extremely efficiently' is...?
(Sorry Ishmael, I haven't found the time to study and comment on your sheet yet.)
The network simplex method is a highly streamlined version of the simplex method for
solving minimum cost flow problems. As such, it goes through the same basic steps at
each iteration—finding the entering basic variable,determining the leaving basic variable,
and solving for the new BF solution—in order to move from the current BF solution to a
better adjacent one. However, it executes these steps in ways that exploit the special net-
work structure of the problem without ever needing a simplex tableau.
You may note some similarities between the network simplex method and the trans-
portation simplex method presented in Sec. 8.2. In fact, both are streamlined versions of
the simplex method that provide alternative algorithms for solving transportation prob-
lems in similar ways. The network simplex method extends these ideas to solving other
types of minimum cost flow problems as well.
In this section, we provide a somewhat abbreviated description of the network sim-
plex method that focuses just on the main concepts. We omit certain details needed for a
full computer implementation, including how to construct an initial BF solution and how
to perform certain calculations (such as for finding the entering basic variable) in the most
efficient manner. These details are provided in various more specialized textbooks, such
as Selected References 1, 2, 3, 5, and 8.
...
1. Ahuja, R. K., T. L. Magnanti, and J. B. Orlin: Network Flows:Theory, Algorithms, and Appli-
cations, Prentice-Hall, Englewood Cliffs, NJ, 1993.
2. Ball, M., T. L. Magnanti, C. Monma, and G. L. Nemhauser: Network Models, Elsevier, New
York, 1995.
3. Bazaraa, M. S., J. J. Jarvis, and H. D. Sherali: Linear Programming and Network Flows, 2d ed.,
Wiley, New York, 1990.
4. Dantzig, G. B., and M. N. Thapa: Linear Programming 1: Introduction, Springer, New York,
1997, chap. 9.
5. Glover, F., D. Klingman, and N. V. Phillips: Network Models in Optimization and Their Appli-
cations in Practice, Wiley, New York, 1992.
6. Hillier, F. S., M. S. Hillier, and G. J. Lieberman: Introduction to Management Science:A Mod-
eling and Case Studies Approach with Spreadsheets, Irwin/McGraw-Hill, Burr Ridge, IL, 2000,
chap. 7.
7. Magnanti, T. L., and R. T. Wong: “Network Design and Transportation Planning: Models and
Algorithms,”Transportation Science, 18:1–55, 1984.
8. Murty, K. G.: Network Programming, Prentice-Hall, Englewood Cliffs, NJ, 1992.
Flow networks also find applications in ecology: flow networks arise naturally when considering the flow of nutrients and energy between different organizations in a food web. The mathematical problems associated with such networks are quite different from those that arise in networks of fluid or traffic flow. The field of ecosystem network analysis, developed by Robert Ulanowicz and others, involves using concepts from information theory and thermodynamics to study the evolution of these networks over time.