You are previewing Operations Research, 2nd Edition.
O'Reilly logo
Operations Research, 2nd Edition

Book Description

Operations Research, 2nd Edition 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.

Table of Contents

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