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.