Operations Research, 2/e

Cover Contents Preface About the Authors 1. Basics of Operations Research 1.1 Development of Operations Research 1.2 Definition of Operations Research 1.3 Necessity of Operations Research in Industry 1.4 Scope/Applications of Operations Research 1.5 Operations Research and Decision-Making 1.6 Operations Research in Modern Management 1.7 Phases of Operations Research 1.8 Models in Operations Research 1.8.1 Classification of Models 1.8.2 Characteristics of a Good Model 1.8.3 Principles of Modelling 1.8.4 General Methods for Solving Operations Research Models 1.9 Role of Operations Research in Engineering 1.10 Limitations of Operations Research Exercises 2. Linear Programming Problem (LPP) 2.1 Introduction 2.2 Mathematical Formulation of Linear Programming Problem 2.3 Statements of Basic Theorems and Properties 2.3.1 General Formulation of Linear Programming Problems 2.3.2 Standard Form of Linear Programming Problem 2.3.3 Matrix Form of Linear Programming Problem 2.3.4 Definitions 2.3.5 Basic Assumptions 2.3.6 Fundamental Theorem of Linear Programming 2.3.7 Fundamental Properties of Solutions 2.4 Graphical Solutions to a Linear Programming Problem 2.4.1 Some Exceptional Cases 2.5 Simplex Method 2.6 Artifical Variable Techniques 2.6.1 The Big M Method 2.6.2 The Two-phase Simplex Method 2.7 Variants of Simplex Method 2.8 Solution of Simultaneous Equations by Simplex Method 2.9 Inverse of a Matrix by Simplex Method Exercises 3. Advanced Topics in Linear Programming 3.1 Duality Theory 3.1.1 The Dual Problem 3.1.2 Duality Theorems 3.1.3 Duality and Simplex Method 3.2 Dual Simplex Method 3.2.1 Introduction 3.2.2 Difference between Regular Simplex Method and Dual Simplex Method 3.2.3 Dual Simplex Algorithm 3.3 Revised Simplex Method 3.3.1 Introduction 3.3.2 Revised Simplex Algorithm 3.3.3 Advantages of the Revised Simplex Method Over the Regular Simplex Method 3.4 Sensitivity Analysis 3.4.1 Introduction 3.4.2 Changes Affecting Optimality 3.5 Parametric Programming 3.5.1 Introduction 3.5.2 Parametric Cost Problem 3.5.3 Parametric Right Hand Side Problem 3.6 Goal Programming 3.6.1 Introduction 3.6.2 Concepts of Goal Programming 3.6.3 Formulation of Goal Programming Problem 3.6.4 Graphical Method of Goal Programming 3.7 Integer Programming 3.7.1 Introduction 3.7.2 Formulation of Integer Programming Problem 3.7.3 Gomory’s all IPP Method (or) Cutting Plane Method or Gomory’s Fractional Cut Method 3.7.4 Branch and Bound Technique 3.8 Zero-One Programming 3.8.1 Introduction 3.8.2 Examples of Zero-one Programming Problems 3.8.3 Importance of Zero-one Integer Programming 3.8.4 Solution Methodologies 3.9 Limitations of Linear Programming Problem 3.9.1 Advantages of Linear Programming Problem 3.9.2 Limitations of Linear Programming Exercises 4. The Transportation Problem 4.1 Introduction 4.2 Mathematical Formulation 4.2.1 Definitions 4.2.2 Theorem (Existence of Feasible Solution) 4.2.3 Theorem (Basic Feasible Solution) 4.2.4 Definition: Triangular Basis 4.2.5 Theorem 4.3 Methods for Finding Initial Basic Feasible Solution 4.3.1 First Method—North-West Corner Rule 4.3.2 Second Method—Least Cost or Matrix Minima Method 4.3.3 Third Method—Vogel’s Approximation Method (VAM) or Unit Cost Penalty Method 4.3.4 Fourth Method—Row Minima Method 4.3.5 Fifth Method—Column Minima Method 4.4 Optimum Solution of a Transportation Problem 4.4.1 The Stepping-stone Method 4.4.2 MODI Method or the u -v Method 4.5 Degeneracy in Transportation Problem 4.5.1 Resolution of Degeneracy in the Initial Stage 4.5.2 Resolution of Degeneracy during Solution Stages 4.6 Unbalanced Transporation Problems 4.7 Maximisation in Transportation Problems 4.8 The Trans-Shipment Problem 4.9 Sensitivity Analysis in Transportation Problem 4.10 Applications Exercises 5. Assignment Problem 5.1 Introduction and Formulation 5.2 Hungarian Assignment Algorithm 5.2.1 Theorem 5.2.2 Theorem 5.2.3 Hungarian Assignment Algorithm 5.3 Variations of the Assignment Problem 5.4 Travelling Salesman Problem 5.4.1 Formulation of a Travelling-Salesman Problem as Assignment Problem Exercises 6. Dynamic Programming 6.1 Introduction 6.1.1 Need for Dynamic Programming Problem 6.1.2 Application of Dynamic Programming Problem 6.1.3 Characteristics of Dynamic Programming 6.1.4 Definition 6.1.5 Dynamic Programming Algorithm 6.2 Some Dynamic Programming Techniques 6.2.1 Single Additive Constraint, Multiplicatively Separable Return 6.2.2 Single Additive Constraint, Additively Separable Return 6.2.3 Single Multiplicative Constraint, Additively Separable Return 6.2.4 Systems Involving More than One Constraint 6.2.5 Problems 6.3 Capital Budgeting Problem 6.4 Reliability Problem 6.5 Stage Coach Problem (Shortest-Route Problem) 6.6 Solution of Linear Programming Problem by Dynamic Programming Exercises 7. Decision Theory and Introduction to Quantitative Methods 7.1 Introduction to Decision Analysis 7.1.1 Steps in Decision Theory Approach 7.1.2 Decision-making Environments 7.2 Decision Under Uncertainty 7.2.1 Criterion of Pessimism (Minimax or Maximin) 7.2.2 Criterion of Optimism (Maximax or Minimin) 7.2.3 Laplace Criterion or Equally Likely Decision Criterion 7.2.4 Criterion of Realism (Hurwicz Criterion) 7.2.5 Criterion of Regret (Savage Criterion) or Minimax Regret Criterion 7.3 Decision Under Certainty 7.4 Decision-Making Under Risk 7.4.1 Expected Monetary Value (EMV) Criterion 7.4.2 Expected Opportunity Loss (EOL) Criterion 7.4.3 Expected Value of Perfect Information (EVPI) 7.5 Decision Trees 7.6 Introduction to Quantitative Methods 7.6.1 Definition and Classification 7.6.2 Role of Quantitative Methods in Business and Industry 7.6.3 Quantitative Techniques and Business Management 7.6.4 Limitations of Quantitative Techniques Exercises 8. Theory of Games 8.1 Introduction to Games 8.1.1 Some Basic Terminologies 8.2 Two-Person Zero-Sum Game 8.2.1 Games with Saddle Point 8.2.2 Games without Saddle Point: Mixed Strategies 8.2.3 Matrix Method 8.3 Graphical Method (for 2 × n or for m × 2 Games) 8.4 Solution of m × n Size Games 8.5 n-Person Zero-Sum Game Exercises 9. Sequencing Models 9.1 Introduction and Basic Assumption 9.1.1 Definition 9.1.2 Terminology and Notations 9.1.3 Assumptions 9.1.4 Solution of Sequencing Problems 9.2 Flow Shop Scheduling 9.2.1 Characteristics of Flow Shop Scheduling Problem 9.2.2 Processing n Jobs Through Two Machines 9.2.3 Processing n Jobs Through 3 Machines 9.2.4 Processing n Jobs Through m Machines 9.3 Job Shop Scheduling 9.3.1 Difference between Flow Shop Scheduling and Job Shop Scheduling 9.3.2 Processing Two Jobs on n Machines 9.4 Gantt Chart 9.5 Shortest Cyclic Route Models (Travelling Salesmen Problem) 9.6 Shortest Acyclic Route Models (Minimal Path Problem) Exercises 10. Replacement Models 10.1 Introduction 10.2 Replacement of Items that Deteriorates Gradually 10.2.1 Replacement Policy When Value of Money Does Not Change with Time 10.2.2 Replacement Policy When Value of Money Changes with Time 10.3 Replacement of Items that Fail Completely and Suddenly 10.3.1 Theorem (Mortality) 10.3.2 Theorem (Group Replacement Policy) 10.4 Other Replacement Problems 10.4.1 Recruitment and Promotion Problems Exercises 11. Inventory Models 11.1 Introduction 11.2 Cost Involved in Inventory Problems 11.3 EOQ Models 11.3.1 Economic Order Quantity (EOQ) 11.3.2 Determination of EOQ by Tabular Method 11.3.3 Determination of EOQ by Graphical Method 11.3.4 Model I: Purchasing Model with No Shortages 11.3.5 Model II: Manufacturing Model with No Shortages 11.3.6 Model III: Purchasing Model with Shortages 11.3.7 Model IV: Manufacturing Model with Shortages 11.4 EOQ Problems with Price Breaks 11.5 Reorder Level and Optimum Buffer Stock 11.6 Probabilistic Inventory Models 11.6.1 Model V: Instantaneous Demand, No Setup Cost, Stock in Discrete Units 11.6.2 Model VI: Instantaneous Demand and Continuous Units 11.6.3 Model VII: Uniform Demand, No Setup cost 11.6.4 Model VIII: Uniform Demand and Continuous Units 11.7 Selection Inventory Control Techniques Exercises 12. Queuing Models 12.1 Characteristics of Queuing Models 12.2 Transient and Steady States 12.3 Role of Exponential Distribution 12.4 Kendall's Notation for Representing Queuing Models 12.5 Classification of Queuing Models 12.6 Pure Birth and Death Models 12.6.1 Pure Birth Model 12.6.2 Pure Death Model 12.7 Model I: (M|M|1): (∞|FIFO) (Birth and Death Model) 12.7.1 Measures of Model I 12.7.2 Little's Formula 12.8 Model II: Multi-Service Model (M|M|s): (∞|FIFO) 12.8.1 Measures of Model II 12.9 Model III: (M/M/1): (N/FIFO) 12.10 Model IV: (M/M/s): (N/FIFO) 12.11 Non-Poisson Queues 12.12 Queuing Control Exercises 13. Network Models 13.1 Introduction 13.1.1 Phases of Project Management 13.1.2 Differences Between PERT and CPM 13.2 Network Construction 13.2.1 Some Basic Definitions 13.2.2 Rules of Network Construction 13.2.3 Fulkerson's Rule (i–j rule) of Numbering Events 13.3 Critical Path Method (CPM) 13.3.1 Forward Pass Computation (for Earliest Event Time) 13.3.2 Backward Pass Computation (for Latest Allowable Time) 13.3.3 Computation of Float and Slack Time 13.3.4 Critical Path 13.4 Project Evaluation and Review Technique (PERT) 13.4.1 PERT Procedure 13.5 Resource Analysis in Network Scheduling 13.5.1 Time Cost Optimisation Algorithm (or) Time Cost Trade-off Algorithm (or) Least Cost Schedule Algorithm 13.6 Resource Allocation and Scheduling 13.7 Application and Disadvantages of Networks 13.7.1 Application Areas of PERT/CPM Techniques 13.7.2 Uses of PERT/CPM for Management 13.7.3 Disadvantages of Network Techniques 13.8 Network Flow Problems 13.8.1 Introduction 13.8.2 Max-flow Min-cut Theorem 13.8.3 Enumeration of Cuts 13.8.4 Ford–Fulkerson Algorithm 13.8.5 Maximal Flow Algorithm 13.8.6 Linear Programming Modelling of Maximal Flow Problem 13.9 Spanning Tree Algorithms 13.9.1 Basic Terminologies 13.9.2 Some Applications of the Spanning Tree Algorithms 13.9.3 Algorithm for Minimum Spanning Tree 13.10 Shortest Route Problem 13.10.1 Shortest Path Model Exercises 14. Simulation 14.1 Introduction 14.1.1 What is Simulation 14.1.2 Definitions of Simulation 14.1.3 Types of Simulation 14.1.4 Why to Use Simulation 14.1.5 Limitations of Simulation 14.1.6 Advantages of Simulation 14.1.7 Phases of Simulation Model 14.2 Event Type Simulation 14.3 Generation of Random Numbers (or) Digits 14.4 Monte-Carlo Method of Simulation 14.5 Applications to Queueing Problems 14.6 Applications to Inventory Problems 14.7 Applications to Capital Budgeting Problem 14.8 Applications to PERT Problems 14.9 Hospital Simulation 14.10 Computer Simulation 14.11 Simulation of Job Sequencing 14.12 Application of Simulation Exercises 15. Non-Linear Programming 15.1 Introduction 15.2 Formulation of a Non-Linear Programming Problem (NLPP) 15.3 Unconstrained Optimisation 15.3.1 Univariate Optimisation 15.3.2 Bivariate Optimisation 15.3.3 Multivariate Optimisation 15.4 Constrained Optimisation 15.4.1 Constrained Optimisation with Equality Constraints 15.4.2 Constrained Optimisation with Inequality Constraints 15.5 Graphical Method of Solving a Non-Linear Programming Problem 15.6 Quadratic Programming 15.6.1 Wolfe’s Modified Simplex Method 15.7 Search Procedure for Unconstrained Optimisation 15.7.1 One-variable Unconstrained Optimisation 15.7.2 One-dimensional Search Procedure 15.7.3 Multivariable Unconstrained Optimisation 15.7.4 The Gradient Search Procedure 15.7.5 Fibonacci Search Technique 15.7.6 Golden Section Search Exercises Index Operations research, 2e is the study of optimization techniques. Designed to cater to the syllabi requirements of Indian universities, this book on operations research reinforces the concepts discussed in each chapter with solved problems. A unique feature of this book is that with its focus on coherence and clarity, it hand-holds students through the solutions, each step of the way