OPERATION RESEARCH FOR BEGINNERS.pdf

Operation Research for
Beginners

By
Girish Bhimani
Tushar Bhatt
Disha Rank
Jalpa Rank

Self-Published

Publisher’s Address:
Department of Statistics
Saurashtra University
Rajkot-360005
Printer’s Details:
Parshva Printery
Rajkot-360005

ISBN: 978-93-5526-378-0
Copyright @ Rank Disha

PREFACE
The purpose of the book is to present the current techniques of operations research in such
a way that they can be readily comprehended by the average business student taking an
introductory course in operations research. Several OR teachers and teachers from management
schools suggested that we should bring out a separate volume on OR with a view to meet the
requirements of OR courses, which can also be used by the practising managers. The book can be
used for one semester/term introductory course in operations research. Instructors may like to
decide the appropriate sequencing of major topics covered.
This book will be useful to the students of management, OR, industrial and production
engineering, computer sciences, chartered and cost-accountancy, economics and commerce. The
approach taken here is to illustrate the practical use of OR techniques and therefore, at places
complicated mathematical proofs have been avoided. To enhance the understanding of the
application of OR techniques, illustrations have been drawn from real life situations. The problems
given at the end of each chapter have been designed to strengthen the student's understanding of
the subject matter. Our long teaching experience indicates that an individual's comprehension of
the various quantitative methods is improved immeasurably by working through and
understanding the solutions to the problems.
It is not possible for us to thank individually all those who have contributed to the case
histories. Our colleagues and many people have contributed to these studies and we gratefully
acknowledge their help. Without their support and cooperation this book could not have been
brought out. Our special thanks are due to Dr. K. H. Atkotiya who have assisted me in editing the
case studies. we wish to express my sincere thanks to Mr. Chandraprakash Shah making available
all facilities needed for this job. We express my gratitude to my parents who have been a constant
source of Inspiration.
We Strongly believe that the road to improvement is never-ending. Suggestions and
criticism of the books will be very much appreciated and most gratefully acknowledged.

Girish Bhimani
Tushar Bhatt
Disha Rank
Jalpa Rank

Index
Module – 1: Fundamental of Operations Research.....………………………………………… …….......1
1.1 Historical background of O.R. ……………………………… 3
1.2 Definition and Meaning of O.R ……………………………… 3
1.3 Features of O.R ……………………………… 3
1.4 Modeling in O.R ……………………………… 4
1.5 Types of Models ……………………………… 5
1.6 General solution methods for O.R. models ……………………………… 5
1.7 Advantages and Limitations of O.R / O.R Models ……………………………… 6
1.8 Multiple Choice Questions – I ……………………………… 6
1.9 Review Questions – I ……………………………… 7
1.10 Linear Programming ……………………………… 7
1.11 Components of Linear Programming Problem ……………………………… 8
1.12 Basic Assumption in LPP [Properties of LP - models] ……………………………… 8
1.13 Different Types of LPP’s ……………………………… 9
1.14 Steps for Mathematical Formulation of LPP’s ……………………………… 9
1.15 Production Allocation Problem ……………………………… 10
1.16 Multiple Choice Questions – II ……………………………… 12
1.17 Review Questions – II ……………………………… 13
1.18 LPP - Graphical Solution and Extension ……………………………… 14
1.19 Standard Form of LPP ……………………………… 22
1.20 Some Basic Definitions ……………………………… 22
1.21 Simplex Method for solving LPP ……………………………… 23
1.22 Steps for solving L.P.P by Simplex method ……………………………… 26
1.23 Review Exercise ……………………………… 31

Module – 2: Transportation Problem……………………………………………………………………… …...32
2.1 Introduction ……………………………… 34
2.2 Structure of Transportation Problem ……………………………… 34
2.3 Types of Transportation Problems ……………………………… 35
2.4 The methods for solving Transportation Problems ……………………………… 35
2.5 North – West Corner Method (NWCM) ……………………………… 35
2.6 Examples for Balanced T.P’s ……………………………… 36
2.7 Least – Cost Method (LCM) ……………………………… 42
2.8 Vogel’s Approximation Method (VAM) ……………………………… 49
2.9 Optimal solution: MODI Method – UV Method ……………………………… 53
2.10 Degeneracy in Transportation Problem ……………………………… 61
2.11 Exercise ……………………………… 65

Index
Module – 3: Assignment Problem…………………………………………………………………………… ……66
3.1 Introduction ……………………………… 67
3.2 Structure of assignment problem ……………………………… 67
3.3 Hungarian Method for solving AP ……………………………… 68
3.4 Exercise ……………………………… 82
Module – 4: Assignment Problem…………………………………………………………………………… ……83
4.1 Introduction ……………………………… 84
4.2 Failure Mechanism of Items ……………………………… 85
4.3 Costs to be considered ……………………………… 86
4.4 When The Replacement Is Justified? ……………………………… 86
4.5 Replacement model ……………………………… 86
4.6 Replacement policy ……………………………… 87
4.7 Replacement of items whose maintenance cost
increases with time and the money value changes at a
constant rate
……………………………… 97
4.8 Exercise ……………………………… 103
Module – 5: Network Analysis……………………………………………………………………………… ……..104
5.1 Introduction ……………………………… 105
5.2 Phases of CPM and PERT ……………………………… 105
5.3 Some important definitions ……………………………… 106
5.4 Project management or representation by a network
diagram
………………………………
107
5.5 Types of activities ……………………………… 107
5.6 Types of events ……………………………… 108
5.7 Common Errors ……………………………… 109
5.8 Rules of network construction ……………………………… 110
5.9 Numbering the events ……………………………… 110
5.10 Time analysis ……………………………… 110
5.11 Determination of Floats and Slack times ……………………………… 111
5.12 Critical activity and Critical path ……………………………… 112
5.13 Project Evaluation and Review Technique (PERT) ……………………………… 121
5.14 Exercise ……………………………… 127
Module – 6: Network Analysis……………………………………………………………………………… ……..128
6.1 Introduction ……………………………… 129
6.2 Properties of Game ……………………………… 130
6.3 Characteristics of Game Theory ……………………………… 130
6.4 Classification of Games ……………………………… 132
6.5 The MaxiMin-MiniMax Principle ……………………………… 133
6.6 Two-Person and Zero-Sum Game ……………………………… 134
6.7 Exercise ……………………………… 143

1 | P a g e

In a sense, every effort to apply science to management of organized systems, and to their
understanding, was a predecessor of operations research. It began as a separate discipline,
however, in 1937 in Britain as a result of the initiative of A.P. Rowe, superintendent of the
Bawdsey Research Station, who led British scientists to teach military leaders how to use
the then newly developed radar to locate enemy aircraft. By 1939 the Royal Air
Force formally commenced efforts to extend the range of radar equipment so as to increase
the time between the first warning provided by radar and the attack by enemy aircraft. At
first they analyzed physical equipment and communication networks, but later they
examined behaviour of the operating personnel and relevant executives. Results of the
studies revealed ways of improving the operators’ techniques and also revealed
unappreciated limitations in the network.
Similar developments took place in the British Army and the Royal Navy, and in both cases
radar again was the instigator. In the army, use of operations research had grown out of the
initial inability to use radar effectively in controlling the fire of antiaircraft weapons. Since
the traditional way of testing equipment did not seem to apply to radar gunsights,
scientists found it necessary to test in the field under operating conditions, and the
distinguished British physicist and future Nobel Laureate P.M.S. Blackett organized a team
to solve the antiaircraft problem. Blackett’s Antiaircraft Command Research Group
included two physiologists, two mathematical physicists, an astrophysicist, an army officer,
a former surveyor, and subsequently a third physiologist, a general physicist, and two
mathematicians.
By 1942 formal operations research groups had been established in all three of Britain’s
military services.Development of operations research paralleling that in Britain took place
in Australia, Canada, France, and, most significantly for future developments, in the United
States, which was the beneficiary of a number of contacts with British researchers. Sir
Robert Watson-Watt, who with A.P. Rowe launched the first two operational studies of
radar in 1937 and who claims to have given the discipline its name, visited the United
States in 1942 and urged that operations research be introduced into the War and Navy
departments. Reports of the British work had already been sent from London by American
observers, and James B. Conant, then chairman of the National Defense Research
Committee, had become aware of operations research during a visit to England in the latter
1
Funda
menta
l of
Opera
tions
Resea
rch

Fundamental of Operations Research

2 | P a g e

half of 1940. Another stimulant was Blackett’s memorandum, “Scientists at the Operational
Level,” of December 1941, which was widely circulated in the U.S. service departments.
The first organized operations research activity in the United States began in 1942 in
the Naval Ordnance Laboratory. This group, which dealt with mine warfare problems, was
later transferred to the Navy Department, from which it designed the aircraft mining
blockade of the Inland Sea of Japan.
As in Britain, radar stimulated developments in the U.S. Air Force. In October 1942, all Air
Force commands were urged to include operations research groups in their staffs. By the
end of World War II there were 26 such groups in the Air Force. In 1943 Gen. George
Marshall suggested to all theatre commanders that they form teams to study amphibious
and ground operations.
At the end of World War II a number of British operations research workers moved to
government and industry. Nationalization of several British industries was an important
factor. One of the first industrial groups was established at the National Coal Board.
Electricity and transport, both nationalized industries, began to use operations research
shortly thereafter. Parts of the private sector began to follow suit, particularly in those
industries with cooperative research associations; for example, in the British Iron and Steel
Research Association.
The early development of industrial operations research was cautious, and for some years
most industrial groups were quite small. In the late 1950s, largely stimulated by
developments in the United States, the development of industrial operations research in
Britain was greatly accelerated.
Although in the United States military research increased at the end of the war, and groups
were expanded, it was not until the early 1950s that American industry began to take
operations research seriously. The advent of the computer brought an awareness of a host
of broad system problems and the potentiality for solving them, and within the decade
about half the large corporations in the United States began to use operations research.
Elsewhere the technique also spread through industry.
Societies were organized, beginning with the Operational Research Club of Britain, formed
in 1948, which in 1954 became the Operational Research Society. The Operations Research
Society in America was formed in 1952. Many other national societies appeared; the first
international conference on operations research was held at Oxford University in 1957. In
1959 an International Federation of Operational Research Societies was formed.

Module – 1: Fundamental of Operations Research
3 | P a g e

1.1 Introduction
The term O.R. was first coined in 1940 by McClosky and Trefthen in a small town, Bowdsey
of the United Kingdom. This new science came into existence as a result of research on
military operations during World War II.

During the war there were strategic and tactical problems which were greatly complicated
to expect adequate solutions from individuals or specialists were unrealistic. Therefore the
military management called on scientists from various disciplines and organized them into
teams to assist in solving strategic and tactical problems, i.e. to discuss, evolve and suggest
ways and deliberations, they suggested certain approaches that showed remarkable
progress. This new approach to systematic and scientific study of the operations of the
system was called the operations research or operational research.
It was only in the early 1950’s that the industries in U.S.A realized the importance of this
new science in solving their management problems. Since then industrial O.R. developed
rapidly in U.S.A as compared to U.K.
Throughout the module we use abbreviation O.R for operations research.
1.2 Definition and Meaning of O.R
O.R. is a scientific approach to problem solving for executive management. –H.M. Wagner
, in which the operation means identify problems and in
scientific way to represent it and research means inventing some new ideas techniques,
models for solving desired problems.
O.R. is the application of the methods of science to solve complex problems arising in the
management of large systems of man, machine, and materials in industry.
It measures the factors such as risk, chances, comparisons, controlling and decision-making
extra. It is experimental.
1.3 Features of O.R
1. Systematic approach: Apply scientific methods for the purpose of solving
problems. It is a formalized process of reasoning.
2. Objectivity: It is attempts to locate the best or optimal solution to the problem
under consideration.

Module – 1: Fundamental of Operations Research
4 | P a g e

3. Decision making: Primarily O.R. is addressed to managerial decision – making or
problem solving. A major premise of O.R. is that decision – making, irrespective of
the situation involved, can be considered as a general systematic process.
4. Inter-disciplinary team approach: O.R. is inter-disciplinary in nature and requires
a team approach to a solution of the problem. Managerial problems have economic,
physical, psychological, biological, sociological and engineering aspects. This
requires a blend of people with expertise in the areas of mathematics, statistics,
engineering, economics, management, computer science and so on.
5. Digital computer: Use of a digital computer has become an integral part of the O.R.
approach to decision making. The computer may be required due to complexity of
the model.

1.4 Modeling in O.R
A model in O.R. is a simplified representation of an operation or a process in which only the
basic aspects or the most important features of a typical problem under investigation are
considered. Models, in general cannot represent every aspect of reality because of
innumerable and changing characteristics of the real life problems to be represented.
Instead, they are limited approximations of the reality.
Following are the main characteristics that a good model for O.R.
1. A good model should be capable of taking into account new formulation without
having any significant change in its frame.
2. Assumptions made in the model should be as small as possible.
3. It should be simple and coherent. Number of variables used should be less.
4. It should be open to parametric type of treatment.
5. It should not take much time in its construction for any problem.
The models are developed by using following methods:
1. Function
2. Predictive
3. Problem structure
4. Nature of the environment
5. Extent of generality

Module – 1: Fundamental of Operations Research
5 | P a g e

1.5 Types of Models
Based on the significance of the problem and its nature suitable model can be selected. If
the problem is trivial and routine any one the verbal, schematic or iconic models can be
chosen. If the outcome of the decision is not significant to the organization, opinion or
judgmental methods can be used to make a decision. Mainly there are four types of models
can be used in decision making in O.R. as follows:

1.6 General solution methods for O.R. models
1. Analytical methods: In these methods classical optimization techniques such as
calculus, finite differences and etc. are used for solving an O.R. model. The kind of
mathematics required depends upon the nature of the model.
2. Numerical methods: Numerical methods are concerned with the iterative or trial
and error procedures, through the use of numerical computation at each step. These
numerical methods are used when some analytical methods fail to derive the
solution.
3. Monte Carlo methods: These involve the use of probability and sampling concepts.
The various steps associated with a Monte Carlo method are as follows:

3.1 For appropriate model of the system, make sample observations and determine
the probability distribution for the variables of interest.
Models
Verbal Physical
(Iconic)
Schematic Mathematical
Verbal Scale Charts & Diagrams Equations

Module – 1: Fundamental of Operations Research
6 | P a g e

3.2 Convert the probability distribution to cumulative distribution.
3.3 Select the sequence of random numbers with the help of random tables.
3.4 Determine the sequence of values of variables of interest with the sequence of
random numbers obtained in the above step.
3.5 Fit an appropriate standard mathematical function to the values obtained in
step-3.4.
The Monte Carlo method is essentially a simulation technique in which statistical
distribution functions are created by generating a series of random numbers.
1.7 Advantages and Limitations of O.R / O.R Models
Models in O.R. are used as an aid for analyzing complex problems. The main advantages of a
model are:
1. Through a model, the problem under consideration becomes controllable.
2. It provides some logical and systematic approach to the problem.
3. It indicates the limitations and scope of an activity.
4. It helps in finding avenues for new research and improvements in a system.
However besides the above advantages a model has the following limitations:
1. Models are only an attempt in understanding operations and should never be
considered as absolute in any sense.
2. Validity of any model with regard to corresponding operation can only be verified
by carrying out the experiment and observing relevant data characteristics.
3. Construction of models requires experts from various disciplines.
1.8 Multiple Choice Questions – I
1. Operation research came into existence _____.
(a) In the year 1940
(b) In the military context
(c) During World War I
(d) During World War II

2. Operation research is _____.
(a) Applied decision theory
(b) A scientific approach to problems solving for executive management
(c) The science of use
(d) all of the above

Module – 1: Fundamental of Operations Research
7 | P a g e

3. Operation research approach is _____.
(a) intuitive
(b) Objective
(c) Multi-disciplinary
(d) all of the above

4. A model in Operation research is _____.
(a) An approximation
(b) An idealization
(c) An essence of reality
(d) all of the above

5. A model in Operations Research is _________
(a) An approximation
(b) An idealization
(c) An essence of reality
(d) All of the above

6. A physical model is an example of __________
(a) Ironic model
(b) Analogue model
(c) Verbal model
(d) Symbolic model

7. The scientific method in Operations Research consists of __________.
(a) Judgment Phase
(b) Research Phase
(c) Action Phase
(d) All of the above

1.9 Review Questions – I
1. What is Operation Research?
2. State the features of O.R.
3. Explain in detail the modeling in O.R.
4. Explain the advantages and limitations of O.R.
5. Explain in detail: General solution methods for O.R. models.
1.10 Linear Programming
 In O.R. our main focus to obtain an optimal solution of any problem, the techniques
for obtaining an optimal solution will be known as optimization. Optimization is the
act of obtaining the best result under given circumstances.

Module – 1: Fundamental of Operations Research
8 | P a g e

 Optimization can be defined as the process of finding the conditions that give
maximum or minimum value of a function.
 Any problem that requires a positive decision to be made can be classified as an
operation research (OR) type problem and solutions can be made according to them
as known as Optimization Techniques.
 The linear programming is one of the best tool or technique of OR.
 George B. Dantzig is generally recognized as the pioneer of linear programming.
1.11 Components of Linear Programming Problem
A linear programming problem (LPP) consists of three components namely,
 Decision Variables / Activities: It refers to the activities that are competing one
another for sharing the resources available. These variables are usually inter-related
in terms of utilization of resources and need simultaneous solutions. All the decision
variables are considered as continuous, controllable and non-negative.

 The Objective / Goal: A linear programming problem must have an objective which
should be clearly identifiable and measurable in quantitative terms. It could be of
profit (sales) maximization, cost (time) minimization and so on. The relationship
among the variables representing objective must be linear.

 The Constraints / Restrictions: There are always certain limitations or
constraints on the use of resources, such as labor, space, raw material, money and
many more that limit the degree to which an objective can be achieved.

1.12 Basic Assumption in LPP [Properties of LP - models]
The following four basic assumptions are necessary for all linear programming problems:
 Certainty: In all LPP’s, it is assumed that all the parameters such as availability of
resources, profit (or cost) contribution of a unit of decision variable and
consumption of resources by a unit decision variable must be known and fixed.

 Divisibility / Continuity: This implies that solution values of the decision variables
can take only non-negative values, including fraction values.

Module – 1: Fundamental of Operations Research
9 | P a g e

 Proportionality: This requires the contribution of each decision variable in both
the objective function and the constraints to be directly proportional to the value of
the variable.

 Additivity: The value of the objective function for the given values of decision
variables and the total sum of resources used, must be equal to the sum of the
contributions (profit or cost) earned from each decision variable and the sum of the
resources used by each decision variable respectively.

1.13 Different Types of LPP’s
 Manufacturing Problems: Determine the number of units that should be produced
and sold in order to maximize profit, when each product requires a fixed manpower,
machine hours and raw materials.

 Diet Problems: Determine the amount of different kinds of to be included in the
diet, minimizing the cost and subject to the availability of food and their prices.

 Transportation Problems: Determine a transportation schedule to find the
cheapest way of transporting a product from plants or factories situated at different
location to different markets.

1.14 Steps for Mathematical Formulation of LPP’s
 Step – 1: To identify the decision variables from the problem.

 Step – 2: To construct the objective function as a linear combination of the
decision variables.

 Note: Let

are some decision variables and

are some
constants the

is called the linear combination of

and

.

 Step – 3: To identify the constraints of the problem such as resources limitations,
Inter-relationship between variables etc. Formulae of these constraints as linear
equations or inequations in terms of non-negative decision variables.
Thus, LPP is a collection of objective function, the set of constraints and the set of the non –
negative constraints.

Module – 1: Fundamental of Operations Research
10 | P a g e

1.15 Production Allocation Problem
Ex-1: A manufacturer produce two types of models M and N each M model requires 4 hours
grinding and 2 hours for polishing whereas each N model requires 2 hours of grinding and
5 hours for polishing. The manufacturer has 2 grinders and 3 polishers. Each grinder works
for 40 hrs a week and each polisher’s works for 60 hrs a week. Profit on an M model is 3 RS.
and on an N model is 4 Rs. whatever is produced in a week sold in the market. How should
the manufacturers allocate this production capacity to the two types of models? So that he
may make the maximum profit in a week?
Solution:
Step – 1: Here first we identify the decision variables

Step – 2: Construct the Objective Function
Maximize

Step – 3: Identify the Constraints
Subject to constraints

And

Ex-2: A firm manufacturers 3 products A, B and C. The profits are 3 Rs, 2Rs, and 4 Rs,
respectively. The firm has two machines
and
below is the required time in minutes
for each machine on each product.

Products

A B C

4 3 5

2 2 4

Module – 1: Fundamental of Operations Research
11 | P a g e

Machines M1 and M2 have 2000 and 2500 machine minutes respectively. The firm must
manufacture 100A’s, 200B’s and 50C’s but not more than 150A’s. Set up an LPP to
maximize profit.
Solution:
Step – 1: Here first we identify the decision variables

Step – 2: Construct the Objective Function
Maximize

Step – 3: Identify the Constraints
Subject to constraints

And

Ex-3: A mine company has two different mines X and Y that produce an ore which after
being crushed, is graded into three classes: high medium and low grade. The company has
contracted to provide a smelting plant with 12 tons of high grade, 8-tons of medium grade
and 24-tons of low grade ore per week. The two mines have different operating
characteristic as detailed below:
Mine Cost/day
(Rs’ 000)
Production(Tons/day)
High Medium Low
X 180 6 3 4
Y 160 1 1 6
How many days per week should each mine be operated to fulfils the smelting plant
contract? For minimizing the cost of product.
Solution:
Step – 1: Here first we identify the decision variables

Module – 1: Fundamental of Operations Research
12 | P a g e

Step – 2: Construct the Objective Function
Maximize
Step – 3: Identify the Constraints
Subject to constraints

Days per week constraints we cannot work more than a certain maximum number of days
a week consider 5 working days in a week therefore and It is obvious
1.16 Multiple Choice Questions – II
8. Linear programming problem (LPP) must have _____.
(a) Objective that we aim to maximize or minimize.
(b) Constraints that we need to specify.
(c) Decision variables that we need to determine.
(d) All of the above

9. Which of the following is not correct about LPP?
(a) All constraints must be linear relationships.
(b) Objective function must be linear
(c) All the constraints and decision variables must be of either or type
(d) All decision variables must be non – negative

10. Which of the following is not associated with an LPP?
(a) Proportionality
(b) Uncertainty
(c) Additivity
(d) Divisibility

11. Which of the following is correct?
(a) Linear programming takes into consideration the effect of time and uncertainty
(b) An LPP can have only two decision variables
(c) Decision variables in an LPP may be more or less than the number of
constraints
(d) Linear programming deals with problems involving only a single objective

Module – 1: Fundamental of Operations Research
13 | P a g e

12. A Constraint in an LPP is expressed as _____
(a) An equation with sign
(b) Inequality with sign
(c) Inequality with sign
(d) Any of the above

1.17 Review Questions – II
1. Discuss about the components of Linear Programming Problem.
2. What is Linear Programming Problem? Discuss about the basic assumptions in LPP.

1.18 LPP - Graphical Solution and Extension
Linear programming problems involving two decision variables can be easily solved by
graphical method. If the problem has more than two variables, graphical method is either
impossible or impractical. Graphical solution to a two variables LP problem can be
obtained using following steps:
Step – 1: To convert all constraints into equations
Step – 2: To plot the graph of equations and apply the conditions given in the constraints.
Step – 3: To identify feasible region (that satisfies all the conditions) and find it’s corners
(extreme points).
Step – 4: To test the maximum / minimum value of objective function for these corners.
Ex – 1: Solve the following LP problem by Graphical method.
Maximize

Subject to

And

.
Solution:
Step – 1: Convert all constraints into equations

Module – 1: Fundamental of Operations Research
14 | P a g e

Decision Variables Points

0 5

3 0

------ (2)
Decision Variables Points

0 2

5 0

Step – 2: To plot the graph of equations and apply the conditions given in the
constraints.
(5, 0)

0(0, 0) 1 2 3 4 5
1
2
3
4
5
B(2, 0)
A (0, 3)
(0, 5)
Feasible Region

Module – 1: Fundamental of Operations Research
15 | P a g e

Consider equation ------ (1) – equation ------ (2) we get

Therefore

put in equation ------ (1) we get,

Therefore

Now the feasible region is: OACBO
Feasible Region
Points
Co-ordinates

Maximum
A (0, 3) 9
12.36
B

(2, 0) 10
C

12.36
O 0

Module – 1: Fundamental of Operations Research
16 | P a g e

Therefore the point

follows Maximize , and hence

and

are the
required solutions.
Ex – 2: Solve the following LP problem by Graphical method.
Maximize

Subject to

And

.
Solution:
Step – 1: Convert all constraints into equations

------ (1)
Decision Variables Points

0 50

100 0

------ (2)
Decision Variables Points

0 80

80 0

Consider equation ------ (1) – equation ------ (2) we get,

------ (1)

------ (2)
_____________________________________________________________________

Put in equation ------ (2) we get
.

.

Module – 1: Fundamental of Operations Research
17 | P a g e

Now the feasible region is: OBCEO
A (0, 80)
B (0, 50)
C (20, 60)
D (100, 0) E (80, 0)
Feasible Region
0(0, 0) 20 40 60 80 100
20
40
60
80
100

Module – 1: Fundamental of Operations Research
18 | P a g e

Feasible Region
Points
Co-ordinates

Maximum
O
(0, 0)

0
4000
B

(0, 50) 900
C (20, 60) 2080
E 4000

Therefore the point follows Maximize , and hence
and
are the
required solutions.
Ex – 3: Solve the following LP problem by Graphical method.
Minimize

Subject to:

,

,

, and

.
Solution:
Step – 1: Convert all constraints into equations

…… (1)
Decision Variables Points

0 -10

0

…… (2)
Decision Variables Points

0 6

6 0

…… (3)
Decision Variables Points

0 2

-2 0

Now next we find the point of intersection of lines form equations (1) and (2) as well as
equations (2) and (3) as follows:

…… (1)

Module – 1: Fundamental of Operations Research
19 | P a g e

…… (2)

put in equation (2) we get

Therefore the point of intersection is

…… (2)

…… (3)

put in equation (2) we get

Therefore the point of intersection is

Module – 1: Fundamental of Operations Research
20 | P a g e

2 4 6 8 10 -10 -8 -6 -4 -2
-2
-4
-6
-8
-10
O
2
4
6
8
10
Feasible Region
A (0, 3.3)
B (-10, 0)
(1)
C (0, 6)
D (6, 0)
(2)
E (0, -2)
(3)
F (2, 0)
G (2, 4)
H (4, 2)

Module – 1: Fundamental of Operations Research
21 | P a g e

Now the feasible region is: OBCEO
Feasible Region
Points
Co-ordinates

Minimum
O
(0, 0)

0
-6
A

(0, 3.3) 6.6
G (2, 4) 6
H (4, 2) 0
D (6, 0) -6
F (2, 0) -2

Therefore the point follows Minimize , and hence
and
are the
required solutions.
Ex-4: A company manufactures two types of boxes, corrugated and ordinary cartons. The
boxes undergo two major processes: cutting and pinning operations. The profits per unit
are Rs. 6 and Rs. 4 respectively. Each corrugated box requires 2 minutes for cutting and 3
minutes for pinning operation, whereas each carton box requires 2 minutes for cutting and
1 minute for pinning. The available operating time is 120 minutes and 60 minutes for
cutting and pinning machines. Determine the optimum quantities of the two boxes to
maximize the profits using graphical method.
Answer:
Maximize

Subject to

And

.
Maximum with

Solution: H.W.

Module – 1: Fundamental of Operations Research
22 | P a g e

1.19 Standard Form of LPP
In order to get the general solution of the LPP id first put into a common format known as
standard form. The standard form should be including the following properties:
1. All Constraints should be converted into equations with non – negative RHS.
2. All the variables should be non – negative.
3. The objective function is to maximize or to minimize.
Converting Constraints into equations
(1) A constraint of the type is converted into an equation by adding a slack variable

to the LHS of the constraint.
For example, in the constraint,

Add slack variable
to the LHS hence we get

(2) A constraint of the type is converted into an equation by subtracting a surplus
variable
to the LHS of the constraint

For example, in the constraint,

Add slack variable
to the LHS hence we get

1.20 Some Basic Definitions
1. Basic Feasible Solution: A basic feasible solution is a basic solution which also
satisfies the non-negative that is, all basic variables are non- negative.

2. Slack Variable: If constraints have sign, then in order to make it an equality we
have to add something positive to the LHS is called a Slack variable.

Module – 1: Fundamental of Operations Research
23 | P a g e

3. Surplus Variable: If constraints have sign, then in order to make it an equality we
have to subtract something positive to the LHS is called a Surplus variable.
1.21 Simplex Method for solving LPP
Simplex Method: The Simplex method is computational procedure - an algorithm for
solving linear programming problems. In the simplex process, we must first find an initial
basis solution (extreme point). We then proceed to an adjacent extreme point. We continue
moving from point to point until we reach an optimal solution.
For a maximization problem, the Simplex method always moves in the direction of
steepest ascent, thus ensuring that value of the objective function improves with each
solution.
Advantages for solving LPP by simplex method: The Simplex method was an invention
of Dr. George Dantzig in 1947, a replacement for other methods of solving linear
programming problems. It effectively replaced them due to its power and efficiency.
1. For complex problems involving many variables, the Simplex method is much
faster than other algorithms at solving linear systems. The Simplex method's
efficiency is important for computer programming, as the need for processing
power is significantly lower when using it.
2. If more than three variables are in the problem, graphical methods will fail, as
dimensions over 3 cannot be visualized using them. The Simplex method can
apply where graphical methods can't.
3. The Simplex method necessitates taking a set of vertices and testing them with
adjacent vertices, until none are left to test. In the method you use two states.
Either the function improves or remains unchanged. Any other change is ignored.
4. The Simplex method necessitates taking a set of vertices and testing them with
adjacent vertices, until none are left to test. Either the function improves or remains
unchanged.
5. If a system is comprised of entities whose behavior can be modeled with a linear
function, you can employ the Simplex method. Systems appropriate for the
Simplex method include numerous applications in economics, such as optimizing
the price given supply and demand, or in science, monitoring predators and prey
in a given environment.

Module – 1: Fundamental of Operations Research
24 | P a g e

Limitations of Simplex Method for solving LPP
1. Simplex method Involves understanding of many conceptual technical aspects. These
cannot be understood by any manager not conversant with the subject.
2. Linear programming problems need lot of expertise, time and are cumbersome. A
number of steps have to be adopted to proceed in a systematic manner before one can
arrive at the solution.
3. Graphic solution method has lot of applications and is relatively short and simple.
However, it has limitations and cannot be applied to problems with more than two
variables in the objective function.
4. Simplex method of LPP can be applied to problems with more than two variables in the
objective function; the procedure adopted is complicated and long. It may need
computation of 4 to 5 simplex tables and can test the patience of the problem solver.
Computers are of course helpful in such cases.
5. LPP does not lead to ‘a unique’ optimal solution. It can provide different types of
solutions like feasible solution, infeasible solution, unbounded solution, degenerate
solution etc.
6. It gives absurd or impractical results in many solutions. The solution may ask for
providing men or 3· 89 machines which is not possible.
7. LPP model makes many assumptions in the values of objective function and constraint
variables, like the rate of profit. In fact, such assumptions may not be right.
8. The whole approach to the solution is based on the linearity of the functions i.e., all the
variables involved in the problem increase or decrease in a linear manner. This assumption
does not hold well in all cases. In many cases, the objective function may assume the form
of a quadratic equation.

LPP method cannot be used where a number of objectives are required to be fulfilled. It
deals with other maximizing of profits, minimization of costs etc.

Module – 1: Fundamental of Operations Research
25 | P a g e

Algorithm for solving LPP by Simplex method:

No No
 Convert LPP into Standard form
 Decide Coefficient of these variables in the Objective function
Setup initial Simplex table to obtain initial
solution
Compute
and

values
Is LPP of
Max or
Min type?
Maximization Minimization
Do

positive
value
exist?
Do

negative
value
exist?

This solution is
optimal
Yes
Select key column
with largest negative

value
Select key row with

If all
then current solution is unbounded and stops the procedure.
Yes
Select key column
with largest
positive

value
Identity key element at the intersection of key row and key column
Update the entries in the Simplex table by
(a) 1
st obtaining key row values, and
(b) Apply elementary row operations

Module – 1: Fundamental of Operations Research
26 | P a g e

1.22 Steps for solving L.P.P by Simplex method
 Step – 1: To convert given LPP into standard form
 Step – 2: To Make an initial simplex table
 Step – 3: To calculate
and

.
 Step – 4: To find maximum value from

.
 Step – 5: The corresponding column to max. Value denotes as key
column and similarly find

and it is denote as key
row. The intersection point of key row and key column mark as key element.
 Step – 6: To replace key row by key column and make zero entry to up
side and down side of the key element. Here observe that the key
element is must be one.
 Step – 7: To be continuing above process until the difference

is either
zero or negative values. Hence we get the optimum solution.
Ex- 1: Solve the following LPP by simplex method
Maximize

Subject to

And

Solution:
(1) Standard Form of LPP

Maximize

And

Module – 1: Fundamental of Operations Research
27 | P a g e

(2) Initial Simplex table
INITIAL TABLE - 0

3 2 0 0
B

0 40 1 1 1 0

0 20 1 -1 0 1

0 0 0 0

3 2 0 0
All

is not therefore further revision is required.
Key element = 1
Incoming variable

Outgoing variable

40 1 1 1 0
20 1 -1 0 1
20 0 2 1 -1
MODIFIED TABLE - 1

3 2 0 0
B

0 20 0 2 1 -1

3 20 1 -1 0 1

3 -3 0 3

0 5 0 -3
All

is not therefore further revision is required.
Key element , here we must make the key element . Therefore 1
st
row in above table
is divided by 2.

Module – 1: Fundamental of Operations Research
28 | P a g e

Incoming Variable

Outgoing Variable

MODIFIED TABLE - 2

3 2 0 0
B

2 10 0 1

3 30 1 0

3 2

0 0 0

In the above table all

therefore there is no need for revision and the values of
basic variables are our required solution.

And

And hence maximize

.
Ex – 2: Solve the following LPP by Simplex method:
Minimize

Subject to

And

.

Solution: Here we are convert first, the given LPP into maximize Z and all numerical values
of right hand side of constraints are non-negative. So we get

Module – 1: Fundamental of Operations Research
29 | P a g e

Maximize

Subject to

And

Standard Form
Maximize

Subject to

And

Initial table - 0

-1 3 -3 0 0 0
B

0 7 3 -1 2 1 0 0 -

0 12 -2 -4 0 0 1 0 -

0 10 -4 3 8 0 0 1

0 0 0 0 0 0

-1 3 -3 0 0 0

Module – 1: Fundamental of Operations Research
30 | P a g e

Incoming variable

Outgoing variable

Key element
Modified table - 1

-1 3 -3 0 0 0
B

0

0

1 0

0

0

0 1

-

3

1

0 0

-

-4 3 8 0 0 1

3 0 -11 0 0 -1

Incoming variable
, Outgoing variable
, Key element

Modified table - 2

-1 3 -3 0 0 0
B

-1

0

0

0

0

1

-

3

1

0

-

-1 3

0

0 0

0

Module – 1: Fundamental of Operations Research
31 | P a g e

According to modified table-2
All

then the optimal/optimum solution is

And maximum

Required minimum

1.23 Review Exercise
Ex – 1: Solve the following LPP’s using Simplex Method.
Maximize

Subject to

And

.
Answer:

and .

Ex – 2: Solve the following LPP’s using Simplex Method.
Maximize

Subject to

And

.
Answer:

and .
.
Ex – 3: Solve the following LPP’s using Simplex Method.
Maximize

Subject to

And

.
Answer:

and .

32 | P a g e

Transportation theory is a name given to the study of optimal transportation and allocation
of resources. The problem was formalized by the French mathematician Gaspard
Monge(1871). In the 1920s A.N. Tolstoi was one of the first to study the transportation
problem mathematically. In 1930, in the collection Transportation Planning Volume I for
the National Commissariat of Transportation of the Soviet Union, he published a paper
Methods of Finding the Minimal Kilometrage in Cargo-transportation in space.
Tolstoi(1939) illuminated his approach by applications to the transportation of salt,
cement, and other cargo between sources and destinations along the railway network of
the Soviet Union. In particular, a, for that large-scale, instance of the transportation
problem was solved to optimality. Major advances in transportation theory were made in
the field during World War II by the Soviet/Russian
mathematician and economist Leonid Kantorovich Consequently, the problem as it is stated
is sometimes known as the Monge–Kantorovich transportation problem. Kantorovich won
the Nobel prize for economics in 1975 for his work on the optimal allocation of scarce
resources, the only winner of the prestigious award to come from the USSR. F.L. Hitchcock
(1941) worked on the distribution of a production from several sources to numerous
localities.
Koopman also worked on the optimum utilization of transportation system and used model
of transportation, in activity analysis of production and allocation. Charnes and Cooper
(1961) mentioned about transportation in their book – Management Models and Industrial
Applications of Linear Programming.
Followed by Ijiri (1965) who mentioned about transportation problem in his book-
Management Goals and Accounting for Control M. Klein (1967) developed a primal method
for minimal cash flows with applications to the assignment and transportation problems.
Hadley(1972) also included transportation problem in his book: Linear Programming. Lee
(1972) and Ignizio(1976) used goal programming to solve transportation problem.
Mackinnon & James (1975) developed an algorithm for the generalized transportation
2
Funda
menta
l of
Opera
tions
Resea
rch

Transportation Problem

33 | P a g e

problem. Moore et-al performed analysis of a transshipment problem with multiple
conflicting objectives. Kwak (1979) developed a goal programming model for improved
transportation problem solutions, followed by Kvanli (1980). OhEigeartaigh (1982)
developed a fuzzy transportation algorithm Arthur-et-al (1982) worked on the multiple
goal production and logistics planning in a chemical and pharmaceutical company.
Olson (1984) has compared four goal programming algorithm. Goyal(1984) worked on
improving VAM for unbalanced transportation problem.
Kwak & Schniederjans(1985) framed goal programming solutions to transportation
problem with variable supply and demand requirement. R.K. Ahuja (1986) developed an
algorithm for minimax transportation problem. In the same Romero has done a survey of
generalized goal programming also Currin worked on the transportation problem with
inadmissible routes.
Romero (1991) has written a book on critical issues in goal programming, followed by
Tamiz & Jones (1995) who has done a review of goal programming and its applications.
Hemaida & Kwak(1994) developed a linear goal programming model for transshipment
problem with flexible supply and demand constraints. Sharma et-al (1999) analyzed
various applications of multi-objective programming in MS/OR.
Sun (2002) worked on the transportation problem with exclusionary side constraints and
branch and bound algorithm. Schrijver(2002) worked on the history of transportation and
maximum flows. Okunbor(2004) worked on the management decision making for
transportation problems through goal programming.

Module – 2: Transportation Problem
34 | P a g e

2.1 Introduction
The transportation problem is a special type of linear programming problem where the
objective consists in minimizing transportation cost of a given commodity from a number
of sources or origins (e.g. factory, manufacturing facility) to a number of destinations (e.g.
warehouse, store). Each source has a limited supply (i.e. maximum number of products that
can be sent from it) while each destination has a demand to be satisfied (i.e. minimum
number of products that need to be shipped to it). The cost of shipping from a source to a
destination is directly proportional to the number of units shipped.
2.2 Structure of Transportation Problem
Basic Notations:










Sources are represented by rows while destinations are represented by columns. In general,
a transportation problem has rows and columns. The problem is solvable if there
are exactly basic variables.

Module – 2: Transportation Problem
35 | P a g e

2.3 Types of Transportation Problems
There are two different types of transportation problems based on the initial given
information:
 Balanced Transportation Problems: cases where the total supply is equal to the total
demand. In short .
 Unbalanced Transportation Problems: cases where the total supply is not equal to
the total demand. When the supply is higher than the demand, a dummy destination is
introduced in the equation to make it equal to the supply (with shipping costs of $0);
the excess supply is assumed to go to inventory. On the other hand, when the demand is
higher than the supply, a dummy source is introduced in the equation to make it equal
to the demand (in these cases there is usually a penalty cost associated for not fulfilling
the demand). In short .
In order to proceed with the solution of any given transportation problem, the first step
consists in verifying if it is balanced. If it is not, it must be balanced accordingly.

2.4 The methods for solving Transportation Problems
Here we are having mainly four methods for solving T.P’s as follows:
1. North – West Corner Method (NWCM)
2. Least – Cost Method (LCM)
3. Vogel’s Approximation Method (VAM)
2.5 North – West Corner Method (NWCM)
Consider the following matrix form of T.P

Module – 2: Transportation Problem
36 | P a g e

Source
Destination

Supply
1

2

3

4

Demand

Working Rules: (Balanced T.P)
1. Select the upper left (North – West) cell of the transportation matrix and allocate
minimum of Supply and Demand value in that cell.

2. After allocation the minimum value to the cell, the cell corresponding row or
columns is completely discard, not consider in the further allocation.

3. Now with the new reduced table, again select the North – West cell and allocate the
available minimum values from the demand and supply.

4. Repeat steps (i), (ii) and (iii) until all supply and demand values are becomes zeros.

5. Hence obtain the initial basic feasible solution.

2.6 Examples for Balanced T.P’s
Ex -1: Solve the following T.P using NWCM
Source
Destination
Supply
1 21 16 25 13 11
2 17 18 14 23 13
3 32 27 18 41 19
Demand 6 10 12 15

Solution: Here given T.P is balanced because .

Module – 2: Transportation Problem
37 | P a g e

TABLE - 1
Source

Destination

Supply
1
21

6
16 25 13 11, 5
2
17 18 14 23 13
3
32 27 18 41 19

Demand 6, 0 10 12 15

TABLE - 2
Source

Destination
Supply
1

16

5
25 13 11, 5, 0
2
18 14 23 13
3
27 18 41 19

Demand 10, 5 12 15

Module – 2: Transportation Problem
38 | P a g e

TABLE - 3
Source

Destination

Supply
1

2

5

18
14 23 13, 8
3
27 18 41 19

Demand 10, 5, 0 12 15

TABLE - 4
Source

Destination
Supply
1

2

8

14
23 13, 8, 0
3
18 41 19

Demand 12,4 15

Module – 2: Transportation Problem
39 | P a g e

TABLE - 5
Source

Destination

Supply

3

18
4
41 19, 15

Demand 12,4, 0 15

TABLE - 6
Source

Destination
Supply

3

41

15
19, 15, 0

Demand 15, 0

Module – 2: Transportation Problem
40 | P a g e

Minimum Transportation Cost

Ex -2: Solve the following T.P using NWCM
Source
Destination
Supply
1 3 1 7 4 250
2 2 6 5 9 350
3 8 3 3 2 400
Demand 200 300 350 150
Solution: Here given T.P is balanced because .
Source
Destination
Supply
1 3 1 7 4
250, 50,
0
2 2

6

5
9
350
,100,0
3 8 3 3 2
400, 150,
0
Demand 200, 0 300, 250, 0
350,
250, 0
150, 0

200 50
250
100
0
250 150

Module – 2: Transportation Problem
41 | P a g e

Minimum Transportation Cost

Working Rules: (Unbalanced T.P)
1. First make a matrix unbalanced to balance by adding dummy row or column with
zero cost.

2. If the total supply is more than the total demand, then we add a new column, with
transportation cost 0

3. If the total demand is more than the total supply, then we add a new row, with
transportation cost 0

4. Select the upper left (North – West) cell of the transportation matrix and allocate
minimum of Supply and Demand value in that cell.

5. After allocation the minimum value to the cell, the cell corresponding row or
columns is completely discard, not consider in the further allocation.

6. Now with the new reduced table, again select the North – West cell and allocate the
available minimum values from the demand and supply.

7. Repeat steps (i), (ii) and (iii) until all supply and demand values are becomes zeros.

8. Hence obtain the initial basic feasible solution.

Ex - 3: Solve the following T.P using NWCM
Destination
Source
Supply
1 4 8 8 76
2 16 25 16 82
3 8 16 24 77

Demand 72 102 41

235
215

Module – 2: Transportation Problem
42 | P a g e

Solution: Here given T.P is unbalanced because .
So first we make the balanced transportation matrix by adding dummy
Destination
DUMMY
COLUMN

Source
Supply
1 4 (72) 8(4) 8 0 76,4,0
2 16 25(82) 16 0 82,0
3 8 16(16) 24(41) 0(20) 77,61,20,0
Demand 72,0 102,98,16,0 41,0 20,0

235

Minimum Transportation Cost

2.7 Least – Cost Method (LCM)
Working Rules: (Balanced T.P)
1. To select the smallest transportation cost cell available in the entire table and
allocate the minimum value from the supply and demand.

2. To delete the row/column which has exhausted means there is zero supply or
demand. The deleted row/column must not be considered for further allocation.

3. Again select the smallest cost cell in the existing table and allocate. (In case, if there
are more than one smallest cost, select the cells where maximum allocation can be
made).

4. And hence obtain the initial basic feasible solution.

Module – 2: Transportation Problem
43 | P a g e

Ex - 1: Solve the following T.P using LCM
Destination
Source
A B C D Supply
1 3 1 7 4 250
2 2 6 5 9 350
3 8 3 3 2 400
Demand 200 300 350 150 1000

Solution: Here given TP is balanced because .
First we find the minimum cost cell from the entire table and give the minimum values
from the supply and demand.
Destination
Source
A B C D Supply
1 3
1
(250)
7 4 250, 0
2 2 6 5 9 350
3 8 3 3 2 400
Demand 200
300,
50
350 150

Destination
Source
A B C D Supply
1
1
(250)

2
2
(200)
6 5 9
350,
150
3 8 3 3 2 400
Demand 200, 0
300,
50
350 150

Module – 2: Transportation Problem
44 | P a g e

Destination
Source
A B C D Supply
1
1
(250)

2
2
(200)
6 5 9
350,
150
3 3 3
2
(150)
400,
250
Demand
300,
50
350 150, 0
Destination
Source
A B C D Supply
1
1
(250)

2
2
(200)
6 5
350,
150
3
3
(50)
3
2
(150)
400,
250,
200
Demand
300,
50, 0
350
Destination
Source
A B C D Supply
1
1
(250)

2
2
(200)
5
350,
150
3
3
(50)
3
(200)
2
(150)
400,
250,
200 ,0
Demand
350,
150

Module – 2: Transportation Problem
45 | P a g e

Total minimum cost
=

Ex - 2: Solve the following T.P using LCM
Source
Destination
Supply

21 16 25 13 11

17 18 14 23 13

32 27 18 41 19
Demand 6 10 12 15 43

Solution: Here given TP is balanced because .
First we find the minimum cost cell from the entire table and give the minimum values
from the supply and demand.

Destination
Source
A B C D Supply
1
1
(250)

2
2
(200)

5
(150)

350,
150,0
3
3
(50)
3
(200)
2
(150)
400,
250,
200 ,0
Demand
350,
150, 0

Module – 2: Transportation Problem
46 | P a g e

Source

Destination
Supply

21
16 25
13
(11)
11,0

17 18 14 23 13

32 27 18 41 19
Demand 6 10 12 15,4 43

Source

Destination
Supply

13
(11)

17 18
14
(12)
23 13,1

32 27 18 41 19
Demand 6 10 12,0 15,4 43

Module – 2: Transportation Problem
47 | P a g e

Source

Destination
Supply

13
(11)

17
(1)
18
14
(12)
23 13,1, 0

32 27 41 19
Demand 6, 5 10 15,4 43

Source

Destination
Supply

13
(11)

17
(1)

14
(12)

32
27
(10)
41 19, 9
Demand 6, 5 10, 0 15,4 43

Module – 2: Transportation Problem
48 | P a g e

Source

Destination
Supply

13
(11)

17
(1)

14
(12)

32
(5)
27
(10)
41 19, 9, 4
Demand 6, 5, 0 15,4 43

Source

Destination
Supply

13
(11)

17
(1)

14
(12)

32
(5)
27
(10)

41
(4)
19, 9, 4, 0
Demand 15,4, 0 43

Module – 2: Transportation Problem
49 | P a g e

Total minimum cost

2.8 Vogel’s Approximation Method (VAM)
Working Rule for balanced TP
1. Calculate penalties for each row and column by taking the difference between the
smallest cost and next highest cost available in that row/column. If there are two
smallest costs, then the penalty is zero.
2. Select the row/column, which has the largest penalty and makes allocation in the
cell having the least cost in the selected row/column, contains minimum unit cost. If
there is again a tie, select one where maximum allocation can be made.
3. Delete the row/column, which has satisfied the supply and demand.
4. Repeat steps 1 and 2 until the entire supply and demands are satisfied.
5. And hence obtained the initial basic feasible solution.

Ex - 1: Solve the following T.P using VAM.
A B C D Supply
1 3 1 7 4 300
2 2 6 5 9 400
3 8 3 3 2 500
Demand 250 350 400 200 1200

Solution: Here given TP is balanced because .
Here first we calculate the penalties for each row and column say

Module – 2: Transportation Problem
50 | P a g e

Module – 2: Transportation Problem
51 | P a g e

Total Minimum cost

Ex - 2: Solve the following T.P using VAM.
A B C Supply
1 2 7 4 5
2 3 3 1 8
3 5 4 7 7
Demand 7 9 4 20

Solution: Here given TP is balanced because .
Here first we calculate the penalties for each row and column say

Module – 2: Transportation Problem
52 | P a g e

Module – 2: Transportation Problem
53 | P a g e

Total minimum cost

2.9 Optimal solution: MODI Method – UV Method
There are two phases to solve the transportation problem. In the first phase, the initial
basic feasible solution has to be found and the second phase involves optimization of the
initial basic feasible solution that was obtained in the first phase. There are three methods
for finding an initial basic feasible solution,
1. North-West Corner Method
2. Least Cost Method
3. Vogel’s Approximation Method
Will discuss how to optimize the initial basic feasible solution through an explained
example. Consider the below transportation problem

Module – 2: Transportation Problem
54 | P a g e

Solution:
Step 1: Check whether the problem is balanced or not. If the total sum of all the supply
from sources O1, O2, and O3 is equal to the total sum of all the demands for destinations
D1, D2, D3 and D4 then the transportation problem is a balanced transportation problem.

Note: If the problem is not unbalanced then the concept of a dummy row or a dummy
column to transform the unbalanced problem to balanced can be followed as discussed.

Module – 2: Transportation Problem
55 | P a g e

Step 2: Finding the initial basic feasible solution. Any of the three aforementioned methods
can be used to find the initial basic feasible solution. Here, North-West Corner Method will
be used. And according to the North-West Corner Method this is the final initial basic
feasible solution:

Now, the total cost of transportation will be

Step 3: U-V method to optimize the initial basic feasible solution.
The following is the initial basic feasible solution:

For U-V method the values
and
have to be found for the rows and the columns
respectively. As there are three rows so three ui values have to be found i.e.
for the first
row,
for the second row and
for the third row.

Module – 2: Transportation Problem
56 | P a g e

Similarly, for four columns four vj values have to be found i.e.

and
. Check the
image below:

There is a separate formula to find
and
,

, where
is the cost value only for the allocated cell. Before applying the
above formula we need to check whether – is equal to the total number of
allocated cells or not where m is the total number of rows and n is the total number of
columns.

In this case and total number of allocated cells is so – . The
case when – is not equal to the total number of allocated cells will be discussed in
the later posts.

Now to find the value for u and v we assign any of the three u or any of the four as . Let
we assign
in this case. Then using the above formula we will get
as

and
as

.
Similarly, we have got the value for
so we get the value for
which
implies
. From the value of
we get
which implies
.

Module – 2: Transportation Problem
57 | P a g e

Now, compute penalties using the formula

–
only for unallocated cells.
We have two unallocated cells in the first row, two in the second row and two in the third
row. Let’s compute this one by one.
1. For

–

2. For

3. For

–
4. For

–
5. For

–
6. For

–
The Rule: If we get all the penalties value as zero or negative values that mean the
optimality is reached and this answer is the final answer.
But if we get any positive value means we need to proceed with the sum in the next step.
Now find the maximum positive penalty.
Here the maximum value is 6 which correspond to
cell. Now this cell is new basic cell.
This cell will also be included in the solution.

Module – 2: Transportation Problem
58 | P a g e

The rule for drawing closed-path or loop. Starting from the new basic cell draw a closed-
path in such a way that the right angle turn is done only at the allocated cell or at the new
basic cell.

Assign alternate plus-minus sign to all the cells with right angle turn (or the corner) in the
loop with plus sign assigned at the new basic cell.

Module – 2: Transportation Problem
59 | P a g e

Consider the cells with a negative sign. Compare the allocated value (i.e. 200 and 250 in this
case) and select the minimum (i.e. select 200 in this case). Now subtract 200 from the cells
with a minus sign and add 200 to the cells with a plus sign. And draw a new iteration. The
work of the loop is over and the new solution looks as shown below

Check the total number of allocated cells is equal to – . Again find values and
values using the formula

where
is the cost value only for allocated cell.
Assign
then we get
. Similarly, we will get following values for
and
.

Find the penalties for all the unallocated cells using the formula

–
.
1. For

–
2. For

–
3. For

–
4. For

–
5. For

–

Module – 2: Transportation Problem
60 | P a g e

6. For

–
There is one positive value i.e. 1 for
. Now this cell becomes new basic cell.

Now draw a loop starting from the new basic cell. Assign alternate plus and minus sign
with new basic cell assigned as a plus sign.

Select the minimum value from allocated values to the cell with a minus sign. Subtract this
value from the cell with a minus sign and add to the cell with a plus sign. Now the solution
looks as shown in the image below:

Module – 2: Transportation Problem
61 | P a g e

Check if the total number of allocated cells is equal to – . Find u and v values as
above.

Now again find the penalties for the unallocated cells as above.
1. For
–
2. For
–
3. For
–
4. For
–
5. For
–
6. For
–
All the penalty values are negative values. So the optimality is reached. Now, find the total
cost i.e.
.
2.10 Degeneracy in Transportation Problem
This session will discuss degeneracy in transportation problem through an explained
example.

Module – 2: Transportation Problem
62 | P a g e

Solution: This problem is balanced transportation problem as total supply is equal to total
demand.

Initial basic feasible solution: Least Cost Cell Method will be used here to find the initial
basic feasible solution. One can also use North-West Corner Method or Vogel’s
Approximation Method to find the initial basic feasible solution. Using Least Cost Method
we get the following solution.

Module – 2: Transportation Problem
63 | P a g e

Optimization of the solution using U-V Method:
Check whether – total number of allocated cells.
In this case – – where as total number of allocated cells are 7,
hence this is the case of degeneracy in transportation problem.
So in this case we convert the necessary number (in this case it is m + n – 1 = total number
of allocated cells i.e. 8 – 7 = 1) of unallocated cells into allocated cells to satisfy the above
condition. Steps to convert unallocated cells into allocated cells:
 Start from the least value of the unallocated cell.
 Check the loop formation one by one.
 There should be no closed-loop formation.
 Select that loop as a new allocated cell and assign a value ‘e’.
The closed loop can be in any form but all the turning point should be only at allocated cell
or at the cell from the loop is started

Module – 2: Transportation Problem
64 | P a g e

There are 13 unallocated cells. Select the least value (i.e. 5 in this case) from unallocated
cells. There are two 5s here so you can select randomly any one. Let’s select the cell with
star marked.

Check if there is any closed-loop formation starting from this cell. If a closed-loop is drawn
from this cell following the condition for closed-loop then it can be observed that this cell
cannot be reached to complete the closed-loop. So this cell will be selected and assigned a
random value ‘e’.

Note: If the closed loop would have been formed from that cell then we would try another
cell with least value and do the same procedure and check whether closed loop is possible
or not. Now total number of allocated cells becomes 8 and – – .
Now this solution can be optimized using U-V method. We get the below solution after
performing optimization using U-V method.

Module – 2: Transportation Problem
65 | P a g e

The presence of two ‘e’ in the final solution means after doing some iterations during
optimization, the condition for degeneracy will be met once again.
While finding the total cost, just leave the ‘e’ and multiply the allocated value with its cell’s
cost value and add all of them.
So, the transportation cost is
.
2.11 Exercise
1. Find the initial basic feasible solution for the following transportation problem,
using North-West Corner Rule method.
Sources

Supply

3 8 5 7

4 4 2 8

6 5 8 10

2 6 3 15
Demand 8 10 22
 Answer: 169

2. Find out the minimum cost solution for the following transportation problem, using
North West Corner Rule method.
Sources

Supply
A 16 19 12 14
B 22 13 19 16
C 14 28 8 12
Demand 10 15 17

Module – 2: Transportation Problem
66 | P a g e

 Answer: 570

3. Obtain the initial basic feasible solution to the following TP using least cost method.
Sources

Supply

1 2 3 4 6

4 3 2 5 8

5 2 2 1 10
Demand 4 6 8 6
 Answer: 38

4. Find the initial basic feasible solution for the following TP by VAM:
Sources

Supply

11 13 17 17 250

16 18 14 10 300

21 24 13 10 400
Demand 200 225 275 250

 Answer: 12075

5. Find the initial basic feasible solution for the following TP by VAM:
Sources

Supply

6 4 1 50

3 8 7 40

4 4 2 60
Demand 20 95 35 150
 Answer: 555

66 | P a g e

As a coherent mathematical discipline, combinatorial optimization is relatively young.
When studying the history of the field, one observes a number of independent lines of
research, separately considering problems like optimum assignment, shortest spanning
tree, transportation, and the traveling salesman problem.
Only in the 1950’s, when the unifying tool of linear and integer programming became
available and the area of operations research got intensive attention, these problems were
put into one framework, and relations between them were laid. Indeed, linear
programming forms the hinge in the history of combinatorial optimization.
Its initial conception by Kantorovich and Koopmans was motivated by combinatorial
applications, in particular in transportation and transshipment. After the formulation of
linear programming as generic problem, and the development in 1947 by Dantzig of the
Simplex method as a tool, one has tried to attack about all combinatorial optimization
problems with linear programming techniques, quite often very successfully.
A cause of the diversity of roots of combinatorial optimization is that several of its
problems descend directly from practice, and instances of them were, and still are, attacked
daily. One can imagine that even in very primitive (even animal) societies, finding short
paths and searching (for instance, for food) is essential. A traveling salesman problem
crops up when you plan shopping or sightseeing, or when a doctor or mailman plans his
tour. Similarly, assigning jobs to men, transporting goods, and making connections, form
elementary problems not just considered by the mathematician.
It makes that these problems probably can be traced back far in history. In this survey
however we restrict ourselves to the mathematical study of these problems. At the other
end of the time scale, we do not pass 1960, to keep size in hand.
3
Funda
menta
l of
Opera
tions
Resea
rch

Assignment Problem

Module – 3: Assignment Problem
67 | P a g e

3.1 Introduction
Assignment Problem is a special type of linear programming problem where the objective
is to minimize the cost or time of completing a number of jobs by a number of persons. The
assignment problem in the general form can be stated as follows:
“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to
assign each facility to one and only one job in such a way that the measure of effectiveness
is optimized (Maximized or minimized).” Several problems of management have a
structure identical with the assignment problem. For example:
Example I: A manager has four persons (i.e. facilities) available for four separate jobs (i.e.
jobs) and the cost of assigning (i.e. effectiveness) each job to each person is given. His
objective is to assign each person to one and only one job in such a way that the total cost
of assignment is minimized.
Example II: A manager has four operators for four separate jobs and the time of completion
of each job by each operator is given. His objective is to assign each operator to one and
only one job in such a way that the total time of completion is minimized.
Example III: A tourist car operator has four cars in each of the four cities and four
customers in four different cities. The distance between different cities is given. His
objective is to assign each car to one and only one customer in such a way that the total
distance covered is minimized
Assignment problems deal with the question how to assign n objects to m other objects in
an injective fashion in the best possible way. An assignment problem is completely
specified by its two components the assignments, which represent the underlying
combinatorial structure, and the objective function to be optimized, which models "the best
possible way”. The assignment problem refers to another special class of linear
programming problem where the objective is to assign a number of resources to an equal
number of activities on a one to one basis so as to minimize total costs of performing the
tasks at hand or maximize total profit of allocation.
3.2 Structure of assignment problem
Each assignment problem has a table or matrix associated with it. Generally the row
contains the objects or people we wish to assign and the column comprise the jobs or task
we want them assigned to. Consider a problem of assignment of n resources to m activities
so as to minimize the overall cost or time in such a way that each resource can associate
with one and only one job. The cost matrix
is given as under:

Module – 3: Assignment Problem
68 | P a g e

3.3 Hungarian Method for solving AP
The Hungarian method was developed by H. Kuhn and is based upon the work of two
Hungarian mathematicians D. Konig and J. Egervary.
For application of the algorithm, it is assumed that all of the
’s of the starting cost matrix
are non- negative and the assignment problem is of minimization case.
Working Rules
1. Subtract the minimum cost from the respective rows then each row containing at
least one zero. Same procedure apply on each column and it is observe that each
column is also having at least one zero. Therefore we get at least one zero in each
row and each column.
2. Examine these rows, which has exactly single zero, give an assignment (means a
square on zero) around it and cross all other zeros in same column. Repeat
same procedure for columns.
3. If passes through above procedure, we get any row/column who does not have any
assignment then follows the below procedure
3.1 Tick the row which does not have any assignment in which also find the
cross .
3.2 Next select the column corresponding to that cross .
3.3 In crossed column find the assignment
3.4 And hence tick the row in assignment lies.
4. Draw lines from unticked rows and ticked columns.
5. Select smallest cost from unlined cost.
6. Add this cost to point of intersection of two lines and subtract it from all unlined cost.
7. Repeat above 1 to 6 steps until each row/column has assignment. And hence we get
optimal assignment cost/time.

Module – 3: Assignment Problem
69 | P a g e

Ex-1: Solve the following AP and find the minimum cost.

2 3 5 3
10 7 13 14
3 2 1 10
3 5 4 6

Solution:
Step-1: Subtract the minimum cost from the respective rows then each row containing at
least one zero.

2 -2 = 0 3-2 = 1 5-2 = 3 3-2 = 1
10-7 = 3 7-7 = 0 13-7 = 6 14-7 = 7
3 -1 = 2 2-1 = 1 1-1 = 0 10-1 = 9
3 -3 = 0 5-3 = 2 4-3 = 1 6-3 = 3

0 1 3 1
3 0 6 7
2 1 0 9
0 2 1 3

Same procedure apply on each column and it is observe that each column is also having at
least one zero.

0 1 3 1-1 = 0
3 0 6 7-1= 6
2 1 0 9-1= 8
0 2 1 3-1= 2

Module – 3: Assignment Problem
70 | P a g e

0 1 3 0
3 0 6 6
2 1 0 8
0 2 1 2

Therefore we get at least one zero in each row and each column.
Step-2: Examine these rows, which has exactly single zero, give an assignment (means a
square on zero) around it and cross all other zeros in same column.

Repeat same procedure for columns.

Since after step – 2 each row/column has an assignment. So optimal assignment are

,

Module – 3: Assignment Problem
71 | P a g e

Therefore the minimum assignment cost/time units.
Ex-2: Solve the following AP and find the minimum cost.

A 26 23 27
B 23 22 24
C 24 20 23
Solution:
Step-1: Subtract the minimum cost from the respective rows then each row containing at
least one zero.

A 26 -23 =23 23-23 =0 27-23 =4
B 23-22 =1 22-22 =0 24-22 =2
C 24-20 =4 20-20 =0 23-20 =3

A 23 0 4
B 1 0 2
C 4 0 3

Same procedure apply on each column and it is observe that each column is also having at
least one zero.

A 23-1=22 0 4-2 =2
B 1-1=0 0 2-2 =0
C 4-1=3 0 3-2 =1

Module – 3: Assignment Problem
72 | P a g e

A 22 0 2
B 0 0 0
C 3 0 1
Therefore we get at least one zero in each row and each column.
Step-2: Examine these rows, which has exactly single zero, give an assignment (means a
square on zero) around it and cross all other zeros in same column.
Repeat same procedure for columns.

Here C does not have any assignment therefore that solution is not optimal then we can
move on step -3 as follows:
Step – 3: Tick the row which does not have any assignment in which also find the
cross .

Module – 3: Assignment Problem
73 | P a g e

Next select the column corresponding to that cross
In crossed column find the assignment

And hence tick the row where assignment lies.

Module – 3: Assignment Problem
74 | P a g e

Step -4: Draw lines from unticked rows and ticked columns.

Step – 5: Select smallest cost from unlined cost.
Here unlined cost are 22, 2, 3 and 1 in which 1 is minimum.
Step -6: Add this cost to point of intersection of two lines and subtract it from all unlined
cost.

Module – 3: Assignment Problem
75 | P a g e

Now according to step – 2 we have each row and column must have at least one assignment
showing in the following table:

As per above table, we say that

,
,

And the minimum cost/time units.
Ex – 3: A computer centre has four expert programmers and needs to develop four
application programs. The head of the computer centre, estimates the computer time (in
minutes) required by the respective experts to develop the application programs as
follows:
Programmers
Programs
A B C D
1 120 100 80 90
2 80 90 110 70
3 110 140 120 100
4 90 90 80 90
Find the assignment pattern that minimizes the time required to develop the application
programs.

A 21 0 1
B 0 1 0
C 2 0 0

Module – 3: Assignment Problem
76 | P a g e

Solution: Let us subtract the minimum element of each row from every element of that
row. Note that the minimum element in the first row is 80. So 80 is to be subtracted from
every element of the first row, i.e., from 120, 100, 80 and 90, respectively. As a result, the
elements of the first row of the resulting matrix would be 40, 20, 0, and 10 respectively.
Similarly, we obtain the elements of the other rows of the resulting matrix. Thus, the
resulting matrix is:
A B C D
1 40 20 0 10
2 10 20 40 0
3 10 40 20 0
4 10 10 0 10

Let us now subtract the minimum element of each column from every element of that
column in the resulting matrix. The minimum element in the first column is 10. So 10 is to
be subtracted from every element of the first column, i.e., from 40, 10, 10, and 10,
respectively.
As a result, the elements of the first column of the resulting matrix are 30, 0, 0, 0,
respectively. Similarly, we obtain the elements of the other columns of the resulting matrix.
Thus, the resulting matrix is:
A B C D
1 30 10 0 10
2 0 10 40 0
3 0 30 20 0
4 0 0 0 10

Now, starting from first row onward, we draw a rectangle around the 0 in each row having
a single zero and cross all other zeroes in the corresponding column. Here, in the very first
row we find a single zero. So, we draw a rectangle around it and cross all other zeroes in
the corresponding column. We get

Module – 3: Assignment Problem
77 | P a g e

In the second, third and fourth row, there is no single zero. Hence, we move column-wise.
In the second column, we have a single zero. Hence, we draw a rectangle around it and
cross all other zeroes in the corresponding row. We get

In the matrix above, there is no row or column, which has a single zero. Therefore, we first
move row-wise to locate the row having more than one zero. The second row has two
zeroes. So, we draw a rectangle arbitrarily around one of these zeroes and cross the other
one. Let us draw a rectangle around the zero in the cell (2, A) and cross the zero in the cell
(2, D). We cross out the other zeroes in the first column. Note that we could just as well
have selected the zero in the cell (2, D), drawn a rectangle around it and crossed all other
zeroes. This would have led to an alternative solution. In this way, we are left with only one
zero in every row and column around which a rectangle has been drawn.
This means that we have assigned only one operation to one operator. Thus, we get the
optimum solution as follows:
A B C D
1 30 10 0 10
2 0 10 40 0
3 0 30 20 0
4 0 0 0 10

Note that the assignment of jobs should be made on the basis of the cells corresponding to
the zeroes around which rectangles have been drawn.
Therefore, the optimum solution for this problem is: 1  C, 2  A, 3  D, 4  B

Module – 3: Assignment Problem
78 | P a g e

This means that programmer 1 is assigned program C, programmer 2 is assigned program
A, and so on.
The minimum time taken in developing the program is = 80 + 80 + 100 + 90 = 350 min.
Ex – 4: A company is producing a single product and selling it through five agencies
situated in different cities. All of a sudden, there is a demand for the product in five more
cities that do not have any agency of the company. The company is faced with the problem
of deciding on how to assign the existing agencies to dispatch the product to the additional
cities in such a way that the travelling distance is minimized. The distances (in km)
between the surplus and deficit cities are given in the following distance matrix
Deficit
City

Surplus
City
I II III IV V
A 160 130 175 190 200
B 135 120 130 160 175
C 140 110 155 170 185
D 50 50 80 80 110
E 55 35 70 80 105
Determine the optimum assignment schedule.
Solution: Subtracting the minimum element of each row from every element of that row,
we have

I II III IV V
A 30 0 45 60 70
B 15 0 10 40 55
C 30 0 45 60 75
D 0 0 30 30 60
E 20 0 35 45 70
Subtracting the minimum element of each column from every element of that column, we
have

Module – 3: Assignment Problem
79 | P a g e

I II III IV V
A 30 0 35 30 15
B 15 0 0 10 0
C 30 0 35 30 20
D 0 0 20 0 5
E 20 0 25 15 15

We now assign zeroes by drawing rectangles around them as explained in Example 1. Thus,
we get

I II III IV V
A 30 0 35 30 15
B 15 0 0 10 0
C 30 0 35 30 20
D 0 0 20 0 5
E 20 0 25 15 15

Since the number of assignments is less than the number of rows (or columns), we proceed
from Step 5 onwards of the Hungarian method as follows:
 We tick mark (  ) the rows in which the assignment has not been made. These are
the 3rd and 5th rows.
 We tick mark (  ) the columns which have zeroes in the marked rows. This is the
2nd column.

 We tick mark (  ) the rows which have assignments in marked columns. This is the
1st row.
 Again we tick mark (  ) the column(s) which have zeroes in the newly marked row.
This is the 2nd column, which has already been marked. There is no other such
column. So, we have

Module – 3: Assignment Problem
80 | P a g e

I II III IV V
A
30
0 35 30 15 
B 15 0 0 10 0
C 30 0 35 30 20 
D 0 0 20 0 5
E 20 0 25 15 15 

We draw straight lines through unmarked rows and marked columns as follows:

I
II
III IV V
A
30
0 35 30 15 
B 15 0 0 10 0
C 30 0 35 30 20 
D 0 0 20 0 5
E 20 0 25 15 15 


We proceed as follows, as explained in step 6 of the Hungarian method:
i) We find the smallest element in the matrix not covered by any of the lines. It is
15 in this case.

Module – 3: Assignment Problem
81 | P a g e

ii) We subtract the number ‘15’ from all the uncovered elements and add it to the
elements at the intersection of the two lines.
iii) Other elements covered by the lines remain unchanged.
Thus, we have

We repeat Steps 1 to 4 of the Hungarian method and obtain the following matrix:

Since each row and each column of this matrix has one and only one assigned 0, we obtain
the optimum assignment schedule as follows: A  V, B  III, C  II, D  I, E  IV Thus,
the minimum distance is 200 + 130 + 110 + 50 + 80 = 570 km.

Module – 3: Assignment Problem
82 | P a g e

3.4 Exercise
1. Find the optimal assignment schedule of the following cost matrix.
Marketing
Executive
N E W S
A 14 20 11 19
B 12 10 15 9
C 16 19 18 15
D 17 13 15 14

2. Solve the assignment problem represented by the following effective matrix.
a b c d e f
A 9 22 58 11 19 27
B 43 78 72 50 63 48
C 41 28 91 37 45 33
D 74 42 27 49 39 32
E 36 11 57 22 25 18
F 3 56 53 31 17 28

83 | P a g e

Replacement problems involve items that degenerate with use or with the passage of time
and those that fail after a certain amount of use or time. Items that deteriorate are likely to
be large and costly (e.g., machine tools, trucks, ships, and home appliances). Non
deteriorating items tend to be small and relatively inexpensive (e.g., light bulbs, vacuum
tubes, ink cartridges). The longer a deteriorating item is operated the more maintenance it
requires to maintain efficiency. Furthermore, the longer such an item is kept the less is its
resale value and the more likely it is to be made obsolete by new equipment. If the item is
replaced frequently, however, investment costs increase. Thus the problem is to determine
when to replace such items and how much maintenance (particularly preventive) to
perform so that the sum of the operating, maintenance, and investment costs is minimized.
In the case of non deteriorating items the problem involves determining whether to replace
them as a group or to replace individuals as they fail. Though group replacement is
wasteful, labor cost of replacements is greater when done singly; for example, the light
bulbs in a large subway system may be replaced in groups to save labor. Replacement
problems that involve minimizing the costs of items, failures, and the replacement labor are
solvable either by numerical analysis or simulation.
The “items” involved in replacement problems may be people. If so, maintenance can be
interpreted as training or improvements in salary, status, or fringe benefits. Failure can be
interpreted as departure and investment as recruiting, hiring, and initial training costs.
There are many additional complexities in such cases; for example, the effect of one
person’s resigning or being promoted on the behavior of others. Such controllable aspects
of the environment as location of work and working hours can have a considerable effect
on productivity and failure rates. In problems of this type, the inputs of the behavioral
sciences are particularly useful.

4
Funda
menta
l of
Opera
tions
Resea
rch

Replacement Theory

Module – 4: Replacement Theory
84 | P a g e

4.1 Introduction
The replacement problems are concerned with the situations that arise when some items
such as men, machines, and electric-light bulbs, etc. need replacement due to their
decreased efficiency, failure or breakdown. Such decreased efficiency or complete
Breakdown may either be gradual or all of a sudden. The replacement problem arises
because of the following factors:

1. The old item has become in worse condition and work badly or requires expensive
maintenance.

2. The old item has failed due to accident or otherwise and does not work at alt, or the old
item is Expected to fail shortly.

3. A better or more efficient design of machine or equipment has become available in the
market.

In the case of items whose efficiency go on decreasing according to their age, it requires to
spend more money on account of increased operating cost, increased repair cost, increased
scrap, etc. So in such cases, the replacement of an old item with new one is the only
alternative to prevent such increased expenses. Thus the problem of replacement is to
decide best policy to determine an age at which the replacement is most economical
instead of continuing at increased cost. The need for replacement arises in many situations
so that different type of decisions may have to be taken.
For example,

i. We may decide whether to wait for complete failure of the item (which might cause
some loss), or to replace earlier at the expense of higher cost of the item.

ii. The expensive items may be considered individually to decide whether we should
replace now or, if not, when it should be reconsidered for replacement.

iii. It may be decided whether we should replace by the same type of item or by
different type (latest model) of item.

The problem of replacement is encountered in the case of both men and machines. Using
probability it is possible to estimate the chance of death (or failure) at various ages.

The main objective of replacement is to direct the organization or maximizing its profit (or
minimizing the cost).

Module – 4: Replacement Theory
85 | P a g e

4.2 Failure Mechanism of Items
The term ‘failure’ has a wider meaning in business than what it has in our daily life. There
are two kinds of failure.

1. Gradual Failure: The mechanism under this category is progressive. That is, as the life
of an item increases, its efficiency deteriorates, causing:

i. Increased expenditure for operating costs,

ii. decreased productivity of the equipments,

iii. Decrease in the value of the equipment, i.e., the resale of saving value decreases.

For example, mechanical items like pistons, bearings, rings etc. Another example is
Automobile tires.

2. Sudden Failure: This type of failure is applicable to those items that do not deteriorate
markedly with service but which ultimately fail after some period of using. The period
between installation and failure is not constant for any particular type of equipment but
will follow some frequency distribution, which may be progressive, retrogressive or
random in nature.

 Progressive failure: Under this mechanism, probability of failure increases with the
increase in the life of an item. For example, electric light bulbs, automobile tubes,
etc.

 Retrogressive failure: Certain items have more probability of failure in the
beginning of their life, and as the time passes the chances of failure become less.
That is, the ability of the unit to survive in the initial period of life increases its
expected life.

 Industrial equipments with this type of distribution of life span are exemplified by
aircraft engines.

 Random failure: Under this failure, constant probability of failure is associated with
items that fail from random causes such as physical shocks, not related to age.

 In such a case, virtually all items fail before aging has any effect. For example,
vacuum tubes in air-borne equipment have been shown to fail at a rate independent
of the age of the tube.

Module – 4: Replacement Theory
86 | P a g e

The replacement situations may be placed into four categories:

1. Replacement of capital equipment that becomes worse with time, e.g. machines
tools, buses in a transport organization, planes, etc.
2. Group replacement of items that fail completely, e.g., light bulbs, radio tubes, etc.
3. Problems of mortality and staffing.
4. Miscellaneous Problems.

4.3 Costs to be considered
In general, the costs to be included in considering replacement decisions are all those costs
that depend upon the choice or age of machine. In some special problems, certain costs
need not be included in the calculations. For example, in considering the optimum decision
of replacement for a particular machine, the costs that do not change with the age of the
machine need not be considered.

4.4 When The Replacement Is Justified?
This question can easily be answered by considering a case of truck owner whose problem
is to find the ‘best’ time at which he should replace the old truck by new one. The truck
owner wants to transport goods as cheaply as possible. The associated costs are:

(i) The running costs, and
(ii) The capital costs of purchasing a truck.

These associated costs can be expressed as average cost per month. Now the truck owner
will observe that the average monthly cost will go on decreasing, longer the replacement is
postponed.

However, there will come an age at which the rate of increase of running costs more than
compensates the saving in average capital costs. Thus, at this age the replacement is
justified.

4.5 Replacement model
Replacement model is used in the decision making process replacing the used asset or
equipment with a substitute mostly the new asset or equipment is best for uses this is the
meaning of replacement.

Module – 4: Replacement Theory
87 | P a g e

Why we need to replace an asset?
The reason is the asset value or the efficiency of asset is gradually decreases with the
passage of time at the same time the maintenance cost of the asset is gradually increasing.

Efficiency Maintenance cost

At some period of time the Maintenance cost for the asset is very high then it is necessary
to replace the asset by new one but it is require finding a right time means period of time
when the asset is resale in the market that is called Optimum replacement period.
4.6 Replacement policy
If the running and maintenance cost of the asset or machine for the next year is more than
the average annual cost of selected year then replace at the end of the selected year.
1. Replacement of items that deteriorate
Whose maintenance costs increase with time; ignoring changes in the value of money
during the period.
2. Replacement of items whose maintenance costs increase with time and value
of the money also changes with time.

3. Group replacement model

Ex-1: The cost of a machine is Rs. 10500 and its scrap value (Resale value) is Rs.500. The
maintenance costs found from experience are as follows:
Year 1 2 3 4 5 6 7 8
Maintenance
cost (Rs.)
300 500 700 1000 1400 1900 2400 3000
When should the machine be replaced?
Solution:

Module – 4: Replacement Theory
88 | P a g e

1 2 3 4 5 6 7
Years
of
Service
Resale
value
Depreciatio
n cost
[Purchase
price –
Resale
value]
[10500-500]
Annual
mainten
ance
cost
Cumulative of
maintenance
cost
Total
cost
[(3)+(5)
]
Average
Annual
cost
1 500 10000 300 300 10300
10300/1
= 10300

2 500 10000 500 800 10800
10800/2
= 5400

3 500 10000 700 1500 11500
11500/3
= 3833

4 500 10000 1000 2500 12500
12500/4
= 3125

5 500 10000 1400 3900 13900
13900/5
= 2780

6 500 10000 1900 5800 15800
15800/6
= 2633.3

7 500 10000 2400 8200 18200
18200/7
= 2600

8 500 10000 3000 11200 21200
21200/8
= 2650
Find minimum cost from the Average Annual cost that opposite year will be final optimum
year for resale the asset or replace it by new one.
Here it is observed that the maintenance cost in the 8
th
year becomes greater than the
average cost for 7 years. Hence the machine should be replaced at the end of 7
th
year.
Alternatively, last column of above table shows that the average cost starts increasing in
the 8
th
year, so the machine should be replaced before the beginning of 8
th
year, i.e. at the
end of 7
th
year.

Module – 4: Replacement Theory
89 | P a g e

Ex – 2: The cost of a machine is Rs.6100 and its scrap value is only Rs. 100. The
maintenance costs are found experience to be:
Year 1 2 3 4 5 6 7 8
Maintenance cost in
Rs.
100 250 400 600 900 1250 1600 2000
When should machine be replaced?
Solution:

1 2 3 4 5 6 7
Years
of
Service
Resale
value
Depreciation
cost
[Purchase
price –
Resale value]
[6100-100]
Annual
mainten
ance
cost
Cumulative
of
maintenanc
e cost
Total
cost
[(3)+(5)]
Average
Annual cost
1 100 6000 100 100 6100

2 100 6000 250 350 6350

3 100 6000 400 750 6750

4 100 6000 600 1350 7350

5 100 6000 900 2250 8250

6 100 6000 1250 3500 9500

7 100 6000 1600 5100 11100

8 100 6000 2000 7100 13100

Here it is observed that the maintenance cost in the 7
th
year becomes greater than the
average cost for 6 years. Hence the machine should be replaced at the end of 6
th
year.

Module – 4: Replacement Theory
90 | P a g e

Alternatively, last column of above table shows that the average cost starts increasing in
the 7
th
year, so the machine should be replaced before the beginning of 7
th
year, i.e. at the
end of 6
th
year.

Ex - 3: A new automobile vehicle costs Rs. 10000 and it can be sold at the end of any year
with the selling price as shown. The operating and maintenance cost table. Find when the
automobile vehicle needs to be replacing because of wear and tear.
Year 1 2 3 4 5 6
Scrap value 7000 5000 3000 2000 1000 500
Maintenance
cost
1000 1600 1800 2500 3000 3500
Solution:

1 2 3 4 5 6 7
Year
Resale/
Scrap
value
Depreciation
cost
[Purchase
price –
Resale value]
[10000-scrap
value]
Annual
mainten
ance
cost
Cumulative
of
maintenanc
e cost
Total
cost
[(3)+(5)
]
Average
Annual cost
1 7000 3000 1000 1000 4000

2 5000 5000 1600 2600 7600

3 3000 7000 1800 4400 11400

4 2000 8000 2500 6900 14900

5 1000 9000 3000 9900 18900

6 500 9500 3500 13400 22900

Here it is observed that the maintenance cost in the 5
th
year becomes greater than the
average cost for 4
th
year. Hence the vehicle should be replaced at the end of 4
th
year.
Alternatively, last column of above table shows that the average cost starts increasing in
the 5
th
year, so the vehicle should be replaced before the beginning of 5
th
year, i.e. at the
end of 4
th
year.

Module – 4: Replacement Theory
91 | P a g e

Ex – 4: Following failure rates have been observed for certain type of light bulbs
Month 1 2 3 4 5
Percentage/
probability of
bulbs failing
by end of
month
10 25 50 80 100
There are total 1000 bulbs in use and it cost Rs. 10 to replace an individual bulb which has
fused out. If all bulbs are replaced simultaneously. It would cost Rs 4. Per bulb. Two
polices are being considered for replacement of bulbs; first replace all bulbs simultaneously
at fixed interval whether fails or not and do individual replacement in immediate periods
secondly individual replacement of bulbs as and when it fails. Determine the optimum
policy for replacement of bulbs based above failure data and costs.
Solution:
Here we are work on both policies individual and group replacement in which those are
having minimum cost for replacement and then we are follow that policy.

PART – I: For individual replacement
Here probability of failure is given and that is always a cumulative probability so first we
calculate probability of failure for each month.

Step – 1: Find probability of failure for each month

Probability of bulbs fails during 1
st
month

Probability of bulbs fails during 2
nd
month

Probability of bulbs fails during 3
rd
month

Probability of bulbs fails during 4
th
month

Probability of bulbs fails during 5
th
month

Step – 2: Find average life of the bulb

Where indicate number of month and
indicates the total number of months.

Module – 4: Replacement Theory
92 | P a g e

Step – 3: Find average number of failure (fail bulbs) per month

Step – 4: Find average cost of individual replacement per month

PART – II: For group replacement
Here given that total number of bulbs used

Step – 1: Calculate number of failure during each month
Number of bulbs fails during 1
st
month

Module – 4: Replacement Theory
93 | P a g e

Number of bulbs fails during 2
nd
month

Number of bulbs fails during 3
rd
month

Number of bulbs fails during 4
th
month

Number of bulbs fails during 5
th
month

Step – 2: Calculate cost for group replacement

And

Module – 4: Replacement Theory
94 | P a g e

Month (n) Total Cost (C )
Average Cost

1
1000(4)+100(10)
=5000

2
1000(4)+[100+160](10)
=6600

3
1000(4)+[100+160+281](10)
=9410

4
1000(4)+[100+160+281+377](10)
=13180

5
1000(4)+[100+160+281+377+350](10)
=16680

According to above tabular data it is clear that after 3
rd
month the average cost would be
increase therefore it is required to replace bulbs in a group at end of the 3
rd
month of
starting of 4
th
month because at that time duration the average cost is minimum like

So the average cost of group replacement is
Now compare both the polices together
Average cost for individual replacement
Average cost for group replacement after 3 months.
So it is advisable to follow the group replacement policy for replacing the bulbs.

Module – 4: Replacement Theory
95 | P a g e

Ex – 5: A milk plant is considering replacement of a machine whose cost price is Rs. 12,200
and the scrap value Rs. 200. The running (maintenance and operating) costs in Rs. are
found from experience to be as follows:
Year: 1 2 3 4 5 6 7 8
Running Cost: 200 500 800 1200 1800 2500 3200 4000
When should the machine be replaced?

Solution: The computations can be summarized in the following tabular form
(In Rupees)
Year

(1)
Running
Cost

(2)
Cumulative
Running
Cost

(3)
Depreciation
Cost

(4)
Total Cost
TC
(5) = (3) + (4)
Average
Cost

(6) = (5)/(1)
1 200 200 12000 12200 12200
2 500 700 12000 12700 6350
3 800 1500 12000 13500 4500
4 1200 2700 12000 14700 3675
5 1800 4500 12000 16500 3300
6 2500 7000 12000 19000 3167
7 3200 10200 12000 22200 3171
8 4000 14200 12000 26200 3275

From the table it is noted that the average total cost per year, A(n) is minimum in the
6
th
year (Rs. 3167). Also the average cost in 7
th
year (Rs.3171) is more than the cost in
6
th
year. Hence the machine should be replaced after every 6 years.
Ex – 6: A Machine owner finds from his past records that the maintenance costs per year of
a machine whose purchase price is Rs. 8000 are as given below:
Year: 1 2 3 4 5 6 7 8
Maintenance Cost: 1000 1300 1700 2200 2900 3800 4800 6000
Resale Price: 4000 2000 1200 600 500 400 400 400
Determine at which time it is profitable to replace the machine.
Solution:
C = Rs. 8000. Table 13.2 shows the average cost per year during the life of machine.
Here, the computations can be summarized in the following tabular form:

Module – 4: Replacement Theory
96 | P a g e

Year
f(t)
Cumulative
maintenance
cost
Scrap
value

Total cost

1 1000 1000 4000 5000 5000
2 1300 2300 2000 8300 4150
3 1700 4000 1200 10800 3600
4 2200 6200 600 13600 3400
5 2900 9100 500 16600

6 3800 12900 400 20500 3417
7 4800 17700 400 25300 3614
8 6000 23700 400 31300 3913

The above table shows that the value of TA during fifth year is Minimum and hence the
machine should be replaced after every fifth year.

Ex – 7: The cost of a machine is Rs. 6100 and its scrap value is only Rs.100. The
maintenance costs are found to be
Year: 1 2 3 4 5 6 7 8
Maintenance Cost (in Rs.): 100 250 400 600 900 1250 1600 2000
When should the Machine be replaced?

Solution: Here we have

The computations can be summarized in the following tabular form:

Module – 4: Replacement Theory
97 | P a g e

Replace
at the
end of
year

Cumulative
maintenance
cost

Total cost

1 100 100 6100 6100
2 250 350 6350 3175
3 400 750 6750 2250
4 600 1350 7350 1737.50
5 900 2250 8250 1650
6 1250 3500 9500 1583.33
7 1600 5100 11100 1585.7
8 2000 7100 13100 1637.50

It is now observed that the machine should be replaced at the end of sixth year otherwise
the average cost per year will start to increase.
4.7 Replacement of items whose maintenance cost increases with time
and the money value changes at a constant rate
To understand this let us define the following terms:
Money Value
Since money has a value over time, therefore the explanation of the statement: Money is
worth 10% per year can be given in two ways:

(a) In one way, spending Rs.100 today would be equivalent to spend Rs.110 in years
time. In other words if we plan to spend Rs.110 after a year from now, we could
spend Rs.100 today and an investment which would be worth Rs.110 next year.
(b) Alternatively if we borrow Rs.100 at the interest of 10% per year and spend
Rs.100 today, we have to pay Rs.100 after one year (next year).

Thus, we conclude that Rs.100 is equal to Rs.110 a year from now. Consequently Rs. 1 from
a year now is equal to

rupee today.

Module – 4: Replacement Theory
98 | P a g e

Present Worth Factor
As we have seen, a rupee a year from now will be equivalent to

rupee today at
the discount rate of 10% per year. So, one rupee in n years from now will be equal
to

. Therefore, the quantity

is called the Present Worth Factor (PWF)
or Present Value (PV) of one rupee spent in n years from now. In general, if r is the rate of
interest, then

is called PWF or PV of one rupee spent in n years from now
onwards. The expression

is known as compound amount factor of one rupee
spent in n years.

Discount Rate
Let r be the rate of interest. Therefore present worth factor of unit amount to be spent after
one year is

.

Then v is known as the discount rate. The optimum replacement policy for replacement of
item where maintenance costs increase with time and money value changes with constant
rate can be determined by following method:

Suppose that the item (which may be machine or equipment) is available for use over a
series of time periods of equal intervals (say one year).

Let
Purchase price of the item to be replaced

Running (or maintenance) cost in the

year
Rate of interest

is the present worth of a rupee to be spent in a year hence.

Let the item be replaced at the end of every n
th
year. The year wise present worth of
expenditure on the item in the successive cycles of n years can be calculated as follows:
Year 1 2---- n n+1 n+2 ---- 2n 2n+1
Present
worth
C+R1 R2v Rnv
n-1
(C+R1)v
n
R2v
n+1

Rnv
2n-1
(C+R1)v
2n

Module – 4: Replacement Theory
99 | P a g e

Assuming that machines has no resale value at the time of replacement, the present worth
of the machine in n years will be given by

And

As a result of these two inequalities, rules for minimizing costs may be stated as follows:
1. Do not replace if the operating cost of next period is less than the weighted average
of previous costs.
2. Replace if the operating cost of the next period is greater than the weighted average
of the previous costs.
Working Procedure
The step-by-step procedure for solving the problem is stated as under:
 Write in a column the running/maintenance costs of machine or equipment for
different year
.
 In the next column write the discount factor indicating the present value of a rupee
received after years

 The two column values are multiplied to get present value of the maintenance costs,
i.e.,

 These discounted maintenance costs are then cumulated to the

year to
get

 The cost of machine or equipment is added to the values obtained in Step 4 above to
obtain

 The discount factors are then cumulated to get

 The total costs obtained in (Step 5) are divided by the corresponding value of the
accumulated discount factor for each of the years.
 Now compare the column of maintenance costs which is constantly increasing with
the last column. Replace the machine in the latest year that the last column exceeds
the column of maintenance costs.

Module – 4: Replacement Theory
100 | P a g e

Ex – 8: A milk plant is offered an equipment A which is priced at Rs.60,000 and the costs of
operation and maintenance are estimated to be Rs.10,000 for each of the first 5 years,
increasing every year by Rs. 3000 per year in the sixth and subsequent years. If money
carries the rate of interest 10% per annum what would the optimal replacement period?
From the above table we find the weighted cost is minimum at the end of 8
th
year, hence
the equipment should be replaced at the end of 8
th
year.
Ex – 9: A Manufacturer is offered two machines A and B. Machine A is priced at Rs. 5000
and running cost is estimated at Rs. 800 for each of the first five years, increasing by Rs.
200 per year in the sixth and subsequent years. Machine B, with the same capacity as A,
costs Rs. 2500, but has running cost of Rs. 1200 per year for six years, thereafter increasing
by Rs. 200 per year. If money is worth 10% per year, which machine should be purchased?
(Assume that the machines will eventually be sold for scrap at a negligible price).
Solution
Since money is worth 10% per year, therefore discount rate is

Module – 4: Replacement Theory
101 | P a g e

From above table we conclude that for machine A 1600 < 1752.043 < 1800. Since the
running cost of 9
th
year is 1600and that of 10
th
year is 1800 and 1800 > 1752.043, it would
be economical to replace machine A at the end of nine years.

Module – 4: Replacement Theory
102 | P a g e

In above table we find that 1800 < 1689 < 2300 so it is better to replace the machine B after
8
th
year. The equivalent yearly average discounted value of future costs is Rs. 1748.60 for
machine A and it is 1680.23 for machine B. Hence, it is more economical to buy machine B
rather than machine A.
Example 3.1: The cost of a machine is Rs. 6100 and its scrap value is only Rs. 100. The
maintenance costs are found from experience to be:

When should machine be replaced?
Solution: First, we find an average cost per year during the life of the machine as follows:
Total cost in first year = maintenance cost in the year + loss in purchase price
= 100 + (6100 − 100) = Rs. 6100.
Therefore, the average cost in the first year = Rs. 6100.
Total cost up to two years = maintenance cost up to two year + loss in purchase price
= (100 + 250) + 6000 = Rs. 6350.
Therefore, average cost in first two years = Rs. 3175.
In a similar fashion, average cost per year during first three years = 6750/3 = Rs. 2250.
Average cost per year during first four years 7350/4 = Rs.1837.50.
Average cost per year during first five years 8250/5 = Rs. 1650.
Average cost per year during first six years

Average cost per year during first seven years

The computations are summarized in the following table:

Module – 4: Replacement Theory
103 | P a g e

Here it is observed that the maintenance cost in the

year becomes greater than the
average cost for 6 years [i.e.

]. Hence the machine should be replaced at the end of
the 6th year. Alternatively, last column of the above table shows that the average cost starts
increasing in the

year. So the machine should be replaced before the beginning of the

year, i.e., at the end of the

year.
4.8 Exercise
1. A milk plant is offered an equipment A which is priced at Rs.70,000 and the costs of
operation and maintenance are estimated to be Rs.10,000 for each of the first 6 years,
increasing every year by Rs. 4000 per year in the sixth and subsequent years. If money
carries the rate of interest 10% per annum what would the optimal replacement period?
2. A Manufacturer is offered two machines A and B. Machine A is priced at Rs. 6000 and
running cost is estimated at Rs. 900 for each of the first five years, increasing by Rs. 300 per
year in the sixth and subsequent years. Machine B, with the same capacity as A, costs Rs.
3500, but has running cost of Rs. 2200 per year for six years, thereafter increasing by Rs.
300 per year. If money is worth 10% per year, which machine should be purchased?
(Assume that the machines will eventually be sold for scrap at a negligible price).

104 | P a g e

A network may be defined by a set of points, or “nodes,” that are connected by lines, or
“links.” A way of going from one node (the “origin”) to another (the “destination”) is called
a “route” or “path.” Links, which may be one-way or two-way, are usually characterized by
the time, cost, or distance required to traverse them. The time or cost of traveling in
different directions on the same link may differ.
A network routing problem consists of finding an optimum route between two or more
nodes in relation to total time, cost, or distance. Various constraints may exist, such as a
prohibition on returning to a node already visited or a stipulation of passing through every
node only once.
Network routing problems commonly arise in communication and transportation systems.
Delays that occur at the nodes (e.g., railroad classification yards or telephone
switchboards) may be a function of the loads placed on them and their capacities.
Breakdowns may occur in either links or nodes. Much studied is the “traveling salesman
problem,” which consists of starting a route from a designated node that goes through each
node (e.g., city) only once and returns to the origin in the least time, cost, or distance. This
problem arises in selecting an order for processing a set of production jobs when the cost
of setting up each job depends on which job has preceded it. In this case the jobs can be
thought of as nodes, each of which is connected to all of the others, with setup costs as
the analogue of distances between them. The order that yields the least total setup cost is
therefore equivalent to a solution to the traveling salesman problem. The complexity of the
calculations is such that even with the use of computers it is very costly to handle more
than 20 nodes. Less costly approximating procedures are available, however. More typical
routing problems involve getting from one place to another in the least time, cost, or
distance. Both graphic and analytic procedures are available for finding such routes.

5
Funda
menta
l of
Opera
tions
Resea
rch

Network Analysis

Module – 5: Network Analysis
105 | P a g e

5.1 Introduction
The techniques of operations research used for planning, scheduling and controlling large
and complex projects are often referred as network analysis. All these techniques are based
on representation of the project as a network of activities.
A network is a graphical plan consisting of a certain configuration of arrows and nodes for
showing the logical sequence of various activities to be performed to achieve project
objectives.
PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method) are two
of the well known techniques belong to the family of network analysis.
The Program Evaluation and Review Technique (PERT) was developed in 1956-58 by a
research team to help in the planning and scheduling of the US Navy’s Polaris Missile
project which involved thousands of activities. The objective of the team was to efficiently
plan and produce the Polaris missile system. Since 1958, this technique was proved to be
useful for all jobs or projects which have an element of uncertainty in the matter of
estimation of duration, as is the case with new types of projects the like of which have
never been taken up before.
At the same time but independently, Critical Path Method (CPM) was developed by E. I.
DuPont company along with Remington Rand Corporation. The aim behind its
development was to provide a technique for control of the maintenance of company’s
chemical plants. In course of time, use of CPM got extended to the field of cost and resource
allocation.
5.2 Phases of CPM and PERT
Project management by CPM and PERT can be based on the following three phases.
1. Planning
 In this phase, the whole project is broken down into smaller projects and
further into activities.
 The time estimates for these activities are then determined.
 Network diagram is constructed.
 Study the network diagram in detail and incorporate any modification at the
initial or execution stage.

Module – 5: Network Analysis
106 | P a g e

2. Scheduling
 Scheduling phase involves time related activities.
 A time chart is constructed showing the start and finish times of each activity.
 The chart also shows or relates one activity to other activities of the project.
 Identify non critical activities and show the amount of slack or float times.
This is very essential to take the advantages of delay in execution of activities
or using limited available resources.

3. Control
 Controlling includes careful supervision of progress of the project with the
help of network diagram and time chart.
 Continuously analyze and update all activities involved and if necessary
reschedule the project for the remaining portion of the project.
5.3 Some important definitions
(1) Activity: It represents some action and is a time consuming effort necessary to
complete a particular part of overall project.
(2) Event: Beginning and end points of an activity are called events or nodes.
(3) Critical activity: An activity is said to be critical if any delay in its start further delays
the completion of the whole work.
(4) Amount of Slack or Float time: The difference between the earliest time and the latest
time is called as activity slack.
(5) Total amount of slack or total float time: Total slack is the difference of latest finish
time and the duration.
(6) Free slack or free float time: Free slack is the amount of time a job can be delayed
without affecting the early start of any other job.
(7) Independent slack: Independent slack

where
the amount
of latest finish time of a job is and
is the amount of earlier start of a job.

Module – 5: Network Analysis
107 | P a g e

5.4 Project management or representation by a network diagram
Network diagram is the graphical representation of logically and sequentially connected
arrows and node, representing activities and events respectively in a project.

Figure 1: Events and activity
Now observe the following figure and indicates event represented by the nodes in
which node known as tail and is known as head moreover the symbol means an arrow
in between and indicates an activity.

Figure 2: Network diagram
5.5 Types of activities
(1) Preceding activity: Activity that must be accomplished before a given event can occur.
(2) Succeeding activity: Activity that cannot be accomplished until an event has occurred.
(3) Concurrent activity: Activity taking place at same time or in the same location.
(4) Dummy activity: Activity which neither consumes time nor resources but is used
simply to represent a connection or a link between the events is known as dummies. It is
shown in network by a dotted line.

A
Arrow Node

Module – 5: Network Analysis
108 | P a g e

In above mentioned figure 2, A is a preceding activity of B, B is a preceding activity of C, D is
a preceding activity of E and E is a preceding activity of F.
Similarly B is a succeeding activity of A, C is a succeeding activity of B, E is a succeeding
activity of C and F is a succeeding activity of E.
Moreover the activities A and D arise from even 1 at same time of same location therefore A
and D are becomes concurrent activities.
Now for understanding the dummy activity observe the following figure 3,

Figure 3: Network diagram and dummy activity
Here according to the rule of network theory, there is only one starting point and one
ending point. But in above mentioned figure 3, we observe that there are two ending
points’ node 4 and node 5. So it is necessary to add a dummy activity between node 3 and
node 4 because after that procedure event 4 is not an end of the network.
Therefore the activity E in figure 3 is called dummy activity and it is denoted by a dotted
line.
5.6 Types of events
(1) Merge event: An event is said to be Merge event if two or more than two activities are
end at the same node (event).

In above figure an event is Merge event.

Module – 5: Network Analysis
109 | P a g e

(2) Burst event: An event is said to be Burst event if it is a starting point of two or more
than two activities.

In above figure an event is Burst event.

5.7 Common Errors
(1) Looping (Cycling): Drawing an endless loop in a network is known as error of looping.

In above figure double arrow for activity create an endless loop in between the events 2,
3 and 4.
(2) Dangling: To disconnect an activity before the complication of all activities called error
of dangling.

In above figure an activity is disconnected before completion of remaining all activities.
(3) Redundancy: Unnecessarily inserting the dummy activity in a network diagram is
known as error of redundancy.

Module – 5: Network Analysis
110 | P a g e

In above figure an activity is a dummy activity which is unnecessary because there is a
path between events 2 to 4 is already exists. Therefore it creates an error namely
redundancy.
5.8 Rules of network construction
 Try to avoid the arrow the cross each other.
 Use straight arrow.
 No event can occur until every activity preceding it has been completed.
 An event can’t occur twice.
 Dummies should be introduced only if it is extremely necessary.
 Network has only one entry point called start event and one end point (emergence).
 Use arrow left to right. Avoid mixing two directions.
5.9 Numbering the events
 Number must be unique.
 Number should be carried out on a sequential basis from left to right and top to
bottom.
 Initial event must be numbered as 1.
 Number of all new starts events 2, 3 and so on.
5.10 Time analysis
Some important notations
(1)

Estimate completion time of activity
(2)
Earliest starting time of activity
(3)
Earliest finishing time of activity
(4)
Latest starting time of activity
(5)
Latest finishing time of activity

Module – 5: Network Analysis
111 | P a g e

Forward pass computation (Left to Right)
 Zero is the starting time for the project.




Backward pass computation (Right to Left)
For ending event assume




5.11 Determination of Floats and Slack times
(1) Float: It is defined as the difference between the latest and earliest activity time. There
are three types of floats.
(a) Total Float

Where
Earliest time for tail event

Latest time for tail event

Normal time for activity .
(b) Free Float

Where
Earliest time for tail event

Normal time for activity .
(c) Independent Float

Where
Earliest time for tail event

Latest time for tail event

Module – 5: Network Analysis
112 | P a g e

Normal time for activity .
(2) Slack: It is defined as the difference between latest and earliest event time.
5.12 Critical activity and Critical path
An activity (i, j) is said to be critical, if it has total float
.
A path throughout the network is said to be critical if it satisfies the following three
conditions.
1.

2.

3.

Where
Earliest starting time of initial event.

Latest finishing time of initial event.

Earliest starting time of final event.

Latest finishing time of final event.
Ex-1: Construct a network for a project whose activities and precedence relationships are
as given below:
Activity A B C D E F G H I J K
Predecessor - - - A B B C D E H,I F,G

Solution:

G

A
B
C
D
E

F
H
I

J

Module – 5: Network Analysis
113 | P a g e

Ex – 2: Draw a network for a house construction project. The sequence of activities with
their predecessors is given in table below.

Name of
the activity
Starting
and
finishing
event
Description of
activity
Predecessor
Time
duration
(days)
A (1, 2)
Prepare The
house plan
-- 4
B (2, 3)
Construct the
house
A 58
C (3, 4)
Fix the
door/windows
B 2
D (3, 5)
Wiring the
house
B 2
E (4, 6) Paint the house C 1
F (5, 6)
Polish the
doors/windows
D 1

Solution:

2
1
4
5
6
7
9
A
B
C
D
E
3
F
H
I
8
J
G
2
2
1
1 A B
C
D
E
F
1 2 3
4
6
5
4 58

Module – 5: Network Analysis
114 | P a g e

Ex – 3: A project schedule has the following properties. According to that
(i) Construct a network
(ii) Compute the earliest event time and latest event time.
(iii) Determine the critical path and total project duration.
(iv) Compute total and free float for each activity.
Activity 1-2 1-3 2-4 3-4
Time(days) 4 1 1 1

Solution:
(i) Network diagram

(ii) Compute the earliest event time and latest event time

1
2
3
4
4
1
1
1
Latest event time
Earliest event time
1
2
3
4
4
1
1
1
0
0
4
4
4
1
5
5

Module – 5: Network Analysis
115 | P a g e

Activity
Normal
time

Earliest Latest
Total
Float
Free
Float
Independent
Float

Start
(ES)
Finishing
(EF)
Start
(LS)
Finish
(LF)
TF FF IF

1-2 4 0 4 0 4 0 0 0 4 0
1-3 1 0 1 3 4 3 0 0 1 0
2-4 1 4 5 4 5 0 0 0 5 4
3-4 1 1 2 4 5 3 3 0 5 4

The critical path: 1 – 2 – 4
Total project duration = 4+1 = 5 days

1
2
3
4
4
1
1
1
0
0
4
4
4
1
5
5

Module – 5: Network Analysis
116 | P a g e

Ex – 4: Determine the early start and late start in respect of all node points and identify
critical path for the following network

Solution: Calculation of E and L for each node is shown in the network

Module – 5: Network Analysis
117 | P a g e

From the table, the critical nodes are (1, 2), (2, 5), (5, 7), (5, 8), (7, 10) and (8, 10). From the
table, there are two possible critical paths
i. 1 → 2 → 5 → 8 → 10
ii. 1 → 2 → 5 → 7 → 10
Ex – 5: Find the critical path and calculate the slack time for the following network

Module – 5: Network Analysis
118 | P a g e

Solution: The earliest time and the latest time are obtained below

From the above table, the critical nodes are the activities (1, 3), (3, 5) and (5, 9)

The critical path is 1 → 3 → 5 → 9.

Module – 5: Network Analysis
119 | P a g e

Ex – 6: A project has the following times schedule

Construct the network and compute
1.
and
for each event
2. Float for each activity
3. Critical path and its duration
Solution: The network is

Event No. 1 2 3 4 5 6 7 8 9 10

0 4 1 5 7 11 15 17 18 25

0 12 1 13 7 16 15 17 18 25

Module – 5: Network Analysis
120 | P a g e

Float =
(Head event) –
(Tail event) – Duration

The resultant network shows the critical path

The two critical paths are (i) 1 → 3 → 5 →7 → 8 → 9 →10 (ii) 1 → 3 → 5 → 7 → 8 →10

Module – 5: Network Analysis
121 | P a g e

5.13 Project Evaluation and Review Technique (PERT)
The main objective in the analysis through PERT is to find out the completion for a
particular event within specified date. The PERT approach takes into account the
uncertainties. The three time values are associated with each activity
1. Optimistic time: It is the shortest possible time in which the activity can be finished. It
assumes that everything goes very well. This is denoted by
.
2. Most likely time: It is the estimate of the normal time the activity would take. This
assumes normal delays. If a graph is plotted in the time of completion and the frequency of
completion in that time period, then most likely time will represent the highest frequency
of occurrence. This is denoted by
.
3. Pessimistic time: It represents the longest time the activity could take if everything
goes wrong. As in optimistic estimate, this value may be such that only one in hundred or
one in twenty will take time longer than this value. This is denoted by
.
In PERT calculation, all values are used to obtain the percent expected value.
4. Expected time: It is the average time an activity will take if it were to be repeated on
large number of times and is based on the assumption that the activity time follows Beta
distribution, this is given by

5. The variance for the activity is given by

–

Ex – 7: For the project

Module – 5: Network Analysis
122 | P a g e

Task A B C D E F G H I J K
Least time 4 5 8 2 4 6 8 5 3 5 6
Greatest time 8 10 12 7 10 15 16 9 7 11 13

Find the earliest and latest expected time to each event and also critical path in the
network.
Solution:

Module – 5: Network Analysis
123 | P a g e

The network is

The critical path is A →C →E → H → K.

Ex – 8: A project has the following characteristics

Construct a PERT network. Find the critical path and variance for each event.

Module – 5: Network Analysis
124 | P a g e

Solution:

The network is constructed as shown below

The critical path: 1 → 2 → 4 → 6 → 7 →9 →10.

Module – 5: Network Analysis
125 | P a g e

Ex – 9: Calculate the variance and the expected time for each activity

Solution:

Module – 5: Network Analysis
126 | P a g e

Ex – 10: A project is represented by the network as shown below and has the following
data

Determine the following
1. Expected task time and their variance
2. Earliest and latest time
Solution: (1)

Task A B C D E F G H I
Least time 5 18 26 16 15 6 7 7 3
Greatest time 10 22 40 20 25 12 12 9 5
Most likely time 15 20 33 18 20 9 10 8 4

Module – 5: Network Analysis
127 | P a g e

(2) Earliest time

(3) Latest time

–

–

–

–

– –

– –
5.14 Exercise
1. What is PERT? 2. For the following data, draw network. Find the critical path, slack time
after calculating the earliest expected time and the latest allowable time

Module – 5: Network Analysis
128 | P a g e

[Ans. Critical path: 1 → 3 → 7 → 10 → 12 →13]
2. A project schedule has the following characteristics

Construct a PERT network and find out
a. The earliest possible time
b. Latest allowable time
c. Slack values
d. Critical path
3. Explain the following terms
a. optimistic time
b. Most likely time
c. Pessimistic time
d. Expected time
e. Variance

128 | P a g e

Discussions on the mathematics of games began long before the rise of modern,
mathematical game theory. Cardano wrote on games of chance in Liber de ludo aleae (Book
on Games of Chance), written around 1564 but published posthumously in 1663. In the
1650s, Pascal and Huygens developed the concept of expectation on reasoning about the
structure of games of chance, and Huygens published his gambling calculus in De ratiociniis
in ludo aleæ (On Reasoning in Games of Chance) in 1657.
In 1713, a letter attributed to Charles Waldegrave analyzed a game called "le Her". He was
an active Jacobite and uncle to James Waldegrave, a British diplomat. In this letter,
Waldegrave provides a minimax mixed strategy solution to a two-person version of the
card game le Her, and the problem is now known as Waldegrave problem. In his
1838 Recherches sur les principes mathématiques de la théorie des richesses (Researches
into the Mathematical Principles of the Theory of Wealth ), Antoine Augustin
Cournot considered a duopoly and presents a solution that is the Nash equilibrium of the
game.
In 1913, Ernst Zermelo published Über eine Anwendung der Mengenlehre auf die Theorie
des Schachspiels (On an Application of Set Theory to the Theory of the Game of Chess),
which proved that the optimal chess strategy is strictly determined. This paved the way for
more general theorems. In 1938, the Danish mathematical economist Frederik
Zeuthen proved that the mathematical model had a winning strategy by using Brouwer's
fixed point theorem.
In his 1938 book Applications aux Jeux de Hasard and earlier notes, Émile Borel proved a
minimax theorem for two-person zero-sum matrix games only when the pay-off matrix was
symmetric and provides a solution to a non-trivial infinite game (known in English
as Blotto game). Borel conjectured the non-existence of mixed-strategy equilibria in finite
two-person zero-sum games, a conjecture that was proved false by von Neumann. Game
theory did not really exist as a unique field until John von Neumann published the paper On
the Theory of Games of Strategy in 1928.

6
Funda
menta
l of
Opera
tions
Resea
rch

Game Theory

Module – 6: Game Theory
129 | P a g e

6.1 Introduction
The Theory of Games was born suddenly in 1944 with the publication of Theory of Games
and Economic Behavior by John von Neumann and Oskar Morgenstern. Their choice of title
was a little unfortunate, since it quickly got shortened to “Game Theory” with the
implication being that the domain of applications consists merely of parlour games.
Nothing could be further from the truth. In fact, the authors hoped that their theory might
form the basis of decision making in all situations where multiple decision makers can
affect an outcome, a large class of situations that includes warfare and economics.
In the years since 1944, the only part of Game Theory where a notion of “solution” has
been developed that is powerful enough to discourage further theoretical work is the part
where there are exactly two players whose interests are in complete opposition. Game
theorists refer to these games as two-person zero sum (TPZS) games.
TPZS games include all parlour games and sports where there are two people involved, as
well as several where more than two people are involved. Tic-tac-toe, chess, cribbage,
backgammon, and tennis are examples of the former. Bridge is an example of the latter;
there are four people involved, but only two players (sides). Team sports are also examples
of the latter. Many of these games were originally conceived in imitation of or as surrogates
for military conflict, so it should come as no surprise that many military problems can also
be analyzed as TPZS games.
Parlour games that are not TPZS are those where the players cannot be clearly separated
into two sides. Examples are poker and Monopoly (when played by more than two people).
Most real economic “games” are not TPZS because there are too many players, and also
because the interests of the players are not completely opposed. Such non-TPZS games are
the object of continued interest in the literature, but will not be mentioned further in these
notes. We will confine ourselves entirely to TPZS games. Washburn (1994) contains a more
in-depth treatment of TPZS games. Luce and Raiffa (1957) is a dated but still worthwhile
introduction to the general subject, or see Owen (1995) or Winston (1994).
Game theory is a type of decision theory in which one’s choice of action is determined after
taking into account all possible alternatives available to an opponent playing the same
game, rather than just by the possibilities of several outcome results.
Game theory does not insist on how a game should be played but tells the procedure and
principles by which action should be selected. Thus it is a decision theory useful in
competitive situations. Game is defined as an activity between two or more persons
according to a set of rules at the end of which each person receives some benefit or suffers

Module – 6: Game Theory
130 | P a g e

loss. The set of rules defines the game. Going through the set of rules once by the
participants defines a play.
6.2 Properties of Game
1. There are finite numbers of competitors called ‘players’
2. Each player has a finite number of possible courses of action called ‘strategies’
3. All the strategies and their effects are known to the players but player does not know
which strategy is to be chosen.
4. A game is played when each player chooses one of his strategies. The strategies are
assumed to be made simultaneously with an outcome such that no player knows his
opponents strategy until he decides his own strategy.
5. The game is a combination of the strategies and in certain units which determines the
gain or loss.
6. The figures shown as the outcomes of strategies in a matrix form are called ‘pay-off
matrix’.
7. The player playing the game always tries to choose the best course of action which
results in optimal pay off called ‘optimal strategy’.
8. The expected pay off when all the players of the game follow their optimal strategies is
known as ‘value of the game’. The main objective of a problem of a game is to find the value
of the game.
6.3 Characteristics of Game Theory
Competitive game: A competitive situation is called a competitive game if it has the
following four properties
 There are finite number of competitors such that . In case , it is called a two
person game and in case , it is referred as n-person game.
 Each player has a list of finite number of possible activities.
 A play is said to occur when each player chooses one of his activities. The choices are
assumed to be made simultaneously i.e. no player knows the choice of the other until he
has decided on his own.

Module – 6: Game Theory
131 | P a g e

 Every combination of activities determines an outcome which results in a gain of
payments to each player, provided each player is playing uncompromisingly to get as much
as possible. Negative gain implies the loss of same amount.
Strategy: The strategy of a player is the predetermined rule by which player decides his
course of action from his own list during the game. The two types of strategy are
 Pure strategy
 Mixed strategy
Pure Strategy: If a player knows exactly what the other player is going to do, a
deterministic situation is obtained and objective function is to maximize the gain.
Therefore, the pure strategy is a decision rule always to select a particular course of action.
Mixed Strategy: If a player is guessing as to which activity is to be selected by the other on
any particular occasion, a probabilistic situation is obtained and objective function is to
maximize the expected gain. Thus the mixed strategy is a selection among pure strategies
with fixed probabilities.
Number of persons: A game is called ‘n’ person game if the number of persons playing is
‘n’. The person means an individual or a group aiming at a particular objective.
Two-person, zero-sum game: A game with only two players (player A and player B) is
called a ‘two-person, zero-sum game’, if the losses of one player are equivalent to the gains
of the other so that the sum of their net gains is zero.
Two-person, zero-sum games are also called rectangular games as these are usually
represented by a payoff matrix in a rectangular form.
Number of activities: The activities may be finite or infinite.
Payoff: The quantitative measure of satisfaction a person gets at the end of each play is
called a payoff.
Payoff matrix: Suppose the player A has ‘m’ activities and the player B has ‘n’ activities.
Then a payoff matrix can be formed by adopting the following rules
 Row designations for each matrix are the activities available to player A
 Column designations for each matrix are the activities available to player B
 Cell entry
is the payment to player A in A’s payoff matrix when A chooses the activity
and B chooses the activity .

Module – 6: Game Theory
132 | P a g e

 With a zero-sum, two-person game, the cell entry in the player B’s payoff matrix will be
negative of the corresponding cell entry
in the player A’s payoff matrix so that sum of
payoff matrices for player A and player B is ultimately zero.
Value of the game: Value of the game is the maximum guaranteed game to player A
(maximizing player) if both the players uses their best strategies. It is generally denoted by
‘V’ and it is unique.
6.4 Classification of Games
All games are classified into
 Pure strategy games
 Mixed strategy games Strategy
It is the pre-determined rule by which each player decides his course of action from his list
available to him. How one course of action is selected out of various courses available to
him is known as strategy of the game. Types of Strategy: Generally two types of strategy are
employed (i) Pure Strategy (ii) Mixed Strategy
(i) Pure Strategy: It is the predetermined course of action to be employed by the player.
The players knew it in advance. It is usually represented by a number with which the
course of action is associated.
(ii) Mixed Strategy: In mixed strategy the player decides his course of action in accordance
with some fixed probability distribution. Probability is associated with each course of
action and the selection is done as per these probabilities.
In mixed strategy the opponent cannot be sure of the course of action to be taken on any
particular occasion. Pure strategy games can be solved by saddle point method.
Decision of a Game: In Game theory, best strategy for each player is determined on the
basis of some rule. Since both the players are expected to be rational in their approach this
is known as the criteria of optimality.
Each player lists the possible outcomes from his action and selects the best action to
achieve his objectives. This criteria of optimality is expressed as Maximin for the
maximising player and Minimax for the minimising player.

Module – 6: Game Theory
133 | P a g e

6.5 The MaxiMin-MiniMax Principle
a) Maximin Criteria: The maximizing player lists his minimum gains from each strategy
and selects the strategy which gives the maximum out of these minimum gains.
b) Minimax Criteria : The minimising player lists his maximum loss from each strategy
and selects the strategy which gives him the minimum loss out of these maximum losses.
For Example: Consider a two person zero sum game involving the set of pure strategy for
Maximizing player A say

& A’s and for player B,
&
, with the following payoff

Player B
Row MaxMin

Player A

9 2 2

8 6

Maximin

6 4 4
Column MiniMax 9

Minimax
Since Maximin = Minimax
Suppose that player A starts the game knowing fully well that whatever strategy he adopts
B will select that particular counter strategy which will minimize the payoff to A.
If A selects the strategy
then B will select
so that A may get minimum gain. Similarly if
A chooses
than B will adopt the strategy of
. Naturally A would like to maximize his
maximin gain which is just the largest of row minima which is called 'maximin strategy'.
Similarly B will minimise his minimum loss which is called 'minimax strategy'. We observe
that in the above example, the maximum if row minima and minimum of column maxima
are equal. In symbols

The strategies followed by both the p1ayersarecalled ‘optimum strategy’.
Value of Game: In game theory, the concept value of game is considered as very
important. The value of game is the maximum guaranteed gain to the maximizing player if

Module – 6: Game Theory
134 | P a g e

both the players use their best strategy. It refers to the average payoff per play of the game
over a period of time. Consider the following the games.

Player Y Player Y
Player X

Player X

(With Positive Value) (With Negative Value)
In the first game player X wins 3 points and the value of the value are three with positive
sign and in the second game the player Y wins 3 points and the value of the game is -ve
which indicates that Y is the Winner. The value is denoted by 'v.
The different methods for solving a mixed strategy game are
• Analytical method
• Graphical method and
• Dominance rule
6. 6 Two-Person and Zero-Sum Game
Two-person zero-sum games may be deterministic or probabilistic. The deterministic
games will have saddle points and pure strategies exist in such games. In contrast, the
probabilistic games will have no saddle points and mixed strategies are taken with the help
of probabilities. Definition of saddle point A saddle point of a matrix is the position of such
an element in the payoff matrix, which is minimum in its row and the maximum in its
column.
Procedure to find the saddle point as follows:
 Select the minimum element of each row of the payoff matrix and mark them with circles.
 Select the maximum element of each column of the payoff matrix and mark them with
squares.
 If their appears an element in the payoff matrix with a circle and a square together then
that position is called saddle point and the element is the value of the game.
Solution of games with saddle point
To obtain a solution of a game with a saddle point, it is feasible to find out

Module – 6: Game Theory
135 | P a g e

 Best strategy for player A
 Best strategy for player B
 The value of the game the best strategies for player A and B will be those which
correspond to the row and column respectively through the saddle point.
Ex – 1: Solve the following payoff matrix

Player B
I II III IV V
Player A
I -2 0 0 5 3
II 3 2 1 2 2
III -4 -3 0 -2 6
IV 5 3 -4 2 -6
Solution:

Column MiniMax
Strategy Player A – II
Strategy Player B – III
Value of Game = 1

Module – 6: Game Theory
136 | P a g e

Ex – 2: Solve the following payoff Matrix

1 7 3 4

5 6 4 5

7 2 0 3
Solution:

Row MaxMin
MaxiMin Value

1 7 3 4 1

5 6 4 5 4

7 2 0 3 0
Column MiniMax
7 7 4 5

MiniMax Value

Strategy of player A

Strategy of player B

Value of the game
 Points to remember
 Saddle point mayor may not exist in a given game.
 There may be more than one saddle point then there will be more than one solution.
(Such situation is rare in the rea1life).
The value of game may be or .
The value of game may be zero which means 'fair game'.

II Games with Mixed Strategies
All game problems, where saddle point does not exist are taken as mixed strategy
problems. Where row minima are not equal to column maxima, then different methods are
used to solve the different types of problems. Both players will use different strategies with

Module – 6: Game Theory
137 | P a g e

certain probabilities to optimize. For the solution of games with mixed strategies, any of
the following methods can be applied.
1. ODDS METHOD (2x 2 games without saddle point)
2. Dominance Method.
3. Sub Games Method. – For (mx2) or (2xn) Matrices
4. Equal Gains Method.
5. Linear Programming Method-Graphic solution
These methods are explained one by one with examples, in detail.

1. ODDS Method - For 2 x 2 Games
Use of odds method is possible only in case of games with 2 x 2 matrix. Here it should be
ensured that the sum of column odds and row odds is equal.

Method of finding out odds
Step 1: Find out the difference in the value of in cell (1, 1) and the value in the cell (1, 2) of
the first row and place it in front of second row.

Step 2: Find out the difference in the value of cell (2, 1) and (2, 2) of the second row and
place it in front of first row.

Step 3: Find out the differences in the value of cell (1, 1) and (2, 1) of the first column and
place it below the second column.

Step 4: Similarly find the difference between the value of the cell (1, 2) and the value in cell
(2, 2) of the second column and place it below the first column.

The above odds or differences are taken as positive (ignoring the negative sign)

Strategy

ODDS

……

……

ODDS

The value of game is determined with the help of following equation.

Module – 6: Game Theory
138 | P a g e

Since the game does not have saddle point, the players will use mixed strategy. We apply
odds methods to solve the game.

Module – 6: Game Theory
139 | P a g e

2. Dominance Method. Dominance method is also applicable to pure strategy and mixed
strategy problem. In pure strategy the solution is obtained by itself while in mixed strategy
it can be used for simplifying the problem.

Principle of Dominance: The Principle of Dominance states that if the strategy of a player
dominates over the other strategy in all condition then the later strategy is ignored because
it will not affect the solution in any way. For the gainer point of view if a strategy gives
more gain than another strategy, then first strategy dominates over the other and the
second strategy can be ignored altogether. Similarly from loser point of view, if a strategy
involves lesser loss than other in all condition then second can be ignored. So
determination of superior or inferior strategy is based upon the objective of the player.
Since each player is to select his best strategy, the inferior strategies can be eliminated. In
other words, ineffective rows & column can be deleted from the game matrix and only
effective rows & columns of the matrix are retained in the reduced matrix.
For deleting the ineffective rows & columns the following general rules are to be followed.
(1) If all the elements of a row (say

row) of a pay off matrix are less than or equal
to the corresponding each element of the other row say

row then the
player A will never choose the

strategy OR

row is dominated by

row.
Then delete

row.

Module – 6: Game Theory
140 | P a g e

(2) If all the elements of a column (say

column are greater than or equal to the
corresponding elements of any other column (say

column) then

column is
dominated by

column. Then delete

column.

(3) A pure strategy of a player may also be dominated if it is inferior to some convex
combination of two or more pure strategies. As a particular case, if all the
elements of a column are greater than or equal to the average of two or more
other columns then this column is dominated by the group of columns. Similarly
if all the elements of row are less than or equal to the average of two or more
rows then this row is dominated by other group of row.

(4) By eliminating some of the dominated rows a columns and if the game is reduced
to 2 x 2 forms it can be easily solved by odds method.

Since there is no saddle point, so we apply dominance method. Here Row II dominates Row
II so we will delete Row II.
B
I II III
A
I 5 20 -10
III 20 15 18

Module – 6: Game Theory
141 | P a g e

Since column III dominates column I, we delete column I we get:
A
II III Odds
I 20 -10 3
II 15 18 30
Odds 28 5 33

Using the dominance property obtain the optimal strategies for both the players and
determine the value of the game. The pay off matrix for player A is given.

Since the questions desire to show the dominance property, that is why we are using it,
even if the question may have saddle point.
Since all elements in row IV are less than respective each element in Row III. Row III
dominates Row IV, Hence we delete Row IV & we get

Module – 6: Game Theory
142 | P a g e

Now all the elements of column I are less than or equal to respective each elements of
column IV, so we can delete column IV now we get

Repeating the above rules now each element of column I is than the respective elements of
column V, we can delete the column V and we get

Now as each element of Row I and Row II are less than the respective elements of III, we
can delete both Row I & II

Value of Game
Strategy for player A
Strategy for player B

Module – 6: Game Theory
143 | P a g e

6.7 Exercise

OPERATION RESEARCH FOR BEGINNERS.pdf

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

OPERATION RESEARCH FOR BEGINNERS.pdf

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77