(^250) | Chapter 8: Network Flow Algorithms
The SIMPLEXalgorithm designed by George Dantzig in 1947 makes it possible to
solve problems such as those shown in Example 8-7, which involve hundreds or
thousands of variables (McCall, 1982). SIMPLEXhas repeatedly been shown to be
efficient in practice, although the approach can, under the right circumstances,
lead to an exponential number of computations. It is not recommended to imple-
ment the SIMPLEXalgorithm yourself, both because of its complexity and because
there are commercially available software libraries that do the job for you.
References
Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin,Network Flows:
Theory, Algorithms, and Applications. Prentice Hall, 1993.
Bazarra, M. and J. Jarvis,Linear Programming and Network Flows. John Wiley &
Sons, 1977.
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
Introduction to Algorithms, Second Edition. McGraw Hill, 2001.
Ford, L. R. Jr. and D. R. Fulkerson,Flows in Networks. Princeton University
Press, 1962.
Fragouli, Christina and Tarik Tabet, “On conditions for constant throughput in
wireless networks,” ACM Transactions on Sensor Networks (TOSN), 2 (3):
359–379, 2006,http://portal.acm.org/citation.cfm?id=1167938.
Goldberg, A. V. and R. E. Tarjan, “A new approach to the maximum flow
problem,” Proceedings of the eighteenth annual ACM symposium on Theory of
computing, pp. 136–146, 1986. http://portal.acm.org/citation.cfm?doid=12130.
12144.
Leighton, Tom and Satish Rao, “Multicommodity max-flow min-cut theorems
and their use in designing approximation algorithms,”Journal of the ACM, 46 (6):
787–832, 1999,http://portal.acm.org/citation.cfm?doid=331524.331526.
McCall, Edward H., “Performance results of the simplex algorithm for a set of
real-world linear programming models,”Communications of the ACM, 25(3):
207–212, March 1982,http://portal.acm.org/citation.cfm?id=358461.
Orden, Alex, “The Transhipment Problem,”Management Science, 2(3), 1956.
0 <= e23, e23 <= 280,
0 <= e24, e24 <= 350
];
Cost := 7e13 + 6e14 + 4e23 + 6e24;

Invoke linear programming to solve problem

minimize (Cost, Constraints, NONNEGATIVE);
Example 8-7. Maple commands to apply minimization to Transportation problem (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use