Operations research : theory and applications

Front Cover
Contents
Preface to the Sixth Edition
Preface to the First Edition
Chapter 1 Operations Research: An Introduction
1.1 Operations Research – A Quantitative Approach to Decision-Making
1.2 The History of Operations Research
1.3 Definitions of Operations Research
1.4 Features of Operations Research Approach
1.5 Operations Research Approach to Problem Solving
Conceptual Questions A
1.6 Models and Modelling in Operations Research
Classification Based on Structure
Classification Based on Function (or Purpose)
Classification Based on Time Reference
Classification Based on Degree of Certainty
Classification Based on Method of Solution or Quantification
1.7 Advantages of Model Building
1.8 Methods for Solving Operations Research Models
1.9 Methodology of Operations Research
1.10 Advantages of Operations Research Study
1.11 Opportunities and Shortcomings of the Operations Research Approach
1.12 Features of Operations Research Solution
1.13 Applications of Operations Research
1.14 Operations Research Models in Practice
1.15 Computer Software for Operations Research
Conceptual Questions B
Chapter Summary
Chapter Concepts Quiz
Case Study
Puzzles in Operations Research
Chapter 2 Linear Programming: Applications and Model Formulation
2.1 Introduction
2.2 Structure of Linear Programming Model
General Structure of an LP Model
Assumptions of an LP Model
2.3 Advantages of Using Linear Programming
2.4 Limitations of Linear Programming
2.5 Application Areas of Linear Programming
2.6 General Mathematical Model of Linear Programming Problem
2.7 Guidelines on Linear Programming Model Formulation
2.8 Examples of LP Model Formulation
Examples on Production
Examples on Marketing
Examples on Finance
Examples on Agriculture
Example on Transportation
Examples on Personnel
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 3 Linear Programming: The Graphical Method
3.1 Introduction
3.2 Important Definitions
3.3 Graphical Solution Methods of LP Problems
Extreme Point Solution Method
Examples on Maximization LP Problem
Examples on Minimization LP Problem
Examples on Mixed Constraints LP Problem
Iso-Profit (Cost) Function Line Method
Comparison of Two Graphical Solution Methods
3.4 Special Cases in Linear programming
Alternative (or Multiple) Optimal Solutions
Unbounded Solution
Infeasible Solution
Redundancy
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 4 Linear Programming: The Simplex Method
4.1 Introduction
4.2 Standard form of an LP Problem
4.3 Simplex Algorithm (Maximization Case)
4.4 Simplex Algorithm (Minimization Case)
Two-Phase Method
Big-M Method
Self Practice Problems A
Hints and Answers
4.5 Some Complications and Their Resolution
Unrestricted Variables
Tie for Entering Basic Variable (Key Column)
Tie for Leaving Basic Variable (Key Row) – Degeneracy
4.6 Types of Linear Programming Solutions
Alternative (Multiple) Optimal Solutions
Unbounded Solution
Infeasible Solution
Conceptual Questions
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 5 Duality in Linear Programming
5.1 Introduction
5.2 Formulation of Dual Linear Programming Problem
Symmetrical Form
Economic Interpretation of Dual Variables
Economic Interpretation of Dual Constraints
Rules for Constructing the Dual from Primal
Self Practice Problems A
Hints and Answers
5.3 Standard Results on Duality
Principle of Complementary Slackness
5.4 Managerial Significance of Duality
5.5 Advantages of Duality
Conceptual Questions
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Appendix: Theorems of Duality
Chapter 6 Sensitivity Analysis in Linear Programming
6.1 Introduction
6.2 Sensitivity Analysis
Change in Objective Function Coefficient
Change in the Availability of Resources (bi )
Change in the Input-Out Coefficients (aij\'s)
Addition of a New Variable (Column)
Addition of a New Constraint (Row)
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 7 Integer Linear Programming
7.1 Introduction
7.2 Types of Integer Programming Problems
7.3 Enumeration and Cutting Plane Solution Concept
7.4 Gomory’s All Integer Cutting Plane Method
Method for Constructing Additional Constraint (Cut)
Steps of Gomory’s All Integer Programming Algorithm
Self Practice Problems A
Hints and Answers
7.5 Gomory’s Mixed-Integer Cutting Plane Method
Method for Constructing Additional Constraint (Cut)
Steps of Gomory’s Mixed-Integer Programming Algorithm
7.6 Branch and Bound Method
7.7 Applications of Zero-One Integer Programming
Capital Budgeting Problem
Fixed Cost (or Charge) Problem
Plant Location Problem
Conceptual Questions
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 8 Goal Programming
8.1 Introduction
8.2 Difference Between LP and GP Approach
8.3 Concept of Goal Programming
Distinction among Objectives, Goals and Constraints
8.4 Goal Programming Model Formulation
Single Goal with Multiple Subgoals
Equally Ranked Multiple Goals
Ranking and Weighting of Unequal Multiple Goals
General GP Model
Steps to Formulate GP Model
8.5 Graphical Solution Method for Goal Programming
8.6 Modified Simplex Method of Goal Programming
8.7 Alternative Simplex Method for Goal Programming
Conceptual Questions
Self Practice Problems
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 9 Transportation Problem
9.1 Introduction
9.2 Mathematical Model of Transportation Problem
General Mathematical Model of Transportation Problem
9.3 The Transportation Algorithm
9.4 Methods for Finding Initial Solution
North-West Corner Method (NWCM)
Least Cost Method (LCM)
Conceptual Questions A
Self Practice Problems A
Hints and Answers
9.5 Test for Optimality
Dual of Transportation Model
Economic Interpretation of ui’s and vj’s
Steps of MODI Method (Transportation Algorithm)
Close-Loop in Transportation Table and its Properties
Conceptual Questions B
Self Practice Problems B
Hints and Answers
9.6 Variations in Transportation Problem
Unbalanced Supply and Demand
Degeneracy and its Resolution
Alternative Optimal Solutions
Prohibited Transportation Routes
9.7 Maximization Transportation Problem
9.8 Trans-Shipment Problem
Conceptual Questions C
Self Practice Problems C
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Appendix: Theorems and Results
Chapter 10 Assignment Problem
10.1 Introduction
10.2 Mathematical Models of Assignment Problem
10.3 Solution Methods of Assignment Problem
Hungarian Method for Solving Assignment Problem
Conceptual Questions A
Self Practice Problems A
Hints and Answers
10.4 Variations of the Assignment Problem
Multiple Optimal Solutions
Maximization Case in Assignment Problem
Unbalanced Assignment Problem
Restrictions on Assignments
Conceptual Questions B
Self Practice Problems B
Hints and Answers
10.5 A Typical Assignment Problem
10.6 Travelling Salesman Problem
Self Practice Problems C
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Appendix: Important Results and Theorems
Chapter 11 Decision Theory and Decision Trees
11.1 Introduction
11.2 Steps of Decision-Making Process
11.3 Types of Decision-Making Environments
11.4 Decision-Making Under Uncertainty
Optimism (Maximax or Minimin) Criterion
Pessimism (Maximin or Minimax) Criterion
Equal Probabilities (Laplace) Criterion
Coefficient of Optimism (Hurwicz) Criterion
Regret (Savage) Criterion
Conceptual Questions A
Self Practice Problems A
Hints and Answers
11.5 Decision-Making Under Risk
Expected Monetary Value (EMV)
Expected Opportunity Loss (EOL)
Expected Value of Perfect Information (EVPI)
11.6 Posterior Probabilities and Bayesian Analysis
Conceptual Questions B
Self Practice Problems B
Hints and Answers
11.7 Decision Trees Analysis
11.8 Decision-Making with Utilities
Utility Functions
Utility Curve
Construction of Utility Curves
Self Practice Problems C
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 12 Theory of Games
12.1 Introduction
12.2 Two-Person Zero-Sum Games
12.3 Pure Strategies (Minimax and Maximin Principles): Games with Saddle Point
Rules to Determine Saddle Point
Conceptual Questions A
Self Practice Problems A
Hints and Answers
12.4 Mixed Strategies: Games without Saddle Point
12.5 The Rules (Principles) of Dominance
12.6 Solution Methods Games without Saddle Point
Algebraic Method
Arithmetic Method
Matrix Method
Graphical Method
Linear Programming Method
Conceptual Questions B
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 13 Project Management: PERT and CPM
13.1 Introduction
13.2 Basic Differences Between PERT and CPM
Significance of Using PERT/CPM
13.3 Phases of Project Management
13.4 PERT/CPM Network Components and Precedence Relationships
Rules for AOA Network Construction
Errors and Dummies in Network
Conceptual Questions A
Self Practice Problems A
13.5 Critical Path Analysis
Forward Pass Method (For Earliest Event Time)
Backward Pass Method (For Latest Allowable Event Time)
Float (Slack) of an Activity and Event
Critical Path
Conceptual Questions B
Self Practice Problems B
Hints and Answers
Project Scheduling with Uncertain Activity Times
Estimation of Project Completion Time
Conceptual Questions C
Self Practice Problems C
Hints and Answers
13.7 Project Time-Cost Trade-Off
Project Crashing
Time-Cost Trade-Off Procedure
Self Practice Problems D
Hints and Answers
13.8 Updating of the Project Progress
13.9 Resource Allocation
Resource Levelling
Resource Smoothing
Self Practice Problems E
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 14 Deterministic Inventory Control Models
14.1 Introduction
14.2 The Meaning of Inventory Control
14.3 Functional Role of Inventory
14.4 Reasons for Carrying Inventory
14.5 Factors Involved in Inventory Problem Analysis
Inventory Cost Components
Demand for Inventory Items
Replenishment Lead Time
Planning Period
14.6 Inventory Model Building
Steps of Inventory Model Building
Replenishment Order Size Decisions and Concept of EOQ
Classification of EOQ Models
14.7 Single Item Inventory Control Models without Shortages
Conceptual Questions A
Self Practice Problems A
Hints and Answers
14.8 Single Item Inventory Control Models with Shortages
Conceptual Questions B
Self Practice Problems B
Hints and Answers
14.9 Multi-Item Inventory Models with Constraints
Self Practice Problems C
14.10 Single Item Inventory Control Models with Quantity Discounts
Self Practice Problems D
Hints and Answers
14.11 Inventory Control Models with Uncertain Demand
Reorder Level with Constant Demand
14.12 Information Systems for Inventory Control
The Q-System with Uncertain Demand
The Q-system with Uncertain Demand and Lead Time
Application of Q-System: Two-Bin System
The P-System with Uncertain Demand
Comparison Between Q-system and P-System
Conceptual Questions C
Self Practice Problems E
Hints and Answers
14.13 Selective Inventory Control Techniques
Conceptual Questions D
Self Practice Problems F
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 15 Probabilistic Inventory Control Models
15.1 Introduction
15.2 Instantaneous Demand Inventory Control Models without Set-Up Cost
Conceptual Questions A
Self Practice Problems A
Hints and Answers
15.3 Continuous Demand Inventory Control Models without Set-Up Cost
15.4 Instantaneous Demand Inventory Control Model with Set-Up Cost
Conceptual Questions B
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter 16 Queuing Theory
16.1 Introduction
16.2 The Structure of a Queuing System
Calling Population Characteristics
Queuing Process
Queue Discipline
Service Process (or Mechanism)
16.3 Performance Measures of a Queuing System
Transient-State and Steady-State
Relationships among Performance Measures
16.4 Probability Distributions in Queuing Systems
Distribution of Arrivals (Pure Birth Process)
Distribution of Interarrival Times
Distribution of Departures (Pure Death Process)
Distribution of Service Times
Conceptual Questions A
16.5 Classification of Queuing Models
Solution of Queuing Models
16.6 Single-Server Queuing Models
Conceptual Questions B
Self Practice Problems A
Hints and Answers
16.7 Multi-Server Queuing Models
Conceptual Questions C
Self Practice Problems B
Hints and Answers
16.8 Finite Calling Population Queuing Models
Self Practice Problems C
16.9 Multi-Phase Service Queuing Model
Self Practice Problems D
Hints and Answers
16.10 Special Purpose Queuing Models
Chapter Summary
Chapter Concepts Quiz
Case Study
Appendix 16.A: Probability Distribution of Arrivals and Departures
Appendix 16.B: Erlangian Service Time Distribution with K-Phases
Chapter 17 Replacement and Maintenance Models
17.1 Introduction
17.2 Types of Failure
Gradual Failure
Sudden Failure
17.3 Replacement of Items whose Efficiency Deteriorates with Time
Conceptual Questions A
Self Practice Problems A
Hints and Answers
17.4 Replacement of Items that Completely Fail
Individual Replacement Policy
Group Replacement Policy
Conceptual Questions B
Self Practice Problems B
Hints and Answers
17.5 Other Replacement Problems
Staffing Problem
Equipment Renewal Problem
Self Practice Problems C
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 18 Markov Chains
18.1 Introduction
18.2 Characteristics of a Markov Chain
18.3 Applications of Markov Analysis
18.4 State and Transition Probabilities
18.5 Multi-Period Transition Probabilities
Procedure to Formulate Matrix of Transition Probabilities
18.6 Steady-State (Equilibrium) Conditions
Procedure for Determining Steady-State Condition
18.7 Absorbing States and Accounts Receivable Application
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Case Study
Chapter 19 Simulation
19.1 Introduction
19.2 Simulation Defined
19.3 Types of Simulation
19.4 Steps of Simulation Process
19.5 Advantages and Disadvantages of Simulation
19.6 Stochastic Simulation and Random Numbers
Monte Carlo Simulation
Random Number Generation
19.7 Simulation of Inventory Problems
19.8 Simulation of Queuing Problems
19.9 Simulation of Investment Problems
19.10 Simulation of Maintenance Problems
19.11 Simulation of PERT Problems
Conceptual Questions
Self Practice Problems
Chapter Summary
Chapter Concepts Quiz
Case Study
Appendix: The Seven Most Frequent Causes of Simulation Analysis Failure and How to Avoid Them
Chapter 20 Sequencing Problems
20.1 Introduction
20.2 Notations, Terminology and Assumptions
20.3 Processing n Jobs Through Two Machines
Johnson Procedure
Conceptual Questions A
Self Practice Problems A
Hints and Answers
20.4 Processing n Jobs Through Three Machines
The Procedure
Self Practice Problems B
Hints and Answers
20.5 Processing n Jobs Through m Machines
20.6 Processing Two Jobs Through m Machines
Conceptual Questions B
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 21 Information Theory
21.1 Introduction
21.2 Communication Processes
Memoryless Channel
The Channel Matrix
Probability Relation in a Channel
Noiseless Channel
21.3 A Measure of Information
Properties of Entropy Function, H
21.4 Measures of Other Information Quantities
Marginal and Joint Entropies
Conditional Entropies
Expected Mutual Information
Axiom of an Entropy Function
Basic Requirements of Logarithmic Entropy Functions
21.5 Channel Capacity, Efficiency and Redundancy
21.6 Encoding
Objectives of Encoding
21.7 Shannon-Fano Encoding Procedure
21.8 Necessary and Sufficient Condition for Noiseless Encoding
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 22 Dynamic Programming
22.1 Introduction
22.2 Dynamic Programming Terminology
22.3 Developing Optimal Decision Policy
22.4 Dynamic Programming under Certainty
22.5 Dynamic Programming Approach for Solving Linear Programming Problem
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 23 Classical Optimization Methods
23.1 Introduction
23.2 Unconstrained Optimization
Optimizing Single-Variable Functions
Conditions for Local Minimum and Maximum Value
Optimizing Multivariable Functions
Self Practice Problems A
Hints and Answers
23.3 Constrained Multivariable Optimization with Equality Constraints
Direct Substitution Method
Lagrange Multipliers Methods
Self Practice Problems B
Hints and Answers
23.4 Constrained Multivariable Optimization with Inequality Constraints
Kuhn-Tucker Necessary Conditions
Kuhn-Tucker Sufficient Conditions
Conceptual Questions
Self Practice Problems C
Hints and Answers
Chapter Summary
Chapter Concepts Quiz
Chapter 24 Non-Linear Programming Methods
24.1 Introduction
24.2 The General Non-Linear Programming Problem
24.3 Graphical Solution Method
Self Practice Problems A
Hints and Answers
24.4 Quadratic Programming
Kuhn-Tucker Conditions
Wolfe’s Modified Simplex Method
Beale’s Method
24.5 Applications of Quadratic Programming
Conceptual Questions A
Self Practice Problems B
Hints and Answers
24.6 Separable Programming
Separable Functions
Definitions
Piece-Wise Linear Approximation of Non-linear Functions
Mixed-Integer Approximation of Separable NLP Problem
Conceptual Questions B
Self Practice Problems C
Hints and Answers
24.7 Geometric Programming
General Mathematical Form of GP
Primal GP Problem with Equality Constraints
24.8 Stochastic Programming
Sequential Stochastic Programming
Non-Sequential Stochastic Programming
Chance-Constrained Programming
Self Practice Problems D
Hints and Answers
Case Study
Chapter Summary
Chapter 25 Theory of Simplex Method
25.1 Introduction
25.2 Canonical and Standard Form of LP Problem
25.3 Slack and Surplus Variables
Basic Solution
Degenerate Solution
Cost (or Price) Vector
Conceptual Questions A
Self Practice Problems A
Hints and Answers
25.4 Reduction of Feasible Solution to a Basic Feasible Solution
25.5 Improving a Basic Feasible Solution
25.6 Alternative Optimal Solutions
25.7 Unbounded Solution
25.8 Optimality Condition
25.9 Some Complications and their Resolution
Unrestricted Variables
Degeneracy and its Resolution
Conceptual Questions B
Self Practice Problems B
Hints and Answers
Chapter Summary
Chapter 26 Revised Simplex Method
26.1 Introduction
26.2 Standard Forms for Revised Simplex Method
Revised Simplex Method in Standard Form I
26.3 Computational Procedure for Standard Form I
Steps of the Procedure
26.4 Comparison of Simplex Method and Revised Simplex Method
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter 27 Dual-Simplex Method
27.1 Introduction
27.2 Dual-Simplex Algorithm
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Appendix: Theory of Dual-Simplex Method
Chapter 28 Bounded Variables LP Problem
28.1 Introduction
28.2 The Simplex Algorithm
Self Practice Problems
Hints and Answers
Chapter Summary
Chapter 29 Parametric Linear Programming
29.1 Introduction
29.2 Variation in the Objective Function Coefficients
29.3 Variation in the Availability of Resources (RHS Values)
Conceptual Questions
Self Practice Problems
Hints and Answers
Chapter Summary
Appendix A: Pre-Study for Operations Research
A.1 Linear Combination of Vectors
A.2 Linear Dependence and Independence
A.3 Simultaneous Linear Equations and Nature of Solution
A.4 Convex Analysis
A.5 Supporting and Separating Hyperplanes
A.6 Convex Functions
A.7 Quadratic Forms
Self Practice Problems
Appendix B: Selected Tables
Table B.1 Values of ex and e–x
Table B.2 Poisson Distribution
Table B.3 Normal Distribution
Table B.4 Random Numbers
Table B.5 Present Values
Table B.6 Cumulative Poisson Probabilities
Selected References
Index