Operations Research Natarajan, A.M.

perations research 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.

Chennai • Delhi
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

Preface
Operations research is the study of optimisation techniques. It is applied to decision theory. The existence of optimisation techniques can be traced at least to the days of Newton and Lagrange. Rapid development and invention of new techniques have occurred since the Second World War, essentially because of the necessity to win the war with limited resources. There has been a long-felt need for a simple book on operations research covering the syllabi of Indian universities. The present book has been designed to address this lacuna and cater to the needs of the students of BE, MCA, MBA, M.Sc. and M.Com. courses. It is an outcome of the long-standing experience and interest of the authors in teaching operations research. A unique feature of the book is that each chapter abounds with solved problems that are explained in a simple way that enables the student to understand the subject with ease.
Chapter 1 provides the definition and a brief historical background of operations research. The chapter acquaints the reader with not only the meaning and purpose but also the limitations of operational research. It also gives insight into the approaches and tools of operations research and describes the relationship between an operational research specialist and a manager.
Chapter 2 discusses the formulation of a linear programming problem (LPP) with different types of linear constraints. The graphical solution to an LPP is explained with the aid of a number of examples. The cases of multiple, unbounded solution and infeasible problems are also illustrated graphically. LPPs involving more than two decision variables can be solved with the help of simplex method. Slack variables are introduced to convert less than or equal to type constraints into equations. When some of the constraints are of greater than or equal to type, surplus variables are introduced to convert inequalities to equations. The chapter describes the concept of introducing artificial variables to initiate simple computations. LPPs, in such cases, are solved by two methods, namely the two-phase method and the Big M method. The cases of multiple solution, unbounded solution and infeasible problems are discussed with the help of appropriate examples.
The dual to an LPP is examined in Chapter 3. The economic interpretations of dual variables, which can be used by the management for planning its resources, are also covered in this chapter. If an LPP involving a large number of variables and constraints is to be solved by this method, it will require a large storage space and time on a computer. In this chapter, we take a close look at some computational techniques that have been developed, which require much less computer storage and time than that required by the simplex method. An important and efficient computational technique is the revised simplex method or simplex method with multipliers. The sensitivity analysis of a problem to study the effect of change in various resource levels is also discussed, as are some integer programming formulation techniques. The chapter also highlights the applications of these techniques in managerial problems where LP techniques fail. Two more methods, namely cutting plane method and branch and bound method, as well as the 0-1 programming are elucidated.
In Chapter 4, the formulation of a transportation problem is analysed. Five methods, namely the north-west corner rule, matrix minima method, row minima method, column minima method and Vogel's approximation method, to determine an initial basic feasible solution are spelt out. In addition, the modified distribution method and stepping stone method for obtaining the optimal solution of a transportation problem are explained. The chapter outlines the unbalanced transportation problem, degenerate transportation problem and trans-shipment problem, while also touching upon sensitive analysis.
Chapter 5 explains the formulation of an assignment problem with the help of examples. The Hungarian method for solving an assignment problem is discussed. The chapter also describes the methods to convert an unbalanced assignment problem into a balanced problem and to handle problems with infeasible assignment. The modification of the assignment problem when the objective is to maximise the objective function is also exemplified.
Chapter 6 is on dynamic programming. It explains the methodology relating to dynamic programming along with various concepts. An assortment of dynamic programming applications is also explained.
The foregoing chapters deal with formulation and solution of models under conditions of perfect information. This is usually referred to as decision-making under certainty. Many managerial decisions, however, are made with some uncertainty. Chapter 7 explores the ways of making decisions under uncertainty, decisions under certainty and decisions under risk. Any decision-making process can be represented by means of a tree known as a decision tree.
Chapter 8 deals with the game theory. The theory of games aids managerial decision-making in a comprehensive environment. After producing a conceptual framework on games, this chapter covers the salient elements of the theory of games, namely saddle mixed strategies, dominance, 2 × n games and n × 2 games.
Chapter 9 elucidates the intricacies associated with the sequencing problem and scrutinizes easier methods of dealing with such problems.
Chapter 10 deals with replacement problems and sheds light on the replacement of items with gradual deterioration, item deterioration with money value and items that failed completely and suddenly. This chapter concludes with the staff replacement problem.
Chapter 11 unravels the various concepts pertaining to inventory. It explains the need, objectives and functions of inventory. Three-way classification of inventory and the factors influencing inventory are also provided. It describes inventory models with probabilistic demand and concludes by discussing Always Better Control (ABC) analysis.
Chapter 12 discusses the basic characteristics of a queuing problem and explains its occurrence in real-life situations. The queuing models under M/M/1, M/M/C and M/Ek/1 systems are illustrated with suitable examples.
The critical path method (CPM) and the project evaluation and review technique (PERT) are discussed in Chapter 13.
Chapter 14 deals with simulation. This technique is used in management problems where it is not possible to use any precise mathematical model. The applications of simulation model in practical business problems are illustrated in this chapter.
The last chapter of this book, Chapter 15, is on non-linear programming (NLP) problems. The necessary and sufficient conditions to obtain optimal solution for an NLP problem given by Kuhn–Tucker are discussed. Further, the concepts of quadratic programming and separable programming are also delineated in this chapter along with their applications.
The Teaching and Learning Package
The teaching and learning package, in the form of PowerPoint lecture slides, can be downloaded from the book's companion Web site www.pearsoned.co.in/amnatarajan. These slides, available for each chapter, provide lecture outlines, important concepts and diagrams and additional material, which can be used by instructors to deliver effective lectures.

English