第1页 / 共1238页
第2页 / 共1238页
第3页 / 共1238页
第4页 / 共1238页
第5页 / 共1238页
第6页 / 共1238页
第7页 / 共1238页
第8页 / 共1238页
运筹学导论Introduction To Operations Research.pdf
COVER
ABOUT THE AUTHORS
ABOUT THE CASE WRITERS
DEDICATION
PREFACE
A WEALTH OF SOFTWARE OPTIONS
NEW EMPHASES
OTHER FEATURES
ACKNOWLEDGMENTS
TABLE OF CONTENTS
1 Introduction
1.1 THE ORIGINS OF OPERATIONS RESEARCH
1.2 THE NATURE OF OPERATIONS RESEARCH
1.3 THE IMPACT OF OPERATIONS RESEARCH
1.4 ALGORITHMS AND OR COURSEWARE
2 Overview of the Operations Research Modeling Approach
2.1 DEFINING THE PROBLEM AND GATHERING DATA
2.2 FORMULATING A MATHEMATICAL MODEL
2.3 DERIVING SOLUTIONS FROM THE MODEL
2.4 TESTING THE MODEL
2.5 PREPARING TO APPLY THE MODEL
2.6 IMPLEMENTATION
2.7 CONCLUSIONS
3 Introduction to Linear Programming
3.1 PROTOTYPE EXAMPLE
Formulation as a Linear Programming Problem
Graphical Solution
Conclusions
Continuing the Learning Process with Your OR Courseware
3.2 THE LINEAR PROGRAMMING MODEL
A Standard Form of the Model
Other Forms
Terminology for Solutions of the Model
3.3 ASSUMPTIONS OF LINEAR PROGRAMMING
Proportionality
Additivity
Divisibility
Certainty
The Assumptions in Perspective
3.4 ADDITIONAL EXAMPLES
Design of Radiation Therapy
Regional Planning
Controlling Air Pollution
Reclaiming Solid Wastes
Personnel Scheduling
Distributing Goods through a Distribution Network
3.5 SOME CASE STUDIES
Choosing the Product Mix at Ponderosa Industrial
Personnel Scheduling at United Airlines
Planning Supply, Distribution, and Marketing at Citgo Petroleum Corporation
3.6 DISPLAYING AND SOLVING LINEAR PROGRAMMING MODELS ON A SPREADSHEET
Displaying the Model on a Spreadsheet
Using the Excel Solver to Solve the Model
3.7 FORMULATING VERY LARGE LINEAR PROGRAMMING MODELS
Modeling Languages
An Example of a Problem with a Huge Model
The Structure of the Resulting Model
Formulation of the Model in MPL
The LINGO Modeling Language
3.8 CONCLUSIONS
Formulation of the Model in LINGO
Importing and Exporting Spreadsheet Data with LINGO
Importing and Exporting from a Database with LINGO
More about LINGO
A Demonstration Example in OR Tutor:
An Excel Add-In:
“Ch. 3—Intro to LP” Files for Solving the Examples:
Supplement to Appendix 3.1:
4 Solving Linear Programming Problems: The Simplex Method
4.1 THE ESSENCE OF THE SIMPLEX METHOD
Solving the Example
The Key Solution Concepts
4.2 SETTING UP THE SIMPLEX METHOD
4.3 THE ALGEBRA OF THE SIMPLEX METHOD
Initialization
Optimality Test
Determining the Direction of Movement (Step 1 of an Iteration)
Determining Where to Stop (Step 2 of an Iteration)
Solving for the New BF Solution (Step 3 of an Iteration)
Optimality Test for the New BF Solution
Iteration 2 and the Resulting Optimal Solution
4.4 THE SIMPLEX METHOD IN TABULAR FORM
Summary of the Simplex Method (and Iteration 1 for the Example)
Iteration 2 for the Example and the Resulting Optimal Solution
4.5 TIE BREAKING IN THE SIMPLEX METHOD
Tie for the Entering Basic Variable
Tie for the Leaving Basic Variable—Degeneracy
No Leaving Basic Variable—Unbounded
Multiple Optimal Solutions
4.6 ADAPTING TO OTHER MODEL FORMS
Equality Constraints
Negative Right-Hand Sides
Functional Constraints in
Form
Minimization
Solving the Radiation Therapy Example
The Two-Phase Method
No Feasible Solutions
Variables Allowed to Be Negative
4.7 POSTOPTIMALITY ANALYSIS
Reoptimization
Shadow Prices
Sensitivity Analysis
Using Excel to Generate Sensitivity Analysis Information
Parametric Linear Programming
4.8 COMPUTER IMPLEMENTATION
Implementation of the Simplex Method
Linear Programming Software Featured in This Book
4.9 THE INTERIOR-POINT APPROACH TO SOLVING LINEAR PROGRAMMING PROBLEMS
The Key Solution Concept
Comparison with the Simplex Method
The Complementary Roles of the Simplex Method and the Interior-Point Approach
4.10 CONCLUSIONS
Demonstration Examples in OR Tutor:
Interactive Routines:
An Automatic Routine:
An Excel Add-In:
Files (Chapter 3) for Solving the Wyndor and Radiation Therapy Examples:
5 The Theory of the Simplex Method
5.1 FOUNDATIONS OF THE SIMPLEX METHOD
Terminology
Adjacent CPF Solutions
Properties of CPF Solutions
Extensions to the Augmented Form of the Problem
5.2 THE REVISED SIMPLEX METHOD
Solving for a Basic Feasible Solution
Matrix Form of the Current Set of Equations
The Overall Procedure
General Observations
5.3 A FUNDAMENTAL INSIGHT
Mathematical Summary
Adapting to Other Model Forms
Applications
5.4 CONCLUSIONS
A Demonstration Example in OR Tutor:
Interactive Routines:
Files (Chapter 3) for Solving the Wyndor Example:
6 Duality Theory and Sensitivity Analysis
6.1 THE ESSENCE OF DUALITY THEORY
Origin of the Dual Problem
Summary of Primal-Dual Relationships
Applications
6.2 ECONOMIC INTERPRETATION OF DUALITY
Interpretation of the Dual Problem
Interpretation of the Simplex Method
6.3 PRIMAL-DUAL RELATIONSHIPS
Complementary Basic Solutions
Relationships between Complementary Basic Solutions
6.4 ADAPTING TO OTHER PRIMAL FORMS
6.5 THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS
Changes in the Coefficients of a Nonbasic Variable
Introduction of a New Variable
Other Applications
6.6 THE ESSENCE OF SENSITIVITY ANALYSIS
6.7 APPLYING SENSITIVITY ANALYSIS
Case 1—Changes in
Case 2
—Changes in the Coefficients of a Nonbasic Variable
Case 2
—Introduction of a New Variable
Case 3—Changes in the Coefficients of a Basic Variable
Case 4—Introduction of a New Constraint
Systematic Sensitivity Analysis—Parametric Programming
6.8 CONCLUSIONS
A Demonstration Example in OR Tutor:
Interactive Routines:
An Excel Add-In:
Files (Chapter 3) for Solving the Wyndor Example:
7 Other Algorithms for Linear Programming
7.1 THE DUAL SIMPLEX METHOD
7.2 PARAMETRIC LINEAR PROGRAMMING
Systematic Changes in the
Parameters
Systematic Changes in the
Parameters
7.3 THE UPPER BOUND TECHNIQUE
7.4 AN INTERIOR-POINT ALGORITHM
The Relevance of the Gradient for Concepts 1 and 2
Using the Projected Gradient to Implement Concepts 1 and 2
A Centering Scheme for Implementing Concept 3
Summary and Illustration of the Algorithm
7.5 LINEAR GOAL PROGRAMMING AND ITS SOLUTION PROCEDURES
Prototype Example for Nonpreemptive Goal Programming
Preemptive Goal Programming
The Sequential Procedure for Preemptive Goal Programming
The Streamlined Procedure for Preemptive Goal Programming
7.6 CONCLUSIONS
Interactive Routines:
An Automatic Routine:
An Excel Add-In:
“Ch. 7—Other Algorithms for LP” Files for Solving the Examples:
8 The Transportation and Assignment Problems
8.1 THE TRANSPORTATION PROBLEM
Prototype Example
An Award Winning Application of a Transportation Problem
The Transportation Problem Model
Using Excel to Formulate and Solve Transportation Problems
An Example with a Dummy Destination
An Example with a Dummy Source
8.2 A STREAMLINED SIMPLEX METHOD FOR THE TRANSPORTATION PROBLEM
Setting Up the Transportation Simplex Method
Initialization
Optimality Test
An Iteration
8.3 THE ASSIGNMENT PROBLEM
Prototype Example
The Assignment Problem Model and Solution Procedures
Example—Assigning Products to Plants
8.4 CONCLUSIONS
A Demonstration Example in OR Tutor:
Interactive Routines:
An Excel Add-in:
“Ch. 8—Transp. & Assignment” Files for Solving the Examples:
Supplement to this Chapter:
9 Network Optimization Models
9.1 PROTOTYPE EXAMPLE
9.2 THE TERMINOLOGY OF NETWORKS
9.3 THE SHORTEST-PATH PROBLEM
Applying This Algorithm to the Seervada Park Shortest-Path Problem
Using Excel to Formulate and Solve Shortest-Path Problems
Other Applications
9.4 THE MINIMUM SPANNING TREE PROBLEM
Some Applications
An Algorithm
Applying This Algorithm to the Seervada Park Minimum Spanning Tree Problem
9.5 THE MAXIMUM FLOW PROBLEM
Some Applications
An Algorithm
Applying This Algorithm to the Seervada Park Maximum Flow Problem
Finding an Augmenting Path
Using Excel to Formulate and Solve Maximum Flow Problems
9.6 THE MINIMUM COST FLOW PROBLEM
Some Applications
Formulation of the Model
An Example
Using Excel to Formulate and Solve Minimum Cost Flow Problems
Special Cases
9.7 THE NETWORK SIMPLEX METHOD
Incorporating the Upper Bound Technique
Correspondence between BF Solutions and Feasible Spanning Trees
Selecting the Entering Basic Variable
Finding the Leaving Basic Variable and the Next BF Solution
9.8 CONCLUSIONS
A Demonstration Example in OR Tutor:
An Interactive Routine:
An Excel Add-in:
“Ch. 9—Network Opt Models” Files for Solving the Examples:
10 Project Management with PERT/CPM
10.1 A PROTOTYPE EXAMPLE—THE RELIABLE CONSTRUCTION CO. PROJECT
10.2 USING A NETWORK TO VISUALLY DISPLAY A PROJECT
Project Networks
Using Microsoft Project
10.3 SCHEDULING A PROJECT WITH PERT/CPM
The Critical Path
Scheduling Individual Activities
Identifying Slack in the Schedule
Review
10.4 DEALING WITH UNCERTAIN ACTIVITY DURATIONS
The PERT Three-Estimate Approach
Three Simplifying Approximations
Approximating the Probability of Meeting the Deadline
10.5 CONSIDERING TIME-COST TRADE-OFFS
Time-Cost Trade-Offs for Individual Activities
Which Activities Should Be Crashed?
Using Linear Programming to Make Crashing Decisions
Mr. Perty’s Conclusions
10.6 SCHEDULING AND CONTROLLING PROJECT COSTS
Scheduling Project Costs
Controlling Project Costs
10.7 AN EVALUATION OF PERT/CPM
The Value of PERT/CPM
Using the Computer
Approximating the Means and Variances of Activity Durations
Approximating the Probability of Meeting the Deadline
Dealing with Overlapping Activities
Incorporating the Allocation of Resources to Activities
The Future
10.8 CONCLUSIONS
“Ch. 10—Project Management” Files:
Excel Templates in Excel File:
An Excel Add-in:
Special Software:
MS Project Folder:
11 Dynamic Programming
11.1 A PROTOTYPE EXAMPLE FOR DYNAMIC PROGRAMMING
Solving the Problem
11.2 CHARACTERISTICS OF DYNAMIC PROGRAMMING PROBLEMS
11.3 DETERMINISTIC DYNAMIC PROGRAMMING
A Prevalent Problem Type—The Distribution of Effort Problem
11.4 PROBABILISTIC DYNAMIC PROGRAMMING
11.5 CONCLUSIONS
“Ch. 11—Dynamic Programming” LINGO File
12 Integer Programming
12.1 PROTOTYPE EXAMPLE
The BIP Model
Software Options for Solving Such Models
12.2 SOME BIP APPLICATIONS
Capital Budgeting with Fixed Investment Proposals
Site Selection
Designing a Production and Distribution Network
Dispatching Shipments
Scheduling Interrelated Activities
Scheduling Asset Divestitures
Airline Applications
12.3 INNOVATIVE USES OF BINARY VARIABLES IN MODEL FORMULATION
Either-Or Constraints
out of
Constraints Must Hold
Functions with
Possible Values
The Fixed-Charge Problem
Binary Representation of General Integer Variables
12.4 SOME FORMULATION EXAMPLES
12.5 SOME PERSPECTIVES ON SOLVING INTEGER PROGRAMMING PROBLEMS
12.6 THE BRANCH-AND-BOUND TECHNIQUE AND ITS APPLICATION TO BINARY INTEGER PROGRAMMING
Branching
Bounding
Fathoming
Completing the Example
Other Options with the Branch-and-Bound Technique
12.7 A BRANCH-AND-BOUND ALGORITHM FOR MIXED INTEGER PROGRAMMING
12.8 OTHER DEVELOPMENTS IN SOLVING BIP PROBLEMS
Background
Automatic Problem Preprocessing for Pure BIP
Generating Cutting Planes for Pure BIP
12.9 CONCLUSIONS
Demonstration Examples in OR Tutor:
Interactive Routines:
An Excel Add-in:
“Ch. 12—Integer Programming” Files for Solving the Examples:
13 Nonlinear Programming
13.1 SAMPLE APPLICATIONS
The Product-Mix Problem with Price Elasticity
The Transportation Problem with Volume Discounts on Shipping Costs
Portfolio Selection with Risky Securities
13.2 GRAPHICAL ILLUSTRATION OF NONLINEAR PROGRAMMING PROBLEMS
13.3 TYPES OF NONLINEAR PROGRAMMING PROBLEMS
Unconstrained Optimization
Linearly Constrained Optimization
Quadratic Programming
Convex Programming
Separable Programming
Nonconvex Programming
Geometric Programming
Fractional Programming
The Complementarity Problem
13.4 ONE-VARIABLE UNCONSTRAINED OPTIMIZATION
The One-Dimensional Search Procedure
13.5 MULTIVARIABLE UNCONSTRAINED OPTIMIZATION
The Gradient Search Procedure
13.6 THE KARUSH-KUHN-TUCKER (KKT) CONDITIONS FOR CONSTRAINED OPTIMIZATION
13.7 QUADRATIC PROGRAMMING
The KKT Conditions for Quadratic Programming
The Modified Simplex Method
Some Software Options
13.8 SEPARABLE PROGRAMMING
Reformulation as a Linear Programming Problem
Extensions
13.9 CONVEX PROGRAMMING
A Sequential Linear Approximation Algorithm (Frank-Wolfe)
Some Software Options
13.10 NONCONVEX PROGRAMMING
Sequential Unconstrained Minimization Technique (SUMT)
13.11 CONCLUSIONS
Demonstration Examples in OR Tutor:
Interactive Routines:
Automatic Routines:
An Excel Add-in:
“Ch. 13—Nonlinear Programming” Files for Solving the Examples:
14 Game Theory
14.1 THE FORMULATION OF TWO-PERSON, ZERO-SUM GAMES
14.2 SOLVING SIMPLE GAMES—A PROTOTYPE EXAMPLE
Formulation as a Two-Person, Zero-Sum Game
Variation 1 of the Example
Variation 2 of the Example
Variation 3 of the Example
14.3 GAMES WITH MIXED STRATEGIES
14.4 GRAPHICAL SOLUTION PROCEDURE
14.5 SOLVING BY LINEAR PROGRAMMING
14.6 EXTENSIONS
14.7 CONCLUSIONS
“Ch. 14—Game Theory” Files for Solving the Examples:
15 Decision Analysis
15.1 A PROTOTYPE EXAMPLE
15.2 DECISION MAKING WITHOUT EXPERIMENTATION
Formulation of the Prototype Example in This Framework
The Maximin Payoff Criterion
The Maximum Likelihood Criterion
Bayes’ Decision Rule
Sensitivity Analysis with Bayes’ Decision Rule
15.3 DECISION MAKING WITH EXPERIMENTATION
Continuing the Prototype Example
Posterior Probabilities
The Value of Experimentation
15.4 DECISION TREES
Constructing the Decision Tree
Performing the Analysis
Helpful Software
15.5 UTILITY THEORY
Utility Functions for Money
Applying Utility Theory to the Goferbroke Co. Problem
Another Approach for Estimating
(
)
Using a Decision Tree to Analyze the Goferbroke Co. Problem with Utilities
15.6 THE PRACTICAL APPLICATION OF DECISION ANALYSIS
15.7 CONCLUSIONS
“Ch. 15—Decision Analysis” Excel File:
Excel Add-Ins:
16 Markov Chains
16.1 STOCHASTIC PROCESSES
An Inventory Example
16.2 MARKOV CHAINS
Formulating the Inventory Example as a Markov Chain
Additional Examples of Markov Chains
16.3 CHAPMAN-KOLMOGOROV EQUATIONS
-Step Transition Matrices for the Inventory Example
Unconditional State Probabilities
16.4 CLASSIFICATION OF STATES OF A MARKOV CHAIN
Recurrent States and Transient States
Periodicity Properties
16.5 LONG-RUN PROPERTIES OF MARKOV CHAINS
Steady-State Probabilities
Expected Average Cost per Unit Time
Expected Average Cost per Unit Time for Complex Cost Functions
16.6 FIRST PASSAGE TIMES
16.7 ABSORBING STATES
16.8 CONTINUOUS TIME MARKOV CHAINS
Formulation
Some Key Random Variables
Steady-State Probabilities
Automatic Routines in OR Courseware:
17 Queueing Theory
17.1 PROTOTYPE EXAMPLE
17.2 BASIC STRUCTURE OF QUEUEING MODELS
The Basic Queueing Process
Input Source (Calling Population)
Queue
Queue Discipline
Service Mechanism
An Elementary Queueing Process
Terminology and Notation
Relationships between
,
, and
17.3 EXAMPLES OF REAL QUEUEING SYSTEMS
17.4 THE ROLE OF THE EXPONENTIAL DISTRIBUTION
17.5 THE BIRTH-AND-DEATH PROCESS
17.6 QUEUEING MODELS BASED ON THE BIRTH-AND-DEATH PROCESS
The
/
Model
The Finite Queue Variation of the
/
Model (Called the
/
Model)
The Finite Calling Population Variation of the
/
Model
A Model with State-Dependent Service Rate and/or Arrival Rate
17.7 QUEUEING MODELS INVOLVING NONEXPONENTIAL DISTRIBUTIONS
The
/
/1 Model
The
/
Model
The
/
Model
Models without a Poisson Input
Other Models
17.8 PRIORITY-DISCIPLINE QUEUEING MODELS
The Models
Results for the Nonpreemptive Priorities Model
A Single-Server Variation of the Nonpreemptive Priorities Model
Results for the Preemptive Priorities Model
The County Hospital Example with Priorities
17.9 QUEUEING NETWORKS
Infinite Queues in Series
Jackson Networks
17.10 CONCLUSIONS
“Ch. 17—Queueing Theory” Excel File:
“Ch. 17—Queueing Theory” LINGO File for Selected Examples
18 The Application of Queueing Theory
18.1 EXAMPLES
Example 1—How Many Repairers?
Example 2—Which Computer?
Example 3—How Many Tool Cribs?
18.2 DECISION MAKING
18.3 FORMULATION OF WAITING-COST FUNCTIONS
The
(
) Form
The
(
) Form
18.4 DECISION MODELS
Model 1—Unknown
Model 2—Unknown
and
Model 3—Unknown
and
18.5 SOME AWARD-WINNING APPLICATIONS OF QUEUEING THEORY
18.6 CONCLUSIONS
“Ch. 18—Application of QT” Excel File:
Supplement to This Chapter:
19 Inventory Theory
19.1 EXAMPLES
19.2 COMPONENTS OF INVENTORY MODELS
19.3 DETERMINISTIC CONTINUOUS-REVIEW MODELS
The Basic EOQ Model
The EOQ Model with Planned Shortages
The EOQ Model with Quantity Discounts
Some Useful Excel Templates
Observations about EOQ Models
A Broader Perspective of the Speaker Example
19.4 A DETERMINISTIC PERIODIC-REVIEW MODEL
An Algorithm
Application of the Algorithm to the Example
19.5 A STOCHASTIC CONTINUOUS-REVIEW MODEL
The Assumptions of the Model
Choosing the Order Quantity
Choosing the Reorder Point
19.6 A STOCHASTIC SINGLE-PERIOD MODEL FOR PERISHABLE PRODUCTS
Some Types of Perishable Products
An Example
The Assumptions of the Model
Analysis of the Model
Application to the Example
The Model with Initial Stock Level
A Single-Period Model with a Setup Cost
19.7 STOCHASTIC PERIODIC-REVIEW MODELS
A Stochastic Two-Period Model with No Setup Cost
Stochastic Multiperiod Models—An Overview
19.8 LARGER INVENTORY SYSTEMS IN PRACTICE
Multiproduct Inventory Systems
Multiechelon Inventory Systems
Multiechelon Inventory Management at IBM
Supply Chain Management
Supply Chain Management at Hewlett-Packard
19.9 CONCLUSIONS
“Ch. 19—Inventory Theory” Excel File:
“Ch. 19—Inventory Theory” LINGO File for Selected Examples
20 Forecasting
20.1 SOME APPLICATIONS OF FORECASTING
Sales Forecasting
Forecasting the Need for Spare Parts
Forecasting Production Yields
Forecasting Economic Trends
Forecasting Staffing Needs
Other
20.2 JUDGMENTAL FORECASTING METHODS
20.3 TIME SERIES
20.4 FORECASTING METHODS FOR A CONSTANT-LEVEL MODEL
Last-Value Forecasting Method
Averaging Forecasting Method
Moving-Average Forecasting Method
Exponential Smoothing Forecasting Method
20.5 INCORPORATING SEASONAL EFFECTS INTO FORECASTING METHODS
The Seasonally Adjusted Time Series
The General Procedure
20.6 AN EXPONENTIAL SMOOTHING METHOD FOR A LINEAR TREND MODEL
Adapting Exponential Smoothing to This Model
Application of the Method to the CCW Example
Forecasting More Than One Time Period Ahead
20.7 FORECASTING ERRORS
20.8 BOX-JENKINS METHOD
20.9 CAUSAL FORECASTING WITH LINEAR REGRESSION
Causal Forecasting
Linear Regression
Method of Least Squares
Confidence Interval Estimation of
(
*)
Predictions
20.10 FORECASTING IN PRACTICE
20.11 CONCLUSIONS
“Ch. 20—Forecasting” Excel File:
“Ch. 20—Forecasting” LINGO File for Selected Examples
21 Markov Decision Processes
21.1 A PROTOTYPE EXAMPLE
21.2 A MODEL FOR MARKOV DECISION PROCESSES
Solving the Prototype Example by Exhaustive Enumeration
21.3 LINEAR PROGRAMMING AND OPTIMAL POLICIES
Randomized Policies
A Linear Programming Formulation
Solving the Prototype Example by Linear Programming
21.4 POLICY IMPROVEMENT ALGORITHM FOR FINDING OPTIMAL POLICIES
Preliminaries
The Policy Improvement Algorithm
Summary of the Policy Improvement Algorithm
Solving the Prototype Example by the Policy Improvement Algorithm
21.5 DISCOUNTED COST CRITERION
A Policy Improvement Algorithm
Linear Programming Formulation
Finite-Period Markov Decision Processes and the Method of Successive Approximations
21.6 CONCLUSIONS
A Demonstration Example in OR Tutor:
Interactive Routines:
Automatic Routines:
“Ch. 21—Markov Decision Proc” Files for Solving the Linear Programming Formulations:
22 Simulation
22.1 ESSENCE OF SIMULATION
The Role of Simulation in Operations Research Studies
Discrete-Event versus Continuous Simulation
More Examples in Your OR Courseware
22.2 SOME COMMON TYPES OF APPLICATIONS OF SIMULATION
Design and Operation of Queueing Systems
Managing Inventory Systems
Estimating the Probability of Completing a Project by the Deadline
Design and Operation of Manufacturing Systems
Design and Operation of Distribution Systems
Financial Risk Analysis
Health Care Applications
Applications to Other Service Industries
New Applications
22.3 GENERATION OF RANDOM NUMBERS
Characteristics of Random Numbers
Congruential Methods for Random Number Generation
22.4 GENERATION OF RANDOM OBSERVATIONS FROM A PROBABILITY DISTRIBUTION
Simple Discrete Distributions
The Inverse Transformation Method
Exponential and Erlang Distributions
Normal and Chi-Square Distributions
The Acceptance-Rejection Method
22.5 OUTLINE OF A MAJOR SIMULATION STUDY
Step 1: Formulate the Problem and Plan the Study
Step 2: Collect the Data and Formulate the Simulation Model
Step 3: Check the Accuracy of the Simulation Model
Step 4: Select the Software and Construct a Computer Program
Step 5: Test the Validity of the Simulation Model
Step 6: Plan the Simulations to Be Performed
Step 7: Conduct the Simulation Runs and Analyze the Results
Step 8: Present Recommendations to Management
22.6 PERFORMING SIMULATIONS ON SPREADSHEETS
Inventory Management—Freddie the Newsboy’s Problem
Improving PERT—Revisiting the Reliable Construction Co. Problem
Financial Risk Analysis—The Think-Big Development Co. Problem
22.7 VARIANCE-REDUCING TECHNIQUES
Stratified Sampling
Method of Complementary Random Numbers
Conclusions
22.8 REGENERATIVE METHOD OF STATISTICAL ANALYSIS
Traditional Methods and Their Shortcomings
The Regenerative Method Approach
Statistical Formulas
Application of the Statistical Formulas to the Example
22.9 CONCLUSIONS
Demonstration Examples in OR Tutor:
Interactive Routines:
“Ch. 22—Simulation” Excel File:
Excel Add-Ins:
APPENDIX 1 DOCUMENTATION FOR THE OR COURSEWARE
INTERACTIVE ROUTINES
OR TUTOR
SPECIAL AUTOMATIC ROUTINES
EXCEL FILES
MPL/CPLEX
EXCEL ADD-INS
MICROSOFT PROJECT
LINGO/LINDO FILES
UPDATES
APPENDIX 2 CONVEXITY
CONVEX OR CONCAVE FUNCTIONS
OF A SINGLE VARIABLE
CONVEX OR CONCAVE FUNCTIONS
OF SEVERAL VARIABLES
CONVEX SETS
APPENDIX 3 CLASSICAL OPTIMIZATION METHODS
UNCONSTRAINED OPTIMIZATION OF A
FUNCTION OF A SINGLE VARIABLE
CONSTRAINED OPTIMIZATION WITH EQUALITY CONSTRAINTS
UNCONSTRAINED OPTIMIZATION OF A
FUNCTION OF SEVERAL VARIABLES
THE DERIVATIVE OF A DEFINITE INTEGRAL
APPENDIX 4 MATRICES AND MATRIX OPERATIONS
MATRIX OPERATIONS
SPECIAL KINDS OF MATRICES
VECTORS
SOME PROPERTIES OF MATRICES
APPENDIX 5 TABLES
PARTIAL ANSWERS TO SELECTED PROBLEMS
CHAPTER 3
CHAPTER 4
CHAPTER 5
CHAPTER 6
CHAPTER 7
CHAPTER 8
CHAPTER 9
CHAPTER 10
CHAPTER 11
CHAPTER 12
CHAPTER 13
CHAPTER 14
CHAPTER 15
CHAPTER 16
CHAPTER 17
CHAPTER 18
CHAPTER 19
CHAPTER 20
CHAPTER 21
CHAPTER 22
AUTHOR INDEX
SUBJECT INDEX
空白页面
ADVANCE PRAISE FOR
INTRODUCTION TO
OPERATIONS RESEARCH,
SEVENTH EDITION
Reviewers seem to agree that this is clearly the best edition yet. Here is a sampling of
comments:
“The new edition seems to contain the most current information available.”
“The new edition of Hillier/Lieberman is very well done and greatly enhances this clas-
sic text.”
“The authors have done an admirable job of rewriting and reorganizing to reflect mod-
ern management practices and the latest software developments.”
“It is a complete package.”
“Hillier/Lieberman has recaptured any advantage it may have lost (to other competitors)
in the past.”
“The changes in this new edition make Hillier/Lieberman the preeminent book for oper-
ations research and I would highly recommend it.”
INTRODUCTION TO
OPERATIONS RESEARCH
McGraw-Hill Series in Industrial Engineering and Management Science
CONSULTING EDITORS
Kenneth E. Case, Department of Industrial Engineering and Management, Oklahoma State University
Philip M. Wolfe, Department of Industrial and Management Systems Engineering, Arizona State University
Barnes
Statistical Analysis for Engineers and Scientists: A Computer-Based Approach
Bedworth, Henderson, and Wolfe
Computer-Integrated Design and Manufacturing
Blank and Tarquin
Engineering Economy
Ebeling
Reliability and Maintainability Engineering
Grant and Leavenworth
Statistical Quality Control
Harrell, Ghosh, and Bowden
Simulation Using PROMODEL
Hillier and Lieberman
Introduction to Operations Research
Gryna
Quality Planning and Analysis: From Product Development through Use
Kelton, Sadowski, and Sadowski
Simulation with ARENA
Khalil
Management of Technology
Kolarik
Creating Quality: Concepts, Systems, Strategies, and Tools
Creating Quality: Process Design for Results
Law and Kelton
Simulation Modeling and Analysis
Nash and Sofer
Linear and Nonlinear Programming
Nelson
Stochastic Modeling: Analysis and Simulation
Niebel and Freivalds
Methods, Standards, and Work Design
Pegden
Introduction to Simulation Using SIMAN
Riggs, Bedworth, and Randhawa
Engineering Economics
Sipper and Bulfin
Production: Planning, Control, and Integration
Steiner
Engineering Economics Principles
INTRODUCTION TO
OPERATIONS RESEARCH
Seventh Edition
FREDERICK S. HILLIER,
Stanford University
GERALD J. LIEBERMAN,
Late of Stanford University
Cases developed by Karl Schmedders and Molly Stephens
Tutorial software developed by Mark Hillier and Michael O’Sullivan
Boston Burr Ridge, IL Dubuque, IA Madison, WI New York
San Francisco St. Louis Bangkok Bogotá Caracas Lisbon London
Madrid Mexico City Milan New Delhi Seoul Singapore Sydney
Taipei Toronto
McGraw-Hill Higher Education
A Division of The McGraw-Hill Companies
INTRODUCTION TO OPERATIONS RESEARCH
Published by McGraw-Hill, an imprint of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas,
New York, NY, 10020. Copyright © 2001, 1995, 1990, 1986, 1980, 1974, 1967, by The McGraw-Hill Com-
panies, Inc. All rights reserved. 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 DOC/DOC 0 9 8 7 6 5 4 3 2 1 0
ISBN
0072321695
Vice president/Editor-in-chief: Kevin Kane
Publisher: Thomas Casson
Executive editor: Eric M. Munson
Developmental editor: Maja Lorkovic
Marketing manager: John Wannemacher
Project manager: Christine A. Vaughan
Manager, new book production: Melonie Salvati
Coordinator, freelance design: Gino Cieslik
Supplement coordinator: Cathy Tepper
Media technology producer: Judi David
Cover design: Gino Cieslik
Cover Illustration: Paul Turnbaugh
Compositor: York Graphic Services, Inc.
Typeface: 10/12 Times
Printer: R. R. Donnelley & Sons Company
Library of Congress Cataloging-in-Publication Data
Hillier, Frederick S.
Introduction to operations research/Frederick S. Hillier, Gerald J. Lieberman; cases
developed by Karl Schmedders and Molly Stephens; tutorial software developed by
Mark Hillier and Michael O’Sullivan.—7th ed.
p. cm.
ISBN 0-07-232169-5
1. Operations research. I. Lieberman, Gerald J. II. Title.
T57.6. H53 2001
658.4⬘034—dc21
www.mhhe.com
00-025683
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 mu-
sic. As an undergraduate at Stanford University he ranked first in his engineering class of
over 300 students. He also won the McKinsey Prize for technical writing, won the Out-
standing Sophomore Debater award, played in the Stanford Woodwind Quintet, and won
the Hamilton Award for combining excellence in engineering with notable 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 re-
search. After receiving his Ph.D. degree, he joined the faculty of Stanford University, and
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 so now is Professor Emeritus of Operations 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 pub-
lished widely, and his seminal papers have been selected for republication in books of se-
lected readings at least ten times. He was the first-prize winner of a research contest on “Cap-
ital 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 received the hon-
orable 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 Institute of Opera-
tions Research and the Management Sciences (INFORMS) for the 6th 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 Amer-
ica (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 Commit-
tee, and Chair of the John von Neumann Theory Prize Selection Committee for INFORMS.
vii
viii
ABOUT THE AUTHORS
He currently is serving as the Series Editor for the International Series in Operations Re-
search and Management Science being published by Kluwer Academic Publishers.
In addition to Introduction to Operations Research and the two companion volumes,
Introduction to Mathematical Programming and Introduction to Stochastic Models in Op-
erations Research, 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, and M. I. Reiman), and Introduc-
tion to Management Science: A Modeling and Case Studies Approach with Spreadsheets
(Irwin/McGraw-Hill, co-authored by M. S. Hillier and G. J. Lieberman).
The late Gerald J. Lieberman sadly passed away shortly before the completion of this edi-
tion. He had been Professor Emeritus of Operations Research and Statistics at Stanford Uni-
versity, where he was the founding chair of the Department of Operations Research. He was
both an engineer (having received an undergraduate degree in mechanical engineering from
Cooper Union) and an operations research statistician (with an A.M. from Columbia Uni-
versity in mathematical statistics, and a Ph.D. 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 Acad-
emy of Engineering, receiving the Shewhart Medal of the American Society for Quality Con-
trol, receiving the Cuthbertson Award for exceptional service to Stanford University, and serv-
ing 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 edi-
tion 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 the two companion volumes,
Introduction to Mathematical Programming and Introduction to Stochastic Models in Op-
erations Research, his books are Handbook of Industrial Statistics (Prentice-Hall, 1955,
co-authored by A. H. Bowker), Tables of the Non-Central t-Distribution (Stanford Uni-
versity Press, 1957, co-authored by G. J. Resnikoff), Tables of the Hypergeometric Prob-
ability Distribution (Stanford University Press, 1961, co-authored by D. Owen), Engi-
neering 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 (Irwin/McGraw-Hill, 2000, co-authored by F. S. Hillier and M. S. Hillier).
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
