PDf-MCA-Maths-2-munotes

Page 1

1
UNIT I
1
LINEAR PROGRAMMING PROBLEM
Unit structure
1.0 Objectives
1.1 Introduction
1.2 Formulation of Linear Programming Problem
1.3 Graphical Method
1.4 Special Cases of LPP
1.5 Summary
1.6 References
1.7 Exercise
1.0 OBJECTIVES After going th rough this chapter, students will able to:
● Learn how to develop linear programming models for simple
problems.
● Formulate a given simplified description of a suitable real world
problem as a linear programming model in general, standard and
canonical forms.
● Understand the importance of extreme points in obtaining the optimal
solution.
● Solve a two -dimensional linear programming problem graphically.
1.1 INTRODUCTION Linear programming is one of the most popular and widely used
quantitative techniques. Linear programming deals with the optimization
{maximization or minimization) of a function of variables. It consists of
linear functions which are subject to constraints in the form of linear
equations or in the form inequalities. Linear programming is considere d an
important technique to find optimum resource utilization. Linear
programming has been used to solve problems involving assignment of
jobs to machines, product mix, advertising media selection, least cost diet,
transportation, investment opportunity se lection and many others.
Linear programming is widely used in Mathematics and some other fields
such as economics, business, telecommunication and manufacturing fields.
In this chapter, we will learn meaning and formulation of linear munotes.in

Page 2

2 Linear Programming Problem programming, its compo nents and various methods to solve linear
programming problems i.e. LPP.
Following are important terms used in LPP :
1. Optimization: It means ‘minimization’ or ‘maximization’ of some
mathematical function of any number of variables.
2. Objective Function: Any m athematical function to be optimized is
called an Objective function
3. Decision variables: Variables appearing in an objective function are
called decision variables.
4. Optimum Solution: The set of values of the decision variables giving
the ‘maximum’ or the ‘minimum’ value of an objective function is
called the optimum solution.
5. Constrained and unconstrained Optimization: If the decision
variable are subject to some limitations (constraints) on the values
which they can take the optimization is called constr ained
optimization otherwise the optimization called unconstrained
optimization.
6. Mathematical Programing: Method of finding solution of a
constrained optimization problem is called mathematical
programming.
Example 1: Find the minimum of z = 2x1 + 5x 2 + 7x3
Example 2: Find the maximum of z = 2x12+ 5x 23+ 3x 3
Subject to x1 + x 2 + 3x 3 ≤ 10
3x1 + 5x 2 + 8x 3 ≤ 20
2x1 + x 2 + 4x 3 ≤ 30
And x1, x2, x3 ≥ 0
In Example 1, the objective function is linear in x 1, x2 and x 3. In Example
2 the objec tive function is non -linear but the constraints are linear function
of the decision variables.
7. Linear Programming: If the objective function as well as all the
constraints are linear function of the decision variables, an
optimization problem is called Lin ear Programming Problem (LPP).
Example 3: Maximize z = x 1 + 5x 2 + 7x 3 Objective Function
Subject to x1 + 3x 2 + 3x 3 ≤ 15
4x1 + 5x 2 + 8x 3 ≤ 25 Constraints munotes.in

Page 3

3 Mathematical Foundation for Computer Science 2 3x1 + x 2 + 4x 3 ≤ 30
And x1, x2, x3 ≥ 0 Non negativity condition
8. Coefficient of Objective Function represent ‘profit’ per unit of the
decision variables for the maximization problem and they represent
‘cost’ for a minimization problem.
9. Coefficient of the variables in the constraints are called
technological coefficient / requirements.
10. Constants on the R. H. S. of the constraints represent the resource
availabilities in different departments.
11. General Statement of an LPP:
Optimize (Minimize / maximize)
Z = C 1x1 + C 2x2 + …………. + C nxn
=

Subject to
a11x1 + a11x1 + ………………+ a 1nxn
b1
a21x1 + a22x1 + ………………+ a 2nxn
b2
.
.
.
Am1x1 + am2x1 + ----------------- + a mnxn
bm
And x 1, x2, ……………. xn ≥ 0
In the matrix notation the same problem can be stated as follows: -
Optimize z = C’x
Sunject to Ax
B
Where
C =
, x =
, A =
and B =

And C’ = Tra nspose of C
Some more Definitions:
1. Feasible Area: Area bounded by all the constraints along with non -
negativity conditions is called the feasible area. munotes.in

Page 4

4 Linear Programming Problem Max or min Z =

Subject to


bi; i = 1, 2 ….m
And x j ≥ 0; j = 1, 2…n
2. Feasible Solution: Any set of values of decision variables satisfying
all the constraints is called a feasible solution.
Number of feasible solution can be infinite. If there is no such
solution, the problem is said to have an infeasible soluti on.
3. Alternate Optimum Solution: If there are more than one set of
values of decision variables giving the optimum values of the
objective function, then the problem is said to have alternate optimum
solution.
4. Unbounded Solution: If for some problem the val ue of the objective
function can be increased or decreased infinitely, then such a solution
is called an unbounded solution.
5. Corner Point: In LPP, intersection of two (any) Constraints is
called a corner point of the feasible area.
6. Degenerate Solution: In an LPP an optimum solution always lies at
some corner point of the feasible solution. If more than two
constraints are passing through the corner point, it means a redundant
(excess/extra/not needed for the solution) constraint. In such situation
degenerac y occur.
1.2 FORMULATION OF LINEAR PROGRAMMING PROBLEM Example 4: A company manufactures two products A and B, Each using
Machine I and Machine II. Processing time per unit of A are 5 and 6 hours
respectively and that of B are 4 and 5 respectively. Maximu m number of
hours available are 20 for machine I and 22 for machine II. Per unit, profit
of A and B are Rs. 6 and Rs. 5 respectively. Formulate LPP to determine
production of A and B for maximum profit.
Solution : Given A and B are products and I and II ar e products.
Processing time per unit of A are 5 and 6 hours respectively and that of B
are 4 and 5 respectively.
Available time 20 hrs for machine I and 22 hrs for machine II
Profit of product A and product B is Rs. 6 and Rs. 5 respectively.
munotes.in

Page 5

5 Mathematical Foundation for Computer Science 2 Machine Machi ne hrs/unit Total Available Time Product A Product B I 5 4 20 II 6 5 22 Profit/unit(Rs) 6 5 -
Let x 1 and x 2 be the number of units of product A and product B to be
produced respectively. The p roblem can be stated as follows:
Maximize z = 6 x1 + 5 x 2
Subject to 5x1 + 4x 2 ≤ 20
6x1 + 5x 2 ≤ 30
And x1, x2
0
Example 5: ABC Company engaged in diet food. Two food A and B
contains three kinds of vitamins Vit A, Vit B and Vit C. One unit of A
costs Rs. 30 and B costs Rs. 60. One unit of A contains 36 unit of vit A, 3
units of vit B and 20 units of vit C. One unit of B contains 6 unit of vit A,
12 units of vit B and 10 units of vit C. Minimum requirement of vit A and
vit B ia 108 and 36 units and of vit C should not exceed 100 units.
Formul ate LPP.
Solution: Given A and B are two types of food.
Cost per unit of A is Rs. 30 and that of B is Rs. 60. Machine Machine hrs / unit Requirement A B Vit A 36 6 108 Vit B 3 12 36 Vit C 20 10 100 Cost/unit(Rs) 30 60
Let x 1 and x 2 be the number of units of food A and food B. The p roblem
can be stated as follows:
Min z = 30 x1 + 60 x 2
Subject to 36 x 1 + 6 x 2
108
3 x1 + 12 x 2
36
20 x 1 + 10 x 2 ≤ 100
And x1, x2
0
Example 6: CCD at Pune runs 24 hou rs coffee shop. Each waiter has to
work in continuity 8 hrs. But to have continuity in work, waiter are added munotes.in

Page 6

6 Linear Programming Problem at every 4 hrs of interval to work along those who have already completed
4 hrs. The requirement for different 4 hrs period are estimated as follo ws.
Formulate an LPP. Duration (Hrs) Minimum number of waiter required 00 – 04 4 04 – 08 5 08 – 12 7 12 – 16 6 16 – 20 7 20 – 24 3
Solution: Let xj = number of waiters reporting at the beginning of the jth
time interval, j = 1, 2, …., 6
Min z = x 1 + x 2+ x 3+ x 4+ x 5 + x 6
Subject to x6 + x 1
4
x1 + x 2
5
x2 + x 3
7
x3 + x 4

x4 + x 5
7
x5 + x 6
3
And x1, x2
0
1.3 GRAPHICAL MET HOD Once a problem is formulated as mathematical model, the next step is to
solve the problem to get the optimal solution. If the number of decision
variables is only two, a linear programming problem can be solved
graphically.
Steps for Graphical Method :
1. Formulate the mathematical model for the given problem.
2. Draw the x 1 and x 2 axes. The non -negativity conditions x 1
0 and x 2

0 implies that solution area lies only in the 1st quadrant of x 1x2.
3. Plot each of the constraint on the graph. For plotting any line (for each
constraint), choose two points:
One on x 1 axis putting x 2 = 0 and other on x 2 axis putting x 1 = 0
4. Identify the feasible region that satisfies all the
constraints. For the constraints with ≤ sign, munotes.in

Page 7

7 Mathematical Foundation for Computer Science 2 solution area lies below the line (towards the
origin) and that of
sign, solution area lies above the line
(that side of line not facing the ori gin). The area common to all the
constraints is called feasible region. This area may be bounded or
unbounded. Show the feasible region by shading.
5. Find the optimum solution.
Example 7: Solve the following LPP by graphical method.
Maximize z = 4 x1 + 7 x 2
Subject to 6x1 + 12x 2 ≤ 60
5x1 + 5x 2 ≤ 30
And x 1, x2
0
Solution: The non -negativity conditions x 1
0 and x2
0
Solution area lies in first quadrant.
Constraints are of ≤ type, Solution area lies below
the line i. e. towards the origin.
For plotting the line,
Constraint 1: 6x 1 + 12x 2 ≤ 60
When x 1 = 0, x 2 = 5; x1 = 10, x 2 = 0
Constraint 2: 5x 1 + 5x 2 ≤ 30
When x 1 = 0, x 2 = 6; x1 = 6, x 2 = 0

Fig 1.1
munotes.in

Page 8

8 Linear Programming Problem Find the intersection of constraints.
Here the point of intersect ion is B (2, 4).
The feasible area is shown shaded and given by the polygon OABC.
Here the feasible area is bounded/closed.
Optimum solution: Optimum solution always lies at a corner point of the
feasible region/area.
Find the values of the objective function z at the corner points O, A, B
and C.
Maximize z = 4 x1 + 7 x 2
Corner Point Value of z
O (x 1 = 0, x 2 = 0) 4 x 0 + 7 x 0 = 0
A (x 1 = 6, x 2 = 0) 4 x 6 + 7 x 0 = 24
B (x 1 = 2, x 2 = 4) 4 x 2 + 7 x 4 = 36
C (x 1 = 0, x 2 = 5) 4 x 0 + 7 x 5 = 35
Since z = 36 is maximum at (x 1 = 2, x 2 = 4), this is the optimum solution
of the given LPP.
Example 8: Solve the following LPP by graphical method.
Minimize z = 2 x1 + 3 x 2
Subject to 2x1 + 2x 2
12
6x1 + 3x 2
18
And x1, x2
0
Solution: The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
Constraints are of
type, Solution area lies above the line.
For plotting the line,
Cons traint 1: 2x 1 + 2x 2
14
When x 1 = 0, x 2 = 7; x1 = 7, x 2 = 0
Constraint 2: 6x 1 + 8x 2
48
When x 1 = 0, x 2 =6; x1 = 8, x 2 = 0
munotes.in

Page 9

9 Mathematical Foundation for Computer Science 2

Fig 1.2
Find the intersection of constraints.
Here the point of intersection is B (3, 4).
Shade th e feasible area. Here the feasible area is unbounded.
Find the values of the objective function z at the corner points A(7, 0),
B(3, 4). and C(0, 8).
Minimum z = 2 x1 + 3 x 2
Corner Point Value of z
A (x 1 = 7, x 2 = 0) 2 x 7 + 3 x 0 = 14
B (x 1 = 3, x 2 = 4) 2 x 3 + 3 x 4 = 18
C (x 1 = 0, x 2 = 8) 2 x 0 + 3 x 8 = 24
Since z = 14 is minimum at (x 1 = 3, x 2 = 4), this is the optimum solution of
the given LPP.
Example 9: A company produces pen A and pen B. Profit is Rs. 5 and Rs.
per pen respectively. Raw mate rial requirement of pen A is twice of pen
B. Supply of raw material is sufficient for 1000 pens of type A and B. Pen
needs special clips, 400 such clips are available for A and for B 700 clips
are available. Formulate problem of LPP and solve it for maximi zing
profit by graphical method. Types of Pen Availability A B Raw Material 2 1 1000 Profit (Rs.) 5 4 -
Solution: First, we formulate the LPP as follows.
Objective Function, munotes.in

Page 10

10 Linear Programming Problem Max z = 5x 1 + 4x 2
Subject to 2x1 + x 2 ≤ 1000
x1 ≤ 400
x2 ≤ 700
And x1, x2
0
The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
Constraints are of ≤ type, Solution area lies below
the line i. e. towards the origin.
For plotting the line,
Constraint 1: 2x 1 + x 2 ≤ 1000
When x 1 = 0, x 2 = 1000; x1 = 500, x 2 = 0
Constraint 2: x 1 ≤ 400

x1 = 400
Constraint 3: x 2 ≤ 700

x2 = 700

Fig 1.3

Find the intersection of constraints.
Here the points of intersection are B (400, 200) and C (150, 700)
The feasible area is shown shaded and given by the polygon OABCD. munotes.in

Page 11

11 Mathematical Foundation for Computer Science 2 Here the feasible area is bounded/closed.
Optimum solution: Optimum solution always lies at a corner point of the
feasible region/area.
Find the values of the objective function z at the corner points O, A, B,
C and D.
Maximize z = 5x1 + 4x 2
Corner Point Value of z
O (x 1 = 0, x 2 = 0) 5 x 0 + 4 x 0 = 0
A (x 1 = 400, x 2 = 0) 5 x 400 + 4 x 0 = 2000
B (x 1 = 400, x 2 = 200) 5 x 400 + 4 x 200 =280 0
C (x 1 = 150, x 2 = 700) 5 x 150 + 4 x 700 = 3550
D (x 1 = 700, x 2 = 0) 5 x 700 + 4 x 0 = 3500
Since z = 3550 is maximum at (x 1 = 150, x 2 = 700), this is the optimum
solution of the given LPP.
Example 10: Solve the following LPP by graphical method.
Max z = 200 x + 300 y
Subject to 5 x + 4 y ≤ 200
3 x + 5 y ≤ 150
5 x + 4 y
100
And x, y
0
Solution: The non -negativity conditions x
0 and y
0
Solution area lies in first quadrant.
Constraints are of ≤ type as well as
type
For plotting the line,
Constraint 1: 5 x + 4 y ≤ 200
When x = 0, y = 50; x = 40, y = 0
Constraint 2: 3 x + 5 y ≤ 150
When x = 0, y = 30; x = 50, y = 0
Constraint 3: 5 x + 4 y
100
When x = 0, y = 25; x = 20, y = 0 munotes.in

Page 12

12 Linear Programming Problem

Fig 1.4
Find the intersection of constraints.
Here the point C is the intersection of constraint 1 and constraint 2.
To find the coordinate of point C, we solve constraint 1 and constraint 2
simultaneously.
i.e. Constraint 1 x 3
15x + 12y = 600
and Constraint 2 x 5
15x + 25y =750
x = 30.8 and y = 11.5
The feasible area is shown shaded and given by the polygon ABCDE.
Optimum solution: Optimum solution always lies at a corner point of the
feasible region/area.
Find the values of the objective function z at the corner points A, B, C,
D and E.
Max z = 200 x + 300 y
Corner Point Value of z
A (x = 20, y = 0) 200 x 20 + 300 x 0 = 4000
B (x = 40, y = 0) 200 x 40 + 300 x 0 = 8000
C (x = 30.8, y = 11.5) 200 x 30.8 + 300 x 11.5 = 9610
D (x = 0, y = 30) 200 x 0 + 300 x 30 = 9000
A (x = 0, y = 25) 200 x 0 + 300 x 25 = 7500
Since z = 9610 is maximum at (x = 30.8, y = 11.5), this is the optimum
solution of the given LPP. munotes.in

Page 13

13 Mathematical Foundation for Computer Science 2 1.4 SPECIAL CASES IN LPP 1. Redun dant Constraint: A constraint in a given programming problem
is said to be redundant if the feasible region of the problem is unchanged
by deflecting that constraint.
Example 11: Solve the following LPP by graphical method.
Max z = 25x 1 + 20 x 2
Subject to 6x1 + 4x 2 ≤ 240
2x1 + 4x 2 ≤ 200
3x1 + 4x 2 ≤ 360
And x 1, x2
0
Solution: The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
For plotting the line,
Constraint 1: 6x 1 + 4x 2 ≤ 240
When x 1 = 0, x 2 = 60; x1= 40, x 2 = 0
Constraint 2: 2x 1 + 4x 2 ≤ 200
When x 1 = 0, x 2 = 50; x1= 100, x 2 = 0
Constraint 3: 3x 1 + 4x 2 ≤ 360
When x 1 = 0, x 2 = 90; x1= 120, x 2 = 0

Fig 1.5 munotes.in

Page 14

14 Linear Programming Problem In LPP, every constraint forms boundary of the feasible regio n. However
if any constraint does not define boundary of feasible region is called
redundant constraint. In above example third constraint does not define the
boundary of feasible region. Therefore, it is redundant constraint. It is not
necessary for the s olution and can be eliminate from the problem.
2. Multiple Solution: So far we have seen that the optimal solution of any
LPP lies at corner point of the feasible region and solution is unique.
However, in certain cases a given LPP may have more than on e optimal
solution
Example 12: Solve the following LPP by graphical method.
` Max z = 100x 1 + 150 x 2
Subject to 8x1 + 12x 2 ≤ 720
x1 ≤ 60
x2 ≤ 40
And x 1, x2
0
Solution: The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
For plotting the line,
Constraint 1: 8x 1 + 12x 2 ≤ 720
When x 1 = 0, x 2 = 60; x1= 90, x 2 = 0
Constraint 2: x 1 ≤ 60
x1 = 6
Constraint 3: x 2 ≤ 40
x2 = 40




munotes.in

Page 15

15 Mathematical Foundation for Computer Science 2

Fig 1.6
The feasible area is sho wn shaded and given by the polygon OABCD.
Optimum solution always lies at a corner point of the feasible region/area.
Find the values of the objective function z at the corner points O, A, B,
C and D.
Max z = 100x 1 + 150 x 2
Corner Point Value of z
O (x 1 = 0, x 2 = 0) 100 x 0 + 150 x 0 = 0
A (x 1 = 60, x 2 = 0) 100 x 60 + 150 x 0 =6000
B (x 1 = 60, x 2 = 20) 100 x 60 + 150 x 20 = 9000
C (x 1 = 30, x 2 = 40) 100 x 30 + 150 x 40 = 9000
D (x 1 = 0, x 2 =40) 100 x 0 + 150 x 40 = 6000
Thus, the maximum value of Z is 9000 and it occurs at two corner points,
B and C.
The problem has multiple solution.
3. Unbounded Solution: LPP may have unbounded solution which means
it has no limit on constraints. The common feasible region is not bounded
at any respect.
Example 13: Solve the following LPP by graphical method.
Max z = 30x 1 + 15 x 2
Subject to 4x1 + 6x 2
12
4x1 + x 2
4 munotes.in

Page 16

16 Linear Programming Problem And x1, x2
0
Solution: The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
For plotting the line,
Constraint 1: 4x 1 + 6x 2
12
When x 1 = 0, x 2 = 2; x1= 3, x 2 = 0
Constraint 2: 4x 1 + x 2
4
When x 1 = 0, x 2 = 4; x1= 1, x 2 = 0

Fig 1.7
In the given graph, feasible region has no upper boundary. Hence solution
is infinitely large (as we want to find Max). This is called unbounded
solution.
4. Infeasible Solution: If it is not possible to find a feasible solution that
satisfies a ll the constraints, then LPP is said to have an infeasible solution
or inconsistence.
Example 14: Solve the following LPP by graphical method.
Max z = 25x 1 + 35 x 2
Subject to 3x1 + 5x 2
15
2x1 + 3x 2 ≤ 6
And x1, x2
0 munotes.in

Page 17

17 Mathematical Foundation for Computer Science 2 Solution: The non -negativity conditions x 1
0 and x 2
0
Solution area lies in first quadrant.
For plotting the line,
Constraint 1: 3x 1 + 5x 2
15
When x 1 = 0, x 2 = 3; x1= 5, x 2 = 0
Constraint 2: 2x 1 + 3x 2 ≤ 6
When x 1 = 0, x 2 = 2; x1= 3, x 2 = 0

Fig 1.8
As there is no common region. There is no point that satisfies both the
quadrant. Thus, the given LPP has no feasible solution.
Limitation of Graphical Method: It is possible to find a graphic solution
of LPP, even if number of decision variables are THREE, but it will be
cumbersome. For more than THREE variable case, a graphic solution will
be impossible.
1.5 SUMMARY Linear programming is widely used technique in various problems of
management. The problem should have well defined objective function
with decision variables. The objective function is of maximization when
we deal with profit and it is of type minimization when we deal with the
cost. The decision variable interact with each other through set of
constraints.
A linear programming problem with two -decision variable can be solved
by graphical method. Any non -negative solution which satisfies all the
constraints is the feasible solution of the problem. The collection of all
feasible solution is ca lled feasible region. The optimum solution of LPP
always lies at a corner point of the feasible region/area. In some problems, munotes.in

Page 18

18 Linear Programming Problem there may be more than one solution. It is also possible that LPP has no
finite solution, sometimes problem may have infeasible s olution. . If more
than three decision variables are there in LPP then graphical method will
be impossible.
1.6 REFERENCES Books:
1. Operations Research Techniques for Management – V. K. Kapoor
2. Operations Research – Prem Kumar Gupta and D. S. Hira
3. Quantitat ive Techniques in Management – Vohra
Website:
https://www.cengage.com/resource_uploads/static_resources/0324312652/
8856/chap7.html
https://web.williams.edu/Mathematics/sjmiller/public_html/BrownClasses/
54/handouts/LinearProgramming.pdf
1.7 EXERCISE Exercise 1: A nutrition program for babies have proposed two types of
food (Food I and Food II) available in the standard packets of 50 grams.
The cost per packet are Rs. 2 and 3 respectively. Vitamin availability in
each of food per packet and minimum requirement for each type of
vitamin a re given in the following table. Vitamins Vitamins availability per packet Minimum Requirement I II A 2 1 6 B 6 2 14 Cost/packet 2 3 -
Formulate LPP to determine the optimal combination of food types with
minimum cost such that the minimum requirem ent of vitamins in each
type is satisfied.
Exercise 2: In a multispecialty hospital, nurses report for duty at the end
of hour period, as shown in the table. Each nurse will work for 8 hours
after reporting for the duty. Interval No. Time Period Minimum number of nurses required From To 1 12 mid night 4 am 18 2 4 am 8 am 23 3 8 am 12 noon 35 munotes.in

Page 19

19 Mathematical Foundation for Computer Science 2 4 12 noon 4 pm 30 5 4 pm 8 pm 22 6 8 pm 12 mid night 15
Formulate an LPP such that total number of nurses reporting for duty is
minimized.
Exercise 3: Five items are to be loaded on a ship. The weight, volume and
return per unit of each item are given in the table below. The ship cannot
carry a weight more than 120 units and volume more than 115 units.
Formulate an LPP. Item No. Weight Volume Return (Rs) 1 6 2 5 2 7 8 9 3 3 5 7 4 3 6 6 5 7 4 3
Exercise 4: Solve the following LPP by graphical method.
Max z = 8 x1 + 9 x 2
Subject to 11x 1 + 9x 2 ≤ 9900
7x1 + 12x 2 ≤ 8400
6x1 + 16x 2 ≤ 9600
And x 1, x2
0
Exercise 5: Solve the following LPP by graphical method.
Max z = 4 x1 + 8 x 2
Subject to 2x1 + 4x 2 ≤ 48
x1 + 3x 2 ≤ 42
x1 + x 2 ≤ 21
And x 1, x2
0
Exercise 6: Solve the following LPP by graphical method.
Minimize z = 10x 1 + 20 x 2
Subject to x1 + 3x 2
3
x1 + x 2
2
And x 1, x2
0 munotes.in

Page 20

20 Linear Programming Problem Exercise 7: Solve the following LPP by graphical method.
Max z = 60x 1 + 100 x 2
Subject to x1 + x 2 ≤ 9
x1
2
x2
3
30 x 1 + 60 x 2 ≤ 360
And x 1, x2
0





*****
munotes.in

Page 21

21
2
SIMPLEX METHOD, BIG M METHOD
AND TWO PHASE METHOD
Unit structure
2.0 Objectives
2.1 Introduction
2.2 Simplex Method
2.3 Big M Method
2.4 Two Phase Method
2.5 Summary
2.6 References
2.7 Exercise
Self-Learning Topics: S pecial Cases of LPP
2.0 OBJECTIVES After going through this chapter, students will able to:
● Identify and write a linear problem in standard form.
● Convert inequality constraints to equations.
● Know the use and interpretation of slack, surplus and artificial
variables.
● Check for opt imality (to determine entering and leaving variable) by
performing pivoting operations.
● Identify the optimal solution.
2.1 INTRODUCTION Linear programming is a very well -known method in the field of
optimization theory. In last chapter we used graphical method to solve the
linear programming problem. But when numbers of decision variables are
more than two, it is very difficult to solve LPP by graphical method. To
deal with this difficulty, a highly efficient method for solving LPP is used.
This method ca n applied for any number i. e. more than two decision
variables and is called Simplex Method.
2.2 SIMPLEX METHOD Simplex method is one of the most popular and used algorithms in
optimization theory. The Simplex method was developed during Second
World War by Dr. George Dantzig. His linear programming models
helped the Allied forces with transportation and scheduling problems. munotes.in

Page 22

22 Simplex Method, Big M Method And Two Phase Method This method uses the basic concepts of matrix algorithm and theory of
equation.
To solve a linear programming prob lem using the si mplex method:
1. First we write the problem in standard canonical form by converting
inequalities into equations by introducing slack variables.
2. Write objective function and constraints in the matrix form. The table
contains n decision variables and m (equ al to number of the
constraints) slack variables. The variables with non -zero values are
called the basic variables, their constraint coefficient make an identity
matrix.
3. Construct the initial simplex table.
4. Check for optimality (Determine entering variab le and select leaving
variable) and identify pivot element.
5. Create a new tableau (next iteration)
6. Identify optimal values.
Some definitions:
1. Basic variable: A variable whose coefficient is “unity: in only one of
the constraints and “zero” in the remaini ng constraints is called a
Basic variable.
2. Basis: The set of all basic variables (= m, the number of constraints)
is called the Basis.
3. Canonical Form: If in the standard form of an LPP, each constraint
has a Basic variable, then such form of the LPP is c alled Canonical
Form.
4. Basic Feasible Solution: Any solution of an LPP where exactly m
(equal to number of the constraints) variables have non zero values
satisfying all the constraints, is called a Basic Feasible Solution.
5. Basic variables: The variables w ith non -zero values are called the
vasic variables, their constraint coefficients make Identity Matrix.
Example 1: Max Z = 6x 1 +8x 2
Sub to 5x1 +10x 2
60
4x1 +4x 2
40
And x1, x2
0
Solution:
Step 1: write the prob lem in standard canonical form by converting
inequalities into equations by introducing slack variables Si’s for each munotes.in

Page 23

23 Mathematical Foundation for Computer Science 2 inequality. The coefficient of each slack variable is unity. All these slack
variables will also be appear in the objective function with zero
coefficient.
Max Z = 6x 1 +8x 2 + 0S 1 + 0S 2
Sub to 5x 1 +10x 2 + S 1
60
4x1 +4x 2 +S2 = 40
And x1, x2, S1, S2
0
Step 2: Write objective function and constraints in the matrix form.
Table 1 Variables x1 x2 S1 S2 bi Constraints 5 10 1 0 60 4 4 0 1 40 Cj 6 8 0 0 z
From above Table 1, it is clear that the problem now amounts to solve m
equations in m + n variables (m slack variables and n decision variables)
such that z is maximum.
Here m = 2 and n = 2
Put x 1 = 0 and x 2 = 0 in above equations,
We get, S 1
60 and S 2 = 40 --------------------- (1)
This is initial basic feasible solution.
Step 3: Construct the initial simplex table as follows:
Table 2: Initial Simplex Table CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 0 S1 5 10 1 0 60
6 ** 0 S2 4 4 0 1 40
10 Cj 6 8 0 0 - Zj 0 0 0 0 0 Cj - Zj 6 8* 0 0 -
First column in Table 2 is Objective Column (old value) which contain
coefficient of objective function of Basic Variables (Current solution
(CB i))
Second column is Basic Variable column. In the initial table slack
variables are Basic Variables.
Here, S 1
and S 2 are basic variables. munotes.in

Page 24

24 Simplex Method, Big M Method And Two Phase Method To the right of basic variables column, columns of decision varia bles x 1 x2
, …and slack variables S 1, S2, … will be there.
First row contain coefficient of decision and slack variables of the first
constraint.
Second row contain coefficient of decision and slack variables of the
second constraint.
Next column is sol ution column which contain value of basic variable.
To find the scope of improvement, calculate row title Z j and C j - Zj
Zj is the present contribution of the jth variable to the objective function z
where
Zj =
, j = 1, 2, ….., m + n
=
, j = 1, 2, ….., 4
i.e Z 1= (0.5) + (0.4) = 0; Z2= (0.10) + (0.4) = 0;
Z3= (0.1) + (0.0) = 0; Z4= (0.0) + (0.1) = 0
Where
is the technological coefficient of the jth variable in the ith row
(constraint).
Cj - Zj is the change in the value of the objective function per unit of the
jth variable.
In the above Table 2, all Z j = 0
Step 4: Check for optimality:
To determine entering variable:
a. Maximization Problem: If all (Cj - Zj) values are
0, then present
solution i s optimal. Otherwise, select the variable with max (C j - Zj) as
the entering variable. Column corresponding to the selected variable
is called the Key Column and is marked by *.
For the present problem, all (C j - Zj)
0, therefore the current
solution is not optimal.
Max (C j - Zj) = 8 and corresponds to x 2. Hence x 2 enters the solution
and the 2nd column is the key column.
b. Minimization Problem: If all Cj - Zj values are
0, then present
solution is optimal. Otherwise the variable with highesr negative
value will enter the solution. Column corresponding to the selected
variable is called the Key Column and is marked by *.

munotes.in

Page 25

25 Mathematical Foundation for Computer Science 2 Selecting the leaving variable: Feasibility Conditions :
In a basic feasible solution, number of non -zero var iable must be equal to
the number of constraints. Thus, one of the basic variables has to leave the
solution and take the position of entering variable. i.e. should become
equal to 0.
The following steps to be taken:
i. For each row, find the ratio of the el ements of the solution column to
the elements of the key column.
i.e. Ratio =
i.e. 60/ 10 = 6; 40/4 = 10
ii. The row corresponding to the smallest positive ratio will be the Key
Row and the corresponding basic variable will leave the solutio n.
For the above problem, the smallest +ve ratio is 6 corresponds to the 1st
row.
Hence, row 1 is the Key Row
The corresponding basic variable S 1 will be the leaving variable.
Note: If there is tie in selecting Key -Column and Key -Row, the element
can be selected arbitrarily.
The intersection of Key Column and Key Row is called Key Element or
Pivot Element.
For the above example, Key Element is 10.
Step 5: Next Iteration:
i. Replace the outgoing variable by the entering variable in the basic
variable colu mn and calculate , Key Row =

R1 (Key Row) = R 1 / (Key Element) i.e. R 1 (Key Row) = R 1 / 10
ii. Bring the column corresponding to the entering variable in the form
of the outgoing variable as follows:
New values of the next iteration table are gi ven by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For above example,
R2(New) = R 2(old) – 4 R 1 (New)
a 21 = 4 – 4 (1/2) = 2; a 22 = 4 – 4 (1) = 0;
a 23 = 0 – 4 (1/10) = -2/5; a 24 = 1 – 4 (0) = 2;
b2 = 40 - 4(6) = 16 munotes.in

Page 26

26 Simplex Method, Big M Method And Two Phase Method Therefore, the Iteration 1 will be as follows:
Table 3: Iteration 1 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 8 x2 1/2 1 1/10 0 6
12 0 S2 2 0 -2/5 1 16
8 ** Cj 6 8 0 0 - Zj 4 8 4/5 0 48 Cj - Zj 2* 0 -4/5 0 -
After computing New values of aij, bi and completing the entries of CBi
and Basic variable columns,
i. Compute the values of Z j
Zj =
, j = 1, 2, ….., m + n
=
, j = 1, 2, ….., 4
i.e Z 1= 8.(1/2) + (2 . 0) = 4; Z2= 8.(1) + (2 . 0) = 8;
Z3= 8.(1/10) + ( -2/5).0 = 4/5; Z4= 8.0 + 1.0 = 0
ii. Find C j - Zj
iii. Test for optimality (Decide the entering variable if required)
iv. Test for feasibility (Decide the leaving variable if required)
[Note that these above steps ( i to iv) form the part of each iteration]
From the above Table 3, all values of (C j - Zj) are
0.
The only +ve value is 2, corresponds to the 1st column.
Thus, 1st column is the key column and variable x 1 enters the solution.
Minimum +ve ratio of solution column to key column is 8 and
corresponding variable S 2 leaves the solution.
The key element (element at the intersection of key column and key row)
is 2.
Now go for second iteration.
R2 (Key Row) = R 2 / (Key Element)
R1(New) = R 1(old) – ½ R 2 (New)
a 11 = 1/2 – (1/2)1 = 2; a 12 = 1 – (1/2)0 = 0; munotes.in

Page 27

27 Mathematical Foundation for Computer Science 2 a 13 = 1/10 + (1/2)1/5 = 1/5; a 14 = 0 – (1/2)1/2 = ¼;
b1 = 6 - (1/2)8 = 2
Compute the values of Z j and Find C j - Zj
Table 4 below gives the values of second iteration using the method f or
first iteration.
Table 4: Iteration 2 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 8 x2 0 1 1/5 -1/4 2 No need to calculate 6 x1 1 0 -1/5 1/2 8 Cj 6 8 0 0 - Zj 6 8 2/5 1 64 Cj - Zj 0 0 -2/5 -1 -
Now all (C j - Zj)
0
Present solution is optimal.
No need for feasibility test. No need to find ratio column.
Here x 1 = 2 and x 2 = 8
Max Z = 6x 1 +8x 2 = 6 x 2 + 8 x 8 = 64
Example 2: Max Z = 4x 1 + 3x 2 +6x 3
Sub to 2x 1 +3x 2+2x 3
440
4x1 +3x 3
470
2x1 +5x 3
430
and x1, x2, x3
0
Solution:
Step 1: write the problem in standard canonical form by converting
inequalities into equations by introducing slack variables Si’s for each
inequality. The coef ficient of each slack variable is unity. All these slack
variables will also be appear in the objective function with zero
coefficient.
Max Z = 4x 1 + 3x 2 +6x 3 + 0S 1 + 0S 2 + 0S 3
Sub to 2x1 +3x 2+2x 3 + S 1 = 440
4x1 +3x 3 + S 2 = 470
2x1 +5x 3 + S 3 = 430 munotes.in

Page 28

28 Simplex Method, Big M Method And Two Phase Method and x1, x2, x3
0
Here Slack variables, m = 3 and decision variables, n = 3
Put x 1 = 0 , x 2 = 0 and x 3 = 0 in above equations,
We get, S 1
440, S 2 = 470 and , S 3 = 430 --------------------- (1)
This is initial basic feasib le solution.
Step 3: Construct the initial simplex table as follows:
Table 1: Initial Simplex Table CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 S3 0 S1 2 3 2 1 0 0 440 440/2 220 0 S2 4 0 3 0 1 0 470 156.66** 0 S3 2 5 0 0 0 1 430
Cj 4 3 6 0 0 0 - Zj 0 0 0 0 0 0 0 Cj - Zj 4 3 6* 0 0 0 -
Compute Z j =
, j = 1, 2, …..
For above example,
Z1 = 0.2 +0.4 + 0. 2 = 0 ; Z2 = 0.3 +0.0 + 0. 5 = 0;
Z3 = 0.2 +0.3 + 0. 0 = 0; Z4 = 0.1 +0.0 + 0. 0 = 0;
Z5 = 0.0 + 0.1 + 0. 0 = 0; Z6 = 0.0 +0.0 + 0. 1 = 0
Compute C j - Zj
Since it is a maximization problem, optima will be if (C j - Zj)
0
Now all (C j - Zj)
0
Largest +ve value 6 corresponds to third column.
Thus column 3 is the key column and x 3 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

i. e. 440/2 = 220; 470/ 3 =156.66; 430/0 =

Row corresponding to the smallest +ve ratio will be the key row.
Here it is 156.66 and corresponds to R 2. munotes.in

Page 29

29 Mathematical Foundation for Computer Science 2 Thus, R 2 is the Key Row and therefore S 2 is the outgoing variable.
The key element is 3. [Element at the intersection of Key row and Key
Column]
Next Iteration: Iteration 1 :
Replace the outgoing variable by the entering variable in the basic variable
column
i.e. Replace S 2 by x 3 and put the value of C 3 at CB 2.
and calculate Key Row =

R2 (Key Row) = R 2 / (Key Element) i.e.R 2 = R 2/3
Bring the column corresponding to the entering variable in the form of the
outgoing variable as follows:
New v alues of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For above example,
R1(New) = R 1(old) – 2 R 2 (New)
a 11 = 2 – 2(4/3) = -2/3; a 12 = 3 – 2(0) = 3;
a 13 = 2 – 2(1) = 0; a 14 = 1 – 2(0) = 1;
a 15 = 0 – 2(1/3) = -2/3; a 16 = 0 – 2(0) = 0;
b1 = 440 – 2(156.66) = 126.68
For above example, in row R3, element below key element is already 0.
Therefore, no need to do calculations for R3.
Find Z j
Zj =
, j = 1 , 2, …..
Z1 = 0.( -2/3) +6.(4/3) + 0. 2 = 8 ; Z2 = 0.3 +6.0 + 0. 5 = 0;
Z3 = 0.0 +6.1 + 0. 0 = 6; Z4 = 0.1 +6.0 + 0. 0 = 0;
Z5 = 0.( -2/3) +6.(1/3) + 0. 0 = 2; Z6 = 0.0 +6.0 + 0. 1 = 0
and C j - Zj
Therefore, the Iteration 1 will be as follows:

munotes.in

Page 30

30 Simplex Method, Big M Method And Two Phase Method Table 2: Iteration 1 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 S3 0 S1 -2/3 3 0 1 -2/3 0 126.68 42.22** 6 x3 4/3 0 1 0 1/3 0 156.66
0 S3 2 5 0 0 0 1 430 86 Cj 4 3 6 0 0 0 - Zj 8 0 6 0 2 0 936.96 Cj - Zj -4 3* 0 0 -2 0 -
Since it is a maximization problem, optima will be if (C j - Zj)
0
Now all (C j - Zj)
0
Largest +ve value 3 corresponds to second column.
Thus column 2 is the key column and x 2 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

i. e. 126.68/3 = 42.22; 156.66/ 0 =
; 430/5 = 86
Row corresponding to the smallest +ve ratio will be the key row.
Here it is 42.22 and corresponds to R 1.
Thus, R 1 is the Key Row and therefore S 1 is the outgoing variable.
The key element is 3. [Element at the intersection of Key row and Key
Column]
Next Iteration: Iteration 2
Replace the outgoing variable by the entering variable in the basic variable
column
i.e. Replace S 1 by x 2 and put the value of C 2 at CB 2.
and calculate
Key Row =

R1 (Key Row) = R 1 / (Key Element)
i.e.R 1 = R 1/3
Bring the column corresponding to the entering variable in the form of the
outgoing variable as follows:
New values of the next iteration table are given by (in each row) munotes.in

Page 31

31 Mathematical Foundation for Computer Science 2 i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For above example,
R3(New) = R 3(old) – 5 R 1 (New)
a 31 = 2 – 5 (-2/9) = 28/9; a 32 = 5 – 5 (1) = 0;
a 33 = 0 – 5 (0) = 0; a 34 = 0 – 5 (1/3) = -5/3;
a 35 = 0 – 5 (-2/9) = 10/9; a 36 = 1 – 5 (0) = 1;
b3 = 430 – 5 (42.22) = 208.9
For above example, in row R2, element below key element is already 0.
Therefore, no need to do calculations for R2.
Find Z j
Zj =
, j = 1, 2, …..
Z1 = 3.( -2/9) +6.(4/ 3) + 0.(28/9) = -10/3; Z2 = 3.1 +6.0 + 0. 0 = 3;
Z3 = 3.0 +6.1 + 0. 0 = 6; Z4 = 3.(1/3) +6.0 + 0.( -5/3)
=1;
Z5 = 3.( -2/9) +6.(1/3) + 0.(10/9) = 4/3; Z6 = 3.0 +6.0 + 0. 1 = 0
and C j - Zj
Therefore, the Iteration 2 will be as follows:
Table 3: Iterati on 2 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 S3 3 x2 -2/3 1 0 1/3 -2/9 0 42.22 6 x3 4/3 0 1 0 1/3 0 156.66 0 S3 28/9 0 0 -5/3 10/9 1 218.9 Cj 4 3 6 0 0 0 - Zj 22/3 3 6 1 4/3 0 1066.62 Cj - Zj -10/3 0 0 -1 -4/3 0 -
All (C j - Zj )
0
The present solution is optimal.
Here x 1 = 0, x 2 = 42.22 and x 3 = 156.66
Max Z = 4x 1 + 3x 2 +6x 3 = (4 x 0) + (3 x 42.22) + (6 x 156.66) = 1066.62 munotes.in

Page 32

32 Simplex Method, Big M Method And Two Phase Method 2.3 BIG M METHOD If some of the constraints are of ‘=’ o r ‘
’ type, then in the standard form
such constraint will not have basic variables (and we will not have a
canonical form). To overcome this difficulty the Big M Method is used,
where M is a large positive quantity. For the constraints with ‘= ’ or ‘
’
sign we introduce new variables called the ‘Artificial Variables’. There are
two methods to deal with the artificial variables.
1. Big M Method
2. Two Phase Method
These artificial variables are fictitious and cannot have any physical
meani ng.
Following points to be consider while using artificial variable:
● Only one artificial variable will appear in any constraint.
● Coefficient of an artificial variable is unity in that constraint.
● Number of artificial variable is equal to the number of cons traints of
the type ‘=’ or ‘
’
● Cost coefficient of an artificial variable will be (+M) for a
minimization problem and ( -M) for a maximization problem.
● Once an artificial variable goes out of the solution, it is not allowed
to re -enter. For thi s purpose, the corresponding column is deleted
from the Simplex Table for further calculations usually.
Example 3: Min Z = 2x 1 + 3x 2
Sub to x 1 +x2
6
7x1 +x2
14
and x1, x2
0
Solution: Write the problem in the standard form.
Min Z = 2x 1 + 3x 2 + 0S 1 + 0S 2
Sub to x 1 +x2 - S1 = 6
7x1 +x2 - S2 = 14
and x1, x2, S1, S2
0 , Si’s are called surplus variables.
As the value of S 1 = S 2 = -1 so these are not basic variable and therefore
this is not a canonical form.
To convert it into canonical form, introduce artificial variables A 1 and A 2
with cost +M, where M is a large +ve number. munotes.in

Page 33

33 Mathematical Foundation for Computer Science 2 Now the problem can be expressed as,
Min Z = 2x 1 + 3x 2 + 0S 1 + 0S 2 + MA 1 + MA 2
Sub to x 1 +x2 - S1+ A 1 = 6
7x1 +x2 - S2 + A 2 = 14
and x1, x2, S1, S2, A1, A2
0
Now A 1 and A 2
are Basic Variables and the solution is A 1 = 6 and A 2
=14
We make the initial simplex table.
Table – 1: Initial Simplex Table CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 A1 A2 M A1 1 1 -1 0 1 0 6
6 M A2 7 1 0 -1 0 1 14
2** Cj 2 3 0 0 M M - Zj 8M 2M -M -M M M 20M Cj - Zj 2- 8M* 3-2M M M 0 0 -
Compute Z j =
, j = 1, 2, …..
For above
Z1 = M.1 + M.7 = 8M; Z2 = M.1 + M.1 = 2M;
Z3 = M.( -1) + M.0 = -M; Z4 = M.0 + M.( -1) = -M;
Z5 = M.1 + M.0 = M; Z6 = M.0 + M.1 = M
Compute C j - Zj
Since it is a minimization problem optima will be if (C j - Zj)
0
[If C j - Zj include M, ignore the numeric term for big M method]
Now all (C j - Zj)
0
Largest –ve value -8M corresponds to first column.
Thus column 1 is the key column and x 1 is the entering variable. munotes.in

Page 34

34 Simplex Method, Big M Method And Two Phase Method Now find entries of the ratio.
i.e. Ra tio =

Row corresponding to the smallest +ve ratio will be the key row.
Here it is 2 and corresponds to R 2.
Thus, R 2 is the Key Row and therefore A 2 is the outgoing variable.
The key element is 7. [Element at the intersection of Key row and Key
Column]
Next Iteration: Iteration 1
Replace the outgoing variable by the entering variable in the basic variable
column
i.e. Replace A 2 by x 1and put the value of C 1 at CB 2.
and calculate Key Row =

R2 (Key Row) = R 2 / (Key Element) i.e. R 2 = R 2/7
Bring the column corresponding to the entering variable in the form of the
outgoing variable as follows:
New values of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For a bove example,
R1(New) = R 1(old) – R2 (New)
a 11 = 1 – 1 = 0; a 12 = 1 – 1/7 = 6/7;
a 13 = -1 – 0 = - 1; a 14 = 0 – (-1/7) = 1/7;
a 15 = 1 – 0 = 1; a 16 = 0 – (1/7) = - 1/7;
b1 = 6 - 2 = 4
Find Z j and C j - Zj
Therefore, the Iteration 1 will be as follows:




munotes.in

Page 35

35 Mathematical Foundation for Computer Science 2 Table 2: Iteration 1 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 A1 A2 M A1 0 6/7 -1 1/7 1 -1/7 4
14/3 ** 2 x1 1 1/7 0 -1/7 0 1/7 2
14 Cj 2 3 0 0 M M - Zj 2
+
-M
+
M
-
4M +4 Cj - Zj 0
-
* M
-
0
+
-
Note: We could have deleted the column 5 corresponding to the outg oing
artificial variable. Removing the outgoing artificial variable for
calculations of the next iteration does not affect future process of finding
the optima, but reduces the computations.
All (C j - Zj)
0
Largest –ve value corresponds to second column.
Thus column 2 is the key column and x 2 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

Row corresponding to the smallest +ve ratio will be the key row.
Here it is 14/3 and corresponds to R 1.
Thus outgoi ng variable is A 1 and key element is 6/7.
Next Iteration: Iteration 2
In the Simplex Table [Table 3], replace the outgoing variable by the
entering variable in the basic variable column
i.e. Replace A 1 by x 2 and put the value of C 2 at CB 1.
and calculate Key Row =

R1(Key Row) = R 1 / (Key Element) i.e. R 1 = R 2/(6/7)
New values of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row) munotes.in

Page 36

36 Simplex Method, Big M Method And Two Phase Method For above example,
R2(New) = R 2(old) – (1/7)R 1 (New)
a 21 = 1 – (1/7).0 = 1; a 22 = 1/7 – (1/7).1 = 0;
a 23 = 0 –(1/7).( -7/6) 0 = 1/6; a 24 = (-1/7) – (1/7).(1/6) = -1/6;
b2 = 2 – (1/7)(14/3) = 4/3
Find Z j and C j - Zj
Therefore, the Iteration 2 will be as follows:
[Note: Here we remove the c olumns A 1 and A 2]
Table 3: Iteration 2 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 3 x2 0 1 -7/6 1/6 14/3 (14/3)/(1/6) =28 ** 2 x1 1 0 1/6 -1/6 4/3 (-ve) Cj 2 3 0 0 Zj 2
-19/6 1/6 50/3 Cj - Zj 0
19/6 -1/6 * -
Now there is still one C j - Zj value corresponds to column 4 which is < 0.
Thus column 4 is the key Column and S 2 is the entering variable.
The smallest +ve ratio [in this case only +ve ratio] is 28 corresponds to R 1.
Thus R 1 is the Key Row, x 2 is the outgoing variable and 1/6 is the Key
Element.
Next Iteration: Iteration 3
In the Simplex Table [Table 4], replace the outgoing variable by the
entering variable in the basic variable column
i.e. Replace x 2 by S 2 and put 0 in the place of 3 (CB 1).
and calculate
Key Row =

R1(Key Row) = R 1 / (Key Element)
i.e. Divide Key Row R 1 by the Key Element [R 1 = R 2/(1/6)]
New values of the next iteration table are given by (in each row) munotes.in

Page 37

37 Mathematical Foundation for Computer Science 2 i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row )
For above example,
R2(New) = R 2(old) – (-1/6)R 1 (New)
a 21 = 1 – (-1/6).0 = 1; a 22 = 0 – (-1/6).6 = 1;
a 23 = (1/6) – (-1/6).( -7) = -1; a 24 = (-1/6) – (-1/6).1 = 0;
b2 = 4/3 – (-1/6)(28) = 4/3
Find Z j and C j - Zj
Therefore, the Iteration 3 will be as follows:
Table 4: Iteration 3 CBi Basic
Variables Variables Solution (bi) x1 x2 S1 S2 0 S2 0 6 -7 1 28 2 x1 1 1 -1 0 6 Cj 2 3 0 0 Zj 2
-2 0 12 Cj - Zj 0
2 0 -
All (C j - Zj )
0
The pres ent solution is optimal.
Here x 1 = 6, S 2 = 28 and x 2 = 0
Min Z = 2x 1 + 3x 2 = 2 x 6 + 3 x 0 = 12
Example 4: Max Z = 10x 1 + 15x 2
Sub to 2x 1 + 2x 2
160
x1 + 2x 2
120
4x1 + 2x 2
280
x2
45
and x1, x2
0
Solution: Write the problem in the standard form.
Max Z = 10x 1 + 15x 2 + 0S 1 + 0S 2 + 0S 3 + 0S 4
Sub to 2x 1 + 2x 2 + S 1 = 160
x1 + 2x 2 + S 2 = 120
4x1 + 2x 2 + S3 = 280 munotes.in

Page 38

38 Simplex Method, Big M Method And Two Phase Method x2 - S4 = 45
and x1, x2, S1, S2 , S3, S4
0
Since m = 4 there must be 4 basic variables and there are only 3.
The last x 2 - S4 = 45 does not have a basic variable.
Introducing artificial variable A 1, with cost coefficient as – M.
Max Z = 10x 1 + 15x 2 + 0S 1 + 0S 2 + 0S 3 + 0S 4 -M A 1
Sub to 2x 1 + 2x 2 + S 1 = 160
x1 + 2x 2 + S 2 = 120
4x1 + 2x 2 + S3 = 280
x2 - S4 + A 1= 45
and x1, x2, S1, S2 , S3, S4, A1
0
Now A 1 is Basic Variables and the solution is A 1 = 45
We make the initial simplex table.
Table – 1: In itial Simplex Table : CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 S3 S4 A1 0 S1 2 2 1 0 0 0 0 160
=80 0 S2 1 2 0 1 0 0 0 120
= 60 0 S3 4 2 0 0 1 0 0 280
= 140 - M A1 0 1 0 0 0 -1 1 45
45** Cj 10 15 0 0 0 0 -M Zj 0 -M 0 0 0 M -M -45M Cj - Zj 10 15+M* 0 0 0 -M 0 -
Compute Z j =
, j = 1, 2, …..
Compute C j - Zj
Since it is a maximization problem optima will be if (C j - Zj)
0
[If C j - Zj include M, ignore the numeric term for big M method]
Now all (C j - Zj)
0
Largest +ve value (15 + M) corresponds to second column. munotes.in

Page 39

39 Mathematical Foundation for Computer Science 2 Thus column 2 is the key column and x 2 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

Row corresponding to the smallest +ve ratio will be the key row.
Here it is 45 and corresponds to R 4.
Thus, R 4 is the Key Row and therefore A 1 is the outgoing variable.
The key element is 1. [Element at the intersection of Key row and Key
Column]
Next Iteration: Iteration 1
Replace the outgoing variable by the entering variable in the basic variable
column
i.e. Replace A 1 by x 2 and calculate
Key Row =

R4 (Key Row) = R 4/ (Key Element)
i.e. R 4 = R 4/1]
Bring the column corresponding t o the entering variable in the form of the
outgoing variable as follows:
New values of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For above example,
R1(New) = R 1(old) – 2R4 (New)
R2(New) = R 2(old) – 2R4 (New)
R3(New) = R 3(old) – 2R4 (New)
Find Z j and C j - Zj
Therefore, the Iteration 1 will be as follows:




munotes.in

Page 40

40 Simplex Method, Big M Method And Two Phase Method Table 2: Iteration 1 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 S3 S4 0 S1 2 0 1 0 0 2 70
= 35 0 S2 1 0 0 1 0 2 30
= 15** 0 S3 4 0 0 0 1 2 190
= 95 15 X2 0 1 0 0 0 -1 45 -ve value Cj 10 15 0 0 0 0 Zj 0 15 0 0 0 -15 675 Cj - Zj 10 0 0 0 0 15* -
Note: We have deleted the column 7 corresponding t o the outgoing
artificial variable (A 1).
All (C j - Zj)
0
Largest +ve value corresponds to sixth column.
Thus column 6 is the key column and S 4 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

Row corresp onding to the smallest +ve ratio will be the key row.
Here it is 15 and corresponds to R 2.
Thus outgoing variable is S 2 and key element is 2.
Next Iteration: Iteration 2
In the Simplex Table [Table 3], replace the outgoing variable by the
entering variab le in the basic variable column
i.e. Replace S 2 by S 4 and and calculate
Key Row =
i.e R 2 = R 2/2
New values of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row)
For abo ve example,
R1(New) = R 1(old) – 2R2 (New) munotes.in

Page 41

41 Mathematical Foundation for Computer Science 2 R3(New) = R 3(old) – 2R2 (New)
R4(New) = R 4(old) + R 2 (New)
Find Z j and C j - Zj
Therefore, the Iteration 2 will be as follows:
Table 3: Iteration 2 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 S3 S4 0 S1 1 0 1 -1 0 0 40
= 40 0 S4 1/2 0 0 1/2 0 1 15
= 30** 0 S3 3 0 0 -1 1 2 160
= 53.33 15 X2 1/2 1 0 1/2 0 0 60
= 120 Cj 10 15 0 0 0 0 Zj 15/2 15 0 0 0 0 900 Cj - Zj 5/2* 0 0 -15/2 0 0 -
All (C j - Zj)
0
Largest +ve value corresponds to first column.
Thus column 1 is the key column and S 1 is the entering variable.
Now find entries of the ratio.
i.e. Ratio =

Row corresponding to the smallest +ve ratio will be the key row.
Here it is 30 and corresponds to R 2.
Thus outgoing variable is S 4 and key element is 1/2.
Next Iteration: Iteration 3 :
In the Simplex Table [Table 3], replace the outgoing variable by the
entering variable in the basic variabl e column
i.e. Replace S 4 by x 1 and calculate Key Row =
i.e. R 1= R 1/(1/2)
New values of the next iteration table are given by (in each row)
i.e. New ith Row = Old ith Row - (New element of R i) x (Key Row) munotes.in

Page 42

42 Simplex Method, Big M Method And Two Phase Method For above example,
R1(New) = R1(old) – R2 (New)
R3(New) = R 3(old) – 3R2 (New)
R4(New) = R 4(old) – 1/2 R 2 (New)
Find Z j and C j - Zj
Therefore, the Iteration 3 will be as follows:
Table 4: Iteration 3 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 S1 S2 S3 S4 0 S1 0 0 1 -2 0 -2 10 10 x1 1 0 0 1 0 2 30 0 S3 0 0 0 -4 1 -6 70 15 x2 0 1 0 0 0 -1 45 Cj 10 15 0 0 0 0 Zj 10 15 0 0 0 0 975 Cj - Zj 0 0 0 0 0 0 -
Now, all (C j - Zj)
0
Solution is optimal.
x1 = 30 and x 2 = 45
Max Z = 10x 1 + 15x 2
= 10 (30) + 15 (45) = 975
2.4 TWO PHASE METHOD This is an alternative method of Big M method for computerized solution.
Following are the steps of Two phase Method:
Step 0 [Initial step]: Obtain canonical form [by introducing slack/sur plus
and artificial variables.]
Phase 1:
Step 1: Form the modified problem
Min z = sum of artificial variables i.e. min z = A 1 + A 2 + …. + A n munotes.in

Page 43

43 Mathematical Foundation for Computer Science 2 Subject to the same set of constraints and non -negativity conditions.
Note: Whatever the original problem (max /m in) the modified phase 1
problem will always be a minimization problem.
Step 2: Apply simplex method till the optimality is reached.
Step 3: Check
a) If the value of objective function (sum of artificial variables (i.e. z) is
0 in the optimal table.
b) If the mo dified z
0 then the problem has no feasible solution.
c) If the modified z = 0, go to Phase 2.
Phase 2:
Step 1: From the optimal table of Phase 1, drop all the columns of
artificial variables which are non -basic.
Step 2: If some artificial varia bles are in the basic solution with value 0
then in the original objective function put their cost coefficient = 0
Step 3: Find the optimal solution of the original problem using the optimal
solution of the Phase 1 as the initial solution. All cost coeffi cients will be
originals.
Example 5: Min Z = 12x 1 + 18x 2 + 15x 3
Sub to 4x 1 + 8x 2 + 6x 3
64
3x1 + 6x 2 + 12x 3
96
and x1, x2
0
Solution:
Step 0: Min z = Min Z = 12x 1 + 18x 2 + 15x 3 + 0 S 1 + 0 S 2 + M A 1 + MA 2
Sub to 4x 1 + 8x 2 + 6x 3 - S1 + A 1 = 64
3x1 + 6x 2 + 12x 3 – S2 + A 2 = 96
and x1, x2 , x3, S1, S2, A 1, A2
0
This is required canonical form.
Phase 1:
Step 1: Form the modified problem
Min Z m = sum of artificial variables
Min Z m = A 1 + A 2 (cost coe. Of all other variables = 0)
Sub to 4x 1 + 8x 2 + 6x 3 - S1 + A 1 = 64 munotes.in

Page 44

44 Simplex Method, Big M Method And Two Phase Method 3x1 + 6x 2 + 12x 3 – S2 + A 2 = 96
and x1, x2 , x3, S1, S2, A 1, A2
0
Step 2: Find the optimal solution of this modified problem

Table – 1: Initial Simplex Ta ble CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 A1 A2 1 A1 4 8 6 -1 0 1 0 64
= 32/3 1 A2 3 6 12 0 -1 0 1 96
= 8** Cj 0 0 0 0 0 1 1 Zmj 7 14 18 -1 -1 1 1 160 Cj - Zmj -7 -14 -18* 1 1 0 0 -
All (C j - Zm j)
0.
x3 is entering variable , A2 is outgoing variable and 12 is Key Element
Table – 2: Iteration 1 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 A1 1 A1 5/2 5 0 -1 1 /2 1 16
** 0 x3 1/4 1/2 1 0 -1/12 0 8
= 16 Cj 0 0 0 0 0 1 Zmj 5/2 5 0 -1 1 /2 1 16 Cj - Zmj -5/2 -5* 0 0 -1/ 2 0 -
All (C j - Zm j)
0.
X2 is entering variable , A1 is outgoing variable and 5 is Key Element



munotes.in

Page 45

45 Mathematical Foundation for Computer Science 2 Table – 3: Iteration 2 CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 0 x2 1 /2 1 0 -1/5 1/10 16/5 0 x3 0 0 1 1/10 -2/15 32/5 Cj 0 0 0 0 0 Zmj 0 0 0 0 0 0 Cj – Zmj 0 0 0 0 0 -
Step 3: Since all (C j - Zm j)
0.
This solution is optimal .
The value of Z mj = 0 therefore the problem is feasible and we can go to
Phase II
Phase II:
Steps 1 and 2: [ All cost coefficients will be originals]
Table – 4: Initial Table Phase II CBi Basic Variables Variables Solution (bi) Ratio x1 x2 x3 S1 S2 18 x2 1 /2 1 0 -1/5 1/10 16/5 15 x3 0 0 1 1/10 -2/15 32/5 Cj 12 18 15 0 0 Zj 9 18 15 -21/10 -1/5 768/5 Cj – Zj 3 0 0 21/10 1/5 -
Since, all (C j - Zj)
0.
The current solution (the one given by Phase I itself) is optimal.
Optimal Solution: x 1 = 0, x 2 = 16/5 and x 3 = 32/5
Min Z = 12x 1 + 18x 2 + 15x 3
= 12(0) + 18(16/5) + 15(32/5) = 768/5
[Note: The optimal solution of Phase 1 need not be optimal for the
original problem and phase II will usually need more than one iterations.]
2.5 SUMMARY The Simplex method is an approach to solving linear programming models
by hand. After studying this chapter, students are able to introduce slack
variables, surplus variables and artificial variable to convert the munotes.in

Page 46

46 Simplex Method, Big M Method And Two Phase Method inequalities into equalities and ab le to get canonical form. Also able to
find optimal solution using tableau and pivot variables (Key Element).
Students are able to used Big M Method and Two Phase Method to find a
best feasible solution by adding artificial variable. In Two Phase method,
the whole procedure of solving a linear programming problem involving
artificial variables is divided into two phases. In phase I, form a new
objective function by assigning zero to every original variable. Then we
try to eliminate artificial variables. The solution at the end of phase I
serves as a basic feasible solution for Phase II. In Phase II the original
objective function is introduced and by using usual method we find an
optimal solution.
2.6 REFERENCES Books:
1. Operations Research Techniques for Ma nagement – V. K. Kapoor
2. Operations Research – Prem Kumar Gupta and D. S. Hira
3. Quantitative Techniques in Management – Vohra
Websites:
https://www.cengage .com/resource_uploads/static_resources/0324312652/
8856/chap7.html
https://web.williams.edu/Mathematics/sjmiller/public_html/BrownCla sses/
54/handouts/LinearProgramming.pdf
http://ecoursesonline.iasri.res.in/mod/page/view.php?id=2939
http://arts.brainkart.com/article/big -m-method --introduction --1123/
2.7 EXERCISE Q.1 Solve by Simplex Method
a) Max Z = 10x 1 + 4x 2
Sub to 20x 1 + 10x 2
1200
40x 1 +10x 2
1600
and x1, x2, x3
0 [Ans: x1 = 20, x 2 = 80, Max Z = 520]

b) Max Z = 25 x + 20 y
Sub to 6 x + 4 y
3600
2 x + 4 y
2000 munotes.in

Page 47

47 Mathematical Foundation for Computer Science 2 and x, y
0 [Ans: x = 400, y = 300, Max Z = 16000]

c) Max Z = 3x 1 + 2x 2 + 5x 3
Sub to x 1 + 2x 2 + x 3
430
3x1 + 2 x 3
460
x1 + 4 x 3
420
and x1, x2, x 3
0 [Ans: x 1 = 250, x 2 = 550/8, x 2 = 170/4, Max Z =
1100]
d) Max Z = 12x 1 + 15x 2 + 14 x 3
Sub to 6x 1 + 5x 2 + 10 x 3
76
2x1 + x 2 - x3
20
3x1 - 3x2 + 6 x 3
50
and x1, x2, x3
0
e) Max Z = 10x 1 + 15x 2 + 20 x 3
Sub to 2x 1 + 4x 2 + 6 x 3
24
3x1 + 9x 2 + 6x 3
30
and x1, x2, x3
0 [ Ans: x 1 = 6, x 2 = 0, x 3 = 2, Max Z = 100]
Q.2 Solve by Big - M Method
a) Min Z = 2x 1 + 3x 2
Sub to 3x 1 + 5x 2
30
5x1 + 3x 2
60
and x1, x2
0 [ Ans: x 1 = 12, x 2 = 0, S 1 = 6, Min Z = 24]
b) Min Z = 25x 1 + 30x 2
Sub to 4x 1 + 3x 2
60
2x1 + 3x 2
36
and x1, x2
0 [Ans: x 1 = 12, x 2 = 4, Min Z = 420]
c) Min Z = 12x 1 + 20x 2
Sub to 6x 1 + 8x 2
100
7x1 + 12x 2
120 munotes.in

Page 48

48 Simplex Method, Big M Method And Two Phase Method and x1, x2
0 [ Ans: x 1 = 15, x 2 = 5/4, Min Z = 205]
d) Min Z = 10x 1 + 15x 2 + 20x 3
Sub to 2x 1 + 4x 2 + 6x 3
24
3x1 + 9x 2 + 6x 3
30
and x1, x2
0
Q.2 Solve by Two Phase Method.
a) Max Z = 5x 1 - 4x2 + 3 x 3
Sub to 2x 1 + x 2 - 6 x3
20
6x1 + 5x 2 + 10 x 3
76
8x1 - 3x2 + 6 x 3
50
and x1, x2, x3
0 [Ans: x 1 = 55/7, x 2 = 30/7, Max Z = 155/7]
b) Max Z = x 1 + 2x 2 + x 3
Sub to x 1 + x 2 + x3
7
2x1 - 5x2 + x3
10
and x1, x2, x3
0 [Ans: x 1 = 45/7, x 2 = 4/7, x 3 =0, Max Z = 53/7]
Self-Learning Topics: Special Cases of LPP
1. Tie between key column: If (C j - Zj) is most positive for two
variables indicating two entering variables are possible then select the
column with largest positive (C j - Zj) from left to right of matrix.
x1 x2 S1 S2 Cj - Zj -10 8 select 8 3
Example: Max Z = 10x 1 + 4x 2 + 6 x 3
Sub to 3x1 + 2x 2 + 6 x 3
240
2x1 + 3x 2 + 3 x 3
270
x1
60
and x1, x2, x3
0
2. Unbounded Solution: If all (Cj - Zj) is positive indicating that
solution is not optimal but all the ratios are negative (negative or 0)
indicating that no variable is ready to come out. This is the case of
unbounded solution. munotes.in

Page 49

49 Mathematical Foundation for Computer Science 2 Example: Max Z = 4x 1 + x 2 + 3 x 3 + 5x 4
Sub to 4x1 - 6x2 - 5 x3 - 4x4
20
-3x1 - 2x2 + 4x 3 + 4x 4
10
-8x1 - 3x2 + 3x 3 + 2x 4
20
and x1, x2, x3, x4
0

3. Infeasible Solution: If artificial variable is in basic variable with non
zero value i.e. artificial variable is the part of the solution. Hence it is
called infeasible solution.
Example: Min Z = x 1 + 2x 2 + x 3
Sub to x1 +
x2 +
x3
1

x1 + 2x 2 + x 3
8
and x1, x2, x3
0
4. Alternate Solution: If (Cj - Zj) = 0 for non basic variable and all other
(Cj - Zj)
0 or negative then it indicates case of alternate solution.
To get alternate solu tion, do one more iter ation by taking key column as
aentering column with (Cj - Zj) = 0 for non -basic variable.
Example: Max Z = 30x 1 + 20x 2
Sub to x1 + 2x 2
80
3x1 + 2x 2
120
and x1, x2
0





*****
munotes.in

Page 50

50 UNIT II
3
TRANSPORTATION PROBLEM
Unit Structure
3.0 Transportation Problem
3.1. Objective
3.2 Introduction
3.3. Definition of Transportation Problem
3.3.1 Balanced Transportation Problem
3.3.2 Unbalanced Transportation Problem
3.3.2 a-demand Greater than supply
3.3.2 b-Demand less than supply
3.4 Solution of Transportation Problem
3.4.1 Initial Basic feasible solution
3.4.1 a. North West Corner method
3.4.1 b. Least Cost Method
3.4.1 c.Vogel’s Approximation method
3.5 Optimum solution
3.5.1 MODI method
3.6 List of Reference
3.1 OBJECTIVE This chapter would make you understand the following concepts:
● Discuss the concept of transportation problem
● Definition of transportation problem
● Three cases occur in transportation problem
● Method to find initial basic solution with example
● Method to find optimal solution with example
3.2 INTRODUCTION In mathematical science "operation research" acts important role. When
we are perform any operation means perform some action to solve
problem. In this unit we are discus s transportation problem technique. In
transportation problem transport goods from setup sources /origin to set of
destination in such a way that total transportation cost is minimised. munotes.in

Page 51

51 Mathematical Foundation for Computer Science 2 Discuss transportation concept with the help of example. Suppose a
manufacturer of soap company has three plants situated at place A,B and
C. Suppose his buyer are located in different region P,Q and R where he
has to supply then the soap(goods).Also assume the demand in the three
region and the production in different plant s per unit time period are
known and the cost out transporting one box to each center is given. The
manufacturer's problem is to determine as to how he should rate this his
product from his plant to the market place so that the total cost involved in
the transportation is minimised. In other word how many soap boxes are
deliver from A to P, Q and R; how many from B to P, Q and R; how many
from C to P,Q and R to achieve 8 and list transportation cost is minimum.


The place where the soap goods originate a re called source or origin and
place where they are supplied are called destination. In the above example
the manufacturer is to decide as how many units to be transported from
different origin to different destinations so the total cost is minimum and
this is the concept of transportation problem.
3.3 DEFINITION OF TRANSPORTATION PROBLEM (HITCH COCK PROBLEM) Transportation problem is linear programming problem. Consider a
transportation problem with m origin n destination with their respective
available c apacity a1, a2, a3….am and respect to demand as b1, b2…. bn.
Mathematically transportation problem may be stated as follows:
Minimise (Total cost) Z=
CijXij Subject to



Supply/Capacity

……………..up to

Constraint
Similarly
munotes.in

Page 52

52 Transportation Problem

Demand / Requirement

…………up to
Constraint
The problem is to transport the goods at minimum cost from source to destination. it is called transportation problem. The transportation problem can be stated as in th e following tabular form :
1 2 3 ………… N Supply 1 C11 C12 C13 C1n a1 X11 X12 X13 …………. X1n 2 C21 C22 C23 C2n a2 X21 X22 X23 ………… X2n 3 C31 C32 C33 C3n a3 X31 X32 X33 ………… X3n Demand b1 b2 b3 ………… bn
According to the tabular form,
ai = Quantity of product available at origin i
bj = Quantity of product available at origin j
Cij = Cost of transportation one unit of th e product from I th origin to j
th destination
Xij = Quan tity transported from i th origin to j th destination.
Then the problem is to determine the transportation operation so is to
minimise the total transportation cost satisfying supply and demand
condition.
Transportation problem can be divided into two cate gories.

3.3.1 Balanced Transportation Problem:
In balance transportation problem check sum of availability of constrain
(demand) equal to the sum of requirements (supply) means check munotes.in

Page 53

53 Mathematical Foundation for Computer Science 2

Demand = Supply
Consider a given example with three origin and three destination. P Q R Supply A 3 6 7 90 B 3 5 2 10 C 5 2 5 20 Demand 60 30 30 60+30+30=120 Equal to 90+10+20=120


3.3.2 Unbalanced Transportation Problem:
Unbalanced transportation problem arises due to shortage of raw mate rial,
improper planning, shortage of transport and time scheduling. In
unbalanced transportation problem check sum of availability of constraints
is equal or not equal to sum of requirement.it it is not equal then either it
can be greater than or less than . In unbalanced transportation have two
cases:

3.3.2. a. Demand is grater is greater than supply:
For balancing the unbalanced the problem can be solved by introducing
the dummy source (row) added. The unit transportation cost to dummy
row are assigned t o zero value and perform demand - supply and place the
result to the corresponding dummy destination. Discuss the c oncept with
the help of example: P Q R Supply A 3 6 7 90 B 3 5 2 10 C 5 2 5 20 Demand 50 50 40 50+50+40=140> 90+10+20=120 munotes.in

Page 54

54 Transportation Problem The problem is unbalanced transportation problem.


140 > 120
To convert it into balanced transportation problem include a dummy
source(row). P Q R Supply A 3 6 7 90 B 3 5 2 10 Demand-supply (40-20=20) C 5 2 5 20 D1 0 0 0 20 Demand 50 50 40
After check demand = Supply.
P Q R Supply A 3 6 7 90 B 3 5 2 10 C 5 2 5 20 D1 0 0 0 20 Demand 50 50 40 140=140
Yes, Problem converted to balanced transportation problem.
3.3.2. b. Demand is less than supply :
In demand variation may be occur in real life because of customer of
preference, New product comes in market, product cost etc. Due to this
demand variation our problem is converted into unbalanced problem.
To solve this unbalanced the problem (demand is less than supply) and
destination ( column) with supply. The unit transportation cost for dummy
column are assigned to zero value and for subtract supply from demand
and place the result to corresponding dummy supply. P Q R S Supply A 5 4 2 6 10 B 8 3 5 7 50 C 10 11 3 1 30 D 9 12 6 3 20 Demand 30 40 20 10 100 < 110
munotes.in

Page 55

55 Mathematical Foundation for Computer Science 2 The given problem is unbalanced transportation problem.
Demand < Supply

To convert it into balanced transportation problem include a destination
(column). P Q R S S1 Supply A 5 4 2 6 0 10 B 8 3 5 7 0 50 C 10 11 3 1 0 30 D 9 12 6 3 0 20 Demand 30 40 20 10 10
Yes the problem converted to balanced transportation problem.
P Q R S S1 Supply A 5 4 2 6 0 10 B 8 3 5 7 0 50 C 10 11 3 1 0 30 D 9 12 6 3 0 20 Demand 30 40 20 10 10 110=110
Remember:
Demand> Supply
Add a dummy row with cost zero and supply equal to (demand - supply)
DemandAdd column with cost zero and demand equal to (supply - demand)
3.4 SOLUTION OF TRANSPORTATION PROBLEM The solution of transportation problem can be obtained in two stages: A)
initial solution B) optimal solution.To update initial basic feasible solution
using any one of the three.
A-1) North West Corner Rule
A-2) least cost method/Matrix minima method
A-3) Vogel's approximation method
To obtain optimal soluti on using any one of the following:
B-1) MODI method
B-2) Stepping Stone Method munotes.in

Page 56

56 Transportation Problem 3.4.1 Initial Feasible Solution:
In previous chapter we have learnt about solve transportation problem
with the help of simplex simplex method is complex to solve problem.
Hindi lesson we will look for an alternate solution to solve transportation
problem. To solve the transportation problem first check total capacity
equal to total requirement that is balanced problem.
The existence of initial feasible solution necessary and sufficient
condition -
1) Rim condition -

2) Number of allocation=m+n -1
(Where m is number of rows and n number of column)
If the above condition is satisfied the solution obtained is a non -
degenerate. When number of positive allocation in initial basic solution
less than m+n -1 the solution is said to be degenerate solution.
Number of allocation< m+n -1……….. degenerate solution
Number of allocation=m+n -1…………non - degenerate solution
The initial feasible solution can be obtained by following three method
1. North West Corner Method
2. Least cost method/ Matrix minima method
3. Vogel's approximation method/ penalty method
3.4.1. a. NCWR method :
Tabular form of transportation problem : 1 2 3 ………….. n Supply 1 C11 C12 C13 C1n a1 X(1,1) X(1,2) X(1,3) ……………. X(1,n) 2 C21 C22 C23 C2n a2 X(2,1) X(2,2) X(2,3) ……………. X(2,n) 3 C31 C32 C33 C3n a3 X(3,1) X(3,2) X(3,3) …………… X(3,n) Demand b1 b2 b3 ………….. bn Consider a transportation method Xij denote th e unit transportation cost
from ith origin to jth destination a1, a2, a3,………,an are respective supply
and b1,b2,b3……bn are respect demand. munotes.in

Page 57

57 Mathematical Foundation for Computer Science 2 Steps for the methods are:
1. Begin with the upper left hand corner X(1,1) cell of transportation
table and allocat e as many unit as possible equal to minimum between
available capacity/ supply and demand/ requirement.
2. Balance the supply and demand units in the respective rows and
column allocation.
3.
a) If the supply for the first row is pending then move down (↓) to the
first sale in second row and first column 21 and locate minimum (bi -
ai, a2) then go to step to for balance the supply and demand unit.
b) If the demand for the first column is satisfied then moved horizontally
(→) to the next sale in the second column and first row and supplied
the quantity as per step 1 then go to step to for adjust the supply and
demand.
4. If for any cell supply equal demand then rim condition will occur in
this case move to next allocation can be made in sale other in the ne xt
row or column.
5. Continue the procedure until the total available quantity is fully
allocated to the same as required hence we have basic feasible
solution with m+n -1 positive allocation.
Question -Obtained initial basic feasible solution for the follo wing problem
using the NCWR method.
w1 w2 w3 w4 supply A 6 7 9 3 70 B 11 5 2 8 55 C 10 12 4 7 90 demand 85 35 50 45
Solution : Above problem is balanced transporta tion problem. Start with
the top cell aw1 and allocate min(85,70)=70 . First allocation 70 done here.
Check b1>a1 we move to cell( B,w1) here we are located min( 55,85 -
70)=15Second allocation satisfies 15. Hence we move horizontally to
(B,w2) we allocate min(55 -15,35)=35Third allocation satisfies 35.
According to step 3 b capacity of B still remains thus we move cell (B,w3)
allocate min(55 -15-35,50)=5
Forth allocation satisfies 5.Requirement of B is over. Move vertically
down to cell(c,w3) allocate min(90, 50-5)=45.Fifth allocation satisfy
45.Finally allocate 45 units. munotes.in

Page 58

58 Transportation Problem 1 2 3 n Supply 1 6 7 9 3 70 0 70 2 11 35 5 2 8 55 40 5 0 15 5 3 10 12 4 7 90 45 0 35 45 45 Demand 85 0 50 45 15 45 0 0 0 Check positive location m=3,n=4 we have m+n -1=3+4 -1=6 positive
allocation.
Calculate total cost -70*6+15*11+35*5+5*2+45*4+45*7=1265.
3.4.1. b. Least cost method:
This method consider lowest cost this method give optimum solution then
NCWR.
Step 1 : select the sale with lowest transportation cost among all rows and
column of table.
Step 2 : allocate as many unit as possible to the sale determined in step 1
and eliminate that rom on column either supp ly is exhausted or
demand satisfied.
Step 3 : search the next minimum cost in the table and repeat from step 2 -
repeat above step till all supply and demand are exhausted.
Question : Obtain initial basic sol ution for the following problem w1 w2 w3 w4 supply A 6 7 9 3 70 B 11 5 2 8 55 C 10 12 4 7 90 demand 85 35 50 45
munotes.in

Page 59

59 Mathematical Foundation for Computer Science 2 Solution :
In given problem minimum cost is to which is unique. We select cell
(B,W3). Allocate min(50,55)=50. Requirement of w3 is satisfied a nd
reduced the capacity 55 by 50 and eliminate the column w3. w1 w2 w3 w4 supply A 6 7 9 3 70 B 11 5 2 8 55 5 50 C 10 12 4 7 90 demand 85 35 50 45 0 Search for next minimum in the remaining table. Next minimum cost is 3.
We select (A,W4) can allocate min(45,70)=45 and reduce the capacity 75
by 45. Eliminate column w4. w1 w2 w3 w4 supply A 6 7 9 3 70 25 45 B 11 5 2 8 55 5 50 C 10 12 4 7 90 demand 85 35 50 45 0 0 Next minimum cost element is 5. Select cell (B,w2) and allocate
min(35,5)=5. Satisfies the requirement of w2 and eliminate the row B.
w1 w2 w3 w4 A 6 7 9 3 70 25 45 B 11 5 2 8 55 5 0 5 50 C 10 12 4 7 90 munotes.in

Page 60

60 Transportation Problem 85 35 50 45 30 0 0 Search next minimum cost element is 6. Sele ct cell (A,w1) allocate
min(85,25)=25 and reduce the capacity 85 by 25. Eliminate row A. w1 w2 w3 w4 A 6 7 9 3 70 25 0 25 45 B 11 5 2 8 55 5 0 5 50 C 10 12 4 7 90 85 35 50 45 60 30 0 0
Next minimum cost is 10 select cell (C,w1) and allocate min(60,90)=60
han reduce the capacity and eliminate column w1. w1 w2 w3 w4 A 6 7 9 3 70 25 0 25 45 B 11 5 2 8 55 5 0 5 50 C 10 12 4 7 90 30 60 85 35 50 45 60 30 0 0 0 Last minimum cost is 12 in the remaining table we select (C, w2) cell.
Allocate cell and satisfy the requirement of w3 warehouse. w1 w2 w3 w4 A 6 7 9 3 70 25 0 25 45 B 11 5 2 8 55 5 0 5 50 C 10 12 4 7 90 30 0 60 30 munotes.in

Page 61

61 Mathematical Foundation for Computer Science 2 85 35 50 45 60 30 0 0 0 0
Ther e is exactly 3 + 4 - 1= 6 allocation.
Total cost is: 25*6+45*3+5*5+50*2+60*10+30*12=1370
The cost is less than the cost determine in the solution by NCWR method.
Hence this method very useful and practical oriented.
3.4.1.C. Vogel's approximation method:
This method is also called Penalty method. This method is a pray for the
other two because the initial solution is a much closed to optimal solution.
Steps :
1. Find the difference between smallest cost and next smallest cost in
particular row or column or penalty. Calculate this penalty for each
row and column in the transportation table.
2. Select largest penalty of all transportation table. Hindi rope or column
choose the sale that how the smallest cost and locate the maximum
possible quantity to the cel l.
3. Adjust the row capacity and column requirement by amount a locate
to the cell in step 2.
4. If only one row or one column is left, we directly allocate the demand.
Question -solve the following transportation problem for initial basic
solution using VAM method : w1 w2 w3 w4 supply A 6 7 9 3 70 B 11 5 2 8 55 C 10 12 4 7 90 demand 85 35 50 45
Solution :
Calculate the difference between smallest cost and next s mallest cost i.e
calculate penalty. Penaulty munotes.in

Page 62

62 Transportation Problem w1 w2 w3 w4 supply A 6 7 9 3 70 0 3 70 B 11 5 2 8 55 20 0 3 3 6← 35 20 C 10 12 4 7 90 60 15 0 3 3 3 3 15 30 45 demand 85 35 50 45 15 0 30 0 0 0 4↑ 2 2 4 1 7
↑ 2 1 1 2 1 1
Select largest penalty of all in above penalty 4 is the largest penalty but it
is not unique. Select any one between them within this column w1 select
smallest cost cell (A,w1) and allocate maximum possible quantity to this
cell.
Remove particular row/ column in which supply/demand is exhausted.
Similar way to calculate penalty for remaining table and allocate cost up to
one row and one cost left directly or locate the demand.
Number of allocation=m+n -1
Solution is a non - degenerate.
Total cost is:
70*6+35*5+20*2+30*4+45*7+10*15=1220
Initial solution is nearest to optimal solution.
3.5 OPTIMALITY TEST: (APPROACH TO OPTIMAL SOLUTION) Once, we get the basic f easible solution for a transportation problem, the
next duty is to test whether the solution got is an optimal one or not?
Optimal solution is achieved when there is no other alternative solution
give lower cost. munotes.in

Page 63

63 Mathematical Foundation for Computer Science 2 An optimality test can be applied to the f easible solution only if it satisfies
the following conditions:
(i) It contains exactly m+n -1 allocations where m and n represent the
number of rows and columns, respectively, of the transportation table.
(ii) These allocations are independent.
This can be done by two methods :
(a) By Modified Distribution Method, or MODI method.
(b) By Stepping Stone Method
3.5.1 Modified Distribution Method (MODI) :
In MODI, we can get the opportunity costs of empty cells without writing
the loop. After getting the op portunity cost of all the cells, we have to
select the cell with highest positive opportunity Cost for including it in the
modified solution.
For modified solution the method follows following steps:
1. First find an initial feasible solution using a suit able method.
2. Check optimality conditions for the current basic feasible solution if it
has exactly
(m+n -1) independent allocations, write the cost matrix for only the
allocated cells.
3. Row 1, row 2,…, row i of the cost matrix are assigned with va riables
U1, U2, …, Ui and the
Column 1, column 2,…, column j are assigned with variables V1, V2,
…,Vj respectively.
4. Using this cost matrix, determine the set of m+n numbers 𝑢𝑖(i
=1,2,…,m) and 𝑣𝑗 (j=1,2,..,n) such that for each occupied cell (i, j),
𝐶𝑖𝑗=𝑢𝑖+𝑣𝑗, taking one of 𝑢𝑖 or 𝑣𝑗 as zero.
5. Fill the vacant cells using 𝑢𝑖+𝑣𝑗.
6. Compute all unit cost differences
Δ𝑖𝑗=𝐶𝑖𝑗−(𝑢𝑖+𝑣𝑗)
by subtract ing the values so obtained in Step 5 from the
corresponding values of the original cost matrix.
7. Examine the sign of each Δ 𝑖𝑗
● If all Δ𝑖𝑗>0, for all i, j; then the current basic feasible solution is an
optimal solution. munotes.in

Page 64

64 Transportation Problem ● (b) If all Δ 𝑖𝑗≥0, for all i, j and at least one Δ 𝑖𝑗 is zero
then the current basic feasible solution is an optimal solution and
multiple basic initial feasible solution exists.
● (c) If some of Δ 𝑖𝑗<0 for some (i, j), the current solution is not optimal.
Then select the cell having the most negative Δ 𝑖𝑗 and tick it.
Question: In initial basic feasible solution is obtained by Matrix
Minimum Method and is shown in table : Distribution Centre D1 D2 D3 D4 Supply Plant P1 19 30 50
7 P2
30
60 10 P3

60
18 Requirement 5 8 7 15
Initial basic feasible solution
12 X 7 + 70 X 3 + 40 X 7 + 40 X 2 + 10 X 8 + 20 X 8 = 894.
Calculating u i and v j using u i + v j = cij
Substituting u 1 = 0, we get
u1 + v 4 = c 14 ⇒ 0 + v 4 = 12 or v 4 = 12
u3 + v 4 = c 34 ⇒ u3 + 12 = 20 or u 3 = 8
u3 + v 2 = c 32 ⇒ 8 + v 2 = 10 or v 2 = 2
u3 + v 1 = c 31 ⇒ 8 + v 1 = 40 or v 1 = 32
u2 + v 1 = c 21 ⇒ u2 + 32 = 70 or u 2 = 38
u2 + v 3 = c23 ⇒ 38 + v 3 = 40 or v 3 = 2 Distribution centre D1 D2 D3 D4 Supply ui Plant P1 19 30 50
7 0 P2
30
60 10 38 P3

60
18 8 Requirement 5 8 7 15 vj 32 2 2 12 munotes.in

Page 65

65 Mathematical Foundation for Computer Science 2 Calculating opportunity cost using c ij – ( ui + v j ) Unoccupied cells Opportunity cost (P1, D1) c11 – ( u1 + v1 ) = 19 – (0 + 32) = –13 (P1, D2) c12 – ( u1 + v2 ) = 30 – (0 + 2) = 28 (P1, D3) c13 – ( u1 + v3 ) = 50 – (0 + 2) = 48 (P2, D2) c22 – ( u2 + v2 ) = 30 – (38 + 2) = –10 (P2, D4) c14 – ( u2 + v4 ) = 60 – (38 + 12) = 10 (P3, D3) c33 – ( u3 + v3 ) = 60 – (8 + 2) = 50 Distribution centre D1 D2 D3 D4 Supply ui Plant P1



7 0 P2



10 38 P3



18 8 Requirement 5 8 7 15 vj 32 2 2 12
Now choose the smallest (most) negative value from opportunity cost (i.e.,
–13) and draw a closed path from P1D1. The following table shows the
closed path. Distribution centre D1 D2 D3 D4 Supply ui Plant P1 7 0 P2 10 38 P3 18 8 Requirement 5 8 7 15 vj 32 2 2 12
Choose the smallest value with a negative position on the closed path(i.e.,
2), it indicates the number of units that can be shipped to the entering cell.
Now add this quantity to all the cells on the corner points of the closed
path marked with plus signs and subtract it from those cells marked with
minus signs. In this way, an unoccupied cell becomes an occupied c ell.
munotes.in

Page 66

66 Transportation Problem Now again calculate the values for u i & v j and opportunity cost. The
resulting matrix is shown below Distribution centre D1 D2 D3 D4 Supply ui Plant P1



7 0 P2



10 51 P3



18 8 Requirement 5 8 7 15 vj 19 2 –11 12
Choose the smallest (most) negative value from opportunity cost (i.e., –
23). Now draw a closed path from P2,D2 . Distribution centre D1 D2 D3 D4 Supply ui Plant P1
7 0 P2 10 51 P3 18 8 Requirement 5 8 7 15 vj 19 2 –11 12
Now again calculate the values for u i & v j and opportunity cost Distribution center D1 D2 D3 D4 Supply ui Plant P1



7 0 P2



10 28
munotes.in

Page 67

67 Mathematical Foundation for Computer Science 2 P3



18 8 Requirement 5 8 7 15 vj 19 2 12 12
Total cost -19*5+30*3+10*5+40*7+12*2+20*13=799
3.6 LIST OF REFERENCE 1. Hamdy A. Taha, University of Arkansas, “Operations Research: An
Introduction”, Pearson, 9th Edition, ©2011, ISBN -13:
9780132555937
2. Sharma, S.D. and Sharma, H. , “Operations R esearch: Theory,
methods and Applications”,KedarNath Ram Nath, 2010, 15, reprint
3. J. K. Sharma, “Operations Research : Theory And Applications” ,
Macmillan India Limited, 2006 (3 Edition),ISBN 1403931518,
9781403931511
4. S. C. Gupta, “Fundamentals of Statistics” – Himalaya Publishing
House, 2017, 7th edition, ISBN 9350515040, 9789350515044
5. Prem Kumar Gupta & D S Hira, S. Chand publications , “Operations
Research”, 7/e, ISBN -13: 978 -8121902816, ISBN -10:
9788121902816
6. A. Ravindran, Don T. Phillip s, James J. Solberg, “Operations
Research: Principles and Practice”, 2nd Edition, January 1987, ISBN:
978-0-471-08608 -6
7. Frederick S. Hillier, Gerald J. Lieberman, Introduction to Operations
Research, McGraw -Hill, 2001,Edition7, illustrated,ISBN
0071181 636, 9780071181631
8. Jerry Banks, John S. Carson, Barry L. Nelson, Contributor Barry L.
Nelson "Discrete -event System Simulation",Prentice Hall, 1996,
Edition 2, illustrated, ISBN 0132174499, 9780132174497
Web References :
1. Operations Research, Prof.Kusu m Deep, IIT -MADRAS,
https://nptel.ac.in/courses/111/107/111107128/
2. Introduction to Operations Research, Prof. G. Srinivasan, IIT -
ROORKEE, https://nptel.ac.in/courses/110/106/110106062/
3. Fundamentals of Operations Research, Prof. G. Srinivasan, IIT -
MAD RAS, https://nptel.ac.in/courses/112/106/112106134/ munotes.in

Page 68

68 Transportation Problem 4. Modeling and simulation of discrete event systems,Prof.P. Kumar Jha,
IIT- ROORKEE, https://nptel.ac.in/courses/112107220/
5. Game Theory, Prof. K. S. MallikarjunaRao, IIT -BOMBAY,
https://nptel.ac.in/co urses/110/101/110101133/
6. Decision Modelling, Prof. BiswajetMahanty, IIT -KHARGPUR,
https://nptel.ac.in/courses/110105082/
7. Karmarkar's Method:
ttps://www.youtube.com/watch?v=LWXXhBIlj0o
8. Karmarkar's Method :
https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm




*****



munotes.in

Page 69

69
UNIT III
4
ASSIGNMENT MODEL
Unit Structure
4.0 Objectives
4.1 Assignment Model
4.2 Hungarian Method for Solving Assignment Problem
4.3 Travelling Salesman Problem
4.4 Summary
4.5 References
4.6 Exercise
4.7 Self Learning Topic
4.0 OBJECTIVES After studyi ng the unit you should be able to:
● Formulate mathematically an assignment problem
● Optimal solution can be obtained by using Hungarian Method
● Special cases of assignment problem viz maximization case, ,
unbalanced assignment problem, restricted assignment p roblem,
alternate optimal solution and travelling salesman problem can be
solved.
4.1 ASSIGNMENT MODEL An assignment problem is a type of linear programming problem or you
can say that it is a special case of transportation problem. The objective of
assign ment model is to allocate number of facilities to number of jobs on
one to one basis i.e. one facility can be assigned to only one job, so as to
minimize the costs and maximize the profits of the jobs. One can notice
situation of this kind in many areas li ke assigning salesmen in different
areas for sales, number of taxis to number of customers, assigning teachers
to classes etc.
4.2 MATHEMATICAL REPRESENTATION OF THE ASSIGNMENT PROBLEM The assignment problem can be represented by n × n matrix, where n
facilities are assigned to n jobs. The matrix is called as cost matrix (cij)
where cij is the cost of assigning ith facility to jth job. munotes.in

Page 70

70 Assignment Model C11 C12 C13……… C1n C21 C22 C23............ C2n …………………………… Cn1 C2n C3n…………Cnn Mathematically, the assignment model can be represented as:
Xij = 1: if ith acility is assigned to jth job
= 0: if ith facility is not assigned to jth job
Minimize Z =


Subject to restrictions (cons traints)




4.2 HUNGARIAN METHOD FOR SOLVING ASSIGNMENT PROBLEM The Hungarian method is an efficient method of solving assignment
problem. The method involves the following steps:
Step 1:
Prepare a cost matrix of the given problem. If the number of rows and
number of columns are equal then matrix will be called as balanced
matrix. If number of rows and number of columns are not equal then
matrix is unbalanced matrix. To convert an unbalanced ma trix to balance
matrix, a dummy row/column is introduced so that matrix becomes
balanced (a square matrix).The cost entries of dummy are always zero.
Step 2:
Row Reduction: Subtract the smallest element of each row from all the
elements of the row. This wi ll result in at least one zero in each row.
Column Reduction: Subtract the smallest element of each column from
all the elements of the column. This will result in at least one zero in each
column. Now each row and column will have at least one zero.
Step 3:
Investigate the rows and columns sequentially, select a row or column
with a single zero element and encircle it (or square it). Mark a X (cross)
in the cells having zero element, lying in the same column or row so that
no further assignments can be don e in that particular column or row. munotes.in

Page 71

71 Mathematical Foundation for Computer Science 2 Again select the next row and encircle (or square) the zero element and
mark a X (cross) in the cells having zero element, lying in the same
column or row so that no further assignments can be done in that
particular col umn or row.
Repeat the process for the remaining rows till all the zero’s are assigned in
each row and column. Each row or column must have one encircled (or
square) zero element in it.
Step 4:
If the number of assignments (zero’s circled or squared) are e qual to
number of row/column, that means we have reached an optimal solution.
The total cost of assignment is obtained by adding original cost values
from the original given cost matrix.
If the number of assignments (zero’s circled or squared) are not equa l to
number of row/column that means no optimal solution is obtained. Go to
step 5.
Step5:
Draw the minimum number of horizontal or vertical straight lines to cover
all the zeroes from the reduced cost matrix (matrix obtained using step 2).
If the number o f straight lines are equal to size of matrix (i.e number of
rows/columns of matrix), the present solution is optimal solution else go to
step 6.
Step 6:
Investigate the uncovered elements of the matrix (elements not covered by
any lines), find the smallest element from uncovered elements. Hence
subtract all the uncovered elements from this smallest uncovered element
and further add the smallest uncovered element to the elements at the
intersection point of two lines. Covered elements will remain unaffected,
no change in their values.
Step 7:
Perform the step 3 and repeat the entire process until optimal solution is
obtained.
Problem 1:
Solve the following assignment problem using Hungarian Method. The
given cost matrix represents the combination of 4 differ ent jobs on 4
different machines. munotes.in

Page 72

72 Assignment Model

Solution:
Since the number of rows and columns are equal we can say that problem
is balanced type.
Step 1:
Choose the minimum element in each row and subtract it from every
element of that row. In this case, 20, 10, 22 a nd 16 are minimum element
from 1st, 2nd, 3rd and 4th row respectively. In this way we get row reduced
matrix.

Step 2:
Choose the minimum element in each column and subtract it from every
element of that column. In this case, 0, 4, 4 and 0 are minimum el ement
from 1st, 2nd, 3rd and 4th column respectively. In this way we get column
reduced matrix.

Step 3:
munotes.in

Page 73

73 Mathematical Foundation for Computer Science 2 Starting with the first row (Machine 1) in table A.5, we examine each
rows until we found a row with single zero (Machine 4). We make an
assignment by encircling that cell. Then we cross other zeroes in that
particular column and row to eliminate the possibility of making further
assignments in that column and row. We repeat the process for other rows
till all the rows have exactly one encircled zero (and columns also). If all
the rows (and columns also) contains exactly one encircled zero or in other
words total number of assignments are equal to size of matrix, we can say
that we have reached an optimal solution.
From table A.5 it is evident that tot al number of assignments (encircled
zeroes) are 4 and size of matrix is also 4, hence we have obtained an
optimal solution.
The pattern of assignments for the combination of machine and jobs are as
follows:

The optimal cost is Rs 76.
Problem 2: Solve the following assignment problem using the Hungarian
method. The cost matrix in the table B.1 represents the combination of
employees and their job status.

Solution: The matrix consist of 5 rows (1,2,3,4,5) and 5 columns
(A,B,C,D,E), since the number of row s and columns are equal, we can say
that matrix is balanced and of minimization (as cost is given) type.
Step 1:
Choose the minimum element in each row and subtract it from every
element of that row. In this case, 10, 14, 8, 6 and 8 are minimum element
from 1st, 2nd, 3rd 4th and 5th row respectively. In this way we get row
reduced matrix. munotes.in

Page 74

74 Assignment Model

Step 2:
Choose the minimum element in each column and subtract it from every
element of that column. In this case, 0, 0, 0,2 and 4 are minimum element
from 1st, 2nd, 3rd 4th and 5th column respectively. In this way we get
column reduced matrix.

Step 3:
Starting with the first row (Employees 1) in table B.3, we examine each
rows until we found a row with single zero (Employees 1). We make an
assignment by encircling that cell. Then we cross other zeroes in that
particular column and row to eliminate the possibility of making further
assignments in that column and row. We repeat the process for other rows
till all the rows have exactly one encircled zero (and columns also) . If all
the rows (and columns also) contains exactly one encircled zero or in other
words total number of assignments are equal to size of matrix, we can say
that we have reached an optimal solution.
From table B.4 it is evident that total number of assig nments (encircled
zeroes) are 4 and size of matrix is 5. The 3rd row (Employees 3) does not
have a single assignment (encircled zero), hence we have not obtained an
optimal solution.
The pattern of assignments for the combination of employees and jobs are
as follows: munotes.in

Page 75

75 Mathematical Foundation for Computer Science 2

Step 4:
Consider Table B.4 and draw minimum number of lines to cover all the
zeroes. We can draw vertical or horizontal lines to cover all the zeroes. To
get minimum number of lines we start with row/column which has
maximum zeroes. Hence we draw 1st horizontal line in the 4th or 5th row as
both the rows has two zeroes. So first horizontal line is drawn on 4th row
and then on 5th row. Now column C consist of two zeroes, to cover these
zeroes we draw a vertical line to cover the zeroes. Then co lumn B consist
of two zeroes out of which one zero ( employees 4 and job B) has
already been covered, so only remaining zero is 1st row (employees 1 and
job B), so we can draw either vertical or horizontal line. Drawing either of
the lines (vertical o r horizontal) will not affect the final outcome. Here we
are drawing a vertical line (employees 1 and job B).After drawing the
lines we will get the following matrix i.e. Table B.5


Identify the smallest value which is not covered by any line (minimum
uncovered value).From table B.5,it is evident that minimum uncovered
value is 2, this value will be subtracted from all the uncovered values and
will be added to the values at the point of intersection (where the two
lines are intersecting) and the remain ing values (covered values) will
remain the same . The resultant matrix is shown in the table B.6.

munotes.in

Page 76

76 Assignment Model Step 6:
Examine all the rows one by one and find the row which have a single
zero. The 1st row and 4th row have a single zero so we will encircle it and
cross other zeroes in that particular column to eliminate the possibility of
making further assignments in that column .Now 2nd row has a single zero
to be encircled (row -Employee -2, column -Job-C) as another zero (lying on
row-Employee -2, column -Job-E) can not be considered because it has been
crossed. We will examine the 3rd row and 5th row in a same way and
encircle the zeroes. Make sure each row consist of only one encircled
zeroes which indicates that all the columns will have single encircled
zeroes.

From Table B.7, number of assignments are 5 and size of matrix is also 5,
hence we can say we have reached an optimal solution. The assignment
schedule is given in Table B.8

The optimal cost is Rs 60.
Problem 3: Solve the following assignment problem usi ng the Hungarian
method. Three jobs A, B and C are to be assigned to the machines. The
processing cost of each job – machine combination matrix is given in the
table C.1
munotes.in

Page 77

77 Mathematical Foundation for Computer Science 2 Solution: The matrix consist of 3 rows (1, 2, 3) and 4 columns (I, II, III,
IV), sin ce the number of rows and columns are not equal, we can say that
matrix is not balanced and of minimization (as cost is given) type. To
apply Hungarian Method the matrix should be of balanced type, so we will
introduce dummy row (as one row is less than th e number of columns)
under the name Dummy where all the entries will be zeroes. Refer Table
C.2 now the number of rows including dummy are 4 and number of
columns are also 4. Hence the matrix is balanced and of minimization type
(cost is given). We can now apply Hungarian Method.

Step 1:
Choose the minimum element in each row and subtract it from every
element of that row. In this case, 6, 1, 2 and 0 are minimum element from
1st, 2nd, 3rd and 4th row respectively. In this way we get row reduced
matrix.

Step 2:
Choose the minimum element in each column and subtract it from every
element of that column. In this case, 0, 0, 0 and 0 are minimum element
from 1st, 2nd, 3rd and 4th column respectively. In this way we get column
reduced matrix.

Step 3:
Startin g with the first row (Job A) in table C.4, we examine each rows
until we found a row with single zero (Job A). In this case 1st has single
zero and we encircle it and marking cross on all other zeroes lying in the munotes.in

Page 78

78 Assignment Model first column. Now 2nd and 3rd row does not have zero to get encircled but
4th row has choice of three zeroes. We can select any zero out of the three
zeroes and encircled it. We make an assignment by encircling that cell.
Then we cross other zeroes in that particular column and row to eliminate
the possibility of making further assignments in that column and row.
From table C.5 it is evident that total number of assignments (encircled
zeroes) are 2 and size of matrix is 4. The 2nd and 3rd row (Job 2 and Job 3)
does not have a single assignment (en circled zero), hence we have not
obtained an optimal solution.
The pattern of assignments for the combination of jobs and machines are
as follows:

Consider Table C.6 and draw minimum number of lines to cover all the
zeroes. We can draw vertical or horiz ontal lines to cover all the zeroes. To
get minimum number of lines we start with row/column which has
maximum zeroes. Hence we draw 1st horizontal line in the Dummy row as
it has four zeroes. So first horizontal line is drawn on Dummy row and
then 1st column consist of four zeroes, to cover these zeroes we draw a
vertical line to cover the zeroes. After drawing the lines we will get the
following matrix i.e. Table C.6.

Identify the smallest value which is not covered by any line (minimum
uncovered value) .From table C.6,it is evident that minimum uncovered
value is 2, this value will be subtracted from all the uncovered values and
will be added to the values at the point of intersection (where the two
lines are intersecting) and the remaining values (cove red values) will
remain the same. The resultant matrix is shown in the table C.7 munotes.in

Page 79

79 Mathematical Foundation for Computer Science 2 .

Step 4:
Now we can do the assignments. Starting with the first row (Job A) in
table C.8, we examine each rows until we found a row with single zero
(Job A). In this case 1st row has single zero and we encircle it and marking
cross on all other zeroes lying in the first column. Now 2nd row has single
zero to be encircled and 3rd row does not have zero to get encircled but 4th
row has choice of two zeroes. We can select any z ero out of the two zeroes
and encircled it. We make an assignment by encircling that cell. Then we
cross other zeroes in that particular column and row to eliminate the
possibility of making further assignments in that column and row.

The number of assi gnments are 3 and size of matrix is 4, hence optimal
solution is not obtained.
Step 5:
Consider Table C.8 and draw minimum number of lines to cover all the
zeroes. We can draw vertical or horizontal lines to cover all the zeroes.
We draw 1st horizontal li ne in the Dummy row as it has three zeroes. So
first horizontal line is drawn on Dummy row and then 1st column consist
of three zeroes and 2nd column consist of two zeroes, and to cover these
zeroes we draw a vertical lines After drawing the lines we wil l get the
following matrix i.e. Table C.9

Step 6:
Identify the smallest value which is not covered by any line (minimum
uncovered value).From table C.9,it is evident that minimum uncovered
value is 2, this value will be subtracted from all the uncovered values and munotes.in

Page 80

80 Assignment Model will be added to the values at the point of intersection (where the two
lines are intersecting) and the remaining values (covered values) will
remain the same. The resultant matrix is shown in the table C.10

Step 7:
Now we can do the assign ments. Starting with the first row (Job A) in
table C.11, we examine each rows until we found a row with single zero
(Job A). In this case 1st row has single zero and we encircle it and marking
cross on all other zeroes lying in the first column. Now 2nd row has two’s
zero out of which one is to be encircled, so we choose zero lying on 2nd
row and 2nd column (Job -B and Machine –II) and marking cross on the
zeroes lying in the 2nd column. 3rd row have single zero lying on 3rd row
and 3rd column (Job -C and M achine –III) to get encircled and 4th row has
also single zero lying on 4th row and 4th column (Job -Dummy and
Machine –IV) to get encircled. After, we obtained the resultant matrix i.e.
Table C.11

Number of assignments are 4 and the size of matrix i s also 4, we can say
that optimal solution is obtained.

The optimal cost is Rs 15
Problem 4: A sales manager has to assign 4 salesman to four territories.
The following table shows the annual profit (in Rs lakh) that has to be munotes.in

Page 81

81 Mathematical Foundation for Computer Science 2 generated by each salesman in each territory. Find optimum assignment of
salesman and territory to maximize the profit.

Solution: The matrix consist of 4 rows (A, B, C.D) and 4 columns (T1,
T2, T3, T4), since the number of rows and columns are equal, we can say
that matrix is bala nced and of maximization type (as profit is given) type.
To apply Hungarian Method the matrix should be of minimization type, so
we will create a regret matrix by selecting the maximum value from the
entire matrix i.e. 80 and subtracting each value by 80. The matrix so
obtained will be consider as Regret Matrix. We can now apply Hungarian
Method to the matrix given in Table D.2

Step 1:
Prepare a Row Reduced matrix by selecting a minimum element from
each row of regret matrix and subtracting it from each e lement of that row.
The minimum elements from each row are 6,0,10 and 16. The following
matrix will be obtained (Table D.3).

Step 2:
Prepare a Column Reduced matrix by selecting a minimum element from
each column of Row Reduced matrix (Table D.3) and sub tracting it from
each element of that column. The minimum elements from each column
are 0, 0, 6 and 0. The following matrix will be obtained (Table D.4). munotes.in

Page 82

82 Assignment Model

Step 3:
Now we can do the assignments. Starting with the first row (Salesman A)
in table D.4, In th is case 1st row has single zero and we encircle it and
marking cross on all other zeroes lying in the fourth column. 3rd row have
single zero lying on 3rd row and 1st column (Salesman -C and Territory -
T1) to get encircled and 4th row has also single zer o lying on 4th row and
2nd column (Salesman –D and Territory -T2) to get encircled. After, we
obtained the resultant matrix i.e. Table D.5

The number of assignments are 3 and size of matrix is 4, hence optimal
solution is not obtained.
Step 5:
Draw m inimum number of lines to cover all the zeroes.

Step 6:
Select the minimum uncovered element from Table D.6 and subtract from
other uncovered elements and minimum uncovered element to the
elements where the two lines are intersecting. In this case minimu m
uncovered element is 4. The following matrix (Table D.7) will be
obtained:

munotes.in

Page 83

83 Mathematical Foundation for Computer Science 2 T1T2T3T4A01680B208120C02208D160812Table D.7 TerritoryAsignment MatrixSalesman

Step 7:
Now we can do the assignments. Starting with the first row (Salesman A)
in table D.8, In this case 1st row has single zero and we encircle it and
marking cross on all other zeroes lying in the first column. 2nd row has
single zero to be encircled, 3rd row and 4th row have single zeroes to be
encircled.. After, we obtained the resultant matrix i.e. Table D.8

The number of assignments are 4 and size of matrix is 4, hen ce optimal
solution is obtained.
Step 8:
The assignment schedule is given in Table D.

The optimal profit is Rs 278.
Problem 5: A manager wants to assign four jobs to four operators and
from his experience he knows that two operators are inefficient to d o two
specific jobs. This is indicated by ‘ - ‘in the cost matrix. Determine the
optimal assignment from the following matrix which gives cost (in
hundred rupees) for employing operators on different jobs. munotes.in

Page 84

84 Assignment Model

Solution: The matrix consist of 4 rows (I, II, II I, IV) and 4 columns (A, B,
C, D), since the number of rows and columns are equal, we can say that
matrix is balanced and of minimization type (as cost is given).Since
operator II cannot perform Job A and operator III cannot perform Job B,
hence it is a pr ohibited or restricted problem. Cost of prohibited or
restricted problem is taken as ‘M’ which indicates infinity. The value ‘M’
will remain as it is throughout the solution. No assignments or no change
in values can happen to value ‘M’. The matrix so obta ined given in Table
E.2

Step 1:
Prepare a Row Reduced matrix by selecting a minimum element from
each row of given matrix and subtracting it from each element of that row.
The minimum elements from each row are 8,12,6 and 4. The following
matrix will be obtained (Table E.3).

Step 2:
Prepare a Column Reduced matrix by selecting a minimum element from
each column of Row Reduced matrix (Table E.3) and subtracting it from
each element of that column. The minimum elements from each column
are 0, 6, 2 and 0 . The following matrix will be obtained (Table E.4). munotes.in

Page 85

85 Mathematical Foundation for Computer Science 2

Step 3:
Now we can do the assignments. Starting with the forth row as it has only
single zero and we encircle it and marking cross on all other zeroes lying
in the 4th column , 3rd row has single zer o to be encircled, 1st row and 2nd
rows have zeroes to be encircled.. After, we obtained the resultant matrix
i.e. Table E.5

Step 4:
The assignment schedule is given in the following Table E.6.

The optimal profit is Rs 36.
Problem 6: A sales manager has to assign salesman to three territories. He
has four salesman of varying candidates. The manager assesses the
possible profit for each salesman in each territory as given below:
munotes.in

Page 86

86 Assignment Model Solution: The matrix consist of 4 rows (S1, S2, S3, S4) and 3 columns
(T1, T2, T3), since the number of rows and columns are not equal, we can
say that matrix is unbalanced and of maximization type (as profit is given)
type.
Step 1:
To apply Hungarian Method the matrix should be balanced and of
minimization type, so we have t o add dummy column with all entries as
zeroes (Table F.2) and further have to create a regret matrix by selecting
the maximum value from the matrix (Table F.3) i.e. 220 and subtracting
each value by 220. The matrix so obtained will be consider as Regret
Matrix. We can now apply Hungarian Method to the matrix


Step 2:
Prepare a Row Reduced matrix by selecting a minimum element from
each row of given matrix and subtracting it from each element of that row.
The minimum elements from each row are 40, 30, 56 , and 0. The
following matrix will be obtained (Table F.4).

Step 3:
Prepare a Column Reduced matrix by selecting a minimum element from
each column of Row Reduced matrix (Table F.4) and subtracting it from
each element of that column. The minimum element s from each column
are 24, 20, 0, and 164. The following matrix will be obtained (Table F.5). munotes.in

Page 87

87 Mathematical Foundation for Computer Science 2 T1T2T3DummyS13626016S264026S30000S42610056Table F.5 TerritoryColumn Reduced MatrixSalesman

Step 4:
Now we can do the assignments. Starting with the first row (Salesman S1)
in table F.6, In this case 1st row has single zero and we encircle it and
mark ing cross on all other zeroes lying in the 3rd column. 3rd row has
single zero to be encircled, 2nd row and 4th row have no zeroes to be
encircled.. After, we obtained the resultant matrix i.e. Table F.6

The number of assignments are 2 and size of matrix is 4, hence no
optimum solution is obtained.
Step 5:
Draw minimum number of lines to cover all the zeroes.

Step 6:
Select the minimum uncovered element from Table F.7 and subtract from
other uncovered elements and minimum uncovered element to the
elemen ts where the two lines are intersecting. In this case minimum
uncovered element is 4. The following matrix (Table F.8) will be
obtained: munotes.in

Page 88

88 Assignment Model

Step 7:
Now we can do the assignments. Starting with the first row (Salesman S1)
in table F.9, In this case 1st row h as single zero and we encircle it and
marking cross on all other zeroes lying in the 3rd column. 2nd row and 3rd
row has single zero to be encircled, and 4th row have no zeroes to be
encircled. After, we obtained the resultant matrix i.e. Table F.9

Numbe r of assignments are 3 and size of matrix is 4 hence optimal
solution is not obtained
Step 8:
Draw minimum number of lines to cover all the zeroes.

Select the minimum uncovered element from Table F.10 and subtract from
other uncovered elements and add mi nimum uncovered element to the
elements where the two lines are intersecting. In this case minimum
uncovered element is 6. The following matrix (Table F.11) will be
obtained:

munotes.in

Page 89

89 Mathematical Foundation for Computer Science 2 Step 9:
Now we can do assignments on zeroes of each row. Every row must
conta in only one encircled zero.

Number of assignments are 4 and size of matrix is 4 hence we reached an
optimal solution.
Step 10:
The assignment schedule is given in the table F.13

The optimal profit is Rs 694.
Problem 7: The following matrix gives infor mation about the cost of
performing jobs on different machines. Find the optimum assignment.

The matrix consist of 4 rows (1, 2, 3, 4) and 5 columns (A, B, C, D, E)
since the number of rows and columns are not equal, we can say that
matrix is not balance d and of minimization (as cost is given) type. To
apply Hungarian Method the matrix should be of balanced type, so we will
introduce dummy row (as one row is less than the number of columns)
under the name Dummy where all the entries will be zeroes. Refer Table
G.2 now the number of rows including dummy are 5 and number of
columns are also 5. Hence the matrix is balanced and of minimization type
(cost is given). We can now apply Hungarian Method. munotes.in

Page 90

90 Assignment Model

Step 1:
Choose the minimum element in each row and subtract it from every
element of that row. In this case, 12, 18, 22, 13 and 0 are minimum
element from 1st, 2nd, 3rd, 4th and 5th row respectively. In this way we get
row reduced matrix.

Step 2:
Choose the minimum element in each column and subtract it from eve ry
element of that column. In this case, 0, 0, 0 and 0 are minimum element
from 1st, 2nd, 3rd and 4th column respectively. In this way we get column
reduced matrix.

From table G.5 it is evident that total number of assignments (encircled
zeroes) are 3 an d size of matrix is 5. The 3rd and 4th row (Job 3 and Job 4)
does not have a single assignment (encircled zero), hence we have not
obtained an optimal solution.
The pattern of assignments for the combination of jobs and machines are
as follows: munotes.in

Page 91

91 Mathematical Foundation for Computer Science 2

Step 3:
Consider Table G.6 and draw minimum number of lines to cover all the
zeroes. We can draw vertical or horizontal lines to cover all the zeroes.

Identify the smallest value which is not covered by any line (minimum
uncovered value).From table G.6,it is evi dent that minimum uncovered
value is 2, this value will be subtracted from all the uncovered values and
will be added to the values at the point of intersection (where the two
lines are intersecting) and the remaining values (covered values) will
remain t he same. The resultant matrix is shown in the table G.7 ABCDE1052652230103010M3487650Dummy20002Table G.7 MachinesJobs
Step 4:
Now we can do the assignments. Starting with the first row (Job 1) in table
G.8, we examine each rows until we found a row with single zero (Job 1).
In this case 1st row has single zero and we encircle it and marking cross on
all other zeroes lying in the first column. Now 2nd row and 3rd row has
single zero to be encircled but 4th row does not have zero to get encircled. munotes.in

Page 92

92 Assignment Model

The number of assignments are 4 and size of matrix is 5, hence solut ion is
not optimal.
Step 8:
Draw minimum number of lines to cover all the zeroes.

Identify the smallest value which is not covered by any line (minimum
uncovered value).From table G.9, it is evident that minimum uncovered
value is 1, this value will be s ubtracted from all the uncovered values and
will be added to the values at the point of intersection (where the two lines
are intersecting) and the remaining values (covered values) will remain the
same. The resultant matrix is shown in the table G.10 ABCDE1042552220003000M3486640Dummy30103JobsTable G.10 Machines
Step 9:
Now we can do assignments on zeroes of each row. Every row must
contain only one encircled zero. munotes.in

Page 93

93 Mathematical Foundation for Computer Science 2 ABCDE1042552220003000M3486640Dummy30103Table G.11 MachinesAssignment MatrixJobs
Number of assignments are 5 and size of matrix is 5 hence we reached an
optimal solution.
Step 10:
The assignment schedule is given in the table G.12 TerritoryCostJobs 1A122C213B254E13DummyD0Total71Table G.12Assignment Schedule

The optimal cost is Rs 71 .
Problem 8: Solve the following assignment problem using the Hungarian
method. The cost matrix in the table F.1 represents the combination of
worker and the time taken to finish their respective jobs.

The matrix consist of 4 rows (W1, W2, W3, W4) and 4 columns (T1, T2,
T3, T4), since the number of rows and columns are equal, we can say that
matrix is balanced and of minimization (as cost is given) type.
Step 1:
Choose the minimum element in each row and subtract it from every
element of that row. In this case20, 10, 40 and 20 are minimum element
from 1st, 2nd, 3rd and 4th row respectively. In this way we get row reduced
matrix. munotes.in

Page 94

94 Assignment Model

Step 2:
Prepare a Column Reduced matrix by selecting a minimum element from
each column of Row Redu ced matrix (Table F.4) and subtracting it from
each element of that column. The minimum elements from each column
are 24, 20, 0, and 164. The following matrix will be obtained (Table F.3)

Step 3:
Now we can do the assignments. Starting with the first row (Job 1) in table
F.4, we examine each rows until we found a row with single zero (W1). In
this case 1st row has single zero and we encircle it and marking cross on
all other zeroes lying in the 3rd column. Now 2nd row has choice of two
zeroes, we are sele cting zero from 1st column (T1), 3rd row and 4th row has
single zero to be encircled. The assignment matrix is given in Table F.4
(A)

OR
1st row has single zero and we encircle it and marking cross on all other
zeroes lying in the 3rd column. Now 2nd row has choice of two zeroes, we
are selecting zero from 4th column (T4), 3rd row and 4th row has single
zero to be encircled. The assignment matrix is given in Table F.4 (B) munotes.in

Page 95

95 Mathematical Foundation for Computer Science 2

Step 4:
The assignment schedule for Table F.4 (A) is:

The optimal cost is Rs 110 .
The assignment schedule for Table F.4 (B) is:
OR

The optimal cost is Rs 110.
4.3 TRAVELLING SALESMAN PROBLEM Travelling Salesman Problem is a special case of assignment problem with
certain restrictions .Consider a salesman who is assigned a job of vis iting
n different cities. He knows the distance between all pairs of cities. He is
allowed to visit each of the cities only once. The travel should be
continuous and he should be come back to the city from where he started
using the shortest route. These r estrictions imply that no assignment
should be made along the diagonal and no city should be travelled more
than once. munotes.in

Page 96

96 Assignment Model

Solution: The matrix consist of 5 rows (1, 2, 3, 4, 5) and 5 columns (1, 2,
3, 4, 5), since the number of rows and columns are equal, we can say that
matrix is balanced and of minimization type (as cost is given).Since
salesman 1 cannot travel to city 1 and salesman 2 cannot travel to city 2,
salesman 3cannot travel to city 3, salesman 4 cannot travel to city 4 and
salesman 5 cannot trav el to city 5, so we assigning value ‘M’ which. No
assignments or no change in values can happen to value ‘M’. The matrix
so obtained given in Table H.2

Step 1:
Prepare a Row Reduced matrix by selecting a minimum element from
each row of given matrix an d subtracting it from each element of that row.
The following matrix will be obtained (Table H.3).

Step 2:
Prepare a Column Reduced matrix by selecting a minimum element from
each column of Row Reduced matrix (Table H.3) and subtracting it from
each elem ent of that column. munotes.in

Page 97

97 Mathematical Foundation for Computer Science 2

Step 3:
Now we can do the assignments. Starting with the first row we obtained
the resultant matrix i.e. Table H.5

The number of assignments are 3 and size of matrix is 4, hence optimal
solution is not obtained.
Step 4:
Draw minimu m number of lines to cover all the zeroes.

Step 5:
Select the minimum uncovered element from Table H.6 and subtract from
other uncovered elements and minimum uncovered element to the
elements where the two lines are intersecting. In this case minimum
uncovered element is 10. The following matrix (Table H.7) will be
obtained: munotes.in

Page 98

98 Assignment Model

The assignment is 1 →3, 2 → 4, 3→ 5, 4→ 2, 5→ 1. The route is not
continuous it has two sub routes 2→4→2 and 1→3→5→1. The total
distance travelled is 50+50= 100 and 60+70 +40 = 170 i.e. is 100+170 =
270 Kms.
We resolve the problem by considering the first sub route 2 →4→2 by
making 2→4 not then 4→2 not possible by assigning large value M to
these routes. The new matrix is obtained

The number of assignments are 3 and size of matrix is 4, hence optimal
solution is not obtained.
Step 6:
Draw minimum number of lines to cover all the zeroes.

Select the minimum uncovered element from Table H.9 and subtract from
other uncovered elements and minimum uncovered element to the
elements where the two lines are intersecting. In this case minimum
uncovered element is 20. The following ma trix (Table H.10) will be
obtained
munotes.in

Page 99

99 Mathematical Foundation for Computer Science 2 Step 5:

The optimum assignment is
1 →3, 2→5, 3→4, 4→2, 5→1 i.e. 1→3→4→2→5→1
The total distance is 60+90+50+40 = 300Kms
Step 6 :
Consider 4 →2 is not possible by putting a large value M at (4, 2)

Prepare row reduced matrix.

Prepare column reduced matrix.
munotes.in

Page 100

100 Assignment Model

The optimum assignment is
1 →5, 2→4, 3→1, 4→3, 5→2 i.e. 1→5→2→4→3→1
The total distance is 40 + 60 + 50 + 90 + 60 = 300Kms.
1→3→4→2→5→1 or 1→5→2→4→3→1 are feasible routes which gives
the same distance travelled (300Kms). The salesman can choose either of
the two routes.
4.5 SUMMARY Assignment problem is a special case of transportation problem where
resources are allocated to equal number of activities to minimize the cost
or maximize the profit. A special method called Hungarian Method is used
to solve assignment problem. Hungarian Met hod is applied on a balanced
matrix i.e. number of resources and number of activities should be same.
If matrix is unbalanced, by introducing dummy row/column, a matrix can
be made balanced. Another type of assignment problem is Maximization
Problem (Profi t/Revenue etc.) has to convert into minimization case by
creating regret matrix. In Prohibited case, no reduction or assignment can
be done in restricted cells.
4.5 REFERENCES • Kapoor, V.K. and Kapoor, S. 2001. Operations Research Techniques
for Management. Sultan Chand and Sons, New Delhi.
• Sharma , S.D. 1999. Operations Research. Kedar Nath Ram Nath &
Co., Mereut.
• Swarup, K., Gupta, P.K. and Mohan, M. 1989. Operations Research.
Sultan Chand and Sons, New Delhi.
• Taha, H.A. 2005. Operations Research: An Intro duction. Prentice Hall
of India Private Limited, New Delhi.
• Wagner, H.M. 1982. Principles of Operations Research, with
Applications to Management Decisions. Prentice Hall of India, New
Delhi.
munotes.in

Page 101

101 Mathematical Foundation for Computer Science 2 4.6 EXERCISE Problem 1: Solve the following assignment problem to obtain optimal
solution.

Problem 2: Solve the following assignment problem to obtain optimal
solution. Table B.1 Jobs (Costs in Rs) A B C D Employees 1 30 32 33 42 2 33 39 34 45 3 40 29 37 38 4 29 37 30 33
Problem 3: Solve the following assignment problem to obtain optimal
solution.

Problem 4: Solve the following assignment problem to obtain optimal
solution.

munotes.in

Page 102

102 Assignment Model Problem 5: Solve the following assignment problem to obtain optimal
solution.

4.7 SELF -LEARNING TOPIC Applications of Assignment Problem in Daily Life :
It involves assignment of people to projects, jobs to machines, workers to
jobs and teachers to classes etc, while minimizing the total assignment
costs. One of the important characteristics of assignment pr oblem is that
only one job (or worker) is assigned to one machine (or project). An
assignment problem is a special type of linear programming problem
where the objective is to minimize the costs or time of completing a
number of jobs by a number of persons .
Though assignment problems finds applicability in various diverse
business situations, like assigning machines to factory orders, in assigning
sales/marketing people to sales territories. In assigning contracts to bidders
to systematic bid evaluation. In assigning teachers to classes, accountants
to accounts of the clients.




*****

munotes.in

Page 103

103
UNIT IV
5
GAME THEORY
Unit structure
5.0 Objective
5.1 Introduction
5.2 Essential features of Game theory
5.3 Operating characteristics of Game theory
5.4 Classification of Game theory
5.5 Summary
5.6 References
5.7 Exercise
5.0 OBJECTIVE After going throu gh this chapter, students will able to:
● Understand the situation of conflict.
● Estimate the probabilities of earning profits by reducing the
probabilities of losses.
● Examine and solve the game theory problems using Maximin -
Minimax and dominance principle.
● Understand the key elements and underlying mathematical concepts
of game theory.
● Understand strengths and weaknesses of game theory.
5.1 INTRODUCTION John Von Newman and Oscar Morgenstern developed the concept of
Game Theory in 1928. A game is a conflicti ng situation where two or
more than two players are involved. Game theory is a branch of Applied
Mathematics which provides devices to examine the situations where
players make decisions that are independent. The approach of game theory
to analyze the oppo nent’s best counter strategy to the one’s own best
strategy and to formulate the appropriate defensive measures. Game
theory deals with competitive situations of decision making under
uncertainty. A solution to game describes the optimal decisions of the
players, who may have similar, mixed or contrasts interest, and the
outcomes that may result from these decisions. The games can be
classified as two person and n person game, zero sum and non - zero sum
game, constant sum game, co -operative and non -cooperat ive games, pure munotes.in

Page 104

104 Game Theory strategy and mixed strategy games etc. Any game in which the gains of the
winners are equal the losses of losers is called a zero sum game. A game
in which there is a difference between the gains and losses is called a non -
zero sum game.
5.2 ESSENTIAL FEATURES OF GAME THEORY 1) There are finite number of competitors or players say ‘n’ with
conflicting interest.
2) Every player has a finite number of alternative choices or strategies
available to them.
3) Before the game begins, each player knows the strategies available to
himself/herself and the ones available to his/her opponents.
4) To each play there corresponds particular outcome called pay off
which determines a set of gains to each player. Loss is considered as
negative gain.
5) Each player attempts to maximize gains or minimizes losses.
5.3 OPERATING CHARACTERISTICS OF GAME THEORY 1) Players: A set of competitors or decision makers or opponent are
termed as players. Any game involves two or more than two players
in a game. A game having two players con testing or playing any game
against each other is termed as” two person sum game” and if in a
game more than two contestants are playing that game is termed as n
– person sum game.
2) Strategies: Strategy in game theory refers to a situation where a
player ha s predetermined set of rules or finite number of alternatives
or course of action available to him. There are two types of strategies :
Pure Strategy: The same strategy or rules or course of action adopted
by player every time is termed as pure strategy. T he objective of
player for adopting pure strategy is to maximize gains and minimizes
the losses. Therefore the pure strategy is considered as best strategy.
Mixed Strategy: In a mixed strategy, a player adopts various
combination of strategies to maximize the gains and make keep
guessing the opponents about his next alternative or course of action
in a particular situation or event. For e.g. in a game of cricket a
bowler cannot throw a ball of same technique every time as batsman
will become alert make more runs. Thus the mixed strategies is a
selection among pure strategies with some fixed probabilities. The
objective of player is to maximize the gains and to minimize the
losses by adopting strategies and each strategy having a fixed
probability. munotes.in

Page 105

105 Mathematical Foundation for Computer Science 2 3) Payoff: Payoff is the outcome of a game. Payoff can be either gain,
draw or loss. The payoff of a game depends upon the strategies or
course of action adopted by player. The tabular representation of
payoff of all players for all strategies gives payoff matrix.
If X and Y are two players playing a game and ‘r’ indicates the
strategies available to X and ‘n’ indicates the strategies available to Y,
then the size of payoff matrix will be r x n.
r = number of rows
n = number of columns


Interpretation:
There are two players X and Y playing a game.
X has two alternatives or strategies and Y has three alternatives or
strategies.
Elements such as 4, 7, 6 and -3, 5, -4 represents the payoff. When
player X opts for strategy I and player Y also opts for strategy I, then
payoff to X is 4. In short, the gain for player X will be of 4 units and
loss of 4 units to player B. If X opts for strategy II and player Y opts
for strategy I, then payoff to X is -4. So in this case , the gain for
player Y will be of 4 units and loss of 4 units to player X ( loss of X
and gain of Y).In other words we can say that positive values
indicates gain of player X and loss to player Y and vice versa.
4) Row Minima: The minimum payoff value from each row is Row
Minima. From Table A.1:
Row Minima for pl ayer X:
Row 1: 4
Row 2: -4
5) Column Maxima: The maximum payoff value from each column
will be Column Minima. From Table A.1:
Column Maxima for player Y:
Column 1 Column 2 Column 3
4 7 6
munotes.in

Page 106

106 Game Theory 6) Maximin: Selecting the maximum value out of Row Minima. For
playe r X (Row Minima are 4 and -4) maximin is 4.
7) Minimax: Selecting the minimum value out of Column Maxima.
For player Y (Column Maxima are 4, 7, 6) minimax is 7.
8) Saddle Point: The saddle points occurs when minimax of rows and
maximin of columns are equal in a payoff matrix.
Minimax of Row = Maximin of Column
9) Optimal Strategy: A strategy or course of action that puts a player
in a preferred position irrespective of the strategies followed by
opponents or competitors is called optimum strategy.
10) Value of the game : The expected outcome per play when players
follow their optimal strategies is called value of the game. The game
is fair if the value of game is zero and if the value of game is not
zero then game is considered as unfair.
11) Two -Person Zero -Sum Game: In a g ame, two persons or
competitors are involved where the gain of one player is equal to the
loss of another player. The payoff matrix is rectangular in form, so
two-person -sum-game is also called as react angular game or matrix.
There are two types of two -person-sum-game, if most preferred
position obtained by adopting single strategy by players then game
is called as pure strategy game and if most preferred position
obtained by adopting mixed strategies by players then game is called
as mixed strategy game. If n-person are playing and the sum of the
game is zero then such game is called as n -person –zero sum game.
The features of two -person -sum-game are:
Only two players are involved.
Each player has a finite number of strategies to use.
Each strategy results in a payoff.
Each payoff results in a payoff matrix.
Total payoff at the end of game of two -person -sum-game is always
zero.
5.4 CLASSIFICATION OF GAME THEORY Pure Strategy Games (Saddle Points):
Minimax and Maximin Principle: When a single strategy follow ed by
player A and similarly a single strategy followed by another player B
every time when they play a game against each other, such a strategy is
pure strategy. munotes.in

Page 107

107 Mathematical Foundation for Computer Science 2 The objective of player A is to maximize his minimum gains and this
strategy is called as ma ximin strategy and his corresponding gains are
called as maximin or lower value of the game. On the other hand the
strategy of player will be minimize the maximum losses incurred to him
during game. This strategy adopted by player B is called as minimax
strategy and his corresponding loss are called as minimax or upper value
of the game.
When minimax value = maximin value, we get a saddle point or
equilibrium point and the value of the game is given by this saddle point.
If maximin value = minimax value =0, then game is called as fair game
and if maximin value = minimax value ≠ 0 then game is said to be strictly
determinable.
The steps involved in finding the saddle point is:
Select a minimum element from each row and write down under the
heading of Row Minima heading pr epare at the right side of matrix)
and ring the largest of them..
Select a maximum element from each column and write down under
the heading of Column Maxima heading prepare at the down side of
matrix) and ring the smallest of them.
If these two ringed ele ments are same, the cell corresponds to
intersection of row and column is a saddle point. The element in the
cell will be the value of the game.
If there are more than one saddle points then there will be more than
one solution.
If these two ringed element s are not same, there will be no saddle
point.
Problem 1 : Find the optimal strategies for player A and player B in the
following game. Also find the value of the game.


Solution:
From each row, select minimum payoff value (Row Minima).
From each column, select maximum payoff value (Column Maxima). munotes.in

Page 108

108 Game Theory

Ring the maximum payoff value out of minimum in Row Minima.
Maximin Value = 130
Ring the minimum payoff value out of maximum in Column Maxima.
Minimax Value = 130.
Thus, Maximin Value = Minimax Value = 130.
The matrix has a saddle point in a cell (A1, B2).
Value of the game = 130.
Thus the optimal strategy for A = A1 (1, 0, 0)
Thus the optimal strategy for B = B2 (0, 1, 0)
Problem 2: Find the optimal strategies for player A and player B in the
following game. Also find the value of the game.

Solution:
From each row, select minimum payoff value (Row Minima).
From each column, select maximum payoff value (Column Maxima).

Ring the maximum payoff value out of minimum in Row Minima.
Maximin Value = 18
Ring the m inimum payoff value out of maximum in Column Maxima.
munotes.in

Page 109

109 Mathematical Foundation for Computer Science 2 Minimax Value = 18.
Thus, Maximin Value = Minimax Value = 18.
The matrix has a saddle point in a cell (A3, B3).
Value of the game = 18.
Thus the optimal strategy for A = A3 (0, 0, 1, 0, 0)
Thus the opt imal strategy for B = B3 (0, 0, 0, 1, 0)
Problem 3: Find the optimal strategies for player A and player B in the
following game. Also find the value of the game.

Solution:
From each row, select minimum payoff value (Row Minima).
From each column, select maximum payoff value. (Column Maxima)

Ring the maximum payoff value out of minimum in Row Minima.
Maximin Value = 8
Ring the minimum payoff value out of maximum in Column Maxima.
Minimax Value = 8.
Thus, Maximin Value = Minimax Value = 8.
The matrix has a saddle point in a cell (A2, B2).
Value of the game = 8.
Thus the optimal strategy for A = A2 (0, 1, 0)
Thus the optimal strategy for B = B2 (0, 1, 0)
Problem 5: Find the optimal strategies for player A and player B in the
following game. Also find the v alue of the game. munotes.in

Page 110

110 Game Theory

Solution:
From each row, select minimum payoff value (Row Minima).
From each column, select maximum payoff value (Column Maxima).

Ring the maximum payoff value out of minimum in Row Minima.
Maximin Value = 7
Ring the minimum payoff va lue out of maximum in Column Maxima.
Minimax Value = 7.
Thus, Maximin Value = Minimax Value = 7.
The matrix has a saddle point in a cell (A2, B3).
Value of the game = 7.
Thus the optimal strategy for A = A2 (0, 1, 0, 0, 0)
Thus the optimal strategy for B = B3 (0, 0, 1, 0, 0)
Principle of Dominance :
If pure strategies does not exist, the next step is reduce the size of matrix
by eliminating a course of action (rows/columns) by the rule of
dominance.
Rule1 : If all the elements of a row say pth are less than or equal to
corresponding elements of another row say qth row, it indicates that pth
row is dominated by qth row. Delete the dominated row.
Rule2 : If all the elements of a column say pth are less than or equal to
corresponding elements of another column say qth column, it indicates that
pth column is dominated by qth column. Delete the dominated column.
Problem 5: Find the optimal strategies for player A and player B in the
following game. Also find the value of the game. munotes.in

Page 111

111 Mathematical Foundation for Computer Science 2

Solution:

In the game, column B4 is dominated by column B2, eliminating B4, the
reduced matrix is given below:

In the game, row A1 is dominated by row A3, eliminating row A1, the
reduced matrix is given below:

In the game, row A2 is dominated by row A3, eliminating row A2, the
reduced matrix is given below:

In the game, column B3 is dominated by column B1, eliminating B3, the
reduced matrix is given below:

In the game, column B1 is dominated by column B2, eliminating B1, the
reduced matrix is given below:
munotes.in

Page 112

112 Game Theory (A3, B2) is the sadd le point. Hence, the value of the game is 24 as it
represents the best pay -off for both the players.
Problem 6: Find the optimal strategies for player A and player B in the
following game. Also find the value of the game.

Solution:

In the game, row A1 is dominated by column A2, eliminating A1, the
reduced matrix is given below:

In the game, row A3 is dominated by column A4, eliminating A3, the
reduced matrix is given below:

In the game, column B1 is dominated by column B3, eliminating B1, the
reduc ed matrix is given below:

In the game, column B2 is dominated by column B3, eliminating B2, the
reduced matrix is given below:
munotes.in

Page 113

113 Mathematical Foundation for Computer Science 2 In the game, column B4 is dominated by column B5, eliminating B4, the
reduced matrix is given below:

In the game, row A4 is dominated by column A2, eliminating A4, the
reduced matrix is given below:

In the game, column B5 is dominated by column B3, eliminating B5, the
reduced matrix is given below:

(A2, B3) is the saddle point. Hence, the value of the game is 14 as it
represents the best pay -off for both the players.
Problem 7: Find the optimal strategies for player A and player B in the
following game. Also find the value of the game.

Solution:
In the game, column IV is dominated by column II, eliminating IV, the
reduced matrix is given below:

In the game, row A is dominated by row C, eliminating row A, the
reduced matrix is given below:
munotes.in

Page 114

114 Game Theory In the game, row B is dominated by row C, eliminating row B, the reduced
matrix is given below:

Column III is dominated by column I, eliminating column III, and the
reduced matrix is given below:

Column I is dominated by column II, eliminating column I, the reduced
matrix is given below:
(C, II) is the saddle point. Hence, the value of the game is 16 as it
represents the best pay -off for both the players.
5.5 SUMMARY The game theory is a branch of Applied Mathematics devised to make
decisions in complex circumstances. Game theory has been widely used in
Social Sciences, Biology, and Economics and in Engineering, Political
Science et c. Game theory is the mathematical study of strategy and
conflict, where a player success depend in making choices depends on the
choice of other. The game theory module explains the concept of
competitive situations, strategy, course of action, payoff etc . The module
also explains the maximin -minimax principle, saddle point and principle
of dominance etc.
5.6 REFERENCES Kapoor, V.K. and Kapoor, S. 2001. Operations Research Techniques for
Management. Sultan Chand and Sons, New Delhi.
Sharma , S.D. 1999. Ope rations Research. Kedar Nath Ram Nath & Co.,
Mereut.
Swarup, K., Gupta, P.K. and Mohan, M. 1989. Operations Research.
Sultan Chand and Sons, New Delhi.
Taha, H.A. 2005. Operations Research: An Introduction. Prentice Hall of
India Private Limited, New Delhi .
Wagner, H.M. 1982. Principles of Operations Research, with Applications
to Management Decisions. Prentice Hall of India, New Delhi.

munotes.in

Page 115

115 Mathematical Foundation for Computer Science 2 5.7 EXERCISE Problem 1: Solve the following 2 × 2 game

Problem 2: Solve the following 3 × 3game

Problem 3: Solve the following 4 × 4 game by dominance principle.

Problem 4: Solve the following game by dominance principle.



***** munotes.in

Page 116

116
6
DECISION THEORY
Unit structure
6.0 Objectives
6.1 Introduction
6.2 Elements of Decision Making Problem
6.3 Types of Decision Making Environments
6.4 Decision Making Under Risk
6.5 Decision making Under Uncertainty
6.6 Summary
6.7 References
6.8 Exercise
Self Learning Topics: Decision tree for decision -making problem.
6.0 OBJECTIVES After going through this chapter, students will able to:
● Understand the decision making process
● Describe a decision problem in terms of decision alternatives, state of
nature and payoffs
● Construct a payoff table and an opportunity loss table.
● Use payoff tables to analyze decision problems
● Understand the types of decision making environment
● Describe the decision environments of certainty and uncertainty
6.1 INTRODUCTIO N Decision theory is used to determine optimal strategies among the several
decision alternatives. While performing various management
functionalities like planning, organizing, directing, coordinating and
controlling, manager has to take several decision s. Manager has to take the
decision under uncertain, risky conditions. We may define Decision theory
as a process, which results in the selection from set of alternative courses
of action, that course of action, which is considered to meet the objectives
of the decision problem.
The decision taken by the manager decide the future of business, right
decisions will have beneficial effect while the wrong ones may prove to be
unsuccessful. Therefore, it is important to choose the appropriate decision.
Decision theory provides a rational approach to the managers in dealing munotes.in

Page 117

117 Mathematical Foundation for Computer Science 2 with the problems challenged with partial, imperfect or uncertain future
conditions.
Steps in Decision Theory:
Systematic approach of decision -making consists of following steps:
1. Clearly defi ne the problem
2. Define the objectives
3. List out all the possible alternatives
4. Identify all possible outcomes for each alternative
5. Identify the payoff for each alternative and outcome combination
6. Use a decision model to choose best alternative
6.2 ELEMENTS O F DECISION MAKING PROBLEM 1. Decision Maker: Decision maker is an individual or group of
individuals who make decisions.
2. Courses of action or strategies: The alternative course of action or
strategies, are the acts that are available to decision maker.
Eg. To order Product A, number of units to be order for that product
depending upon demand. .
3. State of Nature or outcomes: The events identify the occurrences
which are outside of the decision maker’s control and which
determine the level of success for a give n act. These events are called
State of Nature or outcomes.
Eg. State of nature is the level of market demand for a particular item
during stipulated time period.
4. Payoff: Each combination of a course of action and a state of nature
is associated with a pay off. They are also known as conditional profit
values.
5. Payoff Table: Payoff Table consists of the states of nature (outcome
or events) which are mutually exclusive and collectively exhaustive
and a set of given courses of action (strategies). Payoff is c alculated
for each combination of state of nature and course of action.


munotes.in

Page 118

118 Decision Theory Following table shows the general form of Payoff Table:
Table 1: General form of Payoff Table States of Nature (Events) Conditional Pay-off Courses of Action (Strategies) A1 A2 --------- An S1 P11 P12 -------- P1n S2 P21 P22 ---------- P2n . . . . . . . . Sm Pm1 Pm2 --------- pmn
6. Regret or Opportunity Loss Table: The opportunity loss is defined
as the difference between the highest possible profit for the state of
nature an d the actual profit obtained for the particular action taken.
Consider a fixed state of nature Si. The pay offs corresponding to the n
strategies are given by pi1, pi2, …, pin. Suppose Mi is the maximum of
these quantities. Then A 1 is used by the decision maker then there is a loss
of opportunity of M 1 – pi1 and so on.
Following table showing opportunity loss ca be calculated as:
Table 2: General form of Regret Table States of Nature (Events) Conditional Opportunity Loss Courses of Action (Strategies) A1 A2 --------- An S1 M1 - P11 M1 - P12 -------- M1 - P1n S2 M2 - P21 M2 - P22 ---------- M2 - P2n . . . . . . . . Sm Mm - Pm1 Mm -Pm2 --------- Mm - pmn
6.3 TYPES OF DECISION MAKING ENVIRONMENTS The main aim of decision theory is to help the decision maker in selecting
best course of action from the available courses of action. Decisions are
made under four types of environments: certainty, risk, uncertainty and
conflict.
1. Decision making under certainty: In this environment, there is
complete certain ty about future. It is easy to analyze the situation the
situation and make good decision. Since the decision maker has the
knowledge about the future outcome, he simply chooses the
alternative having optimum payoff.
For example, suppose a person has Rs. 100000 to invest for one year
period. One alternative is to open a savings account in bank with rate of munotes.in

Page 119

119 Mathematical Foundation for Computer Science 2 interest of 3 percent and another one is to invest in fixed deposit with 5.5
percent rate of interest. If both alternatives are secure and guaranteed, t hen
there is a certainty that fixed deposit is better alternative.
The various techniques used for solving problems under certainty are:
i. System of equations
ii. Linear programming
iii. Integer programming
iv. Dynamic programming
v. Queuing models
vi. Inventory models
2. Decision making under risk: In this environment, the decision
maker is aware of all the possible states of nature but does not know
their occurrences with certainty. Decision maker knows or can
estimate the probabilities of their occurrences. This is based on his
experience or on the theoretical probability distributions of the states.
3. Decision making under uncertainty: In this environment, more than
one states of nature exist but the decision maker lacks sufficient
knowledge to allow him assign probabilities to t he various states of
nature.
4. Decision making under conflict: In this environment, two or more
opponents with conflicting objectives try to make decisions with each
trying to gain at the cost of the others.
6.4 DECISION MAKING UNDER RISK Here, decision m aker is aware of all the possible states of nature but does
not know their occurrences with certainty. Thus, the decision maker
knows or just estimate the probabilities of their occurrences. This is based
on his/her past experience or on the theoretical pr obability distributions of
the states. Under conditions of risk, a number of decision criteria are
available.
A. Expected Monetary Value (EMV):
This is most generally used decision criterion under the condition of risk.
The main purpose of this criterion i s to optimize the expected payoff i.e.
either maximization of expected profit or minimization of expected loss.
Here in a payoff table, conditional payoffs and their associated
probabilities are given for all state of nature.
Following are the steps for c alculating Expected Monetary Value (EMV):
1. Construct the payoff table using all state of nature and all possible
courses of action. munotes.in

Page 120

120 Decision Theory 2. List the conditional payoff values and corresponding probabilities of
the occurrences of each state of nature.
3. Calculate the Expected Monetary Value as,
EMV (S i) =

4. Select the course of action corresponds to optimal EMV.
Example 1: Consider the following payoff table along with the
probabilities of each state: States A1 A2 A3 Strategies Probabilities of States 0.4 0.5 0.1 S1 15 13 -12 S2 20 10 5 S3 35 -15 7
Solution: Calculate Expected Monetary Value (EMV) for each strategy as
EMV (S i) =

For strategy S1,
EMV (S 1) = (0.4) (15) + (0.5) (13) + (0.1) ( -12)
= 6.0 + 4.5 -1.2= 9.3
EMV (S 2) = (0.4) (20) + (0.5) (10) + (0.1) (5)
= 8.0 + 5.0 +1.5= 14.5
EMV (S 2) = (0.4) (35) + (0.5) ( -15) + (0.1) (7)
= 14.0 – 7.5 +0.7 7.2
The maximum EMV is 14.5 corresponding to S 2.
Hence S 2 is optimal strategy.
B. Expected Value with Perfect Info rmation (EVPI):
Before taking any decision, if decision maker has a perfect information
about the states of nature and associated probabilities then he/ she can
calculate the Expected Value with Perfect Information. To calculate
Expected Value with Perfect Information, select the best alternative for
each state of nature and multiply its payoff with the given probability.
munotes.in

Page 121

121 Mathematical Foundation for Computer Science 2 Example 2: States A1 A2 A3 Strategies Probabilities of States 0.4 0.5 0.1 S1 15 13 -12 S2 20 10 5 S3 35 -15 7
Solution: Best strategy for state A 1 is S 3 with payoff 35 and probability
0.4.
Best strategy for state A 2 is S 1 with payoff 13 and probability 0.5
Best strategy for state A 3 is S 3 with payoff 7 and probability 0.1
Expected Value with Perfect Information = (35) (0.4) + (13) (0.5) + (7)
(0.1) = 21.2
The Expected Value with Perfect Information, EVPI, is the difference
between expected value with perfect information and the expected value
without perfect information (maximum EMV).
EVPI = Expected Value with Perfect Information – Max (EMV)
For above example (From example 1 and example2),
EVPI = 21.2 - 14.5 = 6.7
6.5 DECISION MAKING UNDER UNCERTAINTY In this environment, the probabilities associated with occurrences of
different states of nature are not known. Decision maker has no way of
calculating the expected payoff for his courses of action or strategies.
For example, when a new product is introduced in market or new plant is
set up; in this situation, no previous data is available.
The course of action is depend upon the personality of decision maker and
policies of organization. Various criteria are available under Decision
making Under Uncertainty as follows:
A. Maximax Criterion or Criteria of Optimism:
In this method first find the maximum payoff assoc iated with each course
of action or alternative strategy and then selects the alternative with
maximum number. Since it deals with maximum possible profit or gain, it
is also called as Optimistic decision criterion.

munotes.in

Page 122

122 Decision Theory Example 3: Select the best strategy to maximize the payoff for following. States of Nature Courses of Action A1 A2 A3 A4 S1 25 40 60 80 S2 10 70 150 130 S3 20 40 60 100 S4 15 20 30 40
Solution: First we identify the maximum payoff associated with each
course of action.
Then select the maximum of the maximum values in order to select the
best (optimal) course of action. States of Nature Courses of Action Maximum of each Row A1 A2 A3 A4 S1 25 40 60 80 80 S2 10 70 150 130 150 S3 20 40 60 100 100 S4 15 20 30 40 40
Hence the decisi on maker selects the Strategy 2 i. e. S 2 to maximize the
payoff.
Example 4: Mr. Sharma has 4 alternatives each of which can followed
by any of the four events. The payoff for each combination is given in the
table Alternatives Conditional Events A1 A2 A3 A4 P 16 0 -20 12 Q -8 24 25 -4 R 28 12 0 16 S 20 -18 25 8
Determine which alternative Mr. Sharma should select to get maximum
payoff
Solution: Identify the maximum payoff associated with each alternative.
Then select the maximum of the maximum values in order to select the
best (optimal) course of action. Alternatives Conditional Events Maximum of each Row A1 A2 A3 A4 P 16 0 -20 12 16 munotes.in

Page 123

123 Mathematical Foundation for Computer Science 2 Q -8 24 25 -4 25 R 28 12 0 16 28 S 20 -18 25 8 25
Hence Mr. Sharma selects the alternative R to maxim ize the payoff.
B. Maximin Criterion or Criteria of Pessimism:
In this method, decision maker first find the minimum payoff associated
with each course of action or alternative strategy and then selects the
alternative with maximum number. Since in this cri terion decision maker
find the alternative strategy that has minimum possible loss, it is also
called as Pessimistic decision criterion.
Example 5: Select the optimal strategy to maximin the payoff for
following. States of Nature Courses of Action A1 A2 A3 A4 S1 25 40 60 80 S2 10 70 150 130 S3 20 40 60 100 S4 15 20 30 40
Solution: First determine the minimum payoff associated with each
course of action.
Then select the minimum of the maximum values in order to select the
best (optimal) course of action. States of Nature Courses of Action Minimum of each Row A1 A2 A3 A4 S1 25 40 60 80 25 S2 10 70 150 130 10 S3 20 40 60 100 20 S4 15 20 30 40 15
Hence decision maker selects the alternative S 1 under maximin criterion.
C. Minimax Regret Criterio n (Sevage Criteria):
Leonard Sevage developed this criterion. The basic steps involved in this
criterion are,
I. Consider the largest payoff for each state of nature
II. Find out the regret for each strategy as: munotes.in

Page 124

124 Decision Theory Regret = Largest payoff - Payoff for the strategy
III. Identify the maximum regret fir each strategy.
IV. Find out the minimum regret from these maximum regrets
V. The strategy corresponds to minimax regret is the optimal strategy
Example 6: Select the best strategy using Minimax Regret Criterion. States of Nature Courses of Action A1 A2 A3 A4 S1 25 40 60 80 S2 10 70 150 130 S3 20 40 60 100 S4 15 20 30 40
Solution: First find out the regrets for each state of nature as:
Regret = Largest payoff - Payoff for the strategy
For A 1, Largest payoff is 25.
Regret for S 1 = 25 – 25 = 0; Regret for S 2 =25 - 10 = 15
Regret for S 3= 25 – 20 = 5; Regret for S 4 = 25 – 15 = 10
Similarly, For A 2, Largest payoff is 70
Regret for S 1 = 70 – 40 = 30; Regret for S 2 = 70 – 70 =0
Regret for S 3=70 – 40 = 30; Regret for S 4 = 70 – 20 = 50
For A 3, Largest payoff is 150.
Regret for S 1 = 150 – 60 = 90; Regret for S 2 = 150 – 150 = 0
Regret for S 3 = 150 – 60 = 90; Regret for S 4 = 150 – 30 =12 0
And for A 4, Largest payoff is 130
Regret for S 1 = 130 – 80 = 50; Regret for S 2 = 130 – 130 = 0
Regret for S 3=130 – 100 =30; Regret for S 4 = 130 – 40 = 90
We get the regret table as follows: States of Nature A1 A2 A3 A4 Maximum Regret S1 0 30 90 50 90 S2 15 0 0 0 15 S3 5 30 90 30 90 S4 10 50 120 90 120 munotes.in

Page 125

125 Mathematical Foundation for Computer Science 2
Minimum regret among all the maximum regret is 15 corresponding to
strategy S 2. Hence strategy S 2 is optimal strategy.
D. Hurwicz Criterion (Criterion of Realism):
In this method, decision maker take into consideration both t he maximum
and minimum for each alternative and assign them weight according to
degree of of optimism or pessimism. The alternative which maximizes the
sum of these weighted payoffs is then selected. It uses a coefficient of
optimism
(alpha), 0
1, resentencing the decision maker’s degree
of optimism. Value of
is estimated on the basis of past experience.
=
0 implies pessimism and
= 1 implies optimism.
It consists of following steps:
1. Estimate or identify an appropriate value of
.
2. Determine the maximum payoff and minimum payoff of each
alternative.
3. Obtain Expected profit, P =
maximum + (1 -
) minimum.
4. Select the alternative which has maximum value of P .
5. Strategy corresponding to this maximum value of P is an optimal
Strategy.
Example 7: Consider the previous example. States of Nature Courses of Action A1 A2 A3 A4 S1 25 40 60 80 S2 10 70 150 130 S3 20 40 60 100 S4 15 20 30 40
Solution: Assume th e coefficient of optimism,
= 0.6
(1 -
) = 1 – 0.6
= 0.4 States of Nature Courses of Action Maximum of Row Minimum of Row P =
maximum + (1-
) minimum A1 A2 A3 A4 S1 25 40 60 80 80 25 58 S2 10 70 150 130 150 10 94 S3 20 40 60 100 100 20 68 munotes.in

Page 126

126 Decision Theory S4 15 20 30 40 40 15 30
The strategy corresponding to the maximum expected profit of 94
corresponds to S 2. So S 2 is optimal strategy.
E. Laplace Criterion (Criterion of Rationality (Bayes’ Criterion):
Since the probabilities associated with the occurrences of the states of
nature are not known, assign equal probabilities to all the events of each
alternative and select identify the alternative associated with the maximum
expected pa yoff.
It consists of following steps:
1. Find expected value for each strategy as,
Si =
[P1 + P 2 + …. + P n],
Where P i denotes the payoffs and n denotes number of events.
2. Find out maximum value among these.
3. Strategy corresponding to this maximum value is an optimal Strategy.
Example 8: Consider the same example. States of Nature Courses of Action A1 A2 A3 A4 S1 25 40 60 80 S2 10 70 150 130 S3 20 40 60 100 S4 15 20 30 40
Solution: For each strategy calculate expected value as follows: States of Nature Courses of Action Average Expected Profit A1 A2 A3 A4 S1 25 40 60 80
=
= 51.25 S2 10 70 150 130
=
= 90 S3 20 40 60 100
=
= 55 S4 15 20 30 40
=
= 26.25
The maximum average expected profit is 90 corresponding to strategy S 2.
Hence, S 2 is optimal strategy.
6.6 SUMMARY munotes.in

Page 127

127 Mathematical Foundation for Computer Science 2 Decision theory is used to determine optimal strategies among the several
decision alternatives. The decision mak er analyzes the possible outcomes
resulting from his available alternatives in two dimensions: value (by
means of utility theory) and probability of occurrence. He/she always
selects the alternative that he expects to have the highest value. Decision
Theor y suggests the decision maker to trust more strongly than ever on his
own preferences and judgments. Decision theory provides a rational
approach to the managers in dealing with the problems challenged with
partial, imperfect or uncertain future conditions .
6.7 REFERENCES Books:
1. Operations Research Techniques for Management – V. K. Kapoor
2. Operations Research – Prem Kumar Gupta and D. S. Hira
3. Quantitative Techniques in Management – Vohra
Website:
http://www3.govst.edu/kriordan/files/mvcc/math212/ppt/pdf/ch18ppln.pdf
https://gurunanakcollege.edu.in/files/commerce -
management/S TATISTICS -UNIT -5.pdf
6.8 EXERCISE Exercise 1: Calculate Expected Monetary Value and Expected Value with
Perfect Information for following.
a) States N1 N2 N3 N4 N5 Strategies Probabilities of States 0.10 0.15 0.20 0.25 0.30 S1 150 120 110 60 30 S2 150 170 140 110 80 S3 150 170 190 160 130 S4 150 170 190 210 180 S5 150 170 190 210 230 States A1 A2 A3 A4 Strategies Probabilities of States 0.10 0.20 0.40 0.30 S1 60 45 40 35 S2 60 50 35 40 S3 60 50 45 50 S4 60 50 45 55 munotes.in

Page 128

128 Decision Theory

b)
Exercise 2: Consider the following pay off matrix. Determine best
alternative using maximax criterion, maximin criterion and Minimax
Regret Criterion .
a) Alternatives Conditional Events A1 A2 A3 A4 X1 14 24 40 54 X2 20 18 20 50 X3 56 40 28 56 X4 32 48 42 34
b) Alternatives Conditional Events A1 A2 A3 A4 P 10 20 36 50 Q 16 14 -16 -23 R 20 -18 24 25 S 30 -22 38 30
c) Alternatives Conditional Events A1 A2 A3 A4 X1 -20 -40 -60 -80 X2 3 -17 -35 -65 X3 2 5 -15 -36 X4 3 5 -15 10
d) Alternatives Conditional Events A1 A2 A3 X1 -75 125 195 X2 -175 150 185 X3 -225 135 225
Exercise 3: Consider the following payoff table. Find which strategy is
optimal using
1. Maximin Criterion munotes.in

Page 129

129 Mathematical Foundation for Computer Science 2 2. Maximax Criterion
3. Minimax Regret Criterion
4. Laplace Crite rion
a) States of Nature Payoffs in Rs. Courses of Action A1 A2 A3 A4 S1 40 20 20 18 S2 50 -5 15 17 S3 60 30 4 10
b) States of Nature Payoffs in Rs.
Courses of Action A1 A2 A3 S1 50000 10000 13000 S2 30000 25000 0 S3 10000 10000 10000
Self-Learning Topics: Decision tree for decision -making problem
Some times we have take decisions under the situation where there are
multiple stages. They are considered by a sequence of decisions with each
decision inducing the next. Such problems called s equential decision
problems. These problems are analyzed and solved with the help of
Decision Tree.
Decision Tree is the device for presenting a diagrammatic presentation of
sequential and multi -dimensional aspects of a particular decision problem
for sys tematic analysis and evaluation It requires the decision maker to
examine all possible outcomes, whether desirable or undesirable. It
displays the logical relationship between the parts of a complex decision.
But it becomes highly complicated when interdep endent alternatives and
dependent variables are present in the problem.




*****
munotes.in

Page 130

130
UNIT V
7
SIMULATION
Unit Structure
7.1 Objective
7.2 Introduction to Simulation
7.3 Basic Terms
7.4 Model of a system
7.4 A) Physical Model
7.4 B) Mathematical Model
7.5 Steps in Simulation
7.6 Advantages of simulation
7.7 Disadvantages of simulation
7.8 Application of simulation
7.9 Monte Carlo Method
7.9.1. Steps of Monte Carlo Method
7.9.2. Example of Monte Carlo Method
7.10 Queuing
7.10.1[M/M/1]:{//FCFS} Queue System(Single Channel Queuing
System) -
7.10.2. Example of single server queue
7.11 List of Re ference
7.1 OBJECTIVE This chapter would make you understand the following concepts:
 What is simulation and discuss various model of simulation.
 With the help of simulation step how to solve problem .
 Discuss Advantages and disadvantages and application of simulation.
 Definition and step of Monte Carlo Method
7.2 INTRODUCTION TO SIMULATION In mathematical science we are discuss various types of problem with
solution. In the chapter we are discuss a new term “simulation”.
Simulation is more popular and powe rful and it deal with a real system
problem. In fact simulation can be extremely general tomb since the idea
applies across many field, industries and application deals with model of
system. A system is a facility or process either actual or planned. Real
World system are too complex to evaluate analytically. In simulation we munotes.in

Page 131

131 Mathematical Foundation for Computer Science 2 use a computer to evaluate model numerically and data are gathered in
order to estimate the desired true characteristics of the model.
Example of Simulation: Human Patient Simulator (H PS) use by trainee
to practice of surgery before doing actual. On HPS perform demonstration
of new drugs and new equipment by pharmaceutical and medical
equipment companies. It is beneficial in medical college to teach basic
skill in medical science. All t rainee fill practical standard in a controlled,
safe and even enjoyable environment.

7.3 BASIC TERMS System:
Collection of entities that are joined together for accomplishment of some
purpose.
Example -Bank system and objects are customer, passbook, cash ier,
computer...
 Entity -It is an object of an interest in a system.
 Attribute -It is property of an entity.
 Activity -A process that causes changes in the system.
There are two types of acitivity -1) Deterministic Activity and 2)
Stochastic Activity
Determini stic Activity -The outcome of activity can be described
completely in term of its input. Randomness does not affect the behavior
of the system.
Stochastic Activity -The effect of the activity vary randomly over various
possible outcome.
 State -collection of v ariable necessary to describe the system at any
time relative to the objective of the study.
Example -Bank System:
State - Number of customer waiting in the queue for opening account, first
customer done process and next customer arrived time start. munotes.in

Page 132

132 Simulation  Event -Instantaneous occurrence that may change the state of the
system.
There are mainly five types:
1) Endogenous system 2) Exogenous system 3) Open system 4) Closed
system 5) Discrete system 6) Continuous system
1) Endogenous system -In this system activity and events occurring
within a system.
2) Exogenous system - In this system activity and events outside the
system boundary i.e those variables in the environment, which affect
the system.
3) Open system -It is a system, which has an exogenous activity.
4) Close d system - It is a system, which does not have any exogenous
activity.
5) Discrete system -State of variable change only at a discrete set of
point.
6) Continuous system -State of variable change continuously over time.
7.4 MODEL OF A SYSTEM  A model is an ab straction of real system that represent information
about a system. Model are help to studying of a system.
 Model are classified as follows:

7.4 A) Physical Model:
 This model used for mechanical & electrical and hydraulic system.
Physical model represen t, representation of an object of interest which
shows how the object looks and how well it performs in the real
world.
 A physical model is a scaled -up model of the object under study
which may be small or large and it’s an exact replica of the original
design but smaller and its physical characteristics resemble the
physical characteristics of the original object or system. munotes.in

Page 133

133 Mathematical Foundation for Computer Science 2  The system attribute are reflected in the physical laws that derive the
model.
 E.g. Scale model, Prototype plants.
7.4. B) Mathematic al Model:
 In this model use Symbolic notation and mathematical equation to
represent a system.
 Mathematical models are collections of variables, equations, and
starting values that form a cohesive representation of a process or
behavior.
 Mathematics has th e potential to prove general results, these results
depend critically on the form of equations used.
 Small changes in the structure of equations may require enormous
changes in the mathematical methods.
 Using computers to handle the model equations may ne ver lead to
elegant results, but it is much more robust against alterations.
7.5 STEPS IN SIMULATION Steps of simulation help to study simulation study for find solution of
complex problem. When we are solve the problem with the help of steps
its more cle ar to find solution.
Steps are:
1. Problem formulation:
The initial step involves defining the goals of the study and determine
what needs to be solved. The problem is further defined through objective
observations of the process to be studied. Care should be taken to
determine if simulation is the appropriate tool for the problem under
investigation.
2. Setting of objectives and overall project plan:
Project plan include how many number of people involved, the cost of the
study, and time frame to complete the work of each stage with expected
results at the end of each of each stage. This step define” How we should
approach the problem.” The tasks for completing the project are broken
down into work packages with a responsible party assigned to each
package.
3. Model conceptualization:
How the actual system behaves and determining the basic requirements of
the model are necessary in developing the right model. Creating a flow
chart of how the system operates facilitates the understanding of what
variables ar e involved and how these variables interact. munotes.in

Page 134

134 Simulation

4. Data collection:
In this step collect the data necessary to run the simulation. This data is
collected according to system layout and operating procedures.
5. Model translation:
Translate a model to program ming language or simulation software to
create simulation.
6. Verification:
In this step the semantics and syntax of the model.
7. Validation :
Validation ensures that no significant difference exists between the model
and the real system and that the model reflects reality. Repeat this process
until model accuracy is reached to the acceptable level. Validation can be
achieved through statistical analysis.
8. Experimental design :
Experimentation involves developing the alternative model(s), executing
the sim ulation runs, and statistically comparing the alternative(s) system
performance with that of the real system. For each scenario that is to be
simulated, decisions need to be made concerning the length of the
simulation run, the number of runs (also called replications), and the
manner of initialization, as required.
9. Production runs and analysis :
Production runs, and their subsequent analysis, are used to estimate
measures of performance for the scenarios that are being simulated and
comparing alternativ e system configuration.
10. Repetition :
On the basis of analysis of runs completed in previous steps, the analyst
determine if additional runs are required or not. If additional runs are
required then what design experiments it should follows.
11. Document and report :
There are two types of documentation: program and progress.
Program document is necessary to understand how program operate.
Documentation consists of the written report and/or presentation.
Documentation is necessary for numerous reasons.
12. Implementation : munotes.in

Page 135

135 Mathematical Foundation for Computer Science 2 The success of implementation phase completely depends upon how well
the previous all steps are performed. If the client has been involved
throughout the study period, and the simulation analyst has followed all of
the steps rigorously, t hen the likelihood of a successful implementation is
increased.

7.6 ADVANTAGES OF SIMULATION 1. Simulation model designed for training purpose allow to learning new
system without the cost.
2. Hypothesis of new phenomenon check for feasibility.
3. Without using resources and capital check new hardware design,
physical layout, and transportation system.
4. With help of simulation concept observe the internal states of the
system.
5. Simulation can help in better understanding system operation.
6. ‘‘What-if” question can be answered which is useful in the design of
new system and modification or deployment of a model.
7. Time factor can be compressed or expanded allowing for a speedup or
slowdown of the system under investigation.
8. Simulation help to learn about real system, without having the system
at all. munotes.in

Page 136

136 Simulation 9. In many system actual environment is not possible that time
simulation help to create environment to perform task first virtually.
E.g. Nuclear explosion simulation system.
10. Decision maki ng problem are too complex to be solved by
mathematical programming.
11. Simulation relative free from mathematics can easily be understood
by the operating personal and non -technical situation.
12. Simulation model are comparatively flexible and modified
environment according to real situation.
7.7 DISADVANTAGES OF SIMULATION 1. Non-technical personal not handle simulation system.
2. Simulation result may be difficult to interpret.
3. Simulation modeling and analysis can be time consuming and
expensiv e.
4. Time may be needed to make sense of the results.
5. People’s reaction to the model or simulation might not be realistic
6. Mistake may be made in the programming or rules of the simulation
or model.
7.8 APPLICATION OF SIMULATION 1. Manufacturin g and material handling system
2. Computer system
3. Human system
4. Communication system
5. Business application
6. Production and inventory system.
7. Military application
8. Logistic transportation and distribution application
9. Health system
10. Construction engineering

munotes.in

Page 137

137 Mathematical Foundation for Computer Science 2 7.9 MONTE CARLO METHOD  Monte Carlo simulation is a powerful method for studying the
behavior of a system, as expressed in a mathematical model on a
computer.
 Monte Carlo simulations usually based on computer generation of
pseudo random numbers
 Monte Carlo Method random sampling of values for uncertain
variables that are “plugged into” the simulation model and used to
calculate outcomes of interest.
 Monte Carlo simulation is especially helpful when there are several
differen t sources of uncertainty that interact to produce an outcome.
 The three primary techniques for effective Multiple Probability
Simulation are – predictive approach, probability distribution, and
repeated simulations.
 For example, if we’re dealing with unce rtain market demand,
competitors’ pricing, and variable production and raw materials costs
at the same time, it can be very difficult to estimate the impacts of
these factors — in combination — on Net Profit.
7.9.1. Steps of Monte Carlo Method :
1. IDENTIF Y THE TRANSFER EQUATION
2. DEFINE THE INPUT PARAMETERS
3. SET UP SIMULATION
4. ANALYZE PROCESS OUTPUT
7.9.2 Example of Monte Carlo Method:
Jon’s is a dentist who schedule all her patie nts for 30 minutes
appoinments. S ome of the patients take more or les s than 30 minutes
depending on the type of dental work to be done .The following summary
shows the various categories of work their probabilities and the time
actually needed to complete the work : Category Time Required No. of Patients Filling 45 min 40 Crown 60 min 15 Cleaning 15 min 15 Extracting 45 min 10 Checkup 15 min 20
Simulation the dentist clinic for four hours and find out average waiting
time the patients as well as the idleness of the doctors. Assume that all the
patients show up at the c linic at exactly their schedule arrival. munotes.in

Page 138

138 Simulation Use the following random number for handling the above problem
40, 82,11,34,25,66,17,79.
Solution :
To solve the problem using Monte Carlo break down problem into five
steps :
1. Establishing probability distribution
2. Cumulative probability distribution
3. Setting random number interval
4. Generating random number
5. To find the answer of question asked using the above four steps.
To solve above problem follows the steps
Step 1 -Eshtablising probability : Category Time Required No. of Patients Probability Filling 45 min 40 0.40 Crown 60 min 15 0.15 Cleaning 15 min 15 0.15 Extracting 45 min 10 0.10 Checkup 15 min 20 0.20
1 patient=30 min i.e. in four hours check 8 patients.
Step 2 - Cumulative Probability dist ribution: Category Probability Cumulative Prob. Filling 0.40 0.40 Crown 0.15 0.55 Cleaning 0.15 0.70 Extracting 0.10 0.80 Checkup 0.20 1.00
According to cumulative probability we are set interval.
Step 3 -Setting Random Number interval: Category Probability Cumulative Prob. Random No. Interval Filling 0.40 0.40 00-39 Crown 0.15 0.55 40-54 Cleaning 0.15 0.70 55-69 Extracting 0.10 0.80 70-79 Checkup 0.20 1.00 80-99 munotes.in

Page 139

139 Mathematical Foundation for Computer Science 2 Step 4 -Generating Random number and prepared table: Patient Scheduled Arrival Random Number Category Service time needed 1 8:00 40 Crown 60 min 2 8:30 82 Checkup 15 min 3 9:00 11 Filling 45 min 4 9:30 34 Filling 45 min 5 10:00 25 Filling 45 min 6 10:30 66 Cleaning 15 min 7 11:00 17 Filling 45 min
Step 5 -Find Average waiting tim e and idleness of doctor : Patient Scheduled
Arrival Service Duration Service End Random Number Waiting(in minute) Idle time 1 8:00 60 min 40 0 0 2 8:30 15 min 82 30 0 3 9:00 45 min 11 15 0 4 9:30 45 min 34 30 0 5 10:00 45 min 25 45 0 6 10:30 15 min 66 60 0 7 11:00 45 min 17 45 0 8 11:30 45 min 79 60 0 Total= 285
Average waiting time =285/8 =35.625 min
Idleness of doctor= 0 minutes.
7.10 QUEUING A queuing system consists of one or more servers that provide service of
some sort to arri ving customers. Customers who arrive to find all servers
busy generally join one or more queues (lines) in front of the servers,
hence the name queuing systems such as bank -teller service, computer
systems, manufacturing systems, maintenance systems, commu nications
systems and so on Common to all of these cases are the arrivals of objects
requiring service and the attendant delays when the service mechanism is
busy.
Basic Terminology:
Queuing Model
It is a suitable model used to represent a service -oriente d problem, where
customers arrive randomly to receive some service, the service time being
also a random variable.
 Arrival
The statistical pattern of the arrival can be indicated through the
probability distribution of the number of the arrivals in an inte rval. munotes.in

Page 140

140 Simulation  Service Time
The time taken by a server to complete service is known as service time.
 Queue Discipline
It is the order in which the members of the queue are offered service. i.e, It
is the rule accordingly to which customers are selected for service when
queue has been formed. The most common disciplines are :
1. First come First Services (FCFS)
2. First in First Out (FIFO)
3. Last in First Out (LIFO)
4. Selection for service in Random Order (SIRO)
Notation for Queues:
Since all queues are characte rised by arrival, service and queue and its
discipline, the queue system is usually described in shorten form by using
these characteristics. The general notation is:
[A/B/s]:{d/e/f}
Where,
A = Probability distribution of the arrivals B = Probability distr ibution of
the departures s = Number of servers (channels) d = The capacity of the
queue(s) e = The size of the calling population f = Queue ranking rule
(Ordering of the queue)
 Different types of Queuing Model
1. (M/M/1): (“/FIFO) system
2. (M/M/C): (“/ FIFO) system
3. (M/M/1): (“/FIFO) system
4. (M/M/1): (“/FIFO) system
7.10.1 [M/M/1]:{//FCFS} Queue System(Single Channel Queuing
System) :
This is a queuing model in which the arrival is Marcovian and departure
distribution is also Marcovian, number of server is one and size of the
queue is also Marcovian, no. of server is one and size of the queue is
infinite and service discipline is 1st come 1st serve (FCFS) and the calling
source is also finite .
Applying the single -server model :
1. Analyze service times. munotes.in

Page 141

141 Mathematical Foundation for Computer Science 2 2. Analyze arrival rates
3. Determine queue capacity
4. Determine size of source population
5. Choose model from SINGLEQ worksheet.
Single -server equations :
Arrival rate = ë
Service rate = ì
Mean number in queue = ë2/(ì(ì -ë))
Mean number in system = ë /(ì -ë)
Mean time in queue = ë /(ì(ì -ë))
Mean time in system = 1/(ì -ë)
Utilization ratio = ë /ì
Single -server queuing identities :
A. Number units in system = arrival rate * mean time in system
B. Number units in queue = arrival r ate * mean time in queue
C. Mean time in system = mean time in queue + mean service time
Note: Mean service time = 1/ mean service rate
If we can determine only one of the following, all other values can be
found by substitution:
 Number units in system or queue
 Mean time in system or queue
7.10.2 Example of single server queue model :
A help desk in the computer lab serves students on a first -come, first
served basis. On average, 15 students need help every hour. The help
desk can serve an average of 20 students per hour.
Solution : Based on this description, we know:
µ = 20 students/hour (average service time is 3 minutes)
λ = 15 students/hour (average time between student arrivals is 4 minutes)
Average Utilization is
munotes.in

Page 142

142 Simulation Average Number of Student in the S ystem, and in Line is


Average Time in the System & in Line is.


Probability of n Students in the Line





Single Server: Spreadsheet Approach
Key Formulas :
B9: =1/B5
B10: =1/B6
B13: =B5/B6
B14: =1 -B13
B15: =B5/(B6 -B5)
B16: =B13*B15
B17: =1/(B6 -B5)
B18: =B13*B17
B22: =(1 -B$13)*(B13^B21) munotes.in

Page 143

143 Mathematical Foundation for Computer Science 2

Use Data Table (tracking B22) to easily compute the probability of n
customers in the system.
Single Server: Probability of n Students in the System :


7.11 LIST OF REFERENCE 1. Vogel, M. A., “Q ueuing Theory Applied to Machine Manning,”
Interfaces, Aug. 79.
2. Jerry Banks, John S. Carson, Barry L. Nelson, Contributor Barry L.
Nelson “Discrete -event System Simulation”,Prentice Hall, 1996,
Edition 2, illustrated, ISBN 0132174499, 9780132174497.
3. Averill M. LAW, W David Kelton,” SIMULATION MODELING &
ANALYSIS”,1991, Second Edition,

munotes.in

Page 144

144 Simulation Web References :
1. Decision Modelling, Prof. BiswajetMahanty, IIT -KHARGPUR,
https://nptel.ac.in/courses/110105082/
 “Operations Research: Applications and Algorithms ” By Wayne L.
Winston ,Ch. 21
 “Operations Research: An Introduction” By Hamdi Taha, Ch. 16.


*****


munotes.in

Page 145

145
8
QUEUING MODELS
Unit structure
8.0 Objective
8.1 Introduction
8.2 Essential features of Queuing Systems
8.3 Operating characteristics of Queuing System
8.4 Classification of Queuing Models
8.4.1 M/M/1: 1/FCFS
8.4.2 M/M/1: N/FCFS
8.5 Summary
8.6 References
8.7 Exercise
Self-Learning Topics: Understanding Kendle‟s notation in queuing
theory.
8.0 OBJECTIVES After going through this chapter, students will able to:
● Know the examples of various queuing system structures.
● Understand the key elements and underlying mathematical concepts
queuing mod els.
● Discuss various operating characteristics of queuing system
● Examine and solve the single -server queuing model and multiple -
server queuing model problems.
● Understand economic trade -offs associated with designing and
managing queuing systems.
● Understand strengths and weaknesses of Queuing Models.
8.1 INTRODUCTION Queuing Theory is a branch of mathematics that studies how lines form,
how they function and why they malfunction. It is essential to the study of
how people behave when they have to wait in lin e to make a purchase or
receive a service. Also what sort of queue structure is required to move
people most efficiently. Queue form because resources are limited. For
example how many supermarkets required in a particular area to avoid
queuing, how many b uses or trains needed if queues were to be avoided?
A Queuing model is created in order to anticipate queue length and
waiting time. Queuing model was first developed by a Danish engineer A. munotes.in

Page 146

146 Queuing Models K. Erlang. He considered the problem of determining how many tele phone
circuits were necessary to provide for a service that would prevent
customers from waiting too long for an available circuit. In designing
queuing systems we need to aim a balance between service to customers
and economic considerations (not too many servers).
In short we can say that whenever there is service to be provided and there
are individuals/items/unit needing that service, we usually find a line
formed of units waiting for the service. Such a waiting line is called a
Queue.
Following are f ew examples of queue:
1. Railway Ticket Booking
2. Bank counter
3. Toll Gate
4. Library
5. Airport
6. Maintenance shop
8.2 ESSENT IAL FEATURES OF QUEUING SYSTEMS A. Elements of Queuing System: A schematic representation of a
Queuing System is given below.



Thus, basically there are only two elements of a Queuing System.
1. Customers: Arriving randomly (in the Queue if either customer is
waiting otherwise straightway go to the service counter).
2. Services: Individual / unit giving the desired service (at any service
point there can be more than one service)
Note 1: When there are more than one service, there may be separate
queue for each server (eg. railway ticket booking) or there may be
only one queue and customers approach a free server in the order of
their arrival.
Note 2: Sometimes service is provided sequentially in stages. For
example, in a bank, a customer presents his/her cheque to the counter
clerk. After checking the balance, the counter clerk gives a taken to
the customer and passes the cheque / withdrawal form to the
supervisor for signature verification. Then the supervisor sends the Server Enter Leave Waiting line of customers (Queue) munotes.in

Page 147

147 Mathematical Foundation for Computer Science 2 cheque to the cashier for payment. Such Queues are called Queue in
Jordan.
B. Queue and Service Discipline:
Queue Discipline: It is determined by customers.
Bulk Arrival: Usually customers arrive at the service point singly at
random but in certain case they may arrive in groups. Such arrival are
called Bulk Arrivals.
Balking: In on arrival, a customer things that the queue is too long he or
she may decide no t to joint the cube this is called Balking.
Reneging: The customer joins the queue. After sometime leaves if he or
she thinks the waiting time could be longer than he or she was prepared
for.
Jockeying: This situation occurs when there are multiple servers each
having a separate queue. The customer joins a particular queue but after
some time he or she joins another queue due to the smaller size or fastest
service by the server
Service Discipline: This is determined by service provider. It is the
manner in which the customer will be provided the required service.
First Come First Served (FCFS)/ First In First Out (FIFO): This is the
most common manner of service and is followed in general
Last Come First Served (LCFS)/L ast In First Out (LIFO): This
normally happens when the customer are doing sheets or papers or files
piled up.
Priorities: customer arriving at the service point is taken at the head of the
queue by passing all waiting customers. eg profusely bleeding patient/ an
emergency case of a hospital or VIP. The priorities can be of two type:
1. Pre-emptive: On arrival, the service to the customer starts
immediately by putting the customer already getting the service in
abeyance.
2. Non- Pre-emptive: On arrival the customer is taken at the head of the
queue b ut his service will start only after the customer already getting
service leaves.
8.3 OPERATING CH ARACTERISTICS OF QUEUING SYSTEM A. Terminology:
Arrival Rate : The rate (per unit of time) at which customers arrive at the
service point. The mean rate for a rrivals is denoted by λ . munotes.in

Page 148

148 Queuing Models Service Rate : The rate (customers per unit of time) at which one service
channel can perform the service. The mean service rate is denoted by µ
(number of customers per unit of time). We can use the term departure rate
also.
Proba bility distribution of arrival and departure service straight
through one service channel: The number of arrivals per unit of time and
number of units (customers) served by the service channel follows some
probability distribution. It is assumed that arriv al pattern and service
pattern are independent.
Note 1: The most common probability distribution to describe arrival and
departure (service) pattern is Poison (also called Markorians denoted by
M).
Note 2: If number of occurrences (number of customers arri ving per unit
of time or number of customer serviced per unit of time) follow a poison
distribution then inter arrival time (time between two successive arrivals)
and the service time follow exponential distribution.
B. Some more Definition and Notations :
1. λ = mean number of arrivals per time period
2. µ = mean number of customers ( or units) serviced per unit of time
3. 1/λ = mean inter arrival time (mean time between arrivals)
4. 1/ µ = mean time per customer served
5. ρ = average utilization of the service facil ity (Service utilization
Factor ) defined as ρ = λ / µ
6. Lq = Mean (Expected) number of customers (waiting) in the Queue
7. Ls =Mean (Expected) number of customers in the system (waiting +
receiving service)
8. Wq = Mean (Expected) Waiting Time (Time spent in th e queue before
the start of the service)
9. Ws = Mean time spent in the system (waiting time + service)
10. n = Maximum number of customers permitted in the system
11. Pn = Probability that there are n customers in the system
12. P0 = Probability of zero (No) customer s in the system
13. 1- P0 = Probability of the system being busy
14. Pn (t) = Probability that there are n customers in the system at time t
15. GD: General Discipline (of service) munotes.in

Page 149

149 Mathematical Foundation for Computer Science 2 C. Notation of a Queuing System: (P/Q/R: (X/Y/Z))
Where,
P = Arrival pattern probab ility distribution.
Q = Service pattern exponential distribution.
R = Number of servers / number of service channels
X = Source discipline (FCFS, LCFS etc)
Y = Maximum number of customers permitted in the system
Z = size of source (population of customers)
For example (M/M/K): (FCFS/∞/∞) means
P = Poisson,
Q = Poisson,
R = k services
X = First come first serve (FCFS)
Y = System capacity is infinite (any number of customers can arrive)
Z = size of the source population is infinite i. e. the possible number of
customers are infinite.
8.4 CLASSIFICATION OF QUEUING MODELS 1. (M/M/1): (GD/∞/∞)
2. (M/M/k): (GD/∞/∞)
3. (M/M/1): (GD/N/∞)
4. (M/M/k): (GD/N/∞)
5. (M/M/1): (GD/N/N)
6. (M/M/k): (GD/N/N)
8.4.1 Model 1: Single Server Poisson Arrivals with Exponential
Service Infinite Popula tion Model (M/M/1): (FCFS/∞/∞):
The following are the following are the assumptions to be made in this
type of model:
1. The queue discipline is FCFS i.e. first come first served.
2. Arrival rate follows Poisson distribution and service time follows
exponential distribution. munotes.in

Page 150

150 Queuing Models 3. Arrival rate and service rate are both independent of the number of
customers in the waiting line.
4. Mean arrival rate λ is less than the mean service rate µ.
The basic characteristics of this model are as follows: S.no Parameters System Queue 1 Average waiting time per customer Ws =

2 Average (expected) length (Number of customers) Ls =
Lq =
3 Non empty queue length

4 Probability that there will be n customers in the system

5 Probability that there will be more than n customers in the system
6 Probability that waiting time is more than t. e-(

e-(

Remarks:
1. The average waiting time indicates waiting time in queue not in
system unless specified.
2. Probability that a service channel is busy or utilization factor for the
system, ρ = λ / µ
Problem 1: A self -serviced cafeteria manned by single cashier. During
peak hours, customers arrive at a rate of 24 customer per hour. The
average number of customer that can be serviced by cashier is 28 per hour.
Calculate:
i. The probability that cashier is idle.
ii. The average number of customers in the queuing system.
iii. The average time a customer spends in the system.
iv. The average number of customers in the queue.
v. The ave rage time a customer spends in the queue waiting for service.
Solution:
According to the given information
Mean arrival rate,
= 24 customer per hour
Mean service rate, µ = 28 customer per hour munotes.in

Page 151

151 Mathematical Foundation for Computer Science 2 i. The probability that cashier is idle.
Po = 1 -
= 1 -
= 0.143
ii. The average number of customers in the queuing system.
Ls =

=
= 6
ii. The average time a customer spends in the system.
Ws =



=
hour or 15 minutes
iii. The average number of customers in the queue.
Lq =

=

= 5.142
iv. The average time a customer spends in the queue waiting for service.





=
hour = 12.85 minutes
Problem 2: Arrivals at a certain telephone booth follows Poisson
distribution with an average time of 10 minutes between one arrival and
the next. The length of phone call follows Exponential distribution with a
mean of 4 minutes. Calculate:
i. Expected queue length.
ii. The average number of customers in the queuing system.
iii. The average time a customer has to wait in the queue. munotes.in

Page 152

152 Queuing Models iv. The average time a customer has to spend in the system.
Solution:
According to the given information:
Mean arrival rate,
= 6 customer per hour (one customer in 10 minutes
than 6 customers in 60 minutes
Mean service rate, µ = 15 customer per hour
i. Expected queue length.
Lq =

=

=
customer
ii. The average number of customers in the queuing system.
Ls =

=

=
customer
iii. The average time a customer has to wait in the queue.





=
hour
iv. The average time a customer has to spend in the system.
Ws =



=
hour munotes.in

Page 153

153 Mathematical Foundation for Computer Science 2 Problem 3: Customers arrives at a certain airline reservation booking
counter manned by a single cle rk at a rate of 6 per hour, assuming arrival
of customer follows Poisson distribution. The clerk can serve a customer
on an average of 4 minutes, with an exponentially distributed service time.
Calculate:
i. What is the probability that the system is busy?
ii. What is the average time a customer spends in the system?
iii. What is the average length of the queue?
iv. What is the number of customer in the system?
Solution:
According to the given information:
Mean arrival rate,
= 6 customer per hour
Mean service rate, µ = 15 customer per hour (one customer in 4 minutes,
so in one hour mean service time will be 15 customer per hour)
i. What is the probability that the system is busy?
ρ = Probability of the system being busy =


=

= 0.6 i.e. 60% of the time system is busy.
ii. What is the average time a customer spends in the system?
Ws =



=
hour
iii. What is the average length of the queue?
Lq =

=

=
customer
munotes.in

Page 154

154 Queuing Models iv. What is the number of customer in the system?
Ls =

=

=
customer
Problem 5: Arrival of customers at a petrol pump follows Poisson
distribution with an average time of 4 minutes between arrivals. The
service at petrol pump follows Exponential distribution, and the mean time
taken to service a unit is 1 minute. Find the following:
i. Expected queue length.
ii. The average number of customers in the system.
iii. The average time a customer has to wait in queue.
iv. The average time a customers has to spend in the system.
Solution:
According to the given information:
Mean arrival rate,
= 15 customer per hour
Mean service rate, µ = 60 customer per hour (one customer in 1 minutes,
so in one hour mean service time will be 60 customer per hour)
i. Expected queue length.
Lq =

=

=
customer
ii. The average number of customers in the system.
Ls =

=

=

=
customer
munotes.in

Page 155

155 Mathematical Foundation for Computer Science 2 iii. The average time a customer has to wait in queue.




=
hour

iv. The average time a customers has to spend in the system.
Ws =



=
hour
Problem 6: Arrival of customers at a barber shop manned by single
person follows Poisson distribution with an average tim e of 15 minutes
between arrivals. The customer spend on an average of 10 minutes in the
barber’s shop follows Exponential distribution. Find the following:
i. What is the probability that the barber is busy all the time?
ii. The expected number of custome r in the barber’s shop?
iii. How much time can a customer expect to wait for his turn?
iv. How much time can a customer expect to spend in the shop?
Solution:
According to the given information:
Mean arrival rate,
= 4 customer per hour
Mean service rate, µ = 6 customer per hour
i. The probability that the barber is busy all the time?
ρ = Probability of the barber being busy =


=

=

munotes.in

Page 156

156 Queuing Models ii. The expected number of c ustomer in the barber’s shop?
Ls =

=

=

= 2 customer per hour
iii. The time customer expects to wait for his turn



=
hour
iv. The time customer expect to s pend in the shop
Ws =



=
hour
8.4.1 Model 3: Finite Queue Length Model (M/M/1): (FCFS/N/∞):
This model is different from model 1, this model is applicable for when
the queue can accommodate only a limited number of customers or the
maximum number of customers in the system is limited to N. New arrivals
can join the queue only if space is available, otherwise leaves the queue
without joining the queue. For the queuing system, the arrival rate of
customer follows Poisson distribution and are served on the basis of first
come first served, service rate follows exponential distribution. Ar rivals
are from infinite population and forms finite queue length.
Example for this model are queue formation at cinema ticket counter,
clinics, petrol filling pumps etc.
1. Probability of zero customer in the queue system:
Po =
.
munotes.in

Page 157

157 Mathematical Foundation for Computer Science 2 2. Probability of n customer in the queue system:
Pn = (λ / µ )n.Po 0 < n ≤ N .
3. Average number of customers in the queue:
Lq =

4. Average number of customers in the queue system:
Ls =

5. Average time a customer spends in the system:
Ws =
where λ’ = λ (1-Pn).
6. Average time a customer spends in the queue:
7. Wq =

Problem 4: At a railway station only one train can stand at a time. The
railway yard can accommodate only two trains to wait and other trains if
there were given a signal to leave. Arrivals of trains follows Poisson
distribution at an average rate of 6 per hour. The railway yard can
accommodate on an average of 12 trains per hour. Assuming exponential
service distribution, find the steady state proba bilities for the various
number of trains in the system.
Solution:
According to the given information:
Mean arrival rate,
= 6 customer per hour
Mean service rate, µ = 12 customer per hour)
ρ = Probability of the system being busy =


=

= 0.5 i.e. 50% of the time
The maximum queue length is 2 i.e. the maximum number of trains in the
system is 3 = N (one train will stand and two can remain in queue)
Probability of no train in the queue system:
Po =.
=
=0.53 munotes.in

Page 158

158 Queuing Models Probability of 3 trains in the queue system:
Pn = (λ / µ )n.Po
P1 = (0.5) (0.53) =0.27; P2 = (0.5)2 (0.53) = 0.1325; P3 =
(0.5)3(0.53) = 0.06625
Average number of tr ains in the queue system:
Ls =

Ls = 1(0.27) +2(0.1325) + 3(0.06625) = 0.73
Problem 5: At a railway station, trains arrives at the yard every 12
minutes and the service time is 30 minutes. If the line capacity of yard is
only 4 trains assu ming arrival and service follows Poisson and
Exponential distribution respectively. Find
i. What is the probability that the yard is empty?
ii. The average number of trains in the system
Solution:
According to the given information:
Mean arrival rate,
= 5 trains per hour
Mean service rate, µ = 2 trains per hour
N = 4
ρ = Probability of the yard being busy =

=
= 2.5
i. The probability that the yard is empty
Probability of no train in the queue system :
Po =.
=

=
=

=
= 0.01551
ii. The average time a customer spends in the system
Probability of 4 trains in the queue system:
Pn = (λ / µ )n.Po munotes.in

Page 159

159 Mathematical Foundation for Computer Science 2 P1 = (2.5) (0.01551) =0.038775; P2 = (2.5)2 (0.01551) =
0.0969375;
P3 = (2.5)3(0.01551) = 0.24234375; P4 = (2.5)4(0.01551) =
0.605859375
Average number of trains in the queue system:
Ls =

Ls = 1(0.038775) +2(0.0969375) + 3(0.24234375) + 4(0.605859375)
= 3.383
8.4 SUMMARY A queuing theory is a branch of mathematics that answers how queues are
formed? How it works? and discusses about the mathematical analysis of
queuing process . Queuing theory examines every aspect of queue process,
including arrival process, serv ice process, and number of servers, number
of customers and number of system.
A real life applications of queuing theory finds helpful in wide range of
business. It helps in maintaining traffic flow, faster and improved
customer services, scheduling and ma naging inventory, streamline staffing
needs etc.
8.5 REFERENCES Books:
1. Operations Research Techniques for Management – V. K. Kapoor
2. Operations Research – Prem Kumar Gupta and D. S. Hira
3. Quantitative Techniques in Management – Vohra
Websites:
https://www.csus.edu/indiv/f/freemand/chapter%2018%20objectives.htm
https://ed ge.sagepub.com/venkataraman/student -resources/module -
c/learning -objectives
https://docplayer.net/18444783 -Queuing -analysis -chapter -outline -
learning -objectives -supplementary -chapter -b.html
8.6 EXERCISE Problem 1: The arrival rate of customer in a bank on an average is 15/hr
under Poisson law. The teller of a bank can serve one customer in 3
minutes under exponential law. Find:
i. The probability that teller is busy. munotes.in

Page 160

160 Queuing Models ii. The average number of customers in the queuing system.
iii. The average time a customer spends in the system.
iv. The average number of customers in the queue.
Problem 2: The arrival rate of customer in a bank on an average is 15/hr
under Poisson law. The teller of a bank can serve one customer in 3
minutes under exponential law. Find:
i. The probability that teller is busy.
ii. The average number of customers in the queuing system.
iii. The average time a customer spends in the system.
iv. The average number of customers in the queue
Problem 3: A supermarket has a single cashier. Arrival rate of customers
follows Poisson distribution with an average rate of 28 customer per hour.
The average number of customers that can be serviced by cashier is 32 per
hour assuming exponential service distribution. Calculate:
i. The probability that cahier is idle.
ii. The average number of customers in the queuing system.
iii. The average time a customer spends in the system.
iv. The average number of customers in the queue
v. The average time a customer spends in the queue waiting for service.
Problem 4: Goods train comes to yard at the rate of 34 trains per day and
the inter arrival time follows Poisson distribution. The service train for
each train assumed to be exponential wit h an average of 40 minutes. If the
yard can admit 5 trains at a time. Calculate:
i. What is the probability that the yard is empty?
ii. The average number of trains in the system
Self-Learning Topics: Understanding Kendle‟s notation in queuing
theory
D.G Kendall and later A. Lee (1966) introduced useful notations for
queuing models. The complete notations can be expressed as :
(a/b/c): (d/e/f)
Where,
a = arrival distribution
b = departure distribution munotes.in

Page 161

161 Mathematical Foundation for Computer Science 2 c = number of parallel service channels in the system
d = ser vice discipline
e = maximum number of customer allowed in the system
f = calling source or population
M = Markovian arrival or departure distribution
Ek = Erlangian service time distribution with parameter k
GI = general independent arrival distribution
G = general departure distribution
D = deterministic interarrival or service times
FCFS = first come first served
LCFS = last come first served
SIRO = service in random order
GD = general service discipline





*****

munotes.in