## 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