Modeling with Linear Programming

CHAPTER 2

Modeling with Linear Programming

Chapter Guide. This chapter concentrates on model formulation and computations in linear programming (LP). It starts with the modeling and graphical solution of a two-variable problem which, though highly simplified, provides a concrete understanding of the basic concepts of LP and lays the foundation for the development of the general simplex algorithm in Chapter 3. To illustrate the use of LP in the real world, applications are formulated and solved in the areas of urban planning, currency arbitrage, in-vestment, production planning and inventory control, gasoline blending, manpower planning, and scheduling. On the computational side, two distinct types of software are used in this chapter. (1) TaRA, a totally menu-driven and self-documenting tutorial program, is designed to help you understand the basics of LP through interactive feed-back. (2) Spreadsheet-based Excel Solver and the AMPL modeling language are commercial packages designed for practical problems.

The material in Sections 2.1 and 2.2 is crucial for understanding later LP developments in the book. You will find TORA's interactive graphical module especially helpful in conjunction with Section 2.2. Section 2.3 presents diverse LP applications, each followed by targeted problems.

Section 2.4 introduces the commercial packages Excel Solver and AMPL. Models in Section 2.3 are solved with AMPL and Solver, and all the codes are included in folder ch2Files. Additional Solver and AMPL models are included opportunely in the succeeding chapters, and a detailed presentation of AMPL syntax is given in Appendix A. A good way to learn AMPL and Solver is to experiment with the numerous models presented throughout the book and to try to adapt them to the end-of-section problems. The AMPL codes are cross-referenced with the material in Appendix A to facilitate the learning process.

The TORA, Solver, and AMPL materials have been deliberately compartmentalized either in separate sections or under the subheadings TORA/So!ver/AMPL moment to minimize disruptions in the main text. Nevertheless, you are encouraged to work end-of-section problems on the computer. The reason is that, at times, a model may look "correct" until you try to obtain a solution, and only then will you discover that the formulation needs modifications.

This chapter includes summaries of 2 real-life applications, 12 solved examples, 2 Solver models, 4 AMPL models, 94 end-of-section problems, and 4 cases. The cases are in Appendix E on the CD. The AMPL/Excel/Solver/TORA programs are in folder ch2Files.

Real-life Application-Frontier Airlines Purchases Fuel Economically

The fueling of an aircraft can take place at any of the stopovers along the flight route. Fuel price varies among the stopovers, and potential savings can be realized by loading extra fuel (called tankering) at a cheaper location for use on subsequent flight legs. The disadvantage of tankering is the excess burn of gasoline resulting from the extra weight. LP (and heuristics) is used to determine the optimum amount of tankering that balances the cost of excess burn against the savings in fuel cost. The study, carried out in 1981, resulted in net savings of about $350,000 per year. Case 1 in Chapter 24 on the CD provides the details of the study. Interestingly, with the recent rise in the cost of fuel, many airlines are now using LP-based tankering software to purchase fuel.