Hillier / Lieberman - Introduction To Operations Research

PREFACE

It now is 33 years since the first edition of this book was published in 1967. We have been humbled by having had both the privilege and the responsibility of introducing so many students around the world to our field over such a long span of time. With each new edition, we have worked toward the goal of meeting the changing needs of new generations of students by helping to define the modern approach to teaching the current status of operations research effectively at the introductory level. Over 33 years, much has changed in both the field and the pedagogical needs of the students being introduced to the field. These changes have been reflected in the substantial revisions of successive editions of this book. We believe that this is true for the current 7th edition as well.

The enthusiastic response to our first six editions has been most gratifying. It was a particular pleasure to have the 6th edition receive honorable mention for the 1995 INFORMS Lancaster Prize (the prize awarded for the year's most outstanding English-language publication of any kind in the field of operations research), including receiving the following citation. "This is the latest edition of the textbllk that has introduced approximately one-half million students to the methods and models of Operations Research. While adding material on a variey of new topics, the sixth edition maintains the high standard of clarity and expositional excellence for which the authors have long been known. In honoring this work, the prize committee noted the enormous cumulative impact that the Hillier-Lieberman text has had on the development of our field, not only in the United States but also around the world through its many foreign-language editions."

As we enter a new millennium, the particular challenge for this new edition was to revise a book with deep roots in the 20th century so thoroughly that it would become fully suited for the 21st century. We made a special effort to meet this challenge, especially in regard to the software and pedagogy in the book.

A WEALTH OF SOFTWARE OPTIONS

The new CD-ROM that accompanies the book provides an exciting array of software operations that reflect current practice.

One option is to use the increasingly popular spreadsheet approach with Excel and its Solver. Using spreadsheets as a key medium of instruction clearly is one new wave in the teaching of operations research. The new Sec. 3.6 describes and illustrates how to use Excel and its Solver to formulate and solve linear programming models on a spreadsheet. Similar discussions and examples also are included in several subsequent chapters for other kinds of models. In addition, the CD-ROM provides an Excel file for many of the chapters that displays the spreadsheet formulation and solution for the felevant examples in the chapter. Several of the Excel files also include a number of Excel templates for solving the models in the chapter. Another key resource is a collection of Excel add-ins on the CD-ROM (Premium Solver, TreePlan, SensIt, and RiskSim) that are integrated into the corresponding chapters. In addition, Sec. 22.6 describes how some simulations can be performed efficiently on spreadsheets by using another popular Excel add-in (@RISK) that can be downloaded temporarily from a website.

Practioners of operations research now usually use a modeling language to formulate and manage models of the very large size commonly encountered in practice. A modeling language system also will support one or more sophisticated softeware packages that can be called to solve a model once it has been formulated appropriately. The new Sec. 3.7 discusses the application of modeling languages and illustrates it with one modeling language (MPL) that is relatively amenable to student use. The student version of MPL is provided on the CD-ROM, along with an extensive MPL tutorial. Accompanying MPL as its primary solver is the student version of the renowned state-of-the-art software package, CPLEX. The student version of CONOPT also is provided as the solver for nonlinear programming. We are extremely pleased to be able to provide such powerful and popular software to students using this book. To further assist students, many of the chapters include an MPL/CPLEX file (or MPL/CPLEX-CONOPT file in the case of the nonlinear programming chapter) on the CD-ROM that shows how MPL and CPLEX would formulate and solve the relevant examples in the chapter. These files also illustrate how MPL and CPLEX can be integrated with spreadsheets.

As described in the appendix to Chap. 3 and 4, a third attractive option is to employ the student version of the popular and student-friendly software package LINDO and its modeling language companion LINGO. Both packages can be downloaded free from the LINDO Systems website. Associated tutorial material is included on the CD-ROM, along with a LINDO/LINGO file for many of the chapters showing how LINDO and LINGO would formulate and solve the relevant examples in the chapter. Once again, integration with spreadsheets also is illustrated.

Complementing all these options on the CD-ROM is an updated version of the tutorial software that many instructors have found so useful for their students with the 5th and 6th editions. A program called OR Tutor provides 16 demonstration examples from the 6th edition, but now with an attractive new design based on JavaScript. These demos vividly demonstrate the evolution of an algorithm in ways that cannot be duplicated on the printed page. Most of the interactive routines from the 6th edition also are included on the CD-ROM, but again with an attractive new design. This design features a spreadsheet format based on VisualBasic. Each of the interactive routines enables the student to interactively execute on of the algorithms of operations research, making the needed decision at each step while the computer does the needed arithmetic. By enabling the student to focus on concepts rather than mindless number crunching when doing homework to learn an algorithm, we have found that these interactive routines make the learning process far more efficient and effective as well as more stimulating. In addition to these routines, the CD-ROM includes a few of the automatic routines from the 6th edition (again redesigned with VisualBasic) for those cases that are not covered by the software options described above. We were very fortunate to have the services of Michael O'Sullivan, a talented programmer and an advanced Ph.D. student in operations research at Stanford, to do all this updating of the software that had been developed by Mark S. Hillier for the 5th and 6th editions.

Microsoft Project is introduced in Chap. 10 as a useful tool for project management. This software package also is included on the CD-ROM.

NEW EMPHASES

Today's students in introductory operations research courses tend to be very interested in learning more about the relevance of the material being covered, including how it is actually being used in practice. Therefore, without diluting any of the features of the 6th edition, the focus of the revision for this edition has been on increasing the motivation and excitement of the students by making the book considerably more "real world" oriented and accessible. The new emphasis on the kinds of software that practitioners use is one thrust in this direction. Other major new features are outlined below.

Twenty-five elaborate new cases, embedded in a realistic setting and employing a stimulating storytelling approach, have been added at the end of the problem sections. All but one of these cases were developed jointly by two talented case writers, Karl Schmedders (a faculty member at the Kellogg Graduate School of Management at Northwestern University) and Molly Stephens (recently an operations research consultant with Andersen Consulting). We also have further fleshed out six cases that were in the 6th edition. The cases generally require relatively challenging and comprehensive analyses with substantial use of the computer. Therefore, they are suitable for student projects, working either individually or in teams, and can then lead to class discussion of the analysis.

A complementary new feature is that many new problems embedded in a realistic setting have been added to the problem section of many chapters. Some of the current problems also have been fleshed out in a more interesting way.

This edition also places much more emphasis on providing perspective in terms of what is actually happening in the practice of operations research. What kinds of applications are occuring? What sizes of problems are being solved? Which models and techniques are being used most widely? What are their shortcomings and what new developments are beginning to address these shortcomings? These kinds of questions are being addressed to convey the relevance of the techniques under discussion. Eight new sections (Secs. 10.7, 12.2, 15.6, 18.5, 19.8, 20.1, 20.10, and 22.2) are fully devoted to discussing the practice of operations research in such ways, along with briefer mentions elsewhere.

The new emphases describe above benefited greatly from our work in developing our recent new textbook with Mark S. Hillier (Introduction to Management Science: A Modeling and Case Studies Approach with Spreadsheets, Irwin/McGraw-Hill, 2000). That book has a very different orientation from this one. It is aimed directly at business students rather than students who may be in engineering and the mathematical sciences, and it provides almost no coverage of the mathematical and algorithms of operations research. Nevertheless, its applied orientation enabled us to adapt some excellent material developed for that book to provide a more well-rounded coverage in this edition.

OTHER FEATURES

In addition to all the new software and new emphases just described, this edition received a considerable number of other enhancements as well.

The previous section on project planning and control with PERT/CPM has been replaced by a complete new chapter (Chap. 10) with an applied orientation. Using the activity-on-node (AON) convention, this chapter provides an extensive modern treatment of the topic in a very accessible way.

Other new topics not yet mentioned include the SOB mnemonic device for determining the form of constraints in the dual problem (in Sec. 6.4), 100 percent rules for simultaneous changes when conducting sensitivity analysis (in Sec. 6.7), sensitivity analyis with Bayes' decision rule (in Sec. 15.2), a probability tree diagram for calculating posterior probabilities (in Sec. 15.3), a single-server variation of the nonpreemptive priorities model where the service for different priority classes of customers now have different mean service rates (in Sec. 17.8), a new simpler analysis of a stachastic continuous-review inventory model (Sec. 19.5), the mean absolute deviation as a measure of performance for forecasting methods (in Sec. 20.7), and the elements of a mojor simulation study (Sec. 22.5).

We also have added much supplementary text material on the book's new website, www.mhhe.com/hillier. Some of these supplements are password protected, but are available to all instructors who adopt this textbook. For the most part, this material appeared in previous editions of this book and then was subsequently deleted (for space reasons), to the disappointment of some instructors. Some also appeared in our Introduction to Mathematical Programming textbook. As delineated in the table of contents, this supplementary material includes a chapter on probability theory, and a chapter on reliability, along with supplements to a few chapters in the book.

In addition to providing this supplementary text material, the website will give updates about the book, including an errata, as the need arises.

We made two changes in the order of the chapters. The decision analysis chapter has been moved forward to Chap. 15 in front of the stochastic chapters. The game theory chapter has been moved backward to Chap. 14 to place it next to the related decision alalysis chapter. We believe that these changes provide a better transition from topics that are mainly deterministic to those that are mainly stochastic.

Every chapter has received significant revision and updating, ranging from modest refining to extensive rewriting. Chapters receiving a particularly major revision and reorganization included Chaps. 15 (Decision Analysis), 19 (Inventory Theory), 20 (Forecasting), and 22 (Simulation). Many sections in the linear programming and mathematical programming chapters also received major revisions and updating.

The overall thrust of all the revision efforts has been to build upon the strengths of previous editions while thoroughly updating and clarifying the material in a contemporary setting to fully meet the needs of today's students.

We think that the net effect has been to make this edition even more of a "studentbook"---clear, interesting, and well-organized with lots of helpful examples and illustrations, good motivation and perspective, easy-to-find important material, and enjoyable homework, without too much notation, terminology, and dense mathematics. We believe and trust that the numerous instructors who have used previous editions will agree that this is the best edition yet. This feeling has been reinforced by the generally enthusiastic reviews of drafts of this edition.

The prerequisites for this book can be relatively modest. As with previous editions, the mathematics has been kept at a relatively elementary level. Most of Chaps. 1 to 14 (introduction, linear programming, and mathematical programming) require no mathematics beyond high school algebra. Calculus is used only in Chaps. 13 (Nonlinear Programming) and in one example in Chap. 11(Dynamic Programming). Matrix notation is used in Chap. 5 (The Theory of the Simplex Method), Chap. 6 (Duality Theory and Sensitivity Analysis), Sec. 7.4 (An Interior-Point Algorithm), and Chap. 13, but the only background needed for this is presented in Appendix 4. For Chaps. 15 to 22 (probabilistic models), a previous introduction to probability theory is assumed, and calculus is used in a few places. In general terms, the mathematical maturity that a student achieves through taking an elementary calculus course is useful throughout Chaps. 15 to 22 and for the more advanced material in the preceding chapters.

The content of the book is aimed largely at the upper-division undergraduate level (including well-prepared sophmores) and at first-year (master's level) graduate students. Because of the book's great flexibility, there are many ways to package the material into a course. Chapters 1 and 2 give an introduction to the subject to operations research. Chapters 3 to 14 (on linear programming and on mathematical programming) may essentially be covered independently of Chaps. 15 to 22 (on probabilistic models), and vice versa. furthermore, the individual chapters among Chaps. 3 to 14 are almost independent, except that they all use basic material presentedin Chap. 3 and perhaps in Chap. 4. Chapter 6 and Sec. 7.2 also draw upon Chap. 5. Sections 7.1 and 7.2 use parts of Chap. 6. Section 9.6 assumes an acquaintance with the problem formulations in Secs. 8.1 and 8.3, while prior exposure to Secs. 7.3 and 8.2 is helpful (but not essential) in Sec. 9.7. Within Chaps. 15 to 22, there is considerable flexibility of coverage, although some integration of the material is available.

An elementary survey course covering linear programming, mathematical programming, and some probabilistic models can be presented in a quarter (40 hours) or semester by selecting drawing from material throughout the book. For example, a good survey of the field can be obtained from Chaps. 1,2,3,4,15,17,19,20, and 22, along with parts of Chaps. 9, 11, 12, and 13. A more extensive elementary survey course can be completed in two quarters (60 to 80 hours) by excluding just a gew chapters, for example, Chaps. 7, 14, and 21. Chapters 1 to 8 (and perhaps part of Chap. 9) form an excellent basis for a (one-quarter) course in other deterministic models of operations research suitable for presentation in a (one-quarter) course. In fact, these latter three courses (the material in the entire text) can be viewed as a basic one-year sequence in the techniques of operations research, forming the core of a master's degree program. Each course outlined has been presented at either the undergraduate o the graduate level at Stanford University, and this text has been used in the manner suggested.

To assist the instructor who will be covering only a portion of the chapters and who prefers a slimmer book containing only those chapters, all the material (including the supplementary text material on the book's website) has been placed in McGraw-Hill's PRIMIS system. This system enables an instructor to pick and choose precisely which material to include in a self-designed book, and then to order copies for the students at an economical price. For example, this enables instructors who previously used our Introduction to Mathematical Programming or Introduction to Stochastic Models in Operations Research textbooks to obtain updated versions of the same material from the PRIMIS system. For this reason, we will not be publishing new seperate editions of these other books.

Again, as in previous editions, we thank our wives, Ann and Helen, for their encouragement and support during the long process of preparing this 7th edition. Our children, David, John, and Mark Hillier, Janet Lieberman Argyres, and Joanne, Michael, and Diana Lieberman, have literally grown up with the book and our periodic hibernations to prepare a new edition. Now, most of them have used the book as a text in their own college courses, given considerable advice, and even (in the case of Mark Hillier) become a software collaborator. It is a joy to see them and (we trust) the book reach maturity together.

And now I must add a very sad note. My close friend and co-author, Jerry Lieberman, passed away on May 18, 1999, while this edition was in preparation, so I am writing this preface on behalf of both of us. Jerry was one the greatest leaders of our field and he had a profound influence on my life. More than a third of a century ago, we embarked on a mission together to attempt to develop a path-breaking book for teaching operations research at the introductory level. Ever since, we have striven to meet and extend the same high standards for each new edition. Having worked so closely with Jerry for so many years, I believe I understand well how he would want the book to evolve to meet the needs of each new generation of students. As the substantially younger co-author, I am grateful that I am able to carry on our joint mission to continue to update and improve the book, both with this edition and with future editions as well. It is the least I can do to honor Jerry.

I welcome your comments, suggestions, and errata to help me improve the book in the future.

ACKNOWLEDGMENTS

We are indebted to an excellent group of reviewers who provided sage advice throughout the revision process. This group included Jeffery Cochran, Arizona State University, Yahya Fathi, North Carolina State University; Yasser Hosni and Charles Reilly, University of Central Florida; Cerry Klein, University of Missouri---Columbia; Robert Lipset, Ohio Universtiy; Mark Parker, United States Air Force Academy; Christopher Rump, State University of New York at Buffalo; and Ahmad Seifoddini, California Polytechnic State University---San Luis Obispo. We also received helpful advice from Judith Liebman, Siegfried Schaible, David Sloan, and Arthur F. Veinott, Jr., as well as many instructors who sent us letters or e-mail messages. In addition, we also thank many dozens of Stanford students and many students at other universities who gave us helpful written suggestions.

This edition was very much of a team effort. Our case writers, Karl Schmedders and Molly Stephens (both graduates of our department), made a vital contribution. One of our department's current Ph.D. students, Roberto Szechtman, did an excellent job in preparing the solutions manual. Another Ph.D. student, Michael O'Sullivan, was very skillful in updating the software that Mark Hillier had developed for the 5th and 6th editions. Mark (who was born the same year as the first edition and now is tenured faculty member in the Management Science Department at the University of Washington) helped to oversee this updating and also provided both the spreadsheets and the Excel files (including many Excel templates) for this edition. Linus Schrage of the University of Chicago and LINDO Systems (and who took an introductory operations research course from me 37 years ago) supervised the development of LINGO/LINDO files for the various chapters as well as providing tutorial material for the CD-ROM. Another long-time friend, Bjarni Kristjansson (who heads Maximal Software), did the same thing for the MPL/CPLEX files and MPL tutorial material, as well as arranging to provide student versions of MPL, CPLEX, CONOPT, and OptiMax 2000 for the CD-ROM. One of our department's Ph.D. graduates, Irv Lustig, was the ILOG project manager for providing CPLEX. Linus, Bjarni, and Irv all were helpful in checking material going into this edition regarding their software. Ann Hillier devoted numerous long days and nights to sitting with a Macintosh, doing word processing and constructing many figures and tables, in addition to endless cutting and pasting, photocopying, and FedExing of material. Helen Lieberman also carried a heavy burden in supporting Jerry. They all were vital members of the team.

The inside back cover lists the various companies and individuals who have provided software for the CD-ROM. We greatly appreciate their key contributions.

It was a real pleasure working with McGraw-Hill's thoroughly professional editorial and production staff, including Eric Munson (executive editor), Maja Lorkovic (developmental editor), and Christine Vaughn (project manager).

Frederick S. Hillier
Stanford University (fhillier@Leland.Stanford.edu) January 2000

Home Page