Prelims.tex 22/10/2007 14: 25 Page i OPERATIONS RESEARCH AND MANAGEMENT SCIENCE H A N D B O O K © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page ii The Operations Research Series Series Editor: A. Ravi Ravindran Dept. of Industrial & Manufacturing Engineering The Pennsylvania State University, USA Integer Programming: Theory and Practice John K. Karlof Operations Research: A Practical Approach Michael W. Carter and Camille C. Price Operations Research and Management Science Handbook A. Ravi Ravindran Operations Research Calculations Handbook Dennis Blumenfeld Forthcoming Titles Applied Nonlinear Optimization in Modeling Environments Janos D. Pinter Operations Research Calculations Handbook, Second Edition Dennis Blumenfeld Probability Models in Operations Research Richard C. Cassady and Joel A. Nachlas © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page iii OPERATIONS RESEARCH AND MANAGEMENT SCIENCE H A N D B O O K EDITED BY A. RAVI RAVINDRAN Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page iv CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2008 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-13: 978-0-8493-9721-9 (Hardcover) This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http:// www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC) 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For orga- nizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging-in-Publication Data Operations research and management science handbook / editor, A. Ravi Ravindran. p. cm. -- (Operations research series) Includes bibliographical references and index. ISBN 978-0-8493-9721-9 (alk. paper) 1. Operations research--Handbooks, manuals, etc. I. Ravindran, Ravi. II. Title. III. Series. T57.6.A32 1982 658.4’034--dc22 2007019976 Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page v Dedication This book is dedicated to the memory of Professor G. V. Loganathan, author of Chapter 24, who was killed in the Virginia Tech campus tragedy on April 16, 2007. © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page vii Contents Preface .................................................................................... xiii Acknowledgments ........................................................................ xv Editor ..................................................................................... xvii Contributors ............................................................................. xix History of Operations Research and Management Science ........................ xxi I OR/MS Models and Methods 1 Linear Programming Katta G. Murty ................................................................... 1-1 1.1 Brief History of Algorithms for Solving Linear Equations, Linear Inequalities, and LPs ...................................................... 1-1 1.2 Applicability of the LP Model: Classical Examples of Direct Applications ........................................................ 1-4 1.3 LP Models Involving Transformations of Variables ...................... 1-12 1.4 Intelligent Modeling Essential to Get Good Results, an Example from Container Shipping ........................................................ 1-18 1.5 Planning Uses of LP Models .............................................. 1-22 1.6 Brief Introduction to Algorithms for Solving LP Models ................ 1-26 1.7 Software Systems Available for Solving LP Models ...................... 1-31 1.8 Multiobjective LP Models ................................................. 1-31 2 Nonlinear Programming Theodore B. Trafalis and Robin C. Gilbert ...................................... 2-1 2.1 Introduction ................................................................ 2-1 2.2 Unconstrained Optimization .............................................. 2-3 2.3 Constrained Optimization ................................................. 2-15 2.4 Conclusion ................................................................. 2-19 3 Integer Programming Michael Weng ..................................................................... 3-1 3.1 Introduction ................................................................ 3-1 3.2 Formulation of IP Models ................................................. 3-3 3.3 Branch and Bound Method ............................................... 3-7 3.4 Cutting Plane Method ..................................................... 3-12 3.5 Other Solution Methods and Computer Solution ........................ 3-15 4 Network Optimization Mehmet Bayram Yildirim ........................................................ 4-1 4.1 Introduction ................................................................ 4-1 4.2 Notation .................................................................... 4-2 vii © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page viii viii Contents 4.3 Minimum Cost Flow Problem ............................................. 4-3 4.4 Shortest Path Problem .................................................... 4-4 4.5 Maximum Flow Problem .................................................. 4-8 4.6 Assignment Problem ....................................................... 4-13 4.7 Minimum Spanning Tree Problem ........................................ 4-14 4.8 Minimum Cost Multicommodity Flow Problem .......................... 4-18 4.9 Conclusions ................................................................ 4-19 5 Multiple Criteria Decision Making Abu S. M. Masud and A. Ravi Ravindran ....................................... 5-1 5.1 Some Definitions ........................................................... 5-3 5.2 The Concept of “Best Solution” .......................................... 5-4 5.3 Criteria Normalization ..................................................... 5-5 5.4 Computing Criteria Weights .............................................. 5-6 5.5 Multiple Criteria Methods for Finite Alternatives ................................................................ 5-8 5.6 Multiple Criteria Mathematical Programming Problems ................ 5-15 5.7 Goal Programming ........................................................ 5-19 5.8 Method of Global Criterion and Compromise Programming ............ 5-27 5.9 Interactive Methods ....................................................... 5-29 5.10 MCDM Applications ....................................................... 5-34 5.11 MCDM Software ........................................................... 5-35 5.12 Further Readings .......................................................... 5-35 6 Decision Analysis Cerry M. Klein .................................................................... 6-1 6.1 Introduction ................................................................ 6-1 6.2 Terminology for Decision Analysis ........................................ 6-2 6.3 Decision Making under Risk .............................................. 6-3 6.4 Decision Making under Uncertainty ...................................... 6-17 6.5 Practical Decision Analysis ................................................ 6-21 6.6 Conclusions ................................................................ 6-28 6.7 Resources ................................................................... 6-29 7 Dynamic Programming Jos´e A. Ventura ................................................................... 7-1 7.1 Introduction ................................................................ 7-1 7.2 Deterministic Dynamic Programming Models ............................ 7-3 7.3 Stochastic Dynamic Programming Models ............................... 7-19 7.4 Conclusions ................................................................ 7-24 8 Stochastic Processes Susan H. Xu ...................................................................... 8-1 8.1 Introduction ................................................................ 8-1 8.2 Poisson Processes .......................................................... 8-7 8.3 Discrete-Time Markov Chains ............................................. 8-14 8.4 Continuous-Time Markov Chains ......................................... 8-27 © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page ix Contents ix 8.5 Renewal Theory ............................................................ 8-39 8.6 Software Products Available for Solving Stochastic Models .......................................................... 8-46 9 Queueing Theory Natarajan Gautam ................................................................ 9-1 9.1 Introduction ................................................................ 9-1 9.2 Queueing Theory Basics ................................................... 9-2 9.3 Single-Station and Single-Class Queues ................................... 9-8 9.4 Single-Station and Multiclass Queues ..................................... 9-21 9.5 Multistation and Single-Class Queues .................................... 9-28 9.6 Multistation and Multiclass Queues ...................................... 9-34 9.7 Concluding Remarks ....................................................... 9-37 10 Inventory Control Farhad Azadivar and Atul Rangarajan ........................................... 10-1 10.1 Introduction ................................................................ 10-1 10.2 Design of Inventory Systems .............................................. 10-4 10.3 Deterministic Inventory Systems .......................................... 10-9 10.4 Stochastic Inventory Systems ............................................. 10-20 10.5 Inventory Control at Multiple Locations ................................. 10-27 10.6 Inventory Management in Practice ....................................... 10-34 10.7 Conclusions ................................................................ 10-35 10.8 Current and Future Research ............................................. 10-36 11 Complexity and Large-Scale Networks Hari P. Thadakamalla, Soundar R.T. Kumara, and R´eka Albert ............... 11-1 11.1 Introduction ................................................................ 11-1 11.2 Statistical Properties of Complex Networks .............................. 11-6 11.3 Modeling of Complex Networks ........................................... 11-11 11.4 Why “Complex” Networks ................................................ 11-16 11.5 Optimization in Complex Networks ....................................... 11-18 11.6 Conclusions ................................................................ 11-26 12 Simulation Catherine M. Harmonosky ........................................................ 12-1 12.1 Introduction ................................................................ 12-1 12.2 Basics of Simulation ....................................................... 12-3 12.3 Simulation Languages and Software ...................................... 12-15 12.4 Simulation Projects—The Bigger Picture ................................ 12-20 12.5 Summary ................................................................... 12-22 13 Metaheuristics for Discrete Optimization Problems Rex K. Kincaid .................................................................... 13-1 13.1 Mathematical Framework for Single Solution Metaheuristics ............ 13-3 13.2 Network Location Problems ............................................... 13-3 13.3 Multistart Local Search ................................................... 13-5 13.4 Simulated Annealing ....................................................... 13-6 13.5 Plain Vanilla Tabu Search ................................................. 13-8 13.6 Active Structural Acoustic Control (ASAC) ............................. 13-10 © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page x x Contents 13.7 Nature Reserve Site Selection ............................................. 13-13 13.8 Damper Placement in Flexible Truss Structures ......................... 13-21 13.9 Reactive Tabu Search ...................................................... 13-29 13.10 Discussion .................................................................. 13-35 14 Robust Optimization H. J. Greenberg and Tod Morrison ............................................... 14-1 14.1 Introduction ................................................................ 14-1 14.2 Classical Models ........................................................... 14-2 14.3 Robust Optimization Models .............................................. 14-10 14.4 More Applications ......................................................... 14-16 14.5 Summary ................................................................... 14-30 II OR/MS Applications 15 Project Management Adedeji B. Badiru.................................................................. 15-1 15.1 Introduction ................................................................ 15-1 15.2 Critical Path Method ...................................................... 15-3 15.3 PERT Network Analysis .................................................. 15-18 15.4 Statistical Analysis of Project Duration .................................. 15-23 15.5 Precedence Diagramming Method ........................................ 15-26 15.6 Software Tools for Project Management .................................. 15-34 15.7 Conclusion ................................................................. 15-37 16 Quality Control Qianmei Feng and Kailash C. Kapur............................................. 16-1 16.1 Introduction ................................................................ 16-1 16.2 Quality Control and Product Life Cycle .................................. 16-2 16.3 New Trends and Relationship to Six Sigma .............................. 16-5 16.4 Statistical Process Control ................................................ 16-7 16.5 Process Capability Studies ................................................ 16-16 16.6 Advanced Control Charts ................................................. 16-18 16.7 Limitations of Acceptance Sampling ...................................... 16-20 16.8 Conclusions ................................................................ 16-20 17 Reliability Lawrence M. Leemis ............................................................... 17-1 17.1 Introduction ................................................................ 17-1 17.2 Reliability in System Design .............................................. 17-3 17.3 Lifetime Distributions ..................................................... 17-10 17.4 Parametric Models ......................................................... 17-17 17.5 Parameter Estimation in Survival Analysis .............................. 17-22 17.6 Nonparametric Methods ................................................... 17-32 17.7 Assessing Model Adequacy ................................................ 17-36 17.8 Summary ................................................................... 17-40 © 2008 by Taylor & Francis Group, LLC Prelims.tex 22/10/2007 14: 25 Page xi Contents xi 18 Production Systems Bobbie L. Foote and Katta G. Murty ............................................. 18-1 18.1 Production Planning Problem ............................................. 18-1 18.2 Demand Forecasting ....................................................... 18-2 18.3 Models for Production Layout Design .................................... 18-12 18.4 Scheduling of Production and Service Systems ........................... 18-20 19 Energy Systems C. Randy Hudson and Adedeji B. Badiru ........................................ 19-1 19.1 Introduction ................................................................ 19-1 19.2 Definition of Energy ....................................................... 19-2 19.3 Harnessing Natural Energy ................................................ 19-3 19.4 Mathematical Modeling of Energy Systems .............................. 19-3 19.5 Linear Programming Model of Energy Resource Combination .......... 19-4 19.6 Integer Programming Model for Energy Investment Options ............ 19-5 19.7 Simulation and Optimization of Distributed Energy Systems ........... 19-11 19.8 Point-of-Use Energy Generation .......................................... 19-11 19.9 Modeling of CHP Systems ................................................ 19-12 19.10 Economic Optimization Methods ......................................... 19-13 19.11 Design of a Model for Optimization of CHP System Capacities ........ 19-16 19.12 Capacity Optimization .................................................... 19-21 19.13 Implementation of the Computer Model .................................. 19-24 19.14 Other Scenarios ............................................................ 19-27 20 Airline Optimization Jane L. Snowdon and Giuseppe Paleologo ....................................... 20-1 20.1 Introduction ................................................................ 20-1 20.2 Schedule Planning ......................................................... 20-5 20.3 Revenue Management ..................................................... 20-14 20.4 Aircraft Load Planning .................................................... 20-21 20.5 Future Research Directions and Conclusions ............................. 20-23 21 Financial Engineering Aliza R. Heching and Alan J. King .............................................. 21-1 21.1 Introduction ................................................................ 21-1 21.2 Return ...................................................................... 21-3 21.3 Estimating an Asset’s Mean and Variance ............................... 21-4 21.4 Diversification .............................................................. 21-6 21.5 Efficient Frontier ........................................................... 21-8 21.6 Utility Analysis ............................................................ 21-10 21.7 Black–Litterman Asset Allocation Model ................................. 21-13 21.8 Risk Management .......................................................... 21-18 21.9 Options ..................................................................... 21-22 21.10 Valuing Options ............................................................ 21-24 21.11 Dynamic Programming .................................................... 21-28 21.12 Pricing American Options Using Dynamic Programming ............... 21-29 21.13 Comparison of Monte Carlo Simulation and Dynamic Programming ... 21-33 21.14 Multi-Period Asset Liability Management ................................ 21-33 21.15 Conclusions ................................................................ 21-36 © 2008 by Taylor & Francis Group, LLC