F
or over four decades, Introduction to Operations Research has been the classic text on operations research.
New Emphasis on Real Applications
Introduction to Operations Research and the Institute for
research for further reading
Additional New Features:
All Excel
®
coverage has been updated for Excel 2007
state of the art
The text website (www.mhhe.com/hillier) features the following material for
students and instructors:
Introduction to
Ninth Edition
Frederick S. Hillier
Gerald J. Lieberman
Operations
Research
Introduction to
Ninth
Edition
Hillier
Lieberman
Operations Research
MD DALIM 1000954 12/26/08 CYAN MAG YELO BLACK
INTRODUCTION TO
OPERATIONS RESEARCH
Ninth Edition
FREDERICK S. HILLIER
Stanford University
GERALD J. LIEBERMAN
Late of Stanford University
hil76299_fm_i-xxiv.qxd 12/16/08 06:51 PM Page i
Rev.Confirming Pages
INTRODUCTION TO OPERATIONS RESEARCH, NINTH EDITION
Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas,
New York, NY 10020. Copyright © 2010 by The McGraw-Hill Companies, Inc. All rights reserved. Previous
editions © 2005, 2001, and 1995. No part of this publication may be reproduced or distributed in any form or
by any means, or stored in a database or retrieval system, without the prior written consent of The McGraw-Hill
Companies, Inc., including, but not limited to, in any network or other electronic storage or transmission, or
broadcast for distance learning.
Some ancillaries, including electronic and print components, may not be available to customers outside the
United States.
This book is printed on acid-free paper
1 2 3 4 5 6 7 8 9 0 CCW/CCW 0 9
ISBN 978-0-07-337629-5
MHID 0-07-337629-9
Global Publisher: Raghothaman Srinivasan
Sponsoring Editor: Debra B. Hash
Director of Development: Kristine Tibbetts
Developmental Editor: Lora Neyens
Senior Marketing Manager: Curt Reynolds
Project Manager: Melissa M. Leick
Senior Production Supervisor: Laura Fuller
Senior Media Project Manager: Sandra M. Schnee
Associate Design Coordinator: Brenda A. Rolwes
Cover Designer: Studio Montage, St. Louis, Missouri
Compositor: Laserwords Private Limited
Typeface: 10/12 Times Roman
Printer: Courier Westford, Inc.
Library of Congress Cataloging-in-Publication Data
Hillier, Frederick S.
Introduction to operations research / Frederick S. Hillier, Gerald J. Lieberman.—9th ed.
p. cm.
Includes index.
ISBN 978-0-07-337629-5 — ISBN 0-07-337629-9 (hbk. : alk. paper) 1. Operations research. I.
Lieberman, Gerald J. II. Title.
T57.6.H53 2010
658.4'032—dc22
2008039045
www.mhhe.com
hil76299_fm_i-xxiv.qxd 12/16/08 06:51 PM Page ii
Rev.Confirming Pages
ABOUT THE AUTHORS
Frederick S. Hillier was born and raised in Aberdeen, Washington, where he was an
award winner in statewide high school contests in essay writing, mathematics, debate,
and music. As an undergraduate at Stanford University he ranked first in his engineer-
ing class of over 300 students. He also won the McKinsey Prize for technical writing,
won the Outstanding Sophomore Debater award, played in the Stanford Woodwind
Quintet, and won the Hamilton Award for combining excellence in engineering with no-
table achievements in the humanities and social sciences. Upon his graduation with a
B.S. degree in Industrial Engineering, he was awarded three national fellowships
(National Science Foundation, Tau Beta Pi, and Danforth) for graduate study at Stanford
with specialization in operations research. After receiving his PhD degree, he joined the
faculty of Stanford University, where he earned tenure at the age of 28 and the rank of
full professor at 32. He also received visiting appointments at Cornell University,
Carnegie-Mellon University, the Technical University of Denmark, the University of
Canterbury (New Zealand), and the University of Cambridge (England). After 35 years
on the Stanford faculty, he took early retirement from his faculty responsibilities in 1996
in order to focus full time on textbook writing, and now is Professor Emeritus of Oper-
ations Research at Stanford.
Dr. Hillier’s research has extended into a variety of areas, including integer program-
ming, queueing theory and its application, statistical quality control, and the application of
operations research to the design of production systems and to capital budgeting. He has
published widely, and his seminal papers have been selected for republication in books of
selected readings at least 10 times. He was the first-prize winner of a research contest on
“Capital Budgeting of Interrelated Projects” sponsored by The Institute of Management
Sciences (TIMS) and the U.S. Office of Naval Research. He and Dr. Lieberman also re-
ceived the honorable mention award for the 1995 Lanchester Prize (best English-language
publication of any kind in the field of operations research), which was awarded by the In-
stitute of Operations Research and the Management Sciences (INFORMS) for the 6th edition
of this book. In addition, he was the recipient of the prestigious 2004 INFORMS Expository
Writing Award for the 8th edition of this book.
Dr. Hillier has held many leadership positions with the professional societies in his field.
For example, he has served as Treasurer of the Operations Research Society of America
(ORSA), Vice President for Meetings of TIMS, Co-General Chairman of the 1989 TIMS
International Meeting in Osaka, Japan, Chair of the TIMS Publications Committee,
Chair of the ORSA Search Committee for Editor of Operations Research, Chair of the
ORSA Resources Planning Committee, Chair of the ORSA/TIMS Combined Meetings
Committee, and Chair of the John von Neumann Theory Prize Selection Committee
for INFORMS. He continues to serve as the Series Editor for Springer’s International
Series in Operations Research and Management Science, a particularly prominent book
series that he founded in 1993.
In addition to Introduction to Operations Research and two companion volumes,
Introduction to Mathematical Programming (2nd ed., 1995) and Introduction to Sto-
chastic Models in Operations Research (1990), his books are The Evaluation of Risky
Interrelated Investments (North-Holland, 1969), Queueing Tables and Graphs (Elsevier
North-Holland, 1981, co-authored by O. S. Yu, with D. M. Avis, L. D. Fossett, F. D. Lo,
iii
hil76299_fm_i-xxiv.qxd 12/16/08 06:51 PM Page iii
Rev.Confirming Pages
iv ABOUT THE AUTHORS
and M. I. Reiman), and Introduction to Management Science: A Modeling and Case
Studies Approach with Spreadsheets (3rd ed., McGraw-Hill/Irwin, 2008, co-authored by
M. S. Hillier).
The late Gerald J. Lieberman sadly passed away in 1999. He had been Professor
Emeritus of Operations Research and Statistics at Stanford University, where he was the
founding chair of the Department of Operations Research. He was both an engineer (hav-
ing received an undergraduate degree in mechanical engineering from Cooper Union) and
an operations research statistician (with an AM from Columbia University in mathematical
statistics, and a PhD from Stanford University in statistics).
Dr. Lieberman was one of Stanford’s most eminent leaders in recent decades. After
chairing the Department of Operations Research, he served as Associate Dean of the School
of Humanities and Sciences, Vice Provost and Dean of Research, Vice Provost and Dean
of Graduate Studies, Chair of the Faculty Senate, member of the University Advisory
Board, and Chair of the Centennial Celebration Committee. He also served as Provost or
Acting Provost under three different Stanford presidents.
Throughout these years of university leadership, he also remained active profession-
ally. His research was in the stochastic areas of operations research, often at the interface
of applied probability and statistics. He published extensively in the areas of reliability
and quality control, and in the modeling of complex systems, including their optimal de-
sign, when resources are limited.
Highly respected as a senior statesman of the field of operations research, Dr. Lieberman
served in numerous leadership roles, including as the elected president of The Institute of
Management Sciences. His professional honors included being elected to the National
Academy of Engineering, receiving the Shewhart Medal of the American Society for
Quality Control, receiving the Cuthbertson Award for exceptional service to Stanford Univer-
sity, and serving as a fellow at the Center for Advanced Study in the Behavioral Sciences. In
addition, the Institute of Operations Research and the Management Sciences (INFORMS)
awarded him and Dr. Hillier the honorable mention award for the 1995 Lanchester Prize for
the 6th edition of this book. In 1996, INFORMS also awarded him the prestigious Kimball
Medal for his exceptional contributions to the field of operations research and management
science.
In addition to Introduction to Operations Research and two companion volumes, Intro-
duction to Mathematical Programming (2nd ed., 1995) and Introduction to Stochastic Models
in Operations Research (1990), his books are Handbook of Industrial Statistics (Prentice-
Hall, 1955, co-authored by A. H. Bowker), Tables of the Non-Central t-Distribution (Stan-
ford University Press, 1957, co-authored by G. J. Resnikoff), Tables of the Hypergeometric
Probability Distribution (Stanford University Press, 1961, co-authored by D. Owen),
Engineering Statistics, Second Edition (Prentice-Hall, 1972, co-authored by A. H. Bowker),
and Introduction to Management Science: A Modeling and Case Studies Approach with
Spreadsheets (McGraw-Hill/Irwin, 2000, co-authored by F. S. Hillier and M. S. Hillier).
hil76299_fm_i-xxiv.qxd 12/16/08 06:51 PM Page iv
Rev.Confirming Pages