Page 1
1 1
LINEAR PROGRAMMING
Unit Structure:
1.0 Objectives
1.1 Introduction
1.1.1 Introduction t o Linear Programming
1.1.2 Assumptions of Linear Programming Model
1.1.3 Advantages of Linear Programming
1.1.4 Limitations of Linear Programming
1.1.5 Requireme nts for a Linear Programming Problem
1.1.6 Applications of Linear Programming
1.1.7 Areas of Applications of Linear Programming
1.1.8 Structure of Linear Programming Problem
1.2 Formulation of Linear Programming Problem
1.2.1 Product Mix Problem
1.2.2Production Allocation Problem
1.2.3Inspection Problem
1.2.4 Production Planning Problem
1.2.5 Advertising Media Selection Problem
1.3 Graphical Method of Solution
1.4 Duality
1.5 Post Optimality Analysis and Sensitivity Analysis
1.6 Self Assessment Questi ons
1.0 OBJECTIVES
The learning objectives of Linear Programming are as follows:
1. To develop the skillsets of learners in formulating and solving LPP.
2. To formulate the linear programming problem by considering different
real life business const raints and learners can get solutions to LPP with
alternative courses of action. munotes.in
Page 2
2
Operation Research 1.1 INTRODUCTION
1.1.1 Introduction to Linear Programming Problem
The linear programming problems are the mathematical methods by which
scare or limited resources of the organiz ation are used effectively and
optimally so as to achieve the objective of the organization i.e. to earn and
to maximize the profit. The resources of the organization such as
manpower, money, method, material and machines are utilized effectively
as and wh en required by the management using linear programming
method. The linear programming problems act as optimization problems
involving maximization and minimization problem. The maximization
refers to the maximization of resources such as profit and sales w hereas
the minimization states to minimization of time and cost. These linear
programming techniques are widely used in the field of Product Mix
Problem Production Allocation Problem, Inspection Problem , Production
Planning Problem , Advertising Media Selec tion Problem , Blending
Problem , Investment Problem , Portfolio Selection problem , Capital
Budgeting Problem, Trim Loss Problem, War Strategy Problem,
Production Scheduling Problem and many other fields where
optimizations are required.
Linear Programming Pr oblem refers to a process of applying
mathematical technique to use the resources of organization effectively
and efficiently using optimization method .
1.1.2 Assumptions of Linear Programming Model
While developing the linear programming model, assumption s required to
be considered are as follows :
a. Certainty
b. Additivity
c. Linearity
d. Continuity or Divisibility
e. Proportionality
f. Limited Choices
Let us discuss each assumption of Linear Programming Model one by one
as follows :
a. Certainty
The certainty assumption states that the various elements of Linear
Programming Model such as objective function, various constraints of the
problem are arbitrary or constant and are determined using maximization
or minimization method to know their precise or deterministic value.
Hence the various factors of Linear Programming Model are precise,
deterministic and certain in values.
munotes.in
Page 3
3
Linear Programming
b. Additivity
The Additivity assumption states that the objective function for the given
values of decision variable as dependent variable is the sum of given many
independent variables and their correspondent addition will lead to the
maximization of variable or minimization of variable depending on the
nature of objective function.
The Additivity assumption also states that the constraint functions f or the
given values of decision variable as dependent variable is the either
greater than or equal to the sum of given many independent variables or
less than or equal to sum of given many independent variables and their
correspondent addition will lead to the search of values for the variables
say x and y or any other defined variable.
c. Linearity
The objective function and the defined constraint equations are assumed to
be linear so as to find out the values of variables leading to find out the
values o f assumed variables and their optimized value in the objective
function. The linear function states that there exists simultaneous equation
by which the unknown values can be found out.
d. Continuity or Divisibility
The Continuity assumption states that t he values of decision variables are
either positive values or zero values (non -negative values). The
Divisibility or continuity function states that the whole numbers can be
directly taken to solve linear programming problems whereas fractional
numbers are rounded off to the nearest numbers to use and solve linear
programming problems.
e. Proportionality
The Proportionality assumption states that the values of objective function
are in the multiple of assumed variables (say objective function z=3x+4y,
the objective function z is equal to the summation of thrice proportion of x
variable and fourth multiple (proportion) of y variable).
The Proportionality assumption also states that the values of constraint
functions are assumed to be linear and in the multi ple of assumed
variables (say constraint function 4x+5y ≥ 20, assuming linear function,
the constraint function 4x+5y is equal to 20 and the variables x and y are
in the multiples of 5 and 4 for x and y variables respectively .
f. Limited Choices
The lim ited choice assumption states the decision maker has no broad
choice, he has to select the alternative from all available alternatives only
which are limited in choice. The decision variables are finite and decision
maker has to consider the inter -related an d available conditions mentioned
in the linear programming problems as constraints including the non -
negativity constraint (representing the realistic conditions).
munotes.in
Page 4
4
Operation Research 1.1.3 Advantages of Linear Programming
The linear programming models or problems have sever al advantages in
the form of profit maximization, sales maximization, time minimization or
cost minimization and many more. The linear programming has following
advantages :
a. Optimum Utilization of Limited or Available Resources
b. Improvement in Efficiency and Productivity
c. Assistance for Decision Making
d. Objective oriented direction
e. Attainment of Feasible Solution to the Real Life Situation
f. Understanding the limitations of the project
g. Helps for Change Management
h. Profit and Sales Maximization
i. Time and Cost Minimi zation
Let us discuss the advantages of Linear programming problem in detail as
follows :
a. Optimum Utilization of Limited or Available Resources
The resources are limited in number that's why the decision maker has to
utilize these resources effici ently and effectively so that the management
will achieve the objective of Organization. The constraint represents the
conditions of limited resources and objective function is related to the
optimum utilization of all these resources to maximize the prof it or to
optimize the objective function.
b. Improvement in Efficiency and Productivity
The linear programming problem improve the efficiency and productivity
of available resources such as manpower Maine money method machine
material and 20 improveme nt in available resources will ultimately lead to
the improvement in efficiency and productivity of Manpower and that
leads to the attainment of organisational objective hence the linear
programming problem helps to improve the efficiency and productivity.
c. Assistance for Decision Making
The decision makers are confused for using scare resources. These
ambiguity can be cleared by using linear programming problems as the
optimum utilization of resources can be done with the help of this
technique hen ce decision makers are determine to use proper decision
making principles by using LPP method.
d. Objective oriented direction
The linear programming problems are supposed to achieve the objective
of organization that is to earn and to maximize the p rofit by utilizing
different constraints and achieving the objective function. Hence it
provides the direction to achieve the objective of organization by munotes.in
Page 5
5
Linear Programming
utilization of given real -life situations or conditions in LPP model or in
linear programming model.
e. Attainment of Feasible Solution to the Real Life Situation
The linear programming problem to attend the feasible solution to the real
life situation in organization it provides possible solution to the existing
problems. The appropriate solution t o different business conditions are
brought into reality with the help of linear programming problems. The
linear programming problems are solved to get different feasible solutions
and their output. The decision variables with the given conditions are
solved to get the feasible solution to the real -life problem of the corporate
world and hence the LPP models are considered as the best solution to
complex business situations.
g. Helps for Change Management
Linear programming problems help to understand the dynamism in the
system and co rresponding change management can be implemented with
the help of linear programming problems.
h. Profit and Sales Maximization
Objective function of linear programming problems helps to maximize the
profit as well as the sales of the organisation. The Optimisation technique
used here is maximization.
i. Time and Cost Minimization
The objective function of linear programming problem is to minimise the
time or duration of completion of the project as well as reduces the cost of
production of the project.
1.1.4 Limitations of Linear Programming:
Although there are many advantages of linear programming problems,
there are few limitations of linear programming. The limitations of linear
programming as follows :
a. Linearity
The relationship s among different variables are considered as linear
relationship but it may not be possible every time that the relationship
among variables of decision making Are linear. The linearity function in
business or in real life situat ion may or may not exist the assumption of
linearity function in the case of linear programming problems is a question
mark.
b. Integer value solutions:
The solution obtained for the linear programming problems in t erms of
objective function many may or ma y not be integer value functions. It
may be the whole number or fractional number. Thus every time, an
integer value s olution may not be possible. The optimal solution may not munotes.in
Page 6
6
Operation Research be appropriate if they reach rounding off to the nearest integer value. This
is one of the biggest limitations of linear programming problem.
c. Uncertainty:
The linear programming problem may not consider the change factors
such as internal change factors as well as external change factors. The
uncontrollable external factors may le ad to change the equation and the
optimal solution may be inappropriate. The uncertainty in different
variables of linear programming may lead to biased linear programming
solution.
d. Value of time:
The linear programming problem does not consider the va lue of time that
is the time for completion of the activity or the time required to consider
the conditions of linear programming problem. Schedule of linear
programming problem are unknown and undetermined that leads to to
fluctuate the solution of linear programming problems
e. Small problems:
The linear programming models are suitable for big problems of
multinational organizations w hereas small part of problems cannot be
solved cannot be fragmented by using linear programming problem
methods.
f. constan t parameters:
The linear programming problems have considered constant parameters of
decision variables but it is not possible every time that the parameter s are
constant. Hence, this is one of the limitations of linear programming
problem.
g. Single objec tive
The single objective is considered in a linear programming problem as
objective function. Th e multiple objectives of organiz ations are not
considered in the linear programming models full stop it is not possible to
attain multiple objectives of organi zation by using linear programming
model.
1.1.5 Requirements for a Linear Programming Problem
The requirements for a linear programming problem mean the need for a
linear programming problem in the business field. The basic objective of
management is to ac hieve the objective of organization that is to earn
profit by effective utilization of all available resources. The available
resources are men, material, money, method and machine. These
resources are limited in number. The use of these resources in the p roper
way is an essential part for the management. The optimum use of these
resources for the accomplishment of the objective of organization is done
by one of the methods called - linear programming problem. munotes.in
Page 7
7
Linear Programming
Therefore , there is a need of defining linear p rogramming problem and the
requirements for linear programming problem .
The conditions of linear programming problems and its requirements are
as follows :
a. well defined objective function
b. potential constraints
c. alternative course of action
d. interrelated variables
e. non negative be constraint
f. Limited supply
A. Well defined objective function
Linear programming problems should contain well defined objective
functions that highlight the objective of organization. The well -defined
objective function should be an optimization function leading to either
maximization or minimization case. The objective function is defined in a
mathematical equation starting with the letter Z equal to sum function.
B. Potential constraints
The potential constant refers to the c onditions or limitations for things that
have the capacity to achieve the objective of organisation and this
constants must be capable of being expressed as a linear function as either
greater than or less than are equal to as the variable may b e.
C. Alter native course of action:
Linear programming problems must consist of different alternatives called
alternative course of actions. For example a product may be processed on
three different machines and how much quantity of product can be
processed on what m achine that it is known through linear programming
problems.
D. Interrelated variables
The decision variables of linear programming problem are interrelated to
each other they are dependent on each other hence by using simultaneous
equation we can find out the value of solution of a linear programming
problem.
E. Non negative constraint
The decision variables of linear programming problem are non -negative
that is either Zero OR greater than zero and hence the non -negative the
constant indicates that the con stant are realistic in nature and that they
exist in real life situation. munotes.in
Page 8
8
Operation Research F. Limited supply
The resources may be having l imited supply that's why there is a
requirement of linear programming problem.
1.1.6 Applications of Linear Programming
Applications o f linear programming method are in the resource allocations
of Product Mix Problem, Production Allocation Problem; Inspection
Problem; Production Planning Problem; Advertising Media Selection
Problem; Blending Problem; Investment Problem; Portfolio Selecti on
problem and many other areas.
The linear programming problems are used in assembly line balancing,
make or buy decisions, Facilities location planning, agriculture resource
allocation problems, flight and train scheduling problems, dietary
problems, Env ironment protection problems, profit planning problems,
transportation problems, assignment problems, man power scheduling
cases, profit planning problems and many other areas of business field.
1.1.7 Areas of Applications of Linear Programming
Linear programmi ng problems have wide application in the fi eld of
industry, management and/or other fields. The areas of application of
linear programming problem are as follows :
a. Production scheduling problems
The production scheduling is done in order to match the deman d of the
product, inventory and manpower at minimum threshold level so as to
minimize the total cost of production and so as to keep the minimum
inventory.
b. Product mix problems
The product mix problem involves the mixture of different raw materials,
their ingredients and production capacity and the available resources. The
optimum allocation of resources such as men, machine, money, material,
method, and market can be properly executed with the help of linear
programing problems.
c. Assembly Line balancing P roblems
The high brand value products are not manufactured by a single company.
The multiple brands are involved in the production of different
components of that product. These parts are brought together and
assembled to form brand value product. For exa mple, The Reynolds
Automobile do not build whole car, the tires, seat covers, chromes and
other parts are manufactured by other companies and they are brought
together and assembled to form a new car. The decisions of assembly line
balancing are taken with the help of LPP models.
munotes.in
Page 9
9
Linear Programming
d. Make or buy decisions Problems
The make or buy decisions may be generally taken with a linear
programming problem as the given conditions are related to make or buy
decisions. When quantities to be manufactured are small in number, then
buy decision may be made and when quantities to be produced are larger
in number then make decision may be made. The quantities as a constraint
and other limitations of the company may decide to make or buy
decisions.
e. Transportation problems
Transpor tation problems involve transfer of goods or services from source
to destination. Transportation involves different constraints such as
quantity to be transferred, distance to be travelled, manufacturing capacity
of source, supply from the source and deman d of the destination, unit
transportation cost and other conditions. The combined constraints and
objectives of transportation can be achieved with the help of linear
programming problems.
f. Assignment problems
Assignment problem involves allocation of diffe rent facilities like
manpower or machines to different jobs. Proper allocations of different
facilities make timely arrangement to execute various jobs on different
machines or different jobs by different employees.
g. Portfolio selection problems
The invest ment banks or other non -banking financial services like Mutual
Fund associations and other share market brokers always face the problem
of portfolio selection. The linear programming problem assists to select a
portfolio based on minimum risk and maximum r eturn. Different
investment alternatives are provided and are selected based on given
constraints in LPP.
h. Agricultural problems
The allocation of different agricultural inputs such as water, labour,
fertilizers , pesticides and capital to different crops ar e properly combined
with the help of linear programming problems. The proper allocation of
Agricultural food in more agricultural output in the form of Agricultural
producers and hence the linear programming problems are greatly helpful
in the allocation o f Agricultural inputs.
1.1.8 Structure of Linear Programming Problem
Structure of linear programming model consists of three components.
1. Variables and their relationship
2. Objective function
3. Constraint. munotes.in
Page 10
10
Operation Research The components of linear programming models are described in detail as
follows :
1. Variables and their relationship
Variables are decision variables and they are under the control of the
decision maker. The relationships between the variables are generally
linear relationship and are solved using simultaneous solutions . All
decision variables are controllable, non -negative and continuous. They are
represented as x 1, x2,.....x n.
2. Objective function
Objective function is the objective of creating and solving linear
programming problems. Generally the objective function is represented in
the form of profit, sales, revenue, time and cost. Objective function is
represented in two forms that is either to maximize or to minimise with
the help of letter Z as
Z=c 1x1+c2x2+...+c nxn
Where,
Z is the objective function.
c1, c2,....c n are parameters of uncontrollable variable and
x1, x2,.....x n are parameters of controllable variable.
3. Constraints
Constraints are the limitations or given conditions described in linear
programming problems. They are the representations on the use of limited
resources. Constraint represents the mathematical equation where limited
resources can be used effectively so as to maximise the objective function.
1.2 FORMULATION OF LINEAR PROGRAMMING
PROBLEM :-
The linear programming problems are widely used in different sectors of
business, management and administration such as Product Mix Problem,
Production Allocation Problem; Inspection Problem, Production Planning
Problem; Advertising Media Selection Problem; Blending Problem;
Investment Problem; Portfolio S election problem and many other sectors.
1.2.1 Product Mix Problem
Example: A firm manufactures two items. It purchases castings which are
then machined, bored and polished. Castings for items A and B cost Rs 2
and 3 respectively and are sold at Rs 5 and 6 respectively. Running costs
of three machines are Rs. 20, Rs. 14 and Rs. 17.50 per hour respectively.
Capacities of the machine are
munotes.in
Page 11
11
Linear Programming
Part A Part B
Machining Capacity 25/hr 40/hr
Boring Capacity 28/hr 35/hr
Polishing Capacity 35/hr 25/hr
Formulate the Linear Programming model to determine the product mix
that maximises the profit.
Solution:
1. Variables under study:
As a firm manufactures two items A and B, let us consider x1 and X2 are
the number of units to be manufactured per hour.
2. Objective function:
Here, the objective function is to maximise the profit by utilising proper
product mix.
Determination of Profit for part A and part B
Particulars Formula Part A (Rs.) Part B (Rs.)
Machining Cost = Running cost /
Capacity per hr 20/25= 0.8 20/40=0.5
Boring Cost = Running cost /
Capacity per hr 14/28=0.5 14/35=0.4
Polishing cost = Running cost /
Capacity per hr 17.5/35= 0.5 17.5/25=0.7
Total Assembling
Cost = Machining cost+
Boring Cost+
Polishing Cost 0.8+0.5+0.5=
1.8 0.5+0.4+0.7= 1.6
Casting cost Given 2 3
Total cost =Total assembling
cost+ Casting cost 1.8+2= 3.8 1.6+3 = 4.6
Selling Price Given 5 6
Profit Selling Price - Total
cost 5-3.8= 1.2 6-4.6=1.4
3. Constraints
Constraints are the conditions mentioned on the capacities o f machines.
Running machines for one hour requires following conditions
munotes.in
Page 12
12
Operation Research Machine Constraint : (1/25) x 1+(1/40) x 2 ≤ 1.
8x1+5x 2 ≤ 200.
Boring Constraint : (1/28) x 1+(1/35) x 2 ≤ 1.
5x1+4x 2 ≤ 140.
Polishing constraint : (1/28) x 1+(1/35) x 2 ≤ 1.
5x1+4x 2 ≤ 140.
Non-negativity constraint :x1 ≥ 0; x 2 ≥ 0
1.2.2 Production Allocation Problem
Example : A firm produces three products. These products are processed
on three different machines. The time required to manufacture one unit of
each of the three products and the daily capacity of the three machines are
given in the table below:
Machine Time per unit (minutes) Machine capacity
(minutes/day)
Product 1 Product 2 Product 3
M1 2 3 2 440
M2 4 - 3 470
M3 2 5 - 430
Solution:
1. Variables unde r study:
As a firm produces three products and are processed on three different
machines , let us consider x 1, x2 and x 3 are the number of units to be
manufactured daily for products 1, 2 and 3 respectively.
2. Objective function:
Here, the objective functi on is to maximise the profit.
The objective function Z= 4x 1+3x 2+6x 3 is to maximize.
3. Constraints
Constraints are the conditions mentioned on the capacities of machines.
Machine M 1 Constraint : 2x1+3x 2+2x3≤ 440.
Machine M 2 Constraint : 4x1+0x 2+3x3≤ 470 . munotes.in
Page 13
13
Linear Programming
Machine M 3 constraint : 2x1+5x 2+0x3≤ 430.
Non-negativity constraint : x1 ≥ 0; x 2 ≥ 0 and x 3 ≥ 0
1.2.3 Inspection Problem
Example: A company has two grades of inspectors I and II to undertake
quality control inspection. At least, 1500 pieces must be i nspected in an 8
hour day. Grade I inspector can check 20 pieces in an hour with an
accuracy of 96%. Grade II inspector checks 14 pieces an hour with an
accuracy of 92%.
Wages of grade I inspector are Rs. 5 per hour while those of grade II
inspector are Rs . 4 per hour. Any error made by an inspector costs Rs. 3 to
the company, find the optimal assignment of inspectors that minimizes the
daily inspection cost.
Solution:
1. Variables under study:
As a company has two grades of inspectors I and II and are assign ed
grades to undertake quality control inspection. Let us consider x 1, and x 2
are the number of grades of inspectors I and II that are assigned the job of
quality control inspection respectively.
2. Objective function:
Here, the objective function is to mi nimize the daily cost of inspection.
The daily cost of inspection includes two costs namely wages paid to the
inspectors and cost of inspection.
The cost of grade I inspection per hour is = Rs. (5+3x0.04x20) = Rs. 7.4
The cost of grade II inspection per hour is = Rs. (4+3x0.08x14) = Rs. 7.36
The objective function Z= 8 (7.4x 1+7.36x 2) is to maximize.
3. Constraints
Constraints are the conditions mentioned on the grades of inspections.
Grade I Constraint : x1 ≤ 10.
Grade I Constraint : x2 ≤ 15.
Inspect ion constraint : 20(8x 1)+14 (8x 2) ≤ 1500.
Non-negativity constraint : x1 ≥ 0; and x 2 ≥ 0
1.2.4 Production Planning Problem
A factory manufactures a product each unit of which consists of 5 units of
part A and 4 units of part B. The two parts A and B re quire different raw
materials of which 120 units and 240 units respectively are available. munotes.in
Page 14
14
Operation Research These parts can be manufactured by three different methods. Raw material
requirements per production run and the number of units for each part
produced are given bel ow.
Method Input per run (units) Output per run
(units)
Raw material
1 Raw material
2 Part A Part B
1 7 5 6 4
2 4 7 5 8
3 2 9 7 3
Formulate the Linear Programming Problem model to determine the
number of production runs for each method so as to maxi mize the total
number of complete units of the final product.
Solution:
1. Variables under study:
Let us consider x 1, x2 and x 3 are the number of production runs for each
method 1, 2 and 3 respectively.
2. Objective function:
Here, the objective function is to maximize total units of the final product.
The total units of part A produced by different machines are 6x 1+5x 2+7x 3
and The total units of part B produced by different machines are
4x1+8x 2+3x 3 .
A factory manufactures a product each unit of which consi sts of 5 units of
part A and 4 units of part B. Hence upper limit of production cannot go
beyond ( 6x1+5x 2+7x 3)/5 and (4x 1+8x 2+3x 3)/4.
The objective function Z= Mimimum of (6x 1+5x 2+7x 3)/5 and
(4x 1+8x 2+3x 3)/4).
This equatio n may violates the norms of LPP . We may convert this non -
linear function to linear function by considering the following equation
Let y= Min ((6x 1+5x 2+7x 3)/5 and (4x 1+8x 2+3x 3)/4))
It implies that
(6x 1+5x 2+7x 3)/5 ≥ y and (4x1+8x 2+3x 3)/4) ≥ y.
6x1+5x 2+7x 3 ≥ 5y 4x1+8x 2+3x 3≥ 4y
6x1+5x 2+7x 3 -5y ≥ 0 4x1+8x 2+3x 3-4y≥0
Hence the objective function is to maximize Z =y munotes.in
Page 15
15
Linear Programming
3. Constraints
Constraints are the conditions mentioned.
Raw Material 1 Constraint : 7x1+4x 2+2x3≤ 120.
Raw Material 2 Constraint : 5x1+7x2+9x3≤ 240
Output Part A Constraint : 6x1+5x2+7x3-5y ≥0
Output Part B Constraint : 4x1+8x2+3x3-4y ≥0
Non-negativity constraint : x1; x2; x3, y ≥ 0;
1.2.5 Advertising Media Selection Problem
An advertising company wishes to plan its advertising strategy in 3
different media - television, radio and magazines. The purpose of
advertising is to reach as large a number of potential customers as
possible. Following data have been obtained from market survey:
Television Radio Magazine I Magazine II
Cost of an advertising
unit Rs. 30,000 Rs.
20,000 Rs.15,000 Rs. 10,000
No. of potential
customers reached
per unit 2,00,000 6,00,000 1,50,000 1,00,000
No. of female
customers reached
per unit 1,50,000 4,00,000 70,000 50,000
The Company wants to spend no more than Rs.4,50,000 on advertising.
Following are the further requirements that must be met:
i. at least 1 million exposures take place among female customers.
ii. advertising on magazines be limited to Rs. 1,50,000.
iii. a tleast 3 advertising units to be brought on magazine 1& 2 units on
magazine II,
iv. the number of advertising units on television and radio should each be
between 5 and 10.
Formulate an L.P. model for the problem.
Solution:
1. Variables under study:
As an advertising company wishes to plan its advertising strategy in 3
different media - television, radio and magazines, Let us consider x 1, x2, x3
and x 4 are the number of advertising units to be brought on tel evision,
radio, magazine I and magazine II respectiv ely.
munotes.in
Page 16
16
Operation Research 2. Objective function:
Here, the objective function is to maximize the total number of potential
customers reached.
The objective function Z= 10,00,000 (2x 1+6x2+1.5x3+x4) is to maximize.
3. Constraints
Constraints are the conditions mentioned as foll ows.
Advertising Budget Constraint :
30,000x 1+20,000x 2+15,000x 3+10,000x 4 ≤ 4,50,000.
i.e. 30x 1+20x 2+15x 3+10x 4 ≤ 450
Number of female customers reached by advertising campaign Constraint
1,50,000x 1+4,00,000x 2+70,000x 3+50,000x 4 ≥10,00,000.
i.e. 15x 1+40x 2+7x 3+5x 4 ≤ 100.
Expenses on magazine advertising constraint
15,000x 3+10,000x 4 ≥1,50,000.
i.e. 15x 3+10x 4 ≤ 150.
No. of units on magazines constraints
x3≥ 3
x4≥ 2.
No. of units on television constraints
5≤x1≤10
No. of units on radio constraints
5≤x2≤10
Non-negativity constraint : x1, x2, x3, x4 ≥ 0
1.3 GRAPHICAL METHOD OF SOLUTION
The graphical method of solution is used to solve the problems of linear
programming module . The detail steps can be understood through the
numerical as follows
Numerical 1. Use the graphical method of solution for the following linear
programming problem. Maximize Z= 2x 1+x2subject to the constraints
munotes.in
Page 17
17
Linear Programming
i.) x1+2x 2≤ 10 ii.) x1+x2≤ 6 iii.) x1-x2≤ 2 iv.) x1-2x2≤ 1
and x1, x2 ≥ 0.
Solution:
1. At first we convert the first constraint equa tion x 1+2x 2 ≤ 10 into
x1+2x 2=10.
Now put x 2=0 and calculate the value of x1as x 1=10
Point (x, y) = (10, 0).
Now put x 1 =0 and calculate the value of x2 as x 2=5
Point (x, y) = (0, 5).
2. Now, we convert the second constraint equation x 1+x2 ≤ 6 into
x1+x2=6.
Now put x 2=0 and calculate the value of x1as x 1=6
Point (x, y) = (6, 0).
Now put x 1 =0 and calculate the value of x2 as x 2=6
Point (x, y) = (0, 6).
3. Now, we convert the third constraint equation x 1-x2 ≤ 2into
x1-x2=2.
Now put x 2=0 and calculate the val ue of x1as x 1=2
Point (x, y) = (2, 0).
Now put x 1 =0 and calculate the value of x2 as x 2= -2
Point (x, y) = (0, -2).
x1-2x2≤ 1
4. Now, we convert the third constraint equation x 1-x2 ≤ 2 into
x1-2x2= 1.
Now put x 2=0 and calculate the value of x1as x 1=2
Point (x, y) = (2, 0).
Now put x 1 =0 and calculate the value of x2 as x 2= -1/2
Point (x, y) = (0, -1/2).
Now using graphical points as follows munotes.in
Page 18
18
Operation Research
Source: Operations Research Book by J.K. Sharma
The point B is at the junction of two lines x1-x2= 2 and x1-2x2= 1
The coordinates of the junction point of intersecting lines can be obtained
by solving the equation of two lines intersecting each other using
simultaneous equation as follows
x1-x2= 2
-x1+2x2 = -1
As x2= 1 and putting the value of x2= 1 in above equation , we get x 1 as 3.
Point B (x,y)= B (3,1).
The point D is at the junction of two lines x1+2x 2= 10 and . x1+x2= 6
The coordinates of the junction point of intersecting lines can be obtained
by solving the equation of two lines intersecting each other using
simultaneous equation as follows
x1+2x 2= 10
-x1-x2= -6
As x2= 4 and putting the value of x2= 4 in above equation, we get x 1 as 2.
Point D (x, y)= B (2,4).
Now as all equations are either less than or equal to some value, the
feasible region lies below t hat all lines. Hence the solution of existing LPP
lies in that feasible region.
munotes.in
Page 19
19
Linear Programming
Let us check all extreme values of feasible region as follows
Extreme point Coordinates Value (Objective
function)
0 (0,0) 2(0)+1(0)=0
A (1,0) 2(1)+1(0)=2
B (3,1) 2(3)+1(1)= 7
C (4,2) 2(4)+1(2)=10
D (2,4) 2(2)+1(4)=8
E (0,5) 2(0)+1(5)=5
The maximum value of objective function lies at point C(4,2) as 10 and
hence the optimal solution to the given LPP is : x1=4 and x2=2 and Max
Z=10.
1.4 DUALITY
There is a set of unique li near programming problem for every linear
programming problem. The other linear programming problem includes
same data reflecting program and is called as dual Program. The dual
program is obtained by transposing the rows and columns of linear
programming problem. Dual variables are also called as shadow prices of
various sources. Solution for dual program also exist just like that of
original linear programming problem. Solutions of Primal program and
dual program are very closely related to each other.
The features of duality in linear program is as follows
1. If the original linear programming problem has many rows and few
columns then the calculation can be complex one. At that time,
solution of linear programming problem can be obtained by
converting rows and columns.
2. The duality in linear programming give the additional information as
changes in options can change the optimal solution of linear
programming problem. This change in coefficient leading to change
in the s olution of linear programming problem is reflex sensitivity
analysis or post optimality analysis.
3. Generally , the duality in linear programming evaluates on different
economic nature and hence, it helps to evaluate opportunity cost for
different alternative s available to the solution and their relative
values.
4. The accuracy of primal solution can be checked with the help of
duality in linear programming,
5. The duality in linear programming is just same that of zero Sum game
in Game Theory. munotes.in
Page 20
20
Operation Research 1.5 POST OPTIMALITY A NALYSIS AND SENSITIVITY
ANALYSIS
The change in the values of variables of linear programming problem
leads to changes in the optimal solution of a linear programming problem.
The sensitivity analysis is a study of sensitivity of optimal solution of
linear programming problem by studying the discrete variation in the
variables of linear programming problem.
The sensitivity can be measured from zero value to the corresponding
value as per the corresponding changes in the optimal solution of linear
programmi ng. We first calculate the solution of Original linear
programming problem and we consider the changes in the constraints of
linear programming problem leading to the changes in the solution of
linear programming problem. The variation can be noted and com pared
with orig inal linear programming problem. The process of studying the
sensitivity of optimal solution of linear programming problem is also
called as post optimality analysis because it is done after an optimal
solution.
The changes in one of the fol lowing parameters of original linear
programming problem can make sensitivity analysis and alter the solution
of linear programming problem as :
1. Changes in the objective function
2. Change in the value of constraints.
3. Changing the value of availability of res ources.
4. Change in the consumption of resources.
5. Addition of new variable.
6. Addition of new constraints to the original linear programming
problem
1.6 SELF ASSESSMENT QUESTIONS
Q1. Answer Multiple Choice Questions
1. The linear programming problems are the … …..by which scare or
limited resources of the organization are used effectively and
optimally so as to achieve the objective of the organization i.e. to
earn and to maximize the profit.
a. mathematical methods
b. statistical methods
c. quantitative methods
d. nume rical methods
munotes.in
Page 21
21
Linear Programming
2. ………refers to a process of applying mathematical technique to
use the resources of organization effectively and efficiently using
optimization method.
a. Game Theory
b. Linear Programming Problem
c. Assignment Problem
d. Transportation Problem.
3. Assu mptions of Linear Programming Model do not include …
a. Linearity
b. Continuity or Divisibility
c. Proportionality
d. Unlimited Choices .
4. The linear programming has following advantages
a. Optimum Utilization of Limited or Available Resources
b. Improvement in Efficiency and Productivity
c. Assistance for Decision Making
d. All of these
5. ….. states that the values of decision variables are either positive
values or zero values (non -negative values).
a. Continuity assumption
b. Proportionality assumption
c. Both a and b
d. None of the above
6. The …….states that the values of objective function are in the
multiple of assumed variables
a. Continuity assumption
b. Proportionality assumption
c. Both a and b
d. None of the above
Answers: 1: a 2:b 3:d
4:d 5:a 6:b munotes.in
Page 22
22
Operation Research Q2. Write short notes o n:
a. Assumptions of Linear Programming Model
b. Advantages of Linear Programming
c. Limitations of Linear Programming
d. Requirements for a Linear Programming Problem
e. Applications of Linear Programming
f. Areas of Applications of Linear Programming
g. Structure of Linear P rogramming Problem
h. Duality
i. Post Optimality Analysis
j. Sensitivity Analysis
munotes.in
Page 23
23 2
TRANSPORTATION
Unit Structure:
2.0 Objectives
2.1 Introduction
2.2 Matrix Terminology
2.3 Solution of Transportation model
2.4 Methods of Obtaining an Initial Feasible Solution
2.4.1 North West Corner Method
2.4.2 Row Minima Method
2.4.3 Column Minima Me thod
2.4.4 Least Cost Method
2.4.5 Vogels’ Approximation Method.
2.5 Self Assessment Test
2.0 OBJECTIVES
The learning objectives of transportation are as follows :
1. To understand different concepts and terminologies used in the
transportation problem.
2. To comprehend transportation model and to develop solution to the
transport ation model.
3. To develop logical thinking and analytical solutions to the
transportation problem.
4. To use different methods of solving transportation model and to
minimize th e total transportation cost.
2.1 INTRODUCTION
Transportation is a typical type of operation research technique developed
for transportation of goods from the sources to the destination.
Transportation problem is a special type of linear programming probl em
which can be solved by using different methods of transportation. A single
product can be transported from several sources to different destinations
with the help of transportation problems.
munotes.in
Page 24
24
Operation Research 2.1.1 Constraints or conditions of transportation problem:
The constraints of transportation problems involve different conditions
under which transportation problem can be solved. The const raints of
transportation problem are as follows :
1. Demand and supply relation
Necessary and sufficient condition for existence of a feasible solution to
the transportation problem is that there should be total demand equal to
total supply. (i.e. Total demand is equal to total supply).
2. Balanced Transportation problem
When total demand is equal to total supply then the transportation
problem is said to be balanced.
3. Unbalanced transportation problem
If total demand is not equal to total supply then the transportation problem
is an unbalanced transportation problem.
4. Occu pied cells and unoccupied cells
The occupied cells are having posit ive allocation in a transportation
problem and are denoted by a circular symbol. The cells are not having
any allocation in a transportation problem.
5. Basic feasible solution
The basic feasible solution exists when number of occupied cells are equal
to numb er of rows and number of columns minus one i.e. (No. of occupied
cells = m+n -1). Where m is the number of rows and n is the number of
columns.
6. Degenerate solution and non -degenerate solution
When the number of positive allocated cells are less than m+n -1 and a
solution is degenerate solution and when the number of positive located
cells are equal to m+n -1 then the solution is non -degen erate solution.
7. Prohibited routes
Due to unfavorable road conditions, bad weather conditions or any other
condition etc., It may not be possible to transit products from the sources
to the destination such routes are prohibited routes.
2.2 MATRIX TERMINOLOGY
Following matrix terminologies are often used in transportation model.
1 Cell munotes.in
Page 25
25
Transportation The smallest element of a matrix is called a cell. It is at the intersection of
row and column. The cell in a transportation model represents the unit
cost of transportation from source to the destination.
2 Row
The horizontal arrangement of cells in the matrix is termed as a row. Row
heading may r epresent the source or origins or plants from where goods
are manufactured and ready for transportation. It is related to the supply
function.
3 Column
The vertical arrangement of cells in the matrix is termed as a column. The
column heading may represent the destination center to which goods are
ready for transportation. It is related to the demand function.
4 Source
Source is the origin or plant from where goods are manufactured and
ready for transportation. Generally different sources are available in a
transportation model.
5 Destination
Destination is the final place where goods are required to be transported.
Transportation models with different destinations are available. Due to
availability of different sources and destinations with different unit co sts
of transportation, a transportation model is designed.
2.3 SOLUTION OF TRANSPORTATION MODEL
The solution of transportation model is designed to minimize the total cost
of transportation and to transit the goods from source to destination with
minimum c ost.
The solution of a transportation model has following steps :
a. Formulate the transportation model in matrix form
b. Obtain an initial feasible solution
c. Perform optimally test.
d. Find the transportation solution (after iteration if available)
Steps of soluti ons of transportation models are described in depth as
follows :
a. Formulate the transportation model in matrix form
The o bjective function of transportation problems is to minimize
transportation cost and the constraints are demands from the destination
and supply from the sources and hence transportation problem is similar to
that of linear programming problems. The formulation of transportation
model requires objective function as total transportation cost to be
minimi zed and demand and supply as constrain ts. Key decision is overall munotes.in
Page 26
26
Operation Research minimization of transportation cost. For example, the daily supplies of
milk from different sources to the different destinations having milk
demand are matched with transportation models. The total transportation
cost can be mi nimized using the transportation model.
b. Obtain an initial feasible solution
An initial feasible solution is the first solution to the transportation
problem. The transportation quantities and routes are decided at an initial
stage.
This solution may be ob tained using different methods such as
i. North West Corner Method
ii. Row Minima Method
iii. Column Minima Method
iv. Least Cost Method
v. Vogels’ Approximation Method
c. Perform optimality test.
The initial feasible solution is tested for the optimality using the condition
as when the number of occupied cells is equal to the sum of number of
rows and number of columns -1.
a. Condition A
When the opposite condition is satisfied then the given initial feasible
solution is optimal and this is the final solution where improvement for
minimizing total transportation cost is not possible
b. Condition B
When the opposite condition is not satisfied then the given initial feasible
solution is not optimal and this is not the final solution where
improvement for minimizing total transportati on cost is possible.
c. Find the transportation solution (after iteration if available)
The final minimized transportation solution (after iteration if available) is
computed and this gives the most possible minimum total transportation
cost subject to the av ailability of supply and demand constraints from the
supply and demand respectively.
2.4 METHODS OF OBTAINING AN INITIAL FEASIBLE
SOLUTION
An initial feasible solution is the first solution to the transportation
problem. The transportation quantities and r outes are decided at an initial
stage.
This solution may be obtained using different methods such as :
2.4.1 NORTH WEST CORNER METHOD
North West Corner Method is the simple and easy method to compute
initial feasible solution. This method considers neithe r the cost of
transportation nor the path of transportation. North West Corner is the munotes.in
Page 27
27
Transportation upper left corner of the matrix used for transportation. The process of
transportation of goods starts from the North West Corner of the matrix.
There are several steps of calculating initial feasible solution using North
West Corner Method as follows:
Step 1.
As North West Corner is the upper left corner of the matrix used for
transportation. The process of allocation of goods in transit starts from the
North West Cor ner of the matrix. Start the allocation of transportation
units from the North West Corner (the upper left corner of the matrix) cell
by considering minimum values from the corresponding first row and first
column i.e. Min (First Row, First Column).
Step 2.
a. If the values of First Row and First Column are equal then the same
units will be transferred from the first North West Corner of the matrix.
This condition is termed as degeneracy.
b. If the values of First Row and First Column are not equal then the
minimum units (i.e. Min.( First Row, First Column) will be transferred
from the first North West Corner of the matrix. The balance value of
either first row or first column is kept there and is to be considered for
next North West Corner . The reduced first r ow is considered as the North
West row for allocating transportation units to that cell.
Step 3.
Similar iteration is done for allocating transportation units until it reaches
to the extreme South East Corner of the transportation matrix. At the last
cell of the transportation matrix (extreme South East Corner), the
remaining total demand and total supply would be equal (degeneracy
condition). In this way balanced transportation problem will be solved and
unbalanced transportation problem will be solved by making it balanced
by adding dummy row or column making total demand=total supply.
Let us understand these steps by practical example.
1. Solve the following transportation problem using North West Corner
method.
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
Solution:
As Total Supply= Total Demand (125 units), this is balanced
transportation problem.
munotes.in
Page 28
28
Operation Research Step 1. The North West Corner is Upper Left Corner called S1D1 cell.
Corresponding first row supply is 20 unit s and corresponding first column
demand is 40 Units. Hence allocation of maximum 20 units is possible
(Being the minimum of first row and first column) to the S1D1 cell.
After allocating these 20 u nits, supply side gets completely fulfilled and
hence ther e is no requirement of supply in the f irst row and the demand
side gets reduced from 40 units to 20 units (40 -20=20) hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 (20) 2 1 20, 0
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40, 20 30 55 125
Step 2. Now, the next North West Corner is Upper Left Corner called
S2D1 cell. Corresponding second row supply is 50 units and
corresponding first column demand is 20 Units. Hence allocation of
maximum 20 units is possible (Being the mini mum of second row and
first column) to the S2D1 cell.
After allocating these 20 u nits, demand side gets completely fulfilled and
hence there is no requirement of dema nd in the first column and the
supply side gets reduced from 50 units to 30 units (50 -20=30) hence the
reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 (20) 2 1 20, 0
S2 2 (20) 4 1 50, 30
S3 3 5 2 30
S4 4 6 7 25
Demand 40, 20 30 55 125
Step 3. Now, the next North West Corner is Upper Left Corner called
S2D2 cell. Corre sponding second row supply is 30 units and
corresponding second column demand is 30 Units. Hence allocation of
maximum 30 units is possible (Being the minimum of second row and
second column) to the S2D2 cell. munotes.in
Page 29
29
Transportation
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of deman d in the second column and the
supply side gets fulfilled and hence the reduced transportation matrix
becomes
D1 D2 D3 Supply
S1 3 (20) 2 1 20, 0
S2 2 (20) 4 (30) 1 50, 30
S3 3 5 2 30
S4 4 6 7 25
Demand 40, 20 30 55 125
Step 4. Now, the next North West Corner is Upper Left Corner called
S3D3 cell. Corresponding third row supply is 30 units and corresponding
third column demand is 55 Units. Hence allocation of maximum 30 un its
is possible (Being the minimum of third row and third column) to the
S3D3 cell.
After allocating these 30 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the third row and the demand
side gets reduced from 5 5 to 25 units (55 -30=25) and hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 (20) 2 1 20, 0
S2 2 (20) 4 (30) 1 50, 30
S3 3 5 2 (30) 30
S4 4 6 7 25
Demand 40, 20 30 55, 25 125
Step 5 . Now, the next North West Corner is Upper Left Corner called
S4D3 cell. Corresponding fourth row supply is 25 units and corresponding
third column demand is 25 Units. Hence allocation of maximum 25 units
is possible (Being the minimum of forth row and third column) to the
S4D3 cell.
After allocating these 25 units, supply side gets completely fulfilled and
hence there is no requirement of supply in the fourth row and the demand munotes.in
Page 30
30
Operation Research side gets completed fulfilled and hence there is no requirement of demand
in the fourth row and hence the reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 (20) 2 1 20, 0
S2 2 (20) 4 (30) 1 50, 30
S3 3 5 2 (30) 30
S4 4 6 7 (25) 25
Demand 40, 20 30 55, 25 125
Step 6 . Allocation of Transportation Units.
Total Transportation Cost = 3 (20) + 2 (20) + 4 (30) + 2 (30) + 7(25)
= 60+40+120+60+175
= 455.
Hence , Total Transportation Cost is Rs.455 using North West Corner
Method.
2. Solve the following transportation problem using North West Corner
method.
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
Solution:
As Total Supply = Total Demand (180 units), this is balanced
transportation problem.
Step 1. The North West Corner is Upper Left Corner called S1D1 cell.
Correspo nding first row supply is 50 units and corresponding first column
demand is 30 Units. Hence allocation of maximum 30 units is possible
(Being the minimum of first row and first column) to the S1D1 cell.
After allocating these 30 u nits, demand side gets co mpletely fulfilled and
hence there is no requirement of demand in the first column and the
supply side gets reduced from 50 units to 20 units (50 -30=20) hence the
reduced transportation matrix becomes
munotes.in
Page 31
31
Transportation
D1 D2 D3 D4 Supply
S1 20 (30) 30 40 30 50, 20
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
Step 2. The North West Corner is Upper Left Corner called S1D2 cell.
Corresponding first row supply is 20 units and corresponding second
column demand is 50 Units. Hence allocation of maximum 20 units is
possible (Being the minimum of first row and second column) to the S1D2
cell.
After allocating these 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 50 units to 30 units (50 -20=30) hence the reduced
transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 (30) 30 (20) 40 30 50, 20
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50, 30 30 70 180
Step 3. The North West Corner is Upper Left Corner called S2D 2 cell.
Corresponding second row supply is 60 units and corresponding second
column demand is 30 Units. Hence allocation of maximum 30 units is
possible (Being the minimum of second row and second column) to the
S2D2 cell.
After allocatin g these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the second column and the
supply side gets reduced from 60 units to 30 units (60 -30=30) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 (30) 30 (20) 40 30 50, 20
S2 10 20 (30) 30 10 60, 30
S3 20 40 60 10 70
Demand 30 50, 30 30 70 180 munotes.in
Page 32
32
Operation Research
Step 4. The North West Corner is Upper Left Corner called S2D3 cell.
Corresponding second row supply is 30 units and corresponding third
column demand is 30 Units. Hence allocation of maximum 30 units is
possible (Being the minimum of second row and second column) to the
S2D2 cell.
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of d emand in the third column and the
supply side gets completed fulfilled and hence there is no requireme nt of
supply in the second row hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20
(30) 30
(30) 10 60, 30
S3 20 40 60 10 70
Demand 30 50, 30 30 70 180
Step 5. The North West Corner is Upper Left Corner called S3D4 cell.
Corresponding third row supply is 770 units and corresponding fourth
column demand is 70 Units. Hence allocation of ma ximum 70 units is
possible (Being the equal units) to the S3D4 cell.
After allocating these 70 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the fourth column and the
supply side gets completed fulfilled and h ence there is no requirem ent of
supply in the third row hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20
(30) 30
(30) 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50, 30 30 70 180
Step 6: Computation of Total Transportation Cost munotes.in
Page 33
33
Transportation Total transportation cost can be calculated by summing the multiplication
of unit cost of transportation with transportation units of occupied cells as
follows
Total Transportation Cost = 20(30) +30(20)+20 (30)+30(30)+10(70)
= 600+600+600+900+700
= 3400
Total Transportation Cost using NWCM is Rs. 3400
3. Solve the following transportation problem using North West
Corner method.
D1 D2 D3 D4 Supply
S1 40 50 60 50 50
S2 30 40 50 30 60
S3 40 60 80 30 70
Demand 30 50 30 70 180
Solution:
As Total Supply= Total Demand (180 units), this is balanced
transportation problem.
Step 1. The North West Corner is Upper Left Corner called S1D1 cell.
Corresponding first row supply is 50 units and correspond ing first column
demand is 30 Units. Hence allocation of maximum 30 units is possible
(Being the minimum of first row and first column) to the S1D1 cell.
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirem ent of demand in the first column and the
supply side gets reduced from 50 units to 20 units (50 -30=20) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 40 (30) 50 60 50 50, 20
S2 30 40 50 30 60
S3 40 60 80 30 70
Demand 30 50 30 70 180
Step 2. The North West Corner is Upper Left Corner called S1D2 cell.
Corresponding first row supply is 20 units and corresponding second
column demand is 50 Units. Hence allocation of maximum 20 units is munotes.in
Page 34
34
Operation Research possible (Being the minimum of first row and second column) to the S1D2
cell.
After allocating these 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 50 units to 30 units (50 -20=30) hence the reduc ed
transportation matrix becomes
D1 D2 D3 D4 Supply
S1 40 (30) 50 (20) 60 50 50, 20
S2 30 40 50 30 60
S3 40 60 80 30 70
Demand 30 50, 30 30 70 180
Step 3. The North West Corner is Upper Left Corner called S2D2 cell.
Corresponding second row su pply is 60 units and corresponding second
column demand is 30 Units. Hence allocation of maximum 30 units is
possible (Being the minimum of second row and second column) to the
S2D2 cell.
After allocating these 30 u nits, demand side gets completely fulfil led and
hence there is no requirement of demand in the second column and the
supply side gets reduced from 60 units to 30 units (60 -30=30) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 40 (30) 50 (20) 60 50 50, 20
S2 30 40 (30) 50 30 60, 30
S3 40 60 80 30 70
Demand 30 50, 30 30 70 180
Step 4 . The North West Corner is Upper Left Corner called S2D3 cell.
Corresponding second row supply is 30 units and corresponding third
column demand is 30 Units. Hence allocation of max imum 30 units is
possible (Being the minimum of second row and second column) to the
S2D2 cell.
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the third column and the
supply side gets completed fulfilled and hence there is no requirement of
supply in the second row hence the reduced transportation matrix becomes munotes.in
Page 35
35
Transportation D1 D2 D3 D4 Supply
S1 40
(30) 50
(20) 60 50 50, 20
S2 30 40
(30) 50
(30) 30 60, 30
S3 40 60 80 30 70
Demand 30 50, 30 30 70 180
Step 5. The North West Corner is Upper Left Corner called S3D4 cell.
Corresponding third row supply is 770 units and corresponding fourth
column demand is 70 Units. Hence allocation of maximum 70 units is
possible (Being the equal units) to the S3D4 cell.
After allocating these 70 units, demand s ide gets completely fulfilled and
hence there is no requirement of demand in the fourth column and the
supply side gets completed fulfilled and hence there is no requirem ent of
supply in the third row hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 40
(30) 50
(20) 60 50 50, 20
S2 30 40
(30) 50
(30) 30 60, 30
S3 40 60 80 30
(70) 70
Demand 30 50, 30 30 70 180
Step 6. Computation of Total Transportation Cost
Total transportation cost can be calculated by summing the multiplication
of unit cost of transportation with transportation units of occupied cells as
follows
Total Transportation Cost =
40(30)+50(20)+40(30)+50(30)+30(70)
= 1200+1000+1200+1500+2100
= 7000
Total Transportation Cost using NWCM is Rs. 7000
2.4.2 ROW MINIMA METHOD
Row Minima Method is the simple and easy method to compute initial
feasible solution. This method considers the cost of transportation and the
paths of transportation b oth. Row Minima is the considering minimum munotes.in
Page 36
36
Operation Research value in the given row in sequence from Row 1 onwards used for
transportation. The process of allocation of goods in transit starts from the
first row by considering the minimum value in the first row and similar
calculations are carried forward.
There are several steps of calculating initial feasible solution using Row
Minima Method as follows:
Step 1. Row Minima is the considering minimum value in the given row
in sequence from Row 1 onwards used for transport ation. The process of
allocation of goods in transit starts from the first row by considering the
minimum value in the first row and similar calculations are carried
forward. Start the allocation of transportation units from the first row by
considering mi nimum value from the corresponding first row.
Step 2. After allocation of transportation units to the cell having
minimum value in the first row then if first row transportation units are
remaining then corresponding allocation of transportation units to the next
smaller transportation cost of first row can be done considering the
demand and supply side of transportation problem.
Step 3. Similar iteration is done for allocating transportation units until it
reaches to last row with complete allocation o f transportation units
matching demand and supply side.
Let us understand these steps by practical example.
4. Solve the following transportation problem using Row Minima
Method.
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
Solution:
As Total Supply= Total Demand (125 units), this is balanced
transportation problem.
Step 1. The First row in the transportation matrix is S1. Corresponding
minimum cell value representing unit transportation cost is S1D3 in the
first row. The allocation of transportation unit will be done firstly in the
cell S1D3 by considering corresponding demand and supply for that cell. munotes.in
Page 37
37
Transportation The supply is of 20 units and demand is of 55 units. Minimum of these
two values is 20 and hence the allocatio n of 20 units can be done in this
cell as below .
After allocating these 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 55 units to 35 units (55 -20=35) hen ce the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40, 30 55, 35 125
There is no other cell remaining in the first row.
Step 2. The Second row in the transportation matri x is S2. Corresponding
minimum cell value representing unit transportation cost is S2D3 in the
second row. The allocation of transportation unit will be done firstly in the
cell S2D3 by considering corresponding demand and supply for that cell.
The supply is of 50 units and demand is of 35 units. Minimum of these
two values is 35 and hence the allocation of 35 units can be done in this
cell as below .
After allocating these 35 u nits, demand side gets completely fulfilled and
hence there is no requirement o f dema nd in the third column and the
supply side gets reduced from 50 units to 15 units (50 -35=15) hence the
reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 4 1 (35) 50, 15
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55, 35 125
munotes.in
Page 38
38
Operation Research There is no other cell remaining in the third column.
Step 3. The reduced second row S2 is remaining in the transportation
matrix. Corresponding minimum cell value representing unit
transportation cost is S2D1 in the second row. The allocation of
transportation unit will be done now in the cell S2D1 by considering
corresponding demand and supply for that cell.
The supply is of 15 units and demand is of 40 units. Minimum of these
two values is 15 and hence the allocation of 15 units can be done in this
cell as below .
After allocating these 15 units, supply side g ets completely fulfilled and
hence there is no requirement of su pply in the second row and the demand
side gets reduced from 40 units to 25 units (40 -15=25) hence the reduced
transportat ion matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 (15) 4 1 (35) 50, 15
S3 3 5 2 30
S4 4 6 7 25
Demand 40, 25 30 55, 35 125
There is no other cell remaining in the second row.
Step 4. The next row is third row S3 in the transport ation matrix.
Corresponding minimum cell value representing unit transportation cost is
S3D1 in the third row. The allocation of transportation unit will be done
now in the cell S3D1 by considering corresponding demand and supply
for that cell.
The supply is of 30 units and demand is of 25 units. Minimum of these
two values is 25 and hence the allocation of 25 units can be done in this
cell as below .
After allocating these 25 u nits, demand side gets completely fulfilled and
hence there is no requirement o f demand in the first column and the
supply side gets reduced from 30 units to 5 units (30 -25=5) hence the
reduced transportation matrix becomes
munotes.in
Page 39
39
Transportation D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 (15) 4 1 (35) 50, 15
S3 3 (25) 5 2 30, 5
S4 4 6 7 25
Demand 40, 25 30 55, 35 125
There is no other cell remaining in the first column.
Step 5. The next row is again reduced third row S3 in the transportation
matrix. Corresponding minimum cell value representing unit
transportation cost is S3D2 in the th ird row. The allocation of
transportation unit will be done now in the cell S3D2 by considering
corresponding demand and supply for that cell.
The supply is of 5 units and demand is of 30 units. Minimum of these two
values is 5 and hence the allocation of 5 units can be done in this cell as
below .
After allocating these 5 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the third row and the demand
side gets reduced from 30 units to 25 units (30 -5=25) hence the r educed
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 (15) 4 1 (35) 50, 15
S3 3 (25) 5 (5) 2 30, 5
S4 4 6 7 25
Demand 40, 25 30, 25 55, 35 125
There is no other cell remaining in the third row.
Step 6. The nex t row is reduced fourth row S4 in the transportation
matrix. Corresponding minimum cell value representing unit
transportation cost is S4D2 in the fourth row. The allocation of
transportation unit will be done now in the cell S4D2 by considering
correspond ing demand and supply for that cell.
munotes.in
Page 40
40
Operation Research The supply is of 25 units and demand is of 25 units. Minimum of these
two values is 25 and hence the allocation of 25 units can be done in this
cell as below .
After allocating these 25 u nits, supply side gets complete ly fulfilled and
hence there is no requirement of supply in the fourth row and the demand
side gets completed fulfilled and hence there is no requirement of demand
in the second column hence the reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (20) 20, 0
S2 2 (15) 4 1 (35) 50, 15
S3 3 (25) 5 (5) 2 30, 5
S4 4 6 (25) 7 25
Demand 40, 25 30, 25 55, 35 125
There is no other cell remaining in the fourth row.
Step 7 . Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 1 (20)+ 2 (15)+ 1 (35)+ 3 (25)+ 5(5)+ 6 (25)
= 20+30+35+75+25+ 150
= 335.
Hence , Total Transportation Cost is Rs.335 using Row Minima Method.
5. Solve the following transportation problem using Row Minima
method.
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
Solution:
As Total Supply= Total Demand (180 units), this is balanced
transportation problem.
Step 1. The First row in the transportation matrix is S1. Cor responding
minimum cell value representing unit transportation cost is S1D1 in the munotes.in
Page 41
41
Transportation first row. The allocation of transportation unit will be done firstly in the
cell S1D1 by considering corresponding demand and supply for that cell.
The supply is of 50 unit s and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 units, demand side gets complete ly fulfilled and
hence there is no requirement of dem and in th e first column and the
supply side gets reduced from 50 units to 20 units (50 -30=20) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 (30) 30 40 30 50, 20
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
There is no other cell remaining in the first column.
Step 2. The reduced first row in the transportation matrix is S1.
Corresponding minimum cell value representing unit transportation cost is
S1D2 in the first row. The allocation of transportation unit will be done
firstly in the cell S1D2 by considering corresponding demand and supply
for that cell.
The supply is of 20 units and demand is of 50 units. Minimum of these
two values is 20 and hence the allocation of 20 units can be done in this
cell as below .
After allocating these 20 units, supply side gets complete ly fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 50 units to 30 units (50 -20=30) hence the reduced
transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 (30) 30 (20) 40 30 50, 20
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50,
(30) 30 70 180
munotes.in
Page 42
42
Operation Research There is no other cell remaining in the first row.
Step 3. The next second row in the transportation matrix is S2.
Corresponding minimu m cell value representing unit transportation cost is
S2D4 in the second row. The allocation of transportation unit will be done
firstly in the cell S2D4 by considering corresponding demand and supply
for that cell.
The supply is of 60 units and demand is of 70 units. Minimum of these
two values is 60 and hence the allocation of 60 units can be done in this
cell as below .
After allocating these 60 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the second row an d the demand
side gets reduced from 70 units to 10 units (70 -60=10) hence the reduced
transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20 30 10
(60) 60
S3 20 40 60 10 70
Demand 30 50,
(30) 30 70, 10 180
There is no other cell remaining in the second row.
Step 4. The next third row in the transportation matrix is S3.
Corresponding minimum cell value representing unit transportation cost is
S3D4 in the third row. The allocation of transportation unit will b e done
firstly in the cell S3D4 by considering corresponding demand and supply
for that cell.
The supply is of 70 units and demand is of 10 units. Minimum of these
two values is 10 and hence the allocation of 10 units can be done in this
cell as below
After allocating these 10 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the fourth column and the
supply side gets reduced from 70 units to 60 units (70 -10=60) hence the
reduced transportation matrix becomes
munotes.in
Page 43
43
Transportation D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20 30 10
(60) 60
S3 20 40 60 10
(10) 70, 60
Demand 30 50, 30 30 70, 10 180
There is no other cell remaining in the fourth column.
Step 5. The reduced third row in the transportation ma trix is S3.
Corresponding minimum cell value representing unit transportation cost is
S3D2 in the third row. The allocation of transportation unit will be done
firstly in the cell S3D2 by considering corresponding demand and supply
for that cell.
The supp ly is of 60 units and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below
After allocating these 30 units, demand side gets complete ly fulfilled and
hence there is no requirement of demand in the second column and the
supply side gets reduced from 60 units to 30 units (60 -30=30) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20 30 10
(60) 60
S3 20 40
(30) 60 10
(10) 70, 60,
30
Demand 30 50, 30 30 70, 10 180
There is no other cell remaining in the second column.
Step 6. The reduced third row in the transportation matrix is S3.
Corresponding minimum cell value representing unit transportation cost is
S3D3 in the third row. The allocation of transportation unit will be done
firstly in the cell S3D3 by considering corresponding demand and supply
for that cell. munotes.in
Page 44
44
Operation Research The supply is of 30 units and demand is of 30 units. Minimum of these
two values is 30 and hence the a llocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the third column and the
supply side completed fulfilled and hence there is no r equirement of
supply in the third row hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20
(30) 30
(20) 40 30 50, 20
S2 10 20 30 10
(60) 60
S3 20 40
(30) 60
(30) 10
(10) 70, 60,
30
Demand 30 50, 30 30 70, 10 180
There is no other cell remaining in the third column and third row also.
Step 7. Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 20(30)+30(20)+ 10(60)+ 40(30)+ 60(30)+ 10(10)
= 600+600+600+1200+1800+ 100
= 490 0.
Hence , Total Transportation Cost is Rs.4900 using Row Minima Method.
2.4.3 COLUMN MINIMA METHOD
Column Minima Method is the simple and easy method to compute initial
feasible solution. This method considers the cost of transportation and the
paths o f transportation both. Column Minima is the considering minimum
value in the given column in sequence from Column 1 onwards used for
transportation. The process of allocation of goods in transit starts from the
first column by considering the minimum valu e in the column row and
similar calculations are carried forward.
There are several steps of calculating initial feasible solution using
Column Minima Method as follows:
Step 1. Column Minima is considering the minimum value in the given
column in sequen ce from column 1 onwards used for transportation. The
process of allocation of goods in transit starts from the first column by
considering the minimum value in the first column and similar
calculations are carried forward. Start the allocation of transpor tation units munotes.in
Page 45
45
Transportation from the first column by considering minimum value from the
corresponding first column.
Step 2. After allocation of transportation units to the cell having
minimum value in the first column then if first column transportation units
are remai ning then corresponding allocation of transportation units to the
next smaller transportation cost of first column can be done considering
the demand and supply side of transportation problem.
Step 3. Similar iteration is done for allocating transportati on units until it
reaches to last column with complete allocation of transportation units
matching demand and supply side.
Let us understand these steps by practical example.
6. Solve the following transportation problem using column Minima
Method.
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
Solution:
As Total Supply= Total Demand (125 units), this is balanced
transportation problem.
Step 1. The First column in the transportation matrix is D1.
Corresponding minimum cell value representing unit transportation cost is
S2D1 in the first column. The allocation of transportation unit will be
done firstly in the cell S2D1 by considering corresponding demand and
supply for that cell.
The supply is of 50 units and d emand is of 40 units. Minimum of these
two values is 40 and hence the allocation of 40 units can be done in this
cell as below .
After allocating these 40 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the first column and the
supply side gets reduced from 50 units to 10 units (50 -40=10) hence the
reduced transportation matrix becomes
munotes.in
Page 46
46
Operation Research D1 D2 D3 Supply
S1 3 2 1 20
S2 2 (40) 4 1 50, 10
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
There is no other cell remaining in the first column.
Step 2. The Second column in the transportation matrix is D2.
Corresponding minimum cell value representing unit transportation cost is
S1D2 in the second column. The allocation of transportation unit will be
done firstly in the cell S1D2 by considering corresponding demand and
supply for that cell.
The supply is of 20 units and demand is of 30 units. Minimum of these
two values is 20 and hence the allocation of 20 units can be done in this
cell as below .
After allocating t hese 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 30 units to 10 units (30 -20=10) hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (20) 1 20
S2 2 (40) 4 1 50, 10
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30, 10 55 125
There is no other cell remaining in the first row.
Step 3. The reduced second columnD2 is remaining in the transportation
matrix. Corresponding minimum cell val ue representing unit
transportation cost is S2D2 in the second column. The allocation of
transportation unit will be done now in the cell S2D2 by considering
corresponding demand and supply for that cell.
munotes.in
Page 47
47
Transportation The supply is of 10 units and demand is of 10 unit s. Minimum of these
two values is 10 and hence the allocation of 10 units can be done in this
cell as below .
After allocating these 10 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the second row and the deman d
side gets completed fulfilled and hence there is no requirement of demand
in the second column, hence the reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (20) 1 20
S2 2 (40) 4 (10) 1 50, 10
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30, 10 55 125
There is no other cell remaining in the second row.
There is no other cell remaining in the second column.
Step 4. The next column is third column S3 in the transportation matrix.
Corresponding minimum cell value representing unit transp ortation cost is
S3D3 in the third column. The allocation of transportation unit will be
done now in the cell S3D3 by considering corresponding demand and
supply for that cell.
The supply is of 30 units and demand is of 55 units. Minimum of these
two valu es is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the third row and the demand
side gets reduced from 55 u nits to 25 units (55 -30=25) hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (20) 1 20
S2 2 (40) 4 (10) 1 50, 10
S3 3 5 2 (30) 30
S4 4 6 7 25
Demand 40 30, 10 55, 25 125 munotes.in
Page 48
48
Operation Research There is no other cell remaining in the thi rd row.
Step 5. The next column is again reduced third columnD3 in the
transportation matrix. Corresponding minimum cell value representing
unit transportation cost is S4D3 in the third column. The allocation of
transportation unit will be done now in the cell S4D3 by considering
corresponding demand and supply for that cell.
The supply is of 25 units and demand is of 25 units. Minimum of these
two values is 25 and hence the allocation of 25 units can be done in this
cell as below .
After allocating these 25 units, supply side gets completely fulfilled and
hence there is no requirement of supply in the third row and the demand
side gets completed fulfilled and hence there is no requirement of demand
in the third column, hence the reduced transportation mat rix becomes
D1 D2 D3 Supply
S1 3 2 (20) 1 20
S2 2 (40) 4 (10) 1 50, 10
S3 3 5 2 (30) 30
S4 4 6 7 (25) 25
Demand 40 30, 10 55, 25 125
There is no other cell remaining in the third row.
Step 6. Allocation of Transportation Units to t he occupied cells
Total Transportation Cost = 2(40)+2(20)+ 4(10)+ 20(30)+ 7(25)
= 80+40+40+60+175
= 395.
Hence , Total Transportation Cost is Rs.395 using Column Minima
Method.
7. Solve the following transportation problem using Column Minima
method.
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
munotes.in
Page 49
49
Transportation
Solution:
As Total Supply= Total Demand (180 units), this is balanced
transportation problem.
Step 1. The First column in the transportation mat rix is D1.
Corresponding minimum cell value representing unit transportation cost is
S2D1 in the first column. The allocation of transportation unit will be
done firstly in the cell S2D1 by considering corresponding demand and
supply for that cell.
The su pply is of 60 units and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requireme nt of demand in the first column and the
supply side gets reduced from 60 units to 30 units (60 -30=30) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 (30) 20 30 10 60, 30
S3 20 40 60 10 70
Demand 30 50 30 70 180
There is no other cell remaining in the first column.
Step 2. The second column in the transportation matrix is D2.
Corresponding minimum cell value representing unit transportation cost is
S2D2 in the second column. The allocation of transpor tation unit will be
done firstly in the cell S2D2 by considering corresponding demand and
supply for that cell.
The supply is of 30 units and demand is of 50 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the second row and the demand
side gets reduced from 50 units to 20 units (50 -30=20) hence the reduced
transportation mat rix becomes
munotes.in
Page 50
50
Operation Research
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 (30) 20 (30) 30 10 60, 30
S3 20 40 60 10 70
Demand 30 50,
(20) 30 70 180
There is no other cell remaining in the first row.
Step 3. The reduced second column in the transportation mat rix is D2.
Corresponding minimum cell value representing unit transportation cost is
S1D2 in the second column. The allocation of transportation unit will be
done firstly in the cell S1D2 by considering corresponding demand and
supply for that cell.
The s upply is of 50 units and demand is of 20 units. Minimum of these
two values is 20 and hence the allocation of 20 units can be done in this
cell as below .
After allocating these 20 u nits, demand side gets completely fulfilled and
hence there is no requirem ent of demand in the second column and the
supply side gets reduced from 50 units to 30 units (50 -20=30) hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 30 (20) 40 30 50, 30
S2 10 (30) 20 (30) 30 10 60, 30
S3 20 40 60 10 70
Demand 30 50, 30 30 70 180
There is no other cell remaining in the second column.
Step 4. The next third column in the transportation matrix is D3.
Corresponding minimum cell value representing unit transportation cost is
S1D4 in the third column . The allocation of transportation unit will be
done firstly in the cell S1D4 by considering corresponding demand and
supply for that cell.
The supply is of 30 units and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below . munotes.in
Page 51
51
Transportation
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the third column and the
supply side gets completed fulfilled and hence there is no requireme nt of
demand in the third column hence the reduced transportation matrix
becomes
D1 D2 D3 D4 Supply
S1 20 30
(20) 40
(30) 30 50, 30
S2 10
(30) 20
(30) 30 10 60, 30
S3 20 40 60 10 70
Demand 30 50, 30 30 70 180
There is no other cell remain ing in the third column.
Step 5. The fourth column in the transportation matrix is D4.
Corresponding minimum cell value representing unit transportation cost is
S3D4 in the fourth column. The allocation of transportation unit will be
done firstly in the c ell S3D4 by considering corresponding demand and
supply for that cell.
The supply is of 70 units and demand is of 70 units. Minimum of these
two values is 70 and hence the allocation of 70 units can be done in this
cell as below .
After allocating these 7 0 units, demand side gets completely fulfilled and
hence there is no requirement of demand in the fourth column and the
supply side gets completed fulfilled and he nce there is no requirement of
supply in the third row, hence the reduced transportation matr ix becomes
D1 D2 D3 D4 Supply
S1 20 30
(20) 40
(30) 30 50, 30
S2 10
(30) 20
(30) 30 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50, 30 30 70 180
munotes.in
Page 52
52
Operation Research There is no other cell remaining in the fourth column and third row.
Step 6. Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 10(30)+30(20)+ 20(30)+ 40(30)+ 10(70)
= 300+600+600+1200+1700
= 4400.
Hence , Total Transportation Cost is Rs.4400 using Column Minima
Method.
2.4.4 LEAST COST METHOD
Leas t cost method is also known as matrix minima method because in this
method , minimum value in all rows and all columns are searched out and
corresponding allocation can be made in the transportation model.
Least Cost Method is the simple and easy method to compute initial
feasible solution. This method considers the cost of transportation and the
paths of transportation both. Matrix Minima is the considering minimum
value in the given row and column in sequence from Column 1 onwards
used for transportation . The process of allocation of goods in transit starts
from the anywhere in the matrix by considering the minimum value in the
column or row and similar calculations are carried forward.
There are several steps of calculating initial feasible solution usi ng Lest
Cost Method as follows:
Step 1. Matrix Minima is considering the minimum value in the given
column or row in sequence from c olumn 1 onwards or from row 1
onwards used for transportation. The process of allocation of goods in
transit starts from ei ther row or column by considering the minimum value
in the matrix and similar calculations are carried forward. Start the
allocation of transportation units from the row or column by considering
minimum value from the corresponding transportation matrix.
Step 2. After allocation of transportation units to the cell having
minimum value in the matrix then, find out the next minimum value in the
matrix considering the demand and supply side of transportation problem.
Step 3. Similar iteration is done for a llocating transportation units until it
reaches to cell of the matrix with complete allocation of transportation
units matching demand and supply side.
munotes.in
Page 53
53
Transportation Let us understand these steps by practical example.
8. Solve the following transportation problem using L east Cost Method.
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
Solution:
As Total Supply= Total Demand (125 units), this is balanced
transportation problem.
Step 1. The minimum value in the transportation mat rix is 1 available at
cell S1D3 and S2D3. Now there are two possibilities of allocating
transportation units as follows :
i. If we consider, the minimum value in the transportation matrix is 1
available at cell S1D3 then maximum 20 units can be transported fr om S1
to D3.
ii. If we consider, the minimum value in the transportation matrix is 1
available at cell S2D3 then maximum 50 units can be transported from S2
to D3.
Here , the maximum units should be transported so as to minimize the total
transportation cost.
Hence , the second possibility is better choice.
The minimum value in the transportation matrix is 1 available at cell
S2D3 then maximum 50 units can be transported from S2 to D3.
The allocation of transportation unit will be done firstly in the cell S2 D3
by considering corresponding demand and supply for that cell.
The supply is of 50 units and demand is of 55 units. Minimum of these
two values is 50 and hence the allocation of 50 units can be done in this
cell as below .
After allocating these 50 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the second row and the demand
side gets reduced from 55 units to 5 units (55 -50=5). Hence the reduced
transportation matrix becomes munotes.in
Page 54
54
Operation Research
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 (50) 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55, 5 125
There is no other cell remaining in the second row.
Step 2. The minimum value in the transportation matrix is 1 available at
cell S1D3 then maximum 20 units can be transported from S1 t o D3.
The allocation of transportation unit will be done firstly in the cell S1D3
by considering corresponding demand and supply for that cell.
The supply is of 20 units and demand is of 5 units. Minimum of these two
values is 5 and hence the allocation of 5 units can be done in this cell as
below .
After allocating these 5 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the third column and the
supply side gets reduced from 55 units to 5 units (55 -50=5). Hence the
reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 1 (5) 20, 15
S2 2 4 1 (50) 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55, 5 125
There is no other cell remaining in the third column.
Step 3. The minimum value in the transportat ion matrix is 2 available at
cell S1D2 then 15 units can be transported from S1 to D2.
The allocation of transportation unit will be done firstly in the cell S1D2
by considering corresponding demand and supply for that cell.
munotes.in
Page 55
55
Transportation The supply is of 15 units and demand is of 30 units. Minimum of these
two values is 15 and hence the allocation of 15 units can be done in this
cell as below .
After allocating these 15 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the fir st row and the demand
side gets reduced from 30 units to 15 units (30 -15=15). Hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (15) 1 (5) 20, 15
S2 2 4 1 (50) 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30, 15 55, 5 125
Ther e is no other cell remaining in the third column.
Step 4. The minimum value in the transportation matrix is 3 available at
cell S3D1 then 30 units can be transported from S3 to D1.
The allocation of transportation unit will be done firstly in the cell S 3D1
by considering corresponding demand and supply for that cell.
The supply is of 30 units and demand is of 40 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the third row and the demand
side gets reduced from 40 units to 10 units (40 -30=10). Hence the reduced
transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (15) 1 (5) 20, 15
S2 2 4 1 (50) 50
S3 3 (30) 5 2 30
S4 4 6 7 25
Demand 40, 10 30, 15 55, 5 125
munotes.in
Page 56
56
Operation Research There is no other cell remaining in the third row.
Step 5. The minimum value in the transportation matrix is 4 available at
cell S4D1 then 30 units can be transported from S4 to D1.
The allocation of transportation unit will be done firstly in the cell S4D1
by considering corresponding demand and supply for that cell.
The supply is of 25 units and demand is of 10 units. Minimum of these
two values is 10 and hence the allocation of 10 units can be done in this
cell as below .
After allocating these 10 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the first column and the
supply side gets reduced from 25 units t o 15 units (25 -10=15). Hence the
reduced transportation matrix becomes
D1 D2 D3 Supply
S1 3 2 (15) 1 (5) 20, 15
S2 2 4 1 (50) 50
S3 3 (30) 5 2 30
S4 4 (10) 6 7 25, 15
Demand 40, 10 30, 15 55, 5 125
There is no other cell remaining in th e first column.
Step 6. The minimum value in the transportation matrix is 6 available at
cell S4D2 then 15 units can be transported from S4 to D2.
The allocation of transportation unit will be done firstly in the cell S4D2
by considering corresponding demand and supply for that cell.
The supply is of 15 units and demand is of 15 units. Minimum of these
two values is 15 and hence the allocation of 15 units can be done in this
cell as below .
After allocating these 15 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the second column and the
supply side gets completed fulfilled and hence there is no requirement of
supply in the fourth row. Hence the reduced transportation matrix
becomes
munotes.in
Page 57
57
Transportation D1 D2 D3 Supply
S1 3 2 (15) 1 (5) 20, 15
S2 2 4 1 (50) 50
S3 3 (30) 5 2 30
S4 4 (10) 6 (15) 7 25, 15
Demand 40, 10 30, 15 55, 5 125
Step 7 . Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 2(15)+1(5)+ 1(50)+ 3(30)+ 4(10)+ 6 (15)
= 30+5+50+90+40+90
= 305.
Hence , Total Transportation Cost is Rs.305 using Least Cost Method.
9. Solve the following transportation problem using Matrix Minima
method.
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 20 30 10 60
S3 20 40 60 10 70
Demand 30 50 30 70 180
Solution:
As Total Supply= Total Demand (180 units), this is balanced
transportation problem.
Step 1. The minimum value in the transportation matrix is 10 available at
cell S2D1; S2D4 and S3D4. Now there are three possibil ities of allocating
transportation units as follows
a. If we consider, the minimum value in the transportation matrix is 10
available at cell S2D1 then maximum 30 units can be transported
from S2 to D1.
b. If we consider, the minimum value in the transportatio n matrix is 10
available at cell S2D4 then maximum 60 units can be transported
from S2 to D 4.
munotes.in
Page 58
58
Operation Research c. If we consider, the minimum value in the transportation matrix is 10
available at cell S 3D4 then maximum 70 units can be transported
from S 3 to D4.
Here the max imum units should be transported so as to minimize the total
transportation cost.
Hence , the third possibility is better choice.
The minimum value in the transportation matrix is 1 available at cell
S3D4 then maximum 70 units can be transported from S3 t o D4.
The allocation of transportation unit will be done firstly in the cell S3D4
by considering corresponding demand and supply for that cell.
The supply is of 70 units and demand is of 70 units. Minimum of these
two values is 70 and hence the allocation of 70 units can be done in this
cell as below
After allocating these 70 units, supply and demand both side gets
completed fulfilled and hence there is no requirement of demand and
supply. Hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supp ly
S1 20 30 40 30 50
S2 10 20 30 10 60
S3 20 40 60 10 (70) 70
Demand 30 50 30 70 180
There is no other cell remaining in the third row and fourth column.
Step 2. The minimum value in the transportation matrix is 10 available at
cell S2D1 then max imum 30 units can be transported from S2 to D1.
The allocation of transportation unit will be done firstly in the cell S2D1
by considering corresponding demand and supply for that cell.
The supply is of 60 units and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the first column and the
supply side gets reduce d from 60 units to 30 units (60 -30=30). Hence the
reduced transportation matrix becomes
munotes.in
Page 59
59
Transportation D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10 (30) 20 30 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50 30 70 180
There is no other cell remaining in the third row and fourth column.
Step 3. The minimum value in the transportation matrix is 20 available at
cell S2D2 then maximum 30 units can be transported from S2 to D2.
The allocation of transportation unit will be done firstly in the cell S2D2
by considering corresponding demand and supply for that cell.
The supply is of 30 units and demand is of 50 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 u nits, supply side ge ts completely fulfilled and
hence there is no requirement of supply in the second row and the demand
side gets reduced from 50 units to 20 units (50 -30=20). Hence the reduced
transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 30 40 30 50
S2 10
(30) 20
(30) 30 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50, 20 30 70 180
There is no other cell remaining in the third row and fourth column.
Step 4. The minimum value in the transportation matrix is 30 available at
cell S1D2 then maximum 20 uni ts can be transported from S1 to D2.
The allocation of transportation unit will be done firstly in the cell S1D2
by considering corresponding demand and supply for that cell.
The supply is of 50 units and demand is of 20 units. Minimum of these
two value s is 20 and hence the allocation of 20 units can be done in this
cell as below .
munotes.in
Page 60
60
Operation Research After allocating these 20 u nits, demand side gets completely fulfilled and
hence there is no requirement of demand in the second column and the
supply side gets reduced from 5 0 units to 20 units (50 -30=20). Hence the
reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 30
(20) 40 30 50, 30
S2 10
(30) 20
(30) 30 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50, 20 30 70 180
There is no other cell remaining in the third row and fourth column.
Step 5. The minimum value in the transportation matrix is 40 available at
cell S2D3 then maximum 30 units can be transported from S2 to D3.
The allocation of transportation unit will be done firstly in the cell S2D3
by considering corresponding demand and supply for that cell.
The supply is of 30 units and demand is of 30 units. Minimum of these
two values is 30 and hence the allocation of 30 units can be done in this
cell as below .
After allocating these 30 units, supply side and demand side both get
completed fulfilled and there is no requirement of demand and supply.
Hence the reduced transportation matrix becomes
D1 D2 D3 D4 Supply
S1 20 30
(20) 40
(30) 30 50, 30
S2 10
(30) 20
(30) 30 10 60, 30
S3 20 40 60 10
(70) 70
Demand 30 50, 20 30 70 180
There is no other cell remaining in the first row and third column.
Step 7. Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 30(20)+40(30)+ 10(30)+ 20(30)+ 10(70)
= 600+1200+300+600+700
= 3400. munotes.in
Page 61
61
Transportation
Hence , Total Transportation Cost is Rs.3400 using Least Cost Method.
2.4.5 VOGELS’ APPROXIMATION METHOD
Vogels’ Approximation Method considers the highest penalty value for
making allocation of transportation units . Penalty is the difference
between two minimum cost values. The highest penalty value present in
either row or column will be considered as the row or column for making
allocation of transportation units.
The minimum cost value will be chosen from the se lected row or column
of the highest penalty value. The iteration of highest penalty values and
corresponding allocations of transportation values are done until and
unless all units are transported from the sources to the different
destinations.
Let us un derstand these steps by practical example.
10. Solve following transportation problem using Vogels’ Approximation
Method .
D1 D2 D3 Supply
S1 3 2 1 20
S2 2 4 1 50
S3 3 5 2 30
S4 4 6 7 25
Demand 40 30 55 125
Solution:
As Total Supply= Total Demand (125 units), this is balanced
transportation problem.
Step 1. The maximum penalty value in the transportation matrix is 2
available at cell S4 row and D2 column. Now there are two possibilities of
allocating transportation units as follows :
A. If we consider, th e maximum penalty value in the transportation
matrix is 2 available at S4 row then for minimum unit of transportation 4
(S4D1) maximum 25 units can be transported from S4 to D1.
B. If we consider, the maximum penalty value in the transportation
matrix is 2 a vailable at D2 column then then for minimum unit of
transportation 2, maximum 20 units can be transported from S1 to D2.
Here , the maximum units should be transported so as to minimize the total
transportation cost.
Hence , the first possibility is better choice. munotes.in
Page 62
62
Operation Research The maximum penalty value in the transportation matrix is 2 available at
S4 row then for minimum unit of transportation 4 (S4D1) maximum 25
units can be transported from S4 to D1.
The allocation of transportation unit will be done firstly in the cell S4D1
by considering corresponding demand and supply for that cell.
The supply is of 25 units and demand is of 40 units. Minimum of these
two values is 25 and hence the allocation of 25 units can be done in this
cell as below .
After allocating these 25 units, supply side gets completely fulfilled and
hence there is no requirement of supply in the fourth row and the demand
side gets reduced from 40 units to 15 units (40 -25=15). Hence the reduced
transportation matrix becomes
D1 D2 D3 Supply Penalty1
S1 3 2 1 20 2-1=1
S2 2 4 1 50 2-1=1
S3 3 5 2 30 3-2=1
S4 4 (25) 6 7 25 6-4=2
Demand 40, 15 30 55 125
Penalty1 3-2=1 4-2=2 1-1=0
There is no other cell remaining in the first column.
Step 2. Repeat the process or steps
The maximum penalty va lue for second time in the transportation matrix
is 2 available at S4 row then for minimum unit of transportation 4 (S4D1)
maximum 25 units can be transported from S4 to D1.
The allocation of transportation unit will be done firstly in the cell S4D1
by co nsidering corresponding demand and supply for that cell.
The supply is of 25 units and demand is of 40 units. Minimum of these
two values is 25 and hence the allocation of 25 units can be done in this
cell as below .
After allocating these 25 u nits, suppl y side gets completely fulfilled and
hence there is no requirement of supply in the fourth row and the demand
side gets reduced from 40 units to 15 units (40 -25=15). Hence the reduced
transportation matrix becomes
munotes.in
Page 63
63
Transportation D1 D2 D3 Supply Penalty1 Penalty2 S1 3 2 1 20 2-1=1 2-1=1
S2 2 4 1 50 2-1=1 2-1=1
S3 3 5 2 30 3-2=1 3-2=1
S4 4
(25) 6 7 25 6-4=2
Demand 40,
15 30 55 125
Penalty1 3-
2=1 4-
2=2 1-
1=0
Penalty2 3-
2=1 4-
2=2 1-
1=0
There is no other cell remaining in the fourth row.
Step 3. Repea t the process or steps
The maximum penalty value for second time in the transportation matrix
is 2 available at D2column then for minimum unit of transportation 2
(S1D2) maximum 2 0 units can be transported from S 1 to D2.
The allocation of transportation unit will be done firstly in the cell S1D2
by considering corresponding demand and supply for that cell.
The supply is of 20 units and demand is of 30 units. Minimum of these
two values is 20 and hence the allocation of 20 units can be done in this
cell as below .
After allocating these 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 300 units to 10 units (30 -20=10). Hence the
reduced transportation matrix b ecomes
D1 D2 D3 Supply Penalty1 Penalty2 S1 3 2
(20) 1 20 2-1=1 2-1=1
S2 2 4 1 50 2-1=1 2-1=1
S3 3 5 2 30 3-2=1 3-2=1
S4 4
(25) 6 7 25 6-4=2
Demand 40,
15 30,
10 55 125
Penalty1 3-
2=1 4-
2=2 1-
1=0
Penalty2 3-
2=1 4-
2=2 1-
1=0 munotes.in
Page 64
64
Operation Research There i s no other cell remaining in the first row.
Step 4. Repeat the process or steps
The maximum penalty value for third time in the transportation matrix is 2
available at D2column then for minimum unit of transportation 2 (S1D2)
maximum 2 0 units can be tran sported from S 1 to D2.
The allocation of transportation unit will be done firstly in the cell S1D2
by considering corresponding demand and supply for that cell.
The supply is of 20 units and demand is of 30 units. Minimum of these
two values is 20 and he nce the allocation of 20 units can be done in this
cell as below .
After allocating these 20 u nits, supply side gets completely fulfilled and
hence there is no requirement of supply in the first row and the demand
side gets reduced from 300 units to 10 uni ts (30 -20=10). Hence the
reduced transportation matrix becomes
D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2
(20) 1 20 2-1=1 2-1=1
S2 2 4 1 50 2-1=1 2-1=1 2-1=1
S3 3 5 2 30 3-2=1 3-2=1 3-2=1
S4 4
(25) 6 7 25 6-4=2
Demand 40,
15 30,
10 55 125
Penalty1 3-
2=1 4-
2=2 1-
1=0
Penalty2 3-
2=1 4-
2=2 1-
1=0
Penalty3 3-
2=1 5-
4=1 2-
1=1
There is no other cell remaining in the first row.
The maximum penalty value for this time in the transportation matrix is 1
available at S2; S3 rows and D1; D2 and D3columns then for minimum
unit of transportation 1 (S2D3) maximum 50 units can be transported from
S2 to D3.
munotes.in
Page 65
65
Transportation The allocation of transportation unit will be done firstly in the cell S2D3
by considering corresponding demand and supply fo r that cell.
The supply is of 50 units and demand is of 55 units. Minimum of these
two values is 50 and hence the allocation of 50 units can be done in this
cell as below .
After allocating these 50 units, supply side gets complete ly fulfilled and
hence t here is no requirement of supply in the second row and the demand
side gets reduced from 55 units to 5 units (55 -50=5). Hence the reduced
transportation matrix becomes
D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2
(20) 1 20 2-1=1 2-1=1
S2 2 4 1
(50) 50 2-1=1 2-1=1 2-1=1
S3 3 5 2 30 3-2=1 3-2=1 3-2=1
S4 4
(25) 6 7 25 6-4=2
Demand 40,
15 30,
10 55,
5 125
Penalty1 3-
2=1 4-
2=2 1-
1=0
Penalty2 3-
2=1 4-
2=2 1-
1=0
Penalty3 3-
2=1 5-
4=1 2-
1=1
There is no other cell remaining in the SECOND row.
Step 5. As single cells are remaining in the columns, direct allocation is
possible as follows
D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2
(20) 1 20 2-1=1 2-1=1
S2 2 4 1
(50) 50 2-1=1 2-1=1 2-1=1
S3 3
(15) 5
(10) 2
(5) 30 3-2=1 3-2=1 3-2=1
S4 4
(25) 6 7 25 6-4=2 munotes.in
Page 66
66
Operation Research Demand 40,
15 30,
10 55,
5 125
Penalty1 3-
2=1 4-
2=2 1-
1=0
Penalty2 3-
2=1 4-
2=2 1-
1=0
Penalty3 3-
2=1 5-
4=1 2-
1=1
Step 6 . Allocation of Transportation Units to the occupied cells
Total Transportation Cost = 2(20)+1(50)+ 3(15)+ 5(10)+ 2(5)+4 (25)
= 40+50+45+50+10+100
= 295.
Hence , Total Transportation Cost is Rs.295 using Vogels’ Approximation
Method.
2.5 SELF ASSESSMENT TEST
Q1. Solve following Multiple Choice Quest ions.
1. Transportation is a typical type of operation research technique
developed for ……… from the sources to the destination .
a. transportation of goods
b. assignment of job
c. transfer of employees
d. None of the above.
2. Transportation problem is a s pecial type of ……… which can be solved
by using different methods of transportation .
a. Operations Method
b. linear programming problem
c. Research model
d. Business model.
3. The vertical arrangement of cells in the matrix is termed as …..
a. row b. col umn
c. table d. none of the above.
munotes.in
Page 67
67
Transportation 4. When total demand is equal to total supply then the transportation
problem is said to be …
a. Complete b. incomplete
c. balanced d. Unbalanced.
5. The basic feasible solution exists when …….
a. number of oc cupied cells are equal to number of rows and number of
columns minus one .
b. number of occupied cells are less than number of rows and number of
columns minus one .
c. number of occupied cells are greater than number of rows and number
of columns minus o ne.
d. number of occupied cells are either greater than or less than number of
rows and number of columns minus one .
6. The o bjective function of transportation problems is …..
A. to minimize transportation cost
b. to maximize transportation cost
c. to either minimize or to maximize transportation cost
d. to neither minimize nor to maximize transportation cost
7. …….. is the first solution to the transportation problem.
a. An initial feasible solution
b. An initial infeasible solution
c. An initial feasible or infeasible solution
d. VAM
8. In the North West Corner Method, the process of transportation of
goods starts from the……. Of the matrix.
a. Upper right corner
b. Lower right corner
a. lower left corner
d. upper left corner
Answers
1.) a 2.) b 3.) b 4.) c 5.) a 6.) a 7.) a 8.) d
munotes.in
Page 68
68
Operation Research Q2. Identify statements as true or false statement.
1. Necessary and sufficient condition for existence of a feasible solution
to the transportation problem is that there should be total demand
equal to total supply. (i.e. Total demand is equal to total supply).
(True or False)
2. When total demand is equal to total supply then the transportation
problem is said to be unbalanced. (True or False)
3. If total demand is not equal to t otal supply then the transportation
problem is an unbalanced transportation problem. (True or False).
4. The occupied cells are having positive allocation in a transportation
problem and are denoted by a circular symbol. (True or False).
5. The basic feasible solution exists when number of occupied cells are
not equal to number of rows and number of columns minus one i.e.
(No. of occupied cells = m+n -1). Where m is the number of rows and
n is the number of columns. (True or False).
6. When the number of positi ve allocated cells are less than m+n -1 and a
solution is degenerate solution and when the number of positive
located cells are equal to m+n -1 then the solution is non -degen erate
solution. (True or False)
7. Due to unfavorable road conditions, bad weather co nditions or any
other condition etc., It may not be possible to transit products from
the sources to the destination such routes are prohibited routes. (True
or False)
Answers:
1. True 2. False. 3. True
4. True 5. False 6. True
7. True
Q3. Wr ite short notes on
1. Describe various terminologies used in the transportation method
2. Explain methods of finding initial feasible solution.
3. Describe steps of finding solutions to the transportation prolem.
4. Explain the steps of solving
a. North West Corner M ethod.
b. Row Minima Method
c. Column Minima Method
d. Least Cost Method
e. Vogels’ Approximation Method. munotes.in
Page 69
69
Transportation Q4. Determine the initial feasible solution to the following
transportation problem using
a. North West Corner Method. (Answer: 116)
b. Least Cost Method (Answer: 112)
c. Vogels’ Approximation Method. (Answer: 102) Source/ Destination D1 D2 D3 D4 Supply S1 2 3 11 7 6 S2 1 0 6 1 1 S3 5 8 15 9 10 Demand 7 5 3 2 17
munotes.in
Page 70
70 3
ASSIGNMENT PROBLEMS
Unit Structure:
3.0 Objectives
3.1 Introduction
3.2 Hungarian Method of Solution
3.3 Special Cases in Assignment Problems
3.3.1 Unbalanced Problems
3.3.2 Multiple Optimum Solutions
3.3.3 Maximization Problems
3.4 Summary
3.5 Self-Assessment Questions
3.0 OBJECTIVES
The learning objectives of Game Theory are as follows :
1. To understand the concepts of assignment problems.
2. To allocate different jobs to different machines, different jobs to
different employees on one to one basis.
3. To ut ilize maximum efficiency of employees and machine to get
maximum output and with minimum duration of completion of tasks.
4. To study different methods of assignments in detail.
3.1 INTRODUCTION
Assignment is the particular type of optimization technique whe re object
is to allocate limited resources to maximize the profit. In general,
assignment is the method allocating limited organizational resources such
as manpower, machine to different jobs. Hence assignment problems are
the optimization problem to alloc ate jobs to different machines or to
workers, salesmen to the sales zone or to allocate vehicles to different
routes. Assignment works on one to one basis i.e. one resource to the one
unit likewise.
All assignments are done in order to allocate scare resou rces to machines
or jobs so as to maximize the efficiency or output of the machine or
worker. Assignment problems have same number of rows and columns for
allocating resources properly on one to one basis. If this situation is not munotes.in
Page 71
71
Assignment Problems satisfied, this may becom e unbalanced problem and it can be converted to
the balanced assignment problems by adding dummy row or column to
make it balanced problem and solution can be found out by using
Hungarian Assignment Method or special case solutions. Let us study
these conc epts thoroughly one by one as follows
3.2 HUNGARIAN METHOD OF SOLUTION
The Statistician Hungarian put forward the method of finding solution to
the assignment problems called as Hungarian Assignment Method
(HAM). This method is used for minimization cases of optimization
problems. This method is faster, easier and more efficient to find out
the solutions to the Assignment Problems. The steps of finding
solutions using Hungarian Assignment Method (HAM) are as follows :
Step 1. Verifying Balanced or Unbalanced assignment problem
The first step is to find out the balanced or unbalanced assignment
problem. This can be done by considering equality of rows and columns.
If the number of rows is equal to the number of columns then this is
balanced assignment problem . If the number of rows is not equal to the
number of columns then this is unbalanced assignment problem.
The balanced assignment problem is required for next step.
Step 2. Row Subtraction
In the balanced assignment problem, we have to find the smallest element
from each row. Then subtract that smallest element of row from every
element of corresponding row. This step is row subtraction.
Step 3. Column Subtraction
In the reduced assignment problem, we have to find the smallest element
from each column. Then subtract that smallest element of column from
every element of corresponding column. This step is column subtraction.
Step 4. Line Formation
Then form the lines using maximum number of zeros either in row or in
column as first line and next lines are formed using the same principle of
maximum number of zeros either in row or in column as second line and
so on.
Step 5. Comparing Number of lines with Number of rows and
Number of Columns
In the assignment problems, as jobs are assigned to machines or me n on
one to one basis, the number of rows and number of columns are already
same. Here we have to verify the number of lines formed with number of
rows and number of columns, if they are same then direct allocation is
possible otherwise improvement has to be done. Let us discuss these facts
in detail as follows
munotes.in
Page 72
72
Operation Research i. If number of lines formed are same as number of rows and number of
columns then direct allocation is possible as follows
The allocation is one by considering the only one zero available in the
row or column. Then second time same thing is observed (only one zero
available) and remaining zero in the related column or row are cancelled
accordingly as the allocations are done on one to one basis. The procedure
is repeated until and unless all allocati ons or assignments are done.
ii. If number of lines formed are not same as number of rows and number
of columns then direct allocation is possible as follows
Then Hungerian Assignment Method (HAM) is used.
Step 6. Hungerian Assignment Method (HAM)
If number of lines formed are not same as number of rows and number of
columns then Hungerian Assignment Method (HAM) is used
As the lines are formed, few rows and columns are cancelled. The matrix
is turned into reduced matrix with remaining elements of matrix th at are
not cancelled. Few lines cross each other and crossing points are called as
junction point.
The smallest element in the remaining reduced matrix is subtracted from
all elements of reduced matrix so that one additional zero is obtained at
the loca tion of smallest element of that remaining reduced matrix and that
leads to the chance of formation of new line. At the junction point, that
smallest number is to be added.
The allocation is one by considering the only one zero available in the row
or col umn. Then second time same thing is observed (only one zero
available) and remaining zero in the related column or row are cancelled
accordingly as the allocations are done on one to one basis. The procedure
is repeated until and unless all allocations or assignments are done.
Step 7. Assignments
The allocations or assignments are done on one to one basis so that every
row and column as one allocation. It means that each worker or machine
has one job to be done in minimum time.
Let us study these all step s by practical examples.
Example 1. A job requires four different activities - Sorting, Washing,
Finishing and Assembling. Four workers are assigned all these activities.
The time required by each worker to complete four different activities -
Sorting, Wash ing, Finishing and Assembling are given below
munotes.in
Page 73
73
Assignment Problems Worker 1 Worker 2 Worker 3 Worker 4 Sorting 31 25 33 25 Washing 25 24 23 21 Finishing 19 21 23 24 Assembling 38 36 34 40
How should these activities be arranged to the workers so that the job is
complet ed in minimum time?
Solution:
This is an assignment problem as 4 activities are assigned to 4 workers on
one to one basis. Our objective is to minimize time of completion of work
by assigning proper activities to workers.
Step 1. Verifying Balanced or Un balanced assignment problem
The first step is to find out the balanced or u nbalanced assignment
problem. This can be done by considering equality of rows and columns.
If the number of rows is equal to the number of columns then this is
balanced assignmen t problem. If the number of rows is not equal to th e
number of columns then this is unbalanced assignment problem.
Here the number of rows r=4 and number of columns c=4 and hence this
is balanced assignment problem (r=c=4).
The balanced assignment probl em is required for next step.
Step 2. Row Subtraction
In the balanced assignment problem, we have to find the smallest element
from each row. Then subtract that smallest element of row from every
element of corresponding row. This step is row subtractio n.
Here, sorting activity is given in the first row and smallest element in the
first row is 25. Subtract 25 from each element of first row. Similarly for
the second row, washing activity is given in the second r ow and smallest
element in the second row is 21. Subtract 21 from each elemen t of second
row. For the third row, finishing activity is given in the third row and
smallest element in the third row is 19. Subtract 19 from each elemen t of
third row. For the fourth row, assembling activity is given in the fourth
row and smallest element in the fourth row is 34. Subtract 34 from each
element of fourth row. We get
munotes.in
Page 74
74
Operation Research Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6
Step 3. Column Subtractio n
In the reduced assignment problem, we have to find the smallest element
from each column. Then subtract that smallest elemen t of column from
every element of corresponding column. This step is column subtraction.
Here, worker 1 is given in the first c olumn and smallest element in the
first column is 0. Subtract 0 from each element of first column. Similarly
for the second column, worker 2 is given in the second column and
smallest element in the second column is 0. Subtract 0 from each element
of secon d column. For the third column, worker 3 is given in the third
column and smalle st element in the third column is 0. Subtract 0 from
each element of third column. For the fourth column, worker 4 is given in
the fourth column and smallest element in the fou rth column is 0. Subtract
0from each element of fourth column. We get
Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6
Step 4. Line Formation
Then form the lines using maximum number of ze ros either in row or in
column as first line and next lines are formed using the same principle of
maximum number of zeros either in row or in column as second line and
so on.
First row Sorting and fourth column W orker 4 has two zeroes. So, we may
form fir st line in the first row or in the fo urth column and other rows and
columns have only one zero in their pattern. So, le t us try with first row
having two zeroes as maximum number of zeroes as follows
munotes.in
Page 75
75
Assignment Problems Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6
Next see that second, third and fourth rows have only one zero similarly
first, second, third and fourth columns have only one zero and we may
proceed either row wise or column wise. For the pu rpose of
convenience, consider second, third and fourth rows have only one zero
for line formation as follows
Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6
Step 5. Comparing Number o f lines with Number of rows and
Number of Columns
Here we have to verify the number of lines formed with number of rows
and number of columns, if they are same then direct al location is
possible otherwise improvement has to be done. Let us discuss these f acts
in detail as follows :
The number of lines formed (4) are same as number of rows (4) and
number of columns (4) then direct allocation is possible as follows
The allocation is done by considering the only one zero available in the
row or column. Then second time same thing is observed (only one zero
available) and remaining zero in the related column or row are cancelled
accordingly as the allocations are done on one to one basis. The procedure
is repeated until and unless all allocations or assignment s are done.
Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6 munotes.in
Page 76
76
Operation Research In the second row, only one zero is available which is at the junction of
worker 4 and washing. It means that washing can be done by worker 4. If
worker 4 is busy with washing then he can’t do other task sorting. Hence
sorting can be done by worker 2 (zero availability) as follows
Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0✔ 8 0✖ Washing 4 3 2 0✔ Finishing 0✔ 2 4 5 Assem bling 4 2 0✔ 6
Step 7. Assignments
The allocations or assignments are done on one to one basis so that every
row and column as one allocation. It means that each worker or machine
has one job to be done in minimum time. The single zero in row or
column i ndicates relative cell position to be selected for assignment
purpose as follows
Sr. No. Activities Worker Time (in minutes) 1 Sorting 2 25
2 Washing 4 21
3 Finishing 1 19
4 Assembling 3 34
Total time 99 minutes
These activities should be arrange d to the workers in above assignment so
that the job is completed in minimum 99 minutes.
HAM for improvement type assignment problems
Example 2: The five different machines A, B, C, D and E perform five
different tasks 1, 2, 3, 4 and 5. The costs for per forming each task (in lack
rupees) are given below
1 2 3 4 5
A 8 8 8 11 12
B 4 5 6 3 4
C 12 11 10 9 8
D 18 21 18 17 15
E 10 11 10 8 12
munotes.in
Page 77
77
Assignment Problems How you will assign different tasks to different machines one to one basis
so that the total cost of productio n should be minimum?
Solution:
This is an assignment problem as 5 tasks are assigned to 5 machines on
one to one basis. Our objective is to minimize total cost of production by
assigning proper tasks to machines.
The steps for assignment are as follows :
Step 1. Verifying Balanced or Unbalanced assignment problem
The first step is to find out the balanced or unbalanced assignment
problem. This can be done by considering equality of rows and columns.
If the number of rows is equal to the number of column s then this is
balanced assignment problem. If the number of rows is not equal to the
number of columns then this is unbalanced assignment problem.
Here, the number of tasks and machines are 5 and 5 respectively. Hence
this is balanced assignment proble m.
The balanced assignment problem is required for next step.
Step 2. Row Subtraction
In the balanced assignment problem, we have to find the smallest element
from each row. Then subtract that smallest element of row from every
element of corresponding row. This step is row subtraction.
Here machine A is at first row and the smallest element in the first row is
8. Subtract 8 from every element of first row. Mach ine B is at second row
and the smallest element in the second row is 3. Subtract 3 from ever y
element of second row. Similarly, for third, fourth and fifth row, activities
are carried out as follows
1 2 3 4 5
A 0 0 0 3 4
B 1 2 3 0 1
C 4 3 2 1 0
D 3 6 3 2 0
E 2 3 2 0 4
Step 3. Column Subtraction
In the reduced assignment problem, we have to find the smallest element
from each column. Then subtract that smallest elemen t of column from
every element of corresponding column. This step is column subtraction.
munotes.in
Page 78
78
Operation Research Every column has smallest element 0 and henc e subtracting smallest
element from ever y element of first column will lead to same reduced
assignment table.
1 2 3 4 5
A 0 0 0 3 4
B 1 2 3 0 1
C 4 3 2 1 0
D 3 6 3 2 0
E 2 3 2 0 4
Step 4. Line Formation
Then form the lines using maximum number of ze ros either in row or in
column as fir st line and next lines are formed using the same principle of
maximum number of zeros either in row or in column as second line and
so on.
1 2 3 4 5
A 0 0 0 3 4
B 1 2 3 0 1
C 4 3 2 1 0
D 3 6 3 2 0
E 2 3 2 0 4
By observation, it is found that the first row ha s maximum (3) zeroes and
hence first line formed is in first row. Fourth and fifth co lumns have (2)
maximum zeroes for the next time. Hence second and third lines are
formed at Fourth and fifth columns. There are no other zeroes available
and hence line formation is as follows
1 2 3 4 5
A 0 0 0 3 4
B 1 2 3 0 1
C 4 3 2 1 0
D 3 6 3 2 0
E 2 3 2 0 4
munotes.in
Page 79
79
Assignment Problems Step 5. Comparing Number of lines wit h Number of rows and
Number of Columns
In the assignment problems, as tasks are assigne d to machines o r men on
one to one basis, the number of rows and number of columns are already
same. Here we have to verify the number of lines formed with number of
rows and number of columns, if they are same then direct al location is
possible otherwise improvement has to be done. Let us discuss t hese facts
in detail as follows:
The number of lines formed (3) are not same as number of rows (5) and
number of columns (5) then direct allocation is possible as follows
Then Hungerian Assignment Method (HAM) is used.
Step 6. Hungerian Assignment Method (HAM)
If number of lines formed are not same as number of rows and number of
columns then Hungerian Assignment Method (HAM) is used
The smallest element in the remaining reduced matrix is subtracted from
all elements of re duced matrix so that one additional zero is obtained at
the location of smallest element of that remaining reduced matrix and that
leads to the chance of formation of new line. At the junction point, that
smallest number is to be added.
The allocation is o ne by considering the only one zero available in the row
or column. Then second time same thing is observed (only one zero
available) and remaining zero in the related column or row are cancelled
accordingly as the allocations are done on one to one basis. The procedure
is repeated until and unless all allocations or assignments are done.
1 2 3 4 5
A 0 0 0 3 4
B 1 2 3 0 1
C 4 3 2 1 0
D 3 6 3 2 0
E 2 3 2 0 4
The smallest element in the reduced assignment matrix is 1. Subtract that
smallest element 1 from all elements of reduced assignment matrix. Add
that smallest element at two junctions point A4 and A5 as follows :
The number of lines formed (4) are not same as number of rows (5) and
number of columns (5) then direct allocation is not possible as follows :
Line formation: As second row has zero, this is cancelled as below
munotes.in
Page 80
80
Operation Research 1 2 3 4 5
A 0 0 0 4 5
B 0 1 2 0 1
C 3 2 1 1 0
D 2 5 2 2 0
E 1 2 1 0 4
Here the smallest element in the remaining reduced matrix is 1, subtracted
from all elements of reduced matrix so that one additional zero is obtained
at the location of smallest element of that remaining reduced matrix and
that leads to the chance of formation of new line. At the junction point,
that smallest number (1) is to be added.
Step 7. Line formation:
As third column has 2 zeroes and hence this is cancelled as follows
1 2 3 4 5
A 0 0 0 5 6
B 0 1 2 1 2
C 2 1 0 1 0
D 1 4 1 2 0
E 0 1 0 0 4
Step 8 . Comparing number of lines formed and with number of rows
and columns
The number o f lines formed (5) are same as number of rows (5) and
number of columns (5) then direct allocation is possible as follows
Step 9 . Assignments
The allocations or assignments are done on one to one basis so that every
row and column as one allocation. It me ans that each worker or machine
has one job to be done in minimum time.
The allocation is done by considering the only one zero available in the
row or column. Then second time same thing is observed (only one zero
available) and remaining zero in the rel ated column or row are cancelled
accordingly as the allocations are done on one to one basis. The procedure
is repeated until and unless all allocations or assignments are done.
munotes.in
Page 81
81
Assignment Problems 1 2 3 4 5
A 0 0 0 5 6
B 0 1 2 1 2
C 2 1 0 1 0
D 1 4 1 2 0
E 0 1 0 0 4
Now the second column has only one zero and hence it will be selected at
first.
1 2 3 4 5
A 0✖ 0✔ 0✖ 5 6
B 0 1 2 1 2
C 2 1 0 1 0
D 1 4 1 2 0
E 0 1 0 0 4
As machine A is busy with task 2, it can’t perform any other tasks like 1
and 3 (having zero values)
Now the machine D has only one zero and hence it can perform only 5th
task.
1 2 3 4 5
A 0✖ 0✔ 0✖ 5 6
B 0 1 2 1 2
C 2 1 0 1 0✖
D 1 4 1 2 0✔
E 0 1 0 0 4
Now machine C is capable of performing task 3 as follows
1 2 3 4 5
A 0✖ 0✔ 0✖ 5 6
B 0 1 2 1 2
C 2 1 0✔ 1 0✖
D 1 4 1 2 0✔
E 0 1 0 0 4
munotes.in
Page 82
82
Operation Research As task 3 is already taken up by machine C t hen machine E cant’ do that
task and machine E performs 4th task as follows
1 2 3 4 5
A 0✖ 0✔ 0✖ 5 6
B 0 1 2 1 2
C 2 1 0✔ 1 0✖
D 1 4 1 2 0✔
E 0✖ 1 0✖ 0✔ 4
Now task 1 can be performed by machine B as follows
1 2 3 4 5
A 0✖ 0✔ 0✖ 5 6
B 0✔ 1 2 1 2
C 2 1 0✔ 1 0✖
D 1 4 1 2 0✔
E 0✖ 1 0✖ 0✔ 4
The allocation or assignment of different task s to different machines are as
follows
Sr. No. Machine Task Cost of task
1 A 2 8
2 B 1 4
3 C 3 10
4 D 5 15
5 E 4 8
Total cost of production (in lack rupees) 45
3.3 SPECIAL CASES IN ASSIGNMENT PROBLEMS
The special cases in assignment problems are unbalanced problems,
multiple optimum solution, maximization problems and prohibited
assignments as follows :
3.3.1 Unbalanced Problems
When the number of rows is no t equal to the number of columns then this
is unbalanced assignment problem. While solving it, we have to convert it munotes.in
Page 83
83
Assignment Problems to balanced problem either by adding dummy row or column as per the
requirement and rest steps are similar.
Example 3: The 3 seminar slots are available for 4 MMS students. Now
Professor wants to conduct seminars within minimum time slots available
to students. The slots and students names are given below within cells
representing time required for completing seminar .
Students Slot1 Slot2 Slot3
Aaradhya 40 29 32
Aadvet 42 25 35
Vedika 35 22 38
Shrived 36 26 33
How will you assign slots to students so that minimum time slots are
available to students?
Solution: As 3 slots are available to 4 students, one student is remaining
with the slot . Hence dummy slot may be added to make it equal (number
of rows and number of columns will be made same by adding dummy
column) as follows
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 40 29 32 0
Aadvet 42 25 35 0
Vedika 35 22 38 0
Shrived 36 26 33 0
Step 1. Verifying Balanced or Unbalanced assignment problem
The number of rows (4) is equa l to the number of columns (4) hence , this
is balanced assignment problem. The balanced assignment problem is
required for next step.
Step 2. Row Subtraction
In the balanced assignment problem, we have to find the smallest element
from each row. Then subtract that smallest element of row from every
element of corresponding row. This step is row subtraction.
In all rows, smallest element is zero and hence assignme nt problem
remains unchanged.
munotes.in
Page 84
84
Operation Research Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 40 29 32 0
Aadvet 42 25 35 0
Vedika 35 22 38 0
Shrived 36 26 33 0
Step 3. Column Subtraction
In the reduced assignment problem, we have to find the smallest element
from eac h column. Then subtract that smallest element of column from
every element of corresponding column. This step is column subtraction.
The smallest element in the first column is 35 and subtracts 35 from all
elements of first column and so on
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0
Aadvet 7 3 3 0
Vedika 0 0 6 0
Shrived 1 4 1 0
Step 4. Line Formation
Then form the lines using maximum number of zeros either in row or in
column as first line and next lines are formed using the same principl e of
maximum number of zeros either in row or in column as second line and
so on.
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0
Aadvet 7 3 3 0
Vedika 0 0 6 0
Shrived 1 4 1 0
First line is formed by four zeroes available in the fourth column and
second line is formed by two zeroes in the third row and third column
contains only one zero available forming third line as follows
munotes.in
Page 85
85
Assignment Problems Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0
Aadvet 7 3 3 0
Vedika 0 0 6 0
Shrived 1 4 1 0
Step 5. C omparing Number of lines with Number of rows and
Number of Columns
In the assignment problems, as jobs are assigned to machines or men on
one to one basis, the number of rows and number of columns are already
same. Here we have to verify the number of line s formed with number of
rows and number of columns, if they are same then direct allocation is
possible otherwise improvement has to be done. Let us discuss these facts
in detail as follows
The number of lines formed (3) are not same as number of rows (4) and
number of columns (4)then direct allocation is possible as follows
Then Hungerian Assignment Method (HAM) is used.
Step 6. Hungerian Assignment Method (HAM)
If number of lines formed (3) are not same as number of rows (4) and
number of columns (4) t hen Hungerian Assignment Method (HAM) is
used
As the lines are formed, few rows and columns are cancelled. The matrix
is turned into reduced matrix with remaining elements of matrix that are
not cancelled. Few lines cross each other and crossing points are called as
junction point.
The smallest element in the remaining reduced matrix is subtracted from
all elements of reduced matrix so that one additional zero is obtained at
the location of smallest element of that remaining reduced matrix and that
leads to the chance of formation of new line. At the junction point, that
smallest number is to be added.
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0
Aadvet 7 3 3 0
Vedika 0 0 6 0
Shrived 1 4 1 0
munotes.in
Page 86
86
Operation Research The smallest element (1) in the remaining r educed matrix is subtracted
from all elements of reduced matrix so that one additional zero is obtained
at the location of smallest element of that remaining reduced matrix and
that leads to the chance of formation of new line. At the junction points 6
and 0, that smallest number (1) is to be added.
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0
Aadvet 6 2 3 0
Vedika 0 0 7 1
Shrived 0 3 1 0
Step 7. One additional line is formed and hence total 4 lines are formed
and are equal to the number of rows (4) and number of columns (4).
Hence Assignment is done as follows
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0
Aadvet 6 2 3 0
Vedika 0 0 7 1
Shrived 0 3 1 0
Step 8. Assignments
The allocations or assignments are done on one to one basis so that every
row and column as one allocation. It means that each worker or machine
has one job to be done in minimum time.
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0
Aadvet 6 2 3 0
Vedika 0 0 7 1
Shrived 0 3 1 0
The second row is having only one zero and hence allocation to Aadvet is
dummy slot. As dummy slot is taken by Aadvet and hence dummy slot
can‘t be given to any other student. For the slot2, only one zero is
available at third row. Similarly for the slot3, only one zero is available at
first row and the assignment problem takes the following form. munotes.in
Page 87
87
Assignment Problems
Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0✔ 0✖
Aadvet 6 2 3 0✔
Vedika 0✖ 0✔ 7 1
Shrived 0✔ 3 1 0✖
The Fourth row Shrived is having zero at slot 1 and hence slot 1 can not be
taken by Vedika as follows
Sr. No. Name of the
student Time slot Time (in
minutes)
1 Aaradhya Slot3 32
2 Aadvet Slot4 00* Dummy
3 Vedika Slot2 22
4 Shrived Slot1 36
* Dummy values are not known and are considered for the purpose of
making allocations or assignments.
3.3.2 Multiple Optimum Solutions
When the assignment problem has more than one solution, this is ter med
as multiple optimum solutions to the assignment prob lem. The minimum
two solutions exist for multiple optimum solutions. Hence there are
possibilities of getting different solutions. We can compare solutions and
get the optimum solution required.
Examp le 4. The railway ticket window has 4 reservatio n counters. Four
employees are assigned these tasks of reservation counters. The cost of
assigning each person to each counter is as follows
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 1 8 15 22
Aadvet 13 18 23 28
Vedika 13 18 23 28
Shrived 19 23 27 31
munotes.in
Page 88
88
Operation Research Solution:
Step 1. Verifying Balanced or Unbalanced assignment problem
The number of rows (4) is equa l to the number of columns (4) hence, this
is balanced assignment problem. The balanc ed assignment problem is
required for next step.
Step 2. Row Subtraction
In the balanced assignment problem, we have to find the smallest element
from each row. Then subtract that smallest element of row from every
element of corresponding row. This step is row subtraction.
In first row, the smallest element is 1 and In second and third rows, the
smallest elements are 13 and in the fourth row, the smallest element is 19.
Subtract these smallest elements from all corresponding rows and then we
get
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 7 14 21
Aadvet 0 5 10 15
Vedika 0 5 10 15
Shrived 0 4 27 12
Step 3. Column Subtraction
In the reduced assignment problem, we have to find the smallest element
from each column. Then subtract that smallest element of column from
every element of corresponding column. This step is column subtraction.
The smallest element in the first column is 0 and subtracts 0 from all
elements of first column and so on
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 3 4 9
Aadvet 0 1 0 3
Vedika 0 1 0 3
Shrived 0 0 17 0
Step 4. Line Formation
Then form the lines using maximum number of zeros either in row or in
column as first line and next lines are formed using the same principle of
maximum nu mber of zeros either in row or in column as second line and
so on.
munotes.in
Page 89
89
Assignment Problems First line is formed by four zeroes available in the first column and second
line is formed by two zeroes in the third column and second and fourth
column contains only one zero available forming third and fourth lines as
follows
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 3 4 9
Aadvet 0 1 0 3
Vedika 0 1 0 3
Shrived 0 0 17 0
Step 5. Comparing Number of lines with Number of rows and
Number of Columns
In the assig nment problems, as jobs are assigned to machines or men on
one to one basis, the number of rows and number of columns are already
same. Here we have to verify the number of lines formed with number of
rows and number of columns, if they are same then direc t allocation is
possible otherwise improvement has to be done. Let us discuss these facts
in detail as follows
The number of lines formed (4) are same as number of rows (4) and
number of columns (4) then direct allocation is possible as follows
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 3 4 9
Aadvet 0 1 0 3
Vedika 0 1 0 3
Shrived 0 0 17 0
Step 8. Assignments
The allocations or assignments are done on one to one basis so that every
row and column as one allocation. It means tha t each worker or machine
has one job to be done in minimum time.
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 3 4 9
Aadvet 0 1 0 3
Vedika 0 1 0 3
Shrived 0 0 17 0 munotes.in
Page 90
90
Operation Research As first row has only one zero. Aaradhya will serve to Reservation
Counter 1 and As Reservation Counter 1 is served by Aaradhya and hence
it can ’t be served by any other employee. Similarly, second and fourth
columns have single zeroes. Hence allocation is direct there.
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0✔ 3 4 9
Aadvet 0✖ 1 0✔ 3
Vedika 0✖ 1 0✔ 3
Shrived 0✖ 0✔ 17 0✔
As reservation counter 3 is occupied by the Aadvet and Vedika both so
assignment solution is not optimum.
Hence again repeat the process.
Step 9. Row subtraction
As every row h as zero element and then row subtraction is not possible.
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0✔ 3 4 9
Aadvet 0✖ 1 0✔ 3
Vedika 0✖ 1 0✔ 3
Shrived 0✖ 0✔ 17 0✔
Step 10. Column subtraction
Employee Reservation counter (Rc)
Rc1 Rc2 Rc3 Rc4
Aaradhya 0 3 4 9
Aadvet 0 1 0 3
Vedika 0 1 0 3
Shrived 0 0 17 0
munotes.in
Page 91
91
Assignment Problems Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0✔ 0✖
Aadvet 6 2 3 0✔
Vedika 0✖ 0✔ 7 1
Shrived 0✔ 3 1 0✖
The Fourth row Shrived is having zero at slot 1 and hence slot 1 can not be
taken by Vedika as follows
Sr. No. Name of the
student Time slot Time (in
minutes)
1 Aaradhya Slot3 32
2 Aadvet Slot4 00* Dummy
3 Vedika Slot2 22
4 Shrived Slot1 36
* Dummy values are not known and are considered for the purpose of
making
3.3.3 Maximization Problems
The maximization problems are the assignment problems related to profit,
sales or output maximization or any other units that are required to be
maximized. The optimization techniques used here is to maximize the
sales, pro fit or any other objective of assignment problem. The given
maximization matrix is transformed into a relative loss matrix by
subtracting every element from the largest element of the assignment
matrix. The next steps are similar to the HAM assignment prob lems. All
steps are designed to find out the relative position of allocation or
selection of given alternatives from set of all combinations of alternatives
as follow
Example 5 . A marketing manager has five salesmen and five sales
districts. Considering th e capabilities of the salesmen and the nature of
districts, the marketing manager estimates that sales per month (in
hundred rupees) for each salesman in each district would be as follows
munotes.in
Page 92
92
Operation Research
Salesmen Districts
A B C D E
1 32 38 40 28 40
2 40 24 28 21 36
3 41 27 33 30 37
4 22 38 41 36 36
5 29 33 40 35 39
Find the assignment of salesmen to districts that will result in maximum
sales.
Solution:
Step 1. The given assignment problem is to maximize sales by proper
assignment of salesmen to differ ent districts. Hence this is maximization
problem of assignment.
Step 2. Convert into minimization
This can be done by selecting the largest element (41) of the given
problem and subtract it from all elements to form relative loss matrix
called opportunity loss matrix as follows
Salesmen Districts
A B C D E
1 9 3 1 13 1
2 1 17 13 20 5
3 0 14 8 11 4
4 19 3 0 5 5
5 12 8 1 6 2
munotes.in
Page 93
93
Assignment Problems Step 3. Row subtraction
Salesmen Districts
A B C D E
1 8 0 0 7 0
2 0 16 12 19 4
3 0 14 8 11 4
4 19 3 0 5 5
5 11 7 0 5 1
Step 4. Column subtraction
Salesmen Districts
A B C D E
1 8 0 0 2 0
2 0 16 12 14 4
3 0 14 8 6 4
4 19 3 0 0 5
5 11 7 0 0 1
Step 5. Line formation
Salesmen Districts
A B C D E
1 8 0 0 2 0
2 0 16 12 14 4
3 0 14 8 6 4
4 19 3 0 0 5
5 11 7 0 0 1
munotes.in
Page 94
94
Operation Research The formed lines (4) are less than 5 rows and 5 columns. Hence
improvement can be done by subtracting smallest element (4) from all
elements of reduced matrix and adding this smallest element to the
junction point so as to develop a chance of forming new line.
Salesmen Districts
A B C D E
1 12 0 0 2 0
2 0 12 8 10 0
3 0 10 4 2 0
4 23 3 0 0 5
5 15 7 0 0 1
Step 6. Line formation
Salesmen Districts
A B C D E
1 12 0 0 2 0
2 0 12 8 10 0
3 0 10 4 2 0
4 23 3 0 0 5
5 15 7 0 0 1
The formed lines (5) are equal to 5 rows and 5 columns. Hence
direct allocation is possible as follows
Salesmen Districts
A B C D E
1 12 0✔ 0✖ 2 0✖
2 0 12 8 10 0
3 0 10 4 2 0
4 23 3 0 0 5
5 15 7 0 0 1 munotes.in
Page 95
95
Assignment Problems Now there are two alternatives for A district as
i. Salesman 2 is given an opportunity to serve in A district.
ii. Salesman 3 is given an opportunity to serve in A district.
Salesmen Districts
A B C D E
1 12 0✔ 0✖ 2 0✖
2 0✔ 12 8✖ 10 0✖
3 0✖ 10 4 2 0✔
4 23 3 0 0 5
5 15 7 0 0 1
There are two additional conditions in first alternative as
a. Salesman 4 is given an opportunity to serve in C district.
b. Salesman 5 is given an oppo rtunity to serve in C district.
Let us study (a) option from first alternative as follows
Salesmen Districts
A B C D E
1 12 0✔ 0✖ 2 0✖
2 0✔ 12 8✖ 10 0✖
3 0✖ 10 4 2 0✔
4 23 3 0✔ 0✖ 5
5 15 7 0✖ 0✔ 1
Allocations are made as follows
Sr. No . Salesman District Sales (in Hundred
rupees)
1 1 B 38
2 2 A 40
3 3 E 37
4 4 C 41
5 5 D 35
Total sales 191 munotes.in
Page 96
96
Operation Research Second option: Salesman 5 is given an opportunity to serve in C district.
Let us study (a) option from first alternative as follows
Salesmen Districts
A B C D E
1 12 0✔ 0✖ 2 0✖
2 0✔ 12 8 10 0✖
3 0✖ 10 4 2 0✔
4 23 3 0✖ 0✔ 5
5 15 7 0✔ 0✖ 1
Allocations are made as follows
Sr. No. Salesman District Sales (in
Hundred
rupees)
1 1 B 38
2 2 A 40
3 3 E 37
4 4 D 36
5 5 C 40
Total sales 191
3.4 SUMMARY
Assignment problems are the optimization problem to allocate jobs to
different machines or to workers, salesmen to the sales zone or to allocate
vehicles to different routes. Assignment works on one to one basis i.e. one
resource to the one unit likewise.
Hungarian A ssignment Method (HAM ) is used for minimization cases of
optimization problems. This method is faster, easier and more efficient to
find out the solutions to the Assignment Problems. When the assignment
problem has more than o ne solution, this is termed as multiple optimum
solutions to the assignment prob lem. The minimum two solutions exist for
multiple optimum solutions. Hence there are poss ibilities of getting
different solutions. We can compare solutions and get the optimum
solution required. The maximiz ation problems are the assignment
problems related to profit, sales or output maximization or any other units munotes.in
Page 97
97
Assignment Problems that are required to be maximized. The optimization techniques used here
is to maximize the sales, profit or any other objective of assignment
problem. The given maximization matrix is transformed into a relative
loss matrix by subtracting every element from the largest element of the
assignment matrix. The next steps are similar to the HAM assignment
problems.
3.5 SELF -ASSIGNMENT QUESTIONS.
1. What is an assignment problem? What are the types of assignment
problems?
2. What are the steps of solving assignment problem?
3. Five jobs are assigned to five persons, each person will do one job only.
The expected time (in hours) required for each jo b for each person have
been estimated and are shown in the following table. Determine the
optimal assignments.
Job Person
1 2 3 4 5
A 12 15 13 14 15
B 16 18 15 14 16
C 18 16 15 18 20
D 15 20 18 17 19
E 16 15 18 14 15
4. A company has a team of fou r salesmen and there are four districts
where the company wants to start its business. The following is the profit
per day in rupees for each salesman in each district. Find the assignment
of salesmen to districts which will yield maximum profit.
Salesman District
D1 D2 D3 D4
A 16 10 14 11
B 14 11 15 15
C 15 15 13 12
D 13 12 14 15
munotes.in
Page 98
98 4
GAME THEORY
Unit Structure:
4.0 Objectives
4.1 Introduction
4.2 Meaning and Concept of Game Theory
4.3 Terminologies in Game Theory
4.4 Types of Game
4.4.1 Pure Strategy Game
4.4.2 Mixed Strategy Game
4.5 Principle of Dominance
4.6 Limitati ons of Game Theory
4.7 Summary
4.8 Self-Assessment Questions
4.0 OBJECTIVES
The learning objectives of Game Theory are as follows :
1. To understand and decide winning strategies in a competitive business
world.
2. To study the concepts and terminologies of Game Theory.
3. To solve complex business situation and to assist in decision making
by using game strategies.
4. To analyse the business game and solve it by using pure strategy
game, mixed strategy game and principle of dominance.
4.1 INTRODUCTION
Today, bus iness world is complex, dynamic, and competitive in nature.
The monopoly is quite observed. There are many rivals in the business
and environ is competitive in the industry. Every business firm tries to
achieve success (win) by maximizing profit by defeati ng other rivalry
players in the business world. Hence every business firm tries to win the
game by defeating other players in the game using different strategies.
munotes.in
Page 99
99
Game Theory 4.2 MEANING AND CONCEPT OF GAME THEORY
Game Theory is the competitive situation of business players in the
business competitive environment. Game theory is the study of operations
research technique involving appropriate use of strategies to win the
game. Thus Game theory is the branch of Operations Research dealing
with quantitative decision mak ing when at least two players are involved
in the conflicting and competitive environment, resulting in success and
failure of players.
4.3 TERMINOLOGIES IN GAME THEORY
4.3.1 Strategy: The possible alternatives or available course of action
that may be a dopted to win the game. For example, In order to earn more
profit, either selling price should be decreased to have more sales or cost
of production should be lowered.
4.3.2 Player: Each participant of game is called Player. There are at least
two players. One is considered as maximizing player (winner of the game)
and other is assumed as minimizing player (looser of the game). But
practically, such ideal situation may not come in reality.
4.3.3 Play: A play happens when each player select a particular stra tegy
from all available strategies.
4.3.4 Pay off: The outcome of playing a game is known as Pay off. The
Pay off is the net gain or profit earned by using appropriate strategy by the
winning player.
4.3.5 Pay off Matrix: Pay off matrix is the table of ga me theory
representing the two players out of which One is considered as
maximizing player (winner of the game) and other is assumed as
minimizing player (looser of the game).
4.3.6 Optimum Strategy: The optimum strategy is the strategy used by
the maximiz ing player against the strategies used by the competing
minimizing players.
4.3.7 Value of the Game: It is the expected outcome of the game theory
when all players use their optimum strategy. If the value of the game is
zero then game is said to be the fair game otherwise if the value of the
game is not zero then game is said to be the unfair game.
4.4 TYPES OF GAMES
Game is a particular business situation where at least two players are
involved to overcome the other player using optimum strategy and to get
maximum output using different strategies . The types of games are as
follows
a. Two Person Game
b. Multiple Person Game
c. Zero Sum Game munotes.in
Page 100
100
Operation Research d. Non-Zero Sum Game
e. Two Person Zero Sum Game
These are explained as follows
a. Two Person Game: When there are two players in volved in the
game, then this is termed as two person game. One is considered as
maximizing player and other is considered as minimizing player.
b. Multiple Person Game: When there are more than two players
involved in the game, then this is termed as multip le person game.
This is also termed as n -person game.
c. Zero Sum Game: Zero sum means addition becomes equal to zero.
When the sum of gains of all winners is equal to the sum of losses of
all the losers, this condition of game is called zero sum game.
d. Non-Zero Sum Game: When the sum of gains of all winners is not
equal to the sum of losses of all the losers, this condition of
game is called non -zero sum game.
e. Two Person Zero Sum Game: In the two person game, when the
gain of one player is equal to the loss of other player, such type of
game is termed as Two Person Zero Sum Game.
Two person game having two strategies for each player is called as a two
person 2x2 game involving two rows and two columns in the payoff
matrix.
Based on the type of strategy, Games are again classified as follow
4.4.1 Pure Strategy Game:
In the pure strategy game, players use only one strategy throughout the
game. The pure strategy indicates that there is no other combination of
strategy used by the game player.
4.4.1.1 Steps for solving Pure Strategy Game :
1. Maximizing and Minimizing Player: In the payoff matrix,
maximizing players’ strategy should be written in the row and minimizing
players, strategy should be written in the column.
2. Row Maxi -min Strategy: In the row, maximum values from the
minimum values of the given rows are taken. In simple words, at first row
minima values should be taken for all rows and then maximum value from
all row minima values are taken called as Row Maxi -min value.
3. Column Min i-max Strategy: In the column , minimum values from the
maximum values of the given columns are taken. In simple words, at first
column maxima values should be taken for all columns and then minimum
value from all column maxima values are taken called as Co lumn Mini-
max value.
munotes.in
Page 101
101
Game Theory 4. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min and Column Mini -max values are compared and if these values
are same then there exists a saddle point representing the value of the
game.
5. Saddle Point: The sad dle point is the point of intersection of row and
column of Row Maxi -min and Column Mini -max values. This saddle
point represents the value of the game.
6. One Saddle point and multiple saddle points: If there is only one
saddle point then this represents the value of the game alone. If there is
more than one saddle point, then this represents multiple solutions or
multiple values of the game showing combination of different strategies to
be used in the game strategy.
7. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min and Column Mini -max values are compared and if these values
are not same then there does not exist a saddle point and the game is
mixed strategy game
.
Example 1: Two competing firms A and B are in the local market. They
use different strategies to maximize the profit. Firm A uses two strategies
A1 and A2. Firm B uses three strategies B1, B2 and B3. Their
corresponding pay off matrix is given in the following table as
Firm B
B1 B2 B3
Firm A A1 2 8 4
A2 7 10 6
Solution:
The steps to solve game theory problem is as follows
1. Maximizing and Minimizing Player: Firm A is considered as
maximizing player and firm B is assumed as minimizing player.
Maximizing players’ (Firm A) strategy should be written in the r ow
and minimizing players’ (Firm B) strategy should be written in the
column.
2. Row Maxi -min Strategy: In the row, maximum values from the
minimum values of the given rows are taken. In simple words, at first
row minima values should be taken for all r ows
B1 B2 B3 Row Minima
Firm A A1 2 8 4 2
A2 7 10 6 6
munotes.in
Page 102
102
Operation Research And then maximum value (6) from all row minima values (2 and 6) are
taken called as Row Maxi -min value.
3. Column Mini -max Strategy: In the column , minimum values from the
maxim um values of the given columns are taken. In simple words, at first
column maxima values should be taken for all columns
B1 B2 B3
Firm A A1 2 8 4
A2 7 10 6
Column Maxima 7 10 6
and then minimum value (6) from all column maxima values (7, 10 and 6)
are taken called as Column Mini-max value.
4. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min (6) and Column Mini -max values (6) are compared and if these
values are same then there exists a saddle point (6) representing the value
of the game (6).
5. Saddle Point: The saddle point (A2B3) is the point of intersection of
second row and third column of Row Maxi -min and Column Mini -max
values. This saddle point represents the value of the game.
6. Optimum Strategy and Val ue of the Game :
The optimum strategy corresponding to the saddle point is A2B3
strategies. The value of the game is 6 and Thus for the firm A, strategy A2
is the optimal strategy and it is represented as A (0,1) i.e. probability of
using A1 strategy is 0 a nd probability of using A2 strategy is 100%.
Similarly for the firm B, strategy B3 is the optimal strategy and it is
represented as B (0,0,1) i.e. probability of using B1 and B2 strategies are 0
and probability of using B3 strategy is 100%.
Example 2. A C ompany management and the labour union are
negotiating a new 3 years settlement. Each player has 4 strategies namely
a. Hard and Aggressive Bargaining
b. Reasoning and Logical Approach
c. Legalistic Approach
d. Conciliatory Approach
munotes.in
Page 103
103
Game Theory The cost to the company ( in the f orm of average wage rise in Rs.) are
given for every pair of strategy choices
Union Strategies
A B C D
Company
Strategies A 20 25 40 -5
B 15 14 2 4
C 12 8 10 11
D 35 10 5 0
Which strategy will the two sides adopt? Also determine the value of
game.
Solution:
Solution: The steps to solve game theory problem is as follows
1. Maximizing and Minimizing Player: Company is considered as
maximizing player and Union is assumed as minimizing player. But
Union thinks to be the maximizing player and hence t he transformation of
row and column into column and row takes place.
Maximizing players’ ( Union ) strategy should be written in the row and
minimizing players’ ( Company ) strategy should be written in the column.
Company Strategies
A B C D
Union
Strat egies A 20 15 12 35
B 25 14 8 10
C 40 2 10 5
D -5 4 11 0
2. Row Maxi -min Strategy: In the row, maximum values from the
minimum values of the given rows are taken. In simple words, at first row
minima values should be taken for all rows
Company S trategies
A B C D Row
Minima
Union
Strategies A 20 15 12 35 12
B 25 14 8 10 8
C 40 2 10 5 2
D -5 4 11 0 -5
munotes.in
Page 104
104
Operation Research And then maximum value (12) from all row minima values (12, 8, 2 and -
5) are taken called as Row Maxi -min value.
3. Column Mini -max Str ategy: In the column , minimum values from the
maximum values of the given columns are taken. In simple words, at first
column maxima values should be taken for all columns
Company Strategies
A B C D
Union
Strategies A 20 15 12 35
B 25 14 8 10
C 40 2 10 5
D -5 4 11 0
Column Maxima 40 15 12 35
and then minimum value (12) from all column maxima values (40, 15,12
and 35) are taken called as Column Mini-max value.
4. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min (12) and Colu mn Mini -max values (12) are compared and if
these values are same then there exists a saddle point (12) representing the
value of the game (12).
5. Saddle Point: The saddle point (uAcC) is the point of intersection of
first row and third column of Row Max i-min and Column Mini -max
values. The uA strategy or cell corresponds to the strategy A used by
Union and cC strategy represents to the strategy C used by Company. This
saddle point represents the value of the game.
6. Optimum Strategy and Value of the G ame:
The optimum strategy corresponding to the saddle point is uAcC
strategies. The value of the game is 12 and Thus for the Union, strategy A
is the optimal strategy and it is represented as (1,0,0,0) i.e. probability of
using A strategy is 10%0 and proba bility of using B,C and D strategies are
0%. Similarly for the Company, strategy C is the optimal strategy and it is
represented as (0,0,1,0) i.e. probability of using A,B and D strategies are 0
and probability of using C strategy is 100%.
4.4.2 Mixed Str ategy Game:
In the mixed strategy game, players use different strateg ies throughout the
game. The mixed strategy indicates that there is other combination of
strategies used by the game player.
munotes.in
Page 105
105
Game Theory Mixed strategy games are solved by
1. 2x2 matrix game solution if pay off matrix is having 2 rows and 2
columns otherwise
2. Principle of Dominance strategy is used to solve the problem.
Let us study these two methods as follows :
1. 2x2 matrix game solution
If pay off matrix is having 2 rows and 2 columns then the sol ution of
game theory and their probabilities are obtained as follows
Let us consider ,
p as the probability that A uses strategy A1 and
1-p is the probability that A uses strategy A2.
Similarly ,
q as the probability that B uses strategy B1 and
1-q is the probability that B uses strategy B2.
Consider the pay off matrix
B
B1 (q) B2(1 -q)
A A1(p) a11 a12
A2(1 -p) a21 a22
Where ,
a11 represents the cell position of row 1 and column 1.
a12 represents the cell position of row 1 and column 2.
a21 r epresents the cell position of row 2 and column 1.
a22 represents the cell position of row 2 and column 2.
p as the probability that A uses strategy A1 is obtained by the formula
p= (a22- a21)/D
q as the probability that B uses strategy B1 is obtained b y the formula
q= (a22- a12)/D
and the value of the game is obtained by the formula
v= (a11a22 -a21a12)/D
where , D= denominator= a11+a22 -a21-a12
Example 3. Two business firms A and B are competing in the local
market. Player A is having the choice of two strategies A1 and A2. Player
B is having the choice of two strategies B1 and B2. Determine the
optimum strategy and value of the game using pure strategy and then by
using 2x2 matrix game solution method. munotes.in
Page 106
106
Operation Research Player B
B1 B2
Player A A1 3 5
A2 4 1
Solution:
1. Maximizing and Minimizing Player: In the payoff matrix,
maximizing players’ (A) strategy should be written in the row and
minimizing players’ (B) strategy should be written in the column.
2. Row Maxi -min Strategy: In the row, maximum values fr om the
minimum values of the given rows are taken. In simple words, at first row
minima values should be taken for all rows
Player B
B1 B2 Row
Minima
Player A A1 3 5 3
A2 4 1 1
Then maximum value (1) from all row minima values (3,1) are taken
called as Row Maxi -min value.
3. Column Mini -max Strategy: In the column , minimum values from the
maximum values of the given columns are taken. In simple words, at first
column maxima values should be taken for all columns
Player B
B1 B2
Player A A1 3 5
A2 4 1
Column
Maxima 4 5
then minimum value (4) from all column maxima values (4 and 5) are
taken called as Column Mini-max value.
4. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min (1) and Column Mini -max (4) values are co mpared and these
values are not same then there does not exist a saddle point representing
the value of the game.
5. Mixed Strategy Game : 2x2 matrix two person mixed strategy game
can be solved by using the formula
munotes.in
Page 107
107
Game Theory p as the probability that A uses strat egy A1 is obtained by the formula
p= (a22- a21)/D
q as the probability that B uses strategy B1 is obtained by the formula
q= (a22- a12)/D
and the value of the game is obtained by the formula
v= (a11a22 -a21a12)/D
where D= denominator= a11+a22 -a21-a12
Player B
B1 B2
Player A A1 3 5
A2 4 1
Here,
a11= 3; a12=5; a21=4; a22=1
and D= denominator= a11+a22 -a21-a12= 3+1 -4-5= -5
p as the probability that A uses strategy A1 is obtained by the formula
p= (a22- a21)/D = (1-4)/(-5)= ( -3)/-5= 0.6 and
and the probability that A uses strategy A2 is 1 -p=1-0.6=0.4
q as the probability that B uses strategy B1 is obtained by the formula
q= (a22- a12)/D = (1-5)/-5= (-4)/-5= 0.8
and the probability that B uses strategy B2 is 1 -q=1-0.8=0.2
and the value of t he game is obtained by the formula
v= (a11a22 -a21a12)/ D = (3x1 -4x5)/ -5=(3 -20)/-5=-17/-5=3.4
Therefore , the value of the game is 3.4 and the optimum strategy for A is
A1 and for B is B1.
4.5 PRINCIPLE OF DOMINANCE
The Principle of Dominance states that, if a strategy of a player dominates
over another strategy in all conditions (that is for all counter strategies by
other player), then the later strategy (being dominated) can be ignored. A
strategy dominates over the other strategy, only if it is prefera ble over the
other, under all conditions.
This Principle of Dominance is difficult to understand and hence simple
and logical trick has been developed by the content writer Dr. Gajanan
Mudholkar to remember this principle as follows
The trick to remembe r and apply Principle of Dominance is ‘RC’. The
first capital letter R stands for Capital R means Big R (R for row and R for
retain, it means that Bigger Row should be retained and Smaller Row
should be cancelled. The second capital letter C means Big C (C for
Column and C for cancellation) Greater Column should be Cancelled and
smaller column should be retained.
This principle can be applied in all type of Game Theory problem. This munotes.in
Page 108
108
Operation Research principle can be used for pure strategy game and mixed strategy game
also.
Example 4. Solve the following game directly and by using Principle of
Dominance
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Solution:
Solve the following game directly means by using pure strategy game as
follows :
1. Maximizing and Minimizing Player: In the payoff matrix,
maximizing players’ strategy (Player X) should be written in the row and
minimizing players’ strategy (Player Y) should be written in the column.
2. Row Maxi -min Strategy: In the row, maximum values from the
minimum values of the given rows are taken. In simple words, at first row
minima values should be taken for all rows
Player Y
1 2 3 4 5 Row
Minima
Player
X I 1 3 2 7 4 1
II 3 4 1 5 6 1
III 6 5 7 6 5 5
IV 2 0 6 3 1 0
and then maximum value (5) from all row minima values (1,1,5,0) are
taken called as Row Maxi -min value (5).
3. Column Mini -max Strategy: In the column , minimum values from the
maximum values of the given columns are taken. In simple words, at first
column maxima values should be taken for all columns
munotes.in
Page 109
109
Game Theory Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Column Maxima 6 5 7 7
and then minimum value (5) from all column maxima values (6,5,7,7) are
taken called as Co lumn Mini-max value (5).
4. Comparing Row Maxi -min and Column Mini -max values: The Row
Maxi -min (5) and Column Mini -max values (5) are compared and as these
values are same then there exists a saddle point representing the value of
the game.
5. Saddle Po int: The saddle point (5) is the point of intersection of row
and column of Row Maxi -min and Column Mini -max values. This saddle
point represents the value of the game.
V= Value of the Game=5 and the corresponding optimum strategy for
player X is III stra tegy and for Player Y is 2nd strategy.
6. By using Principle of Dominance
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
As we compare first and second row, we find that 1<3; 3<4; 2>1; 7>5 and
4<6 and there is no comparison possible. Similarly first row and third row
can’t be compared. Similarly first row and fourth row can’ t be compared .
Now we compare second row with third and fourth row as follows .
Similarly , second row and third row can’ t be compared. S imilarly second
row and fourth row can’ t be compared . munotes.in
Page 110
110
Operation Research Now we compare third row with fourth row as follows
We get 6>1; 5>0; 7>6; 6>3 and 5>1. Hence third row is greater than
fourth row.
According to the Principle of Dominance, RC means R for Greater Row
and R for Retain. It means that the greater row should be retained and
smaller row should be cancelled.
III>IV i.e. third row will be retained and fourth row will be cancelled as
follows
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Now , compare column wise
First column 1 with second column 2 as follows
1<3; 3<4; 2>1; 7>5 and 4<6 and hence comparison is not possible.
First column 1 with third column 3 as follows
1<2; 3>1 and 6<7 and hence comparison is not p ossible.
First column 1 with fourth column 4 as follows
1<7; 3<5 and 6=6 and hence First Column 1 ≤ fourth column.
According to the Principle of Dominance, RC means C for Greater
Column and C for cancel. It means that the greater column should be
cancelled and smaller column should be retained.
Fourth column being greater should be cancelled and small er first column
should be retained as follows
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Now compare second column with fifth column we get
3<4; 4<6 and 5=5 and hence comparison is possible as follows
Column 3 ≤ Column 5
munotes.in
Page 111
111
Game Theory According to the Principle of Dominance, RC means C for Greater
Column and C for cancel. It means that the greater column should be
cancelled and smaller column should be retained.
Fourth column being greater should be cancelled and smaller fi rst column
should be retained as follows
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Now compare first row with second row, here comparison is not possible.
Compare first row with third row, we came to know First row I < Third
row III.
According to the Principle of Dominance, RC means R for Greater Row
and R for Retain. It means that the greater row should be retained and
smaller row should be cancelled.
First row I < Third row III i.e. third row will be retained and first row will
be cancelled as follows
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Compare second row with third row, we came to know second row II <
Third row III.
According to the Pr inciple of Dominance, RC means R for Greater Row
and R for Retain. It means that the greater row should be retained and
smaller row should be cancelled.
munotes.in
Page 112
112
Operation Research
Second row II < Third row III i.e. third row will be retained and second
row will be cancelled as f ollows
Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Now compare column wise first column (value 6) is greater than second
column (value 5).
According to the Principle of Dominance, RC means C for Grea ter
Column and C for cancel. It means that the greater column should be
cancelled and smaller column should be retained.
First column being greater should be cancelled and smaller second column
should be retained as follows
Player Y
1 2 3 4 5
Play er X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Now only remaining comparison is in between second column and third
column.
Second column 2< Third column 3.
According to the Principle of Dominance, RC means C for Greater
Column and C for cancel. It means that the greater column should be
cancelled and smaller column should be retained.
Third column being greater should be cancelled and smaller second
column should be retained as follows
munotes.in
Page 113
113
Game Theory Player Y
1 2 3 4 5
Player X I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
Hence only reminder cell in the given matrix is 5 representing the value of
game. The corresponding optimum strategy for player X is third III
strategy and for player Y is second strategy 2.
Example 5. Solve the following game directly.
Player B
B1 B2 B3 B4
Player A A1 7 6 8 9
A2 -4 -3 9 10
A3 3 0 4 2
A4 10 5 -2 0
Solution:
Solve the following game directly means by using pure strategy game as
follows
1. Maximizing and Minimizi ng Player: In the payoff matrix,
maximizing players’ strategy (Player A) should be written in the row and
minimizing players’ strategy (Player B) should be written in the column.
2. Row Maxi -min Strategy: In the row, maximum values from the
minimum values of the given rows are taken. In simple words, at first row
minima values should be taken for all rows
Player B Row
Minima B1 B2 B3 B4
Player A A1 7 6 8 9 6
A2 -4 -3 9 10 -4
A3 3 0 4 2 0
A4 10 5 -2 0 -2
and then maximum value (6) from all ro w minima values (6, -4,0,-2) are
taken called as Row Maxi -min value (6).
munotes.in
Page 114
114
Operation Research 3. Column Mini -max Strategy: In the column , minimum values from the
maximum values of the given columns are taken. In simple words, at first
column maxima values should be taken for a ll columns
Player B
B1 B2 B3 B4
Player A A1 7 6 8 9
A2 -4 -3 9 10
A3 3 0 4 2
A4 10 5 -2 0
Column Maxima 10 6 9 10
and then minimum value (6) from all column maxima values (10,6,9,10)
are taken called as Column Mini-max value (6).
4. Compari ng Row Maxi -min and Column Mini -max
values: The Row Maxi -min (6) and Column Mini -max values (6) are
compared and as these values are same then there exists a saddle point
representing the value of the game.
5. Saddle Point: The saddle point (6) is the po int of intersection of row
and column of Row Maxi -min and Column Mini -max values. This saddle
point represents the value of the game.
V= Value of the Game=6 and the corresponding optimum strategy for
player A is A1 strategy and for Player B is B2 strategy .
Example 6.
4.6 LIMITATIONS OF GAME THEORY
1. Players of game are not competent to know their own and competitors
pay off values. Hence the application of game theory is not realistic in
nature.
2. The theory of game theory is restricted to two playe rs’ duopoly, but the
situation of many players are complex and difficult to solve.
3. Zero sum game situations are not realistic in nature.
4. Players do not have complete knowledge of the strategies and hence the
strategies of Maximin and Minimax is not applicable for conservative
cases and risk averse cases of the players.
4.7 SUMMARY
Today, business world is complex, dynamic, and competitive in nature.
The monopoly is quite observed. Every business firm tries to win the munotes.in
Page 115
115
Game Theory game by defeating other players i n the game using different strategies.
Game Theory is the competitive situation of business players in the
business competitive environment. Game theory is the study of operations
research technique involving appropriate use of strategies to win the
game. Thus Game theory is the branch of Operations Research dealing
with quantitative decision making when at least two players are involved
in the conflicting and competitive environment, resulting in success and
failure of players. Game is a particular busines s situation where at least
two players are involved to overcome the other player using optimum
strategy and to get maximum output using different strategies . The types
of games are Two Person Game, Multiple Person Game, Zero Sum Game,
Non-Zero Sum Game and Two Person Zero Sum Game. In the pure
strategy game, players use only one strategy throughout the game. The
pure strategy indicates that there is no other combination of strategy used
by the game player. In the mixed strategy game, players use different
strateg ies throughout the game. The mixed strategy indicates that there is
other combination of strategies used by the game player. The Principle of
Dominance states that, if a strategy of a player dominates over another
strategy in all conditions (that i s for all counter strategies by other player),
then the later strategy (being dominated) can be ignored. A strategy
dominates over the other strategy, only if it is preferable over the other,
under all conditions.
4.8 SELF -ASSESSMENT QUESTIONS
Q1. Expla in the Meaning and Concept of Game Theory.
Q2. Describe various Terminologies in Game Theory.
Q3. What are types of Game? Explain in depth.
Q4. Explain Principle of Dominance with practical example.
Q5. Describe Limitations of Game Theory.
Q6. Solve the following game directly and by using Principle of
Dominance
Player B
1 2 3 4 5
Player A I 1 3 2 7 4
II 3 4 1 5 6
III 6 5 7 6 5
IV 2 0 6 3 1
munotes.in
Page 116
116
Operation Research Q7. Solve the following game directly and by using Principle of
Dominance
Player B
1 2 3 4 5 6
Player A I 4 2 0 2 1 1
II 4 3 1 3 2 2
III 4 3 7 -5 1 2
IV 4 3 4 -1 2 2
V 4 3 3 -2 2 2
munotes.in
Page 117
117 5
DECISION THEORY
Decision Theory - Under Risk, Uncertainty, and decision tree
Unit Structure
5.0 Objectives
5.1 Introduction
5.2 Certain Key Issues in Decision Theory
5.3 Marginal Analysis
5.4 The steps of decision -making process.
5.5 Decision under va rious decision -making environments.
5.6 Decision -making under uncertainty
5.7 Probability estimates using Bayesian analysis.
5.8 Decision trees for making decision.
5.9 Summary
5.10 Exercises (solved examples)
5.0 OBJECTIVES
After reading this unit, you s hould be able to:
• structure a decision problem involving various alternatives and
uncertainties in outcomes
• apply marginal analysis for solving decision problems under
uncertainty
• analyse sequential problems using decision tree approach
• appreciate the use of utility theory in decision -making
• analyse uncertain situations where probabilities of outcomes are not
known.
5.1 INTRODUCTION
In every sphere of our life we need to take various kinds of decisions. The
ubiquity of decision problems, together wit h the need to make good
decisions, have led many people from different time and fields, to analyse
the decision -making process. A growing body of literature on Decision
Analysis is thus found today. The analysis varies with the nature of the munotes.in
Page 118
118
Operation Research decision probl em, so that any classification base for decision problems
provides us with a means to segregate the Decision Analysis literature. A
necessary condition for the existence of a decision problem is the presence
of alternative ways of action. Each action leads to a consequence through
a possible set of outcome, the information on which might be known or
unknown. One of the several ways of classifying decision problems has
been based on this knowledge about the information on outcomes.
Broadly, two classificatio ns result:
a) The information on outcomes are deterministic and are known with
certainty, and
b) The information on outcomes are probabilistic, with the probabilities
known or unknown.
The former may be classified as Decision Making under certainty, while
the latter is called Decision Making under uncertainty. The theory that has
resulted from analysing decision problems in uncertain situations is
commonly referred to as Decision Theory. With our background in the
Probability Theory, we are in a position to u ndertake a study of Decision
Theory in this unit. The objective of this unit is to study certain methods
for solving decision problems under uncertainty. The methods are
consequent to certain key issues of such problems. Accordingly, in the
next section we discuss the issues and in subsequent sections we present
the different methods for resolving them.
The success or failure that an individual or organization experiences,
depends to a large extent, on the ability of making acceptable decisions on
time. To arrive at such a decision, a decision -maker needs to enumerate
feasible and viable courses of action (alternatives or strategies), the
projection of consequences associated with each course of action, and a
measure of effectiveness (or an objective) to id entify the best course of
action.
Decision theory is both descriptive and prescriptive business modeling
approach to classify the degree of knowledge and compare expected
outcomes due to several courses of action. The degree of knowledge is
divided into fo ur categories: complete knowledge (i.e. certainty),
ignorance, risk and uncertainty.
5.2 CERTAIN KEY ISSUES IN DECISION THEORY
Different issues arise while analysing decision problems under uncertain
conditions of outcomes. Firstly, decisions we take can be viewed either as
independent decisions, or as decisions figuring in the whole sequence of
decisions that are taken over a period of time. Thus, depending on the
planning horizon under consideration, as also the nature of decisions, we
have either a sing le stage decision problem, or a sequential decision
problem. In real life, the decision maker provides the common thread, and
perhaps all his decisions, past, present and future, can be considered to be
sequential. The problem becomes combinatorial, and he nce difficult to munotes.in
Page 119
119
Decision Theory solve. Fortunately, valid assumptions in most of the cases help to reduce
the number of stages, and make the problem tractable.
Irrespective of the type of decision model, following essential components
are common to all:
Decision alterna tives: There is a finite number of decision alternatives
available to the decision -maker at each point in time when a decision is
made. The number and type of such alternatives may depend on the
previous decisions made and their outcomes. Decision alternat ives may be
described numerically, such as stocking 100 units of a particular item, or
non-numerically, such as conducting a market survey to know the likely
demand of an item.
States of nature : A state of nature is an event or scenario that is not under
the control of decision makers. For instance, it may be the state of
economy (e.g. inflation), a weather con dition, a political development etc.
The states of nature may be identified through Scenario Analysis where a
section of people are interviewed – stakeholders, long -time managers, etc.,
to understand states of nature that may have serious impact on a decision.
The states of nature are mutually exclusive and collectively exhaustive
with respect to any decision problem. The states of nature may be
descri bed numerically such as, demand of 100 units of an item or non-
numerically such as, employees strike, etc.
Payoff It is a numerical value (outcome) obtained due to the application of
each possible combination of decision alternatives and states of nature.
The payoff values are always conditional values because of unknown
states of nature.
The payoff values are measured within a specified period (e.g. within one
year, month, etc.) called the decision horizon . The payoffs in most
decisions are monetary. Payof fs resulting from each possible combination
of decision alternatives and states of natures are displayed in a matrix
(also called payoff matrix ) form.
Courses of Action
(Alternatives)
Sates of
Nature Probability S1 S2 … Sn
N1 P1 P11 P21 … P1n
N2 P2 P12 P22 … P2n
… … … … … …
Nm Pn P1n P2n … Pmn
munotes.in
Page 120
120
Operation Research 5.3 MARGINAL ANALYSIS
Expected value can be used while deciding on one alternative from among
several alternative courses of actions, each of which is characterized by a
set of uncertain outcomes. It is easy to see that the computations become
tedious as the number of values, the random variable can take, increases.
Consider the example of the newspaper vendor. Instead of weekly seven
values of the demand of the newspapers, if the demand could take, say,
twenty values, with different chances of occurrence of each value, the
computation would become very tedious. In such cases, marginal analysis
is very helpful. In this section, we explain the concept behind this
analysis.
Consider the demand of the n ewspaper vendor. Let us assume that the
newspaper man has found from the past data that the demand can take
values ranging from 31, 32... to 50. For easy representation, let us assume
that each of these values has got an equal chance of occurrence, viz., 1 /20.
The problem is to decide on the number of copies to be ordered.
Marginal Analysis proceeds by examining whether ordering an additional
unit is worthwhile or not. Thus, we will order X copies, provided ordering
the Xth copy is worthwhile but ordering the (X+1)th copy is not. To find
out whether ordering X copies are worthwhile, we note the following.
Ordering of the Xth copy may meet with two consequences, depending on
the occurrences of two events:
A. The copy can be sold.
B. The copy cannot be sold .
The Xth copy can be sold only if the demand exceeds or equals X,
whereas, the copy cannot be sold if the demand turns out to be less than X.
Also, if event A occurs, we will make a profit of 50 p. on the extra copy,
and if even B occurs, there will be a loss of 30 p. As this profit and loss
pertains to the additional or marginal unit, these are referred to as
marginal profit or loss and the resulting analysis is called marginal
analysis.
Using the following notations:
Kl = Marginal profit = 50p.
K2 = Marginal loss = 30p.
P(A) = Probability (Demand ≥ X) = 1 -Probability (Demand ≤ X - 1).
P(B) = Probability (Demand < X) = Probability (Demand ≤ X - 1).
We can write down the expected marginal profit and expected marginal
loss as:
Expected Marginal Profit = Kl P(A)
Expected Marginal Loss = K2 P(B) munotes.in
Page 121
121
Decision Theory Ordering the Xth
copy is worthwhile only if the expected profit due to it is
more than the expected loss, so that
Kl P(A) ≥ K2 P(B)
Now, if F(D) denotes the c.d.f. of demand, then by definition,
Probability D emand ≤(X-1) ± F(X -1)
Hence, Kl [1-F(X-1)] ≥ K2 F(X-1)
or;
K1 - Kl F(X-1) - K2F(X-1) ≥ 0
Thus, if condition 1 holds well, it is worthwhile to order the Xth
copy.
If the optimal decision is to order X copies, then ordering the (X+1)th
copy
will not be worthwhile, i.e. the expected marginal profit due to the
(X+1)th
copy should be less than the expected loss.
Proceeding with the analysis in the same way as above, we have:
Expected Marginal Profit = K1 Probability (Demand ≥ X + 1)
= Kl [1 – F(X)]
Expe cted Marginal Loss = K 2 F(X)
∴ For the (X+1)th
copy: Kl [1-F(X)] K2 ≤F(X)
From conditions (1) and (2) and the definition of Fractile, it is clear that X
will be the
the fractile of the Demand distribution.
Thus, for our problem, given the above result, all that we have to do is to
calculate
and find the Kth fractile of the distribution, which will give us the required
answer.
In our problem:
K = [0.5 / (0.5 + 0.3)] = 0.625 and the 0.625th fractile is 43.
∴The optimal decision is to order 13 copies. munotes.in
Page 122
122
Operation Research The above shows how marginal analysis helps us in arriving at the optimal
decision with very little computation. This is especially useful when the
random variable of interest takes a large number of values. Though we
have demonstrated this for a discret e demand distribution the same logic
can be shown to be applicable for continuous distributions also. Instead of
the distribution we have taken, if we would have assumed that demand is
normal with a specific μ and σ, then also the same Kth fractile of N (μ ,σ)
would have given us the optimal decision.
5.4 THE STEPS OF DECISION -MAKING PROCESS
The decision -making process involves the following steps:
1. Identify and define the problem.
2. List all possible future events (not under the control of decision -make r)
that are likely to occur.
3. Identify all the courses of action available to the decision -maker.
4. Express the payoffs ( pij) resulting from each combination of course of
action and state of nature.
5. Apply an appropriate decision theory model to selec t the best course of
action from the given list on the basis of a criterion (measure of
effectiveness) to get optimal (desired) payoff.
Example 5.1 A firm manufactures three types of products. The fixed and
variable costs are given below:
Fixed Cost (Rs) Variable Cost per Unit (Rs)
Product A : 25,000 12
Product B : 35,000 9
Product C : 53,000 7
The likely demand (units) of the products is given below:
Poor demand : 3,000
Moderate demand : 7,000
High demand : 11,000
If the sale price of each t ype of product is Rs 25, then prepare the payoff
matrix.
Solution Let D1, D2 and D3 be the poor, moderate and high demand,
respectively. The payoff is determined as:
Payoff = Sales revenue – Cost munotes.in
Page 123
123
Decision Theory The calculations for payoff (in ’000 Rs) for each pair of al ternative
demand (course of action) and the types of product (state of nature) are
shown below:
D1A = 3 × 25 – 25 – 3 × 12 = 14 D2A = 7 × 25 – 25 – 7 × 12 = 66
D1B = 3 × 25 – 35 – 3 × 19 = 13 D2B = 7 × 25 – 35 – 7 × 19 = 77
D1C = 3 × 25 – 53 – 3 × 17 = 1 D2C = 7 × 25 – 53 – 7 × 17 = 73
D3A = 11 × 25 – 25 – 11 × 12 = 118
D3B = 11 × 25 – 35 – 11 × 19 = 141
D3C = 11 × 25 – 53 – 11 × 17 = 145
The payoff values are shown in Table below:
Product Type Alternative demand in (‘000) Rs.
D1 D2 D3
A 14 66 118
B 13 77 141
C 1 73 145
5.5 DECISION UNDER VARIOUS DECISION -MAKING
ENVIRONMENTS
To arrive at an optimal decision it is essential to have an exhaustive list of
decision -alternatives, knowledge of decision environment, and use of
appropriate quantitative approach for decision -making.
In this section three types of decision -making environments: certainty ,
uncertainty , and risk , have been discussed. The knowledge of these
environments helps in choosing the quantitative approach for decision -
making.
Type 1: Decision -Making under Certainty
In this decision -making environment, decision -maker has complete
knowledge (perfect information) of outcome due to each decision -
alternative (course of action). In such a case he would select a decision
alternative that yiel ds the maximum return (payoff) under known state of
nature. For example, the decision to invest in National Saving Certificate ,
Indira Vikas Patra , Public Provident Fund, etc., is where complete
information about the future return due and the principal at maturity is
known.
munotes.in
Page 124
124
Operation Research Type 2: Decision -Making under Risk
In this decision -environment, decision -maker does not have perfect
knowledge about possible outcome of every decision alternative. It may
be due to more than one states of nature. In such a case , he ma kes an
assumption of the probability for occurrence of particular state of nature.
Type 3 : Decision -Making under Uncertainty
In this decision environment, decision -maker is unable to specify the
probability for occurrence of particular state of nature. How ever, this is
not the case of decision -making under ignorance, because the possible
states of nature are known . Thus, decisions under uncertainty are taken
even with less information than decisions under risk. For example, the
probability that Mr . X will b e the prime minister of the country 15years
from now is not known.
5.6 DECISION -MAKING UNDER UNCERTAINTY
When probability of any outcome cannot be quantified, the decision -
maker must arrive at a decision only on the actual conditional payoff
values, keepin g in view the criterion of effectiveness (policy).
The following criteria of decision -making under uncertainty have been
discussed in this section:
Optimism (Maximax or Minimin) criterion
Pessimism (Maximin or Minimax) criterion
Equal probabilities (Lapla ce) criterion
Coefficient of optimism (Hurwiez) criterion
Regret (salvage) criterion.
i) Optimism (Maximax or Minimin) Criterion
In this criterion the decision -maker ensures that he should not miss the
opportunity to achieve the largest possible profit (ma ximax) or the lowest
possible cost (minimin). Thus, he selects the decision alternative that
represents the maximum of the maxima (or minimum of the minima)
payoffs (consequences or outcomes).
The working method is summarized as follows:
(a) Locate the max imum (or minimum) payoff values corresponding to
each decision alternative.
(b) Select a decision alternative with best payoff value (maximum for
profit and minimum for cost).
Since in this criteri on the decision -maker selects a decision -alternative
with l argest (or lowest) possible payoff value, it is also called an
optimistic decision criterion.
munotes.in
Page 125
125
Decision Theory ii) Pessimism (Maximin or Minimax) Criterion
In this criterion the decision -maker ensures that he would earn no less (or
pay no more) than some specified amount. Thus, he selects the decision
alternative that represents the maximum of the minima (or minimum of
the minima in case of loss) payoff in case of profits. The working method
is summarized as follows:
(a) Locate the minimum (or maximum in case of profit) pa yoff value in
case of loss (or cost) data corresponding to each decision alternative.
(b) Select a decision alternative with the best payoff value (maximum for
profit and minimum for loss or cost).
Since in this criterion the decision -maker is conservative about the future
and always anticipates the worst possible outcome (minimum for profit
and maximum for cost or loss), it is called a pessimistic decision criterion .
This criterion is also known as Wald’s criterion .
iii) Equal Probabilities (Laplace) Crite rion
Since the probabilities of states of nature are not known, it is assumed that
all states of nature will occur with equal probability, i.e. each state of
nature is assigned an equal probability. As states of nature are mutually
exclusive and collective ly exhaustive, so the probability of each of these
must be: 1/(number of states of nature). The working method is
summarized as follows:
(a) Assign equal probability value to each state of nature by using the
formula:
1 ÷ (number of states of nature) .
(b) Compute the expected (or average) payoff for each alternative (course
of action) by adding all the payoffs and dividing by the number of
possible states of nature, or by applying the formula:
(Probability of state of nature j ) × ( Payoff value for the combi nation of
alternative I and state of nature j .)
(c) Select the best expected payoff value (maximum for profit and
minimum for cost).
This criterion is also known as the criterion of insufficient reason. This is
because except in a few cases, some informati on of the likelihood of
occurrence of states of nature is available.
iv) Coefficient of Optimism (Hurwicz) Criterion
This criterion suggests that a decision -maker should be neither completely
optimistic nor pessimistic and, therefore, must display a mixtur e of both.
Hurwicz, who suggested this criterion, introduced the idea of a coefficient
of optimism (denoted by α) to measure the decision -maker’s degree of
optimism. This coefficient lies between 0 and 1, where 0 represents a munotes.in
Page 126
126
Operation Research complete pessimistic attitude about the future and 1 a complete optimistic
attitude about the future. Thus, if α is the coefficient of optimism, then (1
– α) will represent the coefficient of pessimism.
The Hurwicz approach suggests that the decision -maker must select an
alternative that maximizes
H (Criterion of realism) = α (Maximum in column ) + (1 – α) (Minimum in
column )
The working method is summarized as follows:
(a) Decide the coefficient of optimism α (alpha) and then coefficient of
pessimism (1 – α).
(b) For each decision alternative select the largest and lowest payoff value
and multiply these with α and (1 – α) values, respectively. Then calculate
the weighted average, H by using above formula.
(c) Select an alternative with best weighted average payoff value.
v) Regret (Savage) Criterion
This criterion is also known as opportunity loss decision criterion or
minimax regret decision criterion because decision -maker regrets for
choosing wrong decision alternative resulting in an opportunity loss of
payoff. Thus, he always intends to minimize this regret. The working
method is summarized as follows:
(a) From the gi ven payoff matrix, develop an opportunity -loss (or regret)
matrix as follows:
(i) Find the best payoff corresponding to each state of nature
(ii) Subtract all other payoff values in that row from this value.
(b) For each decision alternative identify the w orst (or maximum regret)
payoff value. Record this value in the new row.
(c) Select a decision alternative resulting in a smallest anticipated
opportunity -loss value.
Example 5.2 Given the following payoff tables where the table represents
profits:
Alterna tives States of Nature
S1 S2 S3 S4
A1 3 5 8 -1
A2 6 5 2 0
A3 0 5 6 4
munotes.in
Page 127
127
Decision Theory Calculate the payoff using:
(a) Maximax, (b) Maximin,
Decision making under uncertainty.
a) Maximax :
Max( Max Ai) = Max ( 8, 6, 6 ) = 8
Decision : Select A1
b) Maxmin :
Max(Min A i) =Max ( -1, 0 ,0) =0
Decision : Select A2 or A3
Example 5.3 A food products’ company is contemplating the introduction
of a revolutionary new product with new packaging or replacing the
existing product at much higher price (S 1). It may even make a moder ate
change in the composition of the existing product, with a new packaging
at a small increase in price (S 2), or may mall a small change in the
composition of the existing product, backing it with the word ‘New’ and a
negligible increase in price (S 3).
The three possible states of nature or events are: (i) high increase in sales
(N1), (ii) no change in sales (N 2) and (iii) decrease in sales (N 3). The
marketing department of the company worked out the payoffs in terms of
yearly net profits for each of the strategies of three events (expected
sales). This is represented in the following table:
Strategies States of Nature
N1 N2 N3
S1 700 300 150
S2 500 450 0
S3 300 300 300
Which strategy should the concerned executive choose on the basis of
(a) Maximin criterion (b) Maximax criterion
(c) Minimax regret criterion (d) Laplace criterion?
Solution: The payoff matrix is rewritten as follows:
(a) Maximin Criterion
munotes.in
Page 128
128
Operation Research States of Nature Strategies
S1 S2 S3
N1 700 500 300
N2 300 450 300
N3 150 0 300
Column
Minimum 150 0 300
Maximum Payoff -> 300
The maximum of column minima is 300. Hence, the company should
adopt strategy S3.
(b) Maximax Criterion
States of Nature Strategies
S1 S2 S3
N1 700 500 300
N2 300 450 300
N3 150 0 300
Column
Maximum 700 500 300
700 <- Maximum Payoff
The maximum of column maxima is 7,00,000. Hence, the company should
adopt strategy S1.
(c) Minimax Regret Criterion Opportunity loss table is shown below:
States of Nature Strategies
S1 S2 S3
N1 700-700=0 700-500=200 700-300=400
N2 450-300=150 450-450=0 450-300=150
N3 300-150=150 300-0=300 300-300=0
Column
Maximum 150 300 400
150 <- Minimum Regret
munotes.in
Page 129
129
Decision Theory Hence the company should adopt minimum opportunity loss strategy, S1.
(d) Laplace Criterion Assuming that each state of nat ure has a probability
1/3 of occurrence. Thus,
Strategies Expected Return (Rs)
S1 (700 + 300 + 150)/3 = 383.33 <-Largest Payoff S2 (500 + 450 + 0)/3 = 316.66
S3 (300 + 300 + 300)/3 = 300
Since the largest expected return is from strategy S1, the execu tive must
select strategy S1.
5.7 PROBABILITY ESTIMATES USING BAYESIAN
ANALYSIS
In this decision -making environment, decision -maker has sufficient
information to assign probability to the likely occurrence of each outcome
(state of nature). Knowing the pro bability distribution of outcomes (states
of nature), the decision -maker needs to select a course of action resulting a
largest expected (average) payoff value. The expected payoff is the sum of
all possible weighted payoffs resulting from choosing a decis ion
alternative.
The widely used criterion for evaluating decision alternatives (courses of
action) under risk is the Expected Monetary Value (EMV) or Expected
Utility.
(a) Expected Monetary Value (EMV)
The expected monetary value (EMV) for a given course of a ction is
obtained by adding payoff values multiplied by the probabilities
associated with each state of nature. Mathematically, EMV is stated as
follows:
Where, m = number of possible states of nature
pi= probability of occurrence of state of nature, Ni
pij= payoff associated with state of nature Ni and course of action, Sj
The Procedure
1. Construct a payoff matrix listing all possible courses of action and
states of nature. Enter the conditional payoff values associated with each
possible combination of course of action and state of nature along with the
probabilities of the occurrence of each state of nature. munotes.in
Page 130
130
Operation Research 2. Calculate the EMV for each course of action by multiplying the
conditional payoffs by the associated probabilities and adding these
weighted va lues for each course of action.
3. Select the course of action that yields the optimal EMV.
Example 5.4 Mr X flies quite often from town A to town B. He can use
the airport bus which costs Rs 25 but if he takes it, there is a 0.08 chance
that he will miss the flight. The stay in a hotel costs Rs 270 with a 0.96
chance of being on time for the flight. For Rs 350 he can use a taxi which
will make 99 per cent chance of being on time for the flight. If Mr X
catches the plane on time, he will conclude a business transaction that will
produce a profit of Rs 10,000, otherwise he will lose it. Which mode of
transport should Mr X use? Answer on the basis of the EMV criterion.
Solution: Computation of EMV associated with various courses of action
is shown in Table.
States of
Nature Courses of Action
Bus Stay in Hotel Taxi
Cost Prob. Expected
Value Cost Prob. Expected
Value Cost Prob. Expected
Value
Catches
the Flight 1000
-25
=
9975 0.92 9177 10000
-270
=
9730 0.96 9340.80 10000 –350 =
9650 0.99 9553.50
Miss th e
Flight - 25 0.08 - 2.00 - 270 0.04 - 10.80 - 350 0.01 - 3.5
Expected
Monetary
Value
(EMV) 9175 9330 9550
Since EMV associated with course of action ‘Taxi’ is largest (= Rs 9,550),
it is the logical alternative.
5.8 DECISION TREES FOR MAKING DECISI ON
Decision -making problems discussed earlier were limited to arrive at a
decision over a fixed period of time. That is, payoffs, states of nature,
courses of action and probabilities associated with the occurrence of states
of nature were not subject to c hange. However, situations may arise when
a decision -maker needs to revise his previous decisions due to availability
of additional information. Thus he intends to make a sequence of
interrelated decisions over several future periods. Such a situation is c alled
a sequential or multiperiod decision process . For example, in the process
of marketing a new product, a company usually first go for ‘Test
Marketing’ and other alternative courses of action might be either munotes.in
Page 131
131
Decision Theory ‘Intensive Testing’ or ‘Gradual Testing’. Gi ven the various possible
consequences – good, fair, or poor, the company may be required to
decide between redesigning the product, an aggressive advertising
campaign or complete withdrawal of product, etc. Based on this decision
there might be an outcome that leads to another decision and so on.
A decision tree analysis involves the construction of a diagram that shows,
at a glance, when decisions are expected to be made – in what sequence,
their possible outcomes, and the corresponding payoffs. A decision tree
consists of nodes, branches, probability estimates, and payoffs . There are
two types of nodes:
Decision (or act) node: A decision node is represented by a square
and represents a point of time where a decision -maker must select one
alternative course of action among the available. The courses of action are
shown as branches or arcs emerging out of decision node.
Chance (or event) node: Each course of action may result in a chance
node . The chance node is represented by a circle and indicates a point of
time where the decision -maker will discover the response to his decision.
Branches emerge from and connect various nodes and represent either
decisions or states of nature. There are two types of branches:
Decision branch: It is the branch leading away from a decision node
and represents a course of action that can be chosen at a decision point.
Chance branch: It is the branch leading away from a chance node and
represents the state of nature of a set of chance events. The assumed
probabilities of the s tates of nature are written alongside their respective
chance branch.
Terminal branch: Any branch that makes the end of the decision tree
(not followed by either a decision or chance node), is called a terminal
branch. A terminal branch can represent eith er a course of action. The
terminal points of a decision tree are supposed to be mutually exclusive
points so that exactly one course of action will be chosen.
The payoff can be positive (i.e. revenue or sales) or negative (i.e.
expenditure or cost) and it can be associated either with decision or chance
branches.
An illustration of a decision tree is shown in Fig. below. It is possible for a
decision tree to be deterministic or probabilistic. It can also further be
divided in terms of stages – into single stage (a decision under condition
of certainty) and multistage (a sequence of decisions).
munotes.in
Page 132
132
Operation Research
The optimal sequence of decisions in a tree is found by starting at the
right -hand side and rolling backwards . At each node, an expected return is
calculated (call ed position value). If the node is a chance node , then the
position value is calculated as the sum of the products of the probabilities
or the branches emanating from the chance node and their respective
position values. If the node is a decision node, then the expected return is
calculated for each of its branches and the highest return is selected. This
procedure continues until the initial node is reached. The position values
for this node correspond to the maximum expected return obtainable from
the dec ision sequence.
Example 5.5 You are given the following estimates concerning a
Research and Development programme:
Decision
(Di) Probability
of Decision
Di Given
Research R
P(Di | R ) Outcome
Number Probability
of Outcome
xi Given Di )
P(xi|Di ) Payoff
Value of
Outcome, xi
(Rs ’000)
Develop 0.5 1 0.6 600
2 0.3 -100
3 0.1 0
0.5 1 0.0 600
Do not
develop 2 0.0 -100
3 1.1 0
munotes.in
Page 133
133
Decision Theory Construct and evaluate the decision tree diagram for the above data. Show
your workings for evaluation.
Solution: The decis ion tree of the given problem along with necessary
calculations is shown in Fig.
Example 5.6 A glass factory that specializes in crystal is developing a
substantial backlog and for this the firm’s management is considering
three courses of action: To a rrange for subcontracting ( S1), to begin
overtime production ( S2), and to construct new facilities ( S3). The correct
choice depends largely upon the future demand, which may be low,
medium, or high. By consensus, management ranks the respective
probabiliti es as 0.10, 0.50 and 0.40. A cost analysis reveals the effect upon
the profits. This is shown in the table below:
Demand Probability Course of Action
S1 S2 S3
Subcontracting Begin
Overtime Construct
facilities
Low (L) 0.1 10 -20 -50
Medium
(M) 0.5 50 60 20
High (H) 0.4 50 100 200
Solution: A decision tree that represents possible courses of action and
states of nature is shown in Fig. In order to analyze the tree, we start
working backwards from the end branches. The most preferred decision at
the decision node 0 is found by calculating the expected value of each
decision branch and selecting the path (course of action) that has the
highest value. munotes.in
Page 134
134
Operation Research
Since node 3 has the highest EMV, therefore, the decision at node 0 will
be to choose the course of action S3, i.e. construct new facilities.
5.9 SUMMARY
Decision Theory provides us with the framework and methods for
analysing decision problems under uncertainty. A decision problem under
uncertainty is characterized by different alternative courses of action and
uncertain outcomes corresponding to each action. The problems can
involve a single stage or a multi -stage decision process. Marginal Analysis
is helpful in solving single stage problems, whereas the Decision Tree
Approach is useful for solving m ulti-stage problems. In this unit we
examined Optimism (Maximax or Minimin) criterion, Pessimism
(Maximin or Minimax) criterion, Equal probabilities (Laplace) criterion,
Coefficient of optimism (Hurwiez) criterion and Regret (salvage) criterion
and the dec ision tree analysis.
5.10 EXERCISES
Exercise Example 1. The manager of a flower shop promises its
customers delivery within four hours on all flower orders. All flowers are
purchased on the previous day and delivered to Parker by 8.00 am the next
morning. The daily demand for roses is as follows.
Dozens of roses: 70 80 90 100
Probability: 0.1 0.2 0.4 0.3
The manager purchases roses for Rs 10 per dozen and sells them for Rs
30. All unsold roses are donated to a local hospital. How many dozens of
roses should Parker order each evening to maximize its profits? What is
the optimum expected profit?
Solution: The quantity of roses to be purchased per day is considered as
‘course of action’ and the daily demand of the roses is considered as a
‘state of nature’ because demand is uncertain with known probability.
From the data, it is clear that the flower shop must not purchase less than 7
or more than 10 dozen roses, per day. Also each dozen roses sold within a munotes.in
Page 135
135
Decision Theory day y ields a profit of Rs (30 – 10) = Rs 20 and otherwise it is a loss of
Rs 10.
Thus
Marginal profit (MP) = Selling price – Cost = 30 – 10 = Rs 20
Marginal loss (ML) = Loss on unsold roses = Rs 10
Using the information given in the problem, the various conditi onal profit
(payoff) values for each combination of decision alternatives and state of
nature are given by Conditional profit = MP × Roses sold – ML × Roses
not sold
Where, D = number of roses sold within a day and S = number of roses
stocked.
The result ing conditional profit values and corresponding expected
payoffs are computed in the table below:
States if
Nature
(Demand
per Day) Probability Conditional profit
(Rs.) due to courses
of action
(Purchase per Day) Conditional profit (Rs.) due to
courses of action
(Purchase per Day)
70 80 90 100 70 80 90 100
(1) (2) (3) (4) (5) (1)X(2) (1)X(3) (1)X(4) (1)X(5)
70 0.1 140 130 120 110 14 13 12 11
80 0.2 140 160 150 140 28 32 30 28
90 0.4 140 160 180 170 56 64 72 68
100 0.3 140 160 180 200 42 48 54 60
Expected Monetary
Value 140 157 168 167
Since the highest EMV of Rs 168 corresponds to the course of action 90,
the flower shop should purchase nine dozen roses every day.
Exercise Example 2: The probability of demand for hiring cars on any
day in a given city is as follows:
No. of cars demanded: 0 1 2 3 4
Probability: 0.1 0.2 0.3 0.2 0.2
Cars have a fixed cost of Rs 90 each day to keep the daily hire charges
(variable costs of running) Rs. 200. If the car -hire company owns 4 cars,
what i s its daily expectation? If the company is about to go into business
and currently has no car, how many cars should it buy? munotes.in
Page 136
136
Operation Research Solution Given that Rs 90 is the fixed cost and Rs 200 is variable cost.
The payoff values with 4 cars at the disposal of decision -maker are
calculated as under:
No. of cars demanded :
0 1 2 3 4
Payoff (with 4 cars):
0 – 90 × 4 200 – 90 × 4 400 – 90 × 4 600 – 90 × 4 800 – 90 × 4
= – 360 = – 160 = 40 = 240 = 440
Thus, the daily expectation is obtained by multiplyi ng the payoff values
with the given corresponding probabilities of demand:
Daily Expectation =
(– 360)(0.1) + ( – 160)(0.2) + (40)(0.3) + (240)(0.2) + (440)(0.2) = Rs 80
The conditional payoffs and expected payoffs for each course of action are
shown in Ta bles.
Conditional Payoff Values
Demand
of Cars Probability Conditional Payoff (Rs.) due to Decision to
Purchase Cars
(Course of Action)
0 1 2 3 4
0 0.1 0 -90 -180 -270 -360
1 0.2 0 110 20 -70 -160
2 0.3 0 110 220 130 40
3 0.2 0 110 220 330 240
4 0.2 0 110 220 330 440
munotes.in
Page 137
137
Decision Theory Expected Payoffs and EMV
Demand
of Cars Probability Conditional Payoff (Rs.) due to Decision to
Purchase Cars
(Course of Action)
0 1 2 3 4
0 0.1 0 -9 -18 -27 -36
1 0.2 0 22 4 -14 -32
2 0.3 0 33 66 39 12
3 0.2 0 22 44 66 48
4 0.2 0 22 44 66 88
EMV 0 90 140 130 80
Since the EMV of Rs 140 for the course of action 2 is the highest, the
company should buy 2 cars.
munotes.in
Page 138
138 6
WAITING LINES MODEL
Unit Structure
6.0 Objectives
6.1 Introduction
6.2 Characteristics of a Waiting Line or a Queuing Model
6.3 Notations and Symbols
6.4 Statistical methods in queuing
6.5 The M/M/l System
6.6 Summary
6.7 Exercises (solved examples)
6.0 OBJECTIVES
After studying this unit, you should be able to:
Identify the occurrence of waiting line or queuing in real life
situations.
Describe the characteristics of a queuing problem.
Use the statistical methods necessary to analyse queuing problems.
Apply the common queuing models in suitable problems.
Estimate the optimum parameters of a queuing model with respect to
cost and service level for M/M/1 system.
6.1 INTRODUCTION
The waiting line models or the queuing problem is identified by the
presence o f a group of customers who arrive randomly to receive some
service. The customer upon arrival may be attended to immediately or
may have to wait until the server is free. The service time required to
serve the customers is also a statistical variable. This methodology can be
applied in the field of business (banks, booking counters), industries
(servicing of machines), government (railway or post -office counters),
transportation (airport, harbor) and everyday life (elevators, restaurants,
and doctor’s chamb er).
The waiting line or queuing models are basically relevant to service
oriented organisations and suggest ways and means to improve the
efficiency of the service. An improvement of service level is always
possible by increasing the number of employees. Apart from increasing
the cost an immediate consequence of such a step is unutilized or idle time munotes.in
Page 139
139
Waiting Lines Model of the servers. In addition, it is unrealistic to assume that a large -scale
increase in staff is possible in an organisation. Queuing methodology
indicates th e optimal usage of existing manpower and other resources to
improve the service. It can also indicate the cost implications if the
existing service facility has to be improved by adding more servers.
The relationship between queuing and service rates can b e
diagrammatically illustrated using the cost curves shown in Figure.
At a slow service rate, queues build up and the cost of queuing increases.
An ideal service unit will minimise the operating cost of the entire system.
Many real -life situations in which study of queuing theory can provide
solution to waiting line problems are listed below:
Situation Customers Service Facilities
Petrol pumps (stations) Automobiles Pumps
Hospital Patients Doctors/Nurses/Rooms
Airport Aircraft Runways
Post office Letters Sorting system
Job interviews Applicants Interviewers
Cargo Trucks Loader/unloaders
Workshop Machines/Cars Mechanics/Floor space
Factory Employees Cafeteria/Punching Machine
6.2 CHARACTERISTICS OF A WAITING LIN E OR A
QUEUEING MODEL
A queuing system can be described by the following components:
Arrival
The statistical pattern of the arrival can be indicated through the
probability distribution of the number of arrivals in an interval. This is a
discrete random variable. Alternatively, the probability distribution of the
time between successive arrivals (known as inter -arrival time) can also
be studied to ascertain the stochastic aspect of the problem. This variable
is continuous in nature.
munotes.in
Page 140
140
Operation Research
Cost Structure of a Queuing Problem
The probability distribution of the arrival pattern can be identified through
analysis of past data. The discrete random variable indicating the number
of arrivals in a time interval and the continuous random variable
indicating the time between two successive arrivals (interarrival time)
are obviously inter related. A remarkable result in this context is that if the
number of arrivals follows a Poisson distribution , the corresponding
interarrival time follows an exponential distribution. This property is
frequently used to derive elegant results on queuing problems.
Service
The time taken by a server to complete service is known as service time.
The service time is a statistical variable and can be studied either as the
number of services com pleted in a given period of time or the completion
period of a service. The data on actual service time should be analyzed to
find out the probability distribution of service time.
Server
The service may be offered through a single server such as a ticket counter
or through several channels such as a train arriving in a station with
several platforms.
Sometimes the service is to be carried out sequentially through several
phases known as multiphase service. In government, the papers move
through a number of phases in terms of official hierarchy till they arrive at
the appropriate level where a decision can be taken.
Time spent in the queuing system
The time spent by a customer in a queuing system is the sum of waiting
time before service and the service time . munotes.in
Page 141
141
Waiting Lines Model Queue discipline
The queue discipline indicates the order in which members of the queue
are selected for service. It is most frequently assumed that the customers
are served on a first' come first serve basis. This is commonly referred to
as FIFO (first in, first out) system. Occasionally, a certain group of
customers receive priority in service over others even if they arrive late.
This is commonly referred to as priority queue; the queue discipline does
not always take into account the order of arrival. The server chooses one
of the customers to offer service at random. Such a system is known as
service in random order (SIRO). While allotting an item with high demand
and limited supply such as a test match cricketer share of a public limited
company, SIR O is the only possible way of offering service when it is not
possible to identify the order of arrival.
Size of a population
The collection of potential customers may be very large or of a moderate
size. In a railway booking counter the total number of po tential passengers
is so large that although theoretically finite it can be regarded as infinity
for all practical purposes. The assumption of infinite population is very
convenient for analysing a queuing model. However, this assumption is
not valid where the customer group is represented by a few looms in a
spinning mill that require operator facility from time to time. If the
population size is finite then the analysis of queuing model becomes more
involved.
Maximum size of a queue
Sometimes only a finit e number of customers are allowed to stay in the
system although the total number of customers in the population may or
may not be finite. For example, a doctor may make appointments with k
patients in a day. If the number of patients asking for appointmen t exceeds
k, they are not allowed to join the queue. Thus, although the size of the
population is infinite, the maximum number permissible in the system
is k.
Fig.: Schematic Representation of a Queuing Problem
munotes.in
Page 142
142
Operation Research 6.3 NOTATIONS AND SYMBOL S
Kendall (Kendall, 1951) has introduced set of notations which have
become standard in the literature of queuing models. A general queuing
system is denoted by (a/b/c) : (d/e) where
a = probability distribution of the interarrival time.
b=probability distribution of the service time.
c=number of servers in the system.
d = maximum number of customers allowed in the system.
e= queue discipline.
In addition , the size of the population as mentioned in the previous section
is important for certain types of queui ng problem although not explicitly
mentioned in the Kendall's notation. Traditionally, the exponential
distribution in queuing problems is denoted by M. Thus (M/M/1) : (
/FIFO) indicates queuing system when the interarrival times and service
times are exponentially distributed having one server in the system with
first in first out discipline and the number of customers allowed in the
system can be infinite.
In general, the behaviour of a queuing system will depend upon time.
Such a system is said to be in a transient state. This usually occurs at an
early stage of formation of queues where its behavior is still dependent up
on the initial condition s. When sufficient time has elapsed since the
beginning of the operation (mathematically as the time approaches to
infinity) the behaviour of the system may become independent of time.
The system then is said to be in a steady state. Only steady state queuing
problems will be analyzed in this unit.
The following symbols will be used while studying queuing models.
n=number ofunitsinthesystemwhoarewaitingforserviceandwhoarebeingse
rved.
Pn(t)=transientstateprobabilitiesofexactlyncustomersinthesystemattimetass
umingthat the system has started its operation at time zero.
Pn=steady state probability of having n customers in the system.
£ =mean effective arrival rate (number of customer s arriving per unit time).
µ=mean service rate per busy server (number of custome rs served per unit
time)
C=number of parallel servers.
W(t)= density function of the waiting time. munotes.in
Page 143
143
Waiting Lines Model Ws = expected waiting time per customer in the system including the
service time. Wq=expected waiting time per customer in the queue
excluding the service time.
Ls=expected number of customers in the system including those who are
receiving service.
Lq=expected number of customers in the queue excluding those who are
receiving service.
6.4 STATISTICAL METHODS IN QUEUEING
The arrival of customers, the departur e of customers after service and the
waiting time of a customer before being served in a queuing system are
random phenomena. In order to develop appropriate statistical model of
this problem the following assumptions are made:
1) If N(t) denotes the numbe r of arrivals or departures after service in the
timeinterval(0,t)thenN(t)has independentincrements. Thiscanbestatedst
atistically as follows. If t lare independent random variables
Thus, if the service comp onent is ignored the number of arrivals in the
interval (0,t) has the probability distribution of a Poisson variable with
parameter λ t which is the product of the arrival rate and the length of the
interval t. This probability law is known as the Poisson Process.
RelationshipbetweenPoissonProcessandExponentialProbabilityDistrib
ution
a) Consider a queuing model in which the number of arrivals in an interval
of length t follows a Poisson Process with arrival rate λ. If the
interarrival times are independent random variables, they must follow an
exponential distribution with density f(t) where
munotes.in
Page 144
144
Operation Research It can be readily shown by integration that E(t) = 1 / £. Thus if the arrival
rate £=20/hour, the average time between two successive arrivals is 1/20
hour or 3 minut es.
b) If the interarrival times in a queuing system are independently,
identically distributed exponential random variables then the number of
arrivals in an interval follows a Poisson Process with arrival rate identical
with parameter of the exponential distribution.
c) Consider a random variable X with an exponential pr obability
distribution. Therefore , t>0
P(X>t+s | X>s) = P(X>t)
This property is important for solving queuing problems. Assuming that
when a customer arrives the service is in progress for s units of time. The
chance that the service will continue for at least an additional t unit is
identical with the probability that the service will prolong for at least t
units after a fresh start.
One way to look at this property is that the time alread y spent in the
system has no relevance to the additional time the customer i s likely to
spend in the system further. Thus, this property is sometimes referred to as
lack of memory or forgetfulness of the exponential distribution.
6.5 THE M/M/L SYSTEM
In this queuing model, it is assumed that the number of customers arriving
in a time interval t follows a Poisson Process with parameter λ.
Equivalently, the interval between any two successive arrivals is
exponentially distributed with parameter A. The time taken to complete a
single service is exponentially distributed with parameter µ. The numb er
of servers is one. Although not explicitly stated both the population and
the queue size can be infinity. The order of service is assumed to be FIFO.
Performance Measures of a Queuing System
The performance measures (operating characteristics) for the e valuation of
the performance of an existing queuing system, and for designing a new
system in terms of the level of service a customer receives as well as the
proper utilization of the service facilities are listed as follows:
1. Average (or expected) time spent by a customer in the queue and
system
Wq: Average time an arriving customer has to wait in a queue before
being served,
Ws: Average time an arriving customer spends in the system, including
waiting and service.
munotes.in
Page 145
145
Waiting Lines Model 2. Average (expected) number of custo mers in the queue and system
Lq: Average number of customers waiting for service in the queue (queue
length)
Ls: Average number of customers in the system (either waiting for
services in the queue or being served ).
3. Value of time both for customers and s ervers
Pw : Probability that an arriving customer has to wait before being served
(also called blocking probability ).
ρ = λ / μ : Percentage of time a server is busy serving customers, i.e., the
system utilization.
Pn: Probability of n customers waiting fo r service in the queuing system.
Pd: Probability that an arriving customer is not allowed to enter in the
queuing i.e., system capacity is full.
4. Average cost required to operate the queuing system
• Average cost required to operate the system per unit o f time?
• Number of servers (service centres) required to achieve cost
effectiveness?
Transient -State and Steady -State
At the beginning of service operations, a queuing system is influenced by
the initial conditions, such as number of customers waiting for service and
percentage of time servers are busy serving customers, etc.
This initial period is termed as transient -state. However, after certain
period of time, the system becomes independent of the initial conditions
and enters into a steady -state condit ion.
To quantify various measures of system performance in each queuing
model, it is assumed that the system has entered into a steady -state.
Let Pn(t) be the probability that there are n customers in the system at a
particular time t. Any change in the va lue of Pn(t), with respect to time t,
is denoted by Pn′ (t). In the case of steady -state, we have:
munotes.in
Page 146
146
Operation Research If the arrival rate of customers at the system is more than the service rate,
then a steady -state cannot be reached, regardless of the length of the
elapse d time.
Queue size, also referred as line length represents average number of
customers waiting in the system for service.
Queue length represents average number of customers waiting in the
system and being served.
Notations The notations used for analyzin g of a queuing system are as
follows:
n = number of customers in the system (waiting and in service)
Pn= probability of n customers in the system
λ = average customer arrival rate or average number of arrivals per unit of
time
in the queuing system
μ = average service rate or average number of customers served per unit
time at the place of service
λ / μ = ρ= Average service completion time(1/ μ) / A verage interarrival
time(1/ λ)
ρ = traffic intensity or server utilization factor
P0 = probability of no customer in the system
s = number of service channels (service facilities or servers)
N = maximum number of customers allowed in the system
Ls= average number of customers in the system (waiting and in service)
Lq= average number of customers in the queue (queue length)
Ws= average waiting time in the system (waiting and in service)
Wq= average waiting time in the queue
Pw = probability that an arriving customer has to wait (system being
busy),
1 – P0 = (λ/μ)
For achieving a steady -state condition, it is necessary that, λ/μ < 1 (i.e. the
arrival rate must be less than the service rate). Such a situation arises when
the queue length is limited, generally because of space, capacity limitation
or customer s balk.
munotes.in
Page 147
147
Waiting Lines Model Relationships among Performance Measures
The following basic relationships hold for all infinite source queuing
models.
The general relationship among various performance measures is as
follows:
(i) Average number of customers in the system is equal to the average
number of customers in queue(line) plus average number of customers
being served per unit of time (system utilization).
Ls=Lq + Customer being served
= Lq+ λ / μ
The value of ρ =λ / μ is true for a single server finite -source queuing
model.
(ii) Average waiting time for a customer in the queue (line)
Wq=Lq / λ
(iii) Average waiting time for a customer in the system including
average service time
Ws= Wq+1 / μ
(iv) Probabili ty of being in the system (waiting and being served) longer
than time t is given by:
Where, T = time spent in the system
t = specified time period
e = 2.718
(v) Probability of only waiting for service longer than time t is given by:
(vi) Probability of exactly n customers in the system is given by:
(vii) Probability that the number of customers in the system, n exceeds a
given number, r is given by:
munotes.in
Page 148
148
Operation Research The general relationships among various performance measures are:
(M/M/1) System Examples
Example 1:
A petroleum company is considering expansion of its one unloading
facility at its refinery. Due to random variations in weather, loading delays
and other factors, ships arriving at the refinery to unload crude oil arrive at
a rate of 5 ships per week. The service rate is 10 ships per week. Assume
arrivals follow a Poisson Process and the service time is exponential.
a) Find the average time a ship must wait before beginning to deliver
its cargo to the refinery.
b) If a second berth is rented what will be the average number of ships
waiting before being unloaded?
c) What would be the average time a ship would wait before being
unloaded with two berths?
d) What is the average number of idle berths atany specified time?
Solution:
a) The expected waiting time Wq before a ship begins to unload crude
oil is:
munotes.in
Page 149
149
Waiting Lines Model
Example 2: A television repairman finds that the time spent on his jobs
has an exponential distribution with a mean of 30 minutes. If he repairs
the sets in the order in which they came in, and if the arrival of sets
follows a Poi sson distribution with an approximate average rate of 10 per
8-hour day, what is the repairman’s expected idle time each day? How
many jobs are ahead of the average set just brought in ? [Rajasthan,
MCom, 2000; Delhi Univ., MCom 2002 ]
Solution: From the dat a of the problem, we have:
(a) Expected idle time of repairman each day
Since number of hours for which the repairman remains busy in an 8 -hour
day (traffic intensity) is given by:
Therefore, the idle time for a repairman in an 8 -hour day will be: (8 – 5) =
3 hours
(b) Expected (or average) number of TV sets in the system
munotes.in
Page 150
150
Operation Research 6.6 SUMMARY
A common situation that occurs in everyday life is that of waiting in a line
either at bus stops, petrol pumps, restaurants, ticket booths, doctors’
clinics, bank counters, traffic lights and so on. Queues (waiting lines) are
also found in workshops where the machines wait to be repaired; at a tool
crib where the mechanics wait to receive tools; in a warehouse where
items wait to be used, incoming calls wait to mature in the telephone
exchange, trucks wait to be unloaded, airplanes wait either to take off or
land and so on.
In general, a queue is formed at a production/operation system when either
customers (human beings or physical entities) requiring service wait
because nu mber of customers exceeds the number of service facilities , or
service facilities do not work efficiently/take more time than prescribed to
serve a customer.
A queuing problem is characterised by a flow of customers arriving
randomly at one or more service facilities. The customers upon arriving at
the facility may be served immediately or, if willing, may have to wait
until the facility is available.
The arrivals are characterised by either by the number of arrivals time
in a specific period of time or by the time between two
successive arrivals, known as interarrival time . The number of arrivals is
a discrete random variable whereas the interarrival times are continuous
random variables.
The service is characterised either by the number of services complet ed
in a given time period or the time taken to complete the service. The
number of services completed is a discrete random variable while the
service time is a continuous random variable.
Other characteristics of a queuing model are the number of servers,
order of service, size of the population of the customers, maximum
size of the queue. The various characteristics of a queuing problem can
be expressed in terms of a suitable notation known as Kendall's notation.
The time spent by an incoming customer in a queuing system is a random
variable and is of interest to the decision maker. If the customer under
consideration is a down machine it is inoperative during the period of
service. There is, thus, a cost involved due to its lack of functioning. One
of the objectives of studying a queuing problem is to find out the optimum
service rate and the number of servers so that the average cost of being in
queuing system and the cost of service are minimized . The time a
customer spends in a system before the start of service is a random
variable known as waiting time. The probability distribution of waiting
time depends upon the probability distribution of interarrival time and
service time.
munotes.in
Page 151
151
Waiting Lines Model Let Pn(t) indicate the probability of having n customers in the system at
time t. Then if P(t) depends upon t, the queuing system is said to be in the
transient state. After the queuing system has become operative for a
considerable period of time the probability P n(t) may become
independent of t. The probabilities are then known as steady state
probabilities.
When the number of arrivals in a time interval of length t follows a
Poisson distribution with mean Jet where A is the rate of arrival, the
arrivals are said to follow a Poisson Process. In this case, the interarrival
times are independently, identically distributed random variables with an
exponential probability distribution with parameter X and vice versa.
If the service times are independently, identically distributed exponential
random variables with parameter 11 and there is only one server in the
queuing model, t he resulting queuing model is denoted by M/M/1
according to Kendall's notation.
6.7 EXERCISES
Example 3: In a railway marshaling yard, goods trains arrive at a rate of
30 trains per day. Assuming that the int erarrival time follows an
exponential distribution and the service time (the time taken to hump a
train) distribution is also exponential with an average of 36 minutes.
Calculate:
(a) expected queue size (line length)
(b) probability that the queue size ex ceeds 10
If the input of trains increases to an average of 33 per day, what will be
the change in (i) and (ii)?
Solution to Exercise 3: From the data of the problem, we have
£=30/(60 * 24) =1/48 trains per minute and µ =1/36 trains per minute.
The traf fic intensity then is, ρ= £/μ = 36/48 = 0.75
(a) Expected queue size (line length):
(b) Probability that the queue size exceeds 10:
P (n ≥10) =ρ10=(0.75)10=0.06
If the input increases to 33 trains per day, then we have £ = 33/(60* 24 )=
11/480 trai ns per minute and µ = 1/36 trains per minute.
munotes.in
Page 152
152
Operation Research Thus, traffic intensity,
Hence, recalculating the values for (a) and (bi)
Example 4 : Arrivals at telephone booth are considered to be Poisson with
an average time of 10minutes between one arrival and th e next. The length
of phone calls is assumed to be distributed exponentially , with a mean of 3
minutes.
(a) What is the probability that a person arriving at the booth will have to
wait?
(b) The telephone department will install a second booth when convinc ed
that an arrival would expect waiting for at least 3 minutes for a phone
call. By how much should the flow of arrivals increase in order to
justify a second booth?
(c) What is the average length of the queue that forms from time to time?
(d) What is the probability that it will take a customer more than 10
minutes altogether to wait for the phone and complete his call?
Solution : From the data of the problem, we have
λ = 1/10 = 0.10 person per minute and μ = 1/3 = 0.33 person per minute
(a) Probability that a person has to wait at the booth.
P (n > 0) = 1 − P0 = λ/μ = 0.10 / 0.33 = 0.3
(b) The installation of second booth will be justified only if the arrival rate
is mo re than the waiting time.
Let λ′ be the increased arrival rate. Then the expected waiting time in the
queue will be
Where, Wq= 3 (given) and λ = λ′ (say) for second booth. Hence, the
increase in the arrival rate is0.16 – 0.10 = 0.06 arrivals per minute.
munotes.in
Page 153
153
Waiting Lines Model (c) Average length of non -empty queue:
(d) Probability of waiting for 10 minutes or more is given by
This shows that on an average 3 per cent of the arrivals will have to wait
for 10 minutes or more before they can use the phone.
munotes.in
Page 154
154
7
SIMULATION - QUEUE SYSTEM,
INVENTORY AND DEMAND
SIMULATION
Unit Structure
7.0 Objectives
7.1 Introduction
7.2 Reasons for using simulation
7.3 Limitations of simulation
7.4 Steps in the simulation process
7.5 Simulation - queue system
7.6 Simulation - inventory
7.7 Simulation - demand
7.8 Summary
7.9 Exercises (solved examples)
7.0 OBJECTIVES
After studying this unit, you will be able to:
Discuss the need for simulation in management problems where it will
not be possible to use precise mathematical techniqu es
Explain that simulation may be the only method in situations where it
will be extremely difficult to observe actual environment
Describe the process of simulation based on a sound conceptual
framework
Apply simulation techniques in solving queuing and i nventory control
problems.
7.1 INTRODUCTION
Simulation is a quantitative procedure which describes a process by
developing a model of that process and then conducting a series of
organized experiments to predict the behaviour of the process over time.
Observing the experiments is very much like observing the process in
operation. To find out how the real process would react to certain changes, munotes.in
Page 155
155
Simulation - Queue System,
Inventory and Demand
Simulation we can produce these changes in our model and simulate the reaction of
the real process to them.
For instance, in designing an airplane, the designer can solve various
equations describing the aerodynamics of the plane. Or, if these equations
are very difficult and complex to solve, scale model can be built and its
behaviour observed in a wind tunnel. In simulation, w e build
mathematical models which we cannot solve and run them on sample data
to simulate the behaviour of the -system. Thus, simulation involves
performing experiments on the model of a system.
Simulation is one of the widely used techniques by corporate m anagers as
an aid for decision -making. This technique uses a computer to simulate
(imitate) the operation of any system or process. It is also used to analyse
systems that operate indefinitely. In such a case, the computer randomly
generates and records the occurrence of the events that drive the system as
if it was physically operating. Recording the performance of the simulated
operation of the system for a number of alternative options of operating
procedures enables us to evaluate and compare these alte rnatives to
choose the most desired one.
7.2 REASONS FOR USING SIMULATION
In the case of number of problems, we have been able to find through
straight forward techniques, mathematical solutions to the situation. The
economic order quantity, the simplex s olution to a linear programming
problem, and a branch -and- bound solution to an integer programming
problem are some of the typical examples we can cite. However, in each
of those cases the problem was simplified by certain assumptions so that
the appropri ate mathematical techniques could be employed. It is not
difficult to think of managerial situations so complex that mathematical
solution is impossible given the current state of the art in mathematics. In
these cases, simulation offers a good alternative , If we insist that all
managerial problems have to be solved mathematically, then we may find
ourselves simplifying the situation so that it can he solved; sacrificing
realism to solve the problem can get us in real trouble. Whereas the
assumption of norm ality-in dealing with a distribution of inventory
demand may he reasonable, the assumption of linearity in a specific linear
programming environment may be totally unrealistic .
While in some cases the solutions which result from simplifying
assumptions are suitable for the decision -maker, in other cases, they
simply are not. Simulation is an appropriate substitute for mathematical
evaluation of a model in many situations.
Although it also involves assumptions, they are manageable. The use of
simulation enab les us to provide insight into certain management
problems where mathematical evaluation of a model is not possible.
Among the reasons why management scientists would consider using
simulation to solve management problems are the following: munotes.in
Page 156
156
Operation Research Simulation may be the only method available because it is difficult to
observe the actual environment. (In space flight or the charting of
satellite trajectories, it is widely used).
It is not possible to develop a mathematical solution.
Actual observation of a system ma y be too expensive. (The operation
of a large computer centre under a number of different operating
alternatives might be too expensive to be feasible).
There may not be sufficient time to allow the system to operate
extensively. (If we were studying long -run trends in world population, for
instance, we simply could not wait the required number of years to see
results.)
Actual operation and observation of a system may be too disruptive. (If
you are comparing two ways of providing food service in a hospital, the
confusion that would result from operating two different systems for long
enough to get valid observations might be too great).
7.3 LIMITATIONS OF SIMULATION
Use of simulation in place of other techniques, like everything else,
involves a trade - off, and we should be mindful of the disadvantages
involved in the simulation approach. These include the facts that
Simulation is not precise. It is not optimization and does not yield an
answer but merely provides a set of the system's responses to different
operating conditions. In many cases, this lack of precision is difficult
to measure.
A good simulation model may -be very expensive. Often it takes years
to develop a usable corporate planning model.
Not all situations can be evaluated using simulation; only situations
involving uncertainty are candidates, and without a random
component, all simulated experiments would produce the same
answer.
Simulation generates a way of evaluating solutions but does not
generate solutions themselves. Managers must sti ll generate the
solutions they want to test.
7.4 STEPS IN THE SIMULATION PROCESS
All effective simulations require a great deal of planning and organization.
Although simulations vary in complexity from situation to situation, in
general you will have to go through these steps:
1. Define the problem or system you intended to simulate.
2. Formulate the model you intend to use.
3. Test the model; compare its behaviour with the behaviour of the
actual problem. munotes.in
Page 157
157
Simulation - Queue System,
Inventory and Demand
Simulation 4. Identify and collect the data needed to test the model.
5. Run the simulation.
6. Analyze the results of the simulation and, if desired, change the
solution you are evaluating.
7. Rerun the simulation to test the new solution.
8. Validate the simulation; this involves increasing the chances of
the inferences you may draw abo ut the real situation from
running the simulation to become valid.
7.5 SIMULATION - QUEUE SYSTEM
Example: A dentist schedules all his patients for 30 -minute
appointments. Some of the patients take more 30 minutes some less,
depending on the type of dental work to be done. The following summary
shows the various categories of work, their probabilities and time actually
needed to complete the work:
Category of Service Time Required
(minutes) Probability of
Category
Filling 45 0.40
Crown 60 0.15
Cleaning 15 0.15
Extraction 45 0.10
Checkup 15 0.20
Simulate the dentist’s clinic for four hours and determine the average
waiting time for the patients as well as the idleness of the doctor. Assume
that all the patients show up at the clinic at exactly their s cheduled arrival
time starting at 8.00 a.m. Use the following random numbers for handling
the above problem:
40 82 11 34 25 66 17 79 [AMIE, 2005]
Solution: The cumulative probability distribution and random number
interval for service time are sho wn in Table:
munotes.in
Page 158
158
Operation Research Category of
Service Time
Required
(minutes) Probability
of Category Cumulative
Probability Random
Number
Interval
Filling 45 0.40 0.40 00-39
Crown 60 0.15 0.55 40-54
Cleaning 15 0.15 0.70 55-69
Extraction 45 0.10 0.80 70-79
Checkup 15 0.20 1.00 80-99
The various parameters of a queuing system such as arrival pattern of
customers, service time, waiting time , in the context of the given
problem, are shown in below Tables:
Table: Arrival Pattern and Nature of Service
Patient
Number Scheduled
Arrival Random
Number Category of
Service Service
Time
(Minute)
1 8.00 40 Crown 60
2 8.30 82 Checkup 15
3 9.00 11 Filling 45
4 9.30 34 Filling 45
5 10.00 25 Filling 45
6 10.30 66 Cleaning 15
7 11.00 17 Filling 45
8 11.30 79 Extraction 45
munotes.in
Page 159
159
Simulation - Queue System,
Inventory and Demand
Simulation Table: Computation of Arrivals, Departures and Waiting of Patients
Time Event
(Patient Number) Patient Number
(Time to Exit) Waiting
(Patient
Number)
8.00 1 arrive 1 (60) -
8.30 2 arrive 1 (30) 2
9.00 1 departs; 3 arrive 2 (15) 3
9.15 2 depart s 3 (45) -
9.30 4 arrive 3 (30) 4
10.00 3 departs; 3 arrive 4 (45) 5
10.30 6 arrive 4 (15) 5, 6
10.45 4 departs 5 (45) 6
11.00 7 arrive 5 (30) 6, 7
11.30 5 departs; 8 arrive 6 (15) 7, 8
11.45 6 departs 7 (45) 8
12.00 End 7 (30) 8
The dentist was not idle even once during the entire simulated period.
The waiting times for the patients were as follows:
Table: Computation of Average Waiting Time
Patient
Number Arrival Time Service Starts
at Waiting Time
(Minute)
1 8.00 8.00 0
2 8.30 9.00 30
3 9.00 9.15 15
4 9.30 10.00 30
5 10.00 10.45 45
6 10.30 11.30 60
7 11.00 11.45 45
8 11.30 12.30 60
280
Average Waiting Time = 280 / 8 = 25 minutes
munotes.in
Page 160
160
Operation Research 7.6 SIMULATION - INVENTORY
Example: Using random numbers to simulate a sample, find the
probability tha t a packet of 6products does not contain any defective
product, when the production line produces 10 per cent defective products .
Compare your answer with the expected probability.
Solution Given that 10 per cent of the total production is defective and 90
per cent is non -defective, if we have 100 random numbers (0 to 99), then
90 or 90 per cent of them represent non -defective products and the
remaining 10 (or 10 per cent) of them represent defective products. Thus,
the random numbers 00to 89 are assigned t o variables that represent non -
defective products and 90 to 100 are assigned to variables that represent
defective products.
If we choose a set of 2 -digit random numbers in the range 00 to 99 to
represent a packet of 6 products as shown below, then we woul d expect
that 90 per cent of the time they would fall in the range 00 to 89.
It may be noted that out of ten simulated samples 6 contain one or more
defectives and 4 contain no defectives. Thus, the expected percentage of
non-defective products is 40 per c ent. However, theoretically the
probability that a packet of 6 products containing no defective product, is
(0.9)6 = 0.53144 = 53.14%.
Sample
Number Random Number
A 83 02 22 57 51 68
B 39 77 32 77 09 79
C 28 06 24 25 93 22
D 97 66 63 99 61 80
E 69 30 16 09 05 53
F 33 63 99 19 87 26
G 87 14 77 43 96 43
H 99 53 93 61 28 52
I 93 86 52 77 65 15
J 18 46 23 34 25 85
Example: A book store wishes to carry a particular book in stock. The
demand of the book is not certain and there is a lead time of 2 day s for
stock replenishment. munotes.in
Page 161
161
Simulation - Queue System,
Inventory and Demand
Simulation
The probabilities of demand are given below:
Demand (units/day) : 0 1 2 3 4
Probability : 0.05 0.10 0.30 0.45 0.10
Each time an order is placed, the store incurs an ordering cost of Rs 10 per
order. The store also incurs a carrying cost of Re 0.5 per book per day.
The inventory carrying cost is calculated on the basis of stock at the end of
each day. The manager of the book store wishes to compare two options
for his inventory decision.
A : Order 5 books when the pr esent inventory plus any outstanding order
falls below 8 books.
B : Order 8 books when the present inventory plus any outstanding order
falls below 8 books.
Currently (beginning of 1st day) the store has a stock of 8 books plus 6
books ordered two days ago and are expected to arrive the next day.
Carryout simulation runs for 10 days to recommend an appropriate option .
You may use random numbers in the sequences, using the first number for
day one as given below:
89, 34, 78, 63, 61, 81, 39, 16, 13, 73 [AMIE, 2005 ]
Solution: Using the daily demand distribution, we obtain a probability
distribution, as shown in Table of daily demand distribution.
Daily Demand Probability Cumulative
Probability Random
Number
Intervals
0 0.05 0.05 00-04
1 0.10 0.15 05-14
2 0.30 0.45 15-44
3 0.45 0.90 45-89
4 0.10 1.00 90-99
The stock in hand is of 8 books and stock on order is 5 books (expected
next day).
munotes.in
Page 162
162
Operation Research Table: Optimal A
Random
Number Daily
Demand Opening
Stock in
Hand Receipt Closing
Stock
in
Hand Order
Quantity Closing
Stock
89 3 8 - 8-3=5 5 5
34 2 5 5 5+5-
2=8 - 8
78 3 8 - 8-3=5 5 5
63 3 5 5 10-3=7 - 7
61 3 7 - 7-3=4 5 4
81 3 4 5 9-3=6 - 6
39 2 6 - 6-2=4 5 4
16 2 4 5 9-2=7 - 7
13 1 7 - 7-1=6 - 6
73 3 6 - 6-3=3 - 3
55
Since 5 books have been order ed four times as shown in Table above,
therefore, the total ordering cost is Rs (4 × 10) = Rs 40.
Closing stock of 10 days is of 55 books. Therefore, the holding cost at the
rate of Re 0.5 per book per day is Rs 55 × 0.5 = Rs 27.5
Total cost for 10 days = Ordering cost + Holding cost = Rs 40 + 27.5 =
Rs 67.5
munotes.in
Page 163
163
Simulation - Queue System,
Inventory and Demand
Simulation Table: Optimal B
Random
Number Daily
Demand Opening
Stock in
Hand Receipt Closing
Stock
in
Hand Order
Quantity Closing
Stock
89 3 8 - 8-3=5 8 5
34 2 5 8 8+5-
2=11 - 11
78 3 11 - 11-3=8 - 8
63 3 8 - 8-3=5 8 5
61 3 5 8 13-
3=10 - 10
81 3 10 - 10-3=7 - 7
39 2 8 - 7-2=5 8 5
16 2 5 8 13-
2=11 - 11
13 1 11 - 11-
1=10 - 10
73 3 10 - 10-3=7 - 7
71
Eight books have been ordered three times, as shown in Table above,
when the inventory of books at the beginning of the day plus outstanding
orders is less than 8. Therefore, the total ordering cost is: Rs (3 × 10) =
Rs 30.
Closing stock of 10 days is of 71 books. Therefore, the holding cost , Re
0.5 per book per day is Rs 71 × 0.5 = Rs 35.5
The total cost for 10 days = Rs (30 + 35.5) = Rs 65.5. Since option B has a
lower total cost than option A, therefore, the manager should choose
option B.
7.7 SIMULATION - DEMAND
Example: A bakery keeps stock of a popular brand of cake. Previous
exper ience shows the daily demand pattern for the item with associated
probabilities, as given below:
Daily demand (number) : 0 10 20 30 40 50
Probability: 0.01 0.20 0.15 0.50 0.12 0.02 munotes.in
Page 164
164
Operation Research Use the following sequence of random numbers to simulate the demand
for next 10 days.
Random numbers: 25, 39, 65, 76, 12, 05, 73, 89, 19, 49.
Also estimate the daily average demand for the cakes on the basis of the
simulated data.
Solution: Using the daily demand distribution, we first obtain a
probability distribut ion as shown in Table below:
Table: Daily Demand Distribution
Daily Demand Probability Cumulative
Probability Random
Number
Intervals
0 0.01 0.01 00
10 0.20 0.21 01-20
20 0.15 0.36 21-35
30 0.50 0.86 36-85
40 0.12 0.98 86-97
50 0.02 1.00 98-99
Next to conduct the simulation experiment for demand take a sample of 10
random numbers from a table of random numbers, which represent the
sequence of 10 samples. Each random sample number represents a sample
of demand.
The simulation calculations for a period of 10 days are given in Table
below:
Days Random
Number Simulated
Demand
1 40 30 Because random number 40 falls in
the interval 36 -85
2 19 10 Because random number 19 falls in
the interval 01 -20 and so on
3 87 40
4 83 30
5 73 30
6 84 30
7 29 20
8 09 10
9 02 10
10 20 10
Expected Demand = 220/10 = 22 units per day munotes.in
Page 165
165
Simulation - Queue System,
Inventory and Demand
Simulation 7.8 SUMMARY
Simulation is a powerful and intuitive technique and uses computer to
simulate the operation of an entire system or process. Random numbers
are generated using a pr obability distribution to generate various outcomes
over a period of time. These outcomes provide at a glance view of
different configurations of the system at a least cost in comparison of
actually operating the system. Hence, many alternative system
configurations can be investigated and compared before selecting the most
appropriate one to use.
Simulation approach has applications to a wide variety of areas such as
queuing system, inventory system, and demand distribution, etc.
Spread sheet software is i ncreasingly being used to perform basic
computer simulations. The availability of such software enables decision
makers to use simulation approach for solving real -life decision problems.
A simulation imitates the operation of real world processes or syste ms
with the use of models. The model represents the key behaviours and
characteristics of the selected process or system while the simulation
represents how the model evolves under different conditions over time.
Simulations are usually computer -based, usi ng a software -generated
model to provide support for the decisions of managers and engineers as
well as for training purposes. Simulation techniques aid understanding and
experimentation, as the models are both visual and interactive.
Simulation systems in clude discrete event simulation, process simulation
and dynamic simulation. Businesses may use all of these systems across
different levels of the organisation.
7.9 EXERCISES
Example 1: A firm has a single channel service station with the following
arrival and service time probability distributions:
Interarrival
time in minutes Probability Service time
in minutes Probability
10 0.10 5 0.08
15 0.25 10 0.14
20 0.30 15 0.18
25 0.25 20 0.24
30 0.10 25 0.22
30 0.14
munotes.in
Page 166
166
Operation Research The customer’s arrival at the servic e station is a random phenomenon and
the time between the arrivals varies from 10 to 30 minutes. The service
time varies from 5 minutes to 30 minutes. The queuing process begins at
10 a.m. and proceeds for nearly 8 hours. An arrival immediately, goes to
the service facility if it is free. Otherwise it waits in a queue. The queue
discipline is first -come first -served. If the attendant’s wages are Rs 10 per
hour and the customer’s waiting time costs Rs 15 per hour, then would it
be an economical proposition t o engage a second attendant? Answer using
Monte Carlo simulation technique.
Solution: The cumulative probability distributions and random number
interval, both for interarrival time and service time, are shown in the
following Tables:
Table: Interarrival T ime
Interarrival
time
in minutes Probability Cumulative
Probability Random
number
interval
10 0.10 0.10 00-09
15 0.25 0.35 10-34
20 0.30 0.65 35-64
25 0.25 0.90 65-89
30 0.10 1.00 90-99
Table: Service Time
Interarrival
time
in minutes Probability Cumulative
Probability Random
number
interval
5 0.08 0.08 00-07
10 0.14 0.22 08-21
15 0.18 0.40 22-39
20 0.24 0.64 40-63
25 0.22 0.86 64-85
30 0.14 1.00 86-99
munotes.in
Page 167
167
Simulation - Queue System,
Inventory and Demand
Simulation
Table: Single Server Queuing Simulation for 15 Arrivals
Arrival
Number Random Number Interarrival Time
(min) Arrival
Time
(min) Service
Starts
(min) Waiting
Time Random Number Service Time Exit
Time Time
in
System
1 2 3 4 5 6 7 8 9 10= 6+8 1 20 15 10.15 10.15 0 26 15 30 15
2 73 25 10.40 10.40 0 43 20 60 20
3 30 15 10.55 11.00 5 98 30 90 35
4 99 30 11.25 11.30 5 87 30 120 35
5 66 25 11.45 12.00 15 58 20 140 35
6 83 25 12.10 12.20 10 90 30 170 40
7 32 15 12.25 1.05 35 94 25 195 60
8 75 25 12.50 1.30 40 60 20 215 60
9 04 10 1.00 1.50 50 08 10 225 60
10 15 15 1.15 2.00 45 50 20 245 65
11 29 15 1.30 2.20 50 37 15 260 65
12 62 20 1.50 2.35 45 42 20 280 65
13 37 20 2.10 2.55 45 28 15 295 60
14 68 25 2.35 3.10 35 84 25 320 60
15 94 30 3.05 3.35 30 65 25 345 55
From the 15 samples of waiting time, 225 minu tes, and the time spent, 545
minutes, by the customer in the system, we compute all average waiting
time in the system and average service time as follows:
Average waiting time = 380/15 = 25.3 minutes.
Average service time = 545/15 = 36.33 minutes
Thus, th e average cost of waiting and service is given by:
Cost of waiting = 15 × (25.30/60) = Rs 6.32 per hour
Cost of service = 10 × (36.33/60) = Rs 6.05 per hour
Since the average cost of service, per hour, is less than the average cost of
waiting per hour, therefore second attendant may be hired.
Example 2: A company trading in motor vehicle spare parts wishes to
determine the levels of stock it should carry for the items in its range. The
demand is not certain and there is a lead time for stock replenishment . For
an item A, the following information is obtained:
munotes.in
Page 168
168
Operation Research Demand (units/day) : 3 4 5 6 7
Probability : 0.10 0.20 0.30 0.30 0.10
Carrying cost (per unit/day) : Rs 2
Ordering cost (per order) : Rs 50
Lead time for replenishment : 3 days
Stock on hand at the beginning of the simulation exercise was 20 units.
Carry out a simulation run over a period of 10 days with the objective of
evaluating the inventory rule:
Order 15 units when present inventory plus any outstanding order falls
below 15 units.
You may use random numbers in the sequence of: 0, 9, 1, 1, 5, 1, 8, 6, 3,
5, 7, 1, 2, 9, using the first number for day one. Your calculation should
include the total cost of operating this inventory rule for 10 days.
[AMIE, 2004 ]
Solution Let us begin s imulation by assuming that:
(i) Orders are placed at the end of the day and received after 3 days, at the
end of a day.
(ii) Back orders are accumulated in case of short supply and are supplied
when stock is available.
The cumulative probability distributi on and the random number range for
daily demand is shown in Table below:
Table - Daily Demand Distribution
Daily Demand Probability Cumulative
Probability Random
Number
Intervals
3 0.10 0.10 00
4 0.20 0.30 01-02
5 0.30 0.60 03-05
6 0.30 0.90 06-08
7 0.10 1.00 09
munotes.in
Page 169
169
Simulation - Queue System,
Inventory and Demand
Simulation
The results of the simulation experiment conducted are shown in Table
below:
Table - Simulation Experiments
Days Opening
Stock Random
Number Resulting
Demand Closing
Stock Order
Placed Order
Delivered Average
Stock in
the
Evening 1 20 0 3 17 - - 18.5
2 17 9 7 10 15 - 13.5
3 10 1 4 6 - - 8
4 6 1 4 2 - - 4
5 2 5 5 0(-3)* 15 15 1
6 12 1 4 8 - - 10
7 8 8 6 2 - - 6
8 2 6 6 0(-4)* 15 15 1
9 11 3 5 6 - - 8.5
10 6 5 5 1 - - 3.5
* Negative figures indicate back orders.
Average ending stoc k = 78/10 = 7.8 units/day
Daily ordering cost = (Cost of placing one order) × (Number of orders
placed per day) = 50 × 3 = Rs l50
Daily carrying cost = (Cost of carrying one unit for one day) × (Average
ending stock) = 2 × 7.8 = Rs l5.60
Total daily invent ory cost = Daily ordering cost + Daily carrying cost =
150 + 15.60 = Rs 165.60.
Example 3: The manager of a warehouse is interested in designing an
inventory control system for one of the products in stock. The demand for
the product comes from numerous re tail outlets and the orders arrive on a
weekly basis. The warehouse receives its stock from a factory but the lead
time is not constant. The manager wants to determine the best time to
release orders to the factory so that stockouts are minimized, yet the
inventory holding costs are at acceptable levels. Any order from retailers,
not supplied on a given day, constitute lost demand. Based on a sampling
study, the following data are available:
munotes.in
Page 170
170
Operation Research Demand per
week in
thousand Probability Lead time Probability
0 0.20 2 0.30
1 0.40 3 0.40
2 0.30 4 0.30
3 0.10
The manager of the warehouse has determined the following cost
parameters: Ordering cost (C 0) per order equals Rs 50, carrying cost (C h)
equals Rs 2 per thousand units per week, and shortage cost (C s) equals Rs
10 per thousand units.
The objective of inventory analysis is to determine the optimal size of an
order and the best time to place an order. The following ordering policy
has been suggested.
Policy : Whenever the inventory level becomes less than or equal to 2,000
units (reorder level), an order equal to the difference between current
inventory balance and the specified maximum replenishment level , is
equal to 4,000 units, is placed.
Simulate the policy for a week’s period assuming that the (i) th e beginning
inventory is 3,000 units, (ii) no back orders are permitted, (iii) each order
is placed at the beginning of the week, as soon as the inventory level is
less than or equal to the reorder level, and (iv) the replenishment orders
are received at the beginning of the week.
[AMIE, 2005 ]
Solution:
Using weekly demand and lead time distributions, assign an appropriate
set of random numbers to represent value (range) of variables as shown in
below respective Tables:
Table: Probabilities and Random number Interval for Weekly
Demand
Weekly
demand (in
thousand) Probability Cumulative
probability Random
number
interval
0 0.20 0.20 00-19
1 0.40 0.60 20-59
2 0.30 0.90 60-89
3 0.10 1.00 90-99
munotes.in
Page 171
171
Simulation - Queue System,
Inventory and Demand
Simulation Table: Probabilities and Random number Interval for Lea d Time
Lead time in
weeks Probability Cumulative
probability Random
number
interval
2 0.30 0.30 00-29
3 0.40 0.70 30-69
4 0.30 1.00 70-99
The simulation experiment conducted for a 10 week period is shown in the
next Table. The simulation process begin s with an inventory level of
3,000 units. The following four steps occur in the simulation process:
1. Begin each simulation week by checking whether any order has just
arrived. If it has, increase the beginning (current) stock (inventory) by the
quantity received.
2. Generate a weekly demand from the demand probability distribution in
weekly demand Table given above by selection of a random number. This
random number is recorded in column 4. The demand simulated is
recorded in column 5.The random number 31 generates a demand of 1,000
units when it is subtracted from the initial inventory level value of 3,000
units. It yields an ending inventory of 2,000 units at the end of the first
week.
3. Compute the ending inventory every week and record it in column 7.
Ending inventory = Beginning inventory – Demand = 3,000 – 1,000 =
2,000
If on hand inventory is not sufficient to meet the week’s demand, then
record the number of units short in column 6.
4. Determine whether the week’s ending inventory has reached the r eorder
level. If it has, and if thereis no outstanding order (back orders), then place
an order.
Since the ending inventory of 2,000 units is equal to the reorder level,
therefore, an order for4,000 – 2,000 = 2,000 units is placed.
5. The lead time for the new order is simulated by first choosing a random
number and recording it in column 8. Finally, this random number is
converted into a lead time (column 9) by using the lead time distribution
in the earlier Table.
The random number 29 corresponds to a le ad time of 2 weeks, with 2,000
units to be held (carried) in stock. Therefore, the holding cost of Rs 4 is
paid and since there were no shortages, there is no shortage cost. munotes.in
Page 172
172
Operation Research Summing these cost yields a total inventory cost (column 10) for week
one of Rs 54 .
The same step -by-step process is repeated for the remaining 10 weeks of
the simulation experiment.
Analysis of Inventory Cost
Average ending inventory = (1,000 total unit / 10 weeks) = 100 units per
week.
Average number of orders placed = (2 orders / 10 weeks) = 0.2 order per
week.
Average number of lost sales = (7,000 / 1,000 ) = 7 units per week.
Total average inventory cost = Ordering cost + Holding cost + Shortage
cost
= (Cost of placing one order) × (Number of orders placed per week)
+
(Cost of holding one unit for one week) × (Average ending inventory) +
(Cost per lost sale) × (Average number of lost sales per week)
= (100 / 10) + (16 / 10) + (70 / 10)
= 10 + 1.6 + 7
= Rs 18.6
Maximum Inventory Level = 4,000 units Reorder Level = 2 ,000 units
Week Order
Receipt Beginning
Inventory Random
Number Demand Ending
Inventory Quantity
Ordered Random
Number Lead
Time Total Cost
C0+ Ch+ Cs = TC
(R.)
1 0 3000 31 1000 2000 2000 29 2 50 4 - - 54
2 0 2000 73 2000 0 0 - - - - - = -
3 0 0 53 1000 (-1000) 0 - - 0 0 10 = 10
4 2000 2000 86 2000 0 4000 83 4 50 - - = 50
5 0 0 32 1000 (-1000) 0 10 = 10
6 0 0 78 2000 (-2000) 0 20 = 20
7 0 0 26 1000 (-1000) 0 10 = 10
8 0 0 64 2000 (-2000) 0 20 = 20
9 4000 4000 45 1000 3000 0 6 - = 6
10 0 3000 12 0 3000 0 6 - = 6
Total 1000 100 16 70
The negative figures in Table above enclosed in brackets indicate loss of
sales.
munotes.in