BIJU PATNAIK INSTITUTE OF IT & MANAGEMENT STUDIES,

BHUBANESWAR

Decision Science

Sub. Code: MBA 105

(For MBA Students)

Prepared By
Mr. A.P Nanada,
Associate Prof. (OM)

1
2
 BIJU PATNAIK INSTITUTE OF IT & MANAGEMENT STUDIES, BHUBANESWAR

Module- I
Prepared By Mr. A.P. Nanda, Associate Prof. (OM)

Measures of central tendency

INTRODUCTION
According to Simpson and Kafka a measure of central tendency is typical value around which other
figures aggregate‘.
According to Croxton and Cowden. An average is a single value within the range of the data that is
used to represent all the values in the series. Since an average is somewhere within the range of
data, it is sometimes called a measure of central value‘.
OBJECTIVES

The main aim of this unit is to study the frequency distribution. After going through this unit
you should be able to:

 describe measures of central tendency ;

 calculate mean, mode, median, G.M., H.M. ;

 find out partition values like quartiles, deciles, percentiles etc;

 know about measures of dispersion like range, semi-inter-quartile range, mean

deviation, standard deviation;

 Calculate moments, Karls Pearsion’s β and γ coefficients, skewness, kurtosis.

MEASUIRES OF CENTRAL TENDENCY

The following are the five measures of average or central tendency that are in common
use :
(i) Arithmetic average or arithmetic mean or simple mean
(ii) Median
(iii) Mode
(iv) Geometric mean
(v) Harmonic mean
Arithmetic mean, Geometric mean and Harmonic means are usually called Mathematical
averages while Mode and Median are called Positional averages.

ARITHMETIC MEAN
To find the arithmetic mean, add the values of all terms and them divide sum by the number of
terms, the quotient is the arithmetic mean. There are three methods to find the mean :
3
 (i) Direct method: In individual series of observations x1, x2,… xn the arithmetic mean is
obtained by following formula.
x + x + x +x x +x
A.M . = 1 2 3 4.......................... n-1 n
n
(ii) Short-cut method: This method is used to make the calculations simpler.
Let A be any assumed mean (or any assumed number), d the deviation of the arithmetic
mean, then we have

(iii) Step deviation method: If in a frequency table the class intervals have equal width, say i
than it is convenient to use the following formula.

Where u=(x-A)/ i ,and i is length of the interval, A is the assumed mean.

Example 1. Compute the arithmetic mean of the following by direct and short -cut methods
both:

Class 20-30 30-40 40-50 50-60 60-70

Freqyebcy 8 26 30 20 16

Solution.

Class Mid Value f fx d= x-A fd

x A = 45
20-30 25 8 200 -20 -160
30-40 35 26 910 -10 -260
40-50 45 30 1350 0 0
50-60 55 20 1100 10 200
6070 65 16 1040 20 320
Total N = 100 ∑ fx = 4600 ∑f d = 100
By direct method

By short cut method.

Let assumed mean A= 45.

M = A + (∑ fd )/N = 45+100/100 = 46.

Example 2 Compute the mean of the following frequency distribution using step deviation
4
 method. :

Class 0-11 11-22 22-33 33-44 44-55 55-66

Frequency 9 17 28 26 15 8

Solution.

Class Mid-Value f d=x-A u = (x-A)/i fu

(A=38.5) i=11
0-11 5.5 9 -33 -3 -27
11-22 16.5 17 -22 -2 -34
22-33 27.5 28 -11 -1 -28
33-44 38.5 26 0 0 0
44-55 49.5 15 11 1 15
55-66 60.5 8 22 2 16
Total N = 103 ∑fu = -58

Let the assumed mean A= 38.5, then

M = A + i(∑fu )/N = 38.5 + 11(-58)/103

= 38.5 - 638/103 = 38.5 - 6.194 = 32.306

PROPERTIES OF ARITHMETIC MEAN

Property 1 The algebraic sum of the deviations of all the variates from their arithmetic mean is
zero.

Proof . Let X1, X2,… Xn be the values of the variates and their corresponding frequencies be f1, f2,
…, fn respectively.

Let xi be the deviation of the variate Xi from the mean M, where i = 1,2, …, n. Then

=0

M = (∑fx)/N = 4600/100 = 46.

5
 Exercise 1(a)

Q.1) Marks obtained by 9 students in statistics are given below.

52 75 40 70 43 65 40 35 48

calculate the arithmetic mean.

Q.2) Calculate the arithmetic mean of the following distribution

Variate : 6 7 8 9 10 11 12

Frequency : 20 43 57 61 72 45 39

Q.3) Find the mean of the following distribution

Variate : 0-10 10-20 20-30 30-40 40-50

Frequency : 31 44 39 58 12

MEDIAN

The median is defined as the measure of the central term, when the given terms (i.e., values of
the variate) are arranged in the ascending or descending order of magnitudes. In other words
the median is value of the variate for which total of the frequencies above this value is equal to
the total of the frequencies below this value.

Due to Corner, ―The median is the value of the variable which divides the group into two equal
parts one part comprising all values greater, and the other all values less then the median‖.

For example. The marks obtained, by seven students in a paper of Statistics are 15, 20, 23, 32,
34, 39, 48 the maximum marks being 50, then the median is 32 since it is the value of the 4 th
term, which is situated such that the marks of 1 st, 2nd and 3rd students are less than this value
and those of 5th, 6th and 7th students are greater then this value.

COMPUTATION OF MEDIAN

(a) Median in individual series.

Let n be the number of values of a variate (i.e. total of all frequencies). First of all we
write the values of the variate (i.e., the terms) in ascending or descending order of magnitudes

Here two cases arise:

6
 Case 1. If n is odd then value of (n+1)/2th term gives the median.

Case2. If n is even then there are two central terms i.e., n/2th and

The mean of
These two values gives the median.

(b) Median in continuous series (or grouped series). In this case, the median (Md) is computed
by the following formula

Where Md = median

l = lower limit of median class

c f = total of all frequencies before median class

f= frequency of median class

i = class width of median class.

Example 1 – According to the census of 1991, following are the population figure, in thousands,
of 10 cities :

1400, 1250, 1670, 1800, 700, 650, 570, 488, 2100, 1700.

Find the median.

Solution. Arranging the terms in ascending order.

488, 570, 650, 700, 1250, 1400, 1670, 1800, 2100.

Here n=10, therefore the median is the mean of the measure of the 5 th and 6th terms.

Here 5th term is 1250 and 6th term is 1400.

Median (Md) = (1250+14000)/2 Thousands

= 1325 Thousands
Examples 2. Find the median for the following distribution:

Wages in Rs. 0-10 10-20 20-30 30-40 40-50

No. of workers 22 38 46 35 20

7
 Solution . We shall calculate the cumulative frequencies.

Wages in Rs. No. of Workers f Cumulative Frequencies (c.f.)

0-10 22 22
10-20 38 60
20-30 46 106
30-40 35 141
40-50 20 161

Here N = 161. Therefore median is the measure of (N + 1)/2th term i.e 81st term. Clearly 81st
term is situated in the class 20-30. Thus 20-30 is the median class. Consequently.
Median

= 20 + (½ x 161 – 60) / 46 x 10

= 20 + 205/46 = 20 + 4.46 = 24.46.

Example 3. Find the median of the following frequency distribution:

Marks No. of students Marks No. of students

Less than 10 15 Less than 50 106
Less than 20 35 Less than 60 120
Less than 30 60 Less than 70 125
Less than 40 84

Solution. The cumulative frequency distribution table:

Class (Marks) Frequency f Cumulative Frequency

(No. of students) (C. F.)
0-10 15 15
10-20 20 35
20-30 25 60
30-40 24 84
40-50 22 106
50-60 14 120
60-70 5 125
Total N = 125

Median = measure

8
 = 63rd term.

Clearly 63rd term is situated in the class 30-40.

Thus median class = 30 - 40

Median

=30 + [(125/2 – 60) / 24] x 10

= 30 + 25/24

= 30+1.04 = 31.04

MODE

The word ‗mode is formed from the French word ‗La mode‘ which means ‗in fashion‘.
According to Dr. A. L. Bowle ‗the value of the graded quantity in a statistical group at which the
numbers registered are most numerous, is called the mode or the position of greatest density
or the predominant value.‘

Mode

According to other statisticians, ‗The value of the variable which occurs most frequently in the
distribution is called the mode.‘
The mode of a distribution is the value around the items tends to be most heavily
concentrated. It may be regarded at the most typical value of the series‖.
Definition. The mode is that value (or size) of the variate for which the frequency is maximum
or the point of maximum frequency or the point of maximum density. In other words, the mode
is the maximum ordinate of the ideal curve which gives the closest fit to the actual distribution.

9
 Method to Compute the mode:
(a) When the values (or measures) of all the terms (or items) are given. In this case the
mode is the value (or size) of the term (or item) which occurs most frequently.

Example 1. Find the mode from the following size of shoes

Size of shoes 1 2 3 4 5 6 7 8 9

Frequency 1 1 1 1 2 3 2 1 1

Here maximum frequency is 3 whose term value is 6. Hence the mode is modal size number 6.

(b) In continuous frequency distribution the computation of mode is done by the following
formula

l = lower limit of class,s

f1 = frequency of modal class,

f0 =frequency of the class just preceding to the modal class,

f2 =frequency of the class just following of the modal class, i

=class interval

Example 2.Compute the mode of the following distribution:

Class : 0-7 7-14 14-21 21-28 28-35 35-42 42-49
Frequency :19 25 36 72 51 43 28
Solution. Here maximum frequency 72 lies in the class-interval 21-28. Therefore 21-28 is the
modal class.
l = 21, f1 = 72, f0 = 36, f2 = 51, i = 7

Mode M

10
 = 21 + 357 / 87
= 21 + 4.103
= 25.103.

(c) Method of determining mode by the method of grouping frequencies. This method is
usually applied in the cases when there are two maximum frequencies against two different
size of items. This method is also applied in the cases when it is possible that the effect of
neighboring frequencies on the size of item (of maximum frequency) may be greater. The
method is as follows :

Firstly the items are arranged in ascending or descending order and corresponding
frequencies are written against them.The frequencies are then grouped in two and then in
threes and then is fours (if necessary). In the first stage of grouping, they are grouped (i.e.,
frequencies are added) by taking, first and second, third and fourth, …, . After it, the
frequencies are added in threes. The frequencies are added in the following two ways :

1. (i) First and second, third and fourth, fifth and sixth, seventh and eighth, …
(ii) Second and third, fourth and fifth, …
2. (i) First, second and third; fourth, fifth and sixth, …
(ii) Second, third and fourth; fifth, sixth and seventh, …
(iii) Third, fourth and fifth; sixth seventh and eighth, …
Now the items with maximum frequencies are selected and the item which
contains the maximum is called the mode. For illustration see following example 1.

Example 3. Compute the mode from the following distribution :

Size of Item 4 5 6 7 8 9 10 11 12 13
Frequency 2 5 8 9 12 14 14 15 11 13
Solution. From the given date we observe that size 11 has the maximum frequency
15, but it is possible that the effect of neighboring frequencies on the size of the item
may be greater. Thus it may happen that the frequencies of size 10 or 12 may be greater
and 11 may not remain mode. We shall apply the method of grouping.

11
 Size of I II III IV V VI
Items
4 2
7
5 5
13
6 8
17 15
7 9
21 22
8 12
26 35 29
9 14
28 40
10 14
29 40 43
11 15
26 39
12 11
24
13 13

We have used brackets against the frequencies which have been grouped. Now we shall
find the size of the item containing maximum frequency :
Column Size of item having maximum frequency
I 11
II 10,11
III 9,10
IV 10,11,12
V 8,9,10
VI 9,10,11

Here size 8 occurs 1 time, 9 occurs 3 times, 10 occurs 5 times, 11 occurs 4 times, 12
occurs 1 time.
Since 10 occurs maximum number of times (5 times).
Hence the required mode is size 10.

EMPIRICAL RELATION BETWEEN MEDAIN AND MODE

For moderately asymmetrical distribution (or for asymmetrical curve), the relation
Mean – Mode = 3 (Mean - Median),
approximately holds. In such a case, first evaluate mean and median and then mode is
determined by
Mode = 3 Median – 2 Mean.
If in the asymmetrical curve the area on the left of mode is greater than area on the
12
 right then
Mean < median < mode, i. e., (M < Md < M0)

If in the asymmetrical curve, the area on the left of mode is less than the area on the
right then in this case

Mode < median , mean, i.e. (M0 < Md < M).

Exercise 1(c)
Q.1) Find the Mode of the following model size number of shoes.
Model size no. of shoes : 3,4,2,1,7,6,6,7,5,6,8,9,5.

Q.2) Compute the Mode of the following distribution.

Class : 0-7 7-14 14-21 21-28 28-35 35-42 42-49
Frequency : 19 25 36 72 51 43 28

GEOMETRIC MEAN

If x1,x2, … ,xn. are n values of the variate x, none of which is zero . Then their geometric
mean G is defined by
G = (x1, x2, … xn)1/n (1)

If f1, f2, … , fn are the frequencies of x1,x2,…, xn respectively, then geometric mean G is
given by

13
 Example 2. Compute the geometric mean of the following distribution:

Marks 0-10 10-20 20-30 30-40

No. of students 5 8 3 4
Solution . Here
Class Mid-value Frequency Log Product
Log10 x F log x
0-10 5 5 0.6990 3.4950
10-20 15 8 1.1761 9.4088
20-30 25 3 1.3979 4.1937
30-40 35 4 1.5441 6.1764
N = ∑f = 20 ∑flogx =
23.2739

Log G = (∑log x)/N = 23.2739/20 = 1.1637

G = anti-log (1.1637) = 12.58 marks.

HARMONIC MEAN

The Harmonic mean of a series of values is the reciprocal of the arithmetic means of their
reciprocals. Thus if x1,x2,…, xn (none of them being zero) is a series and H is its harmonic mean
then

If f1, f2, …, fn be the frequencies of x1,x2, … , xn (none of them being zero) then harmonic mean H
is given by

14
 Example 1. Find the harmonic mean of the marks obtained in a class test, given below

Marks : 11 12 13 14 15
No. of students: : 3 7 8 5 2

Solution.
Marks Frequency 1/x f x
X f
11 3 0.0909 0.2727
12 7 0.0833 0.5831
13 8 0.0769 0.6152
14 5 0.0714 0.3570
15 2 0.0667 0.1334
N = ∑f = 25 ∑f/x = 1.9614

Required harmonic mean is given by

= 25 / 1.9614
= 25/1.9614
= 250000/19614
= 12.746 marks.
Property . For two observations x1 and x2, we have
AH = G2
Where A = arithmetic mean, H = harmonic mean and G = geometric mean.

PARTITION VALUES

If the values of the variate are arranged in ascending or descending order of magnitudes then
we have seen above that median is that value of the variate which divides the total frequencies
in two equal parts. Similarly the given series can be divided into four, ten and hundred equal
pars. The values of the variate dividing into four equal parts are called Quartile, into ten equal
parts are called Decile and into hundred equal parts are called Percentile.

QUARTILES:

Definition. The values of the variate which divide the total frequency into four equal
parts, are called quartiles. That value of the variate which divides the total frequency into two
equal parts is called median. The lower quartile or first quartile denoted by Q1 divides the
frequency between the lowest value and the median into two equal parts and similarly the

15
 upper quartile (or third quartile) denoted by Q3 divides the frequency between the median and
the greatest value into two equal parts. The formulas for computation of quartiles are given by

where l, cf , n, f, i. have the same meaning as in the formula for median.

DECILES:

Definition,. The values of the variate which divide the total frequency into ten equal
parts are called deciles. The formulas for computation are given by

PERCENTILES:

Definition. The values of the variate which divide the total frequency into hundred equal
parts, arte called percentiles. The formulas for computation are :

Example 1. Compute the lower and upper quartiles, fourth decile and 70th percentile for the
following distribution:

Marks group No. of students Marks group No. of students

5-10 5 25-30 5
10-15 6 30-35 4
15-20 15 35-40 2
20-25 10 40-45 2

Solution. First we make the cumulative frequency table :

Class Frequency Cumulative Class Frequency Cumulative

Frequency Frequency
5-10 5 5 25-30 5 41
10-15 6 11 30-35 4 45
15-20 15 26 35-40 2 47
20-25 10 36 40-45 2 49

16
 (i) To compute Q1 -20 Thus 15-
20 is lower quartile class.
l = 15, cf = 11, f = 15, i = 20-15 = 5

= 15 + (12.25 –
(ii) To Compute Q3 = 36.75 which clearly lies in the class 25-30. Thus

l = 25,cf = 36, f = 5, i = 30-25 = 5

= 25 + (36.75 –

(iii) To compute D4 Here 4/10 N = 4/10 x 49 = 19.6, which clearly lies in the class 15-20.
Thus l = 15, cf = 11, f = 15, i = 5

= 15 + 19.6 –
(iv) To compute P70. Here 70N/100 = 7/10 x 49 = 34.3 which clearly lies in the class 20- 25.
Thus l = 20, cf = 26, f = 10, i = 5

= 20 + (34.3 –
Exercise 1(b)

Q.1) Find the meadian of the following.

20 18 22 27 25 12 15

17
 Q.2) Calculate the meadian, lower and upper quartiles, third decile and 60 th percentile for the
following distribution.
Class : 0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80
Frequency : 5 8 7 12 28 20 10 10

MEASURES OF DISPERSION

DISPERSION OR VARIATION

An averages gives an idea of central tendency of the given distribution but it is

necessary to know how the variates are clustered around or scattered away from the average.
To explain it more clearly consider the works of two typists who typed the following number of
pages in 6 working days of a week :

Mon. Tues. Wed. Thus. Fri. Sat. Total pages

1 typist : 15 20 25 25 30 35 150

2 typist : 10 20 25 25 30 40 150

We see that each of the typist 1 and 2 typed 150 pages in 6 working days and so the
average in both the cases is 25. Thus there is no difference in the average, but we know that in
the first case the number of pages varies from 15 to 35 while in the second case the number of
pages varies from 10 to 40. This denotes that the greatest deviation from the mean in the first
case is 10 and in the second case it is 15 i.e., there is a difference between the two series., The
variation of this type is termed scatter or dispersion or spread.

Definition. The degree to which numerical data tend to spread about an average value is
called variation or dispersion or spread of the data.

Various measures of dispersion or variation are available, the most common are the
following.

THE RANGE

It is the simplest possible measure of dispersion. The range of a set of numbers (data) is
the difference between the largest and the least numbers in the set i.e. values of the variable. If
this difference is small then the series of numbers is supposed regular and if this difference is
large then the series is supposed to be irregular.

Example : Compute the range for the following observation

18
 15 20 25 25 30 35

Solution: Range = Largest – Smallest

i.e., 35-15=20

SEMI-INTER-QUARTILE RANGE

Definition. The inter quartile range of a set of data is defined by

Inter-quartile range = Q3-Q1

where Q1 and Q3 are respectively the first and third quartiles for the data.

Semi-inter quartile range (or quartile deviation) is denoted by Q and is defined by Q

=(Q3 – Q1)/2

where Q1 and Q3 have the same meaning as given above.

The semi-inter-quartile range is a better measure of dispersion than the range and is easily
computed. Its drawback is that it does not take into account all the items.
MEAN DEVIATION

Definition. The average (or mean) deviation about any point M, of a set of N numbers x 1,
x2, …, xN is defined by

1n
Mean Deviation (M. D.) = δm = xi - M
N i=1

where M is the mean or median or mode according as the mean deviation from the
mean or median or mode is to be computed, l xi – M l represents the absolute (or numerical)
value. Thus l-5l = 5.

If x1,x2,…, xk occur with frequencies f1,f2,…,fk respectively, then the mean

deviation (δm) is defined by

Mean deviation depends on all the values of the variables and therefore it is a better
measure of dispersion than the range or the quartile deviation. Since signs of the deviations are
ignored (because all deviations are taken positive), some artificiality is created.

In case of grouped frequency distribution the mid-values are taken as x.

19
 Example 1. Find the mean deviation from the arithmetic mean of the following distribution :

Marks : 0-10 10-20 20-30 30-40 40-50

No. of students : 5 8 15 16 6

Solution. Let assumed mean A = 25 and i=10

Class Mid value Frequency x-A fu x-M f lx-Ml

u=
X f i
0-10 5 5 -2 -10 -22 110
10-20 15 8 -1 -8 -12 96
20-30 25 15 0 0 -2 30
30-40 35 16 1 16 8 128
40-50 45 6 2 12 18 108
Total ∑f =50 ∑fu = 10 ∑f l x – M l
= 472

Example 2. Compute the semi-inter-quartile range of the marks of 63 students in

Mathematics given below :

Marks Group No. of Students Marks Group No. of students

0-10 5 50-60 7
10-20 7 60-70 3
20-30 10 70-80 2
30-40 16 80-90 2
40-50 11 90-100 0

Solution.
20
 Marks Group Frequency f Cumulative Frequency c.f.
0-10 5 5
10-20 7 12
20-30 10 22
30-40 16 38
40-50 11 49
50-60 7 56
60-70 3 59
70-80 2 61
80-90 2 63
90-100 0 63
∑f = 63

To calculate lower Quartile Q1. Here N = 60. So ¼ (N+1)th i.e., 16th students lies in the
marks group 20-30. Thus lower quartile class is 20-30.

21
 47.25 - 38
Similarly Q3 = 40 +
11 x 10 = 48.4.

1
Semi-inter quartile range = (Q3 - Q1)
2

= ½ (48.4-23.75) = 12.32 Marks

STANDARD DEVIATION

Root – mean square Deviation:

Definition. It is defined as the positive square root of the mean of the squares of the deviations
from an origin A and denoted by s

1
s= {  f (x  A)2}
Mean square deviation. It is defined as the mean of the squares of the deviations from an origin
A. Thus

Remark. The origin A may be taken at any arbitrary point A.

Standard Deviation :

Definition. Standard deviation (or S.D.) is the positive square root of the arithmetic
mean of the square deviations of various values from their arithmetic mean M. It is usually
denoted by σ. Thus

1
σ=s= {  f (x  M )2}
Remarks:

1. When the deviations is calculated from the arithmetic mean M, then root mean square
deviation becomes standard deviation.

22
 2. The square of the standard deviation σ2 is called variance.
3. The quantity s2 is said to be second moment about the value A and is denoted by µ2‘.
4. The variance σ2 is called the second moment about the mean M and is denoted by µ2.

RELATION BETWEEN STANDARD DEVIATION AND ROOT-MEAN SQUARE DEVIATION

Consider a frequency distribution (discrete series)

x: x1 x2 … xn

f: f1 f2 … fn

Let A be the assumed mean and M the arithmetic mean. Also suppose M-A = d. Then

Hence s2 = σ2 + d2

Relation (1) shows that s is least when d = 0 i.e., A = M and the least value of s is equal to σ. In

other words the standard deviation is the least possible root mean square deviation.

Remark. Since d2>0, always, therefore, from (1), we have

S2> σ2

i.e., mean square deviation about any point A is greater than variance.

23
 SHORT CUT METHOD FOR CALCULATING STANDARD DEVIATION

We know that

Where ξ = (x-A) and A = assumed mean

STEP DEVIATION METHOD TO COMPUTE S.D.

If u = (x-A)/h = ξ/h, then ξ = uh.

By short cut method

ABSOLUTE AND RELATIVE MEASURES OF DISPERSION

The measure of dispersions namely ranger, quartile deviations, inter-quartile deviation. Mean
deviation, standard deviation, root mean square deviation (these have been discussed above)
are said to be absolute measure of dispersion, since they are expressed in terms of units of
observations (Cm., Km., Rs., degree etc.). We know that different units cannot be compared; for
example a centimeter cannot be compared with a rupee. Therefore, the dispersions in different
units cannot be compared. Also the measures of dispersion depend on the measures of central
tendency. Therefore, it is needed to define some measures which are independent of the units
of measurement and can be adjusted for measures of central tendency. Such type of measures
are called relation measures of dispersion or coefficients of dispersion. These relative measures
are pure numbers and are usually expressed as percentages.

They are useful to compare two series in different units and also to compare variations
of two series having different magnitudes.

Some of the relative measures of dispersion (or coefficient of dispersion) which are in
common use are given below :

(i) Quartile coefficient of dispersion. It is usually denoted by Q.D. and is defined by

24
 Q3 + Q1
Q.D.= =
Q 3 + Q1

(i) Coefficient of mean dispersion = Mean deviation about any point ‘a‘ / a .

Here any point ‗a‘ can be replaced by mean, median, mode etc.

(ii) Coefficient of variation or coefficient of dispersion. It is defined by the ration σ/M, where
σ is standard deviation and M is the arithmetic mean. It is denoted by C.V. or V. thus

C.V. or V = σ / M

Sometimes, we

define

C.V. or V = σ / M x 100

Example1. Calculate the S.D. and coefficient of variation (C.V.) for the following table :

Class : 0-10 10-20 20-30 30-40 40-50 50-60 60-70 70-80

Frequency : 5 10 20 40 30 20 10 5

Solution. We prepare the following table for the computation of S.D.

Class Mid-value x f x fu fu2

u
10
0-10 5 5 -3 -15 45
10-20 15 10 -2 -20 40
20-30 25 20 -1 -20 20
30-40 35 40 0 0 0
40-50 45 30 1 30 30
50-60 55 20 2 40 80
60-70 65 10 3 30 90
70-80 75 5 4 20 80
N=∑f = 140 ∑fu = 65 ∑fu2 = 385

Let assumed mean = 35 = A (say) and h = 10 A.M.

, M = A + h (∑fu)/N = 35 + 10 (65/140)

= 35 + 4.64 = 39.64

 (
fu
S.D., σ =h
N
385
= 10 [  (.464)2 ]
25
140
 = 10
= 10
= 10 x 1.59 = 15.9

C.V. = σ/M x100 = 15.9/39.64 x 100 = 40.11%.

QUARTILE DEVIATION AND ITS COEFFICIENT

Quartile Deviation
It is based on the lower Quartile Q1 and the upper quartile Q3. The difference Q3 - Q1 is called
the inter quartile range. The difference Q3 - Q1 divided by 2 is called semi-inter- quartile range
or the quartile deviation. Thus
Quartile Deviation (Q.D) = 𝑄3−𝑄1. The quartile deviation is a slightly better measure of
2
absolute dispersion than the range. But it ignores the observation on the tails. If we take
different samples from a population and calculate their quartile deviations, their values are
quite likely to be sufficiently different. This is called sampling fluctuation. It is not a popular
measure of dispersion. The quartile deviation calculated from the sample data does not help us
to draw any conclusion (inference) about the quartile deviation in the population.

Coefficient of Quartile Deviation

A relative measure of dispersion based on the quartile deviation is called the coefficient of
quartile deviation. It is defined as

Coefficient of Quartile Deviation =

It is pure number free of any units of measurement. It can be sued for comparing the
dispersion in two or more than two sets of data.
Example
The Wheat production (in Kg) of 20 acres is given as: 1120, 1240, 1320, 1040, 1080, 1200,
1440, 1360, 1680, 1730, 1785, 1342, 1960, 1880, 1755, 1600, 1470, 1750 and 1885. Find the
quartile deviation and coefficient of quartile deviation.
Solution
After arranging the observation in ascending order, we get, 1040, 1080, 1120, 1200, 1240,
1320, 1342, 1360, 1440, 1470, 1600, 1680, 1720, 1730, 1750, 1755, 1785, 1880, 1885, 1960.

Q1 = Value of the item

= Value of the item

26
= Value of (5.25)th item

= 5th item + 0.25 (6th item - 5th item) = 1240 + 0.25 (1320 - 1240) Q1

= 1240 + 20 = 1260

Q3 = Value of 3 (𝑛+1)the item

4

3 (20+1)
= Value of the item
4
= Value od (15.75) the item
15th item + 0.75 (16th item - 15th item) = 1750 + 0.75 (1755 - 1750)
Q3 = 1750 + 3.75 = 1753.75

𝑄3−𝑄1 1753.75−1260 492.75

Quartile Deviation (QD) = = = = 246.875
2 2 2

Coefficient of Quartile Deviation = 𝑄3−𝑄1 = 1753.75−1260 = 0.164.

THE MEAN DEVIATION

The mean deviation or the average deviation is defined as the mean of the absolute deviations
of observations from some suitable average which may be arithmetic mean, the median or the
mode. The difference (X - average) is called deviation and when we ignore the negative sign,
this deviation is written as |𝑋 − 𝑎𝑣𝑒𝑟𝑎𝑔𝑒| and is read as mod deviations. The mean of these
more or absolute deviations is called the mean deviation or the mean absolute deviation. Thus
for sample data in which the suitable average is the 𝑋, the mean deviation (M.D) is given by the
relation
Ʃ|𝑋−𝑋|
M.D =
𝑛
For frequency distribution, the mean deviation is given by
Ʃ𝑓|𝑋−𝑋,|
M.D =
Ʃ𝑓
When the mean deviation is calculated about the median, the formula becomes
Ʃ𝑓|𝑋−𝑀𝑒𝑑𝑖𝑎𝑛 |
M.D. (about median) =
Ʃ𝑓
The mean deviation about the mode is
Ʃ𝑓|𝑋−𝑀𝑒𝑑𝑖𝑎𝑛 |
M.D (about mode) =
Ʃ𝑓
For a population data the mean deviation about the population mean µ is
Ʃ𝑓|𝑋−µ |
M.D =
Ʃ𝑓

The mean deviation is a better measure of absolute dispersion than the range and the quartile
27
deviation.

A drawback in the mean deviation is that we use the absolute deviations |𝑋 − 𝑎𝑣𝑒𝑟𝑎𝑔𝑒| which
does not seem logical. The reason for this is that Ʃ (X - 𝑋) is always equal to zero. Even if we
use median or more in place of 𝑋, even then the summation Ʃ (X - median) or Ʃ (X - mode) will
be zero or approximately zero with the result that the mean deviation would always be better
either zero or close to zero. Thus, the very definition of the mean deviation is possible only on
the absolute deviations.

The mean deviation is based on all the observations, a property which is not possessed by the
range and the quartile deviation. The formula of the mean deviation gives a mathematical
impression that it is a better way of measuring the variation in the data. Any suitable average
among the mean, median or more can be used in its calculation but the value of the mean
deviation is minimum if the deviations are taken from the median. A drawback of the mean
deviation is that it cannot be used in statistical inference.

Coefficient of the Mean Deviation

A relative measure of dispersion based on the mean deviation is called the coefficient of the
mean deviation or the coefficient of dispersion. It is defined as the ratio of the mean deviation
to the average used in the calculation of the mean deviation.
Thus,
Coefficient of M.D (about mean) = Mean Deviation from Mean/Mean
Coefficient of M.D (about median) = Mean Deviation from Median/Median
Coefficient of M.D (about mode) = Mean Deviation from Mode/Mode
Example
Calculate the mean deviation from (1) Arithmetic Mean (2) Median (3) Mode in respect of the
marks obtained by nine students given below and show that the mean deviation from median is
minimum.
Marks out of 25: 7, 4, 10, 9, 15, 12, 7, 9, 7

Solution
After arranging the observations in ascending order, we get
Marks 4, 7, 7, 7, 9, 9, 10, 12, 15
Mean = Ʃ𝑋 = 80 = 8.89
𝑛 9
Median = Value of (𝑛+1) th item
2
9+1
= Value of ( ) th item
2
= Value of (5) the item = 9
Mode = 7 (Since 7 is repeated maximum number of times)

28
 Marks X |X − 𝑋| |𝑋 −𝑚𝑒𝑑𝑖𝑎𝑛| |𝑋 − 𝑚𝑜𝑑𝑒|
4 4.89 5 3
7 1.89 2 0
7 1.89 2 0
7 1.89 2 0
9 0.11 0 2
9 0.11 0 2
10 1.11 1 3
12 3.11 3 5
15 6.11 6 8
Total 21.11 21 23

Ʃ𝑓|𝑋−𝑋|
M.D from mean =
𝑛
21.11
= = 2.35
9
Ʃ|𝑋−𝑀𝑒𝑑𝑖𝑎𝑛 | 21
M.D from Median = = = 2.33
𝑛 9

Ʃ𝑓|𝑋−𝑀𝑜𝑑𝑒,| 23
M.D from Mode = = = 2.56
𝑛 9
From the above calculations, it is clear that the mean deviation from the median has the least
value.

Example
Calculate the mean deviation from mean and its coefficients from the following data:
Size of items 3-4 4-5 5-6 6-7 7-8 8-9 9 - 10
Frequency 3 7 22 60 85 32 8

Solution
The necessary calculation is given below:
Size of Items X F fX |𝑋 − 𝑋| f |𝑋 − 𝑋|
3-4 3.5 3 10.5 3.59 10.77
4-5 4.5 7 31.5 2.59 18.13
5-6 5.5 22 121.0 1.59 34.98
6- 7 6.5 60 390.0 0.59 35.40
7-8 7.5 85 637.5 0.41 34.85
8-9 8.5 32 272.0 1.41 45.12
9 - 10 9.5 8 76.0 2.41 19.28
Total 217 1538.5 198.53

Ʃ𝑓𝑋 = 1538.5
Mean = 𝑋= = 7.09
Ʃ𝑓 217
Ʃ|𝑋−𝑋| 198.53
M.D from Mean = = = 0.915
𝑛 217
𝑀.𝐷 𝑓𝑟𝑜𝑚 𝑚𝑒𝑎𝑛 0.915
Coefficient of M.D (Mean) = = = 0.129
𝑀𝑒𝑎𝑛 7.09

29
 Standard Deviation
The standard deviation is defined as the positive square root of the mean of the square
deviations taken from arithmetic mean of the data.
For the sample data the standard deviation is denoted by S and is defined as
Ʃ (𝑋− 𝑋)2
S=√
𝑛
For a population data the standard deviation is denoted by σ (sigma) and is defined as:
Ʃ (𝑋− µ)2
σ=√
𝑁
For frequency distribution the formulas become
Ʃ𝑓 (𝑋− 𝑋)2 Ʃ𝑓 (𝑋− µ)2
S=√ or σ = √
Ʃ𝑓 Ʃ𝑓
The standard deviation is in the same units as the units of the original observations. If the
original observations are in grams, the value of the standard deviation will also be in grams.
The standard deviation plays a dominating role for the study of variation in the data. It is a very
widely used measure of dispersion. It stands like a tower among measure of dispersion. As far
as the important statistical tools are concerned, the first important tool is the mean 𝑋and the
second important tool is the standard deviation S. It is based on the observations and is subject
to mathematical treatment. It is of great importance for the analysis of data and for the various
statistical inferences.

However, some alternative methods are also available to compute standard deviation. The
alternative methods simplify the computation. Moreover in discussing, these methods we will
confirm ourselves only to sample data because sample data rather than whole population
confront mostly a statistician.
Actual Mean Method
In applying this method first of all we compute arithmetic mean of the given data either
ungroup or grouped data. Then take the deviation from the actual mean. This method is
already is defined above. The following formulas are applied:
For Ungrouped Data For Grouped Data
Ʃ (𝑋− 𝑋)2 Ʃ𝑓 (𝑋− 𝑋)2
S=√ S=√
𝑛 Ʃ𝑓
This method is also known as direct method.
Assumed Mean Method
a. We use the following formulas to calculate standard deviation:
For Ungrouped Data For Grouped Data
Ʃ𝐷2 Ʃ𝐷 Ʃ𝑓𝐷2 Ʃ𝑓𝐷
S=√ − ( )2 S=√ −( )2
𝑛 𝑛 Ʃ𝑓 Ʃ𝑓
where D = X - A and A is any assumed mean other than zero. This method is also known as
short-cut method.

b. If A is considered to be zero then the above formulas are reduced to the following
formulas:

30
 For Ungrouped Data For Grouped Data
Ʃ𝑋2 Ʃ𝑥
S = √ - ( )2 Ʃ𝑓𝑋2 Ʃ𝑓𝑋 2
𝑛 𝑛 S=√ − ( )
Ʃ𝑓 Ʃ𝑓

c. If we are in a position to simplify the calculation by taking some common factor or divisor
from the given data the formulas for computing standard deviation are:
For Ungrouped Data For Grouped Data
Ʃ𝑢2 Ʃ𝑢
S = √ - ( )2 X c S=√
Ʃ𝑓𝑢2
−
Ʃ𝑓𝑢
( ) 2 X c or h
𝑛 𝑛
Ʃ𝑓 Ʃ𝑓

𝑋−𝐴 𝐷
Where u = = ; h = Class Interval and c = Common Divisor. This method is also
𝑕 𝑜𝑟 𝑐 𝑕 𝑜𝑟 𝑐

31
called method of step-deviation.
Examples of Standard Deviation
This tutorial is about some examples of standard deviation using all methods which are
discussed in the previous tutorial.
Example
Calculate the standard deviation for the following sample data using all methods: 2, 4, 8, 6, 10
and 12.
Solution:
Method - 1 Actual mean Method
X )2
(X - 𝑿
2 (2 - 7)2 = 25
4 (4 - 7)2 = 9
8 (8 - 7)2 = 1
6 (6 - 7)2 = 1
10 (10 - 7)2 = 9
12 (12 - 7)2 = 25

ƩX = 42 )2 = 70
Ʃ(X - 𝑿

Ʃ𝑋 42
𝑋= = =7
𝑛 6
Ʃ (𝑋− 𝑋)2
S=√
𝑛
70 35
S=√ = √ = 3.42
6 3

Method 2: Taking assumed mean as 6.

X D = (X - 6) D2
2 -4 16
4 -2 4
8 2 4
6 0 0
10 4 16
12 6 36
Total ƩD = 6 ƩD2 = 76
Ʃ𝐷2 Ʃ𝐷
S=√ − ( )2
𝑛 𝑛
76 6 2
S=√ −( ) = 3.42
6 6

32
 Method 3: Taking Assumed Mean as Zero
X X2
2 4
4 16
8 64
6 36
10 100
12 144
ƩX = 42 Ʃ X2= 364
Ʃ𝑋2 Ʃ𝑥
S = √ - ( )2
𝑛 𝑛
364 42
S=√ - ( )2
6 𝑛6
70 35
S = √ = √ = 3.42
6 3
Method 4: Taking 2 as common divisor or factor
X u = (X - 4)/2 u2
2 -1 1
4 0 0
8 2 4
6 1 1
10 3 9
12 4 16
Total Ʃu = 9 Ʃ u2 = 31

Ʃ𝑢2
S=√ - (Ʃ𝑢)2 X c
𝑛 𝑛
31
S = √ - (9) 2 X 2
6 6

S = √2.92 X 2 = 3.42.

Example
Calculate standard deviation from the following distribution of marks by using all the methods:
Marks No. of Students
1-3 40
3-5 30
5-7 20
7-9 10
Solution
Method 1: Actual mean method

33
 Marks f X fX )2
(X - 𝑿 )2
f (X - 𝑿
1-3 40 2 80 4 160
3-5 30 4 120 0 0
5-7 20 6 120 4 80
7-9 10 8 80 16 160
Total 100 400 400
Ʃ𝑓𝑋 400
𝑋= = =4
Ʃ𝑓 100
Ʃ𝑓 (𝑋−𝑋)2
S=√
Ʃ𝑓

400
S=√ = √4 = 2 Marks
100

Method 2: Taking assumed mean as 2

Marks f X D = (X - 2) fD fD 2
1-3 40 2 0 0 0
3-5 30 4 2 60 120
5-7 20 6 4 80 320
7-9 10 8 6 60 160
Total 100 200 800
Ʃ𝑓𝐷2 Ʃ𝑓𝐷 2
S =√ − ( )
Ʃ𝑓 Ʃ𝑓

800 200 2
S=√ − ( )
100 100

S = √8 − 4 = √4 = 2 Marks

Method 3: Using Assumed Mean as Zero

Marks f X fX fX 2
1-3 40 2 80 160
3-5 30 4 120 480
5-7 20 6 120 720
7-9 10 8 80 640
Total 100 400 2000
Ʃ𝑓𝑋2 Ʃ𝑓𝑋 2
S=√ − ( )
Ʃ𝑓 Ʃ𝑓
2000 400 2
S=√ −( )
100 100

S = √20 − 16 = √4 = 2 marks.

Method 4: By taking 2 as the Common Divisor

34
 Marks f X u = (X - 2)/2 Fu fu 2
1-3 40 2 -2 - 80 160
3-5 30 4 -1 - 30 30
5-7 20 6 0 0 0
7-9 10 8 1 10 10

Total 100 - 100 200

Ʃ𝑓𝑢2 Ʃ𝑓𝑢 2
S=√ − ( ) Xh
Ʃ𝑓 Ʃ𝑓
200 − 100 2
S=√ − ( ) X2
100 100

S = √2 − 1 X 2 = √1 X 2 = 2 marks.

Coefficient of Standard Deviation

The standard deviation is the absolute measure of dispersion. Its relative measure is
called standard coefficient of dispersion or coefficient of standard deviation, It is
defined as
Coefficient of Standard Deviation = 𝑆
𝑋
Coefficient of Variation
The most important of all the relative measure of dispersion is the coefficient of
variation. This word is variation and not variance. There is no such thing as coefficient
of variance. The coefficient of variation (CV) is defined as
Coefficient of Variation (C.V) = x 100
𝑋
Thus C.V is the value of S when 𝑋is assumed equal to 100. It is a pure number and the
unit of observations is not mentioned with its value. It is written in percentage form
like 20% or 25%. When its value is 20%, it means that when the mean of the
observation is assumed
equal to 100, their standard deviation will be 20. The C.V is used to compare the
dispersion in different sets of data particularly the data which differ in their means or
differ in the units of measurement. The wages of workers may be in dollars and the
consumption of meat in their families may be in kilograms. The standard deviation of
wages in dollars cannot be compared with the standard deviation of amount of meat in
kilograms. Both the standard deviations need to be converted into coefficient of
variation for comparison. Suppose the value of C.V for wages is 10% and the values of
C.V for kilograms of meat is 25%. This means that the wages of workers are consistent.
Their wages are close to the overall average of their wages. But the families consume
meat in quite different quantities. Some families use very small quantities of meat and
some others use large quantities of meat. We say that there is greater variation in their
consumption of meat. The observations about the quantity of meat are more dispersed
or more variant.

35
 Example
Calculate the coefficient of standard deviation and coefficient of variation for the
following sample data: 2, 4, 8, 6, 10 and 12.

Solution
X )2
(X - 𝑿
2 (2 - 7)2 = 25
4 (4 - 7)2 = 9
8 (8 - 7)2 = 1
6 (6 - 7)2 = 1
10 (10 - 7)2 = 9
12 (12 - 7)2 = 25
ƩX = 42 )2 = 70
Ʃ(X - 𝑿

Ʃ𝑋 42
𝑋= =7
𝑛6
S = √Ʃ(X - 𝑋 )2/n
70 35
S = √ = √ = 3.42
6 3
Coefficient of Standard Deviation = 𝑆 = 3.42 = 0.49
𝑋 7
Coefficient of Variation (C.V) = 𝑆 X 100 = 3.42 X 100 = 48 .86%
𝑋 7

USES OF COEFFICIENT OF VARIATION

 Coefficient of variation is used to know the consistency of the data. By
consistency we mean the uniformity in the values of the data/distribution
from arithmetic mean of the data/distribution. A distribution with smaller
C.V than the other is taken as more consistent than the other.
 C.V is also very useful when comparing two or more sets of data that are
measured in different units of measurement.

THE VARIANCE
Variance is another absolute measure of dispersion. It is defined as the average of the
squared difference between each of the observation in a set of data and the mean. For
a sample data the variance is denoted by S2 and the population variance is denoted by
σ2 (sigma square).
The sample variance S2 has the formula
Ʃ (𝑋− 𝑋)2
S2 =
𝑛
where 𝑋is sample mean and n is the number of observations in the sample.
The population variance σ2 is defined as
Ʃ (𝑋− µ)2
σ2 =
𝑁
36
 where µ is the mean of the population and N is the number of observations in the data.
It may be remembered that the population variance σ2 is usually not calculated. The
sample variance S2 is calculated and if need be, this S2 is used to make inference about
the population variance.
The term Ʃ (X - 𝑋)2 is positive, therefore S2 is always positive. If the original observations are
in centimetre, the value of the variance will be (Centimetre) 2. Thus the unit of S 2 is the
square of the units of the original measurement.

For a frequency distribution the sample variance S2 is

defined as Ʃ(𝑋− 𝑋 )2
S2 =
Ʃ𝑓
For a frequency distribution the population variance σ2 is defined as
Ʃ (𝑋− µ) 2
σ2 =
Ʃ𝑓
In simple words we can say that variance is the square root of standard
deviation. Variance = (Standard Deviation)2

Example
Calculate variance from the following distribution of marks:
Marks No. of Students
1-3 40
3-5 30
5-7 20
7-9 10
Solution
Marks F X fX (X - 𝑿)2 f (X - 𝑿)2
1 -3 40 2 80 4 160
3-5 30 4 120 0 0
5- 7 20 6 120 4 80
7-9 10 8 80 16 160
Total 100 400 400
Ʃ𝑓𝑋 400
𝑋= = =4
Ʃ𝑓 100
Ʃ𝑓 (𝑋− 𝑋)2 400
S2 = = =4
Ʃ𝑓 100
Variance S2 = 4.

SKEWNESS AND KURTOSIS

Skewness is the absence of symmetry in a distribution. Though averages and measures of dispersion
are useful in studying the data, the shape of the frequency curve may also be equally important to the
statistician. If we are studying a certain phenomenon over a period of time, the average may remain
the same, but the structure of the distribution may change. Two distributions may have identical
averages, yet one my tail off towards the higher values and the other towards the lower values.

37
To study the distribution we need a measure of this tendency which will give us the
direction and degree of this tendency which is called skewness.

A fundamental task in many statistical analyses is to characterize the location and

variability of a data set. A further characterization of the data includes skewness and kurtosis.

Skewness is a measure of symmetry, or more precisely, the lack of symmetry. A distribution, or

data set, is symmetric if it looks the same to the left and right of the center point.

Kurtosis is a measure of whether the data are heavy-tailed or light-tailed relative to a normal
distribution. That is, data sets with high kurtosis tend to have heavy tails, or outliers. Data sets
with low kurtosis tend to have light tails, or lack of outliers. A uniform distribution would be the
extreme case.

The histogram is an effective graphical technique for showing both the

skewness and kurtosis of data set.

For univariate data Y1, Y2, ..., YN, the formula for skewness is:
g1=∑Ni=1(Yi−Y¯)3/Ns3
where Y¯ is the mean, s is the standard deviation, and N is the number of data points. Note
that in computing the skewness, the s is computed with N in the denominator rather than N -
1.

The above formula for skewness is referred to as the Fisher-Pearson coefficient of skewness.
Many software programs actually compute the adjusted Fisher-Pearson coefficient of
skewness

G1=N(N−1)−−−−−−−−√N−2∑Ni=1(Yi−Y¯)3/Ns3

This is an adjustment for sample size. The adjustment approaches 1 as N gets large. For
reference, the adjustment factor is 1.49 for N = 5, 1.19 for N = 10, 1.08 for N = 20, 1.05 for N
= 30, and 1.02 for N = 100.

The skewness for a normal distribution is zero, and any symmetric data should have a
skewness near zero. Negative values for the skewness indicate data that are skewed left and
positive values for the skewness indicate data that are skewed right. By skewed left, we
mean that the left tail is long relative to the right tail. Similarly, skewed right means that the
right tail is long relative to the left tail. If the data are multi-modal, then this may affect the
sign of the skewness.

Some measurements have a lower bound and are skewed right. For example, in reliability
studies, failure times cannot be negative.

It should be noted that there are alternative definitions of skewness in the literature. For
example, the Galton skewness (also known as Bowley's skewness) is defined as

38
 Galton skewness=Q1+Q3−2Q2Q3−Q1

here Q1 is the lower quartile, Q3 is the upper quartile, and Q2 is the median. The Pearson 2

skewness coefficient is defined as

Sk2=3(Y¯−Y~)s

where Y~ is the sample median.

There are many other definitions for skewness that will not be discussed here.

For univariate data Y1, Y2, ..., YN, the formula for kurtosis is:

kurtosis=∑Ni=1(Yi−Y¯)4/Ns4
where Y¯ is the mean, s is the standard deviation, and N is the number of data
points. Note that in computing the kurtosis, the standard deviation is computed using N in the
denominator rather than N - 1.
The kurtosis for a standard normal distribution is three. For this reason, some sources use the
following definition of kurtosis (often referred to as "excess kurtosis"):

kurtosis=∑Ni=1(Yi−Y¯)4/Ns4−3

This definition is used so that the standard normal distribution has a kurtosis of zero. In
addition, with the second definition positive kurtosis indicates a "heavy-tailed" distribution
and negative kurtosis indicates a "light tailed" distribution.

Which definition of kurtosis is used is a matter of convention (this handbook uses the original
definition). When using software to compute the sample kurtosis, you need to be aware of
which convention is being followed. Many sources use the term kurtosis when they are
actually computing "excess kurtosis", so it may not always be clear.
The following example shows histograms for 10,000 random numbers generated from a
normal, a double exponential, a Cauchy, and a Weibull distribution.

39
 The first histogram is a sample from a normal distribution. The normal distribution is a
symmetric distribution with well-behaved tails. This is indicated by the skewness of 0.03. The
kurtosis of 2.96 is near the expected value of 3. The histogram verifies the symmetry.
The second histogram is a sample from a double exponential distribution. The
double exponential is a symmetric distribution. Compared to the normal, it has a stronger
peak, more rapid decay, and heavier tails. That is, we would

expect a skewness near zero and a kurtosis higher than 3. The skewness is
0.06 and the kurtosis is 5.9.
The fourth histogram is a sample from a Weibull distribution with shape parameter 1.5. The
Weibull distribution is a skewed distribution with the amount of skewness depending on the
value of the shape parameter. The degree of decay as we move away from the center also
depends on the value of the shape parameter. For this data set, the skewness is 1.08 and
the kurtosis is 4.46, which indicates moderate skewness and kurtosis.

40
 Many classical statistical tests and intervals depend on normality assumptions. Significant
skewness and kurtosis clearly indicate that data are not normal. If a data set exhibits
significant skewness or kurtosis (as indicated by a histogram or the numerical measures),
what can we do about it?

One approach is to apply some type of transformation to try to make the data normal, or
more nearly normal. The Box-Cox transformation is a useful technique for trying to
normalize a data set. In particular, taking the log or square root of a data set is often useful
for data that exhibit moderate right skewness.

Another approach is to use techniques based on distributions other than the normal. For
example, in reliability studies, the exponential, Weibull, and lognormal distributions are
typically used as a basis for modeling rather than using the normal distribution. The
probability plot correlation coefficient plot and the probability plot are useful tools for
determining a good
distributional model for the data.

41
 EXERCISES
Q1. Calculate the range and quartile deviation for wages: Also calculate coefficient of
quartile deviation:
Wages 30 - 32 32 - 34 34 - 36 36 - 38 38 - 40 40 - 42 42 - 44
Labourers 12 18 16 14 12 8 6

Hint: Coefficient of Q.D. = 𝑄3−𝑄1 = 0.081

𝑄3+𝑄1
Q2. Calculate the standard deviation from the following:
Marks 10 20 30 40 50 60
No. of 8 12 20 10 7 3
Students
Ʃ𝑓𝑑12 Ʃ𝑓𝑑1 2
Hint: σ = √√ − ( ) XC
𝑁 𝑁
109 5
= √√ − ( ) 2 X 10 = 13.5
60 60

Q3. Find the mean and standard deviation of the following

observations: X: 12 4 6 8 9
Transform the above observation such that the mean of transformed observations
becomes double the mean of X, standard deviation remain unchanged.
Hint: Mean = Ʃ𝑋 = 30/6 = 5 Let d = X - 5. Then
𝑁
2 Ʃ𝑑2 Ʃ𝑑 52
Ʃd = 52. σ = √ − ( )2 = √ = 2.94.
𝑁 𝑁 6
Q4. Explain positive and negative skewness with the help of sketches. Q5. Write short notes on skewness and
kurtosis.

42
 Correlation Analysis
Definition

Correlation is a statistical measure that indicates the extent to which two or more variables fluctuate
together. A positive correlation indicates the extent to which those variables increase or decrease in
parallel; a negative correlation indicates the extent to which one variable increases as the other
decreases.

When the fluctuation of one variable reliably predicts a similar fluctuation in another variable, there’s
often a tendency to think that means that the change in one causes the change in the other. However,
correlation does not imply causation. There may be an unknown factor that influences both variables
similarly.

Correlation is a statistical technique that can show whether and how strongly pairs of variables are
related. Although this correlation is fairly obvious your data may contain unsuspected correlations. You
may also suspect there are correlations, but don't know which are the strongest. An intelligent
correlation analysis can lead to a greater understanding of your data.

 Correlation is Positive or direct when the values increase together, and

 Correlation is Negative when one value decreases as the other
increases, and so called inverse or contrary correlation.

a b c d e

If the points plotted were all on a straight line we would have perfect correlation, but it could be
positive or negative as shown in the diagrams above,
a. Strong positive correlation between x and y. The points lie close to a straight line with y increasing
as x increases.
b. Weak, positive correlation between x and y. The trend shown is that y increases as x increases but
the points are not close to a straight line
c. No correlation between x and y; the points are distributed randomly on the graph.
d. Weak, negative correlation between x and y. The trend shown is that y decreases as x
increases but the points do not lie close to a straight line
e. Strong, negative correlation. The points lie close to a straight line, with y decreasing
as x increases
Correlation can have a value:
3. 1 is a perfect positive correlation
4. 0 is no correlation (the values don't seem linked at all)
5. -1 is a perfect negative correlation

43
The value shows how good the correlation is (not how steep the line is), and if it is positive or negative.
Usually, in statistics, there are three types of correlations: Pearson correlation, Kendall rank correlation
and Spearman correlation.

Assumption of Correlation

Employing of correlation rely on some underlying assumptions. The variables are assumed to be
independent, assume that they have been randomly selected from the population; the two variables
are normal distribution; association of data is homoscedastic (homogeneous), homoscedastic data
have the same standard deviation in different groups where data are heteroscedastic have different
standard deviations in different groups and assumes that the relationship between the two variables is
linear. The correlation coefficient is not satisfactory and difficult to interpret the associations between
the variables in case if data have outliers.

An inspection of a scatterplot can give an impression of whether two variables are related and the
direction of their relationship. But it alone is not sufficient to determine whether there is an
association between two variables. The relationship depicted in the scatterplot needs to be described
qualitatively. Descriptive statistics that express the degree of relation between two variables are called
correlation coefficients. A commonly employed correlation coefficient are Pearson correlation, Kendall
rank correlation and Spearman correlation.

Correlation used to examine the presence of a linear relationship between two variables providing
certain assumptions about the data are satisfied. The results of the analysis, however, need to be
interpreted with care, particularly when looking for a causal relationship.

Bivariate Correlation
Bivariate correlation is a measure of the relationship between the two variables; it measures the
strength and direction of their relationship, the strength can range from absolute value 1 to 0. The
stronger the relationship, the closer the value is to 1. Direction of The relationship can be positive
(direct) or negative (inverse or contrary); correlation generally describes the effect that two or more
phenomena occur together and therefore they are linked For example, the positive relationship of .71
can represent positive correlation between the statistics degrees and the science degrees. The student
who has high degree in statistics has also high degree in science and vice versa.

The Pearson correlation coefficient is given by the following equation:

Where 𝑥 is the mean of variable 𝑥 values, and 𝑦 is the mean of variable 𝑦 values.

Example – Correlation of statistics and science tests

44
A study is conducted involving 10 students to investigate the association between statistics and
science tests. The question arises here; is there a relationship between the degrees gained by the 10
students in statistics and science tests?

Table (2.1) Student degree in Statistic and science

Students 1 2 3 4 5 6 7 8 9 10
Statistics 20 23 8 29 14 12 11 20 17 18
Science 20 25 11 24 23 16 12 21 22 26

Notes: the marks out of 30

Suppose that (x) denotes for statistics degrees and ( y) for science degree
Calculating the mean (x , y) ;

Where the mean of statistics degrees x = 17.3 and the mean of science degrees y = 20 Table Calculating

the equation parameters

Statistics Science
y y (x  x)( y  y)
20 20 2.7 7.29 0 0 0
23 25 5.7 32.49 5 25 28
8 11 -9.3 86.49 -9 81 83
29 24 11.7 136.89 4 16 46
14 23 -3.3 10.89 3 9 -9.9
12 16 -5.3 28.09 -4 16 21.2
11 12 -6.3 39.69 -8 64 50.4
21 21 3.7 13.69 1 1 3.7
17 22 -0.3 0.09 2 4 -0.6
18 26 0.7 0.49 6 36 4.2
173 200 0 356.1 0 252 228

Other solution
Also; the Pearson correlation coefficient
is given by the following equation:

45
Pearson Correlation coefficient r = 0.761 exactly the same output of the first equation.

The calculation shows a strong positive correlation (0.761) between the student's statistics and science
degrees. This means that as degrees of statistics increases the degrees of science increase also.
Generally the student who has a high degree in statistics has high degree in science and vice versa.

Partial Correlation

The Partial Correlations procedure computes partial correlation coefficients that describe the linear
relationship between two variables while controlling for the effects of one or more

additional variables. Correlations are measures of linear association. Two variables can be perfectly
related, but if the relationship is not linear, a correlation coefficient is not an appropriate statistic for
measuring their association.

Partial correlation is the correlation between two variables after removing the effect of one or more
46
additional variables. Suppose we want to find the correlation between y and x
controlling by W . This is called the partial correlation and its symbol is rYX .W . This command is
specifically for the case of one additional variable. In this case, the partial correlation can be computed
based on standard correlations between the three variables as follows:

r . Stands for the correlation between x and y controlling by W .

As with the standard correlation coefficient, a value of +1 indicates a perfect positive linear
relationship, a value of -1 indicates a perfect negative linear relationship, and a value of 0 indicates no
linear relationship

Correlation Coefficients Pearson, Kendall and Spearman

Correlation is a Bivariate analysis that measures the strengths of association between two variables.
In statistics, the value of the correlation coefficient varies between +1 and -1. When the value of the
correlation coefficient lies around ± 1, then it is said to be a perfect degree of association between
the two variables. As the correlation coefficient value goes towards 0, the relationship between the
two variables will be weaker. Usually, in statistics, we measure three types of correlations: Pearson
correlation, Kendall rank correlation and Spearman correlation.
Pearson 𝑟r correlation: Pearson correlation is widely used in statistics to measure the degree of the
relationship between linear related variables. For example, in the stock market, if we want to measure
how two commodities are related to each other, Pearson correlation is used to measure the degree of
relationship between the two commodities. The following formula is used to calculate the Pearson
correlation coefficient r

Kendall's Tau rank correlation: Kendall rank correlation is a non-parametric test that measures the
strength of dependence between two variables. If we consider two samples, x and y , where each
sample size is n, we know that the total number of pairings with x y is n (n- 1)/2.

The following formula is used to calculate the value of Kendall rank correlation:

Where:
𝜏 = Kendall rank correlation coefficient
47
𝑛𝑐 = number of concordant (Ordered in the same way).
𝑛𝑑= Number of discordant (Ordered differently).

Kendall’s Tau Basic Concepts

Definition 1: Let x1, …, xn be a sample for random variable x and let y1, …, yn be a sample for random
variable y of the same size n. There are C(n, 2) possible ways of selecting distinct pairs (xi, yi) and (xj,
yj). For any such assignment of pairs, define each pair as concordant, discordant or neither as follows:
xi > xj and yi > yj) or (xi < xj and yi < yj)
xi > xj and yi < yj) or (xi < xj and yi > yj)
xi = xj or yi = yj (i.e. ties are not counted).

Observation: To facilitate the calculation of C – D it is best to first put all the x data elements in
ascending order. If x and y are perfectly positively correlated, then all the values of y would be in
ascending order too, and so if there are no ties then C = C (n, 2) and τ = 1.
Otherwise, there will be some inversions. For each i, count the number of j > i for which xj < xi. This
sum is D. If x and y are perfectly negatively correlated, then all the values of y would be in descending
order, and so if there are no ties then D = C (n, 2) and τ = -1.
An example of calculating Kendall's Tau correlation
To calculate a Kendall's Tau correlation coefficient on same data without any ties we use the following
data:

Students 1 2 3 4 5 6 7 8 9 10
Statistics 20 23 8 29 14 12 11 20 17 18
Science 20 25 11 24 23 16 12 21 22 26

Table Set rank to the data

data Arranged Rank

statistics science Rank Rank Rank Rank
(degree) (degree) (statistics) (science) (science) (statistics)
20 20 4 7 1 5
23 25 2 2 2 2
8 11 10 10 3 1
29 24 1 3 4 7
14 23 7 4 5 6
12 16 8 8 6 3
11 12 9 9 7 4
21 21 3 6 8 8
17 22 6 5 9 9
18 26 5 1 10 10

Continued Table (2.4) Calculating the Number of Concordant C and Discordant (D)

48
 D C
1 --
1 2 D --
2 3 D D --
3 4 C C C --
1 3 5 D C C C --
3 2 6 D D C C D --
3 3 7 C D D C C D --
7 8 C C C C C C C --
8 9 C C C C C C C C --
9 10 C C C C C C C C C --
1 2 3 4 5 6 7 8 9 10
10 35 Total of (D) and ( C )

Kendall's Tau coefficient 𝜏 = 0.556; this indicates a moderate positive relationship between the ranks
individuals obtained in the statistics and science exam. This means the higher you ranked in statistics,
the higher you ranked in science also, and vice versa.
Calculating Kendall's Tau manually can be very tedious without a computer and is rarely done without
a computer. Large dataset make it almost impossible to do manually by hand.

Spearman rank correlation: Spearman rank correlation is a non-parametric test that is used to
measure the degree of association between two variables. It was developed by Spearman, thus it is
called the Spearman rank correlation. Spearman rank correlation test does not assume any
assumptions about the distribution of the data and is the appropriate correlation analysis when the
variables are measured on a scale that is at least ordinal.
The following formula is used to calculate the Spearman rank correlation coefficient:

Where: 𝜌 = Spearman rank correlation coefficient di= the difference between the ranks of
corresponding values Xi and Yi n= number of value in each data set.
The Spearman correlation coefficient,, can take values from +1 to -1. A 𝜌 of +1 indicates a perfect
association of ranks, a 𝜌 of zero indicates no association between ranks and a 𝜌 of -1 indicates a
perfect negative association of ranks. The closer 𝜌 to zero, the weaker the association between the
ranks.

An example of calculating Spearman's correlation

To calculate a Spearman rank-order correlation coefficient on data without any ties use the following

49
data:
Students 1 2 3 4 5 6 7 8 9 10
Statistics 20 23 8 29 14 12 11 20 17 18
Science 20 25 11 24 23 16 12 21 22 26

Table (2.5) Calculating the Parameters of Spearman rank Equation:

statistics science Rank Rank
(degree) (degree) (statistics) (science) |d d2
|
20 20 4 7 3 9
23 25 2 2 0 0
8 11 10 10 0 0
29 24 1 3 2 4
14 23 7 4 3 9
12 16 8 8 0 0
11 12 9 9 0 0
21 21 3 6 3 9
17 22 6 5 1 1
18 26 5 1 4 16

Where d = absolute difference between ranks and d2 = difference squared. Then calculate the following:

Hence, we have a = 0.71; this indicates a strong positive relationship between the ranks individuals
obtained in the statistics and science exam. This means the higher you ranked in statistics, the higher
you ranked in science also, and vice versa.
So; the Pearson r correlation coefficient = 0.761 and Spearman's correlation = 0.71 for the same data
which means that correlation coefficients for both techniques are approximately equal.
Exercises
Study is conducted involving 14 infants to investigate the association between gestational age at birth,
measured in weeks, and birth weight, measured in grams.

Study is conducted involving 14 infants to investigate the association between gestational age at birth,
measured in weeks, and birth weight, measured in grams.

Infant No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Gestationa
34.7 36 29.3 40.1 35.7 42.4 40.3 37.3 40.9 38.3 38.5 41.4 39.7 39.7
l
age
Birth
189 203 144 283 309 382 326 269 328 292 343 365 368 334
Weigh
5 0 0 5 0 7 0 0 5 0 0 7 5 5
t
50
Applying the proper method; Estimate the association between gestational age and infant
birth weight.

Regression Analysis
Definition
Regression analysis is one of the most commonly used statistical techniques in social and behavioral
sciences as well as in physical sciences which involves identifying and evaluating the relationship
between a dependent variable and one or more independent variables, which are also called predictor
or explanatory variables. It is particularly useful for assess and adjusting for confounding. Model of the
relationship is hypothesized and estimates of the parameter values are used to develop an estimated
regression equation. Various tests are then employed to determine if the model is satisfactory. If the
model is deemed satisfactory, the estimated regression equation can be used to predict the value of
the dependent variable given values for the independent variables.

Linear regression explores relationships that can be readily described by straight lines or their
generalization to many dimensions. A surprisingly large number of problems can be solved by linear
regression, and even more by means of transformation of the original variables that result in linear
relationships among the transformed variables.

When there is a single continuous dependent variable and a single independent variable, the analysis is
called a simple linear regression analysis. This analysis assumes that there is a linear association
between the two variables. Multiple regression is to learn more about the relationship between
several independent or predictor variables and a dependent or criterion variable.

Independent variables are characteristics that can be measured directly; these variables are also called
predictor or explanatory variables used to predict or to explain the behavior of the dependent variable.
Dependent variable is a characteristic whose value depends on the values of independent variables.
Reliability and Validity:
• Does the model make intuitive sense? Is the model easy to understand and interpret?
• Are all coefficients statistically significant? (p-values less than .05)
• Are the signs associated with the coefficients as expected?
• Does the model predict values that are reasonably close to the actual values

Objectives of Regression Analysis

Regression analysis used to explain variability in dependent variable by means of one or more of
independent or control variables and to analyze relationships among variables to answer; the question
of how much dependent variable changes with changes in each of the independent's variables, and to
forecast or predict the value of dependent variable based on the values of the independent's variables.
The primary objective of regression is to develop a linear relationship between a response variable
and explanatory variables for the purposes of prediction, assumes that a functional linear relationship
exists, and alternative approaches (functional regression) are superior.

Assumption of Regression Analysis

The regression model is based on the following assumptions.

51
 The relationship between independent variable and dependent is linear.
 The expected value of the error term is zero
 The variance of the error term is constant for all the values of the independent variable, the
assumption of homoscedasticity.
 There is no autocorrelation.
 The independent variable is uncorrelated with the error term.
 The error term is normally distributed.
 On an average difference between the observed value (yi) and the predicted value (ˆyi) is zero.
 On an average the estimated values of errors and values of independent variables are not related
to each other.
 The squared differences between the observed value and the predicted value are similar.
 There is some variation in independent variable. If there are more than one variable in the
equation, then two variables should not be perfectly correlated.

Intercept or Constant
 Intercept is the point at which the regression intercepts y-axis.
 Intercept provides a measure about the mean of dependent variable when slope(s) are zero.
 If slope(s) are not zero then intercept is equal to the mean of dependent variable minus slope ×
mean of independent variable

Slope
 Change is dependent variable as we change independent variable.
 Zero Slope means that independent variable does not have any influence on dependent
variable.
 For a linear model, slope is not equal to elasticity. That is because; elasticity is percent change
in dependent variable, as a result one percent change in independent variable.

Simple Regression Model

Simple linear regression is a statistical method that allows us to summarize and study relationships
between two continuous (quantitative) variables. In a cause and effect relationship, the independent
variable is the cause, and the dependent variable is the effect. Least squares linear regression is a
method for predicting the value of a dependent variable y, based on the value of an independent
variable x.
 One variable, denoted (x), is regarded as the predictor, explanatory, or independent variable.
 The other variable, denoted (y), is regarded as the response, outcome, or dependent variable.

Mathematically, the regression model is represented by the following equation:

52
Example – linear Regression of patient's age and their blood pressure

A study is conducted involving 10 patients to investigate the relationship and effects of patient's age
and their blood pressure.
Table (3.1) calculating the linear regression of patient's age and blood pressure

53
Then substitute the regression coefficient into the regression model 𝑬𝒔𝒕𝒊𝒎𝒂𝒕𝒆𝒅 𝒃𝒍𝒐𝒐𝒅 𝒑𝒓𝒆𝒔𝒔𝒖𝒓𝒆
(Ŷ) = 85.026 + 1.140 𝑎𝑔𝑒
Interpretation of the equation;
Constant (intercept) value 𝛽0 = 85.026 indicates that blood pressure at age zero.
Regression coefficient 𝛽1 = 1.140 indicates that as age increase by one year the blood pressure
increase by 1.140
Table (3.2) Applying the value of age to the regression Model to calculate the estimated blood
pressure (Ŷ) coefficient of determination (R2) as follows:

54
Multiple Regressions Model
Multiple regression is an extension of simple linear regression. It is used when we want to predict the
value of a dependent variable (target or criterion variable) based on the value of two or more
independent variables (predictor or explanatory variables). Multiple regression allows you to
determine the overall fit (variance explained) of the model and the relative contribution of each of the
predictors to the total variance explained. For example, you might want to know how much of the
variation in exam performance can be explained by revision time and lecture attendance "as a whole",
but also the "relative contribution" of each independent variable in explaining the variance.

Mathematically, the multiple regression model is represented by the following equation: 𝒀=𝜷𝟎 ± 𝜷𝒊
𝑿𝒊…………± 𝜷𝒏 𝑿𝒏 ± 𝒖

55
Example – Multiple Regression of students exam performance, revision time and lecture attendance
A study is conducted involving 10 students to investigate the relationship and affects of revision time
and lecture attendance on exam performance.
Table (3.4) Students exam performance, revision time and lecture attendance
Obs 1 2 3 4 5 6 7 8 9 10
Y 40 44 46 48 52 58 60 68 74 80
X1 6 10 12 14 16 18 22 24 26 32
X2 4 4 5 7 9 12 14 20 21 24

Stands for
(Y) Exam performance
(X1) Revision time
(X2) Lecture attendance.
Table Calculating the coefficient of regression

56
57
We can say that 99.17% of the variation in the exam performance variable is explained by revision time
and lecture attendance variables.
Adjusted R2
The adjusted R Square value is adjusted for the number of variables included in the regression
equation. This is used to estimate the expected shrinkage in R Square that would not generalize to the
population because our solution is over-fitted to the data set by including too many independent
variables. If the adjusted R Square value is much lower than the R Square value, it is an indication that
our regression equation may be over-fitted to the sample, and of limited generalize ability.

𝑨𝒅𝒋𝑹𝟐=𝟏− 𝒏−𝟏𝒏−𝒌∗(𝟏−𝑹𝟐)=𝟏− 𝟗𝟕∗(𝟏−𝟎.𝟗𝟗𝟏𝟕)=𝟎.𝟗𝟖𝟗=𝟗𝟖.𝟗%

For the mentions example, R Square = 0.9917 and the Adjusted R Square = 0.989. These values are very
close, anticipating minimal shrinkage based on this indicator.

Exercises
A study examined the heat generated during the hardening of Portland cements, which was assumed
to be a function of the chemical composition, the following variables were measured, where
x1 : amount of tricalcium aluminate x2 : amount of tricalcium silicate
x3 : amount of tetracalcium alumino ferrite x4 : amount of dicalcium silicate
Y : heat evolved in calories per gram of cement.

Investigate the relationship and affects of tricalcium aluminate, tricalcium silicate, tetracalcium
alumino ferrite and dicalcium silicate on heat evolved in calories per gram of cement.

58
 BIJU PATNAIK INSTITUTE OF IT & MANAGEMENT STUDIES, BHUBANESWAR
Module- II
Prepared By Mr. A.P. Nanda, Associate Prof. (OM)
Linear Programming

Introduction: Linear Programming is a special and versatile technique which can be applied to a
variety of management problems viz. Advertising, Distribution, Investment, Production, Refinery
Operations, and Transportation analysis. The linear programming is useful not only in industry
and business but also in non-profit sectors such as Education, Government, Hospital, and
Libraries. The linear programming method is applicable in problems characterized by the
presence of decision variables. The objective function and the constraints can be expressed as
linear functions of the decision variables. The decision variables represent quantities that are, in
some sense, controllable inputs to the system being modeled.

An objective function represents some principal objective criterion or goal that measures the
effectiveness of the system such as maximizing profits or productivity, or minimizing cost or
consumption. There is always some practical limitation on the availability of resources viz. man,
material, machine, or time for the system. These constraints are expressed as linear equations
involving the decision variables. Solving a linear programming problem means determining
actual values of the decision variables that optimize the objective function subject to the
limitation imposed by the constraints.

The main important feature of linear programming model is the presence of linearity in the
problem. The use of linear programming model arises in a wide variety of applications. Some
model may not be strictly linear, but can be made linear by applying appropriate mathematical
transformations. Still some applications are not at all linear, but can be effectively
approximated by linear models. The ease with which linear programming models can usually be
solved makes an attractive means of dealing with otherwise intractable nonlinear models.

Linear Programming Problem Formulation

The linear programming problem formulation is illustrated through a product mix problem. The
product mix problem occurs in an industry where it is possible to manufacture a variety of

59
 products. A product has a certain margin of profit per unit, and uses a common pool of limited
resources. In this case the linear programming technique identifies the products combination
which will maximize the profit subject to the availability of limited resource constraints.

Example

Suppose an industry is manufacturing two types of products P1 and P2. The profits per Kg
of the two products are Rs.30 and Rs.40 respectively. These two products require
processing in three types of machines. The following table shows the available machine
hours per day and the time

required on each machine to produce one Kg of P1 and P2. Formulate the problem in the
form of linear programming model.

Profit/Kg P1 P2 Total available Machine

Rs.30 Rs.40 hours/day
Machine 1 3 2 600
Machine 2 3 5 800
Machine 3 5 6 1100

Solution:

The procedure for linear programming problem

formulation is as follows: Introduce the decision variable as

follows:
Let x1 = amount of
P1 x2 = amount
of P2

In order to maximize profits, we

establish the objective function

as 30x1 + 40x2

Since one Kg of P1 requires 3 hours of processing time in machine 1 while the

corresponding requirement of P2 is 2 hours. So, the first constraint can be expressed
as

60
 3x1 + 2x2 ≤ 600
Similarly, corresponding to machine 2 and 3 the constraints are

3x1 + 5x2 ≤ 800

5x1 + 6x2 ≤ 1100
In addition to the above there is no negative production, which may be

represented algebraically as x1 ≥ 0 ; x2 ≥ 0

Thus, the product mix problem in the linear programming model is as

follows:

Maximize
30x1 + 40x2

Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
x1≥ 0, x2 ≥ 0

Formulation with Different Types of Constraints

The constraints in the previous example 2.1 are of “less than or equal to” type. In this
section we are going to discuss the linear programming problem with different constraints,
which is illustrated in the following Example 2.2.

Example

A company owns two flour mills namely A and B, which have different production
capacities for high, medium and low quality flour. The company has entered a contract to
supply flour to a firm every month with at least 8, 12 and 24 quintals of high, medium and
low quality respectively. It costs the company Rs.2000 and Rs.1500 per day to run mill A
and B respectively. On a day, Mill A produces 6, 2 and 4 quintals of high, medium and low
quality flour, Mill B produces 2, 4 and 12 quintals of high, medium and low quality flour
respectively. How many days per month should each mill be operated in order to meet
the contract order most economically.
Solution:

Let us define x1 and x2 are the mills A and B. Here the objective is to minimize the

61
 cost of the machine runs and to satisfy the contract order. The linear programming
problem is given by
Minimize
2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24

x1 ≥ 0, x2 ≥ 0

Graphical Analysis of Linear Programming

This section shows how a two-variable linear programming problem is solved

graphically, which is illustrated as follows:

Example

Consider the product mix problem discussed in

section 2.2 Maximize

30x1 + 40x2

Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
x1≥ 0, x2 ≥ 0

From the first constraints 3x1 + 2x2 ≤ 600, draw the line 3x1 + 2x2 = 600 which passes through
the point (200, 0) and (0, 300). This is shown in the following graph as line 1.

62
 Three closed half planes and Feasible Region

Half Plane - A linear inequality in two variables is called as a half plane. Boundary - The

corresponding equality (line) is called as the boundary of the half plane. Close Half Plane – Half

plane with its boundary is called as a closed half plane.

In this case we must decide in which side of the line 3x 1 + 2x2 = 600 the half plane is located.

63
 The easiest way to solve the inequality for x2 is 3x1 ≤ 600 – 2x2

And for the fixed x1, the coordinates satisfy this inequality are smaller than the corresponding
ordinate on the line and thus the inequality is satisfied for all the points below the line 1.

Similarly, we have to determine the closed half planes for the inequalities 3x 1 + 5x2 ≤ 800
and 5x1 + 6x2 ≤ 1100 (line 2 and line 3 in the graph). Since all the three constraints must
be satisfied simultaneously we have consider the intersection of these three closed half
planes. The complete intersection of these three closed half planes is shown in the above
graph as ABCD. The region ABCD is called the feasible region, which is shaded in the graph.

Feasible Solution:
Any non-negative value of x1, x2 that is x1 ≥ 0 and x2 ≥ 0 is known as feasible solution of the
linear programming problem if it satisfies all the existing constraints.

Feasible Region:

The collection of all the feasible solution is called as the feasible region.

Example
In the previous example we discussed about the less than or equal to type of linear
programming problem, i.e. maximization problem. Now consider a minimization (i.e. greater
than or equal to type) linear programming problem formulated in Example 2.2.

Minimize
2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24

x1 ≥ 0, x2 ≥ 0

The three lines 6x1 + 2x2 = 8, 2x1 + 4x2 = 12, and 4x1 + 12x2 = 24 passes through the point
(1.3,0) (0,4), (6,0) (0,3) and (6,0) (0,2). The feasible region for this problem is shown in the
following Graph
64
 2. In this problem the constraints are of greater than or equal to type of feasible region, which is
bounded on one side only.

In this section we are going to describe linear programming graphical solution for both the
maximization and minimization problems, discussed in Example 2.3 and Example 2.4.

Example

Consider the maximization problem described in

Example 2.3. Maximize

30x1 + 40x2

Subject to:
3x1 + 2x2 ≤ 600
3x1 + 5x2 ≤ 800
5x1 + 6x2 ≤ 1100
x1 ≥ 0, x2 ≥ 0

M = 30x1 +40x2

The feasible region identified in the Example 2.3 is a convex polygon, which is illustrated
in the following Graph 3. The extreme point of this convex region are A, B, C, D and E.

Graphical Linear Programming Solution

65
 In this problem the objective function is 30x1 + 40x2. Let be M is a parameter, the graph 30x1 +
40x2 = M is a group of parallel lines with slope – 30/40. Some of these lines intersects the feasible
region and contains many feasible solutions, whereas the other lines miss and contain no feasible
solution. In order to maximize the objective function, we find the line of this family that intersects
the feasible region and is farthest out from the origin. Note that the farthest is the line from the
origin the greater will be the value of M.

Observe that the line 30x1 + 40x2 = M passes through the point D, which is the intersection of
the lines 3x1 + 5x2 = 800 and 5x1 + 6x2 = 1100 and has the coordinates x1 = 170 and x2 = 40.
Since D is the only feasible solution on this line the solution is unique.
The value of M is 6700, which is the objective function maximum value. The
optimum value variables are x1 = 170 and X2 = 40.
66
The following Table 1 shows the calculation of maximum value of the objective function.

Extreme Point Coordinates Objective Function

X1 X2 30x1 + 40x2
A X1 = 0 X2 = 0 0
B X1 = 0 X2 = 160 6400
C X1 = 110 X2 = 70 6100
D X1 = 170 X2 = 40 6700
E X1 = 200 X2 = 0 6000

Table 1: Shows the objective function Maximum value calculation

Example

Consider the minimization problem described in

Example 2.4. Minimize

2000x1 + 1500x2

Subject to:
6x1 + 2x2 ≥ 8
2x1 + 4x2 ≥ 12
4x1 + 12x2 ≥ 24
x1≥ 0, x2 ≥ 0

The feasible region for this problem is illustrated in the following Graph 4. Here each of the half
planes lies above its boundary. In this case the feasible region is infinite. In this case, we are
concerned with the minimization; also it is not possible to determine the maximum value. As in
the previous example let us introduce a parameter M in the objective function i.e. 2000x 1 +
1500x2 = M and draw the lines for different values of M, which is shown in the following Table 2.

67
 Graph 4: Graphical Linear Programming Solution
‘

Extreme Coordinates Objective Function

Point X1 X2 2000x1 + 1500x2
A X1 = 0 X2 = 4 6000
B X1 = 0.5 X2= 2.75 5125
C X1 = 6 X2 = 0 12000

Table 2: Shows the objective function Minimum value computation

The minimum value is 5125 at the extreme point B, which is the value of the
M (objective function). The optimum values variables are X1 = 0.5 and X2 =
2.75.
Multiple Optimal Solutions

When the objective function passed through only the extreme point located at the
intersection of two half planes, then the linear programming problem possess unique
solutions. The previous examples i.e. Example 2.5 and Example 2.6 are of this types (which
possessed unique solutions).

When the objective function coincides with one of the half planes generated by the

68
 constraints in the problem, will possess multiple optimal solutions. In this section we are
going to discuss about the multiple optimal solutions of linear programming problem with
the help of the following Example 2.7.
Example

A company purchasing scrap material has two types of scarp materials available. The first
type has 30% of material X, 20% of material Y and 50% of material Z by weight. The second
type has 40% of material X, 10% of material Y and 30% of material Z. The costs of the two
scraps are Rs.120 and Rs.160 per kg respectively. The company requires at least 240 kg of
material X, 100 kg of material Y and 290 kg of material Z. Find the optimum quantities of
the two scraps to be purchased so that the company requirements of the three materials
are satisfied at a minimum cost.
Solution

First we have to formulate the linear programming model. Let us introduce the decision
variables x1 and x2 denoting the amount of scrap material to be purchased. Here the
objective is to minimize the purchasing cost. So, the objective function here is
Minimize
120x1 + 160x2
Subject to:
0.3x1 + 0.4x2 ≥ 240
0.2x1 + 0.1x2 ≥ 100
0.5x1 + 0.3x2 ≥ 290
x1 ≥ 0; x2 ≥ 0

Multiply by 10 both sides of the inequalities, then the problem becomes

Minimize 120x1 + 160x2

Subject to:
3x1 + 4x2 ≥ 2400
2x1 + x2 ≥ 1000
5x1 + 3x2 ≥ 2900

x1 ≥ 0; x2 ≥ 0

Let us introduce parameter M in the objective function i.e. 120x 1 + 160x2 = M. Then

69
 we have to determine the different values for M, which is shown in the following

Table 3.

Extreme Coordinates Objective Function

Point X1 X2 120x1 + 160x2
A X1 = 0 X2 = 1000 160000
B X1 = 150 X2 = 740 136400
C X1 = 400 X2 = 300 96000
D X1=800 X2=0 96000

Table 3: Shows the calculation of Minimum objective function value

Note that there are two minimum value for the objective function (M=96000). The
feasible region and the multiple solutions are indicated in the following Graph 5.

70
71
 The extreme points are A, B, C, and D. One of the objective functions 120x1 + 160x2 = M family
coincides with the line CD at the point C with value M=96000, and the optimum value variables
are x1 = 400, and x2 = 300. And at the point D with value M=96000, and the optimum value
variables are x1 = 800, and x2 = 0.
Thus, every point on the line CD minimizes objective function value and the problem
contains multiple optimal solutions.

Unbounded Solution
When the feasible region is unbounded, a maximization problem may don’t have optimal solution,
since the values of the decision variables may be increased arbitrarily. This is illustrated with the
help of the following problem.
Maximize
3x1 + x2

Subject to:
x1 + x2 ≥ 6
-x1 + x2 ≤ 6
-x1 + 2x2 ≥ -6
and
x1, x2 ≥ 0

Graph 6 shows the unbounded feasible region and demonstrates that the objective function can be
made arbitrarily large by increasing the values of x1 and x2 within the unbounded feasible region. In
this case, there is no point (x1, x2) is optimal because there are always other feasible points for
which objective function is larger. Note that it is not the unbounded feasible region alone that
precludes an optimal solution. The minimization of the function subject to the constraints shown in
the Graph 6 would be solved at one the extreme point (A or B).

The unbounded solutions typically arise because some real constraints, which represent a practical
resource limitation, have been missed from the linear programming formulation. In such situation
the problem needs to be reformulated and re-solved.

72
 - x1 + x2 = 6

x1 + x2 =

-x1 + 2x2 = 6
X2

Graph 6: Unbounded Feasible Region

1 2 3 4 5 6 B X1

Infeasible Solution

A linear programming problem is said to be infeasible if no feasible solution of the problem exists.
This section describes infeasible solution of the linear programming problem with the help of the
following Example 2.8.

Example

Minimize
200x1 + 300x2

Subject to:
0.4x1 + 0.6x2 ≥ 240
0.2x1 + 0.2x2 ≤ 80

73
 0.4x1 + 0.3x2 ≥ 180
x1, x2 ≥ 0

On multiplying both sides of the inequalities by 10, we get

4x1 + 6x2 ≥ 2400

2x1 + 2x2 ≤ 800
4x1 + 3x2 ≥ 1800

700

A
600
4x1 + 3x2 = 1800

500

B
400
X2

300

200 F
2x1 + 2x2 = 800

100 4x1 + 6x2 = 2400

74
 0
D
C E
100 200 300 400 500 600 X1

Graph 7: Infeasible Solution

The region right of the boundary AFE includes all the solutions which satisfy the first (4x1 +
6x2
≥ 2400) and the third (4x1 + 3x2 ≥ 1800) constraints. The region left of the BC contains all
solutions which satisfy the second constraint (2x1 + 2x2 ≤ 800)

Hence, there is no solution satisfying all the three constraints (first, second, and third).
Thus, the linear problem is infeasible. This is illustrated in the above Graph 7

75
 Simplex Methods

Introduction
The Linear Programming with two variables can be solved graphically. The graphical method of
solving linear programming problem is of limited application in the business problems as the
number of variables is substantially large. If the linear programming problem has larger
number of variables, the suitable method for solving is Simplex Method. The simplex method is
an iterative process, through which it reaches ultimately to the minimum or maximum value of
the objective function.
The simplex method also helps the decision maker/manager to identify the following:

 Redundant Constraints
 Multiple Solutions
 Unbounded Solution
 Infeasible Problem

Basics of Simplex Method

The basic of simplex method is explained with the following linear programming problem.

Example:

Maximize
60x1 + 70x2

Subject to:
2x1 + x2 ≤ 300
3x1 + 4x2 ≤ 509
4x1 + 7x2 ≤ 812

x1, x2 ≥ 0

Solution
First we introduce the
variables s3, s4, s5 ≥ 0

So that the constraints becomes equations,

thus 2x1 + x2 + s3 = 300

3x1 + 4x2 + s4 = 509

76
 4x1 + 7x2 + s5 =812

Corresponding to the three constraints, the variables s3, s4, s5 are called as slack variables.
Now, the system of equation has three equations and five variables.

There are two types of solutions they are basic and basic feasible, which are discussed as
follows:

Basic Solution
We may equate any two variables to zero in the above system of equations, and then the
system will have three variables. Thus, if this system of three equations with three variables is
solvable such a solution is called as basic solution.

For example suppose we take x1=0 and x2=0, the solution of the system with remaining three
variables is s3=300, s4=509 and s5=812, this is a basic solution and the variables s3, s4, and s5
are known as basic variables where as the variables x1, x2 are known as non-basic variables.

The number of basic solution of a linear programming problem is depends on the presence of
the number of constraints and variables. For example if the number of constraints is m and
n n
the number of variables including the slack variables is n then there are at most Cn-m = Cm
basic solutions.

Basic Feasible Solution

A basic solution of a linear programming problem is called as basic feasible solutions if it is

feasible it means all the variables are non-negative. The solution s3=300, s4=509 and s5=812 is
a basic feasible solution.

The number of basic feasible solution of a linear programming problem is depends on the
presence of the number of constraints and variables. For example if the number of constraints
n
is m and the number of variables including the slack variables is n then there are at most Cn-m
= nCm basic feasible solutions.

Every basic feasible solution is an extreme point of the convex set of feasible solutions and
every extreme point is a basic feasible solution of the set of given constraints. It is impossible to
identify the extreme points geometrically if the problem has several variables but the extreme
points can be identified using basic feasible solutions. Since one the basic feasible solution will

77
 maximize or minimize the objective function, the searching of extreme points can be carry out
starting from one basic feasible solution to another.

The Simplex Method provides a systematic search so that the objective function increases in
the cases of maximization progressively until the basic feasible solution has been identified
where the objective function is maximized.

Simplex Method Computation

This section describes the computational aspect of simplex method. Consider the following
linear programming problem

Maximize
60x1 + 70x2

Subject to:
2x1 + x2 + s3= 300
3 x1 + 4 x2+ s4= 509
4 x1 + 7 x2+ s5 = 812
x1, x2, s3, s4 , s5 ≥ 0

The profit Z = 60x1 + 70x2 i.e. Maximize 60x1 + 70x2. The standard form can be
summarized in a compact table form as shown in table-1

In this problem the slack variables s3, s4, and s5 provide a basic feasible solution from which
the simplex computation starts. That is s3==300, s4=509 and s5=812. This result follows
because of the special structure of the columns associated with the slacks.

If z represents profit then z = 0 corresponding to this basic feasible solution. We represent by

CB the coefficient of the basic variables in the objective function and by XB the numerical
values of the basic variable.

So that the numerical values of the basic variables are: XB1=300, XB2=509, XB3=812. The
profit z = 60x1+70x2 can also expressed as z- 60x1-70x2=0. The simplex computation starts
with the first compact standard simplex table as given below:

78
 Table-1

CB Basic Cj 60 70 0 0 0
Variables XB x1 x2 s3 s4
s5
0 s3 300 2 1 1 0 0
0 s4 509 3 4 0 1 0
0 s5 812 4 7 0 0 1

Z -60 -70 0 0 0
In the objective function the coefficients of the variables are CB1=CB2=CB3=0. The top most
row of the Table 1 denotes the coefficient of the variables x 1, x2, s3, s4, s5 of the objective
function respectively. The column under x1 indicates the coefficient of x 1 in the three
equations respectively. Similarly the remaining column also formed.

On seeing the equation z = 60x1+70x2 we may observe that if either x1 or x2, which is
currently non-basic is included as a basic variable so that the profit will increase. Since the
coefficient of x2 is higher we choose x2 to be included as a basic variable in the next iteration.
An equivalent criterion of choosing a new basic variable can be obtained the last row of Table
1 i.e. corresponding to z.

Since the entry corresponding to x2 is smaller between the two negative values, x2 will be
included as a basic variable in the next iteration. However with three constraints there can be
only three basic variables.
Thus, by bringing x2 a basic variable one of the existing basic variables becomes non-basic.
The question here is How to identify this variable? The following statements give the solution
to this question.

Consider the first equation i.e. 2x1 + x2 + s3 =

300 From this equation
2x1+s3 = 300-x2
But, x1= 0. Hence, in order that s3 ≥ 0
300 - x2 ≥ 0
i.e. x2 ≤ 300
Similarly consider the second equation i.e. 3x1 + 4x2+ s4= 509
From this equation

79
 3x1+s4 = 509 - 4x2
But, x1 = 0. Hence, in order that s4 ≥ 0
509 - 4x2 ≥ 0
i.e. x2 ≤ 509/9

Similarly consider the third equation i.e. 4x1 + 7x2 + s5 = 812; From this
equation 4x1+s5 = 812 - 7x2
But, x1 = 0. Hence, in order that s5≥0
812 - 7x2 ≥ 0

i.e. x2 ≤ 812/7 Therefore the three equation lead

to x2≤300, x2≤509/9, x2≤812/7
Thus x2 = Min (x2≤300, x2≤509/9, x2≤812/7) it means x2=Min (x2≤300/1, x2≤509/9, x2≤812/7)
=116
Therefore x2 = 116

If x2 = 116, you may be note from the third equation 7x2+s5=812

i.e. s5 = 0
Thus, the variable s5 becomes non-basic in the next iteration. So that the revised values of the
other two basic variables are
S3 = 300 - x2 = 184
S4=509-4*116=45

Refer to Table 1, we obtain the elements of the next Table i.e. Table 2 using the following
rules:
1. We allocate the quantities which are negative in the z-row. Suppose if all the quantities
are positive, the inclusion of any non-basic variable will not increase the value of the
objective function. Hence the present solution maximizes the objective function. If there
are more than one negative values we choose the variable as a basic variable
corresponding to which the z value is least as this is likely to increase the more profit.
th
2. Let xj be the incoming basic variable and the corresponding elements of the j row column
be denoted by Y1j, Y2j and Y3j respectively. If the present values of the basic variables are
XB1, XB2 and XB3 respectively, then we can compute.
80
 Min [XB1/Y1j, XB2/Y2j, XB3/Y3j] for Y1j, Y2j, Y3j > 0.
Note that if any Yij ≤ 0, this need not be included in the comparison. If the minimum
occurs corresponding to XBr/Yrj then the rth basic variable will become non-basic in the
next iteration.
3. Using the following rules the Table 2 is computed from the Table 1.

 The revised basic variables are s3, s4 and x2. Accordingly, we make CB1=0, CB2=0
and CB3=70.
 As x2 is the incoming basic variable we make the coefficient of x2 one by dividing each
element of row-3 by 7. Thus the numerical value of the element corresponding to x1 is
4/7, corresponding to s5 is 1/7 in Table 2.

 The incoming basic variable should appear only in the third row. So we multiply the
Third - row of Table 2 by 1 and subtract it from the first-row of Table 1 element by
element. Thus the element corresponding to x2 in the first-row of Table 2 is 0.
Therefore the element corresponding to x1 is
2-1*4/7 = 10/7 and the element corresponding to s5 is 0 -1* 1/7 = -1/7

In this way we obtain the elements of the first and the second row in Table 2. In Table 2 the
numerical values can also be calculated in a similar way.
Table-2

CB Basic Cj 60 70 0 0 0
Variables XB x1 x2 s s4 s5
3
0 s3 184 10/7 0 1 0 -1/7
0 s4 45 5/7 0 0 1 -4/7
70 x2 116 4/7 1 0 0 1/7

Zj – Cj -140/7 0 0 0 70/7

Let CB1, CB2, Cb3 be the coefficients of the basic variables in the objective function. For
example in Table 2 CB1=0, CB2=0 and CB3=70. Suppose corresponding to a variable J, the
quantity Zj is defined as Zj = CB1, Y1+CB2, Y2j+CB3Y3j. Then the z-row can also be represented
as Zj - Cj.

81
 For example:
z1 - c1 = 10/7 * 0 + 5/7 * 0 + 70 * 4/7 - 60 = -140/7 z5 – c5 = -1/7 * 0 - 4/7 *0 + 1/7*70-0 = 70/7

1. Now we apply rule (1) to Table 2. Here the only negative zj - cj is z1-c1 = -140/7 Hence
x1 should become a basic variable at the next iteration
2. We compute the minimum of the ratio

184 , 45, 116 644 , 63 , 203

Min 10 5 4 = Min 5 = 63
7 7 7

This minimum occurs corresponding to s4, it becomes a non basic variable in next iteration.

3. Like Table 2, the Table 3 is computed using the rules (i), (ii), (iii) as described above.
Table-3

CB Basic Cj 60 70 0 0 0
Variables XB x1 x2 s3 s4 s5

0 s3 94 0 0 1 -2 1
60 x1 63 1 0 0 7/5 -4/5
70 x2 80 0 1 0 -4/5 3/5

zj-cj 0 0 0 28 -6

1. z5 – c5 < 0 should be made a basic variable in the next iteration.

2. Now compute the minimum ratios

94, 80
Min 1 3 = 94
5

Note: Since y25 = -4/5 < 0, the corresponding ratio is not taken for comparison. The variable
s3 becomes non basic in the next iteration.

3. From the Table 3, Table 4 is calculated following the usual steps.

Table-4
CB Basic Cj 60 70 0 0 0
Variables XB x1 x2 s s4 s5
3
0 s5 94 0 0 1 -2 1
82
 60 x1 691/5 1 0 4/5 -1/5 0
70 x2 118/5 0 1 -3/5 2/5 0

Z j - Cj 0 0 6 16 0

Note that zj – cj ≥ 0 for all j, so that the objective function can’t be improved any further.

Thus, the objective function is maximized for x1 = 691/5 and x2=118/5 and the maximum

value of the objective function is 9944.

Simplex Method with More Than Two Variables

An organization has three machine shops viz. A, B and C and it produces three product viz. X, Y
and Z using these three machine shops. Each product involves the operation of the machine
shops. The time available at the machine shops A, B and C are 100, 72 and 80 hours
respectively. The profit per unit of product X, Y and Z is $22, $6 and $2 respectively. The
following table shows the time required for each operation for unit amount of each product.
Determine an appropriate product mix so as to maximize the profit.

Machine
Products A B C Profit per unit
X 10 7 2 22
Y 2 3 4 6
Z 1 2 1 2
Hours available 100 72 80

Solution
First we have to develop linear programming formulation. The linear programming formulation
of the product mix problem is:

Maximize
22x1 + 6x2 + 2x3

Subject to:
83
 10 x1 + 2 x2 + x3 ≤ 100
7 x1 + 3 x2 + 2 x3 ≤ 72
2 x1 + 4 x2 + x3 ≤ 80
x1, x2, x3 ≥ 0

We introduce slack variables s4, s5 and s6 to make the inequalities equation. Thus, the problem
can be stated as
Maximize
22x1 + 6x2 + 2 x3

Subject to:
10 x1 + 2 x2 + x3 + s4 = 100
7 x1 + 3 x2 + 2 x3+ s5 = 72
2 x1 + 4 x2 + x3+ s6 = 80
x1, x2, x3, s4, s5, s6 ≥ 0
From the above equation the simplex Table 5 can be obtained in a straight forward manner.
Here the basic variables are s4, s5 and s6. Therefore CB1 = CB2 = CB3 = 0.

Table 5

CB Basic Cj 22 6 2 0 0 0
Variable XB x1 x2 x3 s4 s5 s6

0 s4 100 10 2 1 1 0 0
0 s5 72 7 3 2 0 1 0
0 s6 80 2 4 1 0 0 1

zj-cj -22 -6 -2 0 0 0

1. Z1- C1 = -22 is the smallest negative value. Hence x1 should be taken as a basic variable
in the next iteration.
2. Calculate the minimum of the ratios

Min 100 , 72 , 80 = 10
10 7 2

3. The variable s4 corresponding to which minimum occurs is made a non basic variable.

84
 4. From the Table 5, the Table 6 is calculated using the following rules:

a) The revised basic variables are x1, s5, s6. Accordingly we make CB1=22, CB2=0 and
CB3=0.
b) Since x1 is the incoming variable we make x1 coefficient one by dividing each element of
row 1 by 10. Thus the numerical value of the element corresponding to x2 is 2/10,
corresponding to x3 is 1/10, corresponding to s4 is 1/10, corresponding to s5 is 0/10 and
corresponding to s6 is 0/10 in Table 6.
c) The incoming basic variable should only appear in the first row. So we multiply first row of
Table 2 by 7 and subtract if from the second row of Table 1 element by element.
Thus,
The element corresponding to x1 in the second row of Table 6 is zero
The element corresponding to x2 is 3 – 7 * 2/10 = 16/10

By using this way we get the elements of the second and the third row in Table 6.

Similarly, the calculation of numerical values of basic variables in Table 6 is done.

Table-6

CB Basic Cj 22 6 2 0 0 0
Variable XB x1 x2 x3 s4 s5 s6

22 x1 10 1 2/10 1/10 1/10 0 0

0 s5 2 0 16/10 13/10 -7/10 1 0
0 s6 60 0 18/5 4/5 -1/5 0 1

zj - cj 0 -8/5 1/5 12/5 0 0

1. z2 - c2 = -8/5. So x2 becomes a basic variable in the next iteration.

2. Calculate the minimum of the ratios

10 , 7, 60 50 , 70 , 300
Min 2 16 18 = Min 16 18 = 70/16
10 10 5

85
 Hence the variable s5 will be a non basic variable in the next iteration.
3. From Table 6, the Table 7 is calculated using the rules (a), (b) and (c)
mentioned above.

Table-7

CB Basic Cj 22 6 2 0 0 0
Variable XB x1 x2 x3 s4 s5 s6

22 x1 73/8 1 0 -1/16 3/16 -1/8 0

6 x2 30/8 0 1 13/16 -7/16 5/8 0
0 s6 177/4 0 0 -17/8 11/8 -9/4 1

zj-cj 0 0 24/16 24/16 1 0

Note that all zj – cj ≥0, so that the solution is x1 = 73/8, x2 = 30/8 and s6 = 177/4 maximizes the
objective function.

The Maximum Profit is: 22*73/8 + 6*30/8 = 1606/8 + 180/8 = 1786/8 = 223.25

Two Phase and M-Method

In the last two section we discussed the simplex method was applied to linear programming
problems with less than or equal to (≤) type constraints. Thus, there we could introduce slack
variables which provide an initial basic feasible solution of the problem.

Generally, the linear programming problem can also be characterized by the presence of both
‘less than or equal to’ type or ‘greater than or equal to (≥)’ type constraints. In such case it is
not always possible to obtain an initial basic feasible solution using slack variables.

The greater than or equal to type of linear programming problem can be solved by using the
following methods:

1. Two Phase Method

2. M Method
In this section we will discuss these two methods.

Two Phase Method

86
 We discuss the Two Phase Method with the help of the following Example:
Example:

Minimize
12.5x1 + 14.5x2

Subject to:
x1 + x2 ≥ 2000
0.4x1 + 0.75x2 ≥ 1000
0.075x1 + 0.1x2 ≤ 200

x1, x2 ≥ 0

Solution
Minimize
12.5x1 + 14.5x2

Subject to:
x1 + x2 ≥ 2000
0.4x1 + 0.75x2 ≥ 1000
0.075x1 + 0.1x2 ≤ 200
x1, x2 ≥ 0

Here the objective function is to be minimized; the values of x1 and x2 which minimized this
objective function are also the values which maximize the revised objective function i.e.

Maximize
-12.5x1 – 14.5x2

We can multiply the second and the third constraints by 100 and 1000 respectively for the
convenience of calculation.
Thus, the revised linear programming problem is:
Maximize
-12.5x1 – 14.5x2
Subject to:

87
 x1 + x2 ≥ 2000
40x1 + 75x2 ≥ 100000
75x1 + 100x2 ≤ 200000
x1, x2 ≥ 0

Now we convert the two inequalities by introducing surplus variables s 3 and s4 respectively.
The third constraint is changed into an equation by introducing a slack variable s 5.

Thus, the linear programming problem becomes as

Maximize
-12.5x1 – 14.5x2 = -25/2x1 – 29/2x2

Subject to:
x1 + x2 -s3= 2000
40x1 + 75x2 - s4 = 100000
75x1 + 100x2 + s5 = 200000
x1, x2, s3, s4, s5 ≥ 0
Even though the surplus variables can convert greater than or equal to type constraints into
equations they are unable to provide initial basic variables to start the simplex method
calculation. So we may have to introduce two more additional variables a 6 and a7 called as
artificial variable to facilitate the calculation of an initial basic feasible solution.

In this method the calculation is carried out in two phases hence tow phase method.
Phase I
In this phase we will consider the following linear programming problem

Maximize

-a6 –a7
Subject to:
x1 + x2 -s3 +a6 = 2000
40x1 + 75x2 -s4 + a7 = 100000
75x1 + 100x2 +s5 = 200000

88
 x1, x2, s3, s4, s5, a6, a7 ≥ 0

The initial basic feasible solution of the problem is

a6 = 2000, a7=100000 and s5 = 200000.
As the minimum value of the objective function of the Phase I is zero at the end of the Phase I
calculation both a6 and a7 become zero.

CB Basic Cj 0 0 0 0 0 -1 -1
variables XB x1 x2 s3 s4 s5 a6 a7

-1 a6 2000 1 1 -1 0 0 1 0
-1 a 100000 40 75 0 -1 0 0 1
0 7 200000 75 100 0 0 1 0 0
s
5
zj - cj -41 -76 1 1 0 0 0

Here x2 becomes a basic variable and a7 becomes non basic variable in the next iteration. It
is no longer considered for re-entry in the table.
CB Basic Cj 0 0 0 0 0 -1
variables XB x1 x2 s3 s4 s5 a6

-1 a6 2000/3 7/15 0 -1 1/75 0 1

0 x2 4000/3 8/15 1 0 -1/75 0 0

0 s5 200000/3 65/3 0 0 4/3 1 0

zj - cj -1/15 0 1 -1/75 0 0

Then x1 becomes a basic variable and a6 becomes a non basic variable in the next iteration.
CB Basic Cj 0 0 0 0 0
variables XB x1 x2 s3 s 4 s5

0 x1 10000/7 1 0 -15/7 1/35 0

0 x2 4000/7 0 1 8/7 -1/35 0

0 s5 250000/7 0 0 325/7 16/21 1

zj-cj 0 0 0 0 0

89
 The calculation of Phase I end at this stage. Note that, both the artificial variable have been
removed and also found a basic feasible solution of the problem.
The basic feasible solution is:
x1 = 10000/7, x2 = 4000/2, s5 = 250000/7.

Phase II
The initial basic feasible solution obtained at the end of the Phase I calculation is used as the
initial basic feasible solution of the problem. In this Phase II calculation the original objective
function is introduced and the usual simplex procedure is applied to solve the linear
programming problem.

CB Basic Cj -25/2 -29/2 0 0 0

variables XB x1 x2 s3 s4 s5

-25/2 x1 10000/7 1 0 -15/7 1/35 0

-29/2 x2 4000/7 0 1 8/7 -1/35 0

0 s5 250000/7 0 0 325/7 5/7 1

zj - cj 0 0 143/14 2/35 0

In this Table 1 all Zj - Cj ≥ 0 the current solution maximizes the revised objective function.
Thus, the solution of the problem is:
x1 = 10000/7 = 1428 and x = 4000/7 = 571.4 and
The Minimum Value of the objective function is: 26135.3

M Method
In this method also we need artificial variables for determining the initial basic feasible
solution. The M method is explained in the following Example with the help of the previous
Example.
Example:

90
 Maximize
-12.5x1 – 14.5x2
Subject to:
x1 + x2 –s3 = 2000
40 x1 + 75 x2- s4 = 100000
75 x1 + 100 x2 + s5 = 200000
x1, x2, s3, s4, s5 ≥ 0.

Introduce the artificial variables a6 and a7 in order to provide basic feasible solution in the
second and third constraints. The objective function is revised using a large positive number
say M.
Thus, instead of the original problem, consider the following problem i.e.

Maximize:
-12.5x1 – 14.5x2 – M (a6 + a7)
Subject to:
x1 + x2 – s3 + a6 = 2000
40x1 + 75x2 - s4 +a7 = 100000
75x1 + 100x2 + s5 = 200000
x1, x2, s3, s4, s5, a6, a7 ≥ 0.

The coefficient of a6 and a7 are large negative number in the objective function. Since the
objective function is to be maximized in the optimum solution, the artificial variables will be
zero. Therefore, the basic variable of the optimum solution are variable other than the
artificial variables and hence is a basic feasible solution of the original problem.
The successive calculation of simplex tables is as follows:

91
 CB Basic Cj -12.5 -14.5 0 0 0 -M -M
variables XB x1 x2 s3 s4 s5 a6 a7

-M a6 2000 1 1 -1 0 0 1 0

-M a7 100000 40 75 0 -1 0 0 1

0 s5 200000 75 100 0 0 1 0 0
zj-cj -41M -76M M M 0 0 0
+12.5 +14.5

Since M is a large positive number, the coefficient of M in the zj – cj row would decide the
entering basic variable. As -76M < -41M, x2 becomes a basic variable in the next iteration
replacing a7. The artificial variable a7 can’t be re-entering as basic variable.

CB Basic Cj -12.5 -14.5 0 0 0 -M

variables XB x1 x2 s3 s4 s5 a6

-M a6 2000/3 7/15 0 -1 1/75 0 1

-14.5 x2 4000/3 8/15 1 0 -1/75 0 0

0 s5 200000/3 65/3 0 0 4/3 1 0

zj-cj -7/15M 0 M -M/75 0 0
+143/30 +29/150

Now x1 becomes a basic variable replacing a6. Like a7 the variable a6 also artificial variable
so it can’t be re-entering in the table.

92
 CB Basic Cj -12.5 -14.5 0 0 0
variables XB x1 x2 s3 s4 s5

-12.5 x1 10000/7 1 0 -15/7 1/35 0

-14.5 x2 4000/7 0 1 8/7 -1/35 0

0 s5 250000/7 0 0 325/7 16/21 1

zj-cj 0 0 143/14 2/35 0

Hence
The optimum solution of the problem is x1 = 10000/7, x2 = 4000/7 and The Minimum Value of
the Objective Function is: 26135.3

Multiple Solutions
The simplex method also helps in identifying multiple solutions of a linear programming
problem. This is explained with the help of the following Example:

Example:
Consider the following linear programming problem.

Maximize
2000x1 +
3000x2
Subject to:
6x1 + 9x2 ≤ 100
2x1 + x2 ≤ 20
x1, x2 ≥ 0.

Solution
Introduce the slack variables s3 and s4, so that the inequalities can be converted in to
equation as follows:
6x1 + 9x2 + s3 = 100
2x1 + x2 + s4 = 20
93
 x1, x2, s3, s4 ≥ 0.

The computation of simple procedure and tables are as follows:

CB Basic Cj 2000 3000 0 0

variables XB x1 x2 s3 s4

0 s3 100 6 9 1 0

0 s4 20 2 1 0 1

zj-cj -2000 -3000 0 0

CB Basic Cj 2000 3000 0 0

variables XB x1 x2 s3 s4

0 x2 100/9 2/3 1 1/9 0

0 s4 80/9 4/3 0 -1/9 1

zj-cj 0 0 3000/9 0

Here zj - cj ≥ 0 for all the variables so that we can’t improve the simplex table any more. Hence
it is optimum.
The optimum solution is x1 = 0, x2 = 100/9 and

The maximum value of the objective function is: 100000/3 = 33333.33.

However, the zj - cj value corresponding to the non basic variable x1 is also zero. This indicates
that there is more than one optimum solution for the problem exists.

In order to calculate the value of the alternate optimum solution we have to introduce x 1 as a

94
 basic variable replacing s4. The next table shows the computation of this.

CB Basic Cj 2000 3000 0 0

variables XB x1 x2 s3 s4

3000 x2 20/3 0 1 1/6 1/2

2000 x1 20/3 1 0 -1/12 3/4

zj-cj 0 0 1000/3 3000

Thus,
x1 = 20/3, x2 = 20/3 also maximize the objective function and
The Maximum value of the objective function is: 100000/3 = 33333.33

Thus, the problem has multiple solutions.

Unbounded Solution

In this section we will discuss how the simplex method is used to identify the unbounded
solution. This is explained with the help of the following Example.
Example:
Consider the following linear programming problem.

Maximize
5x1 + 4x2

Subject to:
x1 – x2 ≤ 8
x1 ≤ 7
x1, x2 ≥ 0.

Solution:

95
 Introduce the slack variables s3 and s4, so that the inequalities becomes as equation as
follows: x1 + s3 = 7
x1 – x2 + s4 = 8
x1, x2, s3, s4 ≥
0.

The calculation of simplex procedures and tables are as follows:

CB Basic Cj 5 4 0 0
variables XB x1 x2 s3 s4

0 s 7 1 0 1 0

0 3 8 1 -1 0 1

zj-cj -5 -4 0 0

96
 CB Basic Cj 5 4 0 0
variables XB x1 x2 s3 s4

5 x 7 1 0 1 0

0 1 1 0 -1 -1 1

s4

zj-cj 0 -4 5 0

Note that z2 - c2 < 0 which indicates x2 should be introduced as a basic variable in the next iteration.
However, both y12 ≤ 0, y22 ≤ 0
Thus, it is not possible to proceed with the simplex method of calculation any further as we cannot
decide which variable will be non-basic at the next iteration. This is the criterion for unbounded
solution.

NOTE: If in the course of simplex computation zj - cj < 0 but yij ≤ 0 for all i then the problem has no
finite solution.
But in this case we may observe that the variable x2 is unconstrained and can be increased
arbitrarily. This is why the solution is unbounded.

Infeasible Solution
This section illustrates how to identify the infeasible solution using simplex method. This is explained
with the help of the following Example.

Example:
Consider the following problem. Minimize
200x1 + 300x2

Subject to:
2x1 + 3x2 ≥ 1200
x1 + x2 ≤ 400
2x1 + 3/2x2 ≥ 900 x1, x2
97
 ≥ 0 Solution

Since it is a minimization problem we have to convert it into maximization problem and introduce the
slack, surplus and artificial variables. The problem appears in the following manner after doing all
these procedure.
Maximize
-200x1 - 300x2
Subject to:
2x1 + 3x2 - s3 +a6 = 1200 x1 +
x2 + s4 = 400
2x1 + 3/2x2 - s5 + a7 = 900

x1, x2, s3, s4, s5, a6, a7 ≥ 0

Here the a6 and a7 are artificial variables. We use two phase method to solve this problem.

Phase I
Maximize
-a6 –a7 Subject to:
2x1 + 3x2 -s3 + a6 = 1200 x1 + x2
+ s4 = 400
2x1 + 3/2x2 - s5 + a = 900
x1, x2, s3, s4, s5, a, a7 ≥ 0

The calculation of simplex procedures and tables are as follows:

CB Basic Cj 0 0 0 0 0 -1 -1
variables XB x1 x2 s3 s4 s5 a6 a7

-1 a6 1200 2 3 -1 0 0 1 0
0 s4 400 1 1 0 1 0 0 1
-1 a7 900 2 3/2 0 0 -1 0 0
zj-cj -4 -9/2 1 0 1 0 0

98
 CB Basic Cj 0 0 0 0 0 -1
variables XB x1 x2 s3 s4 s5 a7

0 x2 400 2/3 1 -1/3 0 0 0

0 s4 0 1/3 0 1/3 1 0 0
-1 a7 300 1 0 1/2 0 -1 1
zj-cj -1 0 -1/2 0 1 0
CB Basic Cj 0 0 0 0 0 -1
variables XB x1 x2 s3 s4 s5 a7

0 x2 400 0 1 -1 -2 0 0
0 x1 0 1 0 1 3 0 0
-1 a7 300 0 0 -1/2 -3 -1 1
zj-cj 0 0 1/2 3 1 0

Note that zj - cj ≥ 0 for all the variables but the artificial variable a7 is still a basic variable. This situation
indicates that the problem has no feasible solution.

99
 Assignment Models : Concept, Flood’s Technique / Hungarian
Method – Minimization form

Introduction

The Assignment Problem can define as follows:

Given n facilities, n jobs and the effectiveness of each facility to each job, here the problem
is to assign each facility to one and only one job so that the measure of effectiveness if
optimized. Here the optimization means Maximized or Minimized. There are many
management problems has a assignment problem structure. For example, the head of the
department may have 6 people available for assignment and 6 jobs to fill. Here the head
may like to know which job should be assigned to which person so that all tasks can be
accomplished in the shortest time possible. Another example a container company may
have an empty container in each of the location 1, 2,3,4,5 and requires an empty container
in each of the locations 6, 7, 8,9,10. It would like to ascertain the assignments of containers
to various locations so as to minimize the total distance.

The third example here is, a marketing set up by making an estimate of sales performance
for different salesmen as well as for different cities one could assign a particular salesman
to a particular city with a view to maximize the overall sales.

Note that with n facilities and n jobs there are n! possible assignments. The simplest way of
finding an optimum assignment is to write all the n! possible arrangements, evaluate their
total cost and select the assignment with minimum cost. Bust this method leads to a
calculation problem of formidable size even when the value of n is moderate. For n=10 the
possible number of arrangements is 3268800.
Assignment Problem Structure and Solution

The structure of the Assignment problem is similar to a transportation problem, is as follows:

100
 The element cij represents the measure of effectiveness when ith person is assigned jth
job. Assume that the overall measure of effectiveness is to be minimized. The element x ij
represents the number of ith individuals assigned to the jth job. Since ith person can be
assigned only one job and jth job can be assigned to only one person we have the
following

xi1 + xi2 + ……………. + xin = 1, where i = 1, 2, ....................................................... , n

x1j + x2j + ……………. + xnj = 1, where j = 1, 2, ........................................................, n

and the objective function is

formulated as Minimize

c11x11 +

c12x12 + ............................................................................... + CnnXnn

xij ≥ 0

The assignment problem is actually a special case of the transportation problem where
m = n and ai = bj = 1. However, it may be easily noted that any basic feasible solution of
an assignment problem contains (2n – 1) variables of which (n – 1) variables are zero.
Because of this high degree of degeneracy the usual computation techniques of a
transportation problem become very inefficient. So, hat a separate computation

101
 technique is necessary for the assignment problem.

The solution of the assignment problem is based on the following results:

“If a constant is added to every element of a row/column of the cost matrix of an assignment
problem the resulting assignment problem has the same optimum solution as the original
assignment problem and vice versa”. – This result may be used in two different methods to solve
the assignment problem. If in an assignment problem some cost elements c ij are negative, we
may have to convert them into an equivalent assignment problem where all the cost elements
are non-negative by adding a suitable large constant to the cost elements of the relevant row or
column, and then we look for a feasible solution which has zero assignment cost after adding
suitable constants to the cost elements of the various rows and columns. Since it has been
assumed that all the cost elements are non-negative, this assignment must be optimum. On the
basis of this principle a computational technique known as Hungarian Method is developed. The
Hungarian Method is discussed as follows.

Hungarian Method:

The Hungarian Method is discussed in the form of a series of computational steps as

follows, when the objective function is that of minimization type.

Step 1:
From the given problem, find out the cost table. Note that if the number of origins is not equal
to the number of destinations then a dummy origin or destination must be added.

Step 2:
In each row of the table find out the smallest cost element, subtract this smallest cost element
from each element in that row. So, that there will be at least one zero in each row of the new
table. This new table is known as First Reduced Cost Table.

Step 3:
In each column of the table find out the smallest cost element, subtract this smallest cost
element from each element in that column. As a result of this, each row and column has at least
one zero element. This new table is known as Second Reduced Cost Table.
102
 Step 4:
Now determine an assignment as follows:

For each row or column with a single zero element cell that has not be assigned or
eliminated, box that zero element as an assigned cell.
1. For every zero that becomes assigned, cross out all other zeros in the same row
and for column.
2. If for a row and for a column there are two or more zero and one can’t be
chosen by inspection, choose the assigned zero cell arbitrarily.
3. The above procedures may be repeated until every zero element cell is either
assigned (boxed) or crossed out.

Step 5:
An optimum assignment is found, if the number of assigned cells is equal to the number
of rows (and columns). In case we had chosen a zero cell arbitrarily, there may be an
alternate optimum. If no optimum solution is found i.e. some rows or columns without an
assignment then go to Step 6.

Step 6:
Draw a set of lines equal to the number of assignments which has been made in Step 4,
covering all the zeros in the following manner

1. Mark check (√) to those rows where no assignment has been made.
2. Examine the checked (√) rows. If any zero element cell occurs in those rows,
check (√) the respective columns that contains those zeros.
3. Examine the checked (√) columns. If any assigned zero element occurs in
those columns, check (√) the respective rows that contain those assigned
zeros.
4. The process may be repeated until now more rows or column can be checked.
5. Draw lines through all unchecked rows and through all checked columns.

Step 7:
103
 Examine those elements that are not covered by a line. Choose the smallest of these
elements and subtract this smallest from all the elements that do not have a line through
them.

Add this smallest element to every element that lies at the intersection of two lines.
Then the resulting matrix is a new revised cost table

Example

Problem
A work shop contains four persons available for work on the four jobs. Only one person can
work on any one job. The following table shows the cost of assigning each person to each job.
The objective is to assign person to jobs such that the total assignment cost is a minimum.
Jobs

1 2 3 4

A 20 25 22 28

B 15 18 23 17
Persons
C 19 17 21 24

D 25 23 24 24

Solution

As per the Hungarian Method

Step 1: The cost Table

Jobs
1 2 3 4

A 20 25 22 28

Persons B 15 18 23 17

C 19 17 21 24

D 25 23 24 24

104
 Step 2: Find the First Reduced Cost Table

Jobs
1 2 3 4

A 0 5 2 8

0 3 8 2
Persons B
2 0 4 7
C
2 0 1 1
D

Step 3: Find the Second Reduced Cost Table

Jobs
1 2 3 4

A 0 5 1 7

0 3 7 1
Persons B
2 0 3 6
C
2 0 0 0
D

Step 4: Determine an Assignment

By examine row A of the table in Step 3, we find that it has only one zero (cell A1) box this zero and
cross out all other zeros in the boxed column. In this way we can eliminate cell B1.

Now examine row C, we find that it has one zero (cell C2) box this zero and cross out (eliminate) the
zeros in the boxed column. This is how cell D2 gets eliminated.
There is one zero in the column 3. Therefore, cell D3 gets boxed and this enables us to eliminate cell
D4.Therefore, we can box (assign) or cross out (eliminate) all zeros. The resultant table is shadblow:

105
 Jobs
1 2 3 4

A 0 5 1 7

Persons B 0 3 7 1

C 2 0 3 6

0
D 2 0 0

Step 5:
The solution obtained in Step 4 is not optimal. Because we were able to make three assignments when
four were required.
Step 6:

Cover all the zeros of the table shown in the Step 4 with three lines (since already we made three
assignments).

Check row B since it has no assignment. Note that row B has a zero in column 1, therefore check
column1. Then we check row A since it has a zero in column 1. Note that no other rows and
columns are checked. Now we may draw three lines through unchecked rows (row C and D) and
the checked column (column 1). This is shown in the table given below:

Jobs
1 2 3 4

Persons

106
 Step 7:
Develop the new revised table.

Examine those elements that are not covered by a line in the table given in Step 6. Take the
smallest element in this case the smallest element is 1. Subtract this smallest element from the
uncovered cells and add 1 to elements (C1 and D1) that lie at the intersection of two lines. Finally,
we get the new revised cost table, which is shown below:

Jobs
1 2 3 4

0 4 0 6
A

0 2 6 0
Persons B

3 0 3 6
C

3 0 0 0
D

Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution (assignment).

Step 9:
Determine an assignment
Examine each of the four rows in the table given in Step 7, we may find that it is only row C which
has only one zero box this cell C2 and cross out D2.

Note that all the remaining rows and columns have two zeros. Choose a zero arbitrarily, say
A1 and box this cell so that the cells A3 and B1 get eliminated.

Now row B (cell B4) and column 3 (cell D4) has one zero box these cells so that cell D4 is
eliminated.

107
 Thus, all the zeros are either boxed or eliminated. This is shown in the following table

Jobs
1 2 3 4

0 4 0 6
A

0 2 6 0
Persons B

3 0 3 6
C

3 0 0 06
D

Since the number of assignments equal to the number of rows (columns), the assignment
shown in the above tale is optimal.
The total cost of assignment is: 78 that is A1 + B4 + C2 + D3
20 + 17 + 17 + 24 = 78

Unbalanced Assignment Problem

In the previous section we assumed that the number of persons to be assigned and the number
of jobs were same. Such kind of assignment problem is called as balanced assignment problem.
Suppose if the number of person is different from the number of jobs then the assignment
problem is called as unbalanced.

If the number of jobs is less than the number of persons, some of them can’t be assigned any job.
So that we have to introduce on or more dummy jobs of zero duration to make the unbalanced
assignment problem into balanced assignment problem. This balanced assignment problem can
be solved by using the Hungarian Method as discussed in the previous section. The persons to
whom the dummy jobs are assigned are left out of assignment.

108
 Similarly, if the number of persons is less than number of jobs then we have introduce one or
more dummy persons with zero duration to modify the unbalanced into balanced and then the
problem is solved using the Hungarian Method. Here the jobs assigned to the dummy persons are
left out.

Example

Solve the following unbalanced assignment problem of minimizing the total time for performing
all the jobs.
Jobs
1 2 3 4 5

A 5 2 4 2 5

2 4 7 6 6
B

6 7 5 8 7
Workers CD

5 2 3 3 4
E

8 3 7 8 6
F

3 6 3 5 7

109
 Jobs
1 2 3 4 5 6

A 5 2 4 2 5

2 4 7 6 6
B

6 7 5 8 7
Workers CD

5 2 3 3 4
E

8 3 7 8 6
F

3 6 3 5 7

Now the problem becomes balanced one since the number of workers is equal to the number jobs.
So that the problem can be solved using Hungarian Method.

Step 1: The cost Table

Jobs
1 2 3 4 5 6

A 5 2 4 2 5

2 4 7 6 6
Workers BC

6 7 5 8 7
D
5 2 3 3 4
E
8 3 7 8 6

F
3 6 3 5 7

110
 Step 2: Find the First Reduced Cost Table

Jobs
1 2 3 4 5 6

5 2 4 2 5
A

2 4 7 6 6
B

6 7 5 8 7
Workers CD

5 2 3 3 4
E

8 3 7 8 6
F

3 6 3 5 7

Step 3: Find the Second Reduced Cost Table

Jobs
1 2 3 4 5 6

3 0 1 0 1
A

0 2 4 4 2
B

4 5 2 6 3
Workers CD

3 0 0 1 0
E

6 1 4 6 2

1 4 0 3 3

111
 Step 4: Determine an Assignment

By using the Hungarian Method the assignment is made as follows:

Jobs
1 2 3 4 5 6

3 0 1 0 1 0
A

0 2 4 4 2 0
B

0 5 2 6 3

0
3 0 0 1 0
Workers DE
6 1 4 6 2 0

F
1 4 0 3 3 0

Step 5:

The solution obtained in Step 4 is not optimal. Because we were able to make five assignments
when six were required.

Step 6:

Cover all the zeros of the table shown in the Step 4 with five lines (since already we made five
assignments).
Check row E since it has no assignment. No
That row B has a zero in column 6, therefore check
column6. Then we check row C since it has a zero in column 6. Note that no other rows and
columns are checked. Now we may draw five lines through unchecked rows (row A, B, D and F) and
the checked column (column 6). This is shown in the table given below:

112
 Jobs
1 2 3 4 5 6

Workers CD

2 0

Step 7:
Develop the new revised table.

Examine those elements that are not covered by a line in the table given in Step 6. Take the
smallest element in this case the smallest element is 1. Subtract this smallest element

from the uncovered cells and add 1 to elements (A6, B6, D6 and F6) that lie at the
intersection of two lines. Finally, we get the new revised cost table, which is shown below:

113
 Jobs
1 2 3 4 5 6

A 3 0 1 0 1 1

B 0 2 4 4 2 1

Workers CD 3 4 1 5 2 0

E 3 0 0 1 0 1

F 5 0 3 5 1 0

1 4 0 3 3 1
Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution (assignment).

Step 9:
Determine an Jobs
assignment

114
 Since the number of assignments equal to the number of rows (columns), the assignment shown in
the above tale is optimal.
Thus, the worker A is assigned to Job4, worker B is assigned to job 1, worker C is assigned to
job 6, worker D is assigned to job 5, worker E is assigned to job 2, and worker F is assigned
to job 3. Since the Job 6 is dummy so that worker C can’t be assigned.

The total minimum time is: 14 that is A4 + B1 + D5 + E2 + F3 2

+ 2 + 4 + 3 + 3 = 14

Example:

A marketing company wants to assign three employees viz. A, B, and C to four offices located at
W, X, Y and Z respectively. The assignment cost for this purpose is given in following table.

Offices
W X Y Z

160 220 240 200

A

Employees B 100 320 260 160

100 200 460 250

C

Solution

Since the problem has fewer employees than offices so that we have introduce a dummy employee
with zero cost of assignment.

The revised problem is as follows:

115
 Offices
W X Y Z

A 160 220 240 200

Employees B C
100 320 260 160

100 200 460 250

D

Now the problem becomes balanced. This can be solved by using Hungarian Method as
in the case of Example 2.2. Thus as per the Hungarian Method the assignment made as follows:
Employee A is assigned to Office X, Employee B is assigned to Office Z, Employee C is assigned to
Office W and Employee D is assigned to Office Y. Note that D is empty so that no one is assigned
to Office Y.
The minimum cost of assignment is: 220 + 160 + 100 = 480

Infeasible Assignment Problem

Sometimes it is possible a particular person is incapable of performing certain job or a specific job
can’t be performed on a particular machine. In this case the solution of the problem takes into
account of these restrictions so that the infeasible assignment can be avoided.

The infeasible assignment can be avoided by assigning a very high cost to the cells where assignments
are restricted or prohibited. This is explained in the following Example 2.4.

Example

A computer centre has five jobs to be done and has five computer machines to perform
them. The cost of processing of each job on any machine is shown in the table below.

116
 Because of specific job requirement and machine configurations certain jobs can’t be done on
certain machines. These have been shown by X in the cost table. The assignment of jobs to the
machines must be done on a one to one basis. The objective here is to assign the jobs to the
available machines so as to minimize the total cost without violating the restrictions as mentioned
above.

Solution
Step 1: The cost Table

Because certain jobs cannot be done on certain machines we assign a high cost say for example 500
to these cells i.e. cells with X and modify the cost table. The revised assignment problem is as
follows:

117
 Jobs
1 2 3 4 5

30 60 30
1

70 30 30
Computer 2
Machines
500 70 60
3

70 40 500
4
30 500 70
5

Now we can solve this problem using Hungarian Method as discussed in the previous sections.

Step 2: Find the First Reduced Cost Table

Jobs
1 2 3 4 5

40 470 30
1

470 40 20
Computer 2
Machines
10 450 20 10
3
40 50 20 480
4
10 470 40
5

Step 3: Find the Second Reduced Cost Table

Jobs

118
 1 2 3 4 5

1 40 470 30

470 40 20
Computer 2
Machines
10 450 20 10
3

40 50 20 480
4

10 470 40
5

Step 4: Determine an Assignment

Computer
Machines
Jobs
2 3 4 5
1

40 470
2
470 40 20 0

3
10 450 0 10
4
40 50 0 20 480

5
0 0 470 40

119
 Step 5:
The solution obtained in Step 4 is not optimal. when five were required.
Because

Step 6:

Cover all the zeros of the table we were able to make four assignments

Shown in the Step 4 with four lines (since already we made four assignments)

Check row 4 since it has no assignment. Note that row 4 has a zero in column 3, therefore check
column3. Then we check row 3 since it has a zero in column 3. Note that no other rows and
columns are checked. Now we may draw four lines through unchecked rows (row 1, 2, 3 and 5) and
the checked column (column 3).
This is shown in the table given below:

Jobs
1 2 3 4 5

1 40 470 30

470 40 20
Computer 2
Machines
10 450 10
3

40 50 20 480
4 0
470 40
5

Step 7:
120
 Develop the new revised table.

Examine those elements that are not covered by a line in the table given in Step 6. Take
the smallest element in this case the smallest element is 10. Subtract this smallest
element
from the uncovered cells and add 1 to elements (A6, B6, D6 and F6) that lie at the
intersection of two lines. Finally, we get the new revised cost table, which is shown below:

Jobs
1 2 3 4 5
0
Computer
40 471
Machines 1

470 40 21
2
440

3
30 40 10 470
4

11 470 40

121
Step 8:

Now, go to Step 4 and repeat the procedure until we arrive at an optimal solution (assignment).

Since the number of assignments equal to the number of rows (columns), the assignment
shown in the above tale is optimal.

Thus, the Machine1 is assigned to Job5, Machine 2 is assigned to job4, Machine3 is

assigned to job1, Machine4 is assigned to job3 and Machine5 is assigned to job2.

The minimum assignment cost is: 170

Maximization in an Assignment Problem

There are situations where certain facilities have to be assigned to a number of jobs so as
to maximize the overall performance of the assignment. In such cases the problem can be
converted into a minimization problem and can be solved by using Hungarian Method.
Here the
conversion of maximization problem into a minimization can be done by subtracting all the
elements of the cost table from the highest value of that table.
122
 Example

Consider the problem of five different machines can do any of the required five jobs with different
profits resulting from each assignment as illustrated below:

Machines
1 2 3 4 5

40 47 50 38 50
1

50 34 37 31 46
2
Jobs
50 42 43 40 45
3

35 48 50 46 46
4

38 72 51 51 49
5

Find out the maximum profit through optimal assignment.

Solution

This is a maximization problem, so that first we have to find out the highest value in the table and
subtract all the values from the highest value. In this case the highest value is 72.

The new revised table is given below:

123
 Machines
1 2 3 4 5

32 35 22 34 22
1

22 38 35 41 26
2
Jobs
22 30 29 32 27
3

37 24 22 26 26
4

34 21 21 23
5

This can be solved by using the Hungarian Method.

By solving this, we obtain the solution is as follows:

Jobs Machines

1 3

2 5

3 1

4 4

5 2

The maximum profit through this assignment is: 264

Crew Assignment Problem

The crew assignment problem is explained with the help of the following problem

Problem:

124
 A trip from Chennai to Coimbatore takes six hours by bus. A typical time table of the bus
service in both the direction is given in the Table 1. The cost of providing this service by the
company based on the time spent by the bus crew i.e. driver and conductor away from their
places in addition to service times. The company has five crews. The condition here is that every
crew should be provided with more than 4 hours of rest before the return trip again and should
not wait for more than 24 hours for the return trip. Also the company has guest house facilities for
the crew of Chennai as well as at Coimbatore.

Find which line of service is connected with which other line so as to reduce the waiting time to the
minimum.

Table 1

Departure Route Number Arrival at Arrival at Route Number Departu

from Coimbatore Chennai re from
Chennai Coimbato
re
06.00 1 12.00 11.30 a 05.30
07.30 2 13.30 15.00 b 09.00
11.30 3 17.30 21.00 c 15.00
19.00 4 01.00 00.30 d 18.30
00.30 5 06.30 06.00 e 00.00
Solution
For each line the service time is constant so that it does not include directly in the computation.

Suppose if the entire crew resides at Chennai then the waiting times in hours at Coimbatore for

different route connections are given below in Table 2.

If route 1 is combined with route a, the crew after arriving at Coimbatore at 12 Noon start at
5.30 next morning. Thus the waiting time is 17.5 hours. Some of the assignments are infeasible.
Route c leaves Coimbatore at 15.00 hours. Thus the crew of route 1 reaching Coimbatore at
12 Noon are unable to take the minimum stipulated rest of four hours if they are asked
to leave by route c. Hence 1-c is an infeasible assignment. Thus it cost is M (a large
positive number).
125
 Table 2

Route a B c d e

1 17.5 21 M 6.5 12

2 16 19.5 M 5 10.5

3 12 15.5 21.5 M 6.5

4 4.5 8 4 17.5 23

5 23 M 8.5 12 17.5

Similarly, if the crews are assumed to reside at Coimbatore then the waiting times of the crew in
hours at Chennai for different route combinations are given below in Table 3.

Table 3

Route a B c d e

1 18.5 15 9 5.5 M

2 20 16.5 10.5 7 M

3 M 20.5 14.5 11 5.5

4 7.5 M 22 18.5 13

5 13 9.5 M M 18.5

126
 Suppose, if the crew can be instructed to reside either at Chennai or at Coimbatore, minimum
waiting time from the above operation can be computed for different route combination by
choosing the minimum of the two waiting times (shown in the Table 2 and Table 3). This is given
in the following Table 4. Table 4

Route a b c d e

1 17.5* 15 9 5.5 12*

2 16* 16.5 10.5 5* 10.5*

3 12* 15.5* 14.5 11 5.5

4 4.5* 8* 14* 17.5* 13

5 13 9.5 8.5* 12* 17.5*

Note: The asterisk marked waiting times denotes that the crew are based at Chennai; otherwise
they are based at Coimbatore.
Now we can solve the assignment problem (presented in Table 4) using Hungarian Method.

Step 1: Cost Table (Table 5)

Table 5
Route
a b c d e

1 17.5* 15 9 5.5 12*

2 16* 16.5 10.5 5* 10.5*

3 12* 15.5* 14.5 11 5.5

4 4.5* 8* 14* 17.5* 13

5 13 9.5 8.5* 12* 17.5*

127
 Step 2: Find the First Reduced cost table (Table 6)

Table 6

Route a B c d e

1 12 9.5 3.5 0 6.5

2 11 11.5 5.5 0 5.5

3 6.5 10 9 5.5 0

4 0 3.5 9.5 13 8.5

5 4.5 1 0 3.5 9

Step 3: Find the Second Reduced cost table (Table 7)

Table 7

Route A B c d e

1 12 8.5 3.5 0 6.5

2 11 10.5 5.5 0 5.5

3 6.5 9 9 5.5 0

4 0 2.5 9.5 13 8.5

5 4.5 0 0 3.5 9

Step 4: Determine an Assignment (Table 8)

128
 Table 8

Route A B C d e

1 12 8.5 3.5 0 6.5

2 11 10.5 5.5 0 5.5

3 6.5 9 9 5.5 0

4 0 2.5 9.5 13 8.5

5 4.5 0 0 3.5 9

Step 5: The solution obtained in Step 4 is not optimal since the number of assignments are less than the
number of rows (columns).

Check (√) column d also. Then check row 1 since it has zero in column d. Draw the lines through
the unchecked rows and checked column using 4 lines (only 4 assignments are made). This is
shown in Table 9. Table 9

Route a b d e

1 12 8.5 3.5 6.5

2 11 10.5 5.5 5.5

6.5 5.5 0
3

2.5 9.5 13 8.5

4
4.5 0 3.5
5
129
 Step 7: Develop a new revised table (Table 10)

Take the smallest element from the elements not covered by the lines in this case 3.5 is the
smallest element. Subtract all the uncovered elements from 3.5 and add 3.5 to the elements lie at
the intersection of two lines (cells 3d, 4d and 5d). The new revised table is presented in Table 10.

Table 10

Route a B C d E

1 8.5 5 0 0 3

2 7.5 7 2 0 2

3 6.5 9 9 9 0

4 0 2.5 9.5 16.5 8.5

5 4.5 0 0 7 9

Step 8: Go to Step 4 and repeat the procedure until an optimal solution if arrived.

Step 9: Determine an Assignment (Table 11)

130
 Table 11

Route a b c d e

8.5
1

7.5 0
2

6.5 0
3

2.5 9.5 16.5 8.5

4

4.5
5

Assignment illustrated in Table 11 is optimal since the number of assignments is equal

to the number of rows (columns).
Thus, the routes to be prepared to achieve the minimum waiting time are
as follow 1-c, 2 – d, 3 – e, 4 – 1a –and 5 – b

By referring Table 5, we can obtain the waiting times of these assignments as well as the residence
(guest house) of the crews. This is presented in the following Table 12.

Table 12
Routes ReResidence of the Crew Waiti
ng
Time
1 –c Coimbatore 9
2 –d Chennai 5
3 –e Coimbator 5.5
4 –a e Chennai 4.5
5 -b Coimbatore 9.5

131
 Linear Programming Problem (LPP):
Transportation Model

Introduction
A special class of linear programming problem is Transportation Problem, where the objective
is to minimize the cost of distributing a product from a number of sources (e.g. factories) to a
number of destinations (e.g. warehouses) while satisfying both the supply limits and the
demand requirement. Because of the special structure of the Transportation Problem the
Simplex Method of solving is unsuitable for the Transportation Problem. The model assumes
that the distributing cost on a given rout is directly proportional to the number of units
distributed on that route. Generally, the transportation model can be extended to areas other
than the direct transportation of a commodity, including among others, inventory control,
employment scheduling, and personnel assignment.
The transportation problem special feature is illustrated here with the help of following
Example.
Example
Suppose a manufacturing company owns three factories (sources) and distribute his products
to five different retail agencies (destinations). The following table shows the capacities of the
three factories, the quantity of products required by the various retail agencies and the cost of
shipping one unit of the product from each of the three factories to each of the five retail
agencies.

Retail
Agency
Factories 1 2 3 4 5 Capacit
y
1 1 9 13 36 51 50
2 24 12 16 20 1 100
3 14 33 1 23 26 150

Requireme 100 60 50 50 40 300

nt

132
 Usually the above table is referred as Transportation Table, which provides the basic information
regarding the transportation problem. The quantities inside the table are known as transportation cost
per unit of product. The capacity of the factories 1, 2, 3 is 50, 100 and 150
respectively. The requirement of the retail agency 1, 2, 3, 4, 5 is 100, 60, 50, 50, and 40
respectively.

In this case, the transportation cost of one unit from factory 1 to retail agency 1 is 1, from factory 1 to
retail agency 2 is 9, from factory 1 to retail agency 3 is 13, and so on.
A transportation problem can be formulated as linear programming problem using variables
with two subscripts.
Let
x11=Amount to be transported from factory 1 to retail agency 1 x12= Amount to be
transported from factory 1 to retail agency 2
……..
……..
……..
……..
X35= Amount to be transported from factory 3 to retail agency 5.

Let the transportation cost per unit be represented by C11, C12, …..C35 that is C11=1, C12=9,
and so on.
Let the capacities of the three factories be represented by a1=50, a2=100, a3=150.
Let the requirement of the retail agencies are b1=100, b2=60, b3=50, b4=50, and b5=40. Thus,
the problem can be formulated as

Minimize

C11x11+C12x12+……. +C35x35
Subject to:
x11 + x12 + x13 + x14 + x15 =
a1 x21 + x22 + x23 + x24 + x25
133
 = a2 x31 + x32 + x33 + x34 +
x35 = a3 x11 + x21 + x31 = b1
x12 + x22 + x32 = b2
x13 + x23 + x33 = b3
x14 + x24 + x34 = b4
x15 + x25 + x35 =
b5

x11, x12, ……, x35 ≥ 0.

Thus, the problem has 8 constraints and 15 variables. So, it is not possible to solve such a
problem using simplex method. This is the reason for the need of special computational
procedure to solve transportation problem. There are varieties of procedures, which are
described in the next section.

Transportation Algorithm
The steps of the transportation algorithm are exact parallels of the simplex algorithm, they are:
Step 1: Determine a starting basic feasible solution, using any one of the following three
methods
1. North West Corner Method
2. Least Cost Method
3. Vogel Approximation Method

Step 2: Determine the optimal solution using the following method

1. MODI (Modified Distribution Method) or UV Method.

Basic Feasible Solution of a Transportation Problem

The computation of an initial feasible solution is illustrated in this section with the help of the
example1.1 discussed in the previous section. The problem in the example 1.1 has 8
constraints and 15 variables we can eliminate one of the constraints since a1 + a2 + a3 = b1 +

134
 b2
+ b3 + b4 +b5. Thus now the problem contains 7 constraints and 15 variables. Note that any
initial (basic) feasible solution has at most 7 non-zero Xij. Generally, any basic feasible solution

with m sources (such as factories) and n destination (such as retail agency) has at most m + n -1
non-zero Xij.
The special structure of the transportation problem allows securing a non artificial basic
feasible solution using one the following three methods.
1. North West Corner Method
2. Least Cost Method
3. Vogel Approximation Method

The difference among these three methods is the quality of the initial basic feasible solution
they produce, in the sense that a better that a better initial solution yields a smaller objective
value. Generally the Vogel Approximation Method produces the best initial basic feasible
solution, and the North West Corner Method produces the worst, but the North West Corner
Method involves least computations.

North West Corner Method:

The method starts at the North West (upper left) corner cell of the tableau (variable x11).

Step -1: Allocate as much as possible to the selected cell, and adjust the associated amounts of
capacity (supply) and requirement (demand) by subtracting the allocated amount.

Step -2: Cross out the row (column) with zero supply or demand to indicate that no further
assignments can be made in that row (column). If both the row and column becomes zero
simultaneously, cross out one of them only, and leave a zero supply or demand in the
uncrossed out row (column).
Step -3: If exactly one row (column) is left uncrossed out, then stop. Otherwise, move to the
cell to the right if a column has just been crossed or the one below if a row has been crossed
out. Go to step -1.

Example 1.2:

135
 Consider the problem discussed in Example 1.1 to illustrate the North West Corner Method of
determining basic feasible solution.

Retail
Agency
Factories 1 2 3 4 5 Capacit
y
1 1 9 13 36 51 50
2 24 1 16 20 1 100
2
3 14 3 1 23 26 150
3
Requireme 100 6 50 50 40 300
nt 0

The allocation is shown in the following tableau:

The arrows show the order in which the allocated (bolded) amounts are generated. The
starting basic solution is given as

x11 = 50,
x21 = 50, x22 = 50
x32 = 10, x33 = 50, x34 = 50, x35 = 40
136
 The corresponding transportation cost is

50 * 1 + 50 * 24 + 50 * 12 + 10 * 33 + 50 * 1 + 50 * 23 + 40 * 26 = 4420

It is clear that as soon as a value of Xij is determined, a row (column) is eliminated from further
consideration. The last value of Xij eliminates both a row and column. Hence a feasible solution
computed by North West Corner Method can have at most m + n – 1 positive Xij if the
transportation problem has m sources and n destinations.
Least Cost Method
The least cost method is also known as matrix minimum method in the sense we look for the row
and the column corresponding to which Cij is minimum. This method finds a better initial basic
feasible solution by concentrating on the cheapest routes. Instead of starting the allocation with the
northwest cell as in the North West Corner Method, we start by allocating as much as possible to the
cell with the smallest unit cost. If there are two or more minimum costs then we should select the
row and the column corresponding to the lower numbered row. If they appear in the same row we
should select the lower numbered column. We then cross out the satisfied row or column, and
adjust the amounts of capacity and requirement accordingly. If both a row and a column is satisfied
simultaneously, only one is crossed out. Next, we look for the uncrossed-out cell with the smallest
unit cost and repeat the process until we are left at the end with exactly one uncrossed-out row or
column.
Example

The least cost method of determining initial basic feasible solution is illustrated with the help
of problem presented in the section 1.1.
Capacity

1 9 13 10 51 50
50
24 60 1 16 20 40 1 50 60
2
14 33 1 23 25 150 100 50
50 50 50
Requirement 100 60 50 50 40
50
137
 The Least Cost method is applied in the following manner:
We observe that C11=1 is the minimum unit cost in the table. Hence X 11=50 and the first row is
crossed out since the row has no more capacity. Then the minimum unit cost in the uncrossed- out
row and column is C25=1, hence X25=40 and the fifth column is crossed out. Next C33=1is the
minimum unit cost, hence X33=50 and the third column is crossed out. Next C22=12 is the minimum
unit cost, hence X22=60 and the second column is crossed out. Next we look for the uncrossed-out
row and column now C31=14 is the minimum unit cost, hence X31=50 and crossed out the first column
since it was satisfied. Finally C34=23 is the minimum unit cost, hence X34=50 and the fourth column is
crossed out.

So that the basic feasible solution developed by the Least Cost Method has transportation cost is 1 *
50 + 12 * 60 + 1 * 40 + 14 * 50 + 1 * 50 + 23 * 50 = 2710
Note that the minimum transportation cost obtained by the least cost method is much lower
than the corresponding cost of the solution developed by using the north-west corner
method.

Vogel Approximation Method (VAM):

VAM is an improved version of the least cost method that generally produces better solutions. The
steps involved in this method are:

Step 1: For each row (column) with strictly positive capacity (requirement), determine a penalty by
subtracting the smallest unit cost element in the row (column) from the next smallest unit cost
element in the same row (column).

Step 2: Identify the row or column with the largest penalty among all the rows and columns. If the
penalties corresponding to two or more rows or columns are equal we select the topmost row and the
extreme left column.

Step 3: We select Xij as a basic variable if Cij is the minimum cost in the row or column with largest
penalty. We choose the numerical value of Xij as high as possible subject to the row and the column

138
 constraints. Depending upon whether ai or bj is the smaller of the two ith row or jth column is crossed
out.
Step 4: The Step 2 is now performed on the uncrossed-out rows and columns until all the basic
variables have been satisfied.

Example
Consider the following transportation problem

Destination
Origin 1 2 3 4 ai
1 20 22 17 4 120
2 24 37 9 7 70
3 32 37 20 15 50
bj 60 40 30 110 240

Note: ai = capacity (supply) bj = requirement (demand)

Now, compute the penalty for various rows and columns which is shown in the following
table:
Destination
Origin 1 2 3 4 ai Column
Penalty
1 20 22 17 4 120 13
2 24 37 9 7 70 2
3 32 37 20 15 50 5
bj 60 40 30 110 240

Row Penalty 4 15 8 3

Look for the highest penalty in the row or column, the highest penalty occurs in the second
column and the minimum unit cost i.e. cij in this column is c12=22. Hence assign 40 to this cell
i.e. x12 = 40 and cross out the second column (since second column was satisfied. This is
shown in the following table:

139
 Destination
Origin 1 2 3 4 ai Column Penalty

1 20 22 40 17 4 80 13
2 24 37 9 7 70 2
3 32 37 20 15 50 5
bj 60 40 30 110 240

Row Penalty 4 15 8 3

The next highest penalty in the uncrossed-out rows and columns is 13 which occur in the first
row and the minimum unit cost in this row is c14=4, hence x14=80 and cross out the first row.

The modified table is as follows

The next highest penalty in the uncrossed-out rows and columns is 8 which occurs in the third

Destination
Origin ai Column
1 2 3 4 Penalty

1 0 13
20 22 17 4
80
40
2 24 37 9 7 40 17

30
3 32 37 20 15 50 17

bj 60 40 30 11 240
0

Row 8

Penalty 8
15 8

column and the minimum cost in this column is c23=9, hence x23=30 and cross out the third
column with adjusted capacity, requirement and penalty values. The modified table is as
follows:

140
 Destination
Origin
1 2 3 4 ai Column
Penalty

1 0
20 22 17 4
40 80

2 24 37 9 7 70

3 32 37 20 15 50

bj 60 40 30 110 240

Row Penalty 4 15 8 3

The next highest penalty in the uncrossed-out rows and columns is 17 which occurs in the second row
and the smallest cost in this row is c24=15, hence x24=30 and cross out the fourth column with the
adjusted capacity, requirement and penalty values. The modified table is as follows:

Destin
at ai

24

32
bj 60 240

Row Penalty 15

The next highest penalty in the uncrossed-out rows and columns is 17 which occurs in the
141
 second row and the smallest cost in this row is c21=24, hence xi21=10 and cross out the

Second own with the adjusted capacity, requirement and penalty values. The modified table is
as follows:

Destination
Origin ai

32
bj 240

Row

The next highest penalty in the uncrossed-out rows and columns is 17 which occurs in the third
row and the smallest cost in this row is c31=32, hence xi31=50 and cross out the third row or
first column. The modified table is as follows:

Destina ai
Origin

bj 60 40 240

RowPenalty 15

The transportation cost corresponding to this choice of basic variables is 22 * 40 + 4 * 80 + 9

* 30 + 7 * 30 + 24 * 10 + 32 * 50 = 3520

142
 Modified Distribution Method

The Modified Distribution Method, also known as MODI method or u-v method, which provides a
minimum cost solution (optimal solution) to the transportation problem. The following are the steps
involved in this method.

Step 1: Find out the basic feasible solution of the transportation problem using any one of the
three methods discussed in the previous section.
Step 2: Introduce dual variables corresponding to the row constraints and the column constraints. If
there are m origins and n destinations then there will be m+n dual variables. The dual variables
corresponding to the row constraints are represented by u i, i=1,2,…..m where as the dual variables
corresponding to the column constraints are represented by vj, j=1,2,…..n.
The values of the dual variables are calculated from the equation given below
ui + vj = cij if xij > 0

Step 3: Any basic feasible solution has m + n -1 xij > 0. Thus, there will be m + n -1 equation to
determine m + n dual variables. One of the dual variables can be chosen arbitrarily. It is also to
be noted that as the primal constraints are equations, the dual variables are unrestricted in
sign.

Step 4: If xij=0, the dual variables calculated in Step 3 are compared with the cij values of this
allocation as cij – ui – vj. If al cij – ui – vj ≥ 0, then by the theorem of complementary slackness it can
be shown that the corresponding solution of the transportation problem is optimum. If one or more cij
– ui – vj < 0, we select the cell with the least value of cij – ui – vj and allocate as much as possible
subject to the row and column constraints. The allocations of the number of adjacent cell are adjusted
so that a basic variable becomes non-basic.

Step 5: A fresh set of dual variables are calculated and repeat the entire procedure from Step 1
to Step 5.

Example

143
 For example consider the transportation problem given below:

Demand

1 9 13 36 51
24 12 16 20 1
14 33 1 23 26
100 70 50 40 40
Supply
50
100
150

Step 1:
First we have to determine the basic feasible solution. The basic feasible solution using least
cost method is
x11=50, x22=60, x25=40, x31=50, x32=10, x33=50 and x34=40

Step 2:
The dual variables u1, u2, u3 and v1, v2, v3, v4, v5 can be calculated from the corresponding cij
values, that is
u1+v1=1 u2+v2=12 u2+v5=1 u3+v1=14 u3+v2=33
u3+v3=1 u3+v4=23
Step 3:
Choose one of the dual variables arbitrarily is zero that is u3= 0 as it occurs most often in the
above equations. The values of the variables calculated are
u1= -13, u2= -21, u3=0
v1=14, v2=33, v3=1, v4=23, v5=22
Step 4:
Now we calculate cij – ui – vj values for all the cells where xij=0 (.e. unallocated cell by the
basic feasible solution)

144
 That is
Cell(1,2)= c12-u1-v2 = 9+13-33 = -11
Cell(1,3)= c13-u1-v3 = 13+13-1 = 25
Cell(1,4)= c14-u1-v4 = 36+13-23 = 26
Cell(1,5)= c15-u1-v5 = 51+13-22 = 42
Cell(2,1)= c21-u2-v1 = 24+21-14 = 31
Cell(2,3)= c23-u2-v3 = 16+21-1 = 36
Cell(2,4)= c24-u2-v4 = 20+21-23 = 18
Cell(3,5)= c35-u3-v5 = 26-0-22 = 4

Note that in the above calculation all the cij – ui – vj ≥ 0 except for cell (1, 2) where c12 – u1 –
v2 = 9+13- 33 = -11.

Thus in the next iteration x12 will be a basic variable changing one of the present basic variables non-
basic. We also observe that for allocating one unit in cell (1, 2) we have to reduce one unit in cells (3,
2) and (1, 1) and increase one unit in cell (3, 1). The net transportation cost for each unit of such
reallocation is
-33 -1 + 9 +14 = -11

The maximum that can be allocated to cell (1, 2) is 10 otherwise the allocation in the cell (3, 2)
will be negative. Thus, the revised basic feasible solution is

x11 = 40, x12 = 10, x22 = 60, x25 = 40, x31 = 60, x33 = 50, x34 = 40

Unbalanced Transportation Problem

In the previous section we discussed about the balanced transportation problem i.e. the total supply
(capacity) at the origins is equal to the total demand (requirement) at the destination. In this section
we are going to discuss about the unbalanced transportation problems i.e. when the total supply is not
equal to the total demand, which are called as unbalanced transportation problem.

In the unbalanced transportation problem if the total supply is more than the total demand then we
introduce an additional column which will indicate the surplus supply with transportation cost zero.
Similarly, if the total demand is more than the total supply an additional row is introduced in the

145
 transportation table which indicates unsatisfied demand with zero transportation cost.
Example 1.6:

Consider the following unbalanced transportation problem

Warehous Supply
e
W1 W2 W3
X 20 17 25 400
Plant
Y 10 10 20 500
Demand 400 400 500

In this problem the demand is 1300 whereas the total supply is 900. Thus, we now introduce an
additional row with zero transportation cost denoting the unsatisfied demand. So that the modified
transportation problem table is as follows:

Now we can solve as balanced problem discussed as in the previous sections.

Degenerate Transportation Problem

In a transportation problem, if a basic feasible solution with m origins and n destinations has less than
m + n -1 positive Xij i.e. occupied cells, then the problem is said to be a degenerate transportation
problem. The degeneracy problem does not cause any serious difficulty, but it can cause
computational problem wile determining the optimal minimum solution.

146
 Therefore, it is important to identify a degenerate problem as early as beginning and take the
necessary action to avoid any computational difficulty. The degeneracy can be identified through the
following results:

“In a transportation problem, a degenerate basic feasible solution exists if and only if some partial sum
of supply (row) is equal to a partial sum of demand (column). For example the following transportation
problem is degenerate. Because in this problem

a1 = 400 = b1
a2 + a3 = 900 = b2 + b3

Warehouse Supply
W1 W2 W3
X 20 17 25 400
Plant
Y 10 10 20 500
Unsat.Demand 0 0 0 400
Demand 400 400 500

There is a technique called perturbation, which helps to solve the degenerate problems.

Perturbation Technique:

The degeneracy of the transportation problem can be avoided if we ensure that no partial sum
of ai (supply) and bj (demand) is equal. We set up a new problem where
ai = ai +d i = 1, 2, ……, m bj
= bj j = 1, 2, ……, n -1
bn = bn + md d > 0

This modified problem is constructed in such a way that no partial sum of a i is equal to the bj.
Once the problem is solved, we substitute d = 0 leading to optimum solution of the original
problem.

Example

147
 Consider the following problem
Warehouse Supply
W1 W2 W3
X 20 17 25 400 + d
Plant
Y 10 10 20 500 + d
0 0 0 400 + d
Unsat.Demand
Demand 400 400 500 +3d 1300 + 3d

Now this modified problem can be solved by using any of the three methods viz. North-west
Corner, Least Cost, or VAM.

Transshipment Problem

There could be a situation where it might be more economical to transport consignments in several
sages that is initially within certain origins and destinations and finally to the ultimate receipt points,
instead of transporting the consignments from an origin to a destination as in the transportation
problem.
The movement of consignment involves two different modes of transport viz. road and railways or
between stations connected by metre gauge and broad gauge lines. Similarly it is not uncommon to
maintain dumps for central storage of certain bulk material. These require transshipment.
Thus for the purpose of transshipment the distinction between an origin and destination is
dropped so that from a transportation problem with m origins and n destinations we obtain a
transshipment problem with m + n origins and m + n destinations.
The formulation and solution of a transshipment problem is illustrated with the following
Example.

Example

Consider the following transportation problem where the origins are plants and destinations
are depots.

148
 Depot Supply
W1 W2 W3

A 1 3 15 150
Plant
B 3 5 25 300

Demand 150 150 150 450

When each plant is also considered as a destination and each depot is also considered as an
origin, there are altogether five origins and five destinations. So that some additional cost data
are necessary, they are as follows:
Unit transportation cost From Plant To Plant to

Unit transportation cost From Depot To Depot

To

Depot
X Y Z
X 0 25 2
Depot Y 2 0 3
Z 55 3 0

Plant
A B
X 3 15
Depot Y 25 3
Z 45 55

Now, from the above Tables, we obtain the transportation formulation of the transshipment
problem, which is shown in the following table
Transshipment Table

149
 A B X Y Z Supply
A 0 55 1 3 15 150+450=600
B 2 0 3 5 25 300+450=750
X 3 15 0 25 2 450
Y 25 3 2 0 3 450
Z 45 55 55 3 0 450
Demand 450 450 150+450=600 150+450=600 150+450=600

A buffer stock of 450 which is the total supply and total demand in the original transportation
problem is added to each row and column of the transshipment problem. The resulting
transportation problem has m + n = 5 origins and m + n = 5 destinations.
By solving the transportation problem presented in the above transshipment table, we obtain

x11=150 x13=300 x14=150 x21=3001 x22=450 x33=30

0
x35=150 x44=450 x55=450
The transshipment problem explanation is as follows:

1. Transport x21=300 from plant B to plant A. This increase the availability at plant A to 450
units including the 150 originally available from A.
2. From plant A transport x13=300 to depot X and x14=150 to depot Y.
3. From depot X transport x35=150 to depot Z. Thus, the total cost of transshipment is:

2*300 + 3 * 150 + 1*300 + 2*150 = $1650

Note: The consignments are transported from pants A, B to depots X, Y, Z only according to the
transportation Table 1, the minimum transportation cost schedule is x 13=150 x21=150
x22=150 with a minimum cost of 3450.
Thus, transshipment reduces the cost of consignment movement.
Transportation Problem Maximization

There are certain types of transportation problem where the objective function is to be maximized
instead of minimized. These kinds of problems can be solved by converting the maximization problem
into minimization problem. The conversion of maximization into minimization is done by subtracting
the unit costs from the highest unit cost of the table.
The maximization of transportation problem is illustrated with the following Example 1.8.
Example

150
 A company has three factories located in three cities viz. X, Y, Z. These factories supplies
consignments to four dealers viz. A, B, C and D. The dealers are spread all over the country. The
production capacity of these factories is 1000, 700 and 900 units per month respectively. The net
return per unit product is given in the following table.

Dealer Capacity
A B C D
X 6 6 6 4 1000
Factory
Y 4 2 4 5 700

Z 5 6 7 8 900
Requirement 900 800 500 400 2600

Determine a suitable allocation to maximize the total return.

This is a maximization problem. Hence first we have to convert this in to minimization problem.
The conversion of maximization into minimization is done by subtracting the unit cost of the
table from the highest unit cost.
Look the table, here 8 is the highest unit cost. So, subtract all the unit cost from the 8, and then
we get the revised minimization transportation table, which is given below.

Dealer Capacity
A B C D
X 2 2 2 4 1000=a1
Factory
Y 4 6 4 3 700=a2

Z 3 2 1 0 900=a3
Requirement 900=b1 800=b2 500=b3 400=b4 2600

Now we can solve the problem as a minimization problem.

The problem here is degenerate, since the partial sum of a1=b2+b3 or a3=b3. So consider the
corresponding perturbed problem, which is shown below.

Dealer Capacity
A B C D
X 2 2 2 4 1000+d
151
 Factory
Y 4 6 4 3 700+d

Z 3 2 1 0 900+d

Requirement 900 800 500 400 + 3d 2600

First we have to find out the basic feasible solution. The basic feasible solution by lest cost
method is x11=100+d, x22=700-d, x23=2d, x33=500-2d and x34=400+3d.
Once if the basic feasible solution is found, next we have to determine the optimum solution
using MODI (Modified Distribution Method) method. By using this method we obtain
u1+v1=2 u1+v2= u2+v2=6
2
u2+v3=4 u3+v3= u3+v4=0
1
Taking u1=0 arbitrarily we obtain u1=0,

u2=4, u3=1 and v1=2, v2=3, v3=0

On verifying the condition of optimality, we know that

C12-u1-v2 < 0 and C32-u3-v2 <0

So, we allocate x12=700 - d and make readjustment in some of the other basic variables. The
revised values are:
x11=200+d, x12=800, x21=700 - d, x23=2d, x33=500-3d, and x34=400+3d
u1+v1=2 u1+v2=2 u2+v1=4 u2+v3=4 u3+v3=1 u3+v4=0
Taking u1=0 arbitrarily we obtain
u1=0, u2=2, u3=-1 v1=2, v2=2, v3=2, v4=1
Now, the optimality condition is satisfied.

Finally, taking d=0 the optimum solution of the transportation problem is X 11=200, x12=800,
x21=700, x33=500 and x34=400
Thus, the maximum return is:
6*200 + 6*800 + 4*700 + 7*500 + 8*400 = 15500

152
 BIJU PATNAIK INSTITUTE OF IT & MANAGEMENT STUDIES, BHUBANESWAR
Module- III
Prepared By Mr. A.P. Nanda, Associate Prof. (OM)

Queuing Theory

Introduction:

A flow of customers from finite or infinite population towards the service facility forms a queue
(waiting line) an account of lack of capability to serve them all at a time. In the absence of a
perfect balance between the service facilities and the customers, waiting time is required either
for the service facilities or for the customers arrival. In general, the queuing system consists of
one or more queues and one or more servers and operates under a set of procedures. Depending
upon the server status, the incoming customer either waits at the queue or gets the turn to be
served. If the server is free at the time of arrival of a customer, the customer can directly enter
into the counter for getting service and then leave the system. In this process, over a period of
time, the system may experience “ Customer waiting” and /or “Server idle time”

Queuing System:

A queuing system can be completely described by

(1) the input (arrival pattern)

(2) the service mechanism (service pattern)
(3) The queue discipline and
(4) Customer’s behaviour

Terminologies of Queuing System

Various terminologies to be used in queuing system have been explained as below-

The input (arrival pattern)

The input described the way in which the customers arrive and join the system. Generally,
customers arrive in a more or less random manner which is not possible for prediction. Thus the
153
 arrival pattern can be described in terms of probabilities and consequently the probability
distribution for inter-arrival times (the time between two successive arrivals) must be defined. We
deal with those Queuing system in which the customers arrive in poisson process. The mean arrival
rate is denoted by
.

The Service Mechanism

This means the arrangement of service facility to serve customers. If there is infinite number of
servers, then all the customers are served instantaneously or arrival and there will be no queue. If
the number of servers is finite then the customers are served according to a specific order with
service time a constant or a random variable. Distribution of service time follows ‘Exponential
distribution’ defined by
f (t) = e -t , t > 0
The mean Service rate is E(t) = 1/

Rules of Queue

Queuing

Discipline

It is a rule according to which the customers are selected for service when a queue has been formed.
The most common disciplines are
1. First come first served – (FCFS)
2. First in first out – (FIFO)
3. Last in first out – (LIFO)
4. Selection for service in random order (SIRO)

Customer’s behaviour

A. Generally, it is assumed that the customers arrive into the system one by one. But in
some cases, customers may arrive in groups. Such arrival is called Bulk arrival

154
 B. If there is more than one queue, the customers from one queue may be tempted to join
another queue because of its smaller size. This behaviour of customers is known as
jockeying
C. If the queue length appears very large to a customer, he/she may not join the queue.
This property is known as Balking of customers
D. Sometimes, a customer who is already in a queue will leave the queue in anticipation of
longer waiting line. This kind of departure is known as Reneging.

List of Variables to be used in Queuing Model

The list of variable used in queuing models is give below:

n - No of customers in the
system C - No of servers in
the system
Pn (t) – Probability of having n customers in the system at
time t Pn - Steady state probability of having customers in
the system P0 - Probability of having zero customers in the
system
Lq - Average number of customers waiting in the queue
Ls - Average number of customers waiting in the system (in the queue and in the service
counters) Wq - Average waiting time of customers in the queue.
Ws - Average waiting time of customers in the system (in the queue and in the service counters)
 - Arrival rate of customers
 - Service rate of server
 - Utilization factor of the server
 eff - Effective rate of arrival of
customers M - Poisson distribution
N - Maximum numbers of customers permitted in the system. Also, it denotes the size of the
calling source of the customers.
GD - General discipline for service. This may be first in first – serve (FIFS), last-in-first serve
(LIFS) random order (Ro) etc.

155
 Traffic intensity (or utilization factor)

An important measure of a simple queue is its traffic intensity given by

Traffic intensity  = Mean arrival time = (< 1)

Mean service time

and the unit of traffic intensity is Erlang

Classification of Queuing models

Generally, queuing models can be classified into six categories using Kendall’s notation
with six parameters to define a model. The parameters of this notation are

P- Arrival rate distribution ie probability law for the arrival /inter – arrival time.
Q - Service rate distribution, ie probability law according to which the customers are being served.

R - Number of Servers (ie number of service

stations) X - Service discipline
Y - Maximum number of customers permitted in the
system. Z - Size of the calling source of the customers.

A queuing model with the above parameters is written as (P/Q/R : X/Y/Z)

Model 1: (M/M/1): (GD/ ∞ / ∞) Model

In this model

a) the arrival rate follows poisson (M) distribution

b) Service rate follows poisson distribution (M)
c) Number of servers is 1
d) Service discipline is general disciple (ie GD)
e) Maximum number of customers permitted in the system is infinite (∞)
f) Size of the calling source is infinite (∞)

The steady state equations to obtain, Pn the probability of having customers in the system and the
156
 values for Ls, Lq, Ws and Wq are given below.

n= 0,1,2,---- ∞ where  =  < 1


Ls – Average number of customers waiting in the system (ie waiting in the queue and in the
service station)

Average waiting time of customer (in the queue and in the service station) = Ws

Ws = Ls = 
 (1 - )
= x 1 1
1-  (1 - )

(Since  = )

Ws = 1
 - 

= 1 Ws = 1
-
-

Wq = Average waiting time of customers in the queue.

= Lq /  = [1 / ] [ 2 / [1- ]]

157
 = 1 /  [ 2 / [1- ]]

=  (Since  = 
 - 

Wq = 
-

Explanation of Empirical Queuing Model:

The above discussed queuing models have been thoroughly discussed below with the help
of few examples:

Example

The arrival rate of customers at a banking counter follows a poisson distibution with a mean of
30 per hours. The service rate of the counter clerk also follows poisson distribution with mean of
45 per hour.
a) What is the probability of having zero customers in the system?
b) What is the probability of having 8 customers in the system?
c) What is the probability of having 12 customers in the system?
d) Find Ls, Lq, Ws and Wq

Solution

Given arrival rate follows poisson distribution with mean =30

= 30 per hour
Given service rate follows poisson distribution with mean = 45
 = 45 Per hour
Utilization factor  = /
= 30/45
= 2/3
= 0.67
a) The probability of having zero customer in

158
 the system P0 = 0 (1- )
= 1- 
= 1-0.67
= 0.33
b) The probability of having 8 customers in
the system P8 = 8 (1- )
= (0.67)8 (1-0.67)
= 0.0406 x 0.33
= 0.0134
c) Probability of having 12 customers in the
system is P12 = 12 (1- )
= (0.67)12 (1-0.67)
= 0.0082 x 0.33
= 0.002706

Ls =  = 0.67
1- 0.67
1- 
= 0.67 = 2.03
0.33
= 2 customers
= (0.67)2 = 0.4489
1-0.67 0.33

159
 Example

At one-man barbar shop, customers arrive according to poisson dist with mean arrival
rate of 5 per hour and the hair cutting time was exponentially distributed with an
average hair cut taking 10 minutes. It is assumed that because of his excellent
reputation, customers were always willing to wait. Calculate the following:

(i) Average number of customers in the shop and the average numbers
waiting for a haircut.
(ii) The percentage of time arrival can walk in straight without having to wait.
(iii) The percentage of customers who have to wait before getting into the
barber’s chair.

Solution:-

Given mean arrival of customer 

and mean time for server 

= 5/60 =1/12 1/10

= /  = [1/12] x 1 = 10 /12

= 0.833
(i) Average number of customers in the system (numbers in the
queue and in the

service station) Ls =  / 1-  = 0.83 / 1- 0.83

= 0.83 / 0.17

= 4.88

= 5 Customers

(ii) The percentage of time arrival can walk straight

into barber’s chair without waiting is Service
utilization =
%

=/%
= 0.833 x 100

= 83.3 %

160
 (iii) The percentage of customers who have to wait before
getting into the barber’s chair = (1-) % (1- 0.833) % =
0.167 x 100 = 16.7%

Example

Vehicles are passing through a toll gate at the rate of 70 per hour. The average time to
pass through the gate is 45 seconds. The arrival rate and service rate follow poisson
distibution. There is a complaint that the vehicles wait for a long duration. The
authorities are willing to install one more gate to reduce the average time to pass
through the toll gate to 35 seconds if the idle time of the toll gate is less than 9% and
the average queue length at the gate is more than 8 vehicle, check whether the
installation of the second gate is justified?

Solutions:-

Arrival rate of vehicles at the toll gate 

=70 per hour Time taken to pass through the

gate= 45 Seconds

Service rate  = 1 hours

45 seconds

= 3600/45 = 80

= 80 Vehicles per hour

 Utilization factor  = /

= 70 / 80

= 0.875

(a) Waiting no. of vehicles in the queue is Lq

Lq = 2 / 1 -  = (0.875)2
1-0.875
= 0.7656
0.125

= 6.125

161
 = 6 Vehicles

(b) Revised time taken to pass through the gate = 30 seconds

The new service rate after installation of an additional gate = 1 hour/35

Seconds = 3600/35

= 102.68 Vehicles / hour

 Utilization factor  =  /  = 70 / 102.86 = 0.681

Percentage of idle time of the gate = (1-)%

= (1-0.681) %

= 0.319 %
= 31.9 = 32 %

This idle time is not less than 9% which is expected.

Therefore the installation of the second gate is not justified since the average
waiting number of vehicles in the queue is more than 8 but the idle time is not less
than 32%. Hence idle time is far greater than the number of vehicles waiting in the
queue.

Explanation of Second Model; (M/M/C): (GD/ ∞/∞ )Model

The parameters of this model are as
follows:

(i) Arrival rate follows poisson distribution

(ii) Service rate follows poisson distribution
(iii) No of servers is C’.
(iv) Service discipline is general discipline.
(v) Maximum number of customers permitted in the system is infinite

Then the steady state equation to obtain the probability of

having n customers in the system is Pn =  n Po ; onC
n!
=  n Po for n >
c; Where  / c < 1 C
n-c C!

Where [ / c] < 1 as  =  / 

162
 C-1
 P0 = {[ n/n!] + c / (c! [1 - /c])}-1
n=0
where c! = 1 x 2 x 3 x .............. up to C
Lq = [ c+1 / [c-1! (c -  )] ] x P0
= (c Pc) / (c -  )2

Ls = Lq +  and Ws = Wq + 1 / 

Wq = Lq / 

Under special conditions Po = 1 -  and Lq =  C+! / c 2 Where  <1 and Po = (C-) (c –

1)! / c c

and Lq =  / (c- ), where  / c < 1

Example

At a central warehouse, vehicles are at the rate of 24 per hour and the arrival rate
follows poisson distribution. The unloading time of the vehicles follows exponential
distribution and the unloading rate is 18 vehicles per hour. There are 4 unloading
crews. Find
(i) Po and P3
(ii) Lq, Ls, Wq and Ws

Solution:
Arrival rate
 = 24 per
hour
Unloading
rate  = 18
per hour No.
of unloading
crews C=4
=/  = 24 / 18=1.33

C-1
(i) P0 ={[ n/n!] + c / (c! [1 - /c])}-1
n=0
3
= {[ (1.33)n/n!] + (1.33)4 /(4! [1 - (1.33)/ 4])}-1

163
 n=0

= { (1.33)0 / = 0! + (1.33)1 / 1! + (1.33)2 / 2! + (1.33)3 / 3! +

(1.33)4 / 24! [1 - (1.33)/ 4] }-1

= [1 + 1.33 + 0.88 + 0.39 + 3.129/16.62] -1

= [3.60 + 0.19]-1 = [3.79]-1

= 0.264

We know Pn = ( n / n!) Po for 0nc

 P3 = ( 3 / 3!) Po Since 0  3  4
= [(1.33)3 / 6 ] x 0.264

= 2.353 x 0.044

= 0.1035

(ii) Lq = C+1 X P0 (C – 1)! (C-)2

= (1.33)5 X 0.264
2
3! X (4 – 1.33)

= (4.1616) X
6 X (2.77)2
0.264

= (4.1616) X 0.264
46 .0374
= 1.099 / 46.0374
= 0.0239

Ls =
=
Lq + 
0.0239 Vehicles
= 0.0239 + 1.33

Wq = Lq / 
= 1.3539 Vehicles
= 0.0239 /24
= 0.000996 hrs

164
 Ws = Wq + 1 /  = 0.000996 + 1/18
= 0.000996 + 0.055555

= 0.056551 hours.

Example

A supermarket has two girls ringing up sales at the counters. If the service time
for each customer is exponential with mean 4 minutes and if the people arrive
in poisson fashion at the rate of 10 per hour
a) What is the probability of having to wait for service?
b) What is the expected percentage of idle time for each girl?
c) If a customer has to wait, what is the expected length of his waiting time?

Solution:-
C-1
P0 ={[ n/n!] + c / (c! [1 - /c])}-1
n=0

Where  =  /   given arrival rate = 10 per hour

 = 10 / 60 = 1 / 6

per minute

Service rate = 4

minutes
=1/4 person per minute

Hence,  =  /  = (1 / 6) x 4
=2/3
= 0.67
1
P0 = {[ n/n!] + (0.67)2/(2! [1 - 0.67/2])}-1
n=0
= [1 + (  / 1!) ] + 0.4489 / (2 – 0.67)]-1
= [1 + 0.67 + 0.4489 / (1.33)]-1

= [1 + 0.67 + 0.34]-1

= [ 2.01]-1 = 1/ 2

165
 The Probability of having to wait for the service is
P (w > 0)
= c X P0 c! [1 -  /c]

= 0.67 2 X (1 / 2)
2! [1 – 0.67 /2]

= 0.4489 / 2.66

= 0.168

b) The probability of idle time for each girl is

= 1- P (w > 0)

= 1 - 1/3
= 2/3
 Percentage of time the service remains idle = 67% approximately

c) The expected length of waiting time (w/w>0)

= 1 / (c  - )
= 1 / [(1 / 2) – (1 / 6)]

= 3 minutes

Examples

A petrol station has two pumps. The service time follows the exponential distribution
with mean 4 minutes and cars arrive for service in a poisson process at the rate of 10
cars per hour. Find the probability that a customer has to wait for service. What
proportion of time the pump remains idle?

Solution: Given C = 2
The arrival rate = 10 cars per hour.
 = 10 / 60 =1
/ 6 car per minute
Service rate = 4
minute per cars.

i.e  = ¼ car per minute.

 =  /  = (1/6) / (1/4)
=2/3

166
 = 0.67
Proportion of time the pumps remain busy =  / c = 0.67 / 2 = 0.33 = 1/3

 The proportion of time, the pumps remain idle

= 1 – proportion of the pumps remain busy
= 1-1 / 3 =2/3
C-1
P0 ={[ n/n!] + c / (c! [1 - /c])}-1
n=0

= [ (0.67)0 / 0!) + (0.67)1 / 1!) + (0.67)2 / 2!) [1- (0.67 / 2)1 ]-1

= [1 + 0.67 + 0.4489 / (1.33)]-1

= [1 + 0.67 + 0.33]-1

= [2]-1

=1/2

Probability that a customer has to wait for service

= p [w>0]

= c x P0 = (0.67)2 x ½
[c [1 -  / c] [2![1 – 0.67/2]
=
0.4489 = 0.4489

1.33x2 = 2.66
= 0.16

167
 Markov Process
Introduction
Markov chains are an important mathematical tool in stochastic processes. The underlying
idea is the Markov Property, in order words, that some predictions about stochastic
processes can be simplified by viewing the future as independent of the past, given the
present state of the process. This is used to simplify predictions about the future state of a
stochastic process. This report will begin with a brief introduction, followed by the analysis,
and end with tips for further reading. The analysis will introduce the concepts of Markov
chains; explain different types of Markov Chains and present examples of its applications in
finance.

Andrei Markov was a Russian mathematician who lived between 1856 and 1922. He was a
poorly performing student and the only subject he didn’t have difficulties in was
mathematics. He later studied mathematics at the university of Petersburg and was lectured
by Pafnuty Chebyshev, known for his work in probability theory. Markov’s first scientific
areas were in number theory, convergent series and approximation theory. His most famous
studies were with Markov chains, hence the name and his first paper on the subject was
published in 1906. He was also very interested in poetry and the first application he found of
Markov chains was in fact in a linguistic analysis of Pusjkins work Eugene Onegin.

Purpose
The purpose of this report is to give a short introduction to Markov chains and to present
examples of different applications within finance.

Definition 1. A stochastic process is a sequence of events in which the outcome at any stage
depends on some probability.

Definition 2. A Markov process is a stochastic process with the following properties:

(a.) The number of possible outcomes or states is finite.
(b.) The outcome at any stage depends only on the outcome of the previous stage.
(c.) The probabilities are constant over time.

If x0 is a vector which represents the initial state of a system, then there is a matrixM such
that the state of the system after one iteration is given by the vector Mx0. Thus we get a
chain of state vectors: x0,Mx0,M2x0, . . . where the state of the system after n iterations is
given by Mnx0. Such a chain is called a Markov chain and the matrix M is called a transition
matrix.

The state vectors can be of one of two types: an absolute vector or a probability vector. An
absolute vector is a vector whose entries give the actual number of objects in a give state, as
in the first example. A probability vector is a vector where the entries give the percentage
(or probability) of objects in a given state. We will take all of our state vectors to be
probability vectors from now on. Note that the entries of a probability vector add up to 1.

Introduction to Markov chains

Markov chains are a fundamental part of stochastic processes. They are used widely in many

168
different disciplines. A Markov chain is a stochastic process that satisfies the Markov
property, which means that the past and future are independent when the present is
known. This means that if one knows the current state of the process, then no additional
information of its past states is required to make the best possible prediction of its future.
This simplicity allows for great reduction of the number of parameters when studying such a
process. [2]In mathematical terms, the definition can be expressed as follows: A stochastic
process X = ,Xn, n ε N- in a countable space S is a discrete-time Markov chain if:

For all n ≥ 0, Xn ε S For all n ≥ 1 and for all i0, ... in−1, in ε S, we have : P, Xn = in | Xn−1 =
in−1, ... , X0 = i0 - = P, Xn = in| Xn−1 = in−1 - *2+
Markov chains are used to compute the probabilities of events occurring by viewing them as
states transitioning into other states, or transitioning into the same state as before. We can
take weather as an example: If we arbitrarily pick probabilities, a prediction regarding the
weather can be the following: If it is a sunny day, there is a 30% probability that the next day
will be a rainy day, and a 20% probability that if it is a rainy day, the day after will be a sunny
day. If it is a sunny day, there is therefore a 70% chance that the next day will be another
sunny day, and if today is a rainy day, there is a 80% chance that the next day will be a rainy
day as well. This can be summarized in a transition diagram, where all of the possible
transitions of states are described:

To approach this mathematically one views today as the current state, S0 , which is a 1 × m
vector. The elements of this vector will be the current state of the process. In our weather
example, we define S = [Sunny Rainy] . Where S is called our state space, in which all the
elements are all the possible states that the process can attain. If, for example, today is a
sunny day, then the S0 vector will be S0 = [1 0] , because there is 100% chance of a sunny
day and zero chance of it being a rainy day. To get to the next state, the transition
probability matrix is required, which is just the state transition probabilities summarized in a
matrix. In this case it will be as follows:

To get to the next state, S1 , you simply calculate the matrix product S1 = S0P . Since
calculations for successive states of S is only of the type Sn = Sn−1P , the general formula for
computing the probability of a process ending up in a certain state is Sn = S0P . This allows
n for great simplicity when calculating the probabilities far into the future. For example, if
today is a sunny day then the state vector 120 days from now, S120 , is S120 = [0.4 0.6] . [3]

169
Explanation of different concepts regarding Markov chains
When approaching Markov chains there are two different types; discrete-time Markov
chains and continuous-time Markov chains. This means that we have one case where the
changes happen at specific states and one where the changes are continuous. In our report
we will mostly focus on discrete-time Markov chains.

One example to explain the discrete-time Markov chain is the price of an asset where the
value is registered only at the end of the day. The value of the Markov chain in discrete-time
is called the state and in this case the state corresponds to the closing price. A continuous-
time Markov chain changes at any time. This can be explained with any example where the
measured events happens at a continuous time and lacks “steps” in its appearance. One
well known example of continuous-time Markov chain is the poisson process, which is often
practised in queuing theory. [1]

For a finite Markov chain the state space S is usually given by S = {1, . . . , M} and the
countable infinite state Markov chain state space usually is taken to be S = {0, 1, 2, . . . }.
These different variances differ in some ways that will not be referred to in this paper. [4] A
Markov chain can be stationary and therefore be independent of the initial state in the
process. This phenomenon is also called a steady-state Markov chain and we will see this
outcome in the example of market trends later on, where the probabilities for different
outcomes converge to a certain value. However, an infinite-state Markov chain does not
have to be steady state, but a steady-state Markov chain must be time-homogenous. Which
by definition means that the transition probabilities matrix Pi, j (n, n + 1) is independent of
n.
[3]
Application areas of Markov chains
Since Markov chains can be designed to model many real-world processes, they are used in
a wide variety of situations. These fields range from the mapping of animal life populations
to search-engine algorithms, music composition and speech recognition. In economics and
finance, they are often used to predict macroeconomic situations like market crashes and
cycles between recession and expansion. Other areas of application include predicting asset
and option prices, and calculating credit risks. When considering a continuous-time financial
market Markov chains are used to model the randomness. The price of an asset, for
example, is set by a random factor – a stochastic discount factor – which is defined using a
Markov chain [5].

Application of Markov chains to credit risk measurement

In the application of Markov chains to credit risk measurement, the transition matrix
represents the likelihood of the future evolution of the ratings. The transition matrix will
describe the probabilities that a certain company, country, etc. will either remain in their
current state, or transition into a new state. [6] An example of this below:

170
The main problem in this application is determining the transition matrix. Of course, these
probabilities could be estimated by analysing historical data from credit rating agencies,
such as Standard & Poor, Moody’s and Fitch. This can, though, lead to unreliable numbers in
case the future does not develop as smoothly as in the past. It can therefore be more
reliable to base the estimations on a combination of empirical data and more subjective,
qualitative data such as opinions from experts. This is because the market view is a mixture
of beliefs determined by both historical ratings and a more extreme view of the ratings. To
combine different sources of information in this way, one may use credibility theory.
Actuarial credibility theory provides a consistent and convenient way of how to combine
information, and how to weigh the different data sources. [6]
Another problem with deciding the transition matrix is that maybe it is not appropriate to
use a homogenous Markov chain to model credit risk over time. This is because it does not
capture the time-varying behaviour of the default risk. Of course, a non-homogeneous
model could be more realistic - but on the other hand much more complicated to use. [6]

Markov chains to predict market trends

Markov chains and their respective diagrams can be used to model the probabilities of
certain
financial market climates and thus predicting the likelihood of future market conditions [7].
These conditions, also known as trends, are:
 Bull markets: periods of time where prices generally are rising, due to the actors
having optimistic hopes of the future.
 Bear markets: periods of time where prices generally are declining, due to the actors
having a pessimistic view of the future.
 Stagnant markets : periods of time where the market is characterized by neither a
decline nor rise in general prices.

In fair markets, it is assumed that the market information is distributed equally among its
actors and that prices fluctuate randomly. This means that every actor has equal access to
information such that no actor has an upper hand due to inside-information. Through
technical analysis of historical data, certain patterns can be found as well as their estimated
probabilities. [7] For example, consider a hypothetical market with Markov properties
where historical data has given us the following patterns: After a week characterized of a
bull market trend there is a 90% chance that another bullish week will follow. Additionally,
there is a 7.5% chance that the bull week instead will be followed by a bearish one, or a
2.5% chance that it will be a stagnant one. After a bearish week there’s an 80% chance that
the upcoming week also will be bearish, and so on. By compiling these probabilities into a
table, we get the following transition matrix M :

171
We then create a 1x3 vector C which contains information about which of the three
different states any current week is in; where column 1 represents a bull week, column 2 a
bear week and column 3 a stagnant week. In this example we will choose to set the current
week as bearish, resulting in the vector C = [0 1 0].

Given the state of the current week, we can then calculate the possibilities of a bull, bear or
stagnant week for any number of n weeks into the future. This is done by multiplying the
vector C with the matrix , giving the following:

172
From this we can conclude that as n → ∞, the probabilities will converge to a steady state,
meaning that 63% of all weeks will be bullish, 31% bearish and 5% stagnant. What we also
see is that the steady-state probabilities of this Markov chain do not depend upon the initial
state [3]. The results can be used in various ways, some examples are calculating the
average time it takes for a bearish period to end, or the risk that a bullish market turns
bearish or stagnant.
Theorem 3. Let M be the transition matrix of a Markov process such that Mk has only
positive entries for some k. Then there exists a unique probability vector X 8 such that Mx8 =
xs. Moreover limk LMkx0 = x8 for any initial state probability vector x0.
The vector xs is called a the steady-state vector.
The Transition Matrix and its Steady-State Vector

The transition matrix of an n-state Markov process is an n×n matrix M where the i, j entry of
M represents the probability that an object is state j transitions into state i, that is if M =
(mij) and the states are S1, S2, . . . , Sn then mij is the probability that an object in state Sj
transitions to state Si. What remains is to determine the steady-state vector. Notice that we
have the chain of equivalences:

Mxs = xs , Mxs − xs = 0 , Mxs − Ixs = 0 , (M − I)xs = 0 , xs 2 N(M − I) Thus xs is a vector in the

nullspace of M −I. If Mk has all positive entries for some k, then dim(N(M −I))=1

Example:
A certain protein molecule can have three configurations which we denote as C1,C2 and C3.
Every second the protein molecule can make a transition from one configuration to another
configuration with the following probabilities:

173
 SIMULATION
Simulation (Definition)

I. Simulation means imitation of a situation or process.

II. A simulation of a system is the operation of a model of the system.
III. Simulation is used before an existing system is altered or a new system built,
to reduce the chances of failure.
IV. Define simulation as ‘an experiment performed on a mathematical model’.
V. Simulation is “the process of designing a model of a real system and
conducting experiments with this model for the purpose either of
understanding the behavior of the system or of evaluating various
strategies for the operation of the system.”
VI. Asics of simulation, including structure, function, data generated, and its proper
use.
VII. Simulation may be performed through;
1) solving a set of equations (a mathematical model),
2) Constructing a physical model,
3) Game (such as war-games), or a computer graphics model (such as an
animation).

Term Used in Simulation:

1) System: A group of objects that are joined together in some regular

interaction or interdependence toward the accomplishment of some
purpose.

2) Entity: An object of interest in the system. Example: customers at a bank

3) Attribute: A property of an entity. Example, checking account balance

4) Activity: Represents a time period of specified length. Collection of

operations that transform the state of an entity. Example, making bank
deposits.

5) Event: change in system state. Example arrival, beginning of a new execution,

departure etc.

6) State Variables: Define the state of the system. Can restart

simulation from state variables.Example, length of the job queue.

7) Process: Sequence of events ordered on time

174
 Example of a System with their Components

Bank (As a System)

System Entity Attribute Activity Event State
Variable
s
Banking Customer Checkin Making Arrival Busy
g Deposit Departur Teller,
Account s e Custome
Balance rWaiting
Process Sequence of events
ordered on time

System:
ii. A system can be anything.
iii. A system is a collection of elements or components that are organized for a
common purpose.
iv. A system is a potential source of data.
v. An unit or process, which exists and operates in time and space through the
interaction of its parts.

Components of System:

Entity: An object of interest in the system : Machines in factory

Attribute: The property of an entity : speed, capacity
Activity: A time period of specified length :welding, stamping
State Variables: A collection of variables that describe the system in any time :
status of machine (busy,idle, down,…)
Event: A instantaneous occurrence that might change the state of the system (e.g.
breakdown.) Endogenous: Activities and events occurring with the system
(growing or originating from within anSystem)
Exogenous: Activities and events occurring with the environment (growing or
originating from outside anorganism)

175
 Classification of a System:

How to Study a System?

Example: A Computer System

A computer system which consist of base unit, monitor, keyboard, mouse, speaker,
printers. So these are theisolated part of reality that we wish to study through
scientific inquiry (simulation).

Computer System Modeling of Computer System (Model)

We study the system by experimenting with it, but as far as concern with Simulation,
we go for making a model of it and then proceed for the simulation. According to
system which is a potential source of data.so an experiment is the process of
extracting data from a system by exerting it through its inputs. Consider a Bank is a
system and their components are describes below;

176
 Example of a System with their
Components
Bank (As a System)
System Entity Attribute Activity Event State
Variables
Banking Customer Checkin Making Arrival Busy
g Deposit Departur Teller,
Account s e Custome
Balance r
Waiting
Process Sequence of
eventsordered
on time

Model:

1) Model means a three-dimensional (3D) representation of a things or structure.

2) A Representation of an object, a system, or an idea in some form other than that
of the entity itself.
3) A simplified representation of a real or theoretical system at some particular
point in time or spaceintended to provide understanding of the system.
4) The Model can be Classified into two types which are;
i. Physical: (Scale models, prototype plants etc.)
ii. Mathematical: (Analytical queuing models, linear programs, simulation
etc.)

Object Model
What is modeling?

1) Modeling is the process of producing a model

2) A model is a representation of the construction and working of system of interest.
3) One purpose of a model is to enable the analyst to predict the effect of changes
to the system.
4) A good model is a judicious tradeoff between realism and simplicity.
5) Generally, a model intended for a simulation study is a mathematical

177
 model developed with thehelp of simulation software.

Classification of System Model:

Types of Mathematical Models in Simulation:

Although many ideas exist but generally well accepted distinction is in the following three
types:

1. Continuous time models ; (In continuous time models the state of a

system changes continuouslyover time.)
2. Discrete time models ; (With discrete time models, the time axis is discretised
i.e. The time-step usedin the discrete-time model is constant.)
3. Discrete event models.(In discrete-event models, the state is discretised and
"jumps" in time. Eventscan happen any time but only every now and then at
(stochastic) time intervals.)

Types of Simulation:

Continuous-state simulation is applicable to systems where the notion of state is

continuous and typically involves solving (numerically) systems of differential

178
 equations. Circuit-level simulators are an example of continuous-state simulation.

Discrete-event simulation is applicable to systems in which the state of the system

changes at discrete instants of time, with a finite number of changes occurring in any
finite interval of time.

Simulation models can be classified into the following 4 categories:

1) Deterministic models: In these models, input and output variables are not
permitted to berandom variables and models are described by exact
functional relationship.
2) Stochastic models: In these models, at least one of the variables or
functional relationshipis given by probability functions.
3) Static models: These models do not take variable time into consideration.
4) Dynamic models: These models deal with time varying interaction.

Advantages of simulation models:

1) Simulation models are comparatively flexible, and can be modified to adjust

according to the variation in the environments of real life situations.
2) Simulation is easier to use than mathematical models and is hence considered
superior to mathematical analysis.
3) Simulation techniques have the advantage of being relatively free from
complicated mathematics and hence, can be easily understood by the
operating staff and also by non- technical managers.
4) Simulation offers up a solution by performing virtual experimentation with a
model of the system without interfering with the real system. It thus bypasses
complex mathematical analysis.
5) Simulation compresses the performance of a system over several years, and
hence performslarge calculations in a few minutes of computer running time.
6) By using simulation, management can foresee the difficulties and bottlenecks
that may arise due to addition of new machines or equipment, or by
modifying a process. It eliminates the need for costly trial and error methods
of trying out a new concept on real processes and equipment.
7) It is better to train people on a simulated model, rather than putting them to
work straightaway on the real system. Simulation develops the trainee
making him experienced and an expert, due to which the trainee now has
sufficient confidence in handling the real system.

Disadvantages of simulation models:

1) Optimum results cannot be produced by simulation. Since the models only

deal with uncertainties, results of simulation are merely reliable
approximations involving statistical errors.

179
 2) In many situations, it isn’t possible to quantify all the variables which play a
role in the system.
3) In large, complex problems involving many variables and their inter-
relationships, the capacity of the computer may not be enough to process the
entire system.
4) Since computers are involved in simulation, it makes simulation a
comparatively costlier technique to use.
5) Simulation is sometimes applied to simple problems, due to over reliance on
simulation, when in fact the problems could be solved in an easier manner by
some other technique like mathematical analysis.

Steps of Simulation Process:

The steps involved in developing a simulation model, designing a simulation

experiment, and performingsimulation analysis are:

Step 1. Identify the problem.

Step 2. Formulate the problem.
Step 3. Collect and process real system
data.
Step 4. Formulate and develop a model.
Step 5. Validate the model.
Step 6. Document model for future use.
Step 7. Select appropriate experimental design. Step 8. Establish experimental
conditions for runs.
Step 9. Perform simulation runs.
Step 10. Interpret and present results.
Step 11. Recommend further course of action

180
 Different Steps in Simulation

HOW TO DEVELOP A SIMULATION MODEL?

Simulation models consist of the following components:

5) system entities,
6) input variables,
7) performance measures,
8) functional relationships.

Indeed, a simulation study is as good as the simulation model. Simulation

modeling comprises thefollowing steps:
Step 1. Identify the problem: Enumerate problems with an existing system.

Step 2. Formulate the problem. Select the bounds of the system, and define
overall objective ofthe study and a few specific issues to be addressed.

Step 3. Collect and process real system data. Collect data on system
specifications (e.g., bandwidth for a communication network), input variables,
as well as performance of the existingsystem.

Step 4. Formulate and develop a model. Develop schematics and network

diagrams of the system(How do entities flow through the system?). Translate
these conceptual models to simulation software acceptable form.

Step 5. Validate the model. Compare the model's performance under known
conditions with theperformance of the real system.

181
Step 6. Document model for future use. Document objectives, assumptions and input
variables indetail. Simulation experiment is a test or a series of tests in which meaningful
changes are made to the input variables of a simulation model so that we may observe
and identify the reasons for changes in the performance measures.

Step 7. Select appropriate experimental design. Select a performance measure, a few

inputvariables that are likely to influence it, and the levels of each input variable.

Step 8. Establish experimental conditions for runs. Address the question of obtaining
accurate information and the most information from each run. Determine if the system
is stationary (performance measure does not change over time) or non-stationary
(performance measure changesover time).

Step 9. Perform simulation runs. Perform runs according to steps 7-8 above. Most
simulation packages provide run statistics (mean, standard deviation, minimum value,
maximum value) on the performance measures, e.g., wait time (non-time persistent
statistic), inventory on hand (time persistent statistic).

Step 10. Interpret and present results. Compute numerical estimates (e.g., mean,
confidence intervals) of the desired performance measure for each configuration of
interest.

Step 11. Recommend further course of action. This may include further experiments to
increase the precision and reduce the bias of estimators, to perform sensitivity analyses,
etc.

What Makes A Problem Suitable For Simulation Modeling And Analysis?

More specifically, situations in which simulation modeling and analysis is used include the
following:

A. It is impossible or extremely expensive to observe certain processes in the

real world, e.g., next year's cancer statistics, performance of the next space
shuttle, and the effect of Internet advertisingon a company's sales.

B. Problems in which mathematical model can be formulated but analytic

solutions are either impossible (e.g., job shop scheduling problem, high
order difference equations) or too complicated(e.g., complex systems like
the stock market, and large scale queuing models).

It is impossible or extremely expensive to validate the mathematical model

describing the system, e.g., dueto insufficient data.

182
 How to select Simulation Software?

Although a simulation model can be built using general purpose programming languages which
are familiar to the analyst, available over a wide variety of platforms, and less expensive, most
simulation studies today are implemented using a simulation package.

The advantages are reduced programming requirements; natural framework for simulation
modeling; conceptual guidance; automated gathering of statistics; graphic symbolism for
communication; animation; and increasingly, flexibility to change the model.

General Purpose Languages used for Simulation:

FORTRAN: Probably more models than any other language.

PASCAL: Not as universal as FORTRAN
MODULA: Many improvements over PASCAL
ADA: Department of Defense attempt at standardization
C, C++: Object-oriented programming language

Modeling With General Purpose Languages:

Advantages:

1) Little or no additional software cost

2) Universally available (portable)
3) No additional training (Everybody knows…(language X) ! )
Disadvantages:

1) Every model starts from scratch

2) Very little reusable code
3) Long development cycle for each model
4) Difficult verification phase
183
 Advantages of Simulation:

9) Obtain a better understanding of the system by developing a mathematical model

of a system.
10) Test hypotheses about the system for feasibility.
11) Expand time to observe a complex phenomenon in detail so that you can
investigate them better.
12) Study the effects of informational, organizational, environmental and
policy changes on theoperation of a system.
13) Experiment with new or unknown situations
14) Employ a systems approach to problem solving.
15) Develop well designed and robust (strong and healthy) systems and reduce time.
16) Choose correctly for every aspect of a proposed change or addition in the system
17) Explore possibilities such new policies, operating procedures or
methods without the need ofexperimenting with the real world
systems.
18) Diagnose problems among the variables that make up the complex system.
19) Develop understanding about how a system really operates and predictions
about how a system willoperate.
20) Visualize the plan to see your how the system actually running.
21) Build consensus about a system, how the system works, so provide an objective
opinion.
22) Prepare for change to determining future improvements and new designs on a
system.
23) Train the team; simulation can provide excellent training when design for that
purpose.
24) Specify requirements used to determine requirements for a system design
by simulating differentpossible configurations of a system.

Disadvantages of Simulation:

25) Model building requires special training; Simulation is an art that is learned
over time and through experience. Building a realistic model may require
domain knowledge regarding simulation from an expert.
26) Simulation results may be difficult to interpret because simulation results are
essentially random variables, It may be hard to determine result of system
interrelationships.
27) Simulation modeling and analysis can be time consuming and expensive
28) Simulation may be used inappropriately when analytical solution is possible, or
even preferable.
29) Unclear objective.
30) Invalid model.

184
 31) Simulation model too complex or too simple.
32) Undocumented Assumptions.
33) A good simulation model may be very expensive.

Application of Simulations:
1) Designing and analyzing manufacturing systems.(Example: Manufacturing Plant,
Organization etc.)
2) Evaluating Hardware and Software requirements for a computer system.
3) Evaluating a new military weapons system.
4) Determining ordering policies for an inventory system
5) Designing and operating transportation facilities such as freeways, airports,
subways, or ports
6) Evaluating designs for service organizations such as hospitals, post offices, or fast-
food restaurants
7) Analyzing financial or economic systems.(Example: Banks).

Some Application Areas of Simulation:

1) Medical research, training & support

2) Industrial engineering designs & presentations (Factory process design,
manufacturing, ...)
3) Civil engineering designs & presentations (Building design, city & infrastructure
planning, ...)
4) Mechanical engineering designs & presentations (Engine designs, aerodynamic
design, ...)
5) Nature sciences (Physic, chemistry, biology, meteorology, astronomy, ...)
6) Geographic Information Systems (Earth modeling, ...)
7) Military Decision Support (War modeling, ...)
8) Training (Simulators, games, ...)
9) Entertainment (Games, ...)

Stochastic Simulation:

34) In a situation where the cause & effect relationship is randomly determined
the stochastic model is used.
35) A stochastic model has one or more stochastic elements. The system having
stochastic element is generally not solved by analytic methods.
36) In case of simulating a stochastic model, a random number is normally
generated by some methods or the other methods to execute trail. Such
simulation is called the Monte Carlo Method or Monte Carlo Simulation.
37) In case of stochastic element in the Simulation are two or more persons and
there is a competitive situation or some types of game being reproduced, this

185
 is known as Gaming Simulation.
38) In stochastic model, unique input leads to different output for each model
run, due to the random component of the modeled process, single simulation
given only one possible result.
39) In stochastic model, multiple runs (sequence of activities) are used to
estimate probability distribution.

Deterministic Simulation:

1) A deterministic model is used in that situation wherein the result is

established straight forwardlyfrom a series of condition.
2) A deterministic model has no stochastic elements and the entire input and
output relation of themodel is conclusively determined.
3) A dynamic model & a static model are included in the deterministic model.
4) Simulation by the deterministic model can be considered, there are no
random elements in thedeterministic model, and simulation can well be
done just one.
5) However in case the initial conditions are to be varied, simulation has to be
repeated by changingdata.
6) In deterministic model, equation can be solved by different numerical methods
such as;
i. Finite Difference Methods
ii. Finite Element Methods
iii. Path Simulation Methods

186
 Event Type Simulation:

• Example: Customer arrives at a one man barber shop.

• The problem is to analyze the system in order to evaluate the quality of

service and economicfeasibility offering the service.

• To measure the quality of service one has to make the assessment of the
average waiting time percustomer and the percentages of the time the
barber remains idle.

• For construction of a model of this system, the changes to analysis of the

system can occurs only ifa customer arrives for service or departs after
completion of service.

• If a customer arrives at barber’s shop, he will have to wait, if the barber is

busy. On the other hand, a departure of customer, after being served,
indicates that the barber is available to serve the waiting customer if any.

Let,
service is determined from service time and this generated Ed at t3.

Both Ed (at t1) & Ed (at t3) are now stored chronologically, so that the simulator
recognizes that Ea occursbefore Ed. The next event to be considered is Ea at t2 and
this point Ea at t1 is deleted from the stored list.

The event Ea at t2 generates Ea at t4. Since the facility is busy, the arriving customer
Ea (at t2) joins awaiting line. Now Ea at t4 is deleted from the list and Ed at t3 is
considered next.

At this time a customer is taken from the waiting line & departure event Ed at t5 is
generated , the processrepeated until the entire simulated period “T” is covered.

Example-1:

Customers arrive at a milk booth required service. Assume that inter-arrival service
times are constant andgiven by 1.8 & 4 times units respectively. Simulate the system
by hand computation for 14 times units.

i. What is the average waiting time per customer?

ii. What is the percentages idle time of the facility? (Assume System start at t=0)

187
 Step-1:

Customer-1 t=0 Departure Time, t= 0+4=4

Customer-2 t= 0+1.8 1.8
Customer-3 t= 1.8+1.8 3.6
Customer-4 t=3.6+1.8 5.4
Customer-5 t= 5.4+1.8 7.2
Customer-6 t= 7.2+1.8 9.0
Customer-7 t= 9.0+1.8 10.8
Customer-8 t= 10.8+1.8 13.6

Step-2:

Time Event Customer Waiting Time

0.0 Ea 1
1.8 Ea 2
3.6 Ea 3
4.0 Ed 1 4-1.8= 2.2 (Customer-
2)
5.4 Ea 4
7.2 Ea 5
8.0 Ed 2 8-3.6= 4.4 (Customer-
3)
9.0 Ea 6
10.8 Ea 7
12.0 Ed 3 12-5.4= 6.6 (Customer-
4)
13.6 Ea 8
14.0 End --

For Customer-5, 14-7.2= 6.8

Customer-6, 14-9.0=5.0

Customer-7, 14-10.8=3.2

Customer-8, 14-13.6=0.4

It is evident from this simulation that the average waiting time per customer is;

(2.2+4.4+6.6+6.8+5.0+3.2+0.4)/8=28.7/8= 3.57

Average waiting time per customer for whose, who must wait is 28.7/8=4.08

And the percentage of idle time of the facility = 0%

188
 Example:-2

Customer arrives at a Restaurant required service. Assume that inter-arrival service

times are constant and given by 2.5 & 5 times units respectively. Simulate the system by
hand computation for 20 times units.

i. What is the average waiting time per customer?

ii. What is the percentages idle time of the facility? (Assume System start at t=0)

Solution Step-1

Customer-1 t=0 Departure Time, t= 0+4=4

Customer-2 t= 0+1.8 1.8
Customer-3 t= 1.8+1.8 3.6
Customer-4 t=3.6+1.8 5.4
Customer-5 t= 5.4+1.8 7.2
Customer-6 t= 7.2+1.8 9.0
Customer-7 t= 9.0+1.8 10.8
Customer-8 t= 10.8+1.8 13.6

Step-2:

Time Event Customer Waiting Time

0.0 Ea 1
1.8 Ea 2
3.6 Ea 3
4.0 Ed 1 4-1.8= 2.2 (Customer-
2)
5.4 Ea 4
7.2 Ea 5
8.0 Ed 2 8-3.6= 4.4 (Customer-
3)
9.0 Ea 6
10.8 Ea 7
12.0 Ed 3 12-5.4= 6.6 (Customer-
4)
13.6 Ea 8

14.0 End --

For Customer-5, 14-7.2= 6.8

Customer-6, 14-9.0=5.0

Customer-7, 14-10.8=3.2

189
 Customer-8, 14-13.6=0.4

It is evident from this simulation that the average waiting time per customer is;

(2.2+4.4+6.6+6.8+5.0+3.2+0.4)/8=28.7/8= 3.57

Average waiting time per customer for whose, who must wait is 28.7/8=4.08

And the percentage of idle time of the facility = 0%

Generation of Random Number:

Defining Random:

Definition of randomness can be accomplished by studying a random phenomenon,

such as a dice roll and exploring what quality makes it random.

In the Ludo game, if you roll the Ludo dice ,the first run, the Ludo rolls a one (1), so
the roll of one is completely random.

Figure. Ludo dice, the first run,

the rolls a one

A Random Number Generator can be defined as any system that creates random
sequences, which is uniformly distributed over all possible values and each number is
independent of the number generated before it.
For example, one digit number 0,1,2,…..9, there are in all 10 numbers and each of the
number should have 1/10 probability of being generated.

In inventory model, the variable include customer’s demand & delivery times which
may be probabilistic. The problem, in all such types simulation is based on the use of
random number. These are the number which have equal probability of being

190
 generated.

A conventional manual method for generation of random number may be

summarized in the followingseven steps.

• Step-1: Collect the data related to the current problem.

• Step-2: Construct a frequency distribution with these data.

• Step-3: construct the relative frequency distribution.

• Step-4: Assign a coding system that relates they identified events to Generated
Random Number.

• Step-5: Select a suitable method for obtaining the required random number.

• Step-6: Match the random to the assigned events and tabulate the result.

• Step-7: Repeat Step-6 until the desired number of simulation runs has be
generated.

Example:

A xyz studio uses an expensive grade of developing colour ink when printing color
portrait. Since the color colour ink cannot be stored for long period, it is important to
keep on hand only as much as is needed to fill anticipated demand. In the past few
months, however demand for the product has been fluctuating. The owner has
decided to simulate the demand for this service.

The data was taken for a 100 day period, during which no more than five special
prints were requested on any given day. Using the data given & generate a ten days
sequence of demand value.

Problems: (2017-2018) (15 marks)

A Backery keep stock of a popular brand of cake. Previous experience shows the
daily demand for the itemwith associated probabilities as given below;

Daily 0 10 20 30 40 50
Demand
(Nos.)
Probabilities0.0 0.20 0.15 0.50 0.12 0.02
1
Use the following sequence of Random Number to simulate the

demand for next 10 days.Random Number:

191
 25,39,65,76,12,05,73,89,19,49.

Problems: (2016-2017) (08 marks)

A Backery keep stock of a popular brand of cake. Previous experience shows the daily
demand for the itemwith associated probabilities as given below;

Daily 0 10 20 30 40 50
Demand
(Nos.)
Probabilities 0.0 0.20 0.15 0.50 0.12 0.02
1
Use the following sequence of Random Number to simulate the

demand for next 8 days.Random Number: 25,39,65,76,12,05,73,89.

Problems: (2015-2016) (15 marks)

A sample of 100 arrivals of customers in a department store is according to the following

distribution;

Time Between Frequency

arrivals (Minutes)
0.5 12
1.0 21
1.5 36
2.0 19
2.5 7
3.0 5

Simulate for the next 10 times between arrivals & time of arrivals by using
Random Number:-25,39,65,76,12,05,73,89, 19,49.

Problems: (2017-2018) (09 marks)

A sample of 100 arrivals of customers in a department store is according to the following

distribution;

Time 1 1.5 2 2.5 3

Between
arrivals
(Minutes)
Frequency 18 15 36 19 12

Simulate for the next 10 times between arrivals & time of arrivals by using Random
Number:-25,39,65,76,12,05,73,89, 19,49.

192
 Problems: (2017-2018) (15 marks)

In a bank cheques are cashed at a single “teller” counter. Customer arrives at the
counter in poisson manner at an average rate of 30 customers per hour. The teller
takes on an average a minute and a half cheque. The service time has been shown to
be exponentially distribution.

a) Calculate the probability that the teller is idle.

b) Calculate the expected number of customer in queue.
c) Calculate the expected waiting time in queue.

193
 DECISION THEORY
INTRODUCTION
Management has to make decisions. We have deal with certain situations where we have
perfect information; such decisions are made under certainty. Most of the managers make major
financial investments and other decisions related with production, marketing, etc., with less
than completeinformation. Decision theory, provides a rational approach in dealing with such
situations, where the information is incomplete and uncertain about future conditions. The
management must make decisions under such circumstances. With the help of decision
theory best possibledecision under a particular situation can be taken.

In decision theory, a number of statistical techniques can help the management in making
rational decisions. One such statistical decision theory is known as Bayesin decision theory

DECISION THEORY APPROACH

While discussing the approach, it will be helpful for us to take a real life situation and relate
it with the steps involved in taking decisions. Let us take the case of a manufacturing
company, which is interested in increasing its production to meet the increasing market
demand.
Step I. Determine all possible alternatives
The first obvious step involved before making a rational decision is to list all the viable
alternatives available in a particular situation. In the example considered above, the
followingoptions are available to the manufacturer:
a) Expand the existing manufacturing facilities (Expansion);
b) Setup a new plant (New facilities);
c) Engage other manufacturers to produce for him as much as is the extra demand (Sub
contracting).
Step II. Identify the future scenario
It is very difficult to identify the exact events that may occur in future. However, it is possible
to list all that can happen. The future events are not under the control of the decision-
maker. In decision theory, identifying the future events is called the state of nature. In the
case which we have taken of a particular manufacturing company, we can identify the
following future events :
a) Demand continues to increase (High demand)
b) Moderate demand
c) Demand starts coming down (Low demand)
d) The product does not remain in demand (No demand).

194
 Step III. Preparing a payoff table
The decision-maker has to now find out possible payoffs, in terms of profits, if any, of the
possible events taking place in future. Putting all the alternatives together (Step I) in relation
to the state of nature (Step II) gives us the payoff table. Let us prepare the payoff table for our
manufacturing company.

State of nature
Alternatives
High Demand Moderate Demand Low Demand No Demand
Expansion 1 2 3 4
Add
5 6 7 8z
New Facilities
Sub-Contact 9 10 11 12

If expansion is carried out and the demand continues to be high (one of the 12 alternatives),
the payoff is going to be maximum in terms of profit of say Rs. X. However, if expansion is
carried out and there is no demand (situation 4), the company will suffer a loss.
Step IV. Select the best alternative
The decision-maker will, of course, select the best course of action in terms of payoff. However,
it must be understood that the decision may not be based on purely quantitative payoff in
terms of profit alone, the decision-maker may consider other qualitative aspects like the
goodwill generated which can be encashed in future, increasing market share with an eye
on specially designed pricing policy which ultimately gives profits to the company, etc

ENVIRONMENT IN, WHICH DECISIONS ARE MADE

Decision-maker faces the following situations while making decisions:
(a) Decision under conditions of certainty
This is a hypothetical situation in which complete information about the future
business environment is available to the decision-maker. It is very easy for him
to take a very good decision, as there is no uncertainty involved. But in real life,
such situations arenever available.
(b) Decision under conditions of uncertainty
The future state of events is not known, i.e., there are more than one state of
nature. As these uncertainties increase, the situation becomes more complex.
The decision- maker does not have sufficient information and cannot assign
probabilities to differentoccurrences.
(c) Decision under risk
Here, there are a number of states of nature like the above case. The only
difference is the decision-maker has sufficient information and can allot
probabilities to the differentsates of nature i.e., the risk can be quantified.
Decision under Certainty
This is a rare situation and no decision-maker is so fortunate to have complete information

195
 before making a decision. Hence, it is not a real life situation and is of no-consequence
in managerialdecisions.
In this situation only one state of nature exits and its probability is one. With one
state of nature, possible alternatives could still be numerous and the decision-maker may
use techniques like Linear programming, Transportation and Assignment technique,
Economic Order Quantity(EOQ) model, input-output analysis, etc.
In our example of the manufacturing company, if the company had perfect information
that the demand would be high: it would have three alternatives of expansion,
construction of additional facilities and sub-contracting. Any one alternative, which gives
the best payoff, say constructing additional facilities may be picked up to get the
maximum benefit. So, the job of decision-maker is simple just to pick-up the best payoff
in the column of state of nature (high demand, low demand, no demand) and use the
associated alternative (expand, add facilities, sub-contract).
Decision Under Uncertainty
Under conditions of uncertainty, one may know the state of nature in future but what is
the probability of occurrence is not known. Since the data or information is incomplete
the decision model becomes complex and the decision is not optimal or the best decision.
Such situations and decision problems are called the Games Theory, which will be taken
up subsequently.
Let us take the case of our manufacturing company. If the company wishes to launch
a new product like a DVD player, it knows that the demand of DVDs in future is likely to
rise, but the probability that it will increase is not known. Also, the company may face
the uncertainty of manufacturing these profitably, because the imported DVDs may
become very cheap because of the Government policy.
There are number of criterion available for making decision under uncertainty. The
assumption, of course, is that no probability distributions are available under these
conditions. The following are discussed in this chapter :
(a) The maximax criterion
(b) The minimax (Maximin) criterion
(c) The Savage criterion (The Minimax Regret Criterion)
(d) The Laplace criterion (Criterion of Rationality)
(e) The Hurwicz criterion (Criterion of Realism).

In the above criteria, the assumption is also made that the decision-maker does not
have an ‘intelligent’ opponent whose interest will oppose the interest of decision-
maker. For example, when two armies fight each other, they are a case of intelligent
opponents and such cases are dealt with and handled by Games Theory.
The Maximax Criterion
This the case of an optimistic criterion in which the decision-maker finds out the

196
 maximum possible payoff for every possible alternative and chooses the alternative with
maximum payoffin the particular group. Let us reproduce the case of our manufacturing
company with payoffsin rupee values.
State of nature (Demand)
Alternatives High Moderate Low No Maximum
Demand Demand Demand Demand of row
Expansion 40000 20000 –20000 –50000 40000
Add New Maximax
50000 25000 –30000 –70000 50000
Facilities
Sub-contract 30000 20000 –5000 –20000 30000

It is obvious that maximum payoff is Rs. 50000 corresponding to the alternative

‘Add new facilities’
The Minimax (Maximin) Criterion
The criterion is considered the most conservative as it aims at making the best of the worst
possible situation. The decision-maker finds the minimum possible payoff and then worst
possible payoff and then selects the best (maximum) out of minimum payoff. Let us
review the above table with minimum of row and then pickup the maximum out of
these, i.e., –20000.

State of nature (Demand)

Alternative High Moderate Low No Minimum
Demand Demand Demand Demand of row
Expansion 40000 20000 –20000 –50000 –50000
Add
50000 25000 –30000 –70000 –70000
New Facilities
Maximin
Sub-contract 30000 20000 –5000 –20000 –20000

The Savage (Minimax Regret) Criterion

This criterion is named after L.J. Savage who developed it. The decision-maker may
regret making decision after it has been made because of the turn of events (state of
nature). Hence, thedecision-maker must keep the regret at the back of his mind and try
and minimize that regret. It involves three steps process.
(a) Find out the quantum of regret associate with each alternative for different
states of nature ;
(b) Determine the maximum regret for each alternative;
(c) Select the alternative which gives minimum of the maximum regrets determined
in (b)above.
The criterion which is considered ‘less conservative’ as compared to Minimax
criterion, which may described as extremely conservative. This quality of Savage
criterion justifies the need of such a criterion. Let us consider the following loss matrix
which may be quoted as a classic example of the illogical conclusion, whih minimax
criterion can give.

197
 Nature state (demand)
Alternativ 2
e
a1 Rs. 10000/- Rs. 100/-
a2 Rs. 8000/- Rs.
8000/-
If we apply minimax criterion to this matrix, we are to pick-up a2 alternative. However,
commonsense dictates us to select a1 as in this case maximum of Rs. 100/- may be lost
where as in a2 alternative there will be a certain loss of Rs. 8000/-. In Savage criterion this
anomaly has been rectified by constructing a new loss matrix. New matrix is constructed by
finding the difference between the best choice in the column and the particular value in the
same column. In our above example in the column 1 the best choice is Rs. 8000. Now, the
difference of the first value under 1 is 2000 and the second value is 0. Similarly, the best
choice under 2, is Rs. 100. So, the difference of the first value under 2 is 0 and the second
value is Rs. 7900/-. The minimax criterion yields a1 as is expected. The students must note
that the regret function represents loss and so the minimax and not the maximin criterion
can be applied to this matrix
Example 2.1. Let us consider the following cost matrix which is to be conerted into
he regret matrix:
1 2 3 2
a1 5 10 18 25
a2 8 7 8 23
a3 21 18 12 21
a4 30 22 19 15

Solution.

1 2 3 4
a1 0 3 10 10
a2 3 0 0 8 Minimax value
a3 16 11 4 6
a4 5 15 11 0

The Laplace Criterion

Decision under uncertainty is represented in the form of a matrix, the columns of which
represent the future state of nature and rows representing the alternatives or actions that
are possible. Associated with each state of nature and each alternative action is the
outcome or result of the action when a particular future state of nature occurs. This outcome
evaluates the gain (or loss). Hence if a1 represents the ith action (i = 1, 2,.…, m) and 1
represents the jth nature state (j = 1, 2, 3.…, n), then V (a1, 1) will represent the outcome
resulting by ith action when j state of nature occurs. This can be represented in the matrix
below.

198
The probability of
occurrence of 1 , 2
…………… n state of
nature are not known, i.e.,
are uncertain. If these
probabilities were not different, we could determine them and the situation will not have
sufficient reason to believe 1 , 2 …………… n are equally likely to occur. This is called
the Principle of insufficient reason. Under these circumstances one selects the
alternative i yielding the largest xpected gain. Hence,

where i/n is the probability that 1(j =1, 2.…, n) occurs.

Example 2.2. A service garage must decide on the level of spare parts it must stock to meet
the need of arrival of cars for servicing. The exact number of cars arriving for serving is not
known but it is expected to be in one of the four categories 80, 100, 120, 150 cars. Four
levels of stocking are thus suggested with level being the best from the point of view of
incurring cost if the number of cars arriving for servicing falls in category one. Any change
from this ideal level will result in additional costs either because extra spares are stocked or
because demand of servicing cannot be satisfied. The table below gives thse costs in
thousand of rupees.

Category of cars arriving for servicing

1 2 3 4
a1 5 10 18 25
Stocking level a2 8 7 8 23
a3 21 18 12 21
a4 30 22 19 15
Solution. Laplace criterion assumes that probability of occurrence of 1, 2, 3 and 4 are
equal. Hence the probability of occurring of p( 1) = 1/4, j = 1, 2, 3, 4. The expected costs
associated with alternatives a1, a2, a3, a4 are as follows:
E [a1] = { 1/4 (5 + 10 + 18 + 25)} = 14.5
E [a2] = {1/4 (8 + 7 + 8 + 23)} = 11.5
E [a3] = {1/4 (21 + 18 + 12 + 21)} = 18.0
E (a4)] = {1/4 (30 + 22 + 19 + 15)} = 21.5
Thus, the best level of stocking of spare parts in the service station according to Laplace
criterion is given by a2 (11.5).

199
 Hurwicz Criterion
The criterion represents the method of choosing an alternative or action under the most
optimistic or under the most pessimistic conditions. The decision-maker selects a parameter
(alpha), which is known as the index of optimism. When = 1, the criterion is too optimistic
and similarly when = 0 it is too pessimistic. Depending upon the attitude of the decision-
maker whether he leans towards optimism or pessimism, a value of between 1 and 0 can
be selected by him.When there is no strong inclination, one or the other, he may assume =
½.

Example 2.3. Let us take the example of service garage given above and apply Hurwicz principle
to it. The solution is provided below
Min v (ai j) Max v (ai j) Min v (ai j) + (1 – ) Max v (ai j)
a1 5 25 15
a2 7 23 15
a3 12 21 16.5
a4 15 30 22.5
this e = 1/2 has been assumed. The op time solution is provided by a1 or a2 (15).
example

Decision-making Under Conditions of Risk

In real life situations managers have to make-decisions under conditions of risk. In
decision- making under conditions of uncertainty, the decision-maker does not have
sufficient information to assign probability to different states of nature. Whereas in
decision-making under conditions of risk, the decision-maker has sufficient information
to assign probabilities to each of the statesof nature.
Decisions under risk are usually based on one of the following criterion :
(a) Expected value criterion (Expected monetary value –EMV criterion)
(b) Combined expected value and variance
(c) Known aspiration level
(d) Most likely occurrence of a future state
Each of the above criterion is discussed in the following paragraphs :

Expected Monetary Value criterion

This criterion consists of the following steps :
(a) Constructing a payoff matrix with different states of nature and alternative
decisions. Enter the conditional profit for each decision-nature state
combination along with the probabilities of occurrence of state and by adding

200
 the conditional values.
(b) Expected monetary value (EMV) is calculated for each decision by multiplying
the profits by the probabilities of occurrence of the nature state and by adding the
conditional values.
(c) Selecting the alternative, which yields highest EMV.
Example 2.4. A newspaper boy has the following prbabilities of selling a magazine:
No. of copies Probabili
sold ty
10 0.10
11 0.15
12 0.20
13 0.25
14 0.30
1.00

Cost of copy is 30 paise and sale price is 50 paise. He cannot return unsold copies. How
many copies should he order ?
Solution Step I. Constructing the conditional profit table
It is obvious that the newspaper boy has to order between 10 and 14 copies. Since the sale
price is 50 paise and the cost of one copy is 30 paise, he makes profit of 20 paise on each sale.
If he sells 10 copies and he stocks 10 copies, he makes a profit of 10 ¥ 20 paise = 200 paise. If
he stocks 10 copies and demand is of say 12 copies, he still makes only a profit of 200 paise.
When he stocks say 11 copies, his profit will be 220 paise but if only 10 copies are sold, his profit
of 200 paise is reduced by 30 paise, the cost of unsold copy, i.e., the profit is only 170 paise.
Similarly, when he stocks 12 copies, the profit can be 240 paise, when he sells 12 copies, but if
he sells only 11 copies, his profit must be reduced by one unsold copy, i.e., 11 ¥ 20 – 30 ¥ 1 =
190 paise. And if he stocks 12 copies but sells only 10, the profit of 20 ¥ 10 = 200 paise must be
reduced by 30 ¥ 2 = 60 paise as these are two unsold copies, i.e., 200 – 60 = 140 paise. Hence
payoff is equal to 20 paise ¥ copis sold – 30 paise ¥ unsold copies.

No. of copies that

Probability Possible stock action (copies)
can be sold
10 11 12 13 14
10 0.10 200 170 140 110 80
11 0.15 200 220 190 160 130
12 0.20 200 220 240 210 180
13 0.25 200 220 240 260 230
14 0.30 200 220 240 260 280

Conditional Profit Table in Paise

Step II. Determine the expected value of each decision by multiplying the profit with the
associated probability and by adding the values of all the alternatives. This is shown in the
xpected Profit table drawn below.

201
 No. of
copies that Probability Expected profit (paise) by stocking
can be sold
10 11 12 13 14
10 0.10 20 17 14 11 8
11 0.15 30 33 28.5 24 19.5
12 0.20 40 44 48 42 36
13 0.25 50 55 60 65 57.5
14 0.30 60 66 72 78 84
Total expected profit 200 215 222.5 220 205
Step III. Pick-up the alternative yielding highest EMV, which is 222.5 paise it means that the
newspaper boy must order 12 copies to earn highest possible daily average profit of 222.5
paise.
Example 2.5. You are given the following payoff of three acts A1,A2, A3 and the events E1, E2,
E3:
States of Acts
Nature A1 A2 A3
E1 25 –10 –125
E2 400 440 400
E3 650 740 750

The probability of the state of nature are respectively 0.1, 0.7 and 0.2. Calculate and tabulate
EMV and conclude which of the acts can be chosen as best.
Solution. EMV can be obtained by multiplying the probabilities with payoffs and adding all the
values ofa particular action A1, A2 or A3.
Acts
State of nature Probability
A1 A2 A3
E1 0.1 25 ¥ 0.1 = 2.5 –10 ¥ 0 .1 = – 1 –125 ¥ 0.1 = –12.5
E2 0.7 280 308 280
E3 0.2 130 148 150
EMV 412.5 455 417.5

The best alternative is A2.

Example 2.6. A management is faced with the problem of choosing one of three products
for manufacturing. The potential demand for each product may turn out to be good,
moderate or poor. The probabilities for each of acts of nture were estimates as follows:
Nature of Demand
Product Good Moderate Poor
X 0.70 0.20 0.10
Y 0.50 0.30 0.20
Z 0.40 0.50 0.10

The estimated profit or loss under he three states may be written as

202
 Prodct Rs. Rs. Rs.
X 3000 2000 10000
0 0
Y 6000 3000 20000
0 0
Z 4000 1000 –15000
0 0
Prepare the expected value table and advise the management about the choice of product.
Solution. Step I. Contruct the condition profit table.
Demand
Product Probability
Good Moderate Poor
Profit
0.70 0.20 0.10
X 30000 20000 10000
0.30 0.30 0.20
Y
6000 30000 2000
0.40 0.50 0.10
Z
4000 10000 –15000

Step II. Clculation of the expected values.

Demand
Product Expected Value
Good Moderate Poor
X 0.70 ¥ 30000 0.20 ¥ 2000 0.10 ¥ 1000 28000
Y 0.50 ¥ 6000 0.30 ¥ 3000 0.20 ¥ 2000 43000
Z 0.40 ¥ 4000 0.50 ¥ 1000 0.10 ¥ (–15000) 19500

Step III. Select the best alternative. As the expected value of product Y is the highest,
the management should choose this product.

Expected Opportunity Loss (EOL) Criterion

Another method is to determine minimum Expected Opportunity Loss (EOL). It represents
the amount by which the maximum possible profit under various possible actions will be
reduced. That course of action, which reduces this loss to minimum, is the best alternative.
The followingsteps are involved in calculating EOL.
Step I. Prepare the conditional profit table for every action-state of nature combination
andlist the associated probabilities.
Step II. For each alternative find out the Conditional Opportunity Loss (COL) this is done by
subtracting the payoff from the maximum payoff from a particular event.
Step III. COL’s are multiplied by the respective probabilities. All these are added to give EOL.
Step IV. Select the alternative, which gives the minimum EOL.

203
 Nature State
Alternatives
1 2 3 4

a1 18 10 12 8
a2 16 12 10 10
a3 12 13 11 12

Solution. Step I. Conditional profit table has already been provided in the example:
Step II. Preparing COL table by subtracting the va1lue of each payoff I column qi (i = 1,2, 3,
4) from the larest payoff value in the same column.

State of Nature
Acts
1 2 3 4
Probability 0.25 0.4 0.15 0.20
a1 18–18 = 0 13 – 10 = 3 12 – 12 = 0 12 – 8 = 4
a2 18 – 16 = 2 13 – 12 = 1 12 – 10 = 2 12 – 10 = 2
a3 18 – 12 = 6 13 – 13 = 0 12 – 11 = 1 12 – 12 = 0
Step III. EOL of acts a1, a2, a3 are as follows:
a1 = 0 ¥ .25 + 3 ¥ 0.4 + 0 ¥ .15 + 4 ¥ .20 = 2.25
a2 = 2 ¥ .25 + 1 ¥ 0.4 + 2 ¥ 0.15 + 2 ¥ 0.20 = 1.6
a3 = 6 ¥ .25 + 0 ¥ 0.4 + 1 ¥ .15 + 0 ¥ .20 = 1.65
Step IV. a2 EOL is minimum = 1.6

Expected Value of Perfect Information (EVPI) Criterion

If the decision-maker had perfect information before taking the decision, this criterion provides
the expected or average return in the long run.
Step I. Calculate the Expected-Payoff with Perfect Information (EPPI) which is equal to
(Max. payoff in first state of nature ¥ probability of occurrence of same state of nature)
+ (Max payoff in second state of nature ¥ probability of occurrence of same state of nature)
+ .... so on up to last state of nature.
Step II. Determine EVPI = EVPI – Maximum EMV.

204
Example 2.8. Payoff of three acts A, B and C ad state of nature XYZ are given below.
Payoff (In Rs.)
Acts
A B C
State of Nature X –20 – 50 200
Y 200 –100 –50
Z
400 600 300

The probability of the state of nature are 0.3, 0.4, and 0.3. Calculate the EMV for
the data given and select the best act. Also find the expected value of perfect
information (EVPI).
Solution. Step I. Calculating EMV of acts A, B, C
A = – 20 ¥ 0.3 + 200 + 0.4 + 400 ¥ 0.3 = 194
B = – 50 ¥ 0.3 – 100 ¥ 0.4 + 600 ¥ 0.3 = 125
C = 200 ¥ .3 – 50 ¥ .4 + 300 ¥ .3 = 130
Rs. 194 is he maximum EMV
Step II. Calculate EPPI

Nature of Acts Max for state of Max Payoff ¥

State nature probability
Prob. A B C
X 0.3 –20 50 200 200 200 ¥ 0.3 = 60
Y 0.4 200 – 100 – 50 200 200 ¥ 0.4 = 80
Z 0.3 400 600 300 600 600 ¥ 0.3 = 18
EPPI 320

Step III. EVPI – EMV

= 320 – 194 = Rs. 126
Example 2.9. The probability of mnthly sales of an item is as follows

Monthly Sales (Units) 0 1 2 3 4 5 6

Probability 0.01 0.06 0.25 0.30 0.22 0.10 0.06
The
cost of carrying inventory (unsold during the month) is Rs. 30 per cent per month and
cost of unit storage is Rs. 70. Determine optimum stock to minimize expected cost.
Solution. Let P – Units purchased during a month
S – Units sold in a month
Then the cost
function = Rs. 70 (S
– P) if P < Sand

= Rs. 30 (P – S) if P

205
 S
Cost table for the aboveproblem can be constructed as
follows:

Strategies
Monthly Sales P (Units in stock or purchased)
Probability
(Units) S
0 1 2 3 4 5 6
0 0.01 0 30 60 90 120 150 180
1 0.06 70 0 30 60 90 120 150
2 0.25 140 70 0 30 60 90 120
3 0.30 210 140 70 0 30 60 90
4 0.22 280 210 140 70 0 30 60
5 0.10 350 280 210 140 70 0 30
6 0.06 420 350 280 210 140 70 0
Expected Cost 224 155 92 54 46 60 84

The columns under different strategies are filled out using the cost functions given above.
For example, under column P = 0, S = 0, the cost function is 0. When the monthly sales S = 1
and P = 0 since P < 0, cost function Rs. 70 (S – P) = 70 (1 – 0) = 70. Again under P = 3 and S
= 1 since P > S cost function is Rs. 30
(P – S) = 30 (3 – 1) = Rs. 60 and so on.

where pi is the probability of occurrence of sales and Ci is the cost incurred.

Expected cost = 0.01 ¥ 0 + 0.06 ¥ 70 + 0.25 ¥ 140 + 0.30 ¥ 210
(When 0 units are stocked) + 0.22 ¥ 280 + 0.10 ¥ 350 + 0.06 ¥ 420 = Rs.
224
Expected cost = 0.01 ¥ 30 + 0.06 ¥ 0 + 0.25 ¥ 70 + 0.30 ¥ 140
(When 1 unit is stocked) + 0.22 ¥ 210 + 0.10 ¥ 280 + 0.06 ¥ 350 = Rs. 155
Expected cost = 0.01 ¥ 60 + 0.06 ¥ 30 + 0.25 ¥ 0 + 0.30 ¥ 70
(Where 2 units are stocked) + 0.22 ¥ 140 + 0.10 ¥ 210 + 0.06 ¥ 280 = Rs.
92
Expected cost = 0.01 ¥ 90 + 0.60 + 0.25 ¥ 30 + 0.30 ¥ 0
(Where 3 units are stocked) + 0.22 ¥ 70 + 0.10 ¥ 140 + 0.06 ¥ 210 = Rs. 54
Expected cost = 0.1 ¥ 120 + 0.06 ¥ 90 + 0.25 ¥ 60 + 0.30 ¥ 30
(Where 4 units are stocked) + 0.22 ¥ 0 + 0.10 ¥ 70 + 0.06 ¥ 140 = Rs. 46
Expect cost = 0.1 ¥ 150 + 0.06 ¥ 20 + 0.25 ¥ 90 + 0.30 ¥ 60
(Where 5 units are stocked) + 0.22 ¥ 30 + 0.10 ¥ 0 + 0.06 ¥ 70 = Rs. 53.75
The expected cost is minimum, i.e., Rs. 46 if 4 units are stocked each month hence the
optimumunits to be stocked to minimize cost is 4.
Example 2.10. The demandfor a seasonal product is given below.

206
 Demand during the season Probability
40 0.10
45 0.20
50 0.30
55 0.25
60 0.10
65 0.05
The product costs Rs. 60 per unit and sells at Rs. 80 per unit. If the units are not sold within
the season, they will have no market value.
(i) Determine the optimum number of units to be produced.
(ii) Calculate EVPI and interpret it.
Solution. (i) The payoff matrix can be prepared by
remembering thatPayoff = sale units ¥ cost of product
For example, if 45 units are stocked and only 40 are sold, payoff = 40 ¥ (0 – 35) ¥ 60
= 3200 – 2700 = Rs. 500/-

Demand Strategies (P Units in stock or purchased)

Probability
S 40 45 50 55 60 65
0 0.10 800 500 200 –100 – 400 –700
45 0.20 800 900 600 300 0 –300
50 0.30 800 900 1000 700 400 100
55 0.25 800 900 1000 1100 800 500
60 0.10 800 900 1000 1100 1200 900
65 0.05 800 900 1000 1100 1200 1300
Expected value 800 860 840 54 460 180

It can be seen that expected value is the highest, i.e., 860 with 45 units. Hence,
the optimumnumber of units to be purchased is 45.
(ii) EPPI— The student should recall that this can be found out by multiplying
probabilitywith the maximum payoff under each demand so
EPPI = 800 ¥ 0.1 + 900 ¥ 0.2 + 1000 ¥ 0.3 + 1100 ¥ .25 + 1200 ¥ 0.1 + 1300 ¥ 0.05
= Rs. 1020
EVPI = Rs. 1020 – 860 = Rs. 160
Interpretation of EVPI
EVPI helps the decision-maker to get the perfect information about the state of nature.
This helps in reducing the uncertainty. How much can be spent by the decision-maker to
get perfect information ? EVPI gives that upper-limit. In the above example, the best
alternative is to produce 45 units with expected payoff of Rs. 860. The expected profit

207
under perfect information is Rs. 1020 and EVPI is 1020 – 860 = 160. However, the
decision-maker can spend up to Rs. 160 perseason to get the perfect information, which
helps him to reduce the uncertainty of demand.
Example. 2.11. Jagdamba Dairy wants to determine the quantity of ice cream it should
produce to meet the demand. Past pattern of demand of their brand of ice cream is as
follows:
Quantity (kg) No. of Days Demand
Demanded Occurred
1 8
0
1 12
5
2 20
0
2 60
5
2 40
5
3 40
0
4 40
0
5 20
0

The company cannot stock ice cream more than 50 kg. Ice cream costs Rs. 60 and is sold at Rs.
70 per kg.
(a) Construct a conditional profit table.
(b) Determine the alternative, which gives the maximum expected profit.
(c) Determine EVPI.
Solution. (a) Constructing conditional profit table.
It is clear from the problem that the company will not produce ice cream less than 10 kg and
more than 50 kg.
Let CP denote the conditional profit, S the quantity in stock and D the demand, then CP = 10 S
when D S because Rs. 10/- is the profit per kg.
CP = 70 D – 60 S when D £ S as whatever is the demand is sold at Rs. 70 per kg and what is
not sold but is in stock and has been produced at the cost of Rs. 60 per kg must be reduced
from the profit.
Let us take the case when the stock is 20 kg and the demand is 15 kg. In this case
CP = 70 ¥ 15 – 60 ¥ 20 = – 150 and so on. Also, probability associated with demand levels
have to be found out. The quantity of ice cream required for 8 days out of a total of 200 days
is 10 kg.
8
It means that the demand of 10 1kg has an associated probability of = 0.04. Similarly,
other
200
Probabilities can also be determined. Conditional profit table along with associate

208
probabilities
is shown in table below.

Demand Possible alternatives of stock (kg)

Probability
(kg) 10 15 20 25 30 40 50
10 0.04 100 – 200 – 500 – 800 –1100 – 1700 – 2300
15 0.06 100 150 – 150 – 450 – 750 – 1350 – 1950
20 0.1 100 150 200 – 100 – 400 –1000 – 1600
25 0.3 100 150 200 250 – 50 – 650 – 1250
30 0.2 100 150 200 250 300 – 300 – 900
40 0.2 100 150 200 250 300 400 – 200
50 0.1 100 150 200 250 300 400 500
(b) Expected payof and EMV are shown in the table below :

Demand Possible alternatives of stock (kg)

Probability
kg 10 15 20 25 30 40 50
10 .04 4 –8 –20 –32 – 44 – 68 – 92
15 .06 6 9 –9 –27 – 45 – 81 –117
20 0.1 10 154 20 –10 – 40 –100 –160
25 0.3 30 45 60 75 – 15 –195 –375
30 0.2 20 30 40 50 – 60 – 60 –180
40 0.2 20 30 40 50 60 80 – 40
50 0.1 10 15 20 25 30 40 50
EMV 100 136 151 –19 –114 –384 –914

Expected payoffs are determined by multiplying the payoff under each stock action by its
associated probability. It means payoff for stock action of 10 is obtained by multiplying 100
by0.04, i.e., 4. Similarly, for stock 15, the probability 0.04 is multiplied with – 200, i.e., 8 and so
on.
Since the maximum EMV is Rs. 151 for stock of 20 kg of ice cream the dairy can expect an
average daily profit of Rs. 151.
(c) EVPI can be calclated with the help of following table:
Demand Probability Conditional Profit Expected Profit with Perfect Information (EPPI)
10 0.04 100 4
15 0.06 150 9
20 0.1 200 20
25 0.3 250 75
30 0.2 300 60
40 0.2 400 80
50 0.1 500 50
EPPI = 298
EVPI = EPPI – EMV = 298 – 151 = Rs. 147/-
EMV for items having salvage value
In earlier calculations if the product is not sold it is assumed that it is of no use, i.e., it
has no salvage value. It may be true in many perishable products, but in case of other

209
products this assumption is not correct as every such product will have a salvage value,
hence, this salvage value must be taken into account while calculating the conditional
profits for every stock options.
Example 2.12. Let us continue with the above example and assume that unsold ice
cream can be sold at Rs. 50 per kg. Post-sales pattern is between 10 – 13 kg per day.
Find the EMV if the pas sales have the following probabilities:

Sales 10 11 12 13
Probability 0.2 0.2 .25 .35

Solution. Let CP = Conditional profit

S = Quantity in stock
D = Market demand
CP = 10 S when D S when = 70 D – 60 S + 50 (S – D) when D < S

Payoff matrix usig the above relationship is as follows :

Demand or Possible stock (S) action (alternative) in Rs.
Probability
event 10 11 12 13
10 0.2 100 – 10 80 70
11 0.2 100 110 100 90
12 0.25 140 130 120 110
13 0.35 160 150 120 130

Now, we can calculate the expected pyoffs and the EMV for each stock action.

Possible Demand- Possible stock (S) action (alternative)

Probability
D (event) 10 11 12 13
10 0.20 0.2 ¥ 100 = 20 0.2 ¥ – 10 = –2 0.2 ¥ 80 = 16 0.2 ¥ 70 = 14
11 0.20 24 22 20 18
12 0.25 35 32.50 30 27.50
13 0.35 56 52.50 42 45.50
EMV (Rs) 135 105 108 105

Max EMV = Rs. 135 for stock action of 10 kg ice cream per day.
Example 2.13. Daily demand (X) for bread at a general store is given by the following
probability distribution:
X 100 150 200 250 300
Probabilit 0.20 0.25 0.3 0.15 0.10
y 0
If a bread is not sold the same day it can be disposed of at Rs. 2 per piece at the end of the
day. Otherwise, the price of fresh bread is Rs. 10. The cost of the bread is Rs. 8. If the
optimum level of stocking is 200 breads daily, find out.
(a) Expected Monetary Value (EMV) of this optimum stock level
(b) Expected Value of Perfect Information (EVPI)
Solution. Selling = Rs. 10 (if sold the same day)

210
 = Rs. 2 (if sold at the end of the day)
Let CP = Conditional profit
Then CP = 2S when D S
And CP = 10 D – 8S + 2 (S – D) when D < S
Conditional profit table ad EMV is calculated in the table below.

Demand (D) Probabilities Payoff for stocking Expected

200 breads payoff
(S)
100 0.20 – – 80
400
150 0.20 0 0
200 0.30 400 120
200 0.30 400 120
250 0.15 800 120
300 0.10 120 120
0
EMV 280
Let us calculate payoff value when demand (D) is 100 and stocking (S) is 200 since D <
S
CP = 10 D – 8 S + 2 (S – D)
= 10 ¥ 100 – 8 ¥ 200 + 2 (200 – 100)
= 1000 – 1600 + 200
= – 400
When D = 150, S = 200
CP = 1500 – 1600 + 2 ¥ 50
=0
When D = 200, S = 200CP =
400
When D = 250, S = 200 CP = 2500 – 1600 – 2 ¥ 50 = 800
When D = 300, S = 200 CP = 1200
Expected payoff for 100 demand = 0.20 ¥ 400 = – 80
150 demand = 0 and so on
Therefore, EMV = Rs. 280
If the demand is known with certainty, Expected Profit with Perfect Information
EPPI) iscalculated in the table below:

211
 Demand Probabilities Payoff for Expected
stocking 200
(D) breads (S) payoff
100 0.20 20 40
0
150 0.25 30 75
0
200 0.30 40 120
0
250 0.15 50 75
0
300 0.10 60 60
0
EPPI 370

EVPI = EPPI – EMV

= 370 – 280
= Rs. 90/-
Decision Trees
We have seen decision situations in which no future decisions will depend on the decision
taken now. Such decision criteria are called ‘single-stage’ alternatives. In real life situations a
decision taken has implications for the subsequent decisions. Hence one must consider
multiple stage decision process in which the future decisions will depend on the decision
taken now. Such decision problems can be represented graphically with the help of decision
tree, such graphicalrepresentation facilitates the decision-making process.
Decision tree indicates decision alternatives, states of nature, probabilities associated with each
state of nature and conditional profit or loss. It consists of nodes and branches. The
following symbols are used:
Decision Node Square State of
nature (circle)
Different courses of action or strategies emerge out of the nodes as main branches of the
decision tree. At the end of each decision branch, there is a node representing state of nature
out of which sub-branches come out representing change events. The payoffs from those
alternatives and their probability of occurrence are shown alongside these branches. At the
end of terminalof the chance branch is shown the expected value of the outcome.
Let us assume a decision-making problem representedby the following conditional profit table :

Alternatives of production units

State of nature Probability
A1 (50) A2 (100)
S1 (High demand) 0.4 5000 10000
S2 (Low demand) 0.6 6000 – 4000

212
The decision tree can be draw as follows to represent the above problem.

EMV of alternative A2 or node 3 is

= Rs. [10000 ¥ 0.4 + (– 4000) ¥ 0.6]
= Rs. [4000 – 240]
= Rs. 1600/-
Some more illustrations are taken to demonstrate the use of decision tree.
Example 2.14. A company has the option of building a new plant or expanding its existing
plant. The decision depends primarily on the future demands for the product the plant will
manufacture. The construction of a new plant can be justified on the grounds that if the
demand keeps expanding the new plant can be run to its optimum capacity, otherwise it may be
advisable to expand the existing facilities as the demand increases. The problem is shown wth
the help of decision tree diagram below

Steps in Decision Tree Analysis

1. List the decision points and the strategies (alternative
courses of action) for each decision point in a systematic
manner.
2. Determine the probability and payoff associated with each
alternative for each decisionpoint.
3. Find out the expected payoff (EMV) of each course of
action, starting from the extremeright working backward
to the left.

213
 4. Select the course of action that gives the best payoff for each alternative.
5. Continue working backward to the next decision point on the left.
6. Continue with this process until the first decision point on the extreme left is
reached.
7. Consider the situation on the whole and find its course of action to be adopted
fromthe beginning to the end under different possible outcomes
Advantages of the Decision Tree Approach
1. It is systematic, orderly, logical and sequential approach.
2. It lists all possible outcomes and helps decision-nodes to examine each one of
them.
3. It is easy to understand. Its graphical representation
can be communicated to otherswith ease.
4. Since a decision now affects the decision-making in
future, decision trees are particularly useful in such
situations.
5. This approach can be applied to different decision
problems, such as introduction ofnew product,
investment decisions, etc.

Limitation of Decision Tree Approach

1. In real life situations, the decisions are made under a large number of
variables. In such cases, the diagram becomes extremely complicated.
2. It assumes utility of money is linear with time, which is not the case.
3. Decision Trees yields only and ‘average’ value solution as the problem is
analyzed on the basis of expected values.
4. The assignment of probabilities for different events is many a times not exact
and onlya reasoned value.
Example 2.15. A farmer is not sure whether he should dig a tube well in his field. He is
presently using the canal water for irrigation of his fields for which he pays Rs. 5000
per year. The history of tube well digging in the village has not been very
encouraging, only 50 per cent of the wells dug up to 200 feet yielded water. Some
farmers drilled further up to 300 feet but only 25 per cent of them struck water at
300 feet. The cost of drilling is Rs. 100 per feet. The farmer has to make the following
three decisions :
(a) Shall he drill up to 200 feet ?
(b) If no water is struck at 200 feet should he drill up to 300 feet ?
(c) Should he continue to buy water from government for next 5 years, as the
life of the tube well is only five years ?
Solution. The decision tree diagram of the above problem is drawn below:

214
 At decision node 1, the farmer has to take a decision before drilling up to 200 ft., or not drilling.
If he drills he pays Rs. 25000 @ Rs. 5000 per year for 5 years. If he drills up to 200 ft., there are
two probabilities 05 of water found and no water being struck. If the water is found, the cost
he incurs is Rs. 20000 as he digs 200 feet @ Rs. 100 per ft. If no water is found at 200 ft., he
takes the decision of drilling up to 300 feet or not drilling. If he does not drill 300 ft., he
incurs expansesof Rs. 45000 because he has already spent Rs. 20000 for drilling up to 200 feet
and he has to pay Rs. 25000 @ Rs. 5000 per year. If he drills up to 300 ft., there is an assured
probability of 0.25that water will be found and of 0.75 that water will not be found. If water
is found he spends Rs. 100 per ft. for 300 ft. If it is not found he spend Rs. 55000 as he has
already spent Rs. 30000 on digging up to 300 ft., but he has also to spend Rs. 25000 @ Rs.
5000 per year for five years.
As explained earlier, in such
problems we work
backward EMV of node B
= 0.25 ¥ 30000 + 0.75 ¥
55000
= Rs. (7500 + 41250) = Rs. 48750
EMV of node 2 = Rs. 45000
(Choosing the
lesser of the two of
Rs. 48750 and Rs.
45000)
EMV of node A = Rs. [0.5 ¥ 20000 + 0.5 ¥ 48750] = Rs. (10000 + 24375)
= Rs. 34375
EMV of node 1 = 25000 (lesser of the two values Rs. 34375 and Rs. 25000)
Hence, it can be easily seen the best course of action for the farmer is not to drill and pay
Rs. 25000/ for water from canal to the government for five years.
Example 2.16. A complex airborne navigating system incorporates a sub-assembly, which
unrolls a map of the flight plan synchronously with the movement of the aeroplane. The sub-
assembly is bought on very good terms from a sub-contractor, but is not always in perfect
adjustment on delivery. The sub-assemblies can be readjusted on delivery to guarantee accuracy
at a cost of Rs. 50 per sub-assembly. It is not however, possible to distinguish visually these

215
sub-assemblies that need adjustments.
Alternatively, the sub-assemblies can each be tested electronically at a cost of Rs. 10 per sub-
assembly tested. Past experience shows that about 30 per cent of those supplied are defective;
the probability of a test indicating a bad adjustment of the sub-assembly is 0.8, while the
probability that the test indicates a good adjustment when the sub-assembly is properly
adjusted is 0◊7. If the adjustment is not made and the sub-assembly is found to be faulty
when the system has its final check, the cost of subsequent rectifications will be Rs. 140.
Draw up an appropriate decision tree to show the alternatives open to the purchaser and use it
to determie his appropriate course of action.
Solution.

The purchaser can either have the sub-assembly tested electrically and pay Rs. 10 or can have
it readjusted at a cost of Rs. 50. If he gets them tested, probability of defective sub-assembly
is
0.3 and good is 0.7. Those which are defective out of these 80%
(0.8) will be with bad adjustment and need readjustment at the
cost of Rs. 50. Only 20% (0.2) are OK as per test but if these are
found to be faulty in the final check, the purchaser has to spend
Rs. 140. Out of 70% of sub- assemblies, which are not defective,
70% are OK as per test and such assemblies will not cost anything
to the purchaser but 30%, which are bad as per test, will have to
be readjusted at the cost of Rs. 50 per sub-assembly.
EMV of node B = Rs. (0.7 + 0.350) = Rs. 15
EMV of node C = Rs. (0.2 ¥ 140 + 0.8 ¥ 50) = Rs. 68

216
 EMV of node A = Rs. (0.7 ¥ 15 + 0.3 ¥ 68) = Rs. 30.90.
EMV of node 1 = Rs. (10 + 30.90) = 40.90.
(When test is carried out)EMV of node 1 =
Rs. 50 (when no test is carried out)
Since the least cost is Rs. 40.90; the decision the purchaser has to take is to get sub-
assembliestested.
Example 2.17. XYZ Ltd., wants to update/change its existing manufacturing prices for
product
A. It wants to strengthen its R & D cell and conduct research for finding a better
product of manufacturing which can get them higher profits. At present the
company is earning a profit of Rs. 20000 after paying for material, labour and
overheads. XYZ Ltd., has the following fouralternatives :
(a) The company continues with the existing process.
(b) The company conducts research P, which costs Rs. 20000, has 75%
probability ofsuccess and can get the profit of Rs. 5000.
(c) The company conducts research Q, which costs Rs. 10000, has 50%
probability ofsuccess and can get the profit of Rs. 25000.
The company pays Rs. 10000 as royalty for a new product and can get profit of Rs. 20000.
The company can carryout only one out of the two types of research P and Q because of
certain limitations. Draw a decision tree diagram and find the best strategy for XYZ Ltd.
Solution. The decision tree is drawn as shown below:

217
Points 1, 2, 3, 4 and 5 are decision boxes. The four alternatives to the company are shown
coming out of decision box 1. Research P succeeds (probability 0.75) or it fails (Probability
0.25). If it fails the company has three alternatives; conduct research Q, continue with the
existing process or pay royalty. If Q fails the company is left only with the option of paying
royalty or continuing with existing process. The payoffs are written at the end of the
branches. Let us now calculate the EMV starting from node 5 (working backward)
EMV at decision node 5 = Maximum out of(a)
Rs. 20000
(b) Rs. 20000 – 10000 = 10000 = Rs. 20000
EMV at decision node 4 = Maximum out of B Rs. 20000 and Rs.
(20000 – 10000) = Rs. 20000

EMV at decision node C = Rs. (0.5 ¥ 20000 + 0.5 ¥ 20000) = Rs. 22500 EMV at decision node D –
Rs. (0.75 ¥ 50000 + 0.25 ¥ 20000) = Rs. 42500EMV at decision node 3 = Maximum out of
(a) Rs. 20000
(b) Rs. 20000 – 10000 = Rs. 10000 ?
EMV at decision node 2 = As for decision node 3, i.e., Rs. 20000
EMV at decision node B = Rs. (0.5 ¥ 20000 + 0.5 ¥ 20000) = Rs. (22500) EMV
at decision node A = Rs. (0.75 ¥ 50000 + 0.25 ¥ 20000) = Rs. 42500 EMV at
decision node 1 = Maximum out of four alternatives
(a) Rs. (42500 – 20000) = Rs. 22500
(b) Rs. (22500 – 10000) = 12500
(c) Rs. 20000
(d) Rs. (20000 – 10000) = Rs. 10000Max.
= Rs. 22500

The company should conduct research P to find a new process to earn a maximum profit of Rs.
22500.
Example 2.18. ABC Lt., has invented a picture cell phone. It is faced with selecting one
alternative out of the following strategies:
(a) Manufacture the cell phone.
(b) Take royalty from another manufacturer.
(c) Sell the rights for the invention and take a lump sum amount.
Profit in thousands of rupees which can be incurred and the probability associated with
sch alternatives are shown in the table below :

218
 Represent the company problem in the form of the decision tree and suggest what
decision the comany should take to maximize profits.
Solution.

EMV at node B = Rs. (0.25 ¥ 60000 + 0.4 ¥ 40000 + .35 ¥ 20000)

= Rs. (15000 + 16000 + 7000) = Rs. 38000
EMV at node A = Rs. (0.25 ¥ 200000 + 0.4 ¥ 50000 + 0.35 ¥ – 10000)
= Rs. (50000 + 20000 – 3500) = Rs. 66500
EMV at decision node 1 = Maximum out of Rs. 50000, 38000, 66000
= Rs. 66500

Thus, the best decision by ABC Ltd., is to manufacture the picture cell phone itself to get
profit of Rs. 66500.
Example 2.19. The investment staff of TNC Bank is considering four investment proposals
for clients, shares, bonds, real estate and saving certificates; these investments will be held
for one year. The past data regarding the four proposals is given below :
Shares : There is 25% chance that shares will decline by 10%, 30% chance that they will
remain stable and 45% chance that they will increase in value by 15%. Also the shares
under consideration do not pay any dividends.
Bonds : These bonds stand a 40% chance of increase in value by 5% and 60% chance of
remaining stable and they yield 12%.
Real Estate : This proposal has a 20% chance of increasing 30% in value, a 25% chance of
increasing 20% in value a 40% chance of increasing 10% in value, a 10% chance of
remaining stable and a 5% chance of loosing 5% of its value.
Saving Certificates : These certificates will yields 8.5 with certainty.
Use a decision tree to structure the alternatives available to the investment staff, and using
the expected value criteria choose the alternative with the highest expected value.

219
Solution. Let us assume that we have Rs. 100 to invest. The decision tree is shown below.

EMV at node 5 = Rs. 1085

EMV at node 4 = Rs. (0.2 ¥ 1300 + 0.25 ¥ 1200 + 0.04 ¥
1100 + 0.05 ¥ 9950)
= Rs. (260 + 300 + 440 + 497.50) = Rs.
1497.50
EMV at node 3 = Rs. (0.4 ¥ 1370 + 0.06 ¥ 1120) = Rs. (548 +
672) = Rs. 1220
EMV at node 2 = Rs. (0.25 ¥ 900 + 0.30 ¥ 1000 + 0.045 ¥
1150)
= Rs. (225 + 300 + 517.50) = Rs. 1042.50
EMV at decision node 4 is maximum, i.e., 1497.50. So the decision should be to invest in
real estate.

220
GAMES THEORY
INTRODUCTION

Till now we have used criteria for decision under uncertainty assuming that ‘state of nature’ is
the opponent. Here the ‘nature’ is in the form of many possible outcomes of some action. When
there are many possible outcomes or state of nature, one can’t predict what will happen, it can
only be predicted as a probability of a happening or occurrence. Such state of nature is beyond
the control of any organization. Here certain happenings (or state of nature) like shift in the life
style of people effecting demand; higher and better technology products made available in
future at cheaper rates etc. effect-the pay-off and will decide the action of the decision-maker.
However, in real life situations, there are many competitors of any organization. Competition is
the essence of existence of individuals and organizations. In modern day life no monopolistic
situations exist in free economy. There are always two or more than two individuals or
organizations making decisions and each wants the outcome in their favour as there is a conflict
in the interest of each party. When decisions have to be made under conditions of uncertainty,
two or more ‘intelligent’ opponents are involved and each one wants to optimize decision in his
favour at the cost of other, Game Theory approach is involved. When we talk of ‘intelligent’
opponents what we mean is that in competitive situations each participant acts in a rational
manner and does his best to resolve the situation in his favour.
This approach was developed by Professor John Von Newman and Oscar Morgensten when they
published a book,. ‘The theory of Games and Economic Behaviour’ Games Theory is now widely
used in economics, business and administration and many humanity disciplines as also by armed
forces for training purposes. It is a useful scientific approach to rational decision-making.
TERMS USED IN GAME THEORY
Following are some important terms used in Game Theory:
1. Player: An opponent is referred to as a player.
2. Strategies: Each player has a number of choices, these are called the strategies.
3. Outcomes or Payoff: Outcome of a game when different alternatives are
adopted bythe competing players, the gains or losses are called the payoffs.
4. Two persons zero-sum game: When only two players are involved in the game and
the gains made by one player are equal to the loss of the other, it is called two
persons zero-sum game. This may be the case when there are just two players in the
game, i.e., assuming that there are only two types of beverages, tea and coffee. Any
market share gained by the tea will equal the loss of market share of coffee. Since
sum of the gainsand losses is zero, this situation is called two persons zero sum gain.
5. n, persons game: A game in which n persons are involved is called n persons game.
When n is more than two, i.e., more than two persons are involved the games
becomecomplex and difficult to solve.

221
 6. Payoff matrix: When the gains and losses, which result from different actions of
the competitors, are represented in the form of a matrix in a table, it is called payoff
matrix, we have already seen many payoff matrix tables in earlier chapters.
7. Decision of a game: In game theory the decision criterion of optimality is adopted,
i.e., a player, which wants to maximize his outcome, maximin, is used and the one
whowishes to minimize his outcome, minimax is used.

A strategy basically relates to selection and use of one course of action out of various courses
available to a player at a particular point of time. There are two types of strategies.
(a) Pure strategy. It is the course of action, which the player decides in advance. If
there are 4 courses of action and the players select the third, then it is the third
strategy whichthe player is using.
(b) Mixed strategy. In mixed strategy, the player decides his course of action by
relating a fixed probability distribution. Some probability is associated with each
course of action and decision to select one is done based on these probabilities.

LIMITATIONS OF GAME THEORY

Following are some limitations of Game Theory:

1. Risk and uncertainty are not taken into account: Since in pure strategies of game theory, no
probability is associated with various courses of action, risk and uncertainty are not taken into
account.
2. A fixed number of competitors: The theory assumes that there are a fixed number of
competitors. In real life situations, there can be more than the expected number ofplayers.
3. Infinite courses of action: Games Theory assumes finite number of courses of action available to
each player. However, it is possible that a player may have infinite number of strategies available
to him.
4. Knowledge about strategies available to the opponent player: The theory assumes that each
player has knowledge about the strategies available to the other players. This may not always be
the case.
5. Zero sum game is not realistic: The assumption that gains of one player are equal to the loss of
the other player is not a realistic assumption.
6. Knowledge of payoff in advance: It is not always possible to know about the payoff of a
particular course of action
7. Rules of games do not permit tackling of all situations: All games are played according a
predetermined set of rules. These rules are based on certain assumptions and govern the
behaviour pattern of the players. Many situations will fall outside the situation, which can be
handled by these rules.

222
SITUATIONS OF TWO-PERSON ZERO-SUM PURE STRATEGY
GAMES
As brought out earlier, the criterion used in Game theory is Maximin or Minimax.
Maximin Criterion. The player who is maximizing his outcome or payoff finds out his minimum
gains from each strategy (course of action) and selects the maximum value out of these
minimum gains.Minimax Criterion. In this criterion the minimizing player determines the
maximum loss from each strategy and then selects the strategy with minimum loss out of the
maximum loss list.
Example 8.1. Let us consider a two person zero sum game involving player A and player B. The
strategies available to player A are A1, A2 and A3 and to the player B are B1 B2. The payoff
matrix is given blow by assuming the values.

Let us suppose that if A starts the game and selects A strategy, player B will select B2 so that A
gets minimum gains. Similarly, if A adopts A3, B will adopt B1 strategy to minimize the gain of A.
Player A by selecting third strategy (A3) is maximizing his minimum gain. Player A’s selection is
called Maximum strategy. Player B by selecting second strategy (B2) is minimizing his maximum
loss. Player B’s selection is called Minimax strategy.
Example 8.2. Consider the following payoff matrix which represents Player A’s gain.

223
 Minimax

When player A plays strategy A1, he may gain 12, 4, 14 or 16 depending upon which strategy
player B plays. But player A is guaranteed minimum of 4 in any case. In each row minimum
gain guaranteed is 4, 6 and – 6. The maximum out of this is 6, so player A by selecting his
second strategy A2 is maximizing his minimum gains. Player B1 he cannot loose more than
maximum out of 12, 10 and 8, i.e., whatever strategy A adopts, B cannot loose more than 12.
Similarly, for strategies B2, B3 and B4 the maximum looses are 12, 6, 14 and 16. Thus, by
selecting B2 he minimizes his maximum loss.

CONCEPT OF VALUE OF GAME

In game theory the value of game is important to both the players. For the maximizing player, it
is the maximum guaranteed gain. For minimizing player, it is minimum loss. Consider the
following game ith payoff matrix as shown:

224
If player A adopts A1 strategy, he gains 4, if player B adopts B1 strategy he losses 4. In thiscase
maxi (min) = min (max).

CONCEPT OF SADDLE POINT OR EQUILIBRIUM POINT

In a payoff matrix the value, which is the smallest in its row and the largest in the column, is
called the saddle point.
Example 8.3. Let us consider the following payoff nature to illustrate the concept
of sddle or Equilibrium point

Saddle point can be found by :

1. Find out the minimum of the row and put a circle around it.
2. Find out the maximum of the column and put a square around it.
3. The value having bot the circle and the square is the saddle point. It should be
remembered that :
(i) Saddle point may or may not exist in a game. It is not necessary that all
payoffmatrixes will have a saddle point.
(ii) If there are more than one saddle points (which is a very rare occurrence), then
theproblem has more than one solution.
(iii) The values of the game could be positive or negative.
(iv) If the value of the game is zero, it is called a ‘fair game’.

Example 8.4. Find the ranges of value of P and Q, which will render the entry (2, ) a saddle point
for the game.
Player B
2 4 5

Player A 10 7 Q

4 P 6

225
Solution. Let us determine the maximin and minimax in te payoff matrix provided above

Maximum value = 7
Minimizing value 7 ignoring the values of P and Q now we want entry (2, 2), i.e., A2, B2 to be the
saddle point, i.e., 7 should be the minimum in the row A2, i.e., Q should be more than 7, i.e., Q
7. Similarly, we want 7 to be highest number out of 4, 7 and P. It means that P should be equal to
or lessor than 7, i.e., P £ 7.
Hence the range of P 7 and Q 7.
Example 8.5. Air Force of a country a wants to bomb the major enemy positions of country B.
Bombers of country A have the option of attacking either high or low. If they fly low they can
cause more damage to the enemy because of the accuracy they achieve. Country B will use its
fighter aircrafts to intercept looking either high or low. If the bombers avoid the fighter they
destroy 8 targets but if the fighter intercept them, no target can be destroyed. If the bombers are
able to fly low, they can destroy 4 extra targets before being intercepted.
Setup a game matrix. What advice you will give to commander of country A?

226
Let us find the saddle point. It can be easily seen that low-low entry 4 is the saddle point as it is
minimum in its row and maximum in its column.
Value of the game V = 4
Bombers of country A and fighters of country B will both fly low entry (2 – 2)
Solution of two persons zero sum games with mixed strategies
In case of pure game, if a saddle point exists it straight away gives the optimal solution. Some
games do not have saddle points. For example, let us consider the following zero-sum game :

In this matrix, the minimax value 9 is greater than the maximin value 8. The game does not have
a saddle point and the pure maximin-minimax strategies are not optimal. In this case the game
is said to be unstable.
have to use mixed strategies. Each player plays all his strategies according to some probabilities
rather than plays a pure strategy.
Let x1, x2, … , xm be the row probabilities by which player A selects his strategies.
Let y1, y2, …… , yn be the column probabilities of which player B selects his strategies then

Hence, if aij represents, the (i, j) entry of the game matrix, xi and yi will appaer as in the following matrix.

227
The solution of the mixed strategy problem is also based on the minimax criterion. However, if
A selects xi that maximizes the lowest expected payoff in a column and if B selects yj, it
minimizes the highest expected payoff in a row.
This will be illustrated in the examples that follow :

Odds Method
This method can be used only for 2 ¥ 2-matrix games. In this method we ensure that sum of
column odds and row odds is equal.

Finding out Odds

Step I. Take first row and find out the difference between values of cell (1, 1)
and
that of cell (1, 2) place this value in front of second row on the right
side.
Step II. Take second row, find out the difference
between the value of cell (2, 1) and that of cell
(2, 2). Place it in front of the first row on the
right side.
Step III. Take first column, find out the difference between the value of cell (1, 1)
and
that of value of cell (2, 1). Place it below the second column.
Step IV. Take second column, find out the difference between the value of cell
(1, 2)and that of the value of cell (2, 2). Place this value below the first column.
Example 8.6. Consider a modified form of “matching biased coins” game problem. The
matching player is paid Rs. 8 if two coins turn both heads and Rs. 1 if the coins turn both
tail. The non-matching player is paid Rs. 3 when the two coins do not match. Given the
choice of being the matching or non-matching players, which one would you choose and
what would be your strategy?

Solution. Let us prepare the payoff matrix.

228
 Let us see if the saddle point exists. Minimum of row one is – 3 and similarly
minimum of row two is also – 3, a circle has been put around these figures.
Maximum of column is 8 and that of column 2 is 1. A square has been put around
these two figures. There is no value, which is the lowest in its row and maximum of
its column. Hence no saddle point exists.
So, both the player will use mixed strategy.

(a) Take first row – difference between the cell A1 B1 and

A1 B28 – (– 3) = 8 + 3 = 11 place it in front of second
row.
(b) Take second row – difference between the cell A2 B1 and A2 B2
– 3 – 1 = – 4 (ignore sign)
(c) Take first column – 3 – 1 = – 4 (ignore sign)
(d) Take second column 8 – (– 3) = 11
Value of the game
For finding out the value of the game, following formula is used :

229
DOMINANCE METHOD OR PRINCIPLE OF DOMINANCE
This method basically states that if a particular strategy of a player dominates in values his other
strategies then this strategy, which dominates, can be retained and what is dominated is
deleted.
The dominance rule for column
Every value in the dominating column (s) must be equal to or less than the
corresponding valueof the dominated column.
The dominance rule for row
Every value in the dominating row (s) must be greater than or equal to the
corresponding value of the dominated row. A given strategy can be dominated if on
average its value is lesser than the average of two or more pure strategies. To illustrate
this point, consider the following game:
B
B1 B2 B3

A1 8 3 4
A A2 2 9 8
A3 3 4 5

230
This game has no saddle point. Also none of the pure strategies of A (A1, A2, A3) is lesser in
value to any of his other pure strategies. Let us find out the average of A’s pure and econd
pure strategies (A1 and A2).

This is superior to A’s third pure strategy (A3). Hence strategy A3 my be deleted
and thematrix becomes
B
B1 B2 B3

Sometimes game, which is reduced by dominance method, shows a saddle point but in
original matrix there was no saddle point. This saddle point must be ignored since it
does not have the properties of a saddle point, i.e., least value in its row and the
highest value in its column.

Example 8.7. Reduce the following game bydominance and find the game value:

Solution. Let us find if there is a saddle point in the matrix. This matrix has no saddle point.
From player A’s point of view, row III dominates row I as every value of row IV is either
equal to or greater than every value in row I. Hence, row I can be deleted. The reduced matrix
is

231
From player B’s point of view, column III dominates column I as every value of column
III is equal to or lesser than the value of column I. Hence, column I can be deleted. The
resulting matrix is

In the above matrix, no single row or column dominates another row or column. Let us find
if average of any two rows dominates the pure strategy of the other. There is no such
possibility. Now let us try if the average of any two columns dominates the third, i.e.,
if the average value of the two columns is equal to or less than the third average of
columns III and IV is

This values is equal to or lesser than value of column II so column II can be deleted. The resulting
matrix is

This is now a 2 ¥ 2 matrix and can be solved by Odds method.

232
 Step I. Subtract the two digits of column III and write them under column IV
(ignor-ing signs).
Step II. Subtract the two digits of column III and write
them under column IV (ignor-ing signs).
Step III. Subtract two digits of row III and write in front of row II (ignoring signs).
Step IV. Subtract two digits of row II and write it in front of row III (ignoring
sign)The resulting matrix with odds is as follows :
Probability of player A III
8/12, IV 4/12, i.e., 2/3,
1/3Probability of player B
III 8/12, I 4/12,i.e., 2/3,
1/3

Sub-Games Method for 2 ¥ n or m ¥ 2 Games

In this method we sub-divide the given game (2 ¥ n or m ¥ 2) into a number of 2 ¥ 2 games.
Now, each of these 2 ¥ 2 games can be solved and then optimal strategies are selected. These
are games when one of the players has 2 alternatives; where as the other player has more
than two alternatives. When there is no saddle point or the game cannot be solved by using
the dominance method the sub-games method is very useful. It is suitable when the number
of alternatives is limited to 4. In case of large number of alternatives, the solution becomes
lengthy and complicated. It follows the following procedure:
Step I. Divide the 2 ¥ n or m ¥ 2 game matrix in 2 ¥ 2 matrix sub-games.
Step II. Take up each game one by one and find out if a saddle point exists.
Such a
sub-game has pure strategies.
Step III. If the sub-game has no saddle point, then use
odds method to solve thesub-game.
Step IV. Select the best sub-game out of all the sub-games from the point of
view ofthe player who has more than two alternatives.
Step V. Find out the strategies of this selected sub-game. This is applicable to both
the players and for the entire game.
Step VI. Find out the value of the selected sub-game, this will be the value of the
whole game.

233
 Example 11.8. Two airlines A and B operate their flights to an island and are
interested in increasing their market share. Airline A has two alternatives, it either
advertises its special fare or it advertises its features unique to it. On the other hand,
airlines B have three alternatives of doing nothing, advertising their special fares or
advertising their own special features. The matrix showing gains and losses of the
two airlines in lakhs of rupees is shown below. Positive values favour airline or A
and negative values favour airline B. Find the value of the game and best strategy by
both the airlines using sub-game method.
Solution
Airline B
B1 B2 B3
Airline A A1 350 – 100 – 75
A2 200 180 175

A1 – Advertising special fares

A2 – Advertise special features
B1 – Do nothing
B2 – Advertise special fares
B3 – Advertise special features
This game has to be solved by sub-games method as per the requirement of the
question.
Step I. Let us divide the complete game (2 3) game as ( ¥ 2) game

234
 Solution to sub-game I

B
B1 B2 Odds

A1 350 – 100 50
A
A2 200 180 450

Odds 250 150

It has a saddle point, as minimum of row A2 is also the maximum of column B2.
Valueogame=180

Solution to sub-game II

As minimum of row A2 is the maximum of column B3, A2, B3 is the saddle point.
Value of game = 175
Solution to sub-game III

Step II. Select the best sub-game from the point of view of the player who has
morealternatives, i.e., B.

Sub-game Value

235
B will select that game which has minimum V.
B will select either sub-game II or III as both have equal V.

Step IV. Now, we find out the probabilities for the player A and B using their
strateies
while using sub-game II or III.

Example 8.9. Solve the following game b equal gains or probability method:

Solution. Let p be the probability of player A selecting strategy A1 so (1 – p) is the

probability of A selecting strategy A2, Also, let q be the probability of player B selecting
strategy B1 then (1 – q) will be the probability of B selecting strategy B2. Redraw the
matrix after introducing the probability.

236
 If player B selects strategy B1 then payoff to A will be 8p + (1 – p).
If player B selects strategy B2 payoff to
player A will be 2p + 6 (1 – p).Since payoff
under both the situations must be equal.
8p + 4 (1 – p) = 2p + 6 (1 – p)
8 p + 4 – 4p = 2p + 6 – 6p
8p = 2
1 3
P = , and (1 – p) =
4 4
Similarly,wecanworkoutthepayofftoplayerB
8q + 2 (1 – q) = 4q + 6 (1 – q)
8p+ 2 – 2q = 4 + 6 – 6q
1 1
8q = 4, q = , (1 – q) =
2 2
Value of game = (Expected pay off of player A when player B uses strategy B1) ¥
(Probability of player B using strategy B1) + (Expected
payoff player A when player B usesstrategy B2) ¥ (Probability
of player B using strategy B2)
= [{8p + 4 (1 – p)} + q + {2p + 6 (1 – p)} ¥ (1 – q)]
= [(8p + 4 – 4p) q + (2p + 6 – 6p) (1 – q)]
= [(4p + 4) q +(– 4p + 6) (1 – q)]
= [4pq + 4q + (6 – 6q – 4p + 4pq)]
= (4pq + 4q + 6 – 6q – 4p + 4pq)
= – 4p – 2q + 8pq + 6

Substituting the value of p and q, we get the value of game.

237
Example 11.10. Player X is paid Rs. 10 if two coins turn both Heads and Rs. 2 if both coins
turn both Tails. Player Y is paid Rs. 4 when the two coins do not match. If you had the choice
of becoming player X or player Y, which one would you like to be and what will be your
strategy ?
Solve the problem using equal gains or probability method.
Solution. Let us construct the payoff matrix for the given problem.

Let p be the probability of player X selecting strategy X1 so, (1 – p) is the probability of

player X selecting strategy X2, similarly, let q be the probability of player Y selecting
strategy Y1 then (1 – q) will be the probability of player Y selecting strategy Y 2. If player Y
selects strategy Y1then payoff to player X is

238
Now let us calculate the value of the game.
V = (Expected pay off of player X when player Y uses strategy Y1) ¥ probability of player Y
using strategy Y1) + (Expected pay off of player Y using strategy Y2) ¥ (probability of player Y
using strategy Y2)

239
 Graphical Solution of (2 ¥ n) and (m ¥ 2) Games
Such solutions are possible only to the games in which at least one of the players has only two
strategies. Let us consider a (2 ¥ n) game of player A and B. Player A has only two strategies
with probabilities p1 and p2 where p2 = 1 – p and player B has n strategies. Te game does not
have a saddle point.

A’s expected payoff corresponding to the pure strategies of B are as follows : B’s pure
strategy A’s expected payoff
B1 a11 p1 + a21 (1
– p1) = (a11 – a21) p1

240
 + a21 B2 a12 p1 + a22
(1 – p1) = (a12 – a22) p1 +
a22 B3 a13 p1 + a23 (1 –
p1) = (a13 – a23) p1 +
a23
: : : : :
Bn a1 n p1 + a2 n (1 – p1) = (a1 n – a2 n) p1 + a2 n

A should selects such a value of p1 in such a manner that it maximizes his minimum payoff.
This can be done by plotting the payoff equations as straight line of functions of p1.
The steps involved in this solutions are as follows :
Step I. The game must be reduced to such a sub-game that at least one of
the playershas only two strategies.
Step II. Take the probability of two alternatives of a player (say A) having only
two strategies as p1 and (1 – p1). We formulate equations of net gain of
A from different strategies of B.
Step III. Two parallel lines are drawn on the graph to include the boundaries of
two
strategies of first player say A.
Step IV. Pay off equations as functions of probabilities of two alternatives of A
for differ- ent strategies of player B are plotted on the graph as
straight-line functions of P.
Step V. If player A is maximizing, the point is identified where minimum
expected gain is maximized, on the other hand, in case of minimizing
player B, the point as identified where maximum loss is minimized.
The method will be demonstrated with the help of an example.
Example 11.11. Solve the following game using the graphic method.

Solution. The game does not have a saddle point. A’s expected payoff according to the
pure strategies of B is shown in the matrix below. p is the probability of A selecting
strategy 1 and (1 – p1) is the probability of A selecting strategy 2.

B’s Strategy A’s expected payoff

B1 2p + 4 (1 – p) = – 2p + 4

B2 2p + 3 (1 – p) = – p + 3

B3 3p + 2 (1 – p) = p + 2

241
 B4 – p + 6 (1 – p) = – 7p + 6

1
It can be seen from the graph that maximin occurs at p = . This is the point of inter-
2
section of any two of the lines.1Hence As optimal strategy is p = 1 , 1
– p = . The value of
2 2
game can be found out by substituting the value of p in the equation of any
of the lines passing through P

P is the point of intersection of any three of the lines B2, B3 and B4. To find out the
optimal strategies of B as three lines pass through P, it indicates that B can mix all the
three strategies, i.e., B2, B3 and B4. The combination of B2 – B3, B3 – B4, B2 – B4 and
must be considered.
Example 8.12. A is paid Rs. 8 if coins turn both heads and Rs. 1 if two coins turn both

242
 tail B. wins Rs 3 when the two coins do not match give the choices t be a or B. Find the
values of Game.

Solution. The above problem does not have saddle point, the players will use mixed
strategy. Let p1 be the probability of player A selecting strategies I (1 – p1) is probability
the player A will select strategy II Similarly, q1 is the probability. of player B selecting
strategy II(1 – q1) is probability of player B selecting I.

243
 Example 11.13. Solve the following game.
B
I II
A I –6 7
II +4 –5
III –1 –2
IV –2 5
V 7 –6
Solution.
B
I –6 7
II 4 –5
A III –1 –2
IV –2 5
V 7 –6

The above game does not have a saddle point and no row or column is dominated.
W will ply sub-game method

Sub-game I
B
I II Odds

A I –6 7 – 4 – (5) = 9

II 4 –5 – 6 – 7 = 13

Odds 7 – (–5) = 12 –6 – 4 = 10

244
 Sub-game II
B
I II Odds
A I –6 7 –1 – (–2) = 1
II –1 –2 – 6 – (7) = 13
7 – (–2) = 9 – 6 – (–1) = 5

Sub-game II
B
I II
A I –6 7
IV 2 5

245
246
247