Network Models

CHAPTER 6

Network Models

Chapter Guide. The network models in this chapter include the traditional applications of finding the most efficient way to link a number of locations directly or indirectly, finding the shortest route between two cities, determining the maximum flow in a pipeline network, determining the minimum-cost flow in a network that satisfies supply and demand requirements at different locations, and scheduling the activities of a project.

The minimum-cost capacitated algorithm is a generalized network that subsumes the shortest-route and the maximal-flow models presented in this chapter. Its details can be found in Section 20.1 on the CD.

As you study the material in this chapter, you should pay special attention to the nontraditional applications of these models. For example, the shortest-route model can be used to determine the optimal equipment replacement policy and the maximum-flow model can be used to determine the optimum number of ships that meet a specif-ic shipping schedule. These situations are included in the chapter as solved examples, problems, or cases.

Throughout the chapter, the formulation and solution of a network model as a linear program is emphasized. It is recommended that you study these relationships, because most commercial codes solve network problems as mere linear programs. Ad-ditionally, some formulations require imposing side constraints, which can be imple-mented only if the problem is solved as an LP.

To understand the computational details, you are encouraged to use TORA's in-teractive modules that create the steps of the solution in the exact manner presented in the book. For large-scale problems, the chapter offers both Excel Solver and AMPL models for the different algorithms.

This chapter includes a summary of 1 real-life application, 17 solved examples, 2 Solver models, 3 AMPL models, 69 end-of-section problems, and 5 cases. The cases are in Appendix E on the CD. The AMPL/Excel/Solver/TORA programs are in folder ch6Files.

Real-Life Application-Saving Federal Travel Dollars

U.S. Federal Government employees are required to attend development conferences and training courses in different locations around the country. Because the federal employees are located in offices scattered around the United States, the selection of the host city impacts travel cost. Currently, the selection of the city hosting confer-ences /training events is done without consideration of incurred travel cost. The prob-lem seeks the determination of the optimal location of the host city. For Fiscal Year 1997, the developed model was estimated to save at least $400,000. Case 4 in Chapter 24 on the CD provides the details of the study.