Optimisation Models- II-munotes

Page 1

1
MODULE - I
ASSIGNMENT TECHNIQUES
1.1
ASSIGNMENT MODEL
Definition of Assignment Model, Mathematical Representation of
Assignment Model, Examples
1.1.1 Introduction
1.1.2 Objectives
1.1.3 Definition of Assignment Model or Assignment Problem (AP)
1.1.4 Mathematical Representation of AP
1.1.5 Examples of AP
1.1.6 Let us sum up
1.1.7 Exercises
1.1.8 Suggested Readings
1.1.1 INTRODUCTION
In this Unit-I - Chapter 1.1, we shall discuss the concept of
assignment model and formulation of the assignment model.
1.1.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand the definition of assignment model also called as
the assignment problem
/g120Understand the mathematical representation of assignment
model
/g120Understand the situations where the assignment model
becomes important.munotes.in

Page 2

2
1.1.3 – DEFINITION OF ASSIGNMENT MODEL OR
ASSIGNMENT PROBLEM (AP)
Assignment problem is a special type of linear programming
problem which deals with the allocation of the various resources to
the various activities on one to one basis. It does it in such a way
that the cost or time involved in the process is minimum and profit
or sale is maximum.
In a factory, a supervisor may have six workers available
and six jobs to fire. He will have to take decision regarding which
job should be given to which worker. Problem forms one to one
basis. This is an assignment model also known as an assignment
problem hereafter.
1.1.4 - Mathematical Representation of AP
As we know, the AP is a special type of Linear Programming
Problem (LPP) where assignees are being assigned to perform
task. For example, the assignees might be employees who need to
be given work assignments. However, the assignees might not be
people. They could be machines or vehicles or plants or even time
slots to be assigned tasks. To fit the definition of an assignment
problem, the problem need to formulate in a way that satisfies the
following assumptions:
/g120 The number of assignees and the number of tasks are the same
/g120 Each assignees is to be assigned to exactly one task
/g120 Each task is to performed by exactly one assignee
/g120 There is a cost Cij associated with assignee i performing task j.
/g120 The objective is to determine how all n assignments should be
made to minimize the total cost.
/g120 Any problem satisfying all these assumptions can be solved
extremely efficiently by algorithm designed specifically for
assignment problem.
Any problem satisfying all these assumptions can be solved
extremely efficiently by algorithm designed specifically for
assignment problem.munotes.in

Page 3

3
Mathematical form
Xij/g1490 for all i and j.
The first set of functional constraints specifies that each
assignee is to perform exactly one task, whereas the second set
requires each task to be performed by exactly one assignee.
1.1.5 EXAMPLES OF AP
In many business situations, management needs to assign -
personnel to jobs, - jobs to machines, - machines to job locations,
or - salespersons to territories.
Consider the situation of assigning njobs to nmachines.
When a job i (=1,2,....,n) is assigned to machine j (=1,2, .....n) that
incurs a cost Cij.
The objective is to assign the jobs to machines at the least possible
total cost. This situation is as the assignment problem .
The job and the machine assignment cost per job is given in the
following matrix called as the assignment cost matrix.munotes.in

Page 4

4
The assignment model can be expressed mathematically as
follows:
Xij= 0, if the job j is not assigned to machine i
Xij= 1, if the job j is assigned to machine i.
Other examples of management assignment situations are as
under:
/g120Ballston Electronics manufactures small electrical devices.
/g120Products are manufactured on five different assembly lines
(1,2,3,4,5).
/g120When manufacturing is finished, products are transported from
the assembly lines to one of the five different inspection areas
(A,B,C,D,E).
/g120Transporting products from five assembly lines to five inspection
areas requires different times (in minutes)munotes.in

Page 5

5
1.1.6 LET US SUM UP
In this UNIT 1 - Chapter 1.1, you have learnt the introduction
and the definition of AP, mathematical representation of AP,
assignment cost matrix formulation for an AP and examples of
management assignment situations.
1.1.7.EXERCISES
1. Define an assignment problem and develop the assignment
cost matrix for a hypothetical situation of your choice.
2. Give examples two examples of situations that resemble an
assignment problem.
3. What do you understand by assignment cost matrix? Give an
example of 2X2 assignment cost matrix.
1.1.8 SUGGESTED READINGS
Assignment problem section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 6

6
1.2
HUNGARIAN METHOD
Hungarian Method of Solution of Assignment Model, Examples
Unit Structure
1.2.1 Introduction
1.2.2 Objectives
1.2.3 Hungarian Method of Solution of Assignment Model or
Assignment Problem (AP)
1.2.4 Solving AP using Hungarian Method
1.2.5 Let us sum up
1.2.6 Exercises
1.2.7 Suggested Readings
1.2.1 INTRODUCTION
In this Unit-I - Chapter 1.2, we shall discuss the Hungarian Method
used to solve the assignment problem.
1.2.2 OBJECTIVES
At the end of this unit the learners will be able to
a. Understand the Hungarian Method for solving the assignment
problem
1.2.3 HUNGARIAN METHOD
The Hungarian algorithm consists of the four steps. The first
two steps are executed once, while Steps 3 and 4 are repeated
until an optimal assignment is found. The input of the algorithm is
an n by n square matrix with only nonnegative elements.
1. Subtract the smallest number in each row from every number in
the row. This is called row reduction
2. Subtract the smallest number in each column of the new table
from every number in the column. This is called column
reduction.munotes.in

Page 7

7
3. Test whether an optimal assignment can be made. You do this
by determining the minimum number of lines to cover all zeros.
If the number of lines equals the number of rows, an optimal set
of assignment is possible. Otherwise go on to step 4
4. If the number of lines is less than the number of rows, modify
the table in the following way
(a) Subtract the smallest uncovered number from every
uncovered number in the table
(b) Add the smallest uncovered number to the numbers at
intersections of covering lines
(c) Numbers crossed out but at the interactions of cross out
lines carry over unchanged to the next table
5. Repeat step 3 and 4 until an optimal set of assignments is
possible.
6. Make the assignments one at a time in positions that have zero
elements. Begin with rows or columns that have only one zero.
Since each row and each column needs to receive exactly one
assignment, cross out both the row and the column involved
after each assignment is made. Then move on to the rows and
such row or column that are not yet crossed out to select the
next assignment, with preference again given to any such row
or column that has only one zero that is not crossed out.
Continue until every row or column has exactly one assignment
and so has been crossed out.
1.2.4 SOLVING AP USING HUNGARIAN METHOD
Hungarian Method – Example 1
We consider an example where four jobs (1, 2, and 3) need
to be executed by four three machines (1, 2, and 3), one job per
one machine. The matrix below shows the cost of assigning a job to
a machine. The objective is to minimize the total cost of the
assignment.
Step 1: Select the smallest value in each row.
Subtract this value from each value in that row
Step 2: Do the same for the columns that do not have any zero
valuemunotes.in

Page 8

8
If not finished, continue with other columns.
Step 3: Assignments are made at zero values.
Therefore, we assign job 1 to machine 1; job 2 to machine 3, and
job 3 to machine 2.Total cost is 5+12+13 = 30.
It is not always possible to obtain a feasible assignment as in here.
Since the number of jobs and number of machines are all assigned,
it is an optimal assignment with the order job1 /g198machine 1, job2
/g198to machine 2, job 3 /g198machine 3 and the minimum cost of
assignment is 5+12+13 = 30 unitsmunotes.in

Page 9

9
Hungarian Method – Example 2
A feasible assignment is not possible at this moment.In such
ac a s e ,t h ep r o c e d u r ei st od r a wam i n i m u mn u m b e ro fl i n e s
through some of the rows and columns, Such that all zero values
are crossed out.
The next step is to select the smallest uncrossed out
element. This element is subtracted from every uncrossed out
element andadded to every element at the intersection of two lines.munotes.in

Page 10

10
We can now easily assign to the zero values. Solution is to
assign (1 to 1), (2 to 3), (3 to 2) and (4 to 4).
If drawing lines do not provide an easy solution, then we
should perform the task of drawing lines one more time.
Actually, we should continue drawing lines until a feasible
assignment is possible.
Now since there is one to one assignment, optimal feasible
solution has been reached and the minimum cost of assignment is
1+10+5+8 = 24.
Hungarian Method – Example 3
At the head office of a college there are five registration
counters. Five persons are available for service.
How should the counters be assigned to persons so as
to maximize the profit?
Here, the highest value is 62. So we subtract each value
from 62. The conversion is shown in the following table.
munotes.in

Page 11

11
Now this table must be used to solve the assignment
problem using the Hungarian method.
The total cost of assignment = 1C + 2E + 3A + 4D + 5B.
Substituting the values from the original table, the total cost is
40 + 36 + 40 + 36 + 62 = 214.
1.2.5 LET US SUM UP
In this INIT – I - Chapter 1.2, you have learnt the Hungarian Method
to solve the AP.
1.2.6.EXERCISES
Question 1 .Solve the assignment problem given below:
Answer: Worker 1 should perform job 3, worker 2 job 2, worker 3
job 1, and worker 4 should perform job 4. The total cost of this
optimal assignment is to 69 + 37 + 11 + 23 = 140.
Question 2. The Funny Toys Company has four men available for
work on four separate jobs. Only one man can work on any one job.
The cost of assigning each man to each job is given in the following
table. The objective is to assign men to jobs in such a way that the
total cost of assignment is minimum.
Job
Person 1 2 3 4
A2 0 2 5 2 2 2 8
B1 5 1 8 2 3 1 7
C1 9 1 7 2 1 2 4
D2 5 2 3 2 4 2 4
Answer: The total cost of assignment = A1 + B4 + C2 +
D3.Substituting values from original table:20 + 17 + 17 + 24 = Rs.
78.munotes.in

Page 12

12
Question 3. Find an optimal solution to an assignment problem with
the following cost matrix:
Answer: Jl->M2, J2->M6, J3->M1, J4->M3, J5->M5, J6->M4 and
the minimum cost= $ (5 + 0+ 6 +15 + 6 + 5) = $ 37.
1.2.7 SUGGESTED READINGS
Hungarian Method to solve the Assignment problem in any of the
reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 13

13
1.3
VARIATION OF THE ASSIGNMENT
MODEL
Variation of the Assignment Model
Unit Structure
1.3.1 Introduction
1.3.2 Objectives
1.3.3 Variation of the Assignment Model – Unbalanced
Assignments
1.3.4 Let us sum up
1.3.5 Exercises
1.3.6 Suggested Readings
1.3.1 INTRODUCTION
In this Unit-I - Chapter 1.3, we shall discuss the variations in the
assignment model.
1.3.2 OBJECTIVES
At the end of this unit the learners will be able to
a. Understand the Hungarian Method for solving the unbalanced
assignment problem.
1.3.3 VARIATION OF THE ASSIGNMENT MODEL –
UNBALANCED ASSIGNMENTS
Unbalanced Assignment Problem
Whenever the cost matrix of an assignment problem is not a
square matrix, that is, whenever the number of sources (rows) is
not equal to the number of destinations (columns), the assignment
problem is called an unbalanced assignment problem. In such
problems, dummy rows (or columns) are added in the matrix so as
to complete it to form a square matrix. The dummy rows or columns
will contain all costs elements as zeroes. The Hungarian method
may be used to solve the problem.munotes.in

Page 14

14
Example 1 . A company has 4 machines on which to do 3 jobs.
Each job can be assigned to one and only one machine. The cost
of each job on each machine is given in the following table:
Solution to Example 1:
munotes.in

Page 15

15
Restricted Assignment Problem
Ar e s t r i c t e da s s i g n m e n tp r o b l e mi st h eo n ei nw h i c ho n eo r
more allocations are prohibited or not possible. For such allocations
we assign “M”, which is infinitely high cost. No allocation is given
in M.
Travelling Salesman Problem
The traveling salesman problem consists of a salesman and
a set of cities. The salesman has to visit each one of the cities
starting from a certain one (e.g. the hometown) and returning to themunotes.in

Page 16

16
same city. The challenge of the problem is that the traveling
salesman wants to minimize the total length of the trip.
The method to solve the travelling salesman problem is
out of the present course.
1.3.4 LET US SUM UP
In this Unit I - Chapter 1.3, you have learnt the Hungarian Method
to solve the AP and the variations in AP.
1.3.5.EXERCISES
Question 1: Ac o m p a n yh a s5j o b st ob ed o n e .T h ef o l l o w i n g
matrix shows the return in terms of rupees on assigning ith( i = 1, 2,
3, 4, 5 ) machine to the jth job ( j = A, B, C, D, E ). Assign the five
jobs to the five machines so as to maximize the total expected
profit.
Answer: Optimal assignment 1 – C 2 – E 3 – D 4 – B 5 – A
Maximum profit = 10 + 5 + 14 + 14 + 7 = Rs. 50
Question 2:
Solve the given unbalanced assignment problem.
Answer: Minimum cost is 54 .munotes.in

Page 17

17
Question 3:
You work as a sales manager for a toy manufacturer, and
you currently have three salespeople on the road meeting buyers.
Your salespeople are in Austin, TX; Boston, MA; and Chicago, IL.
You want them to fly to three other cities: Denver, CO; Edmonton,
Alberta; and Fargo, ND. The table below shows the cost of airplane
tickets in dollars between these cities.
Where should you send each of your salespeople in order to
minimize airfare?
Answer: Optimal assignment is:
Total cost of assignment is: $400 + $350 + $200 = $950.
1.3.6 SUGGESTED READINGS
Hungarian Method to solve the unbalanced Assignment problem in
any of the reference / text books
/g3/g3
/g153/g153/g153/g153/g3munotes.in

Page 18

18
MODULE - II
TRANSPORTATION TECHNIQUES – I
2.1
TRANSPORTATION MODEL
Introduction to Transportation Model, Definition of Transportation
Model, Matrix Terminology
Unit Structure
2.1.1 Introduction
2.1.2 Objectives
2.1.3 Definition of Transportation Model or Transportation
Problem (TP)
2.1.4 Matrix Representation of TP
2.1.5 Examples of TP
2.1.6 Let us sum up
2.1.7 Exercises
2.1.8 Suggested Readings
2.1.1 INTRODUCTION
In this Unit-II - Chapter 2.1, we shall discuss the concept of
transportation model also known as the transportation problem (TP)
and formulation of the transportation problem.
2.1.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand the definition of transportation model also called as
the transportation problem (TP).
/g120Understand the matrix representation of transportation problem
/g120Understand the situations where the transportation problem
becomes important.munotes.in

Page 19

19
2.1.3 DEFINITION OF TRANSPORTATION MODEL OR
TRANSPORTATION PROBLEM (TP)
The transportation problem is a special type of linear
programming problem where the objective is to minimize the cost of
distributing a product from a number of sources ororigins to a
number of destinations. Because of its special structure the usual
simplex method is not suitable for solving transportation problems.
These problems require a special method of solution. The origin of
a transportation problem is the location from which shipments are
dispatched.
The destination of a transportation problem is the location
to which shipments are transported.
2.1.4 MATRIX REPRESENTATION OF TP
The unit transportation cost is the cost of transporting one unit of
the consignment from an origin to a destination.
2.1.5 EXAMPLES OF TP
Example 1: Balanced transportation model.
Consider the following problem with 2 factories and 3 warehouses:munotes.in

Page 20

20
Example 2: Unbalanced transportation model
There are two cases to consider, namely excess demand
and excess supply.
Suppose the demand at warehouse 1 above is 9 units. Then
the total supply and total demand are unequal, and the problem is
unbalanced. In this case it is not possible to satisfy all the demand
at each destination simultaneously. We reformulate the model as
follows: since demand exceeds supply by 2 units, we introduce a
dummy source (i.e. a fictitious factory) which has a capacity of 2.
The amount shipped from this dummy source to a destination
represents the shortage quantity at that destination.
It is necessary to specify the costs associated with the
dummy source. There are two situations to consider.
(a) Since the source does not exist, no shipping from the source will
occur, so the unit transportation costs can be set to zero.
(b) Alternatively, if a penalty cost, P, is incurred for every unit of
unsatisfied demand, then the unit transportation costs should be set
equal to the unit penalty costs.
In effect we are allocating the shortage to different destinations.munotes.in

Page 21

21
2. If supply exceeds demand then a dummy destination is added
which absorbs the surplus units. Any units shipped from a source to
a dummy destination represent a surplus at that source. Again,
there are two cases to consider for how the unit transportation
costs should be determined. (a) Since no shipping takes place, the
unit transportation costs can be set to zero. (b) If there is a cost for
storing, S, the surplus production then the unit transportation costs
should be set equal to the unit storage costs.
Here we are allocating the excess supply to the different
destinations. From now on, we will discuss balanced transportation
problems only, as any unbalanced problem can always be
balanced according to the above constructions
2.1.6 LET US SUM UP
In this unit we have seen the definition of transportation model also
called as the transportation problem (TP) and we have understood
the matrix representation of transportation problem and the
situations where the transportation problem becomes important.
2.1.7.EXERCISES
Question 1: Explain the concept of transportation problem (TP)
and give one example.
Question 2: What do you understand by transportation cost
matrix?
2.1.8 SUGGESTED READINGS
Transportation problem section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 22

22
2.2
TRANSPORTATION MODEL
Formulation and Solution of Transportation Model
Unit Structure
2.2.1 Introduction
2.2.2 Objectives
2.2.3 Formulation and Solution of Transportation Model
2.2.4 North – West Corner Rule
2.2.5 Least Cost Method
2.2.6 Vogel’s Approximation or Penalty Method
2.2.7 Post – Optimality Analysis
2.2.8 Let us sum up
2.2.9 Exercises
2.2.10 Suggested Readings
2.2.1 INTRODUCTION
In this Unit-II - Chapter 2.2, we shall discuss formulation and
solution of transportation problem (TP) and method of optimizing
the TP.
2.2.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand formulation and solution of transportation problem
(TP)
/g120Understand the North – West Corner Rule, Least Cost Method
and Vogel’s Approximation or Penalty Method to find the initial
basic feasible solution to the transportation problem
/g120Understand the Vogel’s Approximation or Penalty Method to
optimize the transportation problem
/g120Understand the Post – Optimality Analysis of the transportation
problemmunotes.in

Page 23

23
2.2.3 FORMULATION AND SOLUTION OF
TRANSPORTATION MODEL
Powerco has three electric power plants that supply the
needs of four cities. Each power plant can supply the following
numbers of kilowatt-hours (kwh) of electricity: plant 1— 35 million;
plant 2—50 million; plant 3—40 million. The peak power demands
in these cities, which occur at the same time (2 P.M.), are as
follows (in kwh): city 1—45 million; city 2—20 million; city 3—30
million; city 4—30 million. The costs of sending 1 million kwh of
electricity from plant to city depend on the distance the electricity
must travel. Formulate the problem as a transportation problem to
minimize the cost of meeting each city’s peak power demand.munotes.in

Page 24

24
2.2.4 NORTH – WEST CORNER RULE
(ai and bj denote supply and demand respectively)
Make the transportation problem as minimization and
balanced problem and then follow the following steps.munotes.in

Page 25

25
Step1: Select the upper left (north-west) cell of the transportation
matrix and allocate the maximum possible value to X11 which is
equal to min(a1,b1).
Step2:
If allocation made is equal to the supply available at the first source
(a1 in first row), then move vertically down to the cell (2,1).
If allocation made is equal to demand of the first destination (b1 in
first column), then move horizontally to the cell (1,2).
If a1=b1 , then allocate X11= a1 or b1 and move to cell (2,2).
Step3: Continue the process until an allocation is made in the
south-east corner cell of the transportation table.
Example: Solve the Transportation Table to find Initial Basic
Feasible Solution using North-West Corner Method.
Total Cost =19*5+30*2+30*6+40*3+70*4+20*14 = Rs. 1015
2.2.5 LEAST COST METHOD
Step1: Select the cell having lowest unit cost in the entire table and
allocate the minimum of supply or demand values in that cell.
Step2: Then eliminate the row or column in which supply or
demand is exhausted. If both the supply and demand values are
same, you can eliminate either of the row or column.
In case, the smallest unit cost is not unique, then select the cell
where maximum allocation can be made.
Step3: Repeat the process with next lowest unit cost and continue
until the entire available supply at various sources and demand at
various destinations is satisfied.munotes.in

Page 26

26
The total transportation cost obtained by this method
= 8*8+10*7+20*7+40*7+70*2+40*3
=R s . 8 1 4
Here, we can see that the Least Cost Method involves a lower cost
than the North-West Corner Method.
2.2.6 VOGEL’S APPROXIMATION OR PENALTY
METHOD
Step1: Calculate penalty for each row and column by taking the
difference between the two smallest unit costs. This penalty or
extra cost has to be paid if one fails to allocate the minimum unit
transportation cost.
Step2: Select the row or column with the highest penalty and select
the minimum unit cost of that row or column. Then, allocate the
minimum of supply or demand values in that cell. If there is a tie,
then select the cell where maximum allocation could be made.
Step3: Adjust the supply and demand and eliminate the satisfied
row or column. If a row and column are satisfied simultaneously,
only of them is eliminated and the other one is assigned a zero
value. Any row or column having zero supply or demand cannot be
used in calculating future penalties.munotes.in

Page 27

27
Step4: Repeat the process until all the supply sources and demand
destinations are satisfied.
The total transportation cost obtained by this method
= 8*8+19*5+20*10+10*2+40*7+60*2 = = Rs.779
Here, we can see that Vogel’s Approximation Method involves the
lowest cost than North-West Corner Method and Least Cost
Method and hence is the most preferred method of finding initial
basic feasible solution.
munotes.in

Page 28

28
2.2.7 POST – OPTIMALITY ANALYSIS – MODI
METHOD
Examining the Initial Basic Feasible Solution for Non -
Degeneracy
If the number of allocations is < (m+n-1) then put a very
small hypothetical allocation /g188in the non-allocated cell with least
cost and use the MODI method to further optimize the
transportation solution.munotes.in

Page 29

29
Transportation Algorithm for Minimization Problem (MODI
Method)
Step1: Construct the transportation table entering the origin
capacities ai, the destination requirement bjand the cost cij
Step2: Find an initial basic feasible solution by vogel’s method or
by any of the given method.
Step3: For all the basic variables xij, solve the system of equations
ui + vj = cij, for all i, j for which cell(i, j) is in the basis, starting
initially with some ui = 0, calculate the values of ui and vj on the
transportation table
Step4: Compute the cost differences dij = cij – ( ui + vj ) for all the
non-basic cells
Step5: Apply optimality test by examining the sign of each dij
/g120If all dij /g1490, the current basic feasible solution is optimal
/g120If at least one dij< 0, select the variable xrs (most negative) to
enter the basis.
/g120Solution under test is not optimal if any dij is negative and
further improvement is required by repeating the above process.
Step6: Let the variable Xrs enter the basis. Allocate an unknown
quantity /g1318to the cell (r, s). Then construct a loop that starts and
ends at the cell (r, s) and connects some of the basic cells. The
amount /g1318is added to and subtracted from the transition cells of the
loop in such a manner that the availabilities and requirements
remain satisfied.
Step7: Assign the largest possible value to the /g1318in such a way
that the value of at least one basic variable becomes zero and the
other basic variables remain non-negative. The basic cell whose
allocation has been made zero will leave the basis.
Step8: Now, return to step 3 and repeat the process until an
optimal solution is obtained.munotes.in

Page 30

30
Example
/g120Find an optimal solution
/g120Find the initial basic feasible solution using Vogel’s
approximation method.
/g120Check for Non-degeneracy
The initial basic feasible solution has m + n – 1 i.e. 3 + 4 – 1 = 6
allocations in independent positions. Hence optimality test is
satisfied.
/g120Calculation of uiand vj: - ui+ vj= cij
Assign a ‘u’ value to zero. (Convenient rule is to select the ui, which
has the largest number of allocations in its row)
Let u3 = 0, then
u3 + v4= 20 which implies 0 + v4 = 20, so v4 = 20
u2 + v4= 60 which implies u2 + 20 = 60, so u2 = 40
u1 + v4= 10 which implies u1 + 20 = 10, so u1 = -10
u2 + v3= 40 which implies 40 + v3 = 40, so v3 = 0
u3 + v2= 8 which implies 0 + v2 = 8, so v2 = 8
u1 + v1= 19 which implies -10 + v1= 19, so v1 = 29munotes.in

Page 31

31
/g120Calculation of cost differences for non-basic cells dij= cij– (
ui+ vj)
/g120Optimality test
dij< 0 i.e. d22 = -18 so X22is entering the basis
/g120Construction of loop and allocation of unknown quantity /g1318
We allocate /g1318to the cell (2, 2). Reallocation is done by transferring
the maximum possible amount /g1318in the marked cell. The value of /g1318
is obtained by equating to zero to the corners of the closed loop.
i.e. min(8- /g1318,2 -/g1318)=0w h i c hg i v e s /g1318=2 .T h e r e f o r ex 2 4i so u t g o i n g
as it becomes zero.
Minimum transportation cost is 5 (19) + 2 (10) + 2 (30) + 7 (40) + 6
(8) + 12 (20) = Rs. 743munotes.in

Page 32

32
/g120Improved Solution
Since dij> 0, an optimal solution is obtained with minimal cost
Rs.743
2.2.8 LET US SUM UP
In this unit we have seen the formulation of transportation model,
North – West Corner Rule, Least Cost Method, Vogel’s
Approximation or Penalty Method and Post – Optimality Analysis.
2.2.9. EXERCISES
Question 1: Explain the method of formulation of transportation
problem (TP) and give an example.
Question 2: Solve by North West corner, least cost and Vogel’s
method obtain an optimal solution for the following problem.
munotes.in

Page 33

33
Question 2 Answer:
Minimum transportation cost is 1 (50) + 3 (90) + 2 (200) + 2 (50) =
Rs. 820
Question 3:
When the evaluation of any empty cell yields the same cost
as the existing allocation, an alternate optimal solution exists
(see Stepping Stone Method – alternate solutions). Assume that all
other cells are optimally assigned. In such cases, management has
additional flexibility and can invoke no transportation cost factors in
deciding on a final shipping schedule.
Degeneracy exists in a transportation problem when the
number of filled cells is less than the number of rows plus the
number of columns minus one (m + n - 1). Degeneracy may be
observed either during the initial allocation when the first entry in a
row or column satisfies both the row and column requirements
or during VAM method application, when the added and subtracted
values are equal. Degeneracy requires some adjustment in the
matrix to evaluate the solution achieved. The form of this
adjustment involves inserting some value in an empty cell so a
closed path can be developed to evaluate other empty cells. This
value may be thought of as an infinitely small amount, having no
direct bearing on the cost of the solution.
A fictive corporation A has a contract to supply motors for all
tractors produced by a fictive corporation B. Corporation B
manufactures the tractors at four locations around Central Europe:
Prague, Warsaw, Budapest and Vienna. Plans call for the following
numbers of tractors to be produced at each location:
/g120Prague 9000
/g120Warsaw 12000
/g120Budapest 9000
Corporation A has three plants that can produce the motors. The
plants and production capacities are
/g120Hamburg 8000
/g120Munich 7000
/g120Leipzig 10000
/g120Dresden 5000munotes.in

Page 34

34
Due to varying production and transportation costs, the profit
earns on each motor depends on where they were produced and
where they were shipped. The following transportation table gives
the accounting department estimates of the euro profit per unit
(motor).
Convert the profit matrix into cost matrix, by subtracting
every cell element from the maximum element and then solve the
following matrix for initial basic feasible solution:
Shipped to
Produced atPrague Warsaw Budapest Source
Capacity
Hamburg 60 40 0 8000
Munich 50 0 70 7000
Leipzig 65 20 30 10000
Dresden 35 50 95 5000
Destination
Capacity9000 12000 9000 30000
Answer: (Cell Hamburg - Budapest was assigned first, Munich
- Warsaw second, Leipzig - Warsaw third, Leipzig – Budapest
fourth, Dresden – Prague fifth and Leipzig – Prague sixth.) Total
profit: 3335000 euro.
2.2.10 SUGGESTED READINGS
Transportation problem section in any of the reference / text books
/g153/g153/g153/g153/g153/g3
/g3munotes.in

Page 35

35
2.3
TRANSPORTATION MODEL
Variants in Transportation Model
Unit Structure
2.3.1 Introduction
2.3.2 Objectives
2.3.3 Variants in Transportation Model
2.3.4 Let us sum up
2.3.5 Exercises
2.3.6 Suggested Readings
2.3.1 INTRODUCTION
This chapter introduces you to variations in transportation
problems like degeneracy and alternate optimal solution
2.3.2 OBJECTIVES
After studying this unit you will be able to understand
/g120Variation in Transportation Problem.
2.3.3 VARIANTS IN TRANSPORTATION MODEL
If the basic feasible solution of a transportation problem with
m origins and n destinations has fewer than m + n – 1 positive xij
(occupied cells), the problem is said to be a degenerate
transportation problem. Degeneracy can occur at two stages:
/g120At the initial solution
/g120During the testing of the optimal solution.
Ad e g e n e r a t eb a s i cf e a s i b l es o l u t i o ni nat r a n s p o r t a t i o n
problem exists if and only if some partial sum of availability’s
(row(s)) is equal to a partial sum of requirements (column(s)).
To resolve degeneracy, we make use of an artificial quantity
(d). The quantity d is assigned to that unoccupied cell, which has
the minimum transportation cost.munotes.in

Page 36

36
/g190Degeneracy in Transportation Problem Example
Initial Basic Feasible Solution
Number of basic variables = m + n – 1 = 3 + 4 – 1 = 6
Since number of basic variables is less than 6, therefore, it is a
degenerate transportation problem.
To resolve degeneracy , we make use of an artificial
quantity(d). The quantity d is assigned to that unoccupied cell,
which has the minimum transportation cost.
The quantity d is so small that it does not affect the supply
and demand constraints.
In the above table, there is a tie in selecting the smallest
unoccupied cell. In this situation, you can choose any cell
arbitrarily. We select the cell C2 as shown in the following table.munotes.in

Page 37

37
Using the MODI method the final optimal solution will be as under:
The optimal solution is
2X2 0 0+2X8 0 0+4X7 0 0+2Xd+1X5 0 0+0X4 0 0=5 3 0 0+2 d .
Notice that dis a very small quantity so it can be neglected in the
optimal solution . Thus, the net transportation cost is Rs. 5300.
/g190What do you think happens when the problem is
maximization instead of a minimization problem?
a) Identify the largest value in the tableau and subtract all the other
cell “profits” from that value.
b) Then replace the original cell profits with the resulting values.
These values reflect the opportunity costs that would be incurred by
using routes with unit profits that are less than the largest unit profit.
c) Then solve the tableau in the usual way for the minimum cost
solution. Minimizing lost opportunity costs is the same as
maximizing the total profit. The optimal solution would have to be
transformed to the original “profits” so as to find the optimal value in
the original problem.
/g190Am u l t i p l eo p t i m a ls o l u t i o nmunotes.in

Page 38

38
This problem occurs when there is more than one optimal
solution. This would be indicated when more than one unoccupied
cell have zero value for the net cost change in the optimal solution.
Thus a reallocation to cell having a net cost change equal to
zero will have no effect on transportation cost. This reallocation will
provide another solution with same transportation cost, but the
route employed will be different from those for the original optimal
solution. This is important because they provide management with
added flexibility in decision making.
/g190Ap r o h i b i t e dr o u t e is assigned a large cost (M) so that it will
never receive an allocation.
2.3.4 LET US SUM UP
In this chapter you have learnt different variants of the
transportation problem.
2.3.5 EXERCISES
Question 1: Solve the following unbalanced transportation problem
by yourself:
Question 2: Solve the following degenerate transportation problem
by yourself:
Question 2 Solution…munotes.in

Page 39

39
Here, S1 = 1000, S2 = 700, S3 = 900 R1 = 900, R2 = 800, R3 =
500, R4 = 400
Since R3 + R4 = S3 so the given problem is a degeneracy problem.
Now we will solve the transportation problem by Matrix Minimum
Method.
To resolve degeneracy, we make use of an artificial quantity (d).
The quantity d is so small that it does not affect the supply and
demand constraints.
Degeneracy can be avoided if we ensure that no partial sum of si
(supply) and rj(requirement) are the same. We set up a new
problem where:
si=si+di=1 ,2 ,. . . . . ,mrj=rjrn=rn+m d
Substituting d = 0.
Initial basic feasible solution:
2*9 0 0+2*1 0 0+6*7 0 0+4*0+1*5 0 0+0*4 0 0=6 7 0 0 .
Now degeneracy has been removed. Use MODI method to
optimize this solution.
Question 3: Solve the following transportation problem by yourself
and find the optimal solution.munotes.in

Page 40

40
2.3.6 SUGGESTED READINGS
Transportation problem section in any of the reference / text books
REFERENCE / TEXT BOOKS
/g153/g153/g153/g153/g153/g3munotes.in

Page 41

41
MODULE - III
TRANSPORTATION TECHNIQUES –II
3.1
VARIATION IN TRANSPORTATION
PROBLEM
Variation in Transportation Problem, Trans Shipment Model, Time
Minimization Problems
Unit Structure :
3.1.1 Introduction
3.1.2 Objectives
3.1.3 Variation in Transportation Problem
3.1.4 Let us sum up
3.1.5 Exercises
3.1.6 Suggested Readings
3.1.1 INTRODUCTION
In this Unit-III - Chapter 3.1, we shall discuss the variations
in transportation problem (TP).
3.1.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand types of variations in the transportation problem.
3.1.3 VARIATIONS IN TRANSPORTATION MODEL OR
TRANSPORTATION PROBLEM (TP)
A very common supply chain involves the shipment of goods
from suppliers at one set of locations to customers at another set of
locations.munotes.in

Page 42

42
The classic transportation model is characterized by a set of
supply sources (each with known capacities), a set of demand
locations (each with known requirements) and the unit costs of
transportation between supply-demand pairs.
The transportation model has two kinds of constraints:
/g120Less-than capacity constraints and
/g120Greater-than demand constraints
If total capacity equals total demand, both capacity and
demand constraints are “=”.
If capacity exceeds demand, the capacity constraints are “<”
and the demand constraints are “>”.
If demand exceeds capacity, the capacity constraints are “>”
and the demand constraints are “<”.
In the transportation model, we have supply and demand
constraints. The solution to the model provides shadow prices on
each. The shadow price on a demand constraint tells us how much
it costs to ship the marginal unit to the corresponding location.
The variations in the transportation problem can be
understood through Sensitivity or Post-Optimality analysis of the
transportation problem.
In this section we discuss the following three aspects of
sensitivity analysis for the transportation problem:
a) Changing the objective function coefficient of a non-basic
variable.
b) Changing the objective function coefficient of a basic variable.
c)/g44/g81/g70/g85/g72/g68/g86/g76/g81/g74/g3/g68/g3/g86/g76/g81/g74/g79/g72/g3/g86/g88/g83/g83/g79/g92/g3/g69/g92/g3/g507/g3/g68/g81/g71/g3/g68/g3/g86/g76/g81/g74/g79/g72/g3/g71/g72/g80/g68/g81/g71/g3/g69/g92/g3/g507/g17
Let us consider the Powerco Example problem with the
following initial transportation cost matrix:
munotes.in

Page 43

43
Decision Variable
Since we have to determine how much electricity is sent
from each plant to each city;
Xij=A m o u n to fe l e c t r i c i t yp r o d u c e da tp l a n tia n ds e n tt oc i t yj
X14=A m o u n to fe l e c t r i c i t yp r o d u c e da tp l a n t1a n ds e n tt o
city 4.
Objective Function
Since we want to minimize the total cost of shipping from
plants to cities;
Minimize Z = 8X 11+6X 12+10X 13+9X 14+9X 21+12X 22+13X 23+7X 24
+14X 31+9X 32+16X 33+5X 34
Supply Constraints
Since each supply point has a limited production capacity;
X11+X12+X13+X14<= 35
X21+X22+X23+X24<= 50
X31+X32+X33+X34<= 40
Demand Constraints
Since each supply point has a limited production capacity;
X11+X21+X31>= 45
X12+X22+X32>= 20
X13+X23+X33>= 30
X14+X24+X34>= 30
Sign Constraints
Since a negative amount of electricity can not be shipped all
Xij’s must be non negative; Xij>= 0 (i= 1,2,3; j= 1,2,3,4)
LP Formulation of Powerco’s Problem
Min Z = 8X 11+6X 12+10X 13+9X 14+9X 21+12X 22+13X 23+7X 24
+14X 31+9X 32+16X 33+5X 34
S.T.: X 11+X12+X13+X14<= 35 (Supply Constraints)
X21+X22+X23+X24<= 50
X31+X32+X33+X34<= 40
X11+X21+X31>= 45 (Demand Constraints)
X12+X22+X32>= 20
X13+X23+X33>= 30
X14+X24+X34>= 30
Xij>= 0 (i= 1,2,3; j= 1,2,3,4)
How to Pivot a Transportation Problem
Based on the transportation tableau, the following steps
should be performed.munotes.in

Page 44

44
Step 1. Determine (by a criterion to be developed shortly, for
example northwest corner method) the variable that should enter
the basis.
Step 2. Find the loop (it can be shown that there is only one loop)
involving the entering variable and some of the basic variables.
Step 3. Counting the cells in the loop, label them as even cells or
odd cells.
Step 4. Find the odd cells whose variable assumes the smallest
value. Call this /g89/g68/g79/g88/g72/g3/g537/g17/g3/g55/g75/g72/g3/g89/g68/g85/g76/g68/g69/g79/g72/g3/g70/g82/g85/g85/g72/g86/g83/g82/g81/g71/g76/g81/g74/g3/g87/g82/g3/g87/g75/g76/g86/g3/g82/g71/g71/g3/g70/g72/g79/g79/g3
will leave the basis. To perform the pivot, decrease the value of
/g72/g68/g70/g75/g3/g82/g71/g71/g3/g70/g72/g79/g79/g3/g69/g92/g3/g537/g3/g68/g81/g71/g3/g76/g81/g70/g85/g72/g68/g86/g72/g3/g87/g75/g72/g3/g89/g68/g79/g88/g72/g3/g82/g73/g3/g72/g68/g70/g75/g3/g72/g89/g72/g81/g3/g70/g72/g79/g79/g3/g69/g92/g3/g537/g17/g3
The variables that are not in the loop remain unchanged. The pivot
is n/g82/g90/g3/g70/g82/g80/g83/g79/g72/g87/g72/g17/g3/g44/g73/g3/g537/g32/g19/g15/g3/g87/g75/g72/g3/g72/g81/g87/g72/g85/g76/g81/g74/g3/g89/g68/g85/g76/g68/g69/g79/g72/g3/g90/g76/g79/g79/g3/g72/g84/g88/g68/g79/g3/g19/g15/g3/g68/g81/g71/g3/g68/g81/g3
odd variable that has a current value of 0 will leave the basis. In this
case a degenerate bfs existed before and will result after the pivot.
/g44/g73/g3/g80/g82/g85/g72/g3/g87/g75/g68/g81/g3/g82/g81/g72/g3/g82/g71/g71/g3/g70/g72/g79/g79/g3/g76/g81/g3/g87/g75/g72/g3/g79/g82/g82/g83/g3/g72/g84/g88/g68/g79/g86/g3/g537/g15/g3/g92 ou may arbitrarily
choose one of these odd cells to leave the basis; again a
degenerate bfs will result
Illustration of pivoting procedure on the Powerco example
We want to find the bfs that would result if X14 were entered
into the basis, the North-West Corner bfs and the loop is shown in
the following table.
New bfs after X 14is pivoted into basis. Since There is no
loop involving the cells (1,1), (1,4), (2,1), (2,2), (3,3) and (3, 4) the
new solution is a bfs.munotes.in

Page 45

45
After the pivot the new bfs is X11=15, X14=20, X21=30,
X22=20, X33=30 and X34=10
In the pivoting procedure:
/g120Since each row has as many +20s as –20s, the new solution will
satisfy each supply and demand constraint.
/g120By choosing the smallest odd variable (X 23) to leave the basis,
we ensured that all variables will remain nonnegative.
Using the MODI method, the optimal solution for Powerco is
X11=10, X13=25, X21=45, X23=5, X32=10 and X34=30.
As a result of this solution the objective function value becomes:
Z=6(10)+10(25)+9(45)+13(5)+9(10)+5(30)=$1020
a) Changing the objective function coefficient of a non-basic
variable.
Let’s try to answer the following question about Powerco as
an example:
For what range of values of the cost of shipping 1 million
kwh of electricity from plant 1 to city 1 will the current basis remain
optimal?
We will need to use the MODI method and the final optimal
solution having uiandvjvalues.
Suppose we change c11/g73/g85/g82/g80/g3/g27/g3/g87/g82/g3/g27/g14/g3/g507/g17
Now /g25411=u 1+v1-c11=0+6-(8+ /g507/g12/g32/g3-2 -/g3/g507/g17
Thus the current basis remains optimal for –2- /g3/g507/g31/g32/g19/g15/g3/g82/g85/g3/g507/g33/g32 -2, and
c11>=8-2=6.munotes.in

Page 46

46
b) Changing the objective function coefficient of a basic
variable.
For what range of values of the cost of shipping 1 million kwh of
electricity from plant 1 to city 3 will the current basis remain
optimal?
Suppose we change c13/g73/g85/g82/g80/g3/g20/g19/g3/g87/g82/g3/g20/g19/g14/g3/g507/g17
Now /g25413=0changes from u1+v3=10tou1+v3=10+ /g507/g17
Thus, to find the ui’s and vj’s we must solve the following equations:
u1=0 u 1+v2=6 u 2+v1=9 u 2+v3=13
u3+v2=9 u 1+v3=10+ /g507u3+v4=5
Solving these equations, we obtain u1=0, v 2=6, v 3=10+ /g507/g15/g3v1=6+ /g507,
u2=3-/g507/g15u3=3,andv4=2.
We now price out each non-basic variable. The current basis
will remain optimal as long as each non-basic variable has a non-
positive coefficient in row 0.
/g25411=u 1+v1-8=/g507-2<=0 /g73/g82/g85/g3/g507/g31/g32/g21
/g25414=u 1+v4-9=-7
/g25422=u 2+v2-12=-3- /g507/g31/g32/g19 /g73/g82/g85/g3/g507/g33/g32 -3
/g25424=u 2+v4-7=-2- /g507/g31/g32/g19 /g73/g82/g85/g3/g507/g33/g32 -2
/g25431=u 3+v1-14=-5+ /g507/g31/g32/g19 /g73/g82/g85/g3/g507/g31/g32/g24
/g25433=u 3+v3-16= /g507-3<=0 /g73/g82/g85/g3/g507/g31/g32/g22
Thus, the current basis remains optimal for –/g21/g31/g32/g507/g31/g32/g21 ,o r
8=10-2<=c 13<=10+2=12
c)/g44/g81/g70/g85/g72/g68/g86/g76/g81/g74/g3/g68/g3/g86/g76/g81/g74/g79/g72/g3/g86/g88/g83/g83/g79/g92/g3/g69/g92/g3/g507/g3/g68/g81/g71/g3/g68/g3/g86/g76/g81/g74/g79/g72/g3/g71/g72/g80/g68/g81/g71/g3/g69/g92/g3/g507/g17
Changing both supply and demand by the same amount will
maintain the balance of the transportation problem. Since ui’s and
vj’s may be thought of as the negative of each constraint’s shadow
price, we know that if the current basis remains optimal,
/g49/g72/g90/g3/g61/g3/g89/g68/g79/g88/g72/g3/g32/g3/g82/g79/g71/g3/g61/g3/g89/g68/g79/g88/g72/g14/g507 ui+/g507vj
For example if we increase plant 1,s supply and city 2’s
demand by 1 unit, then
New cost=1020+1(0)+1(6)=$1026
We can also find the new values of the decision variables as
follows:
/g120/g44/g73/g3/g59/g76/g77/g3/g76/g86/g3/g68/g3/g69/g68/g86/g76/g70/g3/g89/g68/g85/g76/g68/g69/g79/g72/g3/g76/g81/g3/g87/g75/g72/g3/g82/g83/g87/g76/g80/g68/g79/g3/g86/g82/g79/g88/g87/g76/g82/g81/g15/g3/g76/g81/g70/g85/g72/g68/g86/g72/g3/g59/g76/g77/g3/g69/g92/g3/g507/g17
/g120If Xij is a nonbasic variable in the optimal solution, find the loop
involving Xij and some of the basic variables. Find an odd cell in
/g87/g75/g72/g3/g79/g82/g82/g83/g3/g87/g75/g68/g87/g3/g76/g86/g3/g76/g81/g3/g85/g82/g90/g3/g44/g17/g3/g44/g81/g70/g85/g72/g68/g86/g72/g3/g87/g75/g72/g3/g89/g68/g79/g88/g72/g3/g82/g73/g3/g87/g75/g76/g86/g3/g82/g71/g71/g3/g70/g72/g79/g79/g3/g69/g92/g3/g507/g3munotes.in

Page 47

47
and go around the loop, alternately increasing and then
/g71/g72/g70/g85/g72/g68/g86/g76/g81/g74/g3/g70/g88/g85/g85/g72/g81/g87/g3/g69/g68/g86/g76/g70/g3/g89/g68/g85/g76/g68/g69/g79/g72/g86/g3/g76/g81/g3/g87/g75/g72/g3/g79/g82/g82/g83/g3/g69/g92/g3/g507/g17
3.1.4 LET US SUM UP
In this unit we have seen different variations and have
defined the changes in the transportation matrix using the
sensitivity analysis.
3.1.5.EXERCISES
Question 1: Please work out any two examples from the
Transportation problem sensitivity analysis section in any of the
reference / text books.
Question 2: Building Brick Company (BBC) has orders for 80 tons
of bricks at three suburban locations as follows: Northwood -- 25
tons, Westwood -- 45 tons, and Eastwood -- 10 tons. BBC has two
plants, each of which can produce 50 tons per week. How should
end of week shipments be made to fill the above orders given the
following delivery cost per ton:
Northwood Westwood Eastwood
Plant 1 24 30 40
Plant 2 30 40 42
Answer: FromTo Amount Cost
Plant 1 Northwood 5 120
Plant 1 Westwood 45 1,350
Plant 2 Northwood 20 600
Plant 2 Eastwood 10 420
Total Cost = $2,490
Question 3: Ac o m p a n yh a st w op l a n t sp r o d u c i n gac e r t a i np r o d u c t
that is to be shipped to three distribution centers. The unit
production costs are the same at the two plants, and the shipping
cost per unit is shown below:
munotes.in

Page 48

48
Shipments are made once per week. During each week,
each plant produces at most 60 units and each distribution center
needs at least 40 units. How many units should be shipped from
each distribution center to each distribution center, so as to
minimize cost?
Find the optimal solution to this transportation problem.
3.1.6 SUGGESTED READINGS
Transportation problem sensitivity analysis section in any of
the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 49

49
3.2
TRANS SHIPMENT MODEL
Trans Shipment Model
Unit Structure :
3.2.1 Introduction
3.2.2 Objectives
3.2.3 Trans-Shipment Model
3.2.4 Let us sum up
3.2.5 Exercises
3.2.6 Suggested Readings
3.2.1 – INTRODUCTION
In this Unit-III-Chapter3.2, we shall discuss the Trans-
Shipment Model. Transshipment or Transshipment is the
shipment of goods or containers to an intermediate destination, and
then from there to yet another destination. One possible reason is
to change the means of transport during the journey (for example
from ship transport to road transport), known as trans loading.
Another reason is to combine small shipments in to a large
shipment (consolidation), dividing the large shipment at the other
end (deconsolidation). Transshipment usually takes place in
transport hubs. Much international transshipment also takes place
in designated customs areas, thus avoiding the need for customs
checks or duties, otherwise a major hindrance for efficient
transport.
3.2.2 – OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand trans-shipment model and the method of solving
tran-shipment problem.munotes.in

Page 50

50
3.2.3 – TRANS-SHIPMENT MODEL
In a transportation problem, shipments are allowed only
between source-sink pairs. In many applications, this assumption is
too strong. For example, it is often the case that shipments may be
allowed between sources and between sinks.
More over, there may also exist points through which units of a
product can be transshipped from a source to a sink. Model swith
these additional features are called transshipment problems.
Interestingly, it turn south at any given transshipment problem can
be converted easily into an equivalent transportation problem. The
availability of such a conversion procedure significantly broadens
the applicability of our algorithm for solving transportation problems.
munotes.in

Page 51

51
We will illustrate the conversion procedure with an example.
A company manufactures a production two cities, which are Dallas
and Houston. The daily production capacities at Dallas and
Houston are 160 and 200, respectively. Products are shipped by air
to customers in San Francisco and New York. The customers in
each city require 140 units of the product per day. Because of the
deregulation of air fares, the company believes that it may be
cheaper to first fly some products to Chicago or Los Angeles and
then fly the products to their final destinations. The costs of flying
one unit of the product between these cities are shown in the table
below:
The company wants to minimize the total cost of daily
shipments of the required products to its customers. We shall first
define our terminology more carefully. We will define a source as a
city that can send products to another city but cannot receive any
product from any other city. Similarly, a sink is defined as a city that
can receive products from other cities but cannot send products to
any other city. Finally, a transshipment point is defined as a city thatmunotes.in

Page 52

52
can both receive products from other cities and send products to
other cities.
According to these definitions, Dallas and Houston are
sources, with (daily) supplies of 160 and 200 units respectively.
Chicago and Los Angeles are transshipment points. San Francisco
and New York are sinks, each with a (daily) demand of 140 units.
Observe that the total supply equals 360 and the total
demand equals 280. Therefore, we should create a dummy sink,
with a demand of 80, to balance the two. With this revision, we
have a problem with 2 sources, 3 sinks, and 2 transshipment
points.
Since each transshipment point can both receive and send
out products, it plays the dual roles of being as in kanda source.
This naturally suggests that we could attempt are formulation in
which each transshipment point is“ split” into a corresponding sink
and a corresponding source. A little bit of reflection, however, leads
us to the realization that while the demand and the supply at such a
pair of sink and source should be set at the same level (since there
is no gain or loss in units), it is not clear what that level should be.
This is a consequence of the fact that we do not know a priori how
many units will be sent in to and hence shipped out of a
transshipment point. Fortunately, upon further reflection, it turns out
that this difficulty can actually be circumvented by assigning a
“sufficiently-high” value as the demand and the supply for such a
sink-source pair and by allowing fictitious shipments from a given
transshipment point back to itself at zero cost.
More specifically, suppose the common value of the demand
and the supply at the corresponding sink and source of a given
transshipment point is set to c; and suppose x units of “real”
shipments are sent into and shipped out of that transshipment
point. Then, under the assumption that c is no less than x, we can
interpret this as saying:(i) a total of c units of the product are being
sent into the corresponding sink, of which x units are sent from
other points (or cities) and c /g237x units are sent (fictitiously) from the
transshipment point to itself; and (ii) a total of c units of the product
are being shipped out of the corresponding source, of which x units
are shipped to other points (or cities) and c /g237xu n i t sa r es h i p p e d
(fictitiously) back to the transshipment point itself. Notice that since
as h i p m e n tf r o mat r a n s s h i p m e n tp o i n tb a c kt oi t s e l fi sa s s u m e dt o
incur no cost, the proposed reformulation preserves the original
objective function. The only remaining question now is: What
specific value should be assigned to c? The default answer to this
question is to let c equal to the total supply in the original problem.
Such a choice is clearly sufficient because no shipment can exceedmunotes.in

Page 53

53
the total available supply. It follows that we have indeed resolved
the difficulty alluded to earlier.
In our problem, there are two transshipment points.
Therefore, we should replace these by two new sources and two
new sinks (all of which will retain their original city names).
Furthermore, the new sources and sinks should have a common
supply or demand of 360. Our reformulation, therefore, yields an
equivalent transportation problem with 4 sources and 5 sinks. This
equivalent transportation problem is given in the tableau below:
Since the solution method for transportation problems has
been explained in detail, we will not attempt to solve this problem.
Any method to find the initial basic feasible solution and to test the
optimality can be used on the trans-shipment cost matrix given
above.
An interesting variation of the above example is to allow
shipments between Dallas and Houston, say, at a cost of $ 5per
unit either way. This would make Dallas and Houston
transshipment points. It follows that we should introduce into the
above table au two new sinks to represent Dallas and Houston,
respectively.
Both of these two new sinks should have a demand of 360.
Correspondingly, it will also be necessary to increase the supply
from Dallas by 360, to 520, and the supply from Houston by 360, to
560. These revisions result in the formulation below:munotes.in

Page 54

54
Notice that we have introduced 4 “big” M’s as the
transportation costs in four cells. These are intended to in sure that
shipments in to Dallas and Houston from other cities do not appear
in the optimal solution. It should be clear that other variations can
also be handled similarly.
3.2.4 LET US SUMUP
In this unit we have learnt the concept of the trans-shipment
problem and the method of constructing the trans-shipment cost
matrix which can be used to optimize using any of the algorithms to
find the optimal solution for a balanced transportation problem.
3.2.5. EXERCISES
Question1: Solve the following trans-shipment problem using the
optimization techniques of transportation problem.
Wid get co manufactures wid gets at two factories, one in M emphis
and one in Denver. The Memphis factory can produce as 150 wid
gets, and the Denver factory can produce as many as 200 wid gets
per day. Wid gets are shipped by air to customers in LA and
Boston. The customers in each city require 130 wid gets per day.
Because of the deregulation of air fares, Wid get co believes thatit
may be cheaper first fly some wid gets to NY or Chicago and then
fly them to their final destinations. The cost of flying a wid get are
shown next. Wid get co wants to minimize the total cost of shipping
the required widgets to customers.
Question 2:
Consider a firm having two factories to ship its products from the
factories to three-retail stores. The number of units available at
factories X and Y are 200 and 300 respectively, while thosemunotes.in

Page 55

55
demanded at retail stores A, Band C are 100,150 and 250
respectively. Instead of shipping directly from factories to retail
stores, it is asked to investigate the possibility of transshipment.
The transportation cost (in rupees) per unit is given in the table
below:
Factory Retail Stores
XYAB C
X 08 78 9 Factory
Y 60 54 3
A 72 05 1
B 15 10 4Retail
Stores
C 89 78 0
Find the optimal shipping schedule.
Answer: X ->A, X->B 100 units each, Y->B, Y->C 50, 250 units
respectively.
Total cost = 2450
3.2.6 SUGGESTED READINGS
Trans-shipment problem in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 56

56
3.3
TIME MINIMIZATION PROBLEMS
Time Minimization Problems
Unit Structure
3.3.1 Introduction
3.3.2 Objectives
3.3.3 Trans-Shipment Model
3.3.4 Let us sum up
3.3.5 Exercises
3.3.6 Suggested Readings
3.3.1 INTRODUCTION
In the Time Minimizing Transportation Problem the objective
is to minimize the time. This problem is same as the transportation
problem of minimizing the cost, expect that the unit transportation
cost is replaced by the time tij
3.3.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Understand time minimization problem
/g120Technique of solving a time minimization problem
3.3.3 TIME MINIMIZATION PROBLEMS
Example
/g120Determine an initial basic feasible solution using any one of the
following:
1. North West Corner Rule
2. Matrix Minimum Method
3. Vogel Approximation Method
/g120Find Tk for this feasible plan and cross out all the unoccupied
cells for which tij/g149Tk.munotes.in

Page 57

57
/g120Trace a closed path for the occupied cells corresponding to Tk.
If no such closed path can be formed, the solution obtained is
optimum otherwise, go to step 2.
The following matrix gives data concerning the transportation
times tij.
We compute an initial basic feasible solution by north west corner
rule which is shown below:
Here, t 11=2 5 ,t 12=3 0 ,t 13=2 0 ,t 23=2 0 ,t 24=3 0 ,t 34=3 5 ,t 35=4 5 ,
t45=30, t 46=2 5
Choose maximum from tij, i.e., T1 = 45. Now, cross out all the
unoccupied cells that are /g149T1. The unoccupied cell (O3D6) enters
into the basis as shown below:munotes.in

Page 58

58
Choose the smallest value with a negative position on the closed
path, i.e., 10. Clearly only 10 units can be shifted to the entering
cell. The next feasible plan is shown in the following table.
Here, T2 = Max(25, 30, 20, 20, 20, 35, 45, 22, 30) = 45. Now, cross
out all the unoccupied cells that are /g149T2.munotes.in

Page 59

59
By following the same procedure as explained above, we get the
following revised matrix.
T3 = Max(25, 30, 20, 20, 30, 40, 35, 22, 30) = 40. Now, cross out
all the unoccupied cells that are /g149T3.
Now we cannot form any other closed loop with T3.
Hence, the solution obtained at this stage is optimal.
Thus, all the shipments can be made within 40 units.
3.3.4 LET US SUM UP
In this unit we have learnt the concept of time minimization
problem which is similar to the transportation problem and we have
shown the method of solving the time minimization problem.munotes.in

Page 60

60
3.3.5 EXERCISES
Question 1: Consider the following transportation problem with m =
4s o u r c e sA i ,i ЩI={1,2,3,4}, and n = 5 destinations Bj,
jЩJ={1,2,3,4,5}. The initial data are presented in the table below.
Each row corresponds to a supply point and each column to a
demand point. The total supply 65 is equal to the total demand. In
each cell (i,j), top left corner represents the time tij required for
transporting xij units from source Ai to destination Bj. Optimize this
time minimization problem.
Question 2:
A concrete company transports concrete from three plants,
1, 2 and 3, to three constructionsites, A, B and C.
The plants are able to supply the following numbers of tons
per week:
munotes.in

Page 61

61
The requirements of the sites, in number of tons per week, are:
The cost of transporting 1 ton of concrete from each plant to each
site is shown in the figure below:
For computational purposes it is convenient to put all the above
information into a table, as in the simplex method. In this table each
row represents a source and each column represents destination .
Optimize this transportation problem.
3.3.6 SUGGESTED READINGS
Time management problem in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 62

62
MODULE - IV
NETWORK ANALYSIS
4.1
CONCEPT OF PROJECT PLANNING
Concept of Project Planning, Scheduling and Controlling, Work
Break Down Structure, Basic Tools and Techniques of Project
Management, Role of Network Technique in Project Management,
Unit Structure
4.1.1 Introduction
4.1.2 Objectives
4.1.3 Project Planning, Scheduling and Controlling
4.1.4 Work Break Down Structure
4.1.5 Basic Tools and Techniques of Project Management and Role
of Network Technique in Project Management
4.1.6 Let us sum up
4.1.7 Exercises
4.1.8 Suggested Readings
4.1.1 INTRODUCTION
In this Unit-IV - Chapter 4.1, we shall discuss the concept of
project planning, scheduling and controlling, Work Break Down
Structure, Basic Tools and Techniques of Project Management,
Role of Network Technique in Project Management.
4.1.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Project Planning, Scheduling and Controlling
/g120Work Break Down Structure
/g120Basic Tools and Techniques of Project Management
/g120Role of Network Technique in Project Management.munotes.in

Page 63

63
4.1.3 PROJECT PLANNING, SCHEDULING AND
CONTROLLING
What is a project?
Ap r o j e c ti sao n e - s h o t ,t i m e - l i m i t e d ,g o a l - d i r e c t e d ,m a j o r
undertaking, requiring the commitment of varied skills and
resources.
A project is a series of inter-related and sequenced activities,
managed by a single individual, designed and organized to
accomplish a specific goal, within a limited timeframe, frequently
with specific budgetary requirements.
Projects are critical to the realization of the performing
organization’s business strategy because projects are a means by
which strategy is implemented.
A project is a temporary endeavor undertaken to create a
unique product or service. A project is temporary in that there is a
defined start (the decision to proceed) and a defined end (the
achievement of the goals and objectives). Ongoing business or
maintenance operations are not projects. Energy conservation
projects and process improvement efforts that result in better
business processes or more efficient operations can be defined as
projects. Projects usually include constraints and risks regarding
cost, schedule or performance outcome.
Examples of projects
/g120Developing a new product or service
/g120Effecting a change in structure, staffing, or style of an
organization
/g120Designing a new transportation vehicle
/g120Developing or acquiring a new or modified information system
/g120Constructing or renovating a building or facility
/g120Building a water system for a community in a developing
country
/g120Running a campaign for political office
/g120Implementing a new or improved business process or procedure
Within a project there can be sub-projects
/g120Based on project process such as a single phase (e.g. design)
/g120According to human resource skill requirements (e.g. plumbing)
/g120By major deliverable (e.g. training)munotes.in

Page 64

64
What is a project management?
Project management is concerned with the overall planning
and co-ordination of a project from conception to completion aimed
at meeting the stated requirements and ensuring completion on
time, within cost and to required quality standards.
Project management is normally reserved for focused, non-
repetitive, time-limited activities with some degree of risk and that
are beyond the usual scope of operational activities for which the
organization is responsible.
The various elements of project management life cycle are
a) Need identification
b) Initiation
c) Planning
d) Executing
e) Controlling.
a) Need Identification
The first step in the project development cycle is to identify
components of the project. Projects may be identified both
internally and externally:
Internal identification takes place when the energy manager
identifies a package of energy saving opportunities during the day-
to-day energy management activities, or from facility audits.
External identification of energy savings can occur through
systematic energy audits undertaken by a reputable energy auditor
or energy service company.
b) Initiation
Initiating is the basic processes that should be performed to
get the project started. This starting point is critical because those
who will deliver the project, those who will use the project, and
those who will have a stake in the project need to reach an
agreement on its initiation. Involving all stakeholders in the projectmunotes.in

Page 65

65
phases generally improves the probability of satisfying customer
requirements by shared ownership of the project by the
stakeholders.
c) Planning
The planning phase is considered the most important phase
in project management. Project planning defines project activities
that will be performed; the products that will be produced, and
describes how these activities will be accomplished and managed.
Project planning defines each major task, estimates the time,
resources and cost required, and provides a framework for
management review and control. Planning involves identifying and
documenting scope, tasks, schedules, cost, risk, quality, and
staffing needs.
d) Executing
Once a project moves into the execution phase, the project
team and all necessary resources to carry out the project should be
in place and ready to perform project activities. The project plan is
completed and base lined by this time as well. The project team
and the project manager’s focus now shifts from planning the
project efforts to participating, observing, and analyzing the work
being done. In short, it means coordinating and managing the project
resources while executing the project plan, performing the planned
project activities, and ensuring they are completed efficiently.
e) Controlling
Project Control function that involves comparing actual
performance with planned performance and taking corrective action
to get the desired outcome when there are significant differences.
By monitoring and measuring progress regularly, identifying
variances from plan, and taking corrective action if required, project
control ensures that project objectives are met.
f) Closing out
Project closeout is performed after all defined project
objectives have been met and the customer has formally accepted
the project’s deliverables and end product or, in some instances,
when a project has been cancelled or terminated early. Although,
project closeout is a routine process, it is an important one. By
properly completing the project closeout, organizations can benefit
from lessons learned and information compiled. The project
closeout phase is comprised of contract closeout and administrative
closure.munotes.in

Page 66

66
4.1.4 WORK BREAK DOWN STRUCTURE (WBS)
WBS contains a list of activities for a project derived from:
/g120Previous experience
/g120Expert brainstorming.
WBS helps in
/g120identifying the main activities
/g120break each main activity down into sub-activities which can
further be broken down into lower level sub-activities.
WBS problems at times are:
/g120Too many levels
/g120Too few levels.
Approaches to creating WBS are:
/g120Phase based approach
/g120Product based approach
/g120Hybrid approach.
WBS Phase-based Approach (PA)
munotes.in

Page 67

67
WBS PA Advantage
/g120Activity list likely complete and non-overlapping
/g120WBS gives a structure that can berefined as the project
proceeds
/g120used for determining dependencies among activities
WBS PA Disadvantage
/g120May miss some activities related to final product
WBS - Product based approach (PBA)
Product Breakdown Structure (PBS) shows how a system can be
broken down into different products for development.
WBS – Hybrid Approach (HA)
A mix of the phase-based and product based approaches (most
commonly used). The WBS consists of a list of the products of the
project and a list of phases for each product.
munotes.in

Page 68

68
4.1.5 BASIC TOOLS AND TECHNIQUES OF PROJECT
MANAGEMENT
Role of Network Technique in Project Management
Project management is a challenging task with many
complex responsibilities. Fortunately, there are many tools
available to assist with accomplishing the tasks and executing the
responsibilities. Some require a computer with supporting software,
while others can be used manually. Project managers should
choose a project management tool that best suits their
management style. No one tool addresses all project management
needs.
Program Evaluation Review Technique (PERT) and Gantt
Charts are two of the most commonly used project management
tools and are described below. Both of these project management
tools can be produced manually or with commercially available
project management software.
PERT is a planning and control tool used for defining and
controlling the tasks necessary to complete a project. PERT charts
and Critical Path Method (CPM) charts are often used
interchangeably; the only difference is how task times are
computed. Both charts display the total project with all scheduled
tasks shown in sequence. The displayed tasks show which ones
are in parallel, those tasks that can be performed at the same time.
Ag r a p h i cr e p r e s e n t a t i o nc a l l e da" P r o j e c tN e t w o r k "o r" C P M
Diagram" is used to portray graphically the interrelationships of the
elements of a project and to show the order in which the activities
must be performed.
PERT planning involves the following steps:
a.Identify the specific activities and milestones. The activities are
the tasks of the project. The milestones are the events that mark
the beginning and the end of one or more activities.
b.Determine the proper sequence of activities. This step may be
combined with #1 above since the activity sequence is evident
for some tasks. Other tasks may require some analysis to
determine the exact order in which they should be performed.
c.Construct a network diagram. Using the activity sequence
information, a network diagram can be drawn showing the
sequence of the successive and parallel activities. Arrowed lines
represent the activities and circles or "bubbles" represent
milestones.
d.Estimate the time required for each activity. Weeks are a
commonly used unit of time for activity completion, but anymunotes.in

Page 69

69
consistent unit of time can be used. A distinguishing feature of
PERT is it's ability to deal with uncertainty in activity completion
times. For each activity, the model usually includes three time
estimates:
/g120Optimistic time - the shortest time in which the activity can
be completed.
/g120Most likely time - the completion time having the highest
probability.
/g120Pessimistic time - the longest time that an activity may take.
From this, the expected time for each activity can be calculated
using the following weighted average:
Expected Time = (Optimistic + 4 x Most Likely + Pessimistic) / 6
This helps to bias time estimates away from the unrealistically
short timescales normally assumed.
e.Determine the critical path. The critical path is determined by
adding the times for the activities in each sequence and
determining the longest path in the project. The critical path
determines the total calendar time required for the project. The
amount of time that a non-critical path activity can be delayed
without delaying the project is referred to as slack time.
If the critical path is not immediately obvious, it may be helpful
to determine the following four times for each activity:
/g120ES - Earliest Start time
/g120EF - Earliest Finish time
/g120LS - Latest Start time
/g120LF - Latest Finish time
These times are calculated using the expected time for the
relevant activities. The earliest start and finish times of each
activity are determined by working forward through the network
and determining the earliest time at which an activity can start
and finish considering its predecessor activities. The latest start
and finish times are the latest times that an activity can start and
finish without delaying the project. LS and LF are found by
working backward through the network. The difference in the
latest and earliest finish of each activity is that activity's slack.
The critical path then is the path through the network in which
none of the activities have slack.
The variance in the project completion time can be calculated by
summing the variances in the completion times of the activities
in the critical path. Given this variance, one can calculate the
probability that the project will be completed by a certain date
assuming a normal probability distribution for the critical path.
The normal distribution assumption holds if the number ofmunotes.in

Page 70

70
activities in the path is large enough for the central limit theorem
to be applied.
f.Update the PERT chart as the project progresses. As the
project unfolds, the estimated times can be replaced with actual
times. In cases where there are delays, additional resources
may be needed to stay on schedule and the PERT chart may be
modified to reflect the new situation. An example of a PERT
chart is provided below:
g.
Benefits to using a PERT chart or the Critical Path Method include:
/g120Improved planning and scheduling of activities.
/g120Improved forecasting of resource requirements.
/g120Identification of repetitive planning patterns which can be
followed in other projects, thus simplifying the planning process.
/g120Ability to see and thus reschedule activities to reflect interproject
dependencies and resource limitations following know priority
rules.
/g120It also provides the following: expected project completion time,
probability of completion before a specified date, the critical path
activities that impact completion time, the activities that have
slack time and that can lend resources to critical path activities,
and activity start and end dates.
Gantt chart
Gantt charts are used to show calendar time task
assignments in days, weeks or months. The tool uses graphic
representations to show start, elapsed, and completion times of
each task within a project. Gantt charts are ideal for tracking
progress. The number of days actually required to complete a task
that reaches a milestone can be compared with the planned or
estimated number. The actual workdays, from actual start to actual
finish, are plotted below the scheduled days. This information helps
target potential timeline slippage or failure points. These charts
serve as a valuable budgeting tool and can show dollars allocated
versus dollars spent.munotes.in

Page 71

71
To draw up a Gantt chart, follow these steps:
a.List all activities in the plan. For each task, show the earliest
start date, estimated length of time it will take, and whether it is
parallel or sequential. If tasks are sequential, show which stages
they depend on.
b.Head up graph paper with the days or weeks through
completion.
c.Plot tasks onto graph paper. Show each task starting on the
earliest possible date. Draw it as a bar, with the length of the bar
being the length of the task. Above the task bars, mark the time
taken to complete them.
d.Schedule activities. Schedule them in such a way that
sequential actions are carried out in the required sequence.
Ensure that dependent activities do not start until the activities
they depend on have been completed. Where possible,
schedule parallel tasks so that they do not interfere with
sequential actions on the critical path. While scheduling, ensure
that you make best use of the resources you have available,
and do not over-commit resources. Also, allow some slack time
in the schedule for holdups, overruns, failures, etc.
e.Presenting the analysis. In the final version of your Gantt chart,
combine your draft analysis (#3 above) with your scheduling
and analysis of resources (#4 above). This chart will show when
you anticipate that jobs should start and finish. An example of a
Gantt chart is provided below:
munotes.in

Page 72

72
Benefits of using a Gantt chart include:
/g120Gives an easy to understand visual display of the scheduled
time of a task or activity.
/g120Makes it easy to develop "what if" scenarios.
/g120Enables better project control by promoting clearer
communication.
/g120Becomes a tool for negotiations.
/g120Shows the actual progress against the planned schedule.
/g120Can report results at appropriate levels.
/g120Allows comparison of multiple projects to determine risk or
resource allocation.
/g120Rewards the project manager with more visibility and control
over the project.
At the end of this unit the learners will be able to
/g120Project Planning, Scheduling and Controlling
/g120Work Break Down Structure
/g120Basic Tools and Techniques of Project Management
/g120Role of Network Technique in Project Management.munotes.in

Page 73

73
4.1.6 LET US SUM UP
In this unit you have learnt Project Planning, Scheduling and
Controlling, Work Break down Structure, Basic Tools and
Techniques of Project Management and Role of Network
Technique in Project Management.
4.1.7 EXERCISES
Question 1. Discuss with your own examples project planning and
scheduling techniques.
Question 2. An example of the work break-down structure (WBS)
diagram is shown.
WBS Example – Banquet
In a WBS, every level item has a unique assigned number
so that work can be identified and tracked over time. A WBS may
have varying numbers of decomposition levels, but there is a
general scheme for how to number each level so that tasks are
uniquely numbered and correctly summarized. Below is the
general convention for how tasks are decomposed:
/g120Level 1 – Designated by 1.0. This level is the top level of the
WBS and is usually the project name. All other levels are
subordinate to this level.
/g120Level 2 – Designated by 1.X (e.g., 1.1, 1.2). This level is the
summary level.munotes.in

Page 74

74
/g120Level 3 – Designated by 1.X.X (e.g., 1.1.1, 1.1.2). This third
level comprises the subcomponents to each level 2 summary
element. This effort continues down until progressively
subordinate levels are assigned for all work required for the
entire project.
Please name the different hierarchical levels in the above
WBS diagram.
Question 3. Draw the Gantt Chart for the following activities:
Suggested Steps
•List all tasks and milestones from the project along the vertical
axis
•List time frame along the horizontal axis
•Activities: Create box the length of each activity time duration
–E.g., activity one is scheduled from day1-day3
munotes.in

Page 75

75
•Dependencies: Show dependencies between activities with
arrows
–E.g., activity 2 cannot start until activity 1 is complete
Answer to the question:
4.1.8 SUGGESTED READINGS
Network Analysis section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 76

76
4.2
CONCEPT OF NETWORK
Concept of Network or Arrow Diagram, Activity on Node Diagram,
Critical Path Method
Unit Structure
4.2.1 Introduction
4.22 Objectives
4.2.3 Concept of Network or Arrow Diagram, Activity on Node
Diagram, Critical Path Method
4.2.4 Let us sum up
4.2.5 Exercises
4.2.6 Suggested Readings
4.2.1 INTRODUCTION
In this Unit-IV - Chapter 4.2, we shall discuss the concept of
Project Network or Arrow Diagram, Activity on Node Diagram,
Critical Path Method.
The project network arrow diagram shows the required order
of tasks in a project or process, the best schedule for the entire
project, and potential scheduling and resource problems and their
solutions. The arrow diagram lets you calculate the “critical path” of
the project. This is the flow of critical steps where delays will affect
the timing of the entire project and where addition of resources can
speed up the project.
4.2.2 OBJECTIVES
At the end of this unit the learners will be able to
/g120Draw a project network
/g120Calculate different times estimates for different events on the
network activities
/g120Find the critical pathmunotes.in

Page 77

77
4.2.3 CONCEPT OF NETWORK OR ARROW
DIAGRAM, ACTIVITY ON NODE DIAGRAM,
CRITICAL PATH METHOD
Project schedule converts action plan into operating time
table and forms the basis for monitoring and controlling project.
Scheduling is more important in projects than in production,
because of the unique nature of the projects.
An e t w o r ki s :
/g120Graphical portrayal of activities and event
/g120Shows dependency relationships between tasks/activities in a
project
/g120Clearly shows tasks that must precede (precedence) or follow
(succeeding) other tasks in a logical manner
/g120Clear representation of plan – a powerful tool for planning and
controlling project
Example of a Simple Network – Survey
munotes.in

Page 78

78
Definition of Terms in a Network
/g120Activity: any portions of project (tasks) which required by
project, uses up resource and consumes time – may involve labor,
paper work, contractual negotiations, machinery operations Activity
on Arrow (AOA) showed as arrow, AON – Activity on Node
/g120Event: beginning or ending points of one or more activities,
instantaneous point in time, also called ‘nodes’
/g120Network: Combination of all project activities and the events
Emphasis on Logic in Network Construction
Construction of network should be based on logical or technical
dependencies among activities
Example
Before activity ‘Approve Drawing’ can be started, the activity
‘Prepare Drawing’ must be completed
Build network on the basis of time logic (a feeling for proper
sequence ) see example below:
Activity on Node Diagram
Activity-on-node is a project management term that refers to
a precedence diagramming method which uses boxes to denote
schedule activities. These various boxes or “nodes” are connected
from beginning to end with arrows to depict a logical progression of
the dependencies between the schedule activities. Each node ismunotes.in

Page 79

79
coded with a letter or number that correlates to an activity on the
project schedule.
Typically, an activity-on-node diagram will be designed to
show which activities must be completed in order for other activities
to commence. This is referred to as “finish-to-start” precedence –
meaning one activity must be finished before the next one can start.
In the diagram below, activities A and D must be done so that
activity E can begin. It is also possible to create other variations of
this type of diagram. For example, a “start-to-start” diagram is one
in which a predecessor activity must simply be started rather than
fully completed in order for the successor activity to be initiated.
An activity-on-node diagram can be used to provide a visual
representation of the network logic of an entire project schedule.
Or, it can be used for any smaller section of the schedule that lends
itself to being represented as having a defined beginning and end.
To keep the logic in the diagram simple, it may be most effective to
include only critical path schedule activities. The planned start date
of each node may also be listed in the diagram legend in
accordance with the project management timeline.
But in the network analysis an activity is indicated by an
arrow with circles at the start and at the end of the arrow as follows.
A (tij)
The activity is named by an alphabet that is placed on the
top of the arrow. The beginning of an activity which is the tail of the
arrow is the start event of that activity; the start event is denoted by
a circle with a number inside it. The ending of an activity which is
the head of the arrow is the end event of that activity; the end event
is denoted by a circle with a number inside it. The progress of an
activity is from the tail to the head of the activity arrow.ijmunotes.in

Page 80

80
In the above figure activity i-j is named as A, i is the start
event and j is the end event of that activity, (tij) is the time duration
of the activity A.
Example 1- A simple network
Consider the list of four activities for making a simple product.
Immediate predecessors for a particular activity are the
activities that, when completed, enable the start of the activity in
question.
Can start work on activities A and B anytime, since neither of
these activities depends upon the completion of prior activities.
Activity C cannot be started until activity B has been
completed.
Activity D cannot be started until both activities A and C have
been completed.
The graphical representation (next slide) is referred to as the
PERT/CPM network.
Example 1 - Network of Four Activities
munotes.in

Page 81

81
Example 2
Develop the network for a project with following activities and
immediate predecessors:
Try to do for the first five (A,B,C,D,E) activities
Example 2 – Network of Seven Activities
Note how the network correctly identifies D, E, and F as the
immediate predecessors for activity G.
Dummy activities are used to identify precedence relationships
correctly and to eliminate possible confusion of two or more
activities having the same starting and ending nodes.
Dummy activities have no resources (time, labor, machinery, etc),
their purpose is to preserve the logic of the networkmunotes.in

Page 82

82
Examples of the Use of Dummy Activity
munotes.in

Page 83

83
Scheduling with activity time
This information indicates that the total time required to
complete activities is 51 weeks. However, we can see from the
network that several of the activities can be conducted
simultaneously (A and B, for example).
Earliest Start & Earliest Finish Time
We are interested in the longest path through the network,
i.e., the critical path. Starting at the network’s origin (node 1) and
using a starting time of 0, we compute an earliest start (ES) and
earliest finish (EF) time for each activity in the network.
The expression EF = ES + t can be used to find the earliest
finish time for a given activity.
For example, for activity A, ES = 0 and t = 5; thus the earliest finish
time for activity A is EF = 0 + 5 = 5
Arc with ES & EF time
munotes.in

Page 84

84
Network with ES & EF time
Earliest start time rule
The earliest start time for an activity leaving a particular node is
equal to the largest of the earliest finish times for all activities
entering the node.
Activity, duration, ES, EF, LS, LF
munotes.in

Page 85

85
Latest start & latest finish time
To find the critical path we need a backward pass calculation .
Starting at the completion point (node 7) and using a latest finish
time (LF) of 26 for activity I, we trace back through the network
computing a latest start (LS) and latest finish time for each activity.
The expression LS = LF – t can be used to calculate latest start
time for each activity. For example, for activity I, LF = 26 and t= 2,
thus the latest start time for activity I is LS = 26 – 2 = 24.
Network with LS & LF time
Latest finish time rule
The latest finish time for an activity entering a particular node
is equal to the smallest of the latest start times for all activities
leaving the node.
Slack or Free Time or Float
Slack is the length of time an activity can be delayed without
affecting the completion date for the entire project.
For example, slack for C = 3 weeks, i.e. Activity C can be delayed
up to 3 weeks
(Start, anywhere between weeks 5 and 8).munotes.in

Page 86

86
Activity schedule for the example
Activity Earliest
start
(ES)Latest
start
(LS)Earliest
finish
(EF)Latest
finish
(LF)Slack
(LS-
ES)Critical
path
A0 0 5 5 0 Y e s
B0 6 6 1 2 6
C589 1 2 3
D578 1 0 2
E5 5 6 6 0 Y e s
F6 6 1 0 1 0 0 Y e s
G1 0 1 0 2 4 2 4 0 Y e s
H9 1 2 2 1 2 4 3
I2 4 2 4 2 6 2 6 0 Y e s
Important Questions
1. What is the total time to complete the project?
26 weeks if the individual activities are completed on schedule.
2. What are the scheduled start and completion times for each
activity?
ES, EF, LS, LF are given for each activity.
3. What activities are critical and must be completed as scheduled
in order to keep the project on time?
Critical path activities: A, E, F, G, and I.
4. How long can non-critical activities be delayed before they
cause a delay in the project’s completion time
Slack time that is available for all activities are given.munotes.in

Page 87

87
Critical Path Method
Slack or Float shows how much allowance each activity has,
i.e how long it can be delayed without affecting completion date of
project
Critical path is a sequence of activities from start to finish
with zero slack. Critical activities are activities on the critical path.
Critical path identifies the minimum time to complete project
If any activity on the critical path is shortened or extended, project
time will be shortened or extended accordingly.
So, a lot of effort should be put in trying to control activities
along this path, so that project can meet due date. If any activity is
lengthened, be aware that project will not meet deadline and some
action needs to be taken.
If can spend resources to speed up some activity, do so only
for critical activities.
Don’t waste resources on non-critical activity; it will not
shorten the project time.
If resources can be saved by lengthening some activities, do
so for non-critical activities, up to limit of float.
Total Float belongs to the path.
4.2.4 LET US SUM UP
In this chapter you have learnt how to draw a network and find the
total project duration and the critical path.
4.2.5 EXERCISES
Question 1: Table below shows the activities within a small
project.
munotes.in

Page 88

88
/g120 Draw the network diagram.
/g120 Calculate the minimum overall project completion time.
/g120 Calculate the float time for each activity and hence identify
the activities which are critical.
Ans: The critical activities (those with a float of zero) are 2,5,8,9
and 10 and these form the critical path from the start node (node 1)
to the finish node (node 8) in the network. The overall project
completion time is 22 weeks. Drawing a network is left as an
exercise.
Question 2: Table below shows the activities within a small
project.
/g120Draw the network diagram.
/g120Calculate the minimum overall project completion time.
/g120Calculate the float time for each activity and hence identify the
activities which are critical.
Ans: The critical activities (those with a float of zero) are
2,3,6,7,8,10 and 13 forming the critical path and the total project
duration is 21 weeks. Drawing a network is left as an exercise.
4.2.6 SUGGESTED READINGS
Network Analysis section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 89

89
4.3
CONCEPT OF PERT/CRASHING
Concept of PERT, Concept of CPM, Cost Analysis and Crashing
the Network
Unit Structure
4.3.1 Introduction
4.3.2 Objectives
4.3.3 Concept of PERT
4.3.4 Concept of CPM
4.3.5 Crashing the Network
4.3.6 Let us sum up
4.3.7 Exercises
4.3.8 Suggested Readings
4.3.1 INTRODUCTION
The program (or project) evaluation and review technique,
commonly abbreviated PERT, is a statistical tool, used in project
management, which was designed to analyze and represent the
tasks involved in completing a given project. First developed by the
United States Navy in the 1950s, it is commonly used in
conjunction with the critical path method (CPM).
4.3.2 OBJECTIVES
In this unit you will learn the following:
/g120Concept of PERT
/g120Concept of CPM and
/g120Cost analysis and crashing the network.
4.3.3 CONCEPT OF PERT
The Navy's Special Projects Office, charged with developing
the Polaris-Submarine weapon system and the Fleet Ballistic
Missile capability, has developed a statistical technique for
measuring and forecasting progress in research and development
programs. This program evaluation and review technique (code-
named PERT) is applied as a decision-making tool designed tomunotes.in

Page 90

90
save time in achieving end-objectives, and is of particular interest to
those engaged in research and development programs for which
time is a critical factor.
The new technique takes recognition of three factors that
influence successful achievement of research and development
program objectives: time, resources, and technical performance
specifications. PERT employs time as the variable that reflects
planned resource-applications and performance specifications.
With units of time as a common denominator, PERT quantifies
knowledge about the uncertainties involved in developmental
programs requiring effort at the edge of, or beyond, current
knowledge of the subject — effort for which little or no previous
experience exists.
Through an electronic computer, the PERT technique
processes data representing the major, finite accomplishments
(events) essential to achieve end-objectives; the inter-dependence
of those events; and estimates of time and range of time necessary
to complete each activity between two successive events. Such
time expectations include estimates of "most likely time", "optimistic
time", and "pessimistic time" for each activity. The technique is a
management control tool that sizes up the outlook for meeting
objectives on time; highlights danger signals requiring management
decisions; reveals and defines both methodical ness and slack in
the flow plan or the network of sequential activities that must be
performed to meet objectives; compares current expectations with
scheduled completion dates and computes the probability for
meeting scheduled dates; and simulates the effects of options for
decision — before decision.
The concept of PERT was developed by an operations
research team staffed with representatives from the Operations
Research Department of Booz, Allen and Hamilton; the Evaluation
Office of the Lockheed Missile Systems Division; and the Program
Evaluation Branch, Special Projects Office, of the Department of
the Navy.
PERT is a method of analyzing the tasks involved in
completing a given project, especially the time needed to complete
each task, and to identify the minimum time needed to complete the
total project.
PERT was developed primarily to simplify the planning and
scheduling of large and complex projects. It was developed for the
U.S. Navy Special Projects Office in 1957 to support the U.S.
Navy's Polaris nuclear submarine project. It was able to incorporate
uncertainty by making it possible to schedule a project while not
knowing precisely the details and durations of all the activities. It ismunotes.in

Page 91

91
more of an event-oriented technique rather than start- and
completion-oriented, and is used more in projects where time is the
major factor rather than cost. It is applied to very large-scale, one-
time, complex, non-routine infrastructure and Research and
Development projects. An example of this was for the 1968 Winter
Olympics in Grenoble which applied PERT from 1965 until the
opening of the 1968 Games.
This project model was the first of its kind, a revival for
scientific management, founded by Frederick Taylor (Taylorism)
and later refined by Henry Ford (Fordism). DuPont's critical path
method was invented at roughly the same time as PERT.
4.3.4 CONCEPT OF CPM
The critical path method (CPM) is a step-by-step
methodology, technique or algorithm for planning projects with
numerous activities that involve complex, interdependent
interactions. CPM is an important tool for project management
because it identifies critical and non-critical tasks to prevent
conflicts and bottlenecks. CPM is often applied to the analysis of a
project network logic diagram to produce maximum practical
efficiency.
CPM is commonly employed in many diverse types of projects.
These include product development, engineering, construction,
aerospace and defense, software development and research
projects. Several CPM software solutions are available.
The basic steps employed in CPM are:
1. Determine required tasks
2. List required tasks in sequence
3. Create a flowchart including each required task
4. Identify all critical and non-critical relationships (paths) among
required tasks
5. Assign an expected completion/execution time for each required
task
6. Study all critical relationships to determine all possible
alternatives or backups for as many as possible.
Often a major objective in CPM is to complete the project in
the shortest time possible. One way to do this is called fast
tracking, which involves performing activities in parallel
(simultaneously) and adding resources to shorten critical path
durations (called crashing the critical path). This may result inmunotes.in

Page 92

92
expansion, which leads to increasing project complexity, duration or
both.
4.3.5 COST ANALYSIS AND CRASHING THE
NETWORK
Crashing Example :T h en e t w o r ka n dd u r a t i o n sg i v e nb e l o ws h o w s
the normal schedule for a project. You can decrease (crash) the
durations at an additional expense. The Table given below
summarizes the time-cost information for the activities. The owner
wants you to you to finish the project in 110 days. Find the
minimum possible cost for the project if you want to finish it on 110
days. (Assume that for each activity there is a single linear,
continuous function between the crash duration and normal
duration points).
Assume that the duration-cost relationship for each activity is
as i n g l el i n e a r ,c o n t i n u o u sf u n c t i o nb e t w e e nt h ec r a s hd u r a t i o na n d
normal duration points. Using the normal duration(ND), crash
duration (CD), normal cost (NC), and crash cost (CC), the crash
cost slope for each activity can be determined as follows:munotes.in

Page 93

93
The normal cost for the project is the sum of a normal cost
for each activity. The normal cost for the project is $48300 and the
normal duration is 140 days. The activity which should be crashed
is the one on the critical path which will add the least amount to the
overall project cost. This will be the activity with the flattest or least-
cost slope. The duration can be reduced as long as the critical path
is not changed or a new critical path is created. In addition, the
activity duration cannot be less than the crash duration.
SD = $60/day (least-cost slope) Maximum of 10 days can be cut
from this schedule by reducing the duration of activity D to the
crash duration of 20 days.
Overall duration is 130 days and there are multiple critical
paths (B-F-E and B-C-D-E). Total project cost at this duration is the
normal cost of $48300 plus the cost of crashing the activity by 10
days (60 * 10 = $600) for a total of $48900.
The next activity to be crashed would be the activity E, since
it has the least-cost slope ($120per day) of any of the activities onmunotes.in

Page 94

94
the critical path. Activity E can be crashed by a total of 10days.
Crashing the activity E by 10 days will cost an additional $120 per
day or $1200.
The project duration is now 120 days and the total project
cost is $50100. There are now three critical paths (A, B-C-D-E, and
B-F-E). The next stage of crashing requires a more through
analysis since it is impossible to crash one activity alone and
achieve a reduction in the overall project duration. Activity A is
paired with each of the other activities to determine which has the
least overall cost slope for those activities which have remaining
days to be crashed.
Activity A ($100) + activity B ($200)
Activity A ($100) + activity C ($600) + activity F ($300)
The least-cost slope will be activity A + activity B for a cost
increase of $300 per day. Reducing the project duration by 5 days
will add 5*300 = $1500 dollar crashing cost and the total project
cost would be $51600. Activity B cannot be crashed any more.
Final step in crashing the project to 110 days would be
accomplished by reducing the duration of activity A by 5 days to
110 days, reducing activity C by 5 days to 35 days, and reducing
activity F by 5 days to 55 days. The combined cost slope for themunotes.in

Page 95

95
simultaneous reduction of activity A, activity C, and activity F would
be $1000 per day. For 5 days of reduction this would be an
additional $5000 in total project cost. The total project cost for the
crashed schedule to 110 days of duration would be $56600.
4.3.6 LET US SUM UP
In this unit you have understood the concept of PERT and
CPM and the method of cost analysis and crashing the network has
been explained to you.
4.3.7 EXERCISES
Question 1: You are given the following data about the project
tasks, network, and crash times/costs. Calculate the cost of the
project at all-time durations until you can no longer crash the
project any further.
Answer is not given as the question is left as an exercise.munotes.in

Page 96

96
Question 2:
Crash the project activities given in the following table:
Answer:
Suppose the project manager wants to reduce the new product
project from 41 to 36 weeks:
/g120Crashing Costs are considered to be linear
/g120Look to crash activities on the critical path
/g120Crash the least expensive activities on the critical path first
(based on cost per week)
a. Crash activity I from 3 weeks to 2 weeks $1000
b. Crash activity J from 4 weeks to 2 weeks $2400
c. Crash activity D from 6 weeks to 4 weeks $4000
d. Recommend Crash Cost $7400
/g120Will crashing 5 weeks return more than it costs?munotes.in

Page 97

97
4.3.8 SUGGESTED READINGS
Network Analysis section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 98

98
MODULE – V
GAME THEORY
5.1
INTRODUCTION TO THEORY OF GAMES
Introduction to Theory of Games, Characteristics of Games, Game
Models
Unit Structure
5.1.1 Introduction
5.1.2 Objectives
5.1.3 Introduction to Theory of Games
5.1.4 Characteristics of Games and Game Models
5.1.5 Let us sum up
5.1.6 Exercises
5.1.7 Suggested Readings
5.1.1 INTRODUCTION
Game theory is "the study of mathematical models of conflict
and cooperation between intelligent rational decision-makers."
Game theory is mainly used in economics, political science
and psychology as well as in logic, computer science and biology.
Originally, it addressed zero-sum games, in which one person's
gains result in losses for the other participants. Today, game theory
applies to a wide range of behavioral relations, and is now
an umbrella term for the science of logical decision making in
humans, animals, and computers.
This theory was developed extensively in the 1950s by many
scholars. Game theory was later explicitly applied to biology in the
1970s, although similar developments go back at least as far as the
1930s. Game theory has been widely recognized as an important
tool in many fields.
Game theory is a tool used to analyze strategic behavior by
taking into account how participants expect others to behave.munotes.in

Page 99

99
Game theory is used to find the optimal outcome from a set of
choices by analyzing the costs and benefits to each independent
party as they compete with each other.
5.1.2 OBJECTIVES
After studying this Unit – V Chapter 5.1, you will be able to
understand the following:
/g120Introduction to Theory of Games
/g120Characteristics of Games
/g120Characteristics of Game Models.
5.1.3 INTRODUCTION TO THEORY OF GAMES
Game theory is the formal study of conflict and cooperation.
Game theoretic concepts apply whenever the actions of several
agents are interdependent. These agents may be individuals,
groups, firms, or any combination of these. The concepts of game
theory provide a language to formulate structure, analyze, and
understand strategic scenarios.
The earliest example of a formal game-theoretic analysis is
the study of a duopoly by Antoine Cournot in 1838. The
mathematician Emile Borel suggested a formal theory of games in
1921, which was furthered by the mathematician John von
Neumann in 1928 in a “theory of parlor games.” Game theory was
established as a field in its own right after the 1944 publication of
the monumental volume Theory of Games and Economic Behavior
by von Neumann and the economist Oskar Morgenstern. This book
provided much of the basic terminology and problem setup that is
still in use today.
In 1950, John Nash demonstrated that finite games have
always had an equilibrium point, at which all players choose actions
which are best for them given their opponents’ choices. This central
concept of non-cooperative game theory has been a focal point of
analysis since then. In the 1950s and 1960s, game theory was
broadened theoretically and applied to problems of war and politics.
Since the 1970s, it has driven a revolution in economic theory.
Additionally, it has found applications in sociology and psychology,
and established links with evolution and biology. Game theory
received special attention in 1994 with the awarding of the Nobel
Prize in economics to Nash, John Harsanyi, and ReinhardSelten.
At the end of the 1990s, a high-profile application of game
theory has been the design of auctions. Prominent game theorists
have been involved in the design of auctions for allocating rights to
the use of bands of the electromagnetic spectrum to the mobilemunotes.in

Page 100

100
telecommunications industry. Most of these auctions were designed
with the goal of allocating these resources more efficiently than
traditional governmental practices, and additionally raised billions of
dollars in the United States and Europe.
How does it work (example)?
Game theory explores the possible outcomes of a situation
in which two or more competing parties look for the course of action
that best benefits them. No variables are left to chance, so each
possible outcome is derived from the combinations of simultaneous
actions by each party.
Game theory is best exemplified by a classic hypothetical
situation called the Prisoners' Dilemma. In this scenario, two people
are arrested for stealing a car. They will each serve 2 years in
prison for their crime.
The case is air-tight, but the police have reason to suspect
that the two prisoners are also responsible for a recent string of
high-profile bank robberies. Each prisoner is placed in a separate
cell. Each is told he is suspected of being a bank robber and
questioned separately regarding the robberies. The prisoners
cannot communicate with each other.
The prisoners are told that a) if they both confess to the
robberies, they'll each serve 3 years for the robberies and the car
theft, and b) if only one confesses to the robbery and the other
does not, the one who confesses will be rewarded with a
1y e a rs e n t e n c e w h i l e t h e o t h e r w i l l b e p u n i s h e d w i t h a 1 0 y e a r
sentence.
In the game, the prisoners have only two possible actions:
confess to the bank robbery, or deny having participated in the
bank robbery.
Since there are two players, each with two different
strategies, there are four outcomes that are possible:munotes.in

Page 101

101
The best option for both prisoners is to deny committing the
robberies and face 2 years in prison for the car theft. But because
neither can be guaranteed that the other won't confess, the most
likely outcome is that both prisoners will hedge their bets and
confess to the robberies -- effectively taking the 10 year sentence
off the table and replacing it with the 3 year sentence.
5.1.4 CHARACTERISTICS OF GAMES AND GAME
MODELS
AG a m ei sd e f i n e da sa na c t i v i t ya m o n gt w oo rm o r e
persons as per a set of rules at the end of which each person gets
some benefit or bears loss. The set of rules and procedures defines
thegame .G o i n gw i t ht h es e to fr u l e sa n dp r o c e d u r e so n c eb yt h e
participants defines the play.
Characteristics of Games
/g120There are finite number of competitors known as 'players'
/g120All the strategies and their impacts are specified to the players
but player does not know which strategy is to be selected.
/g120Each player has a limited number of possible courses of action
known as 'strategies'
/g120A game is played when every player selects one of his
strategies. The strategies are supposed to be preparedmunotes.in

Page 102

102
simultaneously with an outcome such that no player recognizes
his opponent's strategy until he chooses his own strategy.
/g120The figures present as the outcomes of strategies in a matrix
form are known as 'pay-off matrix'.
/g120The game is a blend of the strategies and in certain units which
finds out the gain or loss.
/g120The player playing the game always attempts to select the best
course of action which results in optimal pay off known as
'optimal strategy'.
/g120The expected pay off when all the players of the game go after
their optimal strategies is called as 'value of the game'. The
main aim of a problem of a game is to determine the value of
the game.
/g120The game is said to be 'fair' if the value of the game is zero or
else it is known as 'unfair'.
1. Competitive game
Ac o m p e t i t i v es i t u a t i o ni sk n o w na s competitive game if it
has the four properties
a. There are limited number of competitors such that n /g1492. In the
case of n = 2, it is known as a two-person game and in case of
n>2 ,i ti sk n o w na s n-person game .
b. Each player has a record of finite number of possible actions.
c. A play is said to takes place when each player selects one of his
activities. The choices are supposed to be made simultaneously
i.e. no player knows the selection of the other until he has
chosen on his own.
d. Every combination of activities finds out an outcome which
results in a gain of payments to every player, provided each
player is playing openly to get as much as possible. Negative
gain means the loss of same amount.
2. Strategy
The strategy of a player is the determined rule by which
player chooses his strategy from his own list during the game. The
two types of strategy are:
/g120Pure strategy
/g120Mixed strategy.
Pure Strategy
If a player knows precisely what another player is going to
do, a deterministic condition is achieved and objective function is to
maximize the profit. Thus, the pure strategy is a decision rule
always to choose a particular startegy.munotes.in

Page 103

103
Mixed Strategy
If a player is guessing as to which action is to be chosen by
the other on any particular instance, a probabilistic condition is
achieved and objective function is to maximize the expected profit.
Hence the mixed strategy is a choice among pure strategies with
fixed probabilities.
Repeated Game Strategies
/g120In repeated games, the chronological nature of the relationship
permits for the acceptance of strategies that are dependent on
the actions chosen in previous plays of the game.
/g120Most contingent strategies are of the kind called as "trigger"
strategies.
/g120For Example trigger strategies
- In prisoners' dilemma: At start, play doesn't confess. If your
opponent plays Confess, then you need to play Confess in the next
round. If your opponent plays don't confess, then go for doesn't
confess in the subsequent round. This is called as the "tit for tat"
strategy.
- In the investment game, if you are sender: At start play Send.
Play Send providing the receiver plays Return. If the receiver plays
keep, then never go for Send again. This is called as the "grim
trigger" strategy.
3. Number of persons
When the number of persons playing is 'n' then the game is
known as 'n' person game. The person here means an individual or
ag r o u pa i m sa tap a r t i c u l a ro b j e c t i v e .
Two-person, zero-sum game
A game with just two players (player A and player B) is
known as 'two-person, zero-sum game', if the losses of one player
are equal to the gains of the other one so that the sum total of their
net gains or profits is zero.
Two-person, zero-sum games are also known as rectangular
games as these are generally presented through a payoff matrix in
a rectangular form.
4. Number of activities
The activities can be finite or infinite.
5. Payoff
Payoff is referred to as the quantitative measure of
satisfaction a person obtains at the end of each play.munotes.in

Page 104

104
6. Payoff matrix
Assume the player A has 'm' activities and the player B has
'n' activities. Then a payoff matrix can be made by accepting the
following rules
/g120Row designations for every matrix are the activities or actions
available to player A
/g120Column designations for every matrix are the activities or
actions available to player B
/g120Cell entry V ijis the payment to player A in A's payoff matrix
when A selects the activity i and B selects the activity j.
/g120In a zero-sum, two-person game, the cell entry in the player B's
payoff matrix will be negative of the related cell entry V ijin the
player A's payoff matrix in order that total sum of payoff matrices
for player A and player B is finally zero.
7.Value of the game
Value of the game is the maximum guaranteed game to
player A (maximizing player) when both the players utilizes their
best strategies. It is usually signifies with 'V' and it is unique.
Game Models
Simultaneous v. Sequential Move Games
/g120Games where players select activities simultaneously are
simultaneous move games.
a. Examples: Sealed-Bid Auctions, Prisoners' Dilemma.
b. Must forecast what your opponent will do at this point,
finding that your opponent is also doing the same.
/g120Games where players select activities in a particular series or
sequence are sequential move games.
a. Examples: Bargaining/Negotiations, Chess.
b. Must look forward so as to know what action to select now.
c. Many sequential move games have deadlines on moves.
/g120Many strategic situations include both sequential and
simultaneous moves
One-Shot versus Repeated Games
/g120One-shot: play of the game takes place once.
a. Players likely not know much about each another.munotes.in

Page 105

105
b. Example - tipping on vacation
/g120Repeated: play of the game is recurring with the same players.
a. Finitely versus Indefinitely repeated games
b. Reputational concerns do matter; opportunities for
cooperative behavior may emerge.
/g120Advise: If you plan to follow an aggressive strategy, ask yourself
whether you are in a one-shot game or in repeated game. If a
repeated game then think again .
Usually games are divided into
/g120Pure strategy games
/g120Mixed strategy games
The technique for solving for these two types does change.
By solving a game, we require to determine best strategies for both
the players and also to get the value of the game.
Saddle point method can be used to solve pure strategy games.
The diverse methods for solving a mixed strategy game are
/g120Dominance rule
/g120Analytical method
/g120Graphical method
/g120Simplex method
In the next chapter you will learn solution of 2x2, MxN games
using the dominance rule and analytical method. The Simplex
method for solving a mixed strategy game is out of this course.
5.1.5 LET US SUM UP
In this unit you have learnt Project Planning, Scheduling and
Controlling, Work Break down Structure, Basic Tools and
Techniques of Project Management and Role of Network
Technique in Project Management.
Limitations of Game Theory
The main limitations are
/g120The hypothesis that the players have the information about their
own payoffs and others is rather impracticalmunotes.in

Page 106

106
/g120As the number of players adds in the game, the analysis of the
gaming strategies turns out to be increasingly intricate and
complicated.
/g120The assumptions of maximin and minimax presents that the
players are risk-averse and have whole information of the
strategies. It doesn't look practical.
/g120Rather than each player in an oligopoly condition working under
uncertain situations, the players will permit each other to share
the secrets of business so as to work out collusion. Then the
mixed strategies are not very helpful.
5.1.6 EXERCISES
Question 1 :D i s c u s st h ep r o p e r t i e so fag a m e .
Question 2 :W h a td oy o uu n d e r s t a n db yG a m eT h e o r y ?
5.1.7 SUGGESTED READINGS
Game Theory section in any of the reference / text books
/g153/g153/g153/g153/g153/g3/g3munotes.in

Page 107

107
5.2
RULES FOR GAME THEORY
Rules for Game Theory, Concept of Pure Game, Mixed Strategies
–2 x 2G a m e s
Unit Structure
5.2.1 Introduction
5.2.2 Objectives
5.2.3 Rules of Game Theory
5.2.4 Concept of Pure Game
5.2.5 Mixed Strategies – 2X2 Games
5.2.6 Let us sum up
5.2.7 Exercises
5.2.8 Suggested Readings
5.2.1 INTRODUCTION
Game Theory is the process of modeling the strategic
interaction between two or more players in a situation containing
set rules and outcomes. While used in a number of disciplines,
game theory is most notably used as a tool within the study
of economics. The economic application of game theory can be a
valuable tool to aide in the fundamental analysis of industries,
sectors and any strategic interaction between two or more firms.
Here, we'll take an introductory look at game theory and the terms
involved, and introduce you to a simple method of solving games.
Definitions
Any time we have a situation with two or more players that
involves known payouts or quantifiable consequences, we can
use game theory to help determine the most likely
outcomes. Let's start out by revisiting a few terms commonly
used in the study of game theory:
/g120Game: Any set of circumstances that has a result dependent on
the actions of two of more decision makers ("players")
/g120Players: A strategic decision maker within the context of the
gamemunotes.in

Page 108

108
/g120Strategy: A complete plan of action a player will take given the
set of circumstances that might arise within the game
/g120Payoff: The payout a player receives from arriving at a particular
outcome. The payout can be in any quantifiable form, from
dollars to utility.
/g120 Information Set: The information available at a given point in the
game. The term information set is most usually applied when
the game has a sequential component.
Equilibrium: The point in a game where both players have made
their decisions and an outcome is reached.
Assumptions
As with any concept in economics, there is the assumption
of rationality. There is also an assumption of maximization. It is
assumed that players within the game are rational and will strive to
maximize their payoffs in the game. (The question of rationality has
been applied to investor behavior as well).
When examining games that are already set up, it is
assumed on your behalf that the payouts listed include the sum of
all payoffs that are associated with that outcome. This will exclude
any "what if" questions that may arise.
The number of players in a game can theoretically be infinite,
but most games will be put into the context of two players. One of
the simplest games is a sequential game involving two players.
5.2.2 OBJECTIVES
After studying this unit V – Chapter 5.2, you will be able to
understand the following:
/g120Rules of Game Theory
/g120Concept of Pure Game
/g120Mixed Strategies –2 X 2G a m e s .
5.2.3 RULES OF GAME THEORY
The game theory provides an appropriate solution of a
problem if its conditions are properly satisfied. These conditions are
often termed as the assumptions of the game theory which can be
considered as the rules of game theory.munotes.in

Page 109

109
Some of these assumptions are as follows:
i. Assumes that a player can adopt multiple strategies for
solving a problem
ii. Assumes that there is an availability of pre-defined outcomes
iii. Assumes that the overall outcome for all players would be
zero at the end of the game
iv. Assumes that all players in the game are aware of the game
rules as well as outcomes of other players
v. Assumes that players take a rational decision to increase
their profit.
Among the aforementioned assumptions, the last two
assumptions make the application of the game theory confined in
real world.
5.2.4 CONCEPT OF PURE GAME
In a game theory, the pay-off for the players is given in the
pay-off matrix. In a two person game denoted below, player A is
maximizing player and player B is minimizing player. The player A
tries to maximize all his gains while player B tries to minimize all his
losses when opposite player plays his strategies.
Player B
B1 B2
A1 a11 a12 Player A
A2 a21 a22
Player A has two strategies A1, A2 whereas player B has
two strategies B1, B2. The pay-off values a11, a12, a21, a22 are
given in the above pay-off matrix across the strategies when player
Aa n dBa d o p tt h e i rs t r a t e g i e s .
The simplest type of game is one where the best strategies
for both players are pure strategies .T h i si st h ec a s ei fa n do n l yi f ,
the pay-off matrix contains a saddle point.
Asaddle point is a payoff that is simultaneously a row
minimum and a column maximum. To locate saddle points, circle
the row minima and box the column maxima. The saddle
points are those entries that are both circled and boxed. A game is
strictly determined if it has at least one saddle point.
Ap u r es t r a t e g y defines a specific move or action that a player will
follow in every possible attainable situation in a game. Such movesmunotes.in

Page 110

110
may not be random, or drawn from a distribution, as in the case of
mixed strategies. So a pure strategy can be considered as a single
strategy.
Example: What is the optimal strategy for both the players? Use
the pay-off matrix given below:
We use the maximin (minimax) principle to analyze the game.
Select minimum from the maximum of columns.
Minimax = 1
Player A will choose II strategy, which yields the maximum payoff
of 1.
Select maximum from the minimum of rows.
Maximin = 1
Similarly, player B will choose III strategy.
Since the value of maximin coincides with the value of the minimax,
therefore, saddle point (equilibrium point) = 1.
The amount of payoff at an equilibrium point is also known as value
of the game.munotes.in

Page 111

111
The optimal strategies for both players are: Player A must
select II strategy and player B must select III strategy. The value of
game is 1, which indicates that player A will gain 1 unit and player
B will sacrifice 1 unit.
5.2.5 MIXED STRATEGIES – 2X2 GAMES
Mixed strategy means a situation where a saddle point does
not exist, the maximin (minimax) principle for solving a game
problem breaks down. The concept is illustrated with the help of
following example.
Example: Two companies A and B are competing for the same
product. Their different strategies are given in the following pay-off
matrix:
Determine the optimal strategies for both the companies.
First, we apply the maximin (mini max) principle to analyze the
game.
Minimax = -2
Maximin = -2munotes.in

Page 112

112
There are two elements whose value is –2. Hence, the
solution to such a game is not unique.
In the above problem, there is no saddle point. In such
cases, the maximin and minimax principle of solving a game
problem can't be applied. Under this situation, both the companies
may resort to what is known as mixed strategy.
In a mixed strategy, each player moves in a random fashion.
A mixed strategy game can be solved by algebraic method.
We will now talk about the algebraic method used to solve
mixed strategy games. Here we have provided formulas and
examples of algebraic method.
Consider the zero sum two person game given below:
The solution of the game is:
Ap l a y ’ s( p ,1-p )
where:
p=d-c
--------------------
(a + d) - (b + c)
Bp l a y ’ s( q ,1-q )
where:
q=d-b
-------------------
(a + d) - (b + c)
Value of the game, V =ad - bc
--------------------
(a + d) - (b + c)munotes.in

Page 113

113
Example: Consider the game of matching coins. Two players, A &
B, put down a coin. If coins match (i.e., both are heads or both are
tails) A gets rewarded, otherwise B. However, matching on heads
gives a double premium. Obtain the best strategies for both players
and the value of the game.
This game has no saddle point
.p=1-( - 1 )
-----------------------
(2 + 1) - (-1 - 1)=2
----
5
1 – p = 3/5
q=1-( - 1 )
-----------------------
(2 + 1) - (-1 - 1)=2
----
5
1 – q = 3/5
V=2X1-( - 1 )X( - 1 )
--------------------------
(2 + 1) - (-1 - 1)=1
----
5
5.2.6 LET US SUM UP
In this Unit –IV, Chapter – 5.2, you have learnt the Rules of
Game Theory, Concept of Pure Game, Solution of 2X2 game with
saddle point and mixed strategies for 2X2 game.
5.2.7 EXERCISES
Question 1 :
Solve the game whose pay-off matrix is given below:
munotes.in

Page 114

114
Question 2 :
Solve the game whose pay-off matrix is given below:
Question 3:
Discuss and define important terms in Game Theory.
5.2.8 SUGGESTED READINGS
Game Theory section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 115

115
5.3
MIXED STRATEGIES – MXN GAMES
Mixed Strategies – 2xN or Mx2, Mixed Strategies – MxN Games
Unit Structure
5.3.1 Introduction
5.3.2 Objectives
5.3.3 Solution of 2xN Game
5.3.4 Solution of Mx2 Game
5.3.5 Mixed Strategies – MxN Games
5.3.6 Let us sum up
5.3.7 Exercises
5.3.9 Suggested Readings
5.3.1 INTRODUCTION
In the theory of games a player is said to use a mixed
strategy whenever he or she chooses to randomize over the setof
available actions. Formally, a mixed strategy is a probability
distribution that assigns to each available action a likelihood of
being selected. If only one action has a positive probability of being
selected, the player is said to use a pure strategy.
Am i x e ds t r a t e g yp r o f i l ei sal i s to fs t r a t e g i e s ,o n ef o re a c h
player in the game. A mixed strategy profile induces a probability
distribution or lottery over the possible out-comes of the game. A
Nash equilibrium (mixed strategy)is a strategy profile with the
property that no single player can, by deviating unilaterally to
another strategy, induce a lottery that he or she finds strictly
preferable. In 1950 the mathematician John Nash proved that every
game with afinite set of players and actions has at least one
equilibrium.
To illustrate, one can consider the children’s game Matching
Pennies, in which each of two players can choose either heads (H)
or tails (T); player 1 wins a dollar from player 2 if their choices
match and loses a dollar to player 2 if they do not. This game can
be represented as follows:munotes.in

Page 116

116
Here player 1’s choice determines a row, player 2’schoice
determines a column, and the corresponding cell indicates the
payoffs to players 1 and 2 in that order. This game has a unique
Nash equilibrium that requires each player to choose each action
with probability one-half.
5.3.2 OBJECTIVES
In this Unit – V – Chapter 5.3, you will learn about the solution of
game using mixed strategies for the following game models:
/g1202xN
/g120Mx2
/g120MxN Games.
5.3.3 SOLUTION OF 2XN GAME
Graphical Method can only be used in games with no saddle
point, and having a pay-off matrix of type n X 2 or 2 X n.
Consider the following pay-off matrix:
munotes.in

Page 117

117
The game does not have a saddle point as shown in the
following table.
Maximin = 4, Minimax = 3
First, we draw two parallel lines 1 unit distance apart and
mark a scale on each. The two parallel lines represent strategies of
player B.
If player A selects strategy A1, player B can win –2 (i.e., lose
2 units) or 4 units depending on B’s selection of strategies. The
value -2 is plotted along the vertical axis under strategy B 1and the
value 4 is plotted along the vertical axis under strategy B 2.A
straight line joining the two points is then drawn.
Similarly, we can plot strategies A2 and A3 also. The
problem is graphed in the following figure.
munotes.in

Page 118

118
The lowest point V in the shaded region indicates the value
of game. From the above figure, the value of the game is 3.4 units.
Likewise, we can draw a graph for player B.
The point of optimal solution (i.e., maximin point) occurs at the
intersection of two lines:
E1 = -2p 1+4 p 2and
E2 = 8p 1+3 p 2
Comparing the above two equations, we have
-2p 1+4 p 2=8 p 1+3 p 2
Substituting p 2=1-p 1
-2p 1+4 ( 1-p 1)=8 p 1+3 ( 1-p 1)
p1=1 / 1 1
p2= 10/11
5.3.4 SOLUTION OF MX2 GAME
Draw two vertical axes 1 unit apart. The two lines are x1=0,
x1= 1.
Take the points of the first row in the payoff matrix on the
vertical line x1= 1 and the points of the second row in the payoff
matrix on the vertical line x1= 0.
The point a1jon axis x1= 1 is then joined to the point a2jon
the axis x1= 0 to give a straight line. Draw‘n’ straight lines for j=1,
2... n and determine the lowest point of the upper envelope
obtained. This will be the minimax point .
The two or more lines passing through the minimax point
determines the required 2 x 2 payoff matrix. This in turn gives the
optimum solution by making use of analytical method.
Example 1: Solve by Graphical Method .
munotes.in

Page 119

119
V=3 / 9=1 / 3
SA = (0, 5 /9, 4/9, 0)
SB = (3/9, 6 /9)munotes.in

Page 120

120
Example 2: Solve by Graphical Method.
V=7 3 / 1 7
SA= (0, 16/17, 1/17, 0, 0)
SB= (5/17, 12 /17)munotes.in

Page 121

121
5.3.5 MIXED STRATEGIES – MXN GAME
The MxN game is reduced to 2xn or Mx2 game using the
principle of dominance and then the Graphical Method is used on
the revised matrix.
In a game, sometimes a strategy available to a player might
be found to be preferable to some other strategy / strategies. Such
a strategy is said to dominate the other one(s). The rules of
dominance are used to reduce the size of the payoff matrix. These
rules help in deleting certain rows and/or columns of the payoff
matrix, which are of lower priority to at least one of the remaining
rows, and/or columns in terms of payoffs to both the players. Rows
/c o l u m n so n c ed e l e t e dw i l ln e v e rb eu s e df o rd e t e r m i n i n gt h e
optimal strategy for both the players.
This concept of domination is very usefully employed in
simplifying the two – person zero sum games without saddle point.
In general the following rules are used to reduce the size of payoff
matrix.
The Rules (Principles of Dominance) you will have to follow are:
Rule 1: If all the elements in a row (say ithrow) of a payoff matrix
are less than or equal to the corresponding elements of the other
row (say jthrow) then the player A will never choose the ithstrategy
then we say ithstrategy is dominated by jthstrategy and will delete
the ith row.
Rule 2: If all the elements in a column (say rthcolumn) of a payoff
matrix are greater than or equal to the corresponding elements of
the other column (say sthcolumn ) then the player B will never
choose the rthstrategy or in the other words
the rthstrategy is dominated by the sthstrategy and we delete rth
column.
Rule 3: A pure strategy may be dominated if it is inferior to average
of two or more other pure strategies.
Example:
Given the payoff matrix for player A, obtain the optimum
strategies for both the players and determine the value of the
game.munotes.in

Page 122

122
Solution
When A chooses strategy A1 or A2, B will never go to strategy B3.
Hence strategyB3 is redundant.
Minimax (=0), maximin (= -3).Hence this isnot a pure strategy with
a saddle point.
Let the probability of mixed strategy of A for choosing Al and A2
strategies are p1and 1-p1respectively. We get
Again, q1and 1 - q1being probabilities of strategy B, we get
munotes.in

Page 123

123
Hence optimum strategies for players A and B will be as follows:
5.3.6 LET US SUM UP
In this Unit V, Chapter 5.3, you have learnt Game Theory
Mixed Strategies – 2xN or Mx2 Games, Mixed Strategies – MxN
Games and theory of dominance.
5.3.7 EXERCISES
Exercise 1: Given the payoff table for player 1 (politician 1), which
strategy should each player select?
Exercise 2: Solve the following game:
munotes.in

Page 124

124
Exercise 3: Solve the following games:
5.3.8 SUGGESTED READINGS
Game Theory section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 125

125
MODULE - VI
MARKOV CHAINS
6.1
INTRODUCTION TO MARKOV CHAINS
Introduction to Markov Chains, Brand Switching Examples
Unit Structure
6.1.1 Introduction
6.1.2 Objectives
6.1.3 What is Markov Chains
6.1.4 Brand Switching Example
6.1.5 Let us sum up
6.1.6 Exercises
6.1.7 Suggested Readings
6.1.1 INTRODUCTION
Most of our study of probability has dealt with independent
trials processes. These processes are the basis of classical
probability theory and much of statistics.
We have seen that when a sequence of chance experiments
forms an independent trials process, the possible outcomes for
each experiment are the same and occur with the same probability.
Further, knowledge of the outcomes of the previous experiments
does not influence our predictions for the outcomes of the next
experiment. The distribution for the outcomes of a single
experiment is sufficient to construct a tree and a tree measure for a
sequence of n experiments, and we can answer any probability
question about these experiments by using this tree measure.
Modern probability theory studies chance processes for
which the knowledge of previous outcomes influences predictions
for future experiments. In principle, when we observe a sequence
of chance experiments, all of the past outcomes could influence our
predictions for the next experiment. For example, this should be the
case in predicting a student's grades on a sequence of exams in a
course. But to allow this much generality would make it very difficult
to prove general results.munotes.in

Page 126

126
In 1907, A. A. Markov began the study of an important new
type of chance process. In this process, the outcome of a given
experiment can affect the outcome of the next experiment. This
type of process is called a Markov chain.
Markov chains, named after Andrey Markov, are
mathematical systems that hop from one "state" (a situation or set
of values) to another. For example, if you made a Markov chain
model of a baby's behavior, you might include "playing," "eating",
"sleeping," and "crying" as states, which together with other
behaviors could form a 'state space': a list of all possible states. In
addition, on top of the state space, a Markov chain tells you the
probability of hopping, or "transitioning," from one state to any other
state---e.g., the chance that a baby currently playing will fall asleep
in the next five minutes without crying first.
6.1.2 OBJECTIVES
After studying this Unit VI – Chapter 6.1, you will be able to
understand:
/g120Markov Chain
/g120Brand Switching Examples.
6.1.3 WHAT IS MARKOV CHAINS?
Markov Property: The state of the system at time t+1 depends
only on the state of the system at time t
Specifying a Markov Chain
We describe a Markov chain as follows: We have a set of
states, S ={s1;s2, … , sr}.The process starts in one of these states
and moves successively from one state to another. Each move is
called a step. If the chain is currently in state si, then it moves to
state sjat the next step with a probability denoted by pij,a n dt h i s
probability does not depend upon which states the chain was in
before the current state.
The probabilities pijare called transition probabilities. The
process can remainin the state it is in, and this occurs with
probability pii. An initial probability distribution, defined on S,
specifies the starting state. Usually this is done by specifying a
particular state as the starting state.
A picturesque description of a Markov chain is a frog
jumping on a set of lily pads. The frog starts on one of the pads and
then jumps from lily pad to lily pad with the appropriate transition
probabilities.munotes.in

Page 127

127
Example 1: Transition Matrix
Newzeland is blessed by many things, but not by good
weather. They never have two nice days in a row. If they have a
nice day, they are just as likely to have snow as rain the next day. If
they have snow or rain, they have an even chance of having the
same the next day. If there is change from snow or rain, only half of
the time is this a change to a nice day. With this information we
form a Markov chain as follows:
We take as states the kinds of weather R, N, and S. From
the above information we determine the transition probabilities.
These are most conveniently represented in a square array as
The entries in the first row of the matrix P in the above
example represent the probabilities for the various kinds of weather
following a rainy day. Similarly, the entries in the second and third
rows represent the probabilities for the various kinds of weather
following nice and snowy days, respectively. Such a square array is
called the matrix of transition probabilities , or the transition matrix .
We consider the question of determining the probability that,
given the chain is in state itoday, it will be in state jtwo days from
now. We denote this probability by pij(2).
We see that if it is rainy today then the event that itis snowy two
days from now is the disjoint union of the following three events:
/g120it is rainy tomorrow and snowy two days from now,
/g120it is nice tomorrow and snowy two days from now, and
/g120it is snowy tomorrow and snowy two days from now.
The probability of the first of these events is the product of
the conditional probability that it is rainy tomorrow, given that it is
rainy today, and the conditional probability that it is snowy two days
from now, given that it is rainy tomorrow.
Using the transition matrix P, we can write this product as
p11p13.The other two events also have probabilities that can be
written as products of entries of P. Thus, we have
munotes.in

Page 128

128
In general, if a Markov chain has rstates, then
6.1.4 BRAND SWITCHING EXAMPLE
Coke vs. Pepsi Example
•Given that a person’s last cola purchase was Coke, there is a
90% chance that his next cola purchase will also be Coke.
•If a person’s last cola purchase was Pepsi, there is an 80%
chance that his next cola purchase will also be Pepsi.
Transition Matrix
Given that a person is currently a Pepsi purchaser, what is
the probability that he will purchase Coke two purchases from now?
Pr[ Pepsi /g198?/g198Coke ] =
Pr[ Pepsi /g198Coke /g198Coke ] + Pr[ Pepsi /g198Pepsi /g198Coke ] =
0.2 * 0.9 + 0.8 * 0.2 = 0.34/g187/g188/g186
/g171/g172/g170/g328.02.01.09.0P
coke pepsi0.1 0.9 0.8
0.2munotes.in

Page 129

129
6.1.5 LET US SUM UP
In this UNIT VI – Chapter 6.1, you have been taught Markov
Chain, brand switching example and calculation of probabilities.
6.1.6 EXERCISES
Question 1: Given that a person is currently a Coke purchaser,
what is the probability that he will purchase Pepsi three purchases
from now?
Answer: 0.219
Question 2:
Consider a Markov Chain with the following transition matrix:
Draw the transition graph.
Answer:
6.1.7 SUGGESTED READINGS
Markov Chain section in any of the reference / text books
/g153/g153/g153/g153/g153/g3munotes.in

Page 130

130
6.2
MARKOV PROCESS
Markov Process
Unit Structure
6.2.1 Introduction
6.2.2 Objectives
6.2.3 What is a Markov Process
6.2.4 Let us sum up
6.2.5 Exercises
6.2.6 Suggested Readings
6.2.1 INTRODUCTION
As we have discussed earlier, a Markov process is a random
process in which the future is independent of the past, given the
present. Markov processes, named for Andrei Markov are among the
most important of all random processes. In a sense, they are the
stochastic analogs of differential equations and recurrence
relations, which are of course, among the most important
deterministic processes.
6.2.2 OBJECTIVES
In this Unit VI, Chapter 6.2 you will learn about the Markov
Process and the State Transition Matrix.
6.2.3 WHAT IS A MARKOV PROCESS
Suppose that we perform, one after the other, a sequence of
experiments that have the same set of outcomes. If the probabilities
of the various outcomes of the current experiment depend (at most)
on the outcome of the preceding experiment, then we call the
sequence a Markov process.
Every Markov Process has a Markov Property.The state of
the system at time t+1 depends only on the state of the system at
time t.munotes.in

Page 131

131
The experiments of a Markov process are performed at
regular time intervals and have the same set of outcomes. These
outcomes are called states, and the outcome of the current
experiment is referred to as the current state of the process. The
states are represented as column matrices.
Markov Process – Transition Matrix Examples
Example 1:
The transition matrix records all data about transitions from
one state to the other. The form of a general transition matrix is
A stochastic matrix is any square matrix that satisfies the
following two properties:
/g120 All entries are greater than or equal to 0;
/g120 The sum of the entries in each column is 1.munotes.in

Page 132

132
In a double stochastic matrix rows and columns sum up to one.
All transition matrices are stochastic matrices. The transition
matrix for given example is as under:
Transition Matrix – State Diagram
Example 2:
Ap a r t i c u l a ru t i l i t ys t o c ki sv e r ys t a b l ea n d ,i nt h es h o r tr u n ,
the probability that it increases or decreases in price depends only
on the result of the preceding day's trading. The price of the stock is
observed at 4 P.M. each day and is recorded as "increased,"
"decreased," or "unchanged." The sequence of observations forms
a Markov process.
For the utility stock, if the stock increases one day, the
probability that on the next day it increases are .3, remains
unchanged .2 and decreases .5. If the stock is unchanged one day,
the probability that on the next day it increases is .6, remains
unchanged .1, and decreases .3. If the stock decreases one day,
the probability that it increases the next day is .3, is unchanged .4,
decreases .3. Find the transition matrix.
The Markov process has three states: "increases,"
"unchanged," and "decreases."
The transitions from the first state ("increases") to the other
states aremunotes.in

Page 133

133
The transitions from the other two states are:
Putting this information into a single matrix so that each
column of the matrix records the information about transitions from
one particular state is the transition matrix.
Distribution Matrix
The matrix that represents a particular state is called a
distribution matrix. Whenever a Markov process applies to a group
with members in r possible states, a distribution matrix for n is a
column matrix whose entries give the percentages of members in
each of the r states after n time periods.munotes.in

Page 134

134
Distribution Matrix for n
Let A be the transition matrix for a Markov process with initial
distribution matrix then the distribution matrix after n time periods is
given by
Example 3:
Census studies from the 1960s reveal that in the US 80% of
the daughters of working women also work and that 30% of
daughters of nonworking women work. Assume that this trend
remains unchanged from one generation to the next. If 40% of
women worked in 1960, determine the percentage of working
women in each of the next two generations.
There are two states, "work" and "don't work."
The first column of the transition matrix corresponds to
transitions from "work".
The probability that a daughter from this state "works" is 0.8
and "doesn't work" is 1 - 0.8 = 0.2.
Similarly, the daughter from the "don't work" state "works"
with probability 0.3 and "doesn't work" with probability 0.7.
Transition Matrix is as under:
munotes.in

Page 135

135
The Initial Distribution Matrix is as under:
Let us show the Distribution Matrix for n(4).
In one generation,
So 50% women work and 50% don't work.
For the second generation,
So 55% women work and 45% don't work.
Interpretation of the Entries of An
The entry in the ithrow and jthcolumn of the matrix Anis the
probability of the transition from state jto state iafter nperiods.
Example Interpretation of the Entries
Interpret from the last example.
If a woman works, the probability that her granddaughter will
work is .7 and not work is .3.
If a woman does not work, the probability that her
granddaughter will work is .45 and not work is .55.
munotes.in

Page 136

136
6.2.4 LET US SUM UP
In this UNIT VI – Chapter 6.2, you have learnt that:
/g120A Markov process is a sequence of experiments performed at
regular time intervals involving states .A sar e s u l to fe a c h
experiment, transitions between states occur with probabilities
given by a matrix called the transition matrix .T h e ijthentry in the
transition matrix is the conditional probability
Pr(moving to state i|in state j).
/g120Astochastic matrix is a square matrix for which every entry is
greater than or equal to 0 and the sum of the entries in each
column is 1. Every transition matrix is a stochastic matrix.
/g120The nthdistribution matrix gives the percentage of members in
each state after ntime periods.
/g120Anis obtained by multiplying together ncopies of A. Itsijthentry
is the conditional probability Pr(moving to state iafter ntime
periods | in state j). Also, Antimes the initial distribution matrix
gives the nthdistribution matrix.
6.2.5 EXERCISES
Question 1: Explain Markov Process, Markov Chain and State
Transition Diagram.
Question 2:
Each time a certain horse runs in a three-horse race, he has
probability 1/2 of winning, 1/4 of coming in second, and 1/4 of
coming in third, independent of the outcome of any previous race.
We have an independent trials process, but it can also be
considered from the point of view of Markov chain theory. Draw the
transition probability matrix.
Answer:
munotes.in

Page 137

137
Question 3:
We have two urns that, between them, contain four balls. At
each step, one of the four balls is chosen at random and moved
from the urn that it is in into the other urn. We choose, as states,
the number of balls in the first urn. Draw the transition matrix.
Answer:
6.2.6 SUGGESTED READINGS
Markov Chain section in any of the reference / text book
/g153/g153/g153/g153/g153/g3munotes.in

Page 138

138
6.3
MARKOV PROCESS
Markov Analysis – Input and Output
Unit Structure
6.3.1 Introduction
6.3.2 Objectives
6.3.3 Markov Analysis – Input and Output
6.3.4 Let us sum up
6.3.5 Exercises
6.3.6 Suggested Readings
6.3.1 INTRODUCTION
Markov analysis, like decision analysis, is a probabilistic
technique. However, Marko analysis is different in that it does not
provide a recommended decision. Instead, Markov analysis
provides probabilistic information about a decision situation that can
aid the decision maker in making a decision. In other words,
Markov analysis is not an optimization technique; it is a descriptive
technique that results in probabilistic information.
Markov analysis is specifically applicable to systems that
exhibit probabilistic movement from one state (or condition) to
another, over time. For example, Markov analysis can be used to
determine the probability that a machine will be running one day
and broken down the next or that a customer will change brands of
cereal from one month to the next. This latter type of example—
referred to as the “brand-switching” problem—will be used to
demonstrate the principles of Markov analysis in the following
discussion.
6.3.2 OBJECTIVES
In this Unit VI, Chapter 6.3 you will learn about the Markov
Analysis – Input and Outputmunotes.in

Page 139

139
6.3.3 MARKOV ANALYSIS – INPUT AND OUTPUT
Markov analysis can be used to analyze a number of
different decision situations; however, one of its most popular
applications has been the analysis of customer brand switching.
This is basically a marketing application that focuses on the loyalty
of customers to a particular product brand, store, or supplier.
Markov analysis provides information on the probability of
customers’ switching from one brand to one or more other brands.
An example of the brand-switching problem will be used to
demonstrate Markov analysis.
As m a l lc o m m u n i t yh a st w og a s o l i n es e r v i c es t a t i o n s ,
Petroco and National. The residents of the community purchase
gasoline at the two stations on a monthly basis. The marketing
department of Petroco surveyed a number of residents and found
that the customers were not totally loyal to either brand of gasoline.
Customers were willing to change service stations as a result of
advertising, service, and other factors. The marketing department
found that if a customer bought gasoline from Petroco in any given
month, there was only a 0.60 probability that the customer would
buy from Petroco the next month and a 0.40probability that the
customer would buy gas from National the next month. Likewise, if
a customer traded with National in a given month, there was an0.80
probability that the customer would purchase gasoline from
National in the next month and a 0.20 probability that the customer
would purchase gasoline from Petroco. These probabilities are
summarized in the table below:
Markov assumptions in this example are:
(1) the probabilities of moving from a state to all others sum to one,
(2) the probabilities apply to all system participants, and
(3) the probabilities are constant over time.
This example contains several important assumptions. First,
notice that in the above table the probabilities in each row sum to
one because they are mutually exclusive and collectively
exhaustive. This means that if a customer trades with Petroco one
month, the customer must trade with either Petroco or National themunotes.in

Page 140

140
next month (i.e., the customer will not give up buying gasoline, nor
will the customer trade with both in one month). Second, the
probabilities in the table apply to every customer who purchases
gasoline. Third, the probabilities in the table will not change over
time. In other words, regardless of when the customer buys
gasoline, the probabilities of trading with one of the service stations
the next month will be the values in the table. The probabilities in
the table will not change in the future if conditions remain the same.
It is these properties that make this example a Markov
process. In Markov terminology, the service station a customer
trades at in a given month is referred to as a state of the system.
Thus, this example contains two states of the system—a customer
will purchase gasolineat either Petroco or National in any given
month. The probabilities of the various states in the table are known
as transition probabilities. In other words, they are the probabilities
of a customer’s making the transition from one state to another
during one time period. The table contains four transition
probabilities.
A transition probability is the probability of moving from one
state to another during one time period.
The state of the system is where the system is at a point in time.
The properties for the service station example just described
define a Markov process. They are summarized in Markov
terminology as follows:
/g120Property 1: The transition probabilities for a given beginning
state of the system sum to one.
/g120Property 2: The probabilities apply to all participants in the
system.
/g120Property 3: The transition probabilities are constant over time.
/g120Property 4: The states are independent over time.
Now that we have defined a Markov process and determined
that our example exhibits the Markov properties, the next question
is, What information will Markov analysis provide?
The most obvious information available from Markov
analysis is the probability of being in a state at some future time
period, which is also the sort of information we can gain from a
decision tree.
For example, suppose the service stations wanted to know
the probability that a customer would trade with it in month 3, given
that the customer traded with it this month.munotes.in

Page 141

141
(l). This analysis can be performed for each service station by using
decision trees, as in the figures below.
To determine the probability of a customer’s trading with
Petroco in month 3, given that the customer initially traded with
Petroco in month 1, we must add the two branch probabilities in
figure associated with Petroco:
0.36 + 0.08 = 0.44, the probability of a customer’s trading with Petroco in
month 3
Likewise, to determine the probability of a customer’s purchasing
gasoline from National in month 3, we add the two branch
probabilities in figure associated with National:
0.24 + 0.32 = 0.56, the probability of a customer’s trading with National in
month 3
Probabilities of future states, given that a customer trades with
Petroco this month
Probabilities of future states, given that a customer trades with
National this month
munotes.in

Page 142

142
This same type of analysis can be performed under the
condition that a customer initially purchased gasoline from National,
as shown in the figure. Given that
National is the startingstate in month 1, the probability of a
customer’s purchasing gasoline from National in month 3 is
0.08 + 0.64 = .72
and the probability of a customer’s trading with Petroco in month 3
is
0.12 + 0.16 = 0.28
Notice that for each starting state, Petroco and National, the
probabilities of ending upin either state in month 3 sum to one:
Although the use of decision trees is perfectly logical for this
type of analysis, it is time consuming and cumbersome. For
example, if Petroco wanted to know the probability that a customer
who traded with it in month 1 will trade with it in month 10, a rather
large decision tree would have to be constructed. Alternatively, the
same analysis performed previously using decision trees can be
done by using matrix algebra techniques.
6.3.4 LET US SUM UP
In this UNIT VI – Chapter 6.3, you have learn Markov Analysis with
examples.
6.3.5 EXERCISES
Question 1:
Discuss the properties that must exist for the transition matrix in to
be considered a Markov process.
Question 2:
The only grocery store in a community stocks milk from two
dairies: Cream wood and Cheese dale.munotes.in

Page 143

143
The following transition matrix shows the probabilities of a
customer’s purchasing each brand of milk next week, given that he
or she purchased a particular brand this week:
Given that a customer purchases Cream wood milk this
week, use a decision tree to determine the probability that he or
she will purchase Cheese dale milk in week 4.
6.3.6 SUGGESTED READINGS
Markov Chain section in any of the reference / text book
/g153/g153/g153/g153/g153/g3munotes.in