## Page 1

1 1

LINEAR PROGRAMMING

Unit Structure:

1.0 Objectives

1.1 Introduction

1.1.1 Introduction t o Linear Programming

1.1.2 Assumptions of Linear Programming Model

1.1.3 Advantages of Linear Programming

1.1.4 Limitations of Linear Programming

1.1.5 Requireme nts for a Linear Programming Problem

1.1.6 Applications of Linear Programming

1.1.7 Areas of Applications of Linear Programming

1.1.8 Structure of Linear Programming Problem

1.2 Formulation of Linear Programming Problem

1.2.1 Product Mix Problem

1.2.2Production Allocation Problem

1.2.3Inspection Problem

1.2.4 Production Planning Problem

1.2.5 Advertising Media Selection Problem

1.3 Graphical Method of Solution

1.4 Duality

1.5 Post Optimality Analysis and Sensitivity Analysis

1.6 Self Assessment Questi ons

1.0 OBJECTIVES

The learning objectives of Linear Programming are as follows:

1. To develop the skillsets of learners in formulating and solving LPP.

2. To formulate the linear programming problem by considering different

real life business const raints and learners can get solutions to LPP with

alternative courses of action. munotes.in

## Page 2

2

Operation Research 1.1 INTRODUCTION

1.1.1 Introduction to Linear Programming Problem

The linear programming problems are the mathematical methods by which

scare or limited resources of the organiz ation are used effectively and

optimally so as to achieve the objective of the organization i.e. to earn and

to maximize the profit. The resources of the organization such as

manpower, money, method, material and machines are utilized effectively

as and wh en required by the management using linear programming

method. The linear programming problems act as optimization problems

involving maximization and minimization problem. The maximization

refers to the maximization of resources such as profit and sales w hereas

the minimization states to minimization of time and cost. These linear

programming techniques are widely used in the field of Product Mix

Problem Production Allocation Problem, Inspection Problem , Production

Planning Problem , Advertising Media Selec tion Problem , Blending

Problem , Investment Problem , Portfolio Selection problem , Capital

Budgeting Problem, Trim Loss Problem, War Strategy Problem,

Production Scheduling Problem and many other fields where

optimizations are required.

Linear Programming Pr oblem refers to a process of applying

mathematical technique to use the resources of organization effectively

and efficiently using optimization method .

1.1.2 Assumptions of Linear Programming Model

While developing the linear programming model, assumption s required to

be considered are as follows :

a. Certainty

b. Additivity

c. Linearity

d. Continuity or Divisibility

e. Proportionality

f. Limited Choices

Let us discuss each assumption of Linear Programming Model one by one

as follows :

a. Certainty

The certainty assumption states that the various elements of Linear

Programming Model such as objective function, various constraints of the

problem are arbitrary or constant and are determined using maximization

or minimization method to know their precise or deterministic value.

Hence the various factors of Linear Programming Model are precise,

deterministic and certain in values.

munotes.in

## Page 3

3

Linear Programming

b. Additivity

The Additivity assumption states that the objective function for the given

values of decision variable as dependent variable is the sum of given many

independent variables and their correspondent addition will lead to the

maximization of variable or minimization of variable depending on the

nature of objective function.

The Additivity assumption also states that the constraint functions f or the

given values of decision variable as dependent variable is the either

greater than or equal to the sum of given many independent variables or

less than or equal to sum of given many independent variables and their

correspondent addition will lead to the search of values for the variables

say x and y or any other defined variable.

c. Linearity

The objective function and the defined constraint equations are assumed to

be linear so as to find out the values of variables leading to find out the

values o f assumed variables and their optimized value in the objective

function. The linear function states that there exists simultaneous equation

by which the unknown values can be found out.

d. Continuity or Divisibility

The Continuity assumption states that t he values of decision variables are

either positive values or zero values (non -negative values). The

Divisibility or continuity function states that the whole numbers can be

directly taken to solve linear programming problems whereas fractional

numbers are rounded off to the nearest numbers to use and solve linear

programming problems.

e. Proportionality

The Proportionality assumption states that the values of objective function

are in the multiple of assumed variables (say objective function z=3x+4y,

the objective function z is equal to the summation of thrice proportion of x

variable and fourth multiple (proportion) of y variable).

The Proportionality assumption also states that the values of constraint

functions are assumed to be linear and in the multi ple of assumed

variables (say constraint function 4x+5y ≥ 20, assuming linear function,

the constraint function 4x+5y is equal to 20 and the variables x and y are

in the multiples of 5 and 4 for x and y variables respectively .

f. Limited Choices

The lim ited choice assumption states the decision maker has no broad

choice, he has to select the alternative from all available alternatives only

which are limited in choice. The decision variables are finite and decision

maker has to consider the inter -related an d available conditions mentioned

in the linear programming problems as constraints including the non -

negativity constraint (representing the realistic conditions).

munotes.in

## Page 4

4

Operation Research 1.1.3 Advantages of Linear Programming

The linear programming models or problems have sever al advantages in

the form of profit maximization, sales maximization, time minimization or

cost minimization and many more. The linear programming has following

advantages :

a. Optimum Utilization of Limited or Available Resources

b. Improvement in Efficiency and Productivity

c. Assistance for Decision Making

d. Objective oriented direction

e. Attainment of Feasible Solution to the Real Life Situation

f. Understanding the limitations of the project

g. Helps for Change Management

h. Profit and Sales Maximization

i. Time and Cost Minimi zation

Let us discuss the advantages of Linear programming problem in detail as

follows :

a. Optimum Utilization of Limited or Available Resources

The resources are limited in number that's why the decision maker has to

utilize these resources effici ently and effectively so that the management

will achieve the objective of Organization. The constraint represents the

conditions of limited resources and objective function is related to the

optimum utilization of all these resources to maximize the prof it or to

optimize the objective function.

b. Improvement in Efficiency and Productivity

The linear programming problem improve the efficiency and productivity

of available resources such as manpower Maine money method machine

material and 20 improveme nt in available resources will ultimately lead to

the improvement in efficiency and productivity of Manpower and that

leads to the attainment of organisational objective hence the linear

programming problem helps to improve the efficiency and productivity.

c. Assistance for Decision Making

The decision makers are confused for using scare resources. These

ambiguity can be cleared by using linear programming problems as the

optimum utilization of resources can be done with the help of this

technique hen ce decision makers are determine to use proper decision

making principles by using LPP method.

d. Objective oriented direction

The linear programming problems are supposed to achieve the objective

of organization that is to earn and to maximize the p rofit by utilizing

different constraints and achieving the objective function. Hence it

provides the direction to achieve the objective of organization by munotes.in

## Page 5

5

Linear Programming

utilization of given real -life situations or conditions in LPP model or in

linear programming model.

e. Attainment of Feasible Solution to the Real Life Situation

The linear programming problem to attend the feasible solution to the real

life situation in organization it provides possible solution to the existing

problems. The appropriate solution t o different business conditions are

brought into reality with the help of linear programming problems. The

linear programming problems are solved to get different feasible solutions

and their output. The decision variables with the given conditions are

solved to get the feasible solution to the real -life problem of the corporate

world and hence the LPP models are considered as the best solution to

complex business situations.

g. Helps for Change Management

Linear programming problems help to understand the dynamism in the

system and co rresponding change management can be implemented with

the help of linear programming problems.

h. Profit and Sales Maximization

Objective function of linear programming problems helps to maximize the

profit as well as the sales of the organisation. The Optimisation technique

used here is maximization.

i. Time and Cost Minimization

The objective function of linear programming problem is to minimise the

time or duration of completion of the project as well as reduces the cost of

production of the project.

1.1.4 Limitations of Linear Programming:

Although there are many advantages of linear programming problems,

there are few limitations of linear programming. The limitations of linear

programming as follows :

a. Linearity

The relationship s among different variables are considered as linear

relationship but it may not be possible every time that the relationship

among variables of decision making Are linear. The linearity function in

business or in real life situat ion may or may not exist the assumption of

linearity function in the case of linear programming problems is a question

mark.

b. Integer value solutions:

The solution obtained for the linear programming problems in t erms of

objective function many may or ma y not be integer value functions. It

may be the whole number or fractional number. Thus every time, an

integer value s olution may not be possible. The optimal solution may not munotes.in

## Page 6

6

Operation Research be appropriate if they reach rounding off to the nearest integer value. This

is one of the biggest limitations of linear programming problem.

c. Uncertainty:

The linear programming problem may not consider the change factors

such as internal change factors as well as external change factors. The

uncontrollable external factors may le ad to change the equation and the

optimal solution may be inappropriate. The uncertainty in different

variables of linear programming may lead to biased linear programming

solution.

d. Value of time:

The linear programming problem does not consider the va lue of time that

is the time for completion of the activity or the time required to consider

the conditions of linear programming problem. Schedule of linear

programming problem are unknown and undetermined that leads to to

fluctuate the solution of linear programming problems

e. Small problems:

The linear programming models are suitable for big problems of

multinational organizations w hereas small part of problems cannot be

solved cannot be fragmented by using linear programming problem

methods.

f. constan t parameters:

The linear programming problems have considered constant parameters of

decision variables but it is not possible every time that the parameter s are

constant. Hence, this is one of the limitations of linear programming

problem.

g. Single objec tive

The single objective is considered in a linear programming problem as

objective function. Th e multiple objectives of organiz ations are not

considered in the linear programming models full stop it is not possible to

attain multiple objectives of organi zation by using linear programming

model.

1.1.5 Requirements for a Linear Programming Problem

The requirements for a linear programming problem mean the need for a

linear programming problem in the business field. The basic objective of

management is to ac hieve the objective of organization that is to earn

profit by effective utilization of all available resources. The available

resources are men, material, money, method and machine. These

resources are limited in number. The use of these resources in the p roper

way is an essential part for the management. The optimum use of these

resources for the accomplishment of the objective of organization is done

by one of the methods called - linear programming problem. munotes.in

## Page 7

7

Linear Programming

Therefore , there is a need of defining linear p rogramming problem and the

requirements for linear programming problem .

The conditions of linear programming problems and its requirements are

as follows :

a. well defined objective function

b. potential constraints

c. alternative course of action

d. interrelated variables

e. non negative be constraint

f. Limited supply

A. Well defined objective function

Linear programming problems should contain well defined objective

functions that highlight the objective of organization. The well -defined

objective function should be an optimization function leading to either

maximization or minimization case. The objective function is defined in a

mathematical equation starting with the letter Z equal to sum function.

B. Potential constraints

The potential constant refers to the c onditions or limitations for things that

have the capacity to achieve the objective of organisation and this

constants must be capable of being expressed as a linear function as either

greater than or less than are equal to as the variable may b e.

C. Alter native course of action:

Linear programming problems must consist of different alternatives called

alternative course of actions. For example a product may be processed on

three different machines and how much quantity of product can be

processed on what m achine that it is known through linear programming

problems.

D. Interrelated variables

The decision variables of linear programming problem are interrelated to

each other they are dependent on each other hence by using simultaneous

equation we can find out the value of solution of a linear programming

problem.

E. Non negative constraint

The decision variables of linear programming problem are non -negative

that is either Zero OR greater than zero and hence the non -negative the

constant indicates that the con stant are realistic in nature and that they

exist in real life situation. munotes.in

## Page 8

8

Operation Research F. Limited supply

The resources may be having l imited supply that's why there is a

requirement of linear programming problem.

1.1.6 Applications of Linear Programming

Applications o f linear programming method are in the resource allocations

of Product Mix Problem, Production Allocation Problem; Inspection

Problem; Production Planning Problem; Advertising Media Selection

Problem; Blending Problem; Investment Problem; Portfolio Selecti on

problem and many other areas.

The linear programming problems are used in assembly line balancing,

make or buy decisions, Facilities location planning, agriculture resource

allocation problems, flight and train scheduling problems, dietary

problems, Env ironment protection problems, profit planning problems,

transportation problems, assignment problems, man power scheduling

cases, profit planning problems and many other areas of business field.

1.1.7 Areas of Applications of Linear Programming

Linear programmi ng problems have wide application in the fi eld of

industry, management and/or other fields. The areas of application of

linear programming problem are as follows :

a. Production scheduling problems

The production scheduling is done in order to match the deman d of the

product, inventory and manpower at minimum threshold level so as to

minimize the total cost of production and so as to keep the minimum

inventory.

b. Product mix problems

The product mix problem involves the mixture of different raw materials,

their ingredients and production capacity and the available resources. The

optimum allocation of resources such as men, machine, money, material,

method, and market can be properly executed with the help of linear

programing problems.

c. Assembly Line balancing P roblems

The high brand value products are not manufactured by a single company.

The multiple brands are involved in the production of different

components of that product. These parts are brought together and

assembled to form brand value product. For exa mple, The Reynolds

Automobile do not build whole car, the tires, seat covers, chromes and

other parts are manufactured by other companies and they are brought

together and assembled to form a new car. The decisions of assembly line

balancing are taken with the help of LPP models.

munotes.in

## Page 9

9

Linear Programming

d. Make or buy decisions Problems

The make or buy decisions may be generally taken with a linear

programming problem as the given conditions are related to make or buy

decisions. When quantities to be manufactured are small in number, then

buy decision may be made and when quantities to be produced are larger

in number then make decision may be made. The quantities as a constraint

and other limitations of the company may decide to make or buy

decisions.

e. Transportation problems

Transpor tation problems involve transfer of goods or services from source

to destination. Transportation involves different constraints such as

quantity to be transferred, distance to be travelled, manufacturing capacity

of source, supply from the source and deman d of the destination, unit

transportation cost and other conditions. The combined constraints and

objectives of transportation can be achieved with the help of linear

programming problems.

f. Assignment problems

Assignment problem involves allocation of diffe rent facilities like

manpower or machines to different jobs. Proper allocations of different

facilities make timely arrangement to execute various jobs on different

machines or different jobs by different employees.

g. Portfolio selection problems

The invest ment banks or other non -banking financial services like Mutual

Fund associations and other share market brokers always face the problem

of portfolio selection. The linear programming problem assists to select a

portfolio based on minimum risk and maximum r eturn. Different

investment alternatives are provided and are selected based on given

constraints in LPP.

h. Agricultural problems

The allocation of different agricultural inputs such as water, labour,

fertilizers , pesticides and capital to different crops ar e properly combined

with the help of linear programming problems. The proper allocation of

Agricultural food in more agricultural output in the form of Agricultural

producers and hence the linear programming problems are greatly helpful

in the allocation o f Agricultural inputs.

1.1.8 Structure of Linear Programming Problem

Structure of linear programming model consists of three components.

1. Variables and their relationship

2. Objective function

3. Constraint. munotes.in

## Page 10

10

Operation Research The components of linear programming models are described in detail as

follows :

1. Variables and their relationship

Variables are decision variables and they are under the control of the

decision maker. The relationships between the variables are generally

linear relationship and are solved using simultaneous solutions . All

decision variables are controllable, non -negative and continuous. They are

represented as x 1, x2,.....x n.

2. Objective function

Objective function is the objective of creating and solving linear

programming problems. Generally the objective function is represented in

the form of profit, sales, revenue, time and cost. Objective function is

represented in two forms that is either to maximize or to minimise with

the help of letter Z as

Z=c 1x1+c2x2+...+c nxn

Where,

Z is the objective function.

c1, c2,....c n are parameters of uncontrollable variable and

x1, x2,.....x n are parameters of controllable variable.

3. Constraints

Constraints are the limitations or given conditions described in linear

programming problems. They are the representations on the use of limited

resources. Constraint represents the mathematical equation where limited

resources can be used effectively so as to maximise the objective function.

1.2 FORMULATION OF LINEAR PROGRAMMING

PROBLEM :-

The linear programming problems are widely used in different sectors of

business, management and administration such as Product Mix Problem,

Production Allocation Problem; Inspection Problem, Production Planning

Problem; Advertising Media Selection Problem; Blending Problem;

Investment Problem; Portfolio S election problem and many other sectors.

1.2.1 Product Mix Problem

Example: A firm manufactures two items. It purchases castings which are

then machined, bored and polished. Castings for items A and B cost Rs 2

and 3 respectively and are sold at Rs 5 and 6 respectively. Running costs

of three machines are Rs. 20, Rs. 14 and Rs. 17.50 per hour respectively.

Capacities of the machine are

munotes.in

## Page 11

11

Linear Programming

Part A Part B

Machining Capacity 25/hr 40/hr

Boring Capacity 28/hr 35/hr

Polishing Capacity 35/hr 25/hr

Formulate the Linear Programming model to determine the product mix

that maximises the profit.

Solution:

1. Variables under study:

As a firm manufactures two items A and B, let us consider x1 and X2 are

the number of units to be manufactured per hour.

2. Objective function:

Here, the objective function is to maximise the profit by utilising proper

product mix.

Determination of Profit for part A and part B

Particulars Formula Part A (Rs.) Part B (Rs.)

Machining Cost = Running cost /

Capacity per hr 20/25= 0.8 20/40=0.5

Boring Cost = Running cost /

Capacity per hr 14/28=0.5 14/35=0.4

Polishing cost = Running cost /

Capacity per hr 17.5/35= 0.5 17.5/25=0.7

Total Assembling

Cost = Machining cost+

Boring Cost+

Polishing Cost 0.8+0.5+0.5=

1.8 0.5+0.4+0.7= 1.6

Casting cost Given 2 3

Total cost =Total assembling

cost+ Casting cost 1.8+2= 3.8 1.6+3 = 4.6

Selling Price Given 5 6

Profit Selling Price - Total

cost 5-3.8= 1.2 6-4.6=1.4

3. Constraints

Constraints are the conditions mentioned on the capacities o f machines.

Running machines for one hour requires following conditions

munotes.in

## Page 12

12

Operation Research Machine Constraint : (1/25) x 1+(1/40) x 2 ≤ 1.

8x1+5x 2 ≤ 200.

Boring Constraint : (1/28) x 1+(1/35) x 2 ≤ 1.

5x1+4x 2 ≤ 140.

Polishing constraint : (1/28) x 1+(1/35) x 2 ≤ 1.

5x1+4x 2 ≤ 140.

Non-negativity constraint :x1 ≥ 0; x 2 ≥ 0

1.2.2 Production Allocation Problem

Example : A firm produces three products. These products are processed

on three different machines. The time required to manufacture one unit of

each of the three products and the daily capacity of the three machines are

given in the table below:

Machine Time per unit (minutes) Machine capacity

(minutes/day)

Product 1 Product 2 Product 3

M1 2 3 2 440

M2 4 - 3 470

M3 2 5 - 430

Solution:

1. Variables unde r study:

As a firm produces three products and are processed on three different

machines , let us consider x 1, x2 and x 3 are the number of units to be

manufactured daily for products 1, 2 and 3 respectively.

2. Objective function:

Here, the objective functi on is to maximise the profit.

The objective function Z= 4x 1+3x 2+6x 3 is to maximize.

3. Constraints

Constraints are the conditions mentioned on the capacities of machines.

Machine M 1 Constraint : 2x1+3x 2+2x3≤ 440.

Machine M 2 Constraint : 4x1+0x 2+3x3≤ 470 . munotes.in

## Page 13

13

Linear Programming

Machine M 3 constraint : 2x1+5x 2+0x3≤ 430.

Non-negativity constraint : x1 ≥ 0; x 2 ≥ 0 and x 3 ≥ 0

1.2.3 Inspection Problem

Example: A company has two grades of inspectors I and II to undertake

quality control inspection. At least, 1500 pieces must be i nspected in an 8

hour day. Grade I inspector can check 20 pieces in an hour with an

accuracy of 96%. Grade II inspector checks 14 pieces an hour with an

accuracy of 92%.

Wages of grade I inspector are Rs. 5 per hour while those of grade II

inspector are Rs . 4 per hour. Any error made by an inspector costs Rs. 3 to

the company, find the optimal assignment of inspectors that minimizes the

daily inspection cost.

Solution:

1. Variables under study:

As a company has two grades of inspectors I and II and are assign ed

grades to undertake quality control inspection. Let us consider x 1, and x 2

are the number of grades of inspectors I and II that are assigned the job of

quality control inspection respectively.

2. Objective function:

Here, the objective function is to mi nimize the daily cost of inspection.

The daily cost of inspection includes two costs namely wages paid to the

inspectors and cost of inspection.

The cost of grade I inspection per hour is = Rs. (5+3x0.04x20) = Rs. 7.4

The cost of grade II inspection per hour is = Rs. (4+3x0.08x14) = Rs. 7.36

The objective function Z= 8 (7.4x 1+7.36x 2) is to maximize.

3. Constraints

Constraints are the conditions mentioned on the grades of inspections.

Grade I Constraint : x1 ≤ 10.

Grade I Constraint : x2 ≤ 15.

Inspect ion constraint : 20(8x 1)+14 (8x 2) ≤ 1500.

Non-negativity constraint : x1 ≥ 0; and x 2 ≥ 0

1.2.4 Production Planning Problem

A factory manufactures a product each unit of which consists of 5 units of

part A and 4 units of part B. The two parts A and B re quire different raw

materials of which 120 units and 240 units respectively are available. munotes.in

## Page 14

14

Operation Research These parts can be manufactured by three different methods. Raw material

requirements per production run and the number of units for each part

produced are given bel ow.

Method Input per run (units) Output per run

(units)

Raw material

1 Raw material

2 Part A Part B

1 7 5 6 4

2 4 7 5 8

3 2 9 7 3

Formulate the Linear Programming Problem model to determine the

number of production runs for each method so as to maxi mize the total

number of complete units of the final product.

Solution:

1. Variables under study:

Let us consider x 1, x2 and x 3 are the number of production runs for each

method 1, 2 and 3 respectively.

2. Objective function:

Here, the objective function is to maximize total units of the final product.

The total units of part A produced by different machines are 6x 1+5x 2+7x 3

and The total units of part B produced by different machines are

4x1+8x 2+3x 3 .

A factory manufactures a product each unit of which consi sts of 5 units of

part A and 4 units of part B. Hence upper limit of production cannot go

beyond ( 6x1+5x 2+7x 3)/5 and (4x 1+8x 2+3x 3)/4.

The objective function Z= Mimimum of (6x 1+5x 2+7x 3)/5 and

(4x 1+8x 2+3x 3)/4).

This equatio n may violates the norms of LPP . We may convert this non -

linear function to linear function by considering the following equation

Let y= Min ((6x 1+5x 2+7x 3)/5 and (4x 1+8x 2+3x 3)/4))

It implies that

(6x 1+5x 2+7x 3)/5 ≥ y and (4x1+8x 2+3x 3)/4) ≥ y.

6x1+5x 2+7x 3 ≥ 5y 4x1+8x 2+3x 3≥ 4y

6x1+5x 2+7x 3 -5y ≥ 0 4x1+8x 2+3x 3-4y≥0

Hence the objective function is to maximize Z =y munotes.in

## Page 15

15

Linear Programming

3. Constraints

Constraints are the conditions mentioned.

Raw Material 1 Constraint : 7x1+4x 2+2x3≤ 120.

Raw Material 2 Constraint : 5x1+7x2+9x3≤ 240

Output Part A Constraint : 6x1+5x2+7x3-5y ≥0

Output Part B Constraint : 4x1+8x2+3x3-4y ≥0

Non-negativity constraint : x1; x2; x3, y ≥ 0;

1.2.5 Advertising Media Selection Problem

An advertising company wishes to plan its advertising strategy in 3

different media - television, radio and magazines. The purpose of

advertising is to reach as large a number of potential customers as

possible. Following data have been obtained from market survey:

Television Radio Magazine I Magazine II

Cost of an advertising

unit Rs. 30,000 Rs.

20,000 Rs.15,000 Rs. 10,000

No. of potential

customers reached

per unit 2,00,000 6,00,000 1,50,000 1,00,000

No. of female

customers reached

per unit 1,50,000 4,00,000 70,000 50,000

The Company wants to spend no more than Rs.4,50,000 on advertising.

Following are the further requirements that must be met:

i. at least 1 million exposures take place among female customers.

ii. advertising on magazines be limited to Rs. 1,50,000.

iii. a tleast 3 advertising units to be brought on magazine 1& 2 units on

magazine II,

iv. the number of advertising units on television and radio should each be

between 5 and 10.

Formulate an L.P. model for the problem.

Solution:

1. Variables under study:

As an advertising company wishes to plan its advertising strategy in 3

different media - television, radio and magazines, Let us consider x 1, x2, x3

and x 4 are the number of advertising units to be brought on tel evision,

radio, magazine I and magazine II respectiv ely.

munotes.in

## Page 16

16

Operation Research 2. Objective function:

Here, the objective function is to maximize the total number of potential

customers reached.

The objective function Z= 10,00,000 (2x 1+6x2+1.5x3+x4) is to maximize.

3. Constraints

Constraints are the conditions mentioned as foll ows.

Advertising Budget Constraint :

30,000x 1+20,000x 2+15,000x 3+10,000x 4 ≤ 4,50,000.

i.e. 30x 1+20x 2+15x 3+10x 4 ≤ 450

Number of female customers reached by advertising campaign Constraint

1,50,000x 1+4,00,000x 2+70,000x 3+50,000x 4 ≥10,00,000.

i.e. 15x 1+40x 2+7x 3+5x 4 ≤ 100.

Expenses on magazine advertising constraint

15,000x 3+10,000x 4 ≥1,50,000.

i.e. 15x 3+10x 4 ≤ 150.

No. of units on magazines constraints

x3≥ 3

x4≥ 2.

No. of units on television constraints

5≤x1≤10

No. of units on radio constraints

5≤x2≤10

Non-negativity constraint : x1, x2, x3, x4 ≥ 0

1.3 GRAPHICAL METHOD OF SOLUTION

The graphical method of solution is used to solve the problems of linear

programming module . The detail steps can be understood through the

numerical as follows

Numerical 1. Use the graphical method of solution for the following linear

programming problem. Maximize Z= 2x 1+x2subject to the constraints

munotes.in

## Page 17

17

Linear Programming

i.) x1+2x 2≤ 10 ii.) x1+x2≤ 6 iii.) x1-x2≤ 2 iv.) x1-2x2≤ 1

and x1, x2 ≥ 0.

Solution:

1. At first we convert the first constraint equa tion x 1+2x 2 ≤ 10 into

x1+2x 2=10.

Now put x 2=0 and calculate the value of x1as x 1=10

Point (x, y) = (10, 0).

Now put x 1 =0 and calculate the value of x2 as x 2=5

Point (x, y) = (0, 5).

2. Now, we convert the second constraint equation x 1+x2 ≤ 6 into

x1+x2=6.

Now put x 2=0 and calculate the value of x1as x 1=6

Point (x, y) = (6, 0).

Now put x 1 =0 and calculate the value of x2 as x 2=6

Point (x, y) = (0, 6).

3. Now, we convert the third constraint equation x 1-x2 ≤ 2into

x1-x2=2.

Now put x 2=0 and calculate the val ue of x1as x 1=2

Point (x, y) = (2, 0).

Now put x 1 =0 and calculate the value of x2 as x 2= -2

Point (x, y) = (0, -2).

x1-2x2≤ 1

4. Now, we convert the third constraint equation x 1-x2 ≤ 2 into

x1-2x2= 1.

Now put x 2=0 and calculate the value of x1as x 1=2

Point (x, y) = (2, 0).

Now put x 1 =0 and calculate the value of x2 as x 2= -1/2

Point (x, y) = (0, -1/2).

Now using graphical points as follows munotes.in

## Page 18

18

Operation Research

Source: Operations Research Book by J.K. Sharma

The point B is at the junction of two lines x1-x2= 2 and x1-2x2= 1

The coordinates of the junction point of intersecting lines can be obtained

by solving the equation of two lines intersecting each other using

simultaneous equation as follows

x1-x2= 2

-x1+2x2 = -1

As x2= 1 and putting the value of x2= 1 in above equation , we get x 1 as 3.

Point B (x,y)= B (3,1).

The point D is at the junction of two lines x1+2x 2= 10 and . x1+x2= 6

The coordinates of the junction point of intersecting lines can be obtained

by solving the equation of two lines intersecting each other using

simultaneous equation as follows

x1+2x 2= 10

-x1-x2= -6

As x2= 4 and putting the value of x2= 4 in above equation, we get x 1 as 2.

Point D (x, y)= B (2,4).

Now as all equations are either less than or equal to some value, the

feasible region lies below t hat all lines. Hence the solution of existing LPP

lies in that feasible region.

munotes.in

## Page 19

19

Linear Programming

Let us check all extreme values of feasible region as follows

Extreme point Coordinates Value (Objective

function)

0 (0,0) 2(0)+1(0)=0

A (1,0) 2(1)+1(0)=2

B (3,1) 2(3)+1(1)= 7

C (4,2) 2(4)+1(2)=10

D (2,4) 2(2)+1(4)=8

E (0,5) 2(0)+1(5)=5

The maximum value of objective function lies at point C(4,2) as 10 and

hence the optimal solution to the given LPP is : x1=4 and x2=2 and Max

Z=10.

1.4 DUALITY

There is a set of unique li near programming problem for every linear

programming problem. The other linear programming problem includes

same data reflecting program and is called as dual Program. The dual

program is obtained by transposing the rows and columns of linear

programming problem. Dual variables are also called as shadow prices of

various sources. Solution for dual program also exist just like that of

original linear programming problem. Solutions of Primal program and

dual program are very closely related to each other.

The features of duality in linear program is as follows

1. If the original linear programming problem has many rows and few

columns then the calculation can be complex one. At that time,

solution of linear programming problem can be obtained by

converting rows and columns.

2. The duality in linear programming give the additional information as

changes in options can change the optimal solution of linear

programming problem. This change in coefficient leading to change

in the s olution of linear programming problem is reflex sensitivity

analysis or post optimality analysis.

3. Generally , the duality in linear programming evaluates on different

economic nature and hence, it helps to evaluate opportunity cost for

different alternative s available to the solution and their relative

values.

4. The accuracy of primal solution can be checked with the help of

duality in linear programming,

5. The duality in linear programming is just same that of zero Sum game

in Game Theory. munotes.in

## Page 20

20

Operation Research 1.5 POST OPTIMALITY A NALYSIS AND SENSITIVITY

ANALYSIS

The change in the values of variables of linear programming problem

leads to changes in the optimal solution of a linear programming problem.

The sensitivity analysis is a study of sensitivity of optimal solution of

linear programming problem by studying the discrete variation in the

variables of linear programming problem.

The sensitivity can be measured from zero value to the corresponding

value as per the corresponding changes in the optimal solution of linear

programmi ng. We first calculate the solution of Original linear

programming problem and we consider the changes in the constraints of

linear programming problem leading to the changes in the solution of

linear programming problem. The variation can be noted and com pared

with orig inal linear programming problem. The process of studying the

sensitivity of optimal solution of linear programming problem is also

called as post optimality analysis because it is done after an optimal

solution.

The changes in one of the fol lowing parameters of original linear

programming problem can make sensitivity analysis and alter the solution

of linear programming problem as :

1. Changes in the objective function

2. Change in the value of constraints.

3. Changing the value of availability of res ources.

4. Change in the consumption of resources.

5. Addition of new variable.

6. Addition of new constraints to the original linear programming

problem

1.6 SELF ASSESSMENT QUESTIONS

Q1. Answer Multiple Choice Questions

1. The linear programming problems are the … …..by which scare or

limited resources of the organization are used effectively and

optimally so as to achieve the objective of the organization i.e. to

earn and to maximize the profit.

a. mathematical methods

b. statistical methods

c. quantitative methods

d. nume rical methods

munotes.in

## Page 21

21

Linear Programming

2. ………refers to a process of applying mathematical technique to

use the resources of organization effectively and efficiently using

optimization method.

a. Game Theory

b. Linear Programming Problem

c. Assignment Problem

d. Transportation Problem.

3. Assu mptions of Linear Programming Model do not include …

a. Linearity

b. Continuity or Divisibility

c. Proportionality

d. Unlimited Choices .

4. The linear programming has following advantages

a. Optimum Utilization of Limited or Available Resources

b. Improvement in Efficiency and Productivity

c. Assistance for Decision Making

d. All of these

5. ….. states that the values of decision variables are either positive

values or zero values (non -negative values).

a. Continuity assumption

b. Proportionality assumption

c. Both a and b

d. None of the above

6. The …….states that the values of objective function are in the

multiple of assumed variables

a. Continuity assumption

b. Proportionality assumption

c. Both a and b

d. None of the above

Answers: 1: a 2:b 3:d

4:d 5:a 6:b munotes.in

## Page 22

22

Operation Research Q2. Write short notes o n:

a. Assumptions of Linear Programming Model

b. Advantages of Linear Programming

c. Limitations of Linear Programming

d. Requirements for a Linear Programming Problem

e. Applications of Linear Programming

f. Areas of Applications of Linear Programming

g. Structure of Linear P rogramming Problem

h. Duality

i. Post Optimality Analysis

j. Sensitivity Analysis

munotes.in

## Page 23

23 2

TRANSPORTATION

Unit Structure:

2.0 Objectives

2.1 Introduction

2.2 Matrix Terminology

2.3 Solution of Transportation model

2.4 Methods of Obtaining an Initial Feasible Solution

2.4.1 North West Corner Method

2.4.2 Row Minima Method

2.4.3 Column Minima Me thod

2.4.4 Least Cost Method

2.4.5 Vogels’ Approximation Method.

2.5 Self Assessment Test

2.0 OBJECTIVES

The learning objectives of transportation are as follows :

1. To understand different concepts and terminologies used in the

transportation problem.

2. To comprehend transportation model and to develop solution to the

transport ation model.

3. To develop logical thinking and analytical solutions to the

transportation problem.

4. To use different methods of solving transportation model and to

minimize th e total transportation cost.

2.1 INTRODUCTION

Transportation is a typical type of operation research technique developed

for transportation of goods from the sources to the destination.

Transportation problem is a special type of linear programming probl em

which can be solved by using different methods of transportation. A single

product can be transported from several sources to different destinations

with the help of transportation problems.

munotes.in

## Page 24

24

Operation Research 2.1.1 Constraints or conditions of transportation problem:

The constraints of transportation problems involve different conditions

under which transportation problem can be solved. The const raints of

transportation problem are as follows :

1. Demand and supply relation

Necessary and sufficient condition for existence of a feasible solution to

the transportation problem is that there should be total demand equal to

total supply. (i.e. Total demand is equal to total supply).

2. Balanced Transportation problem

When total demand is equal to total supply then the transportation

problem is said to be balanced.

3. Unbalanced transportation problem

If total demand is not equal to total supply then the transportation problem

is an unbalanced transportation problem.

4. Occu pied cells and unoccupied cells

The occupied cells are having posit ive allocation in a transportation

problem and are denoted by a circular symbol. The cells are not having

any allocation in a transportation problem.

5. Basic feasible solution

The basic feasible solution exists when number of occupied cells are equal

to numb er of rows and number of columns minus one i.e. (No. of occupied

cells = m+n -1). Where m is the number of rows and n is the number of

columns.

6. Degenerate solution and non -degenerate solution

When the number of positive allocated cells are less than m+n -1 and a

solution is degenerate solution and when the number of positive located

cells are equal to m+n -1 then the solution is non -degen erate solution.

7. Prohibited routes

Due to unfavorable road conditions, bad weather conditions or any other

condition etc., It may not be possible to transit products from the sources

to the destination such routes are prohibited routes.

2.2 MATRIX TERMINOLOGY

Following matrix terminologies are often used in transportation model.

1 Cell munotes.in

## Page 25

25

Transportation The smallest element of a matrix is called a cell. It is at the intersection of

row and column. The cell in a transportation model represents the unit

cost of transportation from source to the destination.

2 Row

The horizontal arrangement of cells in the matrix is termed as a row. Row

heading may r epresent the source or origins or plants from where goods

are manufactured and ready for transportation. It is related to the supply

function.

3 Column

The vertical arrangement of cells in the matrix is termed as a column. The

column heading may represent the destination center to which goods are

ready for transportation. It is related to the demand function.

4 Source

Source is the origin or plant from where goods are manufactured and

ready for transportation. Generally different sources are available in a

transportation model.

5 Destination

Destination is the final place where goods are required to be transported.

Transportation models with different destinations are available. Due to

availability of different sources and destinations with different unit co sts

of transportation, a transportation model is designed.

2.3 SOLUTION OF TRANSPORTATION MODEL

The solution of transportation model is designed to minimize the total cost

of transportation and to transit the goods from source to destination with

minimum c ost.

The solution of a transportation model has following steps :

a. Formulate the transportation model in matrix form

b. Obtain an initial feasible solution

c. Perform optimally test.

d. Find the transportation solution (after iteration if available)

Steps of soluti ons of transportation models are described in depth as

follows :

a. Formulate the transportation model in matrix form

The o bjective function of transportation problems is to minimize

transportation cost and the constraints are demands from the destination

and supply from the sources and hence transportation problem is similar to

that of linear programming problems. The formulation of transportation

model requires objective function as total transportation cost to be

minimi zed and demand and supply as constrain ts. Key decision is overall munotes.in

## Page 26

26

Operation Research minimization of transportation cost. For example, the daily supplies of

milk from different sources to the different destinations having milk

demand are matched with transportation models. The total transportation

cost can be mi nimized using the transportation model.

b. Obtain an initial feasible solution

An initial feasible solution is the first solution to the transportation

problem. The transportation quantities and routes are decided at an initial

stage.

This solution may be ob tained using different methods such as

i. North West Corner Method

ii. Row Minima Method

iii. Column Minima Method

iv. Least Cost Method

v. Vogels’ Approximation Method

c. Perform optimality test.

The initial feasible solution is tested for the optimality using the condition

as when the number of occupied cells is equal to the sum of number of

rows and number of columns -1.

a. Condition A

When the opposite condition is satisfied then the given initial feasible

solution is optimal and this is the final solution where improvement for

minimizing total transportation cost is not possible

b. Condition B

When the opposite condition is not satisfied then the given initial feasible

solution is not optimal and this is not the final solution where

improvement for minimizing total transportati on cost is possible.

c. Find the transportation solution (after iteration if available)

The final minimized transportation solution (after iteration if available) is

computed and this gives the most possible minimum total transportation

cost subject to the av ailability of supply and demand constraints from the

supply and demand respectively.

2.4 METHODS OF OBTAINING AN INITIAL FEASIBLE

SOLUTION

An initial feasible solution is the first solution to the transportation

problem. The transportation quantities and r outes are decided at an initial

stage.

This solution may be obtained using different methods such as :

2.4.1 NORTH WEST CORNER METHOD

North West Corner Method is the simple and easy method to compute

initial feasible solution. This method considers neithe r the cost of

transportation nor the path of transportation. North West Corner is the munotes.in

## Page 27

27

Transportation upper left corner of the matrix used for transportation. The process of

transportation of goods starts from the North West Corner of the matrix.

There are several steps of calculating initial feasible solution using North

West Corner Method as follows:

Step 1.

As North West Corner is the upper left corner of the matrix used for

transportation. The process of allocation of goods in transit starts from the

North West Cor ner of the matrix. Start the allocation of transportation

units from the North West Corner (the upper left corner of the matrix) cell

by considering minimum values from the corresponding first row and first

column i.e. Min (First Row, First Column).

Step 2.

a. If the values of First Row and First Column are equal then the same

units will be transferred from the first North West Corner of the matrix.

This condition is termed as degeneracy.

b. If the values of First Row and First Column are not equal then the

minimum units (i.e. Min.( First Row, First Column) will be transferred

from the first North West Corner of the matrix. The balance value of

either first row or first column is kept there and is to be considered for

next North West Corner . The reduced first r ow is considered as the North

West row for allocating transportation units to that cell.

Step 3.

Similar iteration is done for allocating transportation units until it reaches

to the extreme South East Corner of the transportation matrix. At the last

cell of the transportation matrix (extreme South East Corner), the

remaining total demand and total supply would be equal (degeneracy

condition). In this way balanced transportation problem will be solved and

unbalanced transportation problem will be solved by making it balanced

by adding dummy row or column making total demand=total supply.

Let us understand these steps by practical example.

1. Solve the following transportation problem using North West Corner

method.

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

Solution:

As Total Supply= Total Demand (125 units), this is balanced

transportation problem.

munotes.in

## Page 28

28

Operation Research Step 1. The North West Corner is Upper Left Corner called S1D1 cell.

Corresponding first row supply is 20 unit s and corresponding first column

demand is 40 Units. Hence allocation of maximum 20 units is possible

(Being the minimum of first row and first column) to the S1D1 cell.

After allocating these 20 u nits, supply side gets completely fulfilled and

hence ther e is no requirement of supply in the f irst row and the demand

side gets reduced from 40 units to 20 units (40 -20=20) hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 (20) 2 1 20, 0

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40, 20 30 55 125

Step 2. Now, the next North West Corner is Upper Left Corner called

S2D1 cell. Corresponding second row supply is 50 units and

corresponding first column demand is 20 Units. Hence allocation of

maximum 20 units is possible (Being the mini mum of second row and

first column) to the S2D1 cell.

After allocating these 20 u nits, demand side gets completely fulfilled and

hence there is no requirement of dema nd in the first column and the

supply side gets reduced from 50 units to 30 units (50 -20=30) hence the

reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 (20) 2 1 20, 0

S2 2 (20) 4 1 50, 30

S3 3 5 2 30

S4 4 6 7 25

Demand 40, 20 30 55 125

Step 3. Now, the next North West Corner is Upper Left Corner called

S2D2 cell. Corre sponding second row supply is 30 units and

corresponding second column demand is 30 Units. Hence allocation of

maximum 30 units is possible (Being the minimum of second row and

second column) to the S2D2 cell. munotes.in

## Page 29

29

Transportation

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of deman d in the second column and the

supply side gets fulfilled and hence the reduced transportation matrix

becomes

D1 D2 D3 Supply

S1 3 (20) 2 1 20, 0

S2 2 (20) 4 (30) 1 50, 30

S3 3 5 2 30

S4 4 6 7 25

Demand 40, 20 30 55 125

Step 4. Now, the next North West Corner is Upper Left Corner called

S3D3 cell. Corresponding third row supply is 30 units and corresponding

third column demand is 55 Units. Hence allocation of maximum 30 un its

is possible (Being the minimum of third row and third column) to the

S3D3 cell.

After allocating these 30 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the third row and the demand

side gets reduced from 5 5 to 25 units (55 -30=25) and hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 (20) 2 1 20, 0

S2 2 (20) 4 (30) 1 50, 30

S3 3 5 2 (30) 30

S4 4 6 7 25

Demand 40, 20 30 55, 25 125

Step 5 . Now, the next North West Corner is Upper Left Corner called

S4D3 cell. Corresponding fourth row supply is 25 units and corresponding

third column demand is 25 Units. Hence allocation of maximum 25 units

is possible (Being the minimum of forth row and third column) to the

S4D3 cell.

After allocating these 25 units, supply side gets completely fulfilled and

hence there is no requirement of supply in the fourth row and the demand munotes.in

## Page 30

30

Operation Research side gets completed fulfilled and hence there is no requirement of demand

in the fourth row and hence the reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 (20) 2 1 20, 0

S2 2 (20) 4 (30) 1 50, 30

S3 3 5 2 (30) 30

S4 4 6 7 (25) 25

Demand 40, 20 30 55, 25 125

Step 6 . Allocation of Transportation Units.

Total Transportation Cost = 3 (20) + 2 (20) + 4 (30) + 2 (30) + 7(25)

= 60+40+120+60+175

= 455.

Hence , Total Transportation Cost is Rs.455 using North West Corner

Method.

2. Solve the following transportation problem using North West Corner

method.

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

Solution:

As Total Supply = Total Demand (180 units), this is balanced

transportation problem.

Step 1. The North West Corner is Upper Left Corner called S1D1 cell.

Correspo nding first row supply is 50 units and corresponding first column

demand is 30 Units. Hence allocation of maximum 30 units is possible

(Being the minimum of first row and first column) to the S1D1 cell.

After allocating these 30 u nits, demand side gets co mpletely fulfilled and

hence there is no requirement of demand in the first column and the

supply side gets reduced from 50 units to 20 units (50 -30=20) hence the

reduced transportation matrix becomes

munotes.in

## Page 31

31

Transportation

D1 D2 D3 D4 Supply

S1 20 (30) 30 40 30 50, 20

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

Step 2. The North West Corner is Upper Left Corner called S1D2 cell.

Corresponding first row supply is 20 units and corresponding second

column demand is 50 Units. Hence allocation of maximum 20 units is

possible (Being the minimum of first row and second column) to the S1D2

cell.

After allocating these 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 50 units to 30 units (50 -20=30) hence the reduced

transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 (30) 30 (20) 40 30 50, 20

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50, 30 30 70 180

Step 3. The North West Corner is Upper Left Corner called S2D 2 cell.

Corresponding second row supply is 60 units and corresponding second

column demand is 30 Units. Hence allocation of maximum 30 units is

possible (Being the minimum of second row and second column) to the

S2D2 cell.

After allocatin g these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the second column and the

supply side gets reduced from 60 units to 30 units (60 -30=30) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 (30) 30 (20) 40 30 50, 20

S2 10 20 (30) 30 10 60, 30

S3 20 40 60 10 70

Demand 30 50, 30 30 70 180 munotes.in

## Page 32

32

Operation Research

Step 4. The North West Corner is Upper Left Corner called S2D3 cell.

Corresponding second row supply is 30 units and corresponding third

column demand is 30 Units. Hence allocation of maximum 30 units is

possible (Being the minimum of second row and second column) to the

S2D2 cell.

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of d emand in the third column and the

supply side gets completed fulfilled and hence there is no requireme nt of

supply in the second row hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20

(30) 30

(30) 10 60, 30

S3 20 40 60 10 70

Demand 30 50, 30 30 70 180

Step 5. The North West Corner is Upper Left Corner called S3D4 cell.

Corresponding third row supply is 770 units and corresponding fourth

column demand is 70 Units. Hence allocation of ma ximum 70 units is

possible (Being the equal units) to the S3D4 cell.

After allocating these 70 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the fourth column and the

supply side gets completed fulfilled and h ence there is no requirem ent of

supply in the third row hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20

(30) 30

(30) 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50, 30 30 70 180

Step 6: Computation of Total Transportation Cost munotes.in

## Page 33

33

Transportation Total transportation cost can be calculated by summing the multiplication

of unit cost of transportation with transportation units of occupied cells as

follows

Total Transportation Cost = 20(30) +30(20)+20 (30)+30(30)+10(70)

= 600+600+600+900+700

= 3400

Total Transportation Cost using NWCM is Rs. 3400

3. Solve the following transportation problem using North West

Corner method.

D1 D2 D3 D4 Supply

S1 40 50 60 50 50

S2 30 40 50 30 60

S3 40 60 80 30 70

Demand 30 50 30 70 180

Solution:

As Total Supply= Total Demand (180 units), this is balanced

transportation problem.

Step 1. The North West Corner is Upper Left Corner called S1D1 cell.

Corresponding first row supply is 50 units and correspond ing first column

demand is 30 Units. Hence allocation of maximum 30 units is possible

(Being the minimum of first row and first column) to the S1D1 cell.

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirem ent of demand in the first column and the

supply side gets reduced from 50 units to 20 units (50 -30=20) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 40 (30) 50 60 50 50, 20

S2 30 40 50 30 60

S3 40 60 80 30 70

Demand 30 50 30 70 180

Step 2. The North West Corner is Upper Left Corner called S1D2 cell.

Corresponding first row supply is 20 units and corresponding second

column demand is 50 Units. Hence allocation of maximum 20 units is munotes.in

## Page 34

34

Operation Research possible (Being the minimum of first row and second column) to the S1D2

cell.

After allocating these 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 50 units to 30 units (50 -20=30) hence the reduc ed

transportation matrix becomes

D1 D2 D3 D4 Supply

S1 40 (30) 50 (20) 60 50 50, 20

S2 30 40 50 30 60

S3 40 60 80 30 70

Demand 30 50, 30 30 70 180

Step 3. The North West Corner is Upper Left Corner called S2D2 cell.

Corresponding second row su pply is 60 units and corresponding second

column demand is 30 Units. Hence allocation of maximum 30 units is

possible (Being the minimum of second row and second column) to the

S2D2 cell.

After allocating these 30 u nits, demand side gets completely fulfil led and

hence there is no requirement of demand in the second column and the

supply side gets reduced from 60 units to 30 units (60 -30=30) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 40 (30) 50 (20) 60 50 50, 20

S2 30 40 (30) 50 30 60, 30

S3 40 60 80 30 70

Demand 30 50, 30 30 70 180

Step 4 . The North West Corner is Upper Left Corner called S2D3 cell.

Corresponding second row supply is 30 units and corresponding third

column demand is 30 Units. Hence allocation of max imum 30 units is

possible (Being the minimum of second row and second column) to the

S2D2 cell.

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the third column and the

supply side gets completed fulfilled and hence there is no requirement of

supply in the second row hence the reduced transportation matrix becomes munotes.in

## Page 35

35

Transportation D1 D2 D3 D4 Supply

S1 40

(30) 50

(20) 60 50 50, 20

S2 30 40

(30) 50

(30) 30 60, 30

S3 40 60 80 30 70

Demand 30 50, 30 30 70 180

Step 5. The North West Corner is Upper Left Corner called S3D4 cell.

Corresponding third row supply is 770 units and corresponding fourth

column demand is 70 Units. Hence allocation of maximum 70 units is

possible (Being the equal units) to the S3D4 cell.

After allocating these 70 units, demand s ide gets completely fulfilled and

hence there is no requirement of demand in the fourth column and the

supply side gets completed fulfilled and hence there is no requirem ent of

supply in the third row hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 40

(30) 50

(20) 60 50 50, 20

S2 30 40

(30) 50

(30) 30 60, 30

S3 40 60 80 30

(70) 70

Demand 30 50, 30 30 70 180

Step 6. Computation of Total Transportation Cost

Total transportation cost can be calculated by summing the multiplication

of unit cost of transportation with transportation units of occupied cells as

follows

Total Transportation Cost =

40(30)+50(20)+40(30)+50(30)+30(70)

= 1200+1000+1200+1500+2100

= 7000

Total Transportation Cost using NWCM is Rs. 7000

2.4.2 ROW MINIMA METHOD

Row Minima Method is the simple and easy method to compute initial

feasible solution. This method considers the cost of transportation and the

paths of transportation b oth. Row Minima is the considering minimum munotes.in

## Page 36

36

Operation Research value in the given row in sequence from Row 1 onwards used for

transportation. The process of allocation of goods in transit starts from the

first row by considering the minimum value in the first row and similar

calculations are carried forward.

There are several steps of calculating initial feasible solution using Row

Minima Method as follows:

Step 1. Row Minima is the considering minimum value in the given row

in sequence from Row 1 onwards used for transport ation. The process of

allocation of goods in transit starts from the first row by considering the

minimum value in the first row and similar calculations are carried

forward. Start the allocation of transportation units from the first row by

considering mi nimum value from the corresponding first row.

Step 2. After allocation of transportation units to the cell having

minimum value in the first row then if first row transportation units are

remaining then corresponding allocation of transportation units to the next

smaller transportation cost of first row can be done considering the

demand and supply side of transportation problem.

Step 3. Similar iteration is done for allocating transportation units until it

reaches to last row with complete allocation o f transportation units

matching demand and supply side.

Let us understand these steps by practical example.

4. Solve the following transportation problem using Row Minima

Method.

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

Solution:

As Total Supply= Total Demand (125 units), this is balanced

transportation problem.

Step 1. The First row in the transportation matrix is S1. Corresponding

minimum cell value representing unit transportation cost is S1D3 in the

first row. The allocation of transportation unit will be done firstly in the

cell S1D3 by considering corresponding demand and supply for that cell. munotes.in

## Page 37

37

Transportation The supply is of 20 units and demand is of 55 units. Minimum of these

two values is 20 and hence the allocatio n of 20 units can be done in this

cell as below .

After allocating these 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 55 units to 35 units (55 -20=35) hen ce the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40, 30 55, 35 125

There is no other cell remaining in the first row.

Step 2. The Second row in the transportation matri x is S2. Corresponding

minimum cell value representing unit transportation cost is S2D3 in the

second row. The allocation of transportation unit will be done firstly in the

cell S2D3 by considering corresponding demand and supply for that cell.

The supply is of 50 units and demand is of 35 units. Minimum of these

two values is 35 and hence the allocation of 35 units can be done in this

cell as below .

After allocating these 35 u nits, demand side gets completely fulfilled and

hence there is no requirement o f dema nd in the third column and the

supply side gets reduced from 50 units to 15 units (50 -35=15) hence the

reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 4 1 (35) 50, 15

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55, 35 125

munotes.in

## Page 38

38

Operation Research There is no other cell remaining in the third column.

Step 3. The reduced second row S2 is remaining in the transportation

matrix. Corresponding minimum cell value representing unit

transportation cost is S2D1 in the second row. The allocation of

transportation unit will be done now in the cell S2D1 by considering

corresponding demand and supply for that cell.

The supply is of 15 units and demand is of 40 units. Minimum of these

two values is 15 and hence the allocation of 15 units can be done in this

cell as below .

After allocating these 15 units, supply side g ets completely fulfilled and

hence there is no requirement of su pply in the second row and the demand

side gets reduced from 40 units to 25 units (40 -15=25) hence the reduced

transportat ion matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 (15) 4 1 (35) 50, 15

S3 3 5 2 30

S4 4 6 7 25

Demand 40, 25 30 55, 35 125

There is no other cell remaining in the second row.

Step 4. The next row is third row S3 in the transport ation matrix.

Corresponding minimum cell value representing unit transportation cost is

S3D1 in the third row. The allocation of transportation unit will be done

now in the cell S3D1 by considering corresponding demand and supply

for that cell.

The supply is of 30 units and demand is of 25 units. Minimum of these

two values is 25 and hence the allocation of 25 units can be done in this

cell as below .

After allocating these 25 u nits, demand side gets completely fulfilled and

hence there is no requirement o f demand in the first column and the

supply side gets reduced from 30 units to 5 units (30 -25=5) hence the

reduced transportation matrix becomes

munotes.in

## Page 39

39

Transportation D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 (15) 4 1 (35) 50, 15

S3 3 (25) 5 2 30, 5

S4 4 6 7 25

Demand 40, 25 30 55, 35 125

There is no other cell remaining in the first column.

Step 5. The next row is again reduced third row S3 in the transportation

matrix. Corresponding minimum cell value representing unit

transportation cost is S3D2 in the th ird row. The allocation of

transportation unit will be done now in the cell S3D2 by considering

corresponding demand and supply for that cell.

The supply is of 5 units and demand is of 30 units. Minimum of these two

values is 5 and hence the allocation of 5 units can be done in this cell as

below .

After allocating these 5 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the third row and the demand

side gets reduced from 30 units to 25 units (30 -5=25) hence the r educed

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 (15) 4 1 (35) 50, 15

S3 3 (25) 5 (5) 2 30, 5

S4 4 6 7 25

Demand 40, 25 30, 25 55, 35 125

There is no other cell remaining in the third row.

Step 6. The nex t row is reduced fourth row S4 in the transportation

matrix. Corresponding minimum cell value representing unit

transportation cost is S4D2 in the fourth row. The allocation of

transportation unit will be done now in the cell S4D2 by considering

correspond ing demand and supply for that cell.

munotes.in

## Page 40

40

Operation Research The supply is of 25 units and demand is of 25 units. Minimum of these

two values is 25 and hence the allocation of 25 units can be done in this

cell as below .

After allocating these 25 u nits, supply side gets complete ly fulfilled and

hence there is no requirement of supply in the fourth row and the demand

side gets completed fulfilled and hence there is no requirement of demand

in the second column hence the reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (20) 20, 0

S2 2 (15) 4 1 (35) 50, 15

S3 3 (25) 5 (5) 2 30, 5

S4 4 6 (25) 7 25

Demand 40, 25 30, 25 55, 35 125

There is no other cell remaining in the fourth row.

Step 7 . Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 1 (20)+ 2 (15)+ 1 (35)+ 3 (25)+ 5(5)+ 6 (25)

= 20+30+35+75+25+ 150

= 335.

Hence , Total Transportation Cost is Rs.335 using Row Minima Method.

5. Solve the following transportation problem using Row Minima

method.

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

Solution:

As Total Supply= Total Demand (180 units), this is balanced

transportation problem.

Step 1. The First row in the transportation matrix is S1. Cor responding

minimum cell value representing unit transportation cost is S1D1 in the munotes.in

## Page 41

41

Transportation first row. The allocation of transportation unit will be done firstly in the

cell S1D1 by considering corresponding demand and supply for that cell.

The supply is of 50 unit s and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 units, demand side gets complete ly fulfilled and

hence there is no requirement of dem and in th e first column and the

supply side gets reduced from 50 units to 20 units (50 -30=20) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 (30) 30 40 30 50, 20

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

There is no other cell remaining in the first column.

Step 2. The reduced first row in the transportation matrix is S1.

Corresponding minimum cell value representing unit transportation cost is

S1D2 in the first row. The allocation of transportation unit will be done

firstly in the cell S1D2 by considering corresponding demand and supply

for that cell.

The supply is of 20 units and demand is of 50 units. Minimum of these

two values is 20 and hence the allocation of 20 units can be done in this

cell as below .

After allocating these 20 units, supply side gets complete ly fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 50 units to 30 units (50 -20=30) hence the reduced

transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 (30) 30 (20) 40 30 50, 20

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50,

(30) 30 70 180

munotes.in

## Page 42

42

Operation Research There is no other cell remaining in the first row.

Step 3. The next second row in the transportation matrix is S2.

Corresponding minimu m cell value representing unit transportation cost is

S2D4 in the second row. The allocation of transportation unit will be done

firstly in the cell S2D4 by considering corresponding demand and supply

for that cell.

The supply is of 60 units and demand is of 70 units. Minimum of these

two values is 60 and hence the allocation of 60 units can be done in this

cell as below .

After allocating these 60 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the second row an d the demand

side gets reduced from 70 units to 10 units (70 -60=10) hence the reduced

transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20 30 10

(60) 60

S3 20 40 60 10 70

Demand 30 50,

(30) 30 70, 10 180

There is no other cell remaining in the second row.

Step 4. The next third row in the transportation matrix is S3.

Corresponding minimum cell value representing unit transportation cost is

S3D4 in the third row. The allocation of transportation unit will b e done

firstly in the cell S3D4 by considering corresponding demand and supply

for that cell.

The supply is of 70 units and demand is of 10 units. Minimum of these

two values is 10 and hence the allocation of 10 units can be done in this

cell as below

After allocating these 10 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the fourth column and the

supply side gets reduced from 70 units to 60 units (70 -10=60) hence the

reduced transportation matrix becomes

munotes.in

## Page 43

43

Transportation D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20 30 10

(60) 60

S3 20 40 60 10

(10) 70, 60

Demand 30 50, 30 30 70, 10 180

There is no other cell remaining in the fourth column.

Step 5. The reduced third row in the transportation ma trix is S3.

Corresponding minimum cell value representing unit transportation cost is

S3D2 in the third row. The allocation of transportation unit will be done

firstly in the cell S3D2 by considering corresponding demand and supply

for that cell.

The supp ly is of 60 units and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below

After allocating these 30 units, demand side gets complete ly fulfilled and

hence there is no requirement of demand in the second column and the

supply side gets reduced from 60 units to 30 units (60 -30=30) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20 30 10

(60) 60

S3 20 40

(30) 60 10

(10) 70, 60,

30

Demand 30 50, 30 30 70, 10 180

There is no other cell remaining in the second column.

Step 6. The reduced third row in the transportation matrix is S3.

Corresponding minimum cell value representing unit transportation cost is

S3D3 in the third row. The allocation of transportation unit will be done

firstly in the cell S3D3 by considering corresponding demand and supply

for that cell. munotes.in

## Page 44

44

Operation Research The supply is of 30 units and demand is of 30 units. Minimum of these

two values is 30 and hence the a llocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the third column and the

supply side completed fulfilled and hence there is no r equirement of

supply in the third row hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20

(30) 30

(20) 40 30 50, 20

S2 10 20 30 10

(60) 60

S3 20 40

(30) 60

(30) 10

(10) 70, 60,

30

Demand 30 50, 30 30 70, 10 180

There is no other cell remaining in the third column and third row also.

Step 7. Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 20(30)+30(20)+ 10(60)+ 40(30)+ 60(30)+ 10(10)

= 600+600+600+1200+1800+ 100

= 490 0.

Hence , Total Transportation Cost is Rs.4900 using Row Minima Method.

2.4.3 COLUMN MINIMA METHOD

Column Minima Method is the simple and easy method to compute initial

feasible solution. This method considers the cost of transportation and the

paths o f transportation both. Column Minima is the considering minimum

value in the given column in sequence from Column 1 onwards used for

transportation. The process of allocation of goods in transit starts from the

first column by considering the minimum valu e in the column row and

similar calculations are carried forward.

There are several steps of calculating initial feasible solution using

Column Minima Method as follows:

Step 1. Column Minima is considering the minimum value in the given

column in sequen ce from column 1 onwards used for transportation. The

process of allocation of goods in transit starts from the first column by

considering the minimum value in the first column and similar

calculations are carried forward. Start the allocation of transpor tation units munotes.in

## Page 45

45

Transportation from the first column by considering minimum value from the

corresponding first column.

Step 2. After allocation of transportation units to the cell having

minimum value in the first column then if first column transportation units

are remai ning then corresponding allocation of transportation units to the

next smaller transportation cost of first column can be done considering

the demand and supply side of transportation problem.

Step 3. Similar iteration is done for allocating transportati on units until it

reaches to last column with complete allocation of transportation units

matching demand and supply side.

Let us understand these steps by practical example.

6. Solve the following transportation problem using column Minima

Method.

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

Solution:

As Total Supply= Total Demand (125 units), this is balanced

transportation problem.

Step 1. The First column in the transportation matrix is D1.

Corresponding minimum cell value representing unit transportation cost is

S2D1 in the first column. The allocation of transportation unit will be

done firstly in the cell S2D1 by considering corresponding demand and

supply for that cell.

The supply is of 50 units and d emand is of 40 units. Minimum of these

two values is 40 and hence the allocation of 40 units can be done in this

cell as below .

After allocating these 40 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the first column and the

supply side gets reduced from 50 units to 10 units (50 -40=10) hence the

reduced transportation matrix becomes

munotes.in

## Page 46

46

Operation Research D1 D2 D3 Supply

S1 3 2 1 20

S2 2 (40) 4 1 50, 10

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

There is no other cell remaining in the first column.

Step 2. The Second column in the transportation matrix is D2.

Corresponding minimum cell value representing unit transportation cost is

S1D2 in the second column. The allocation of transportation unit will be

done firstly in the cell S1D2 by considering corresponding demand and

supply for that cell.

The supply is of 20 units and demand is of 30 units. Minimum of these

two values is 20 and hence the allocation of 20 units can be done in this

cell as below .

After allocating t hese 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 30 units to 10 units (30 -20=10) hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (20) 1 20

S2 2 (40) 4 1 50, 10

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30, 10 55 125

There is no other cell remaining in the first row.

Step 3. The reduced second columnD2 is remaining in the transportation

matrix. Corresponding minimum cell val ue representing unit

transportation cost is S2D2 in the second column. The allocation of

transportation unit will be done now in the cell S2D2 by considering

corresponding demand and supply for that cell.

munotes.in

## Page 47

47

Transportation The supply is of 10 units and demand is of 10 unit s. Minimum of these

two values is 10 and hence the allocation of 10 units can be done in this

cell as below .

After allocating these 10 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the second row and the deman d

side gets completed fulfilled and hence there is no requirement of demand

in the second column, hence the reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (20) 1 20

S2 2 (40) 4 (10) 1 50, 10

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30, 10 55 125

There is no other cell remaining in the second row.

There is no other cell remaining in the second column.

Step 4. The next column is third column S3 in the transportation matrix.

Corresponding minimum cell value representing unit transp ortation cost is

S3D3 in the third column. The allocation of transportation unit will be

done now in the cell S3D3 by considering corresponding demand and

supply for that cell.

The supply is of 30 units and demand is of 55 units. Minimum of these

two valu es is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the third row and the demand

side gets reduced from 55 u nits to 25 units (55 -30=25) hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (20) 1 20

S2 2 (40) 4 (10) 1 50, 10

S3 3 5 2 (30) 30

S4 4 6 7 25

Demand 40 30, 10 55, 25 125 munotes.in

## Page 48

48

Operation Research There is no other cell remaining in the thi rd row.

Step 5. The next column is again reduced third columnD3 in the

transportation matrix. Corresponding minimum cell value representing

unit transportation cost is S4D3 in the third column. The allocation of

transportation unit will be done now in the cell S4D3 by considering

corresponding demand and supply for that cell.

The supply is of 25 units and demand is of 25 units. Minimum of these

two values is 25 and hence the allocation of 25 units can be done in this

cell as below .

After allocating these 25 units, supply side gets completely fulfilled and

hence there is no requirement of supply in the third row and the demand

side gets completed fulfilled and hence there is no requirement of demand

in the third column, hence the reduced transportation mat rix becomes

D1 D2 D3 Supply

S1 3 2 (20) 1 20

S2 2 (40) 4 (10) 1 50, 10

S3 3 5 2 (30) 30

S4 4 6 7 (25) 25

Demand 40 30, 10 55, 25 125

There is no other cell remaining in the third row.

Step 6. Allocation of Transportation Units to t he occupied cells

Total Transportation Cost = 2(40)+2(20)+ 4(10)+ 20(30)+ 7(25)

= 80+40+40+60+175

= 395.

Hence , Total Transportation Cost is Rs.395 using Column Minima

Method.

7. Solve the following transportation problem using Column Minima

method.

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

munotes.in

## Page 49

49

Transportation

Solution:

As Total Supply= Total Demand (180 units), this is balanced

transportation problem.

Step 1. The First column in the transportation mat rix is D1.

Corresponding minimum cell value representing unit transportation cost is

S2D1 in the first column. The allocation of transportation unit will be

done firstly in the cell S2D1 by considering corresponding demand and

supply for that cell.

The su pply is of 60 units and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requireme nt of demand in the first column and the

supply side gets reduced from 60 units to 30 units (60 -30=30) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 (30) 20 30 10 60, 30

S3 20 40 60 10 70

Demand 30 50 30 70 180

There is no other cell remaining in the first column.

Step 2. The second column in the transportation matrix is D2.

Corresponding minimum cell value representing unit transportation cost is

S2D2 in the second column. The allocation of transpor tation unit will be

done firstly in the cell S2D2 by considering corresponding demand and

supply for that cell.

The supply is of 30 units and demand is of 50 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the second row and the demand

side gets reduced from 50 units to 20 units (50 -30=20) hence the reduced

transportation mat rix becomes

munotes.in

## Page 50

50

Operation Research

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 (30) 20 (30) 30 10 60, 30

S3 20 40 60 10 70

Demand 30 50,

(20) 30 70 180

There is no other cell remaining in the first row.

Step 3. The reduced second column in the transportation mat rix is D2.

Corresponding minimum cell value representing unit transportation cost is

S1D2 in the second column. The allocation of transportation unit will be

done firstly in the cell S1D2 by considering corresponding demand and

supply for that cell.

The s upply is of 50 units and demand is of 20 units. Minimum of these

two values is 20 and hence the allocation of 20 units can be done in this

cell as below .

After allocating these 20 u nits, demand side gets completely fulfilled and

hence there is no requirem ent of demand in the second column and the

supply side gets reduced from 50 units to 30 units (50 -20=30) hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 30 (20) 40 30 50, 30

S2 10 (30) 20 (30) 30 10 60, 30

S3 20 40 60 10 70

Demand 30 50, 30 30 70 180

There is no other cell remaining in the second column.

Step 4. The next third column in the transportation matrix is D3.

Corresponding minimum cell value representing unit transportation cost is

S1D4 in the third column . The allocation of transportation unit will be

done firstly in the cell S1D4 by considering corresponding demand and

supply for that cell.

The supply is of 30 units and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below . munotes.in

## Page 51

51

Transportation

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the third column and the

supply side gets completed fulfilled and hence there is no requireme nt of

demand in the third column hence the reduced transportation matrix

becomes

D1 D2 D3 D4 Supply

S1 20 30

(20) 40

(30) 30 50, 30

S2 10

(30) 20

(30) 30 10 60, 30

S3 20 40 60 10 70

Demand 30 50, 30 30 70 180

There is no other cell remain ing in the third column.

Step 5. The fourth column in the transportation matrix is D4.

Corresponding minimum cell value representing unit transportation cost is

S3D4 in the fourth column. The allocation of transportation unit will be

done firstly in the c ell S3D4 by considering corresponding demand and

supply for that cell.

The supply is of 70 units and demand is of 70 units. Minimum of these

two values is 70 and hence the allocation of 70 units can be done in this

cell as below .

After allocating these 7 0 units, demand side gets completely fulfilled and

hence there is no requirement of demand in the fourth column and the

supply side gets completed fulfilled and he nce there is no requirement of

supply in the third row, hence the reduced transportation matr ix becomes

D1 D2 D3 D4 Supply

S1 20 30

(20) 40

(30) 30 50, 30

S2 10

(30) 20

(30) 30 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50, 30 30 70 180

munotes.in

## Page 52

52

Operation Research There is no other cell remaining in the fourth column and third row.

Step 6. Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 10(30)+30(20)+ 20(30)+ 40(30)+ 10(70)

= 300+600+600+1200+1700

= 4400.

Hence , Total Transportation Cost is Rs.4400 using Column Minima

Method.

2.4.4 LEAST COST METHOD

Leas t cost method is also known as matrix minima method because in this

method , minimum value in all rows and all columns are searched out and

corresponding allocation can be made in the transportation model.

Least Cost Method is the simple and easy method to compute initial

feasible solution. This method considers the cost of transportation and the

paths of transportation both. Matrix Minima is the considering minimum

value in the given row and column in sequence from Column 1 onwards

used for transportation . The process of allocation of goods in transit starts

from the anywhere in the matrix by considering the minimum value in the

column or row and similar calculations are carried forward.

There are several steps of calculating initial feasible solution usi ng Lest

Cost Method as follows:

Step 1. Matrix Minima is considering the minimum value in the given

column or row in sequence from c olumn 1 onwards or from row 1

onwards used for transportation. The process of allocation of goods in

transit starts from ei ther row or column by considering the minimum value

in the matrix and similar calculations are carried forward. Start the

allocation of transportation units from the row or column by considering

minimum value from the corresponding transportation matrix.

Step 2. After allocation of transportation units to the cell having

minimum value in the matrix then, find out the next minimum value in the

matrix considering the demand and supply side of transportation problem.

Step 3. Similar iteration is done for a llocating transportation units until it

reaches to cell of the matrix with complete allocation of transportation

units matching demand and supply side.

munotes.in

## Page 53

53

Transportation Let us understand these steps by practical example.

8. Solve the following transportation problem using L east Cost Method.

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

Solution:

As Total Supply= Total Demand (125 units), this is balanced

transportation problem.

Step 1. The minimum value in the transportation mat rix is 1 available at

cell S1D3 and S2D3. Now there are two possibilities of allocating

transportation units as follows :

i. If we consider, the minimum value in the transportation matrix is 1

available at cell S1D3 then maximum 20 units can be transported fr om S1

to D3.

ii. If we consider, the minimum value in the transportation matrix is 1

available at cell S2D3 then maximum 50 units can be transported from S2

to D3.

Here , the maximum units should be transported so as to minimize the total

transportation cost.

Hence , the second possibility is better choice.

The minimum value in the transportation matrix is 1 available at cell

S2D3 then maximum 50 units can be transported from S2 to D3.

The allocation of transportation unit will be done firstly in the cell S2 D3

by considering corresponding demand and supply for that cell.

The supply is of 50 units and demand is of 55 units. Minimum of these

two values is 50 and hence the allocation of 50 units can be done in this

cell as below .

After allocating these 50 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the second row and the demand

side gets reduced from 55 units to 5 units (55 -50=5). Hence the reduced

transportation matrix becomes munotes.in

## Page 54

54

Operation Research

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 (50) 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55, 5 125

There is no other cell remaining in the second row.

Step 2. The minimum value in the transportation matrix is 1 available at

cell S1D3 then maximum 20 units can be transported from S1 t o D3.

The allocation of transportation unit will be done firstly in the cell S1D3

by considering corresponding demand and supply for that cell.

The supply is of 20 units and demand is of 5 units. Minimum of these two

values is 5 and hence the allocation of 5 units can be done in this cell as

below .

After allocating these 5 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the third column and the

supply side gets reduced from 55 units to 5 units (55 -50=5). Hence the

reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 1 (5) 20, 15

S2 2 4 1 (50) 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55, 5 125

There is no other cell remaining in the third column.

Step 3. The minimum value in the transportat ion matrix is 2 available at

cell S1D2 then 15 units can be transported from S1 to D2.

The allocation of transportation unit will be done firstly in the cell S1D2

by considering corresponding demand and supply for that cell.

munotes.in

## Page 55

55

Transportation The supply is of 15 units and demand is of 30 units. Minimum of these

two values is 15 and hence the allocation of 15 units can be done in this

cell as below .

After allocating these 15 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the fir st row and the demand

side gets reduced from 30 units to 15 units (30 -15=15). Hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (15) 1 (5) 20, 15

S2 2 4 1 (50) 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30, 15 55, 5 125

Ther e is no other cell remaining in the third column.

Step 4. The minimum value in the transportation matrix is 3 available at

cell S3D1 then 30 units can be transported from S3 to D1.

The allocation of transportation unit will be done firstly in the cell S 3D1

by considering corresponding demand and supply for that cell.

The supply is of 30 units and demand is of 40 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the third row and the demand

side gets reduced from 40 units to 10 units (40 -30=10). Hence the reduced

transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (15) 1 (5) 20, 15

S2 2 4 1 (50) 50

S3 3 (30) 5 2 30

S4 4 6 7 25

Demand 40, 10 30, 15 55, 5 125

munotes.in

## Page 56

56

Operation Research There is no other cell remaining in the third row.

Step 5. The minimum value in the transportation matrix is 4 available at

cell S4D1 then 30 units can be transported from S4 to D1.

The allocation of transportation unit will be done firstly in the cell S4D1

by considering corresponding demand and supply for that cell.

The supply is of 25 units and demand is of 10 units. Minimum of these

two values is 10 and hence the allocation of 10 units can be done in this

cell as below .

After allocating these 10 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the first column and the

supply side gets reduced from 25 units t o 15 units (25 -10=15). Hence the

reduced transportation matrix becomes

D1 D2 D3 Supply

S1 3 2 (15) 1 (5) 20, 15

S2 2 4 1 (50) 50

S3 3 (30) 5 2 30

S4 4 (10) 6 7 25, 15

Demand 40, 10 30, 15 55, 5 125

There is no other cell remaining in th e first column.

Step 6. The minimum value in the transportation matrix is 6 available at

cell S4D2 then 15 units can be transported from S4 to D2.

The allocation of transportation unit will be done firstly in the cell S4D2

by considering corresponding demand and supply for that cell.

The supply is of 15 units and demand is of 15 units. Minimum of these

two values is 15 and hence the allocation of 15 units can be done in this

cell as below .

After allocating these 15 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the second column and the

supply side gets completed fulfilled and hence there is no requirement of

supply in the fourth row. Hence the reduced transportation matrix

becomes

munotes.in

## Page 57

57

Transportation D1 D2 D3 Supply

S1 3 2 (15) 1 (5) 20, 15

S2 2 4 1 (50) 50

S3 3 (30) 5 2 30

S4 4 (10) 6 (15) 7 25, 15

Demand 40, 10 30, 15 55, 5 125

Step 7 . Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 2(15)+1(5)+ 1(50)+ 3(30)+ 4(10)+ 6 (15)

= 30+5+50+90+40+90

= 305.

Hence , Total Transportation Cost is Rs.305 using Least Cost Method.

9. Solve the following transportation problem using Matrix Minima

method.

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 20 30 10 60

S3 20 40 60 10 70

Demand 30 50 30 70 180

Solution:

As Total Supply= Total Demand (180 units), this is balanced

transportation problem.

Step 1. The minimum value in the transportation matrix is 10 available at

cell S2D1; S2D4 and S3D4. Now there are three possibil ities of allocating

transportation units as follows

a. If we consider, the minimum value in the transportation matrix is 10

available at cell S2D1 then maximum 30 units can be transported

from S2 to D1.

b. If we consider, the minimum value in the transportatio n matrix is 10

available at cell S2D4 then maximum 60 units can be transported

from S2 to D 4.

munotes.in

## Page 58

58

Operation Research c. If we consider, the minimum value in the transportation matrix is 10

available at cell S 3D4 then maximum 70 units can be transported

from S 3 to D4.

Here the max imum units should be transported so as to minimize the total

transportation cost.

Hence , the third possibility is better choice.

The minimum value in the transportation matrix is 1 available at cell

S3D4 then maximum 70 units can be transported from S3 t o D4.

The allocation of transportation unit will be done firstly in the cell S3D4

by considering corresponding demand and supply for that cell.

The supply is of 70 units and demand is of 70 units. Minimum of these

two values is 70 and hence the allocation of 70 units can be done in this

cell as below

After allocating these 70 units, supply and demand both side gets

completed fulfilled and hence there is no requirement of demand and

supply. Hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supp ly

S1 20 30 40 30 50

S2 10 20 30 10 60

S3 20 40 60 10 (70) 70

Demand 30 50 30 70 180

There is no other cell remaining in the third row and fourth column.

Step 2. The minimum value in the transportation matrix is 10 available at

cell S2D1 then max imum 30 units can be transported from S2 to D1.

The allocation of transportation unit will be done firstly in the cell S2D1

by considering corresponding demand and supply for that cell.

The supply is of 60 units and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the first column and the

supply side gets reduce d from 60 units to 30 units (60 -30=30). Hence the

reduced transportation matrix becomes

munotes.in

## Page 59

59

Transportation D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10 (30) 20 30 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50 30 70 180

There is no other cell remaining in the third row and fourth column.

Step 3. The minimum value in the transportation matrix is 20 available at

cell S2D2 then maximum 30 units can be transported from S2 to D2.

The allocation of transportation unit will be done firstly in the cell S2D2

by considering corresponding demand and supply for that cell.

The supply is of 30 units and demand is of 50 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 u nits, supply side ge ts completely fulfilled and

hence there is no requirement of supply in the second row and the demand

side gets reduced from 50 units to 20 units (50 -30=20). Hence the reduced

transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 30 40 30 50

S2 10

(30) 20

(30) 30 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50, 20 30 70 180

There is no other cell remaining in the third row and fourth column.

Step 4. The minimum value in the transportation matrix is 30 available at

cell S1D2 then maximum 20 uni ts can be transported from S1 to D2.

The allocation of transportation unit will be done firstly in the cell S1D2

by considering corresponding demand and supply for that cell.

The supply is of 50 units and demand is of 20 units. Minimum of these

two value s is 20 and hence the allocation of 20 units can be done in this

cell as below .

munotes.in

## Page 60

60

Operation Research After allocating these 20 u nits, demand side gets completely fulfilled and

hence there is no requirement of demand in the second column and the

supply side gets reduced from 5 0 units to 20 units (50 -30=20). Hence the

reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 30

(20) 40 30 50, 30

S2 10

(30) 20

(30) 30 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50, 20 30 70 180

There is no other cell remaining in the third row and fourth column.

Step 5. The minimum value in the transportation matrix is 40 available at

cell S2D3 then maximum 30 units can be transported from S2 to D3.

The allocation of transportation unit will be done firstly in the cell S2D3

by considering corresponding demand and supply for that cell.

The supply is of 30 units and demand is of 30 units. Minimum of these

two values is 30 and hence the allocation of 30 units can be done in this

cell as below .

After allocating these 30 units, supply side and demand side both get

completed fulfilled and there is no requirement of demand and supply.

Hence the reduced transportation matrix becomes

D1 D2 D3 D4 Supply

S1 20 30

(20) 40

(30) 30 50, 30

S2 10

(30) 20

(30) 30 10 60, 30

S3 20 40 60 10

(70) 70

Demand 30 50, 20 30 70 180

There is no other cell remaining in the first row and third column.

Step 7. Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 30(20)+40(30)+ 10(30)+ 20(30)+ 10(70)

= 600+1200+300+600+700

= 3400. munotes.in

## Page 61

61

Transportation

Hence , Total Transportation Cost is Rs.3400 using Least Cost Method.

2.4.5 VOGELS’ APPROXIMATION METHOD

Vogels’ Approximation Method considers the highest penalty value for

making allocation of transportation units . Penalty is the difference

between two minimum cost values. The highest penalty value present in

either row or column will be considered as the row or column for making

allocation of transportation units.

The minimum cost value will be chosen from the se lected row or column

of the highest penalty value. The iteration of highest penalty values and

corresponding allocations of transportation values are done until and

unless all units are transported from the sources to the different

destinations.

Let us un derstand these steps by practical example.

10. Solve following transportation problem using Vogels’ Approximation

Method .

D1 D2 D3 Supply

S1 3 2 1 20

S2 2 4 1 50

S3 3 5 2 30

S4 4 6 7 25

Demand 40 30 55 125

Solution:

As Total Supply= Total Demand (125 units), this is balanced

transportation problem.

Step 1. The maximum penalty value in the transportation matrix is 2

available at cell S4 row and D2 column. Now there are two possibilities of

allocating transportation units as follows :

A. If we consider, th e maximum penalty value in the transportation

matrix is 2 available at S4 row then for minimum unit of transportation 4

(S4D1) maximum 25 units can be transported from S4 to D1.

B. If we consider, the maximum penalty value in the transportation

matrix is 2 a vailable at D2 column then then for minimum unit of

transportation 2, maximum 20 units can be transported from S1 to D2.

Here , the maximum units should be transported so as to minimize the total

transportation cost.

Hence , the first possibility is better choice. munotes.in

## Page 62

62

Operation Research The maximum penalty value in the transportation matrix is 2 available at

S4 row then for minimum unit of transportation 4 (S4D1) maximum 25

units can be transported from S4 to D1.

The allocation of transportation unit will be done firstly in the cell S4D1

by considering corresponding demand and supply for that cell.

The supply is of 25 units and demand is of 40 units. Minimum of these

two values is 25 and hence the allocation of 25 units can be done in this

cell as below .

After allocating these 25 units, supply side gets completely fulfilled and

hence there is no requirement of supply in the fourth row and the demand

side gets reduced from 40 units to 15 units (40 -25=15). Hence the reduced

transportation matrix becomes

D1 D2 D3 Supply Penalty1

S1 3 2 1 20 2-1=1

S2 2 4 1 50 2-1=1

S3 3 5 2 30 3-2=1

S4 4 (25) 6 7 25 6-4=2

Demand 40, 15 30 55 125

Penalty1 3-2=1 4-2=2 1-1=0

There is no other cell remaining in the first column.

Step 2. Repeat the process or steps

The maximum penalty va lue for second time in the transportation matrix

is 2 available at S4 row then for minimum unit of transportation 4 (S4D1)

maximum 25 units can be transported from S4 to D1.

The allocation of transportation unit will be done firstly in the cell S4D1

by co nsidering corresponding demand and supply for that cell.

The supply is of 25 units and demand is of 40 units. Minimum of these

two values is 25 and hence the allocation of 25 units can be done in this

cell as below .

After allocating these 25 u nits, suppl y side gets completely fulfilled and

hence there is no requirement of supply in the fourth row and the demand

side gets reduced from 40 units to 15 units (40 -25=15). Hence the reduced

transportation matrix becomes

munotes.in

## Page 63

63

Transportation D1 D2 D3 Supply Penalty1 Penalty2 S1 3 2 1 20 2-1=1 2-1=1

S2 2 4 1 50 2-1=1 2-1=1

S3 3 5 2 30 3-2=1 3-2=1

S4 4

(25) 6 7 25 6-4=2

Demand 40,

15 30 55 125

Penalty1 3-

2=1 4-

2=2 1-

1=0

Penalty2 3-

2=1 4-

2=2 1-

1=0

There is no other cell remaining in the fourth row.

Step 3. Repea t the process or steps

The maximum penalty value for second time in the transportation matrix

is 2 available at D2column then for minimum unit of transportation 2

(S1D2) maximum 2 0 units can be transported from S 1 to D2.

The allocation of transportation unit will be done firstly in the cell S1D2

by considering corresponding demand and supply for that cell.

The supply is of 20 units and demand is of 30 units. Minimum of these

two values is 20 and hence the allocation of 20 units can be done in this

cell as below .

After allocating these 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 300 units to 10 units (30 -20=10). Hence the

reduced transportation matrix b ecomes

D1 D2 D3 Supply Penalty1 Penalty2 S1 3 2

(20) 1 20 2-1=1 2-1=1

S2 2 4 1 50 2-1=1 2-1=1

S3 3 5 2 30 3-2=1 3-2=1

S4 4

(25) 6 7 25 6-4=2

Demand 40,

15 30,

10 55 125

Penalty1 3-

2=1 4-

2=2 1-

1=0

Penalty2 3-

2=1 4-

2=2 1-

1=0 munotes.in

## Page 64

64

Operation Research There i s no other cell remaining in the first row.

Step 4. Repeat the process or steps

The maximum penalty value for third time in the transportation matrix is 2

available at D2column then for minimum unit of transportation 2 (S1D2)

maximum 2 0 units can be tran sported from S 1 to D2.

The allocation of transportation unit will be done firstly in the cell S1D2

by considering corresponding demand and supply for that cell.

The supply is of 20 units and demand is of 30 units. Minimum of these

two values is 20 and he nce the allocation of 20 units can be done in this

cell as below .

After allocating these 20 u nits, supply side gets completely fulfilled and

hence there is no requirement of supply in the first row and the demand

side gets reduced from 300 units to 10 uni ts (30 -20=10). Hence the

reduced transportation matrix becomes

D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2

(20) 1 20 2-1=1 2-1=1

S2 2 4 1 50 2-1=1 2-1=1 2-1=1

S3 3 5 2 30 3-2=1 3-2=1 3-2=1

S4 4

(25) 6 7 25 6-4=2

Demand 40,

15 30,

10 55 125

Penalty1 3-

2=1 4-

2=2 1-

1=0

Penalty2 3-

2=1 4-

2=2 1-

1=0

Penalty3 3-

2=1 5-

4=1 2-

1=1

There is no other cell remaining in the first row.

The maximum penalty value for this time in the transportation matrix is 1

available at S2; S3 rows and D1; D2 and D3columns then for minimum

unit of transportation 1 (S2D3) maximum 50 units can be transported from

S2 to D3.

munotes.in

## Page 65

65

Transportation The allocation of transportation unit will be done firstly in the cell S2D3

by considering corresponding demand and supply fo r that cell.

The supply is of 50 units and demand is of 55 units. Minimum of these

two values is 50 and hence the allocation of 50 units can be done in this

cell as below .

After allocating these 50 units, supply side gets complete ly fulfilled and

hence t here is no requirement of supply in the second row and the demand

side gets reduced from 55 units to 5 units (55 -50=5). Hence the reduced

transportation matrix becomes

D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2

(20) 1 20 2-1=1 2-1=1

S2 2 4 1

(50) 50 2-1=1 2-1=1 2-1=1

S3 3 5 2 30 3-2=1 3-2=1 3-2=1

S4 4

(25) 6 7 25 6-4=2

Demand 40,

15 30,

10 55,

5 125

Penalty1 3-

2=1 4-

2=2 1-

1=0

Penalty2 3-

2=1 4-

2=2 1-

1=0

Penalty3 3-

2=1 5-

4=1 2-

1=1

There is no other cell remaining in the SECOND row.

Step 5. As single cells are remaining in the columns, direct allocation is

possible as follows

D1 D2 D3 Supply Penalty1 Penalty2 Penalty3 S1 3 2

(20) 1 20 2-1=1 2-1=1

S2 2 4 1

(50) 50 2-1=1 2-1=1 2-1=1

S3 3

(15) 5

(10) 2

(5) 30 3-2=1 3-2=1 3-2=1

S4 4

(25) 6 7 25 6-4=2 munotes.in

## Page 66

66

Operation Research Demand 40,

15 30,

10 55,

5 125

Penalty1 3-

2=1 4-

2=2 1-

1=0

Penalty2 3-

2=1 4-

2=2 1-

1=0

Penalty3 3-

2=1 5-

4=1 2-

1=1

Step 6 . Allocation of Transportation Units to the occupied cells

Total Transportation Cost = 2(20)+1(50)+ 3(15)+ 5(10)+ 2(5)+4 (25)

= 40+50+45+50+10+100

= 295.

Hence , Total Transportation Cost is Rs.295 using Vogels’ Approximation

Method.

2.5 SELF ASSESSMENT TEST

Q1. Solve following Multiple Choice Quest ions.

1. Transportation is a typical type of operation research technique

developed for ……… from the sources to the destination .

a. transportation of goods

b. assignment of job

c. transfer of employees

d. None of the above.

2. Transportation problem is a s pecial type of ……… which can be solved

by using different methods of transportation .

a. Operations Method

b. linear programming problem

c. Research model

d. Business model.

3. The vertical arrangement of cells in the matrix is termed as …..

a. row b. col umn

c. table d. none of the above.

munotes.in

## Page 67

67

Transportation 4. When total demand is equal to total supply then the transportation

problem is said to be …

a. Complete b. incomplete

c. balanced d. Unbalanced.

5. The basic feasible solution exists when …….

a. number of oc cupied cells are equal to number of rows and number of

columns minus one .

b. number of occupied cells are less than number of rows and number of

columns minus one .

c. number of occupied cells are greater than number of rows and number

of columns minus o ne.

d. number of occupied cells are either greater than or less than number of

rows and number of columns minus one .

6. The o bjective function of transportation problems is …..

A. to minimize transportation cost

b. to maximize transportation cost

c. to either minimize or to maximize transportation cost

d. to neither minimize nor to maximize transportation cost

7. …….. is the first solution to the transportation problem.

a. An initial feasible solution

b. An initial infeasible solution

c. An initial feasible or infeasible solution

d. VAM

8. In the North West Corner Method, the process of transportation of

goods starts from the……. Of the matrix.

a. Upper right corner

b. Lower right corner

a. lower left corner

d. upper left corner

Answers

1.) a 2.) b 3.) b 4.) c 5.) a 6.) a 7.) a 8.) d

munotes.in

## Page 68

68

Operation Research Q2. Identify statements as true or false statement.

1. Necessary and sufficient condition for existence of a feasible solution

to the transportation problem is that there should be total demand

equal to total supply. (i.e. Total demand is equal to total supply).

(True or False)

2. When total demand is equal to total supply then the transportation

problem is said to be unbalanced. (True or False)

3. If total demand is not equal to t otal supply then the transportation

problem is an unbalanced transportation problem. (True or False).

4. The occupied cells are having positive allocation in a transportation

problem and are denoted by a circular symbol. (True or False).

5. The basic feasible solution exists when number of occupied cells are

not equal to number of rows and number of columns minus one i.e.

(No. of occupied cells = m+n -1). Where m is the number of rows and

n is the number of columns. (True or False).

6. When the number of positi ve allocated cells are less than m+n -1 and a

solution is degenerate solution and when the number of positive

located cells are equal to m+n -1 then the solution is non -degen erate

solution. (True or False)

7. Due to unfavorable road conditions, bad weather co nditions or any

other condition etc., It may not be possible to transit products from

the sources to the destination such routes are prohibited routes. (True

or False)

Answers:

1. True 2. False. 3. True

4. True 5. False 6. True

7. True

Q3. Wr ite short notes on

1. Describe various terminologies used in the transportation method

2. Explain methods of finding initial feasible solution.

3. Describe steps of finding solutions to the transportation prolem.

4. Explain the steps of solving

a. North West Corner M ethod.

b. Row Minima Method

c. Column Minima Method

d. Least Cost Method

e. Vogels’ Approximation Method. munotes.in

## Page 69

69

Transportation Q4. Determine the initial feasible solution to the following

transportation problem using

a. North West Corner Method. (Answer: 116)

b. Least Cost Method (Answer: 112)

c. Vogels’ Approximation Method. (Answer: 102) Source/ Destination D1 D2 D3 D4 Supply S1 2 3 11 7 6 S2 1 0 6 1 1 S3 5 8 15 9 10 Demand 7 5 3 2 17

munotes.in

## Page 70

70 3

ASSIGNMENT PROBLEMS

Unit Structure:

3.0 Objectives

3.1 Introduction

3.2 Hungarian Method of Solution

3.3 Special Cases in Assignment Problems

3.3.1 Unbalanced Problems

3.3.2 Multiple Optimum Solutions

3.3.3 Maximization Problems

3.4 Summary

3.5 Self-Assessment Questions

3.0 OBJECTIVES

The learning objectives of Game Theory are as follows :

1. To understand the concepts of assignment problems.

2. To allocate different jobs to different machines, different jobs to

different employees on one to one basis.

3. To ut ilize maximum efficiency of employees and machine to get

maximum output and with minimum duration of completion of tasks.

4. To study different methods of assignments in detail.

3.1 INTRODUCTION

Assignment is the particular type of optimization technique whe re object

is to allocate limited resources to maximize the profit. In general,

assignment is the method allocating limited organizational resources such

as manpower, machine to different jobs. Hence assignment problems are

the optimization problem to alloc ate jobs to different machines or to

workers, salesmen to the sales zone or to allocate vehicles to different

routes. Assignment works on one to one basis i.e. one resource to the one

unit likewise.

All assignments are done in order to allocate scare resou rces to machines

or jobs so as to maximize the efficiency or output of the machine or

worker. Assignment problems have same number of rows and columns for

allocating resources properly on one to one basis. If this situation is not munotes.in

## Page 71

71

Assignment Problems satisfied, this may becom e unbalanced problem and it can be converted to

the balanced assignment problems by adding dummy row or column to

make it balanced problem and solution can be found out by using

Hungarian Assignment Method or special case solutions. Let us study

these conc epts thoroughly one by one as follows

3.2 HUNGARIAN METHOD OF SOLUTION

The Statistician Hungarian put forward the method of finding solution to

the assignment problems called as Hungarian Assignment Method

(HAM). This method is used for minimization cases of optimization

problems. This method is faster, easier and more efficient to find out

the solutions to the Assignment Problems. The steps of finding

solutions using Hungarian Assignment Method (HAM) are as follows :

Step 1. Verifying Balanced or Unbalanced assignment problem

The first step is to find out the balanced or unbalanced assignment

problem. This can be done by considering equality of rows and columns.

If the number of rows is equal to the number of columns then this is

balanced assignment problem . If the number of rows is not equal to the

number of columns then this is unbalanced assignment problem.

The balanced assignment problem is required for next step.

Step 2. Row Subtraction

In the balanced assignment problem, we have to find the smallest element

from each row. Then subtract that smallest element of row from every

element of corresponding row. This step is row subtraction.

Step 3. Column Subtraction

In the reduced assignment problem, we have to find the smallest element

from each column. Then subtract that smallest element of column from

every element of corresponding column. This step is column subtraction.

Step 4. Line Formation

Then form the lines using maximum number of zeros either in row or in

column as first line and next lines are formed using the same principle of

maximum number of zeros either in row or in column as second line and

so on.

Step 5. Comparing Number of lines with Number of rows and

Number of Columns

In the assignment problems, as jobs are assigned to machines or me n on

one to one basis, the number of rows and number of columns are already

same. Here we have to verify the number of lines formed with number of

rows and number of columns, if they are same then direct allocation is

possible otherwise improvement has to be done. Let us discuss these facts

in detail as follows

munotes.in

## Page 72

72

Operation Research i. If number of lines formed are same as number of rows and number of

columns then direct allocation is possible as follows

The allocation is one by considering the only one zero available in the

row or column. Then second time same thing is observed (only one zero

available) and remaining zero in the related column or row are cancelled

accordingly as the allocations are done on one to one basis. The procedure

is repeated until and unless all allocati ons or assignments are done.

ii. If number of lines formed are not same as number of rows and number

of columns then direct allocation is possible as follows

Then Hungerian Assignment Method (HAM) is used.

Step 6. Hungerian Assignment Method (HAM)

If number of lines formed are not same as number of rows and number of

columns then Hungerian Assignment Method (HAM) is used

As the lines are formed, few rows and columns are cancelled. The matrix

is turned into reduced matrix with remaining elements of matrix th at are

not cancelled. Few lines cross each other and crossing points are called as

junction point.

The smallest element in the remaining reduced matrix is subtracted from

all elements of reduced matrix so that one additional zero is obtained at

the loca tion of smallest element of that remaining reduced matrix and that

leads to the chance of formation of new line. At the junction point, that

smallest number is to be added.

The allocation is one by considering the only one zero available in the row

or col umn. Then second time same thing is observed (only one zero

available) and remaining zero in the related column or row are cancelled

accordingly as the allocations are done on one to one basis. The procedure

is repeated until and unless all allocations or assignments are done.

Step 7. Assignments

The allocations or assignments are done on one to one basis so that every

row and column as one allocation. It means that each worker or machine

has one job to be done in minimum time.

Let us study these all step s by practical examples.

Example 1. A job requires four different activities - Sorting, Washing,

Finishing and Assembling. Four workers are assigned all these activities.

The time required by each worker to complete four different activities -

Sorting, Wash ing, Finishing and Assembling are given below

munotes.in

## Page 73

73

Assignment Problems Worker 1 Worker 2 Worker 3 Worker 4 Sorting 31 25 33 25 Washing 25 24 23 21 Finishing 19 21 23 24 Assembling 38 36 34 40

How should these activities be arranged to the workers so that the job is

complet ed in minimum time?

Solution:

This is an assignment problem as 4 activities are assigned to 4 workers on

one to one basis. Our objective is to minimize time of completion of work

by assigning proper activities to workers.

Step 1. Verifying Balanced or Un balanced assignment problem

The first step is to find out the balanced or u nbalanced assignment

problem. This can be done by considering equality of rows and columns.

If the number of rows is equal to the number of columns then this is

balanced assignmen t problem. If the number of rows is not equal to th e

number of columns then this is unbalanced assignment problem.

Here the number of rows r=4 and number of columns c=4 and hence this

is balanced assignment problem (r=c=4).

The balanced assignment probl em is required for next step.

Step 2. Row Subtraction

In the balanced assignment problem, we have to find the smallest element

from each row. Then subtract that smallest element of row from every

element of corresponding row. This step is row subtractio n.

Here, sorting activity is given in the first row and smallest element in the

first row is 25. Subtract 25 from each element of first row. Similarly for

the second row, washing activity is given in the second r ow and smallest

element in the second row is 21. Subtract 21 from each elemen t of second

row. For the third row, finishing activity is given in the third row and

smallest element in the third row is 19. Subtract 19 from each elemen t of

third row. For the fourth row, assembling activity is given in the fourth

row and smallest element in the fourth row is 34. Subtract 34 from each

element of fourth row. We get

munotes.in

## Page 74

74

Operation Research Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6

Step 3. Column Subtractio n

In the reduced assignment problem, we have to find the smallest element

from each column. Then subtract that smallest elemen t of column from

every element of corresponding column. This step is column subtraction.

Here, worker 1 is given in the first c olumn and smallest element in the

first column is 0. Subtract 0 from each element of first column. Similarly

for the second column, worker 2 is given in the second column and

smallest element in the second column is 0. Subtract 0 from each element

of secon d column. For the third column, worker 3 is given in the third

column and smalle st element in the third column is 0. Subtract 0 from

each element of third column. For the fourth column, worker 4 is given in

the fourth column and smallest element in the fou rth column is 0. Subtract

0from each element of fourth column. We get

Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6

Step 4. Line Formation

Then form the lines using maximum number of ze ros either in row or in

column as first line and next lines are formed using the same principle of

maximum number of zeros either in row or in column as second line and

so on.

First row Sorting and fourth column W orker 4 has two zeroes. So, we may

form fir st line in the first row or in the fo urth column and other rows and

columns have only one zero in their pattern. So, le t us try with first row

having two zeroes as maximum number of zeroes as follows

munotes.in

## Page 75

75

Assignment Problems Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6

Next see that second, third and fourth rows have only one zero similarly

first, second, third and fourth columns have only one zero and we may

proceed either row wise or column wise. For the pu rpose of

convenience, consider second, third and fourth rows have only one zero

for line formation as follows

Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6

Step 5. Comparing Number o f lines with Number of rows and

Number of Columns

Here we have to verify the number of lines formed with number of rows

and number of columns, if they are same then direct al location is

possible otherwise improvement has to be done. Let us discuss these f acts

in detail as follows :

The number of lines formed (4) are same as number of rows (4) and

number of columns (4) then direct allocation is possible as follows

The allocation is done by considering the only one zero available in the

row or column. Then second time same thing is observed (only one zero

available) and remaining zero in the related column or row are cancelled

accordingly as the allocations are done on one to one basis. The procedure

is repeated until and unless all allocations or assignment s are done.

Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0 8 0 Washing 4 3 2 0 Finishing 0 2 4 5 Assembling 4 2 0 6 munotes.in

## Page 76

76

Operation Research In the second row, only one zero is available which is at the junction of

worker 4 and washing. It means that washing can be done by worker 4. If

worker 4 is busy with washing then he can’t do other task sorting. Hence

sorting can be done by worker 2 (zero availability) as follows

Worker 1 Worker 2 Worker 3 Worker 4 Sorting 6 0✔ 8 0✖ Washing 4 3 2 0✔ Finishing 0✔ 2 4 5 Assem bling 4 2 0✔ 6

Step 7. Assignments

The allocations or assignments are done on one to one basis so that every

row and column as one allocation. It means that each worker or machine

has one job to be done in minimum time. The single zero in row or

column i ndicates relative cell position to be selected for assignment

purpose as follows

Sr. No. Activities Worker Time (in minutes) 1 Sorting 2 25

2 Washing 4 21

3 Finishing 1 19

4 Assembling 3 34

Total time 99 minutes

These activities should be arrange d to the workers in above assignment so

that the job is completed in minimum 99 minutes.

HAM for improvement type assignment problems

Example 2: The five different machines A, B, C, D and E perform five

different tasks 1, 2, 3, 4 and 5. The costs for per forming each task (in lack

rupees) are given below

1 2 3 4 5

A 8 8 8 11 12

B 4 5 6 3 4

C 12 11 10 9 8

D 18 21 18 17 15

E 10 11 10 8 12

munotes.in

## Page 77

77

Assignment Problems How you will assign different tasks to different machines one to one basis

so that the total cost of productio n should be minimum?

Solution:

This is an assignment problem as 5 tasks are assigned to 5 machines on

one to one basis. Our objective is to minimize total cost of production by

assigning proper tasks to machines.

The steps for assignment are as follows :

Step 1. Verifying Balanced or Unbalanced assignment problem

The first step is to find out the balanced or unbalanced assignment

problem. This can be done by considering equality of rows and columns.

If the number of rows is equal to the number of column s then this is

balanced assignment problem. If the number of rows is not equal to the

number of columns then this is unbalanced assignment problem.

Here, the number of tasks and machines are 5 and 5 respectively. Hence

this is balanced assignment proble m.

The balanced assignment problem is required for next step.

Step 2. Row Subtraction

In the balanced assignment problem, we have to find the smallest element

from each row. Then subtract that smallest element of row from every

element of corresponding row. This step is row subtraction.

Here machine A is at first row and the smallest element in the first row is

8. Subtract 8 from every element of first row. Mach ine B is at second row

and the smallest element in the second row is 3. Subtract 3 from ever y

element of second row. Similarly, for third, fourth and fifth row, activities

are carried out as follows

1 2 3 4 5

A 0 0 0 3 4

B 1 2 3 0 1

C 4 3 2 1 0

D 3 6 3 2 0

E 2 3 2 0 4

Step 3. Column Subtraction

In the reduced assignment problem, we have to find the smallest element

from each column. Then subtract that smallest elemen t of column from

every element of corresponding column. This step is column subtraction.

munotes.in

## Page 78

78

Operation Research Every column has smallest element 0 and henc e subtracting smallest

element from ever y element of first column will lead to same reduced

assignment table.

1 2 3 4 5

A 0 0 0 3 4

B 1 2 3 0 1

C 4 3 2 1 0

D 3 6 3 2 0

E 2 3 2 0 4

Step 4. Line Formation

Then form the lines using maximum number of ze ros either in row or in

column as fir st line and next lines are formed using the same principle of

maximum number of zeros either in row or in column as second line and

so on.

1 2 3 4 5

A 0 0 0 3 4

B 1 2 3 0 1

C 4 3 2 1 0

D 3 6 3 2 0

E 2 3 2 0 4

By observation, it is found that the first row ha s maximum (3) zeroes and

hence first line formed is in first row. Fourth and fifth co lumns have (2)

maximum zeroes for the next time. Hence second and third lines are

formed at Fourth and fifth columns. There are no other zeroes available

and hence line formation is as follows

1 2 3 4 5

A 0 0 0 3 4

B 1 2 3 0 1

C 4 3 2 1 0

D 3 6 3 2 0

E 2 3 2 0 4

munotes.in

## Page 79

79

Assignment Problems Step 5. Comparing Number of lines wit h Number of rows and

Number of Columns

In the assignment problems, as tasks are assigne d to machines o r men on

one to one basis, the number of rows and number of columns are already

same. Here we have to verify the number of lines formed with number of

rows and number of columns, if they are same then direct al location is

possible otherwise improvement has to be done. Let us discuss t hese facts

in detail as follows:

The number of lines formed (3) are not same as number of rows (5) and

number of columns (5) then direct allocation is possible as follows

Then Hungerian Assignment Method (HAM) is used.

Step 6. Hungerian Assignment Method (HAM)

If number of lines formed are not same as number of rows and number of

columns then Hungerian Assignment Method (HAM) is used

The smallest element in the remaining reduced matrix is subtracted from

all elements of re duced matrix so that one additional zero is obtained at

the location of smallest element of that remaining reduced matrix and that

leads to the chance of formation of new line. At the junction point, that

smallest number is to be added.

The allocation is o ne by considering the only one zero available in the row

or column. Then second time same thing is observed (only one zero

available) and remaining zero in the related column or row are cancelled

accordingly as the allocations are done on one to one basis. The procedure

is repeated until and unless all allocations or assignments are done.

1 2 3 4 5

A 0 0 0 3 4

B 1 2 3 0 1

C 4 3 2 1 0

D 3 6 3 2 0

E 2 3 2 0 4

The smallest element in the reduced assignment matrix is 1. Subtract that

smallest element 1 from all elements of reduced assignment matrix. Add

that smallest element at two junctions point A4 and A5 as follows :

The number of lines formed (4) are not same as number of rows (5) and

number of columns (5) then direct allocation is not possible as follows :

Line formation: As second row has zero, this is cancelled as below

munotes.in

## Page 80

80

Operation Research 1 2 3 4 5

A 0 0 0 4 5

B 0 1 2 0 1

C 3 2 1 1 0

D 2 5 2 2 0

E 1 2 1 0 4

Here the smallest element in the remaining reduced matrix is 1, subtracted

from all elements of reduced matrix so that one additional zero is obtained

at the location of smallest element of that remaining reduced matrix and

that leads to the chance of formation of new line. At the junction point,

that smallest number (1) is to be added.

Step 7. Line formation:

As third column has 2 zeroes and hence this is cancelled as follows

1 2 3 4 5

A 0 0 0 5 6

B 0 1 2 1 2

C 2 1 0 1 0

D 1 4 1 2 0

E 0 1 0 0 4

Step 8 . Comparing number of lines formed and with number of rows

and columns

The number o f lines formed (5) are same as number of rows (5) and

number of columns (5) then direct allocation is possible as follows

Step 9 . Assignments

The allocations or assignments are done on one to one basis so that every

row and column as one allocation. It me ans that each worker or machine

has one job to be done in minimum time.

The allocation is done by considering the only one zero available in the

row or column. Then second time same thing is observed (only one zero

available) and remaining zero in the rel ated column or row are cancelled

accordingly as the allocations are done on one to one basis. The procedure

is repeated until and unless all allocations or assignments are done.

munotes.in

## Page 81

81

Assignment Problems 1 2 3 4 5

A 0 0 0 5 6

B 0 1 2 1 2

C 2 1 0 1 0

D 1 4 1 2 0

E 0 1 0 0 4

Now the second column has only one zero and hence it will be selected at

first.

1 2 3 4 5

A 0✖ 0✔ 0✖ 5 6

B 0 1 2 1 2

C 2 1 0 1 0

D 1 4 1 2 0

E 0 1 0 0 4

As machine A is busy with task 2, it can’t perform any other tasks like 1

and 3 (having zero values)

Now the machine D has only one zero and hence it can perform only 5th

task.

1 2 3 4 5

A 0✖ 0✔ 0✖ 5 6

B 0 1 2 1 2

C 2 1 0 1 0✖

D 1 4 1 2 0✔

E 0 1 0 0 4

Now machine C is capable of performing task 3 as follows

1 2 3 4 5

A 0✖ 0✔ 0✖ 5 6

B 0 1 2 1 2

C 2 1 0✔ 1 0✖

D 1 4 1 2 0✔

E 0 1 0 0 4

munotes.in

## Page 82

82

Operation Research As task 3 is already taken up by machine C t hen machine E cant’ do that

task and machine E performs 4th task as follows

1 2 3 4 5

A 0✖ 0✔ 0✖ 5 6

B 0 1 2 1 2

C 2 1 0✔ 1 0✖

D 1 4 1 2 0✔

E 0✖ 1 0✖ 0✔ 4

Now task 1 can be performed by machine B as follows

1 2 3 4 5

A 0✖ 0✔ 0✖ 5 6

B 0✔ 1 2 1 2

C 2 1 0✔ 1 0✖

D 1 4 1 2 0✔

E 0✖ 1 0✖ 0✔ 4

The allocation or assignment of different task s to different machines are as

follows

Sr. No. Machine Task Cost of task

1 A 2 8

2 B 1 4

3 C 3 10

4 D 5 15

5 E 4 8

Total cost of production (in lack rupees) 45

3.3 SPECIAL CASES IN ASSIGNMENT PROBLEMS

The special cases in assignment problems are unbalanced problems,

multiple optimum solution, maximization problems and prohibited

assignments as follows :

3.3.1 Unbalanced Problems

When the number of rows is no t equal to the number of columns then this

is unbalanced assignment problem. While solving it, we have to convert it munotes.in

## Page 83

83

Assignment Problems to balanced problem either by adding dummy row or column as per the

requirement and rest steps are similar.

Example 3: The 3 seminar slots are available for 4 MMS students. Now

Professor wants to conduct seminars within minimum time slots available

to students. The slots and students names are given below within cells

representing time required for completing seminar .

Students Slot1 Slot2 Slot3

Aaradhya 40 29 32

Aadvet 42 25 35

Vedika 35 22 38

Shrived 36 26 33

How will you assign slots to students so that minimum time slots are

available to students?

Solution: As 3 slots are available to 4 students, one student is remaining

with the slot . Hence dummy slot may be added to make it equal (number

of rows and number of columns will be made same by adding dummy

column) as follows

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 40 29 32 0

Aadvet 42 25 35 0

Vedika 35 22 38 0

Shrived 36 26 33 0

Step 1. Verifying Balanced or Unbalanced assignment problem

The number of rows (4) is equa l to the number of columns (4) hence , this

is balanced assignment problem. The balanced assignment problem is

required for next step.

Step 2. Row Subtraction

In the balanced assignment problem, we have to find the smallest element

from each row. Then subtract that smallest element of row from every

element of corresponding row. This step is row subtraction.

In all rows, smallest element is zero and hence assignme nt problem

remains unchanged.

munotes.in

## Page 84

84

Operation Research Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 40 29 32 0

Aadvet 42 25 35 0

Vedika 35 22 38 0

Shrived 36 26 33 0

Step 3. Column Subtraction

In the reduced assignment problem, we have to find the smallest element

from eac h column. Then subtract that smallest element of column from

every element of corresponding column. This step is column subtraction.

The smallest element in the first column is 35 and subtracts 35 from all

elements of first column and so on

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0

Aadvet 7 3 3 0

Vedika 0 0 6 0

Shrived 1 4 1 0

Step 4. Line Formation

Then form the lines using maximum number of zeros either in row or in

column as first line and next lines are formed using the same principl e of

maximum number of zeros either in row or in column as second line and

so on.

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0

Aadvet 7 3 3 0

Vedika 0 0 6 0

Shrived 1 4 1 0

First line is formed by four zeroes available in the fourth column and

second line is formed by two zeroes in the third row and third column

contains only one zero available forming third line as follows

munotes.in

## Page 85

85

Assignment Problems Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0

Aadvet 7 3 3 0

Vedika 0 0 6 0

Shrived 1 4 1 0

Step 5. C omparing Number of lines with Number of rows and

Number of Columns

In the assignment problems, as jobs are assigned to machines or men on

one to one basis, the number of rows and number of columns are already

same. Here we have to verify the number of line s formed with number of

rows and number of columns, if they are same then direct allocation is

possible otherwise improvement has to be done. Let us discuss these facts

in detail as follows

The number of lines formed (3) are not same as number of rows (4) and

number of columns (4)then direct allocation is possible as follows

Then Hungerian Assignment Method (HAM) is used.

Step 6. Hungerian Assignment Method (HAM)

If number of lines formed (3) are not same as number of rows (4) and

number of columns (4) t hen Hungerian Assignment Method (HAM) is

used

As the lines are formed, few rows and columns are cancelled. The matrix

is turned into reduced matrix with remaining elements of matrix that are

not cancelled. Few lines cross each other and crossing points are called as

junction point.

The smallest element in the remaining reduced matrix is subtracted from

all elements of reduced matrix so that one additional zero is obtained at

the location of smallest element of that remaining reduced matrix and that

leads to the chance of formation of new line. At the junction point, that

smallest number is to be added.

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 5 7 0 0

Aadvet 7 3 3 0

Vedika 0 0 6 0

Shrived 1 4 1 0

munotes.in

## Page 86

86

Operation Research The smallest element (1) in the remaining r educed matrix is subtracted

from all elements of reduced matrix so that one additional zero is obtained

at the location of smallest element of that remaining reduced matrix and

that leads to the chance of formation of new line. At the junction points 6

and 0, that smallest number (1) is to be added.

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0

Aadvet 6 2 3 0

Vedika 0 0 7 1

Shrived 0 3 1 0

Step 7. One additional line is formed and hence total 4 lines are formed

and are equal to the number of rows (4) and number of columns (4).

Hence Assignment is done as follows

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0

Aadvet 6 2 3 0

Vedika 0 0 7 1

Shrived 0 3 1 0

Step 8. Assignments

The allocations or assignments are done on one to one basis so that every

row and column as one allocation. It means that each worker or machine

has one job to be done in minimum time.

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0 0

Aadvet 6 2 3 0

Vedika 0 0 7 1

Shrived 0 3 1 0

The second row is having only one zero and hence allocation to Aadvet is

dummy slot. As dummy slot is taken by Aadvet and hence dummy slot

can‘t be given to any other student. For the slot2, only one zero is

available at third row. Similarly for the slot3, only one zero is available at

first row and the assignment problem takes the following form. munotes.in

## Page 87

87

Assignment Problems

Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0✔ 0✖

Aadvet 6 2 3 0✔

Vedika 0✖ 0✔ 7 1

Shrived 0✔ 3 1 0✖

The Fourth row Shrived is having zero at slot 1 and hence slot 1 can not be

taken by Vedika as follows

Sr. No. Name of the

student Time slot Time (in

minutes)

1 Aaradhya Slot3 32

2 Aadvet Slot4 00* Dummy

3 Vedika Slot2 22

4 Shrived Slot1 36

* Dummy values are not known and are considered for the purpose of

making allocations or assignments.

3.3.2 Multiple Optimum Solutions

When the assignment problem has more than one solution, this is ter med

as multiple optimum solutions to the assignment prob lem. The minimum

two solutions exist for multiple optimum solutions. Hence there are

possibilities of getting different solutions. We can compare solutions and

get the optimum solution required.

Examp le 4. The railway ticket window has 4 reservatio n counters. Four

employees are assigned these tasks of reservation counters. The cost of

assigning each person to each counter is as follows

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 1 8 15 22

Aadvet 13 18 23 28

Vedika 13 18 23 28

Shrived 19 23 27 31

munotes.in

## Page 88

88

Operation Research Solution:

Step 1. Verifying Balanced or Unbalanced assignment problem

The number of rows (4) is equa l to the number of columns (4) hence, this

is balanced assignment problem. The balanc ed assignment problem is

required for next step.

Step 2. Row Subtraction

In the balanced assignment problem, we have to find the smallest element

from each row. Then subtract that smallest element of row from every

element of corresponding row. This step is row subtraction.

In first row, the smallest element is 1 and In second and third rows, the

smallest elements are 13 and in the fourth row, the smallest element is 19.

Subtract these smallest elements from all corresponding rows and then we

get

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 7 14 21

Aadvet 0 5 10 15

Vedika 0 5 10 15

Shrived 0 4 27 12

Step 3. Column Subtraction

In the reduced assignment problem, we have to find the smallest element

from each column. Then subtract that smallest element of column from

every element of corresponding column. This step is column subtraction.

The smallest element in the first column is 0 and subtracts 0 from all

elements of first column and so on

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 3 4 9

Aadvet 0 1 0 3

Vedika 0 1 0 3

Shrived 0 0 17 0

Step 4. Line Formation

Then form the lines using maximum number of zeros either in row or in

column as first line and next lines are formed using the same principle of

maximum nu mber of zeros either in row or in column as second line and

so on.

munotes.in

## Page 89

89

Assignment Problems First line is formed by four zeroes available in the first column and second

line is formed by two zeroes in the third column and second and fourth

column contains only one zero available forming third and fourth lines as

follows

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 3 4 9

Aadvet 0 1 0 3

Vedika 0 1 0 3

Shrived 0 0 17 0

Step 5. Comparing Number of lines with Number of rows and

Number of Columns

In the assig nment problems, as jobs are assigned to machines or men on

one to one basis, the number of rows and number of columns are already

same. Here we have to verify the number of lines formed with number of

rows and number of columns, if they are same then direc t allocation is

possible otherwise improvement has to be done. Let us discuss these facts

in detail as follows

The number of lines formed (4) are same as number of rows (4) and

number of columns (4) then direct allocation is possible as follows

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 3 4 9

Aadvet 0 1 0 3

Vedika 0 1 0 3

Shrived 0 0 17 0

Step 8. Assignments

The allocations or assignments are done on one to one basis so that every

row and column as one allocation. It means tha t each worker or machine

has one job to be done in minimum time.

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 3 4 9

Aadvet 0 1 0 3

Vedika 0 1 0 3

Shrived 0 0 17 0 munotes.in

## Page 90

90

Operation Research As first row has only one zero. Aaradhya will serve to Reservation

Counter 1 and As Reservation Counter 1 is served by Aaradhya and hence

it can ’t be served by any other employee. Similarly, second and fourth

columns have single zeroes. Hence allocation is direct there.

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0✔ 3 4 9

Aadvet 0✖ 1 0✔ 3

Vedika 0✖ 1 0✔ 3

Shrived 0✖ 0✔ 17 0✔

As reservation counter 3 is occupied by the Aadvet and Vedika both so

assignment solution is not optimum.

Hence again repeat the process.

Step 9. Row subtraction

As every row h as zero element and then row subtraction is not possible.

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0✔ 3 4 9

Aadvet 0✖ 1 0✔ 3

Vedika 0✖ 1 0✔ 3

Shrived 0✖ 0✔ 17 0✔

Step 10. Column subtraction

Employee Reservation counter (Rc)

Rc1 Rc2 Rc3 Rc4

Aaradhya 0 3 4 9

Aadvet 0 1 0 3

Vedika 0 1 0 3

Shrived 0 0 17 0

munotes.in

## Page 91

91

Assignment Problems Students Slot1 Slot2 Slot3 Dummy Slot Aaradhya 4 6 0✔ 0✖

Aadvet 6 2 3 0✔

Vedika 0✖ 0✔ 7 1

Shrived 0✔ 3 1 0✖

The Fourth row Shrived is having zero at slot 1 and hence slot 1 can not be

taken by Vedika as follows

Sr. No. Name of the

student Time slot Time (in

minutes)

1 Aaradhya Slot3 32

2 Aadvet Slot4 00* Dummy

3 Vedika Slot2 22

4 Shrived Slot1 36

* Dummy values are not known and are considered for the purpose of

making

3.3.3 Maximization Problems

The maximization problems are the assignment problems related to profit,

sales or output maximization or any other units that are required to be

maximized. The optimization techniques used here is to maximize the

sales, pro fit or any other objective of assignment problem. The given

maximization matrix is transformed into a relative loss matrix by

subtracting every element from the largest element of the assignment

matrix. The next steps are similar to the HAM assignment prob lems. All

steps are designed to find out the relative position of allocation or

selection of given alternatives from set of all combinations of alternatives

as follow

Example 5 . A marketing manager has five salesmen and five sales

districts. Considering th e capabilities of the salesmen and the nature of

districts, the marketing manager estimates that sales per month (in

hundred rupees) for each salesman in each district would be as follows

munotes.in

## Page 92

92

Operation Research

Salesmen Districts

A B C D E

1 32 38 40 28 40

2 40 24 28 21 36

3 41 27 33 30 37

4 22 38 41 36 36

5 29 33 40 35 39

Find the assignment of salesmen to districts that will result in maximum

sales.

Solution:

Step 1. The given assignment problem is to maximize sales by proper

assignment of salesmen to differ ent districts. Hence this is maximization

problem of assignment.

Step 2. Convert into minimization

This can be done by selecting the largest element (41) of the given

problem and subtract it from all elements to form relative loss matrix

called opportunity loss matrix as follows

Salesmen Districts

A B C D E

1 9 3 1 13 1

2 1 17 13 20 5

3 0 14 8 11 4

4 19 3 0 5 5

5 12 8 1 6 2

munotes.in

## Page 93

93

Assignment Problems Step 3. Row subtraction

Salesmen Districts

A B C D E

1 8 0 0 7 0

2 0 16 12 19 4

3 0 14 8 11 4

4 19 3 0 5 5

5 11 7 0 5 1

Step 4. Column subtraction

Salesmen Districts

A B C D E

1 8 0 0 2 0

2 0 16 12 14 4

3 0 14 8 6 4

4 19 3 0 0 5

5 11 7 0 0 1

Step 5. Line formation

Salesmen Districts

A B C D E

1 8 0 0 2 0

2 0 16 12 14 4

3 0 14 8 6 4

4 19 3 0 0 5

5 11 7 0 0 1

munotes.in

## Page 94

94

Operation Research The formed lines (4) are less than 5 rows and 5 columns. Hence

improvement can be done by subtracting smallest element (4) from all

elements of reduced matrix and adding this smallest element to the

junction point so as to develop a chance of forming new line.

Salesmen Districts

A B C D E

1 12 0 0 2 0

2 0 12 8 10 0

3 0 10 4 2 0

4 23 3 0 0 5

5 15 7 0 0 1

Step 6. Line formation

Salesmen Districts

A B C D E

1 12 0 0 2 0

2 0 12 8 10 0

3 0 10 4 2 0

4 23 3 0 0 5

5 15 7 0 0 1

The formed lines (5) are equal to 5 rows and 5 columns. Hence

direct allocation is possible as follows

Salesmen Districts

A B C D E

1 12 0✔ 0✖ 2 0✖

2 0 12 8 10 0

3 0 10 4 2 0

4 23 3 0 0 5

5 15 7 0 0 1 munotes.in

## Page 95

95

Assignment Problems Now there are two alternatives for A district as

i. Salesman 2 is given an opportunity to serve in A district.

ii. Salesman 3 is given an opportunity to serve in A district.

Salesmen Districts

A B C D E

1 12 0✔ 0✖ 2 0✖

2 0✔ 12 8✖ 10 0✖

3 0✖ 10 4 2 0✔

4 23 3 0 0 5

5 15 7 0 0 1

There are two additional conditions in first alternative as

a. Salesman 4 is given an opportunity to serve in C district.

b. Salesman 5 is given an oppo rtunity to serve in C district.

Let us study (a) option from first alternative as follows

Salesmen Districts

A B C D E

1 12 0✔ 0✖ 2 0✖

2 0✔ 12 8✖ 10 0✖

3 0✖ 10 4 2 0✔

4 23 3 0✔ 0✖ 5

5 15 7 0✖ 0✔ 1

Allocations are made as follows

Sr. No . Salesman District Sales (in Hundred

rupees)

1 1 B 38

2 2 A 40

3 3 E 37

4 4 C 41

5 5 D 35

Total sales 191 munotes.in

## Page 96

96

Operation Research Second option: Salesman 5 is given an opportunity to serve in C district.

Let us study (a) option from first alternative as follows

Salesmen Districts

A B C D E

1 12 0✔ 0✖ 2 0✖

2 0✔ 12 8 10 0✖

3 0✖ 10 4 2 0✔

4 23 3 0✖ 0✔ 5

5 15 7 0✔ 0✖ 1

Allocations are made as follows

Sr. No. Salesman District Sales (in

Hundred

rupees)

1 1 B 38

2 2 A 40

3 3 E 37

4 4 D 36

5 5 C 40

Total sales 191

3.4 SUMMARY

Assignment problems are the optimization problem to allocate jobs to

different machines or to workers, salesmen to the sales zone or to allocate

vehicles to different routes. Assignment works on one to one basis i.e. one

resource to the one unit likewise.

Hungarian A ssignment Method (HAM ) is used for minimization cases of

optimization problems. This method is faster, easier and more efficient to

find out the solutions to the Assignment Problems. When the assignment

problem has more than o ne solution, this is termed as multiple optimum

solutions to the assignment prob lem. The minimum two solutions exist for

multiple optimum solutions. Hence there are poss ibilities of getting

different solutions. We can compare solutions and get the optimum

solution required. The maximiz ation problems are the assignment

problems related to profit, sales or output maximization or any other units munotes.in

## Page 97

97

Assignment Problems that are required to be maximized. The optimization techniques used here

is to maximize the sales, profit or any other objective of assignment

problem. The given maximization matrix is transformed into a relative

loss matrix by subtracting every element from the largest element of the

assignment matrix. The next steps are similar to the HAM assignment

problems.

3.5 SELF -ASSIGNMENT QUESTIONS.

1. What is an assignment problem? What are the types of assignment

problems?

2. What are the steps of solving assignment problem?

3. Five jobs are assigned to five persons, each person will do one job only.

The expected time (in hours) required for each jo b for each person have

been estimated and are shown in the following table. Determine the

optimal assignments.

Job Person

1 2 3 4 5

A 12 15 13 14 15

B 16 18 15 14 16

C 18 16 15 18 20

D 15 20 18 17 19

E 16 15 18 14 15

4. A company has a team of fou r salesmen and there are four districts

where the company wants to start its business. The following is the profit

per day in rupees for each salesman in each district. Find the assignment

of salesmen to districts which will yield maximum profit.

Salesman District

D1 D2 D3 D4

A 16 10 14 11

B 14 11 15 15

C 15 15 13 12

D 13 12 14 15

munotes.in

## Page 98

98 4

GAME THEORY

Unit Structure:

4.0 Objectives

4.1 Introduction

4.2 Meaning and Concept of Game Theory

4.3 Terminologies in Game Theory

4.4 Types of Game

4.4.1 Pure Strategy Game

4.4.2 Mixed Strategy Game

4.5 Principle of Dominance

4.6 Limitati ons of Game Theory

4.7 Summary

4.8 Self-Assessment Questions

4.0 OBJECTIVES

The learning objectives of Game Theory are as follows :

1. To understand and decide winning strategies in a competitive business

world.

2. To study the concepts and terminologies of Game Theory.

3. To solve complex business situation and to assist in decision making

by using game strategies.

4. To analyse the business game and solve it by using pure strategy

game, mixed strategy game and principle of dominance.

4.1 INTRODUCTION

Today, bus iness world is complex, dynamic, and competitive in nature.

The monopoly is quite observed. There are many rivals in the business

and environ is competitive in the industry. Every business firm tries to

achieve success (win) by maximizing profit by defeati ng other rivalry

players in the business world. Hence every business firm tries to win the

game by defeating other players in the game using different strategies.

munotes.in

## Page 99

99

Game Theory 4.2 MEANING AND CONCEPT OF GAME THEORY

Game Theory is the competitive situation of business players in the

business competitive environment. Game theory is the study of operations

research technique involving appropriate use of strategies to win the

game. Thus Game theory is the branch of Operations Research dealing

with quantitative decision mak ing when at least two players are involved

in the conflicting and competitive environment, resulting in success and

failure of players.

4.3 TERMINOLOGIES IN GAME THEORY

4.3.1 Strategy: The possible alternatives or available course of action

that may be a dopted to win the game. For example, In order to earn more

profit, either selling price should be decreased to have more sales or cost

of production should be lowered.

4.3.2 Player: Each participant of game is called Player. There are at least

two players. One is considered as maximizing player (winner of the game)

and other is assumed as minimizing player (looser of the game). But

practically, such ideal situation may not come in reality.

4.3.3 Play: A play happens when each player select a particular stra tegy

from all available strategies.

4.3.4 Pay off: The outcome of playing a game is known as Pay off. The

Pay off is the net gain or profit earned by using appropriate strategy by the

winning player.

4.3.5 Pay off Matrix: Pay off matrix is the table of ga me theory

representing the two players out of which One is considered as

maximizing player (winner of the game) and other is assumed as

minimizing player (looser of the game).

4.3.6 Optimum Strategy: The optimum strategy is the strategy used by

the maximiz ing player against the strategies used by the competing

minimizing players.

4.3.7 Value of the Game: It is the expected outcome of the game theory

when all players use their optimum strategy. If the value of the game is

zero then game is said to be the fair game otherwise if the value of the

game is not zero then game is said to be the unfair game.

4.4 TYPES OF GAMES

Game is a particular business situation where at least two players are

involved to overcome the other player using optimum strategy and to get

maximum output using different strategies . The types of games are as

follows

a. Two Person Game

b. Multiple Person Game

c. Zero Sum Game munotes.in

## Page 100

100

Operation Research d. Non-Zero Sum Game

e. Two Person Zero Sum Game

These are explained as follows

a. Two Person Game: When there are two players in volved in the

game, then this is termed as two person game. One is considered as

maximizing player and other is considered as minimizing player.

b. Multiple Person Game: When there are more than two players

involved in the game, then this is termed as multip le person game.

This is also termed as n -person game.

c. Zero Sum Game: Zero sum means addition becomes equal to zero.

When the sum of gains of all winners is equal to the sum of losses of

all the losers, this condition of game is called zero sum game.

d. Non-Zero Sum Game: When the sum of gains of all winners is not

equal to the sum of losses of all the losers, this condition of

game is called non -zero sum game.

e. Two Person Zero Sum Game: In the two person game, when the

gain of one player is equal to the loss of other player, such type of

game is termed as Two Person Zero Sum Game.

Two person game having two strategies for each player is called as a two

person 2x2 game involving two rows and two columns in the payoff

matrix.

Based on the type of strategy, Games are again classified as follow

4.4.1 Pure Strategy Game:

In the pure strategy game, players use only one strategy throughout the

game. The pure strategy indicates that there is no other combination of

strategy used by the game player.

4.4.1.1 Steps for solving Pure Strategy Game :

1. Maximizing and Minimizing Player: In the payoff matrix,

maximizing players’ strategy should be written in the row and minimizing

players, strategy should be written in the column.

2. Row Maxi -min Strategy: In the row, maximum values from the

minimum values of the given rows are taken. In simple words, at first row

minima values should be taken for all rows and then maximum value from

all row minima values are taken called as Row Maxi -min value.

3. Column Min i-max Strategy: In the column , minimum values from the

maximum values of the given columns are taken. In simple words, at first

column maxima values should be taken for all columns and then minimum

value from all column maxima values are taken called as Co lumn Mini-

max value.

munotes.in

## Page 101

101

Game Theory 4. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min and Column Mini -max values are compared and if these values

are same then there exists a saddle point representing the value of the

game.

5. Saddle Point: The sad dle point is the point of intersection of row and

column of Row Maxi -min and Column Mini -max values. This saddle

point represents the value of the game.

6. One Saddle point and multiple saddle points: If there is only one

saddle point then this represents the value of the game alone. If there is

more than one saddle point, then this represents multiple solutions or

multiple values of the game showing combination of different strategies to

be used in the game strategy.

7. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min and Column Mini -max values are compared and if these values

are not same then there does not exist a saddle point and the game is

mixed strategy game

.

Example 1: Two competing firms A and B are in the local market. They

use different strategies to maximize the profit. Firm A uses two strategies

A1 and A2. Firm B uses three strategies B1, B2 and B3. Their

corresponding pay off matrix is given in the following table as

Firm B

B1 B2 B3

Firm A A1 2 8 4

A2 7 10 6

Solution:

The steps to solve game theory problem is as follows

1. Maximizing and Minimizing Player: Firm A is considered as

maximizing player and firm B is assumed as minimizing player.

Maximizing players’ (Firm A) strategy should be written in the r ow

and minimizing players’ (Firm B) strategy should be written in the

column.

2. Row Maxi -min Strategy: In the row, maximum values from the

minimum values of the given rows are taken. In simple words, at first

row minima values should be taken for all r ows

B1 B2 B3 Row Minima

Firm A A1 2 8 4 2

A2 7 10 6 6

munotes.in

## Page 102

102

Operation Research And then maximum value (6) from all row minima values (2 and 6) are

taken called as Row Maxi -min value.

3. Column Mini -max Strategy: In the column , minimum values from the

maxim um values of the given columns are taken. In simple words, at first

column maxima values should be taken for all columns

B1 B2 B3

Firm A A1 2 8 4

A2 7 10 6

Column Maxima 7 10 6

and then minimum value (6) from all column maxima values (7, 10 and 6)

are taken called as Column Mini-max value.

4. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min (6) and Column Mini -max values (6) are compared and if these

values are same then there exists a saddle point (6) representing the value

of the game (6).

5. Saddle Point: The saddle point (A2B3) is the point of intersection of

second row and third column of Row Maxi -min and Column Mini -max

values. This saddle point represents the value of the game.

6. Optimum Strategy and Val ue of the Game :

The optimum strategy corresponding to the saddle point is A2B3

strategies. The value of the game is 6 and Thus for the firm A, strategy A2

is the optimal strategy and it is represented as A (0,1) i.e. probability of

using A1 strategy is 0 a nd probability of using A2 strategy is 100%.

Similarly for the firm B, strategy B3 is the optimal strategy and it is

represented as B (0,0,1) i.e. probability of using B1 and B2 strategies are 0

and probability of using B3 strategy is 100%.

Example 2. A C ompany management and the labour union are

negotiating a new 3 years settlement. Each player has 4 strategies namely

a. Hard and Aggressive Bargaining

b. Reasoning and Logical Approach

c. Legalistic Approach

d. Conciliatory Approach

munotes.in

## Page 103

103

Game Theory The cost to the company ( in the f orm of average wage rise in Rs.) are

given for every pair of strategy choices

Union Strategies

A B C D

Company

Strategies A 20 25 40 -5

B 15 14 2 4

C 12 8 10 11

D 35 10 5 0

Which strategy will the two sides adopt? Also determine the value of

game.

Solution:

Solution: The steps to solve game theory problem is as follows

1. Maximizing and Minimizing Player: Company is considered as

maximizing player and Union is assumed as minimizing player. But

Union thinks to be the maximizing player and hence t he transformation of

row and column into column and row takes place.

Maximizing players’ ( Union ) strategy should be written in the row and

minimizing players’ ( Company ) strategy should be written in the column.

Company Strategies

A B C D

Union

Strat egies A 20 15 12 35

B 25 14 8 10

C 40 2 10 5

D -5 4 11 0

2. Row Maxi -min Strategy: In the row, maximum values from the

minimum values of the given rows are taken. In simple words, at first row

minima values should be taken for all rows

Company S trategies

A B C D Row

Minima

Union

Strategies A 20 15 12 35 12

B 25 14 8 10 8

C 40 2 10 5 2

D -5 4 11 0 -5

munotes.in

## Page 104

104

Operation Research And then maximum value (12) from all row minima values (12, 8, 2 and -

5) are taken called as Row Maxi -min value.

3. Column Mini -max Str ategy: In the column , minimum values from the

maximum values of the given columns are taken. In simple words, at first

column maxima values should be taken for all columns

Company Strategies

A B C D

Union

Strategies A 20 15 12 35

B 25 14 8 10

C 40 2 10 5

D -5 4 11 0

Column Maxima 40 15 12 35

and then minimum value (12) from all column maxima values (40, 15,12

and 35) are taken called as Column Mini-max value.

4. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min (12) and Colu mn Mini -max values (12) are compared and if

these values are same then there exists a saddle point (12) representing the

value of the game (12).

5. Saddle Point: The saddle point (uAcC) is the point of intersection of

first row and third column of Row Max i-min and Column Mini -max

values. The uA strategy or cell corresponds to the strategy A used by

Union and cC strategy represents to the strategy C used by Company. This

saddle point represents the value of the game.

6. Optimum Strategy and Value of the G ame:

The optimum strategy corresponding to the saddle point is uAcC

strategies. The value of the game is 12 and Thus for the Union, strategy A

is the optimal strategy and it is represented as (1,0,0,0) i.e. probability of

using A strategy is 10%0 and proba bility of using B,C and D strategies are

0%. Similarly for the Company, strategy C is the optimal strategy and it is

represented as (0,0,1,0) i.e. probability of using A,B and D strategies are 0

and probability of using C strategy is 100%.

4.4.2 Mixed Str ategy Game:

In the mixed strategy game, players use different strateg ies throughout the

game. The mixed strategy indicates that there is other combination of

strategies used by the game player.

munotes.in

## Page 105

105

Game Theory Mixed strategy games are solved by

1. 2x2 matrix game solution if pay off matrix is having 2 rows and 2

columns otherwise

2. Principle of Dominance strategy is used to solve the problem.

Let us study these two methods as follows :

1. 2x2 matrix game solution

If pay off matrix is having 2 rows and 2 columns then the sol ution of

game theory and their probabilities are obtained as follows

Let us consider ,

p as the probability that A uses strategy A1 and

1-p is the probability that A uses strategy A2.

Similarly ,

q as the probability that B uses strategy B1 and

1-q is the probability that B uses strategy B2.

Consider the pay off matrix

B

B1 (q) B2(1 -q)

A A1(p) a11 a12

A2(1 -p) a21 a22

Where ,

a11 represents the cell position of row 1 and column 1.

a12 represents the cell position of row 1 and column 2.

a21 r epresents the cell position of row 2 and column 1.

a22 represents the cell position of row 2 and column 2.

p as the probability that A uses strategy A1 is obtained by the formula

p= (a22- a21)/D

q as the probability that B uses strategy B1 is obtained b y the formula

q= (a22- a12)/D

and the value of the game is obtained by the formula

v= (a11a22 -a21a12)/D

where , D= denominator= a11+a22 -a21-a12

Example 3. Two business firms A and B are competing in the local

market. Player A is having the choice of two strategies A1 and A2. Player

B is having the choice of two strategies B1 and B2. Determine the

optimum strategy and value of the game using pure strategy and then by

using 2x2 matrix game solution method. munotes.in

## Page 106

106

Operation Research Player B

B1 B2

Player A A1 3 5

A2 4 1

Solution:

1. Maximizing and Minimizing Player: In the payoff matrix,

maximizing players’ (A) strategy should be written in the row and

minimizing players’ (B) strategy should be written in the column.

2. Row Maxi -min Strategy: In the row, maximum values fr om the

minimum values of the given rows are taken. In simple words, at first row

minima values should be taken for all rows

Player B

B1 B2 Row

Minima

Player A A1 3 5 3

A2 4 1 1

Then maximum value (1) from all row minima values (3,1) are taken

called as Row Maxi -min value.

3. Column Mini -max Strategy: In the column , minimum values from the

maximum values of the given columns are taken. In simple words, at first

column maxima values should be taken for all columns

Player B

B1 B2

Player A A1 3 5

A2 4 1

Column

Maxima 4 5

then minimum value (4) from all column maxima values (4 and 5) are

taken called as Column Mini-max value.

4. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min (1) and Column Mini -max (4) values are co mpared and these

values are not same then there does not exist a saddle point representing

the value of the game.

5. Mixed Strategy Game : 2x2 matrix two person mixed strategy game

can be solved by using the formula

munotes.in

## Page 107

107

Game Theory p as the probability that A uses strat egy A1 is obtained by the formula

p= (a22- a21)/D

q as the probability that B uses strategy B1 is obtained by the formula

q= (a22- a12)/D

and the value of the game is obtained by the formula

v= (a11a22 -a21a12)/D

where D= denominator= a11+a22 -a21-a12

Player B

B1 B2

Player A A1 3 5

A2 4 1

Here,

a11= 3; a12=5; a21=4; a22=1

and D= denominator= a11+a22 -a21-a12= 3+1 -4-5= -5

p as the probability that A uses strategy A1 is obtained by the formula

p= (a22- a21)/D = (1-4)/(-5)= ( -3)/-5= 0.6 and

and the probability that A uses strategy A2 is 1 -p=1-0.6=0.4

q as the probability that B uses strategy B1 is obtained by the formula

q= (a22- a12)/D = (1-5)/-5= (-4)/-5= 0.8

and the probability that B uses strategy B2 is 1 -q=1-0.8=0.2

and the value of t he game is obtained by the formula

v= (a11a22 -a21a12)/ D = (3x1 -4x5)/ -5=(3 -20)/-5=-17/-5=3.4

Therefore , the value of the game is 3.4 and the optimum strategy for A is

A1 and for B is B1.

4.5 PRINCIPLE OF DOMINANCE

The Principle of Dominance states that, if a strategy of a player dominates

over another strategy in all conditions (that is for all counter strategies by

other player), then the later strategy (being dominated) can be ignored. A

strategy dominates over the other strategy, only if it is prefera ble over the

other, under all conditions.

This Principle of Dominance is difficult to understand and hence simple

and logical trick has been developed by the content writer Dr. Gajanan

Mudholkar to remember this principle as follows

The trick to remembe r and apply Principle of Dominance is ‘RC’. The

first capital letter R stands for Capital R means Big R (R for row and R for

retain, it means that Bigger Row should be retained and Smaller Row

should be cancelled. The second capital letter C means Big C (C for

Column and C for cancellation) Greater Column should be Cancelled and

smaller column should be retained.

This principle can be applied in all type of Game Theory problem. This munotes.in

## Page 108

108

Operation Research principle can be used for pure strategy game and mixed strategy game

also.

Example 4. Solve the following game directly and by using Principle of

Dominance

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Solution:

Solve the following game directly means by using pure strategy game as

follows :

1. Maximizing and Minimizing Player: In the payoff matrix,

maximizing players’ strategy (Player X) should be written in the row and

minimizing players’ strategy (Player Y) should be written in the column.

2. Row Maxi -min Strategy: In the row, maximum values from the

minimum values of the given rows are taken. In simple words, at first row

minima values should be taken for all rows

Player Y

1 2 3 4 5 Row

Minima

Player

X I 1 3 2 7 4 1

II 3 4 1 5 6 1

III 6 5 7 6 5 5

IV 2 0 6 3 1 0

and then maximum value (5) from all row minima values (1,1,5,0) are

taken called as Row Maxi -min value (5).

3. Column Mini -max Strategy: In the column , minimum values from the

maximum values of the given columns are taken. In simple words, at first

column maxima values should be taken for all columns

munotes.in

## Page 109

109

Game Theory Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Column Maxima 6 5 7 7

and then minimum value (5) from all column maxima values (6,5,7,7) are

taken called as Co lumn Mini-max value (5).

4. Comparing Row Maxi -min and Column Mini -max values: The Row

Maxi -min (5) and Column Mini -max values (5) are compared and as these

values are same then there exists a saddle point representing the value of

the game.

5. Saddle Po int: The saddle point (5) is the point of intersection of row

and column of Row Maxi -min and Column Mini -max values. This saddle

point represents the value of the game.

V= Value of the Game=5 and the corresponding optimum strategy for

player X is III stra tegy and for Player Y is 2nd strategy.

6. By using Principle of Dominance

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

As we compare first and second row, we find that 1<3; 3<4; 2>1; 7>5 and

4<6 and there is no comparison possible. Similarly first row and third row

can’t be compared. Similarly first row and fourth row can’ t be compared .

Now we compare second row with third and fourth row as follows .

Similarly , second row and third row can’ t be compared. S imilarly second

row and fourth row can’ t be compared . munotes.in

## Page 110

110

Operation Research Now we compare third row with fourth row as follows

We get 6>1; 5>0; 7>6; 6>3 and 5>1. Hence third row is greater than

fourth row.

According to the Principle of Dominance, RC means R for Greater Row

and R for Retain. It means that the greater row should be retained and

smaller row should be cancelled.

III>IV i.e. third row will be retained and fourth row will be cancelled as

follows

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Now , compare column wise

First column 1 with second column 2 as follows

1<3; 3<4; 2>1; 7>5 and 4<6 and hence comparison is not possible.

First column 1 with third column 3 as follows

1<2; 3>1 and 6<7 and hence comparison is not p ossible.

First column 1 with fourth column 4 as follows

1<7; 3<5 and 6=6 and hence First Column 1 ≤ fourth column.

According to the Principle of Dominance, RC means C for Greater

Column and C for cancel. It means that the greater column should be

cancelled and smaller column should be retained.

Fourth column being greater should be cancelled and small er first column

should be retained as follows

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Now compare second column with fifth column we get

3<4; 4<6 and 5=5 and hence comparison is possible as follows

Column 3 ≤ Column 5

munotes.in

## Page 111

111

Game Theory According to the Principle of Dominance, RC means C for Greater

Column and C for cancel. It means that the greater column should be

cancelled and smaller column should be retained.

Fourth column being greater should be cancelled and smaller fi rst column

should be retained as follows

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Now compare first row with second row, here comparison is not possible.

Compare first row with third row, we came to know First row I < Third

row III.

According to the Principle of Dominance, RC means R for Greater Row

and R for Retain. It means that the greater row should be retained and

smaller row should be cancelled.

First row I < Third row III i.e. third row will be retained and first row will

be cancelled as follows

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Compare second row with third row, we came to know second row II <

Third row III.

According to the Pr inciple of Dominance, RC means R for Greater Row

and R for Retain. It means that the greater row should be retained and

smaller row should be cancelled.

munotes.in

## Page 112

112

Operation Research

Second row II < Third row III i.e. third row will be retained and second

row will be cancelled as f ollows

Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Now compare column wise first column (value 6) is greater than second

column (value 5).

According to the Principle of Dominance, RC means C for Grea ter

Column and C for cancel. It means that the greater column should be

cancelled and smaller column should be retained.

First column being greater should be cancelled and smaller second column

should be retained as follows

Player Y

1 2 3 4 5

Play er X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Now only remaining comparison is in between second column and third

column.

Second column 2< Third column 3.

According to the Principle of Dominance, RC means C for Greater

Column and C for cancel. It means that the greater column should be

cancelled and smaller column should be retained.

Third column being greater should be cancelled and smaller second

column should be retained as follows

munotes.in

## Page 113

113

Game Theory Player Y

1 2 3 4 5

Player X I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

Hence only reminder cell in the given matrix is 5 representing the value of

game. The corresponding optimum strategy for player X is third III

strategy and for player Y is second strategy 2.

Example 5. Solve the following game directly.

Player B

B1 B2 B3 B4

Player A A1 7 6 8 9

A2 -4 -3 9 10

A3 3 0 4 2

A4 10 5 -2 0

Solution:

Solve the following game directly means by using pure strategy game as

follows

1. Maximizing and Minimizi ng Player: In the payoff matrix,

maximizing players’ strategy (Player A) should be written in the row and

minimizing players’ strategy (Player B) should be written in the column.

2. Row Maxi -min Strategy: In the row, maximum values from the

minimum values of the given rows are taken. In simple words, at first row

minima values should be taken for all rows

Player B Row

Minima B1 B2 B3 B4

Player A A1 7 6 8 9 6

A2 -4 -3 9 10 -4

A3 3 0 4 2 0

A4 10 5 -2 0 -2

and then maximum value (6) from all ro w minima values (6, -4,0,-2) are

taken called as Row Maxi -min value (6).

munotes.in

## Page 114

114

Operation Research 3. Column Mini -max Strategy: In the column , minimum values from the

maximum values of the given columns are taken. In simple words, at first

column maxima values should be taken for a ll columns

Player B

B1 B2 B3 B4

Player A A1 7 6 8 9

A2 -4 -3 9 10

A3 3 0 4 2

A4 10 5 -2 0

Column Maxima 10 6 9 10

and then minimum value (6) from all column maxima values (10,6,9,10)

are taken called as Column Mini-max value (6).

4. Compari ng Row Maxi -min and Column Mini -max

values: The Row Maxi -min (6) and Column Mini -max values (6) are

compared and as these values are same then there exists a saddle point

representing the value of the game.

5. Saddle Point: The saddle point (6) is the po int of intersection of row

and column of Row Maxi -min and Column Mini -max values. This saddle

point represents the value of the game.

V= Value of the Game=6 and the corresponding optimum strategy for

player A is A1 strategy and for Player B is B2 strategy .

Example 6.

4.6 LIMITATIONS OF GAME THEORY

1. Players of game are not competent to know their own and competitors

pay off values. Hence the application of game theory is not realistic in

nature.

2. The theory of game theory is restricted to two playe rs’ duopoly, but the

situation of many players are complex and difficult to solve.

3. Zero sum game situations are not realistic in nature.

4. Players do not have complete knowledge of the strategies and hence the

strategies of Maximin and Minimax is not applicable for conservative

cases and risk averse cases of the players.

4.7 SUMMARY

Today, business world is complex, dynamic, and competitive in nature.

The monopoly is quite observed. Every business firm tries to win the munotes.in

## Page 115

115

Game Theory game by defeating other players i n the game using different strategies.

Game Theory is the competitive situation of business players in the

business competitive environment. Game theory is the study of operations

research technique involving appropriate use of strategies to win the

game. Thus Game theory is the branch of Operations Research dealing

with quantitative decision making when at least two players are involved

in the conflicting and competitive environment, resulting in success and

failure of players. Game is a particular busines s situation where at least

two players are involved to overcome the other player using optimum

strategy and to get maximum output using different strategies . The types

of games are Two Person Game, Multiple Person Game, Zero Sum Game,

Non-Zero Sum Game and Two Person Zero Sum Game. In the pure

strategy game, players use only one strategy throughout the game. The

pure strategy indicates that there is no other combination of strategy used

by the game player. In the mixed strategy game, players use different

strateg ies throughout the game. The mixed strategy indicates that there is

other combination of strategies used by the game player. The Principle of

Dominance states that, if a strategy of a player dominates over another

strategy in all conditions (that i s for all counter strategies by other player),

then the later strategy (being dominated) can be ignored. A strategy

dominates over the other strategy, only if it is preferable over the other,

under all conditions.

4.8 SELF -ASSESSMENT QUESTIONS

Q1. Expla in the Meaning and Concept of Game Theory.

Q2. Describe various Terminologies in Game Theory.

Q3. What are types of Game? Explain in depth.

Q4. Explain Principle of Dominance with practical example.

Q5. Describe Limitations of Game Theory.

Q6. Solve the following game directly and by using Principle of

Dominance

Player B

1 2 3 4 5

Player A I 1 3 2 7 4

II 3 4 1 5 6

III 6 5 7 6 5

IV 2 0 6 3 1

munotes.in

## Page 116

116

Operation Research Q7. Solve the following game directly and by using Principle of

Dominance

Player B

1 2 3 4 5 6

Player A I 4 2 0 2 1 1

II 4 3 1 3 2 2

III 4 3 7 -5 1 2

IV 4 3 4 -1 2 2

V 4 3 3 -2 2 2

munotes.in

## Page 117

117 5

DECISION THEORY

Decision Theory - Under Risk, Uncertainty, and decision tree

Unit Structure

5.0 Objectives

5.1 Introduction

5.2 Certain Key Issues in Decision Theory

5.3 Marginal Analysis

5.4 The steps of decision -making process.

5.5 Decision under va rious decision -making environments.

5.6 Decision -making under uncertainty

5.7 Probability estimates using Bayesian analysis.

5.8 Decision trees for making decision.

5.9 Summary

5.10 Exercises (solved examples)

5.0 OBJECTIVES

After reading this unit, you s hould be able to:

• structure a decision problem involving various alternatives and

uncertainties in outcomes

• apply marginal analysis for solving decision problems under

uncertainty

• analyse sequential problems using decision tree approach

• appreciate the use of utility theory in decision -making

• analyse uncertain situations where probabilities of outcomes are not

known.

5.1 INTRODUCTION

In every sphere of our life we need to take various kinds of decisions. The

ubiquity of decision problems, together wit h the need to make good

decisions, have led many people from different time and fields, to analyse

the decision -making process. A growing body of literature on Decision

Analysis is thus found today. The analysis varies with the nature of the munotes.in

## Page 118

118

Operation Research decision probl em, so that any classification base for decision problems

provides us with a means to segregate the Decision Analysis literature. A

necessary condition for the existence of a decision problem is the presence

of alternative ways of action. Each action leads to a consequence through

a possible set of outcome, the information on which might be known or

unknown. One of the several ways of classifying decision problems has

been based on this knowledge about the information on outcomes.

Broadly, two classificatio ns result:

a) The information on outcomes are deterministic and are known with

certainty, and

b) The information on outcomes are probabilistic, with the probabilities

known or unknown.

The former may be classified as Decision Making under certainty, while

the latter is called Decision Making under uncertainty. The theory that has

resulted from analysing decision problems in uncertain situations is

commonly referred to as Decision Theory. With our background in the

Probability Theory, we are in a position to u ndertake a study of Decision

Theory in this unit. The objective of this unit is to study certain methods

for solving decision problems under uncertainty. The methods are

consequent to certain key issues of such problems. Accordingly, in the

next section we discuss the issues and in subsequent sections we present

the different methods for resolving them.

The success or failure that an individual or organization experiences,

depends to a large extent, on the ability of making acceptable decisions on

time. To arrive at such a decision, a decision -maker needs to enumerate

feasible and viable courses of action (alternatives or strategies), the

projection of consequences associated with each course of action, and a

measure of effectiveness (or an objective) to id entify the best course of

action.

Decision theory is both descriptive and prescriptive business modeling

approach to classify the degree of knowledge and compare expected

outcomes due to several courses of action. The degree of knowledge is

divided into fo ur categories: complete knowledge (i.e. certainty),

ignorance, risk and uncertainty.

5.2 CERTAIN KEY ISSUES IN DECISION THEORY

Different issues arise while analysing decision problems under uncertain

conditions of outcomes. Firstly, decisions we take can be viewed either as

independent decisions, or as decisions figuring in the whole sequence of

decisions that are taken over a period of time. Thus, depending on the

planning horizon under consideration, as also the nature of decisions, we

have either a sing le stage decision problem, or a sequential decision

problem. In real life, the decision maker provides the common thread, and

perhaps all his decisions, past, present and future, can be considered to be

sequential. The problem becomes combinatorial, and he nce difficult to munotes.in

## Page 119

119

Decision Theory solve. Fortunately, valid assumptions in most of the cases help to reduce

the number of stages, and make the problem tractable.

Irrespective of the type of decision model, following essential components

are common to all:

Decision alterna tives: There is a finite number of decision alternatives

available to the decision -maker at each point in time when a decision is

made. The number and type of such alternatives may depend on the

previous decisions made and their outcomes. Decision alternat ives may be

described numerically, such as stocking 100 units of a particular item, or

non-numerically, such as conducting a market survey to know the likely

demand of an item.

States of nature : A state of nature is an event or scenario that is not under

the control of decision makers. For instance, it may be the state of

economy (e.g. inflation), a weather con dition, a political development etc.

The states of nature may be identified through Scenario Analysis where a

section of people are interviewed – stakeholders, long -time managers, etc.,

to understand states of nature that may have serious impact on a decision.

The states of nature are mutually exclusive and collectively exhaustive

with respect to any decision problem. The states of nature may be

descri bed numerically such as, demand of 100 units of an item or non-

numerically such as, employees strike, etc.

Payoff It is a numerical value (outcome) obtained due to the application of

each possible combination of decision alternatives and states of nature.

The payoff values are always conditional values because of unknown

states of nature.

The payoff values are measured within a specified period (e.g. within one

year, month, etc.) called the decision horizon . The payoffs in most

decisions are monetary. Payof fs resulting from each possible combination

of decision alternatives and states of natures are displayed in a matrix

(also called payoff matrix ) form.

Courses of Action

(Alternatives)

Sates of

Nature Probability S1 S2 … Sn

N1 P1 P11 P21 … P1n

N2 P2 P12 P22 … P2n

… … … … … …

Nm Pn P1n P2n … Pmn

munotes.in

## Page 120

120

Operation Research 5.3 MARGINAL ANALYSIS

Expected value can be used while deciding on one alternative from among

several alternative courses of actions, each of which is characterized by a

set of uncertain outcomes. It is easy to see that the computations become

tedious as the number of values, the random variable can take, increases.

Consider the example of the newspaper vendor. Instead of weekly seven

values of the demand of the newspapers, if the demand could take, say,

twenty values, with different chances of occurrence of each value, the

computation would become very tedious. In such cases, marginal analysis

is very helpful. In this section, we explain the concept behind this

analysis.

Consider the demand of the n ewspaper vendor. Let us assume that the

newspaper man has found from the past data that the demand can take

values ranging from 31, 32... to 50. For easy representation, let us assume

that each of these values has got an equal chance of occurrence, viz., 1 /20.

The problem is to decide on the number of copies to be ordered.

Marginal Analysis proceeds by examining whether ordering an additional

unit is worthwhile or not. Thus, we will order X copies, provided ordering

the Xth copy is worthwhile but ordering the (X+1)th copy is not. To find

out whether ordering X copies are worthwhile, we note the following.

Ordering of the Xth copy may meet with two consequences, depending on

the occurrences of two events:

A. The copy can be sold.

B. The copy cannot be sold .

The Xth copy can be sold only if the demand exceeds or equals X,

whereas, the copy cannot be sold if the demand turns out to be less than X.

Also, if event A occurs, we will make a profit of 50 p. on the extra copy,

and if even B occurs, there will be a loss of 30 p. As this profit and loss

pertains to the additional or marginal unit, these are referred to as

marginal profit or loss and the resulting analysis is called marginal

analysis.

Using the following notations:

Kl = Marginal profit = 50p.

K2 = Marginal loss = 30p.

P(A) = Probability (Demand ≥ X) = 1 -Probability (Demand ≤ X - 1).

P(B) = Probability (Demand < X) = Probability (Demand ≤ X - 1).

We can write down the expected marginal profit and expected marginal

loss as:

Expected Marginal Profit = Kl P(A)

Expected Marginal Loss = K2 P(B) munotes.in

## Page 121

121

Decision Theory Ordering the Xth

copy is worthwhile only if the expected profit due to it is

more than the expected loss, so that

Kl P(A) ≥ K2 P(B)

Now, if F(D) denotes the c.d.f. of demand, then by definition,

Probability D emand ≤(X-1) ± F(X -1)

Hence, Kl [1-F(X-1)] ≥ K2 F(X-1)

or;

K1 - Kl F(X-1) - K2F(X-1) ≥ 0

Thus, if condition 1 holds well, it is worthwhile to order the Xth

copy.

If the optimal decision is to order X copies, then ordering the (X+1)th

copy

will not be worthwhile, i.e. the expected marginal profit due to the

(X+1)th

copy should be less than the expected loss.

Proceeding with the analysis in the same way as above, we have:

Expected Marginal Profit = K1 Probability (Demand ≥ X + 1)

= Kl [1 – F(X)]

Expe cted Marginal Loss = K 2 F(X)

∴ For the (X+1)th

copy: Kl [1-F(X)] K2 ≤F(X)

From conditions (1) and (2) and the definition of Fractile, it is clear that X

will be the

the fractile of the Demand distribution.

Thus, for our problem, given the above result, all that we have to do is to

calculate

and find the Kth fractile of the distribution, which will give us the required

answer.

In our problem:

K = [0.5 / (0.5 + 0.3)] = 0.625 and the 0.625th fractile is 43.

∴The optimal decision is to order 13 copies. munotes.in

## Page 122

122

Operation Research The above shows how marginal analysis helps us in arriving at the optimal

decision with very little computation. This is especially useful when the

random variable of interest takes a large number of values. Though we

have demonstrated this for a discret e demand distribution the same logic

can be shown to be applicable for continuous distributions also. Instead of

the distribution we have taken, if we would have assumed that demand is

normal with a specific μ and σ, then also the same Kth fractile of N (μ ,σ)

would have given us the optimal decision.

5.4 THE STEPS OF DECISION -MAKING PROCESS

The decision -making process involves the following steps:

1. Identify and define the problem.

2. List all possible future events (not under the control of decision -make r)

that are likely to occur.

3. Identify all the courses of action available to the decision -maker.

4. Express the payoffs ( pij) resulting from each combination of course of

action and state of nature.

5. Apply an appropriate decision theory model to selec t the best course of

action from the given list on the basis of a criterion (measure of

effectiveness) to get optimal (desired) payoff.

Example 5.1 A firm manufactures three types of products. The fixed and

variable costs are given below:

Fixed Cost (Rs) Variable Cost per Unit (Rs)

Product A : 25,000 12

Product B : 35,000 9

Product C : 53,000 7

The likely demand (units) of the products is given below:

Poor demand : 3,000

Moderate demand : 7,000

High demand : 11,000

If the sale price of each t ype of product is Rs 25, then prepare the payoff

matrix.

Solution Let D1, D2 and D3 be the poor, moderate and high demand,

respectively. The payoff is determined as:

Payoff = Sales revenue – Cost munotes.in

## Page 123

123

Decision Theory The calculations for payoff (in ’000 Rs) for each pair of al ternative

demand (course of action) and the types of product (state of nature) are

shown below:

D1A = 3 × 25 – 25 – 3 × 12 = 14 D2A = 7 × 25 – 25 – 7 × 12 = 66

D1B = 3 × 25 – 35 – 3 × 19 = 13 D2B = 7 × 25 – 35 – 7 × 19 = 77

D1C = 3 × 25 – 53 – 3 × 17 = 1 D2C = 7 × 25 – 53 – 7 × 17 = 73

D3A = 11 × 25 – 25 – 11 × 12 = 118

D3B = 11 × 25 – 35 – 11 × 19 = 141

D3C = 11 × 25 – 53 – 11 × 17 = 145

The payoff values are shown in Table below:

Product Type Alternative demand in (‘000) Rs.

D1 D2 D3

A 14 66 118

B 13 77 141

C 1 73 145

5.5 DECISION UNDER VARIOUS DECISION -MAKING

ENVIRONMENTS

To arrive at an optimal decision it is essential to have an exhaustive list of

decision -alternatives, knowledge of decision environment, and use of

appropriate quantitative approach for decision -making.

In this section three types of decision -making environments: certainty ,

uncertainty , and risk , have been discussed. The knowledge of these

environments helps in choosing the quantitative approach for decision -

making.

Type 1: Decision -Making under Certainty

In this decision -making environment, decision -maker has complete

knowledge (perfect information) of outcome due to each decision -

alternative (course of action). In such a case he would select a decision

alternative that yiel ds the maximum return (payoff) under known state of

nature. For example, the decision to invest in National Saving Certificate ,

Indira Vikas Patra , Public Provident Fund, etc., is where complete

information about the future return due and the principal at maturity is

known.

munotes.in

## Page 124

124

Operation Research Type 2: Decision -Making under Risk

In this decision -environment, decision -maker does not have perfect

knowledge about possible outcome of every decision alternative. It may

be due to more than one states of nature. In such a case , he ma kes an

assumption of the probability for occurrence of particular state of nature.

Type 3 : Decision -Making under Uncertainty

In this decision environment, decision -maker is unable to specify the

probability for occurrence of particular state of nature. How ever, this is

not the case of decision -making under ignorance, because the possible

states of nature are known . Thus, decisions under uncertainty are taken

even with less information than decisions under risk. For example, the

probability that Mr . X will b e the prime minister of the country 15years

from now is not known.

5.6 DECISION -MAKING UNDER UNCERTAINTY

When probability of any outcome cannot be quantified, the decision -

maker must arrive at a decision only on the actual conditional payoff

values, keepin g in view the criterion of effectiveness (policy).

The following criteria of decision -making under uncertainty have been

discussed in this section:

Optimism (Maximax or Minimin) criterion

Pessimism (Maximin or Minimax) criterion

Equal probabilities (Lapla ce) criterion

Coefficient of optimism (Hurwiez) criterion

Regret (salvage) criterion.

i) Optimism (Maximax or Minimin) Criterion

In this criterion the decision -maker ensures that he should not miss the

opportunity to achieve the largest possible profit (ma ximax) or the lowest

possible cost (minimin). Thus, he selects the decision alternative that

represents the maximum of the maxima (or minimum of the minima)

payoffs (consequences or outcomes).

The working method is summarized as follows:

(a) Locate the max imum (or minimum) payoff values corresponding to

each decision alternative.

(b) Select a decision alternative with best payoff value (maximum for

profit and minimum for cost).

Since in this criteri on the decision -maker selects a decision -alternative

with l argest (or lowest) possible payoff value, it is also called an

optimistic decision criterion.

munotes.in

## Page 125

125

Decision Theory ii) Pessimism (Maximin or Minimax) Criterion

In this criterion the decision -maker ensures that he would earn no less (or

pay no more) than some specified amount. Thus, he selects the decision

alternative that represents the maximum of the minima (or minimum of

the minima in case of loss) payoff in case of profits. The working method

is summarized as follows:

(a) Locate the minimum (or maximum in case of profit) pa yoff value in

case of loss (or cost) data corresponding to each decision alternative.

(b) Select a decision alternative with the best payoff value (maximum for

profit and minimum for loss or cost).

Since in this criterion the decision -maker is conservative about the future

and always anticipates the worst possible outcome (minimum for profit

and maximum for cost or loss), it is called a pessimistic decision criterion .

This criterion is also known as Wald’s criterion .

iii) Equal Probabilities (Laplace) Crite rion

Since the probabilities of states of nature are not known, it is assumed that

all states of nature will occur with equal probability, i.e. each state of

nature is assigned an equal probability. As states of nature are mutually

exclusive and collective ly exhaustive, so the probability of each of these

must be: 1/(number of states of nature). The working method is

summarized as follows:

(a) Assign equal probability value to each state of nature by using the

formula:

1 ÷ (number of states of nature) .

(b) Compute the expected (or average) payoff for each alternative (course

of action) by adding all the payoffs and dividing by the number of

possible states of nature, or by applying the formula:

(Probability of state of nature j ) × ( Payoff value for the combi nation of

alternative I and state of nature j .)

(c) Select the best expected payoff value (maximum for profit and

minimum for cost).

This criterion is also known as the criterion of insufficient reason. This is

because except in a few cases, some informati on of the likelihood of

occurrence of states of nature is available.

iv) Coefficient of Optimism (Hurwicz) Criterion

This criterion suggests that a decision -maker should be neither completely

optimistic nor pessimistic and, therefore, must display a mixtur e of both.

Hurwicz, who suggested this criterion, introduced the idea of a coefficient

of optimism (denoted by α) to measure the decision -maker’s degree of

optimism. This coefficient lies between 0 and 1, where 0 represents a munotes.in

## Page 126

126

Operation Research complete pessimistic attitude about the future and 1 a complete optimistic

attitude about the future. Thus, if α is the coefficient of optimism, then (1

– α) will represent the coefficient of pessimism.

The Hurwicz approach suggests that the decision -maker must select an

alternative that maximizes

H (Criterion of realism) = α (Maximum in column ) + (1 – α) (Minimum in

column )

The working method is summarized as follows:

(a) Decide the coefficient of optimism α (alpha) and then coefficient of

pessimism (1 – α).

(b) For each decision alternative select the largest and lowest payoff value

and multiply these with α and (1 – α) values, respectively. Then calculate

the weighted average, H by using above formula.

(c) Select an alternative with best weighted average payoff value.

v) Regret (Savage) Criterion

This criterion is also known as opportunity loss decision criterion or

minimax regret decision criterion because decision -maker regrets for

choosing wrong decision alternative resulting in an opportunity loss of

payoff. Thus, he always intends to minimize this regret. The working

method is summarized as follows:

(a) From the gi ven payoff matrix, develop an opportunity -loss (or regret)

matrix as follows:

(i) Find the best payoff corresponding to each state of nature

(ii) Subtract all other payoff values in that row from this value.

(b) For each decision alternative identify the w orst (or maximum regret)

payoff value. Record this value in the new row.

(c) Select a decision alternative resulting in a smallest anticipated

opportunity -loss value.

Example 5.2 Given the following payoff tables where the table represents

profits:

Alterna tives States of Nature

S1 S2 S3 S4

A1 3 5 8 -1

A2 6 5 2 0

A3 0 5 6 4

munotes.in

## Page 127

127

Decision Theory Calculate the payoff using:

(a) Maximax, (b) Maximin,

Decision making under uncertainty.

a) Maximax :

Max( Max Ai) = Max ( 8, 6, 6 ) = 8

Decision : Select A1

b) Maxmin :

Max(Min A i) =Max ( -1, 0 ,0) =0

Decision : Select A2 or A3

Example 5.3 A food products’ company is contemplating the introduction

of a revolutionary new product with new packaging or replacing the

existing product at much higher price (S 1). It may even make a moder ate

change in the composition of the existing product, with a new packaging

at a small increase in price (S 2), or may mall a small change in the

composition of the existing product, backing it with the word ‘New’ and a

negligible increase in price (S 3).

The three possible states of nature or events are: (i) high increase in sales

(N1), (ii) no change in sales (N 2) and (iii) decrease in sales (N 3). The

marketing department of the company worked out the payoffs in terms of

yearly net profits for each of the strategies of three events (expected

sales). This is represented in the following table:

Strategies States of Nature

N1 N2 N3

S1 700 300 150

S2 500 450 0

S3 300 300 300

Which strategy should the concerned executive choose on the basis of

(a) Maximin criterion (b) Maximax criterion

(c) Minimax regret criterion (d) Laplace criterion?

Solution: The payoff matrix is rewritten as follows:

(a) Maximin Criterion

munotes.in

## Page 128

128

Operation Research States of Nature Strategies

S1 S2 S3

N1 700 500 300

N2 300 450 300

N3 150 0 300

Column

Minimum 150 0 300

Maximum Payoff -> 300

The maximum of column minima is 300. Hence, the company should

adopt strategy S3.

(b) Maximax Criterion

States of Nature Strategies

S1 S2 S3

N1 700 500 300

N2 300 450 300

N3 150 0 300

Column

Maximum 700 500 300

700 <- Maximum Payoff

The maximum of column maxima is 7,00,000. Hence, the company should

adopt strategy S1.

(c) Minimax Regret Criterion Opportunity loss table is shown below:

States of Nature Strategies

S1 S2 S3

N1 700-700=0 700-500=200 700-300=400

N2 450-300=150 450-450=0 450-300=150

N3 300-150=150 300-0=300 300-300=0

Column

Maximum 150 300 400

150 <- Minimum Regret

munotes.in

## Page 129

129

Decision Theory Hence the company should adopt minimum opportunity loss strategy, S1.

(d) Laplace Criterion Assuming that each state of nat ure has a probability

1/3 of occurrence. Thus,

Strategies Expected Return (Rs)

S1 (700 + 300 + 150)/3 = 383.33 <-Largest Payoff S2 (500 + 450 + 0)/3 = 316.66

S3 (300 + 300 + 300)/3 = 300

Since the largest expected return is from strategy S1, the execu tive must

select strategy S1.

5.7 PROBABILITY ESTIMATES USING BAYESIAN

ANALYSIS

In this decision -making environment, decision -maker has sufficient

information to assign probability to the likely occurrence of each outcome

(state of nature). Knowing the pro bability distribution of outcomes (states

of nature), the decision -maker needs to select a course of action resulting a

largest expected (average) payoff value. The expected payoff is the sum of

all possible weighted payoffs resulting from choosing a decis ion

alternative.

The widely used criterion for evaluating decision alternatives (courses of

action) under risk is the Expected Monetary Value (EMV) or Expected

Utility.

(a) Expected Monetary Value (EMV)

The expected monetary value (EMV) for a given course of a ction is

obtained by adding payoff values multiplied by the probabilities

associated with each state of nature. Mathematically, EMV is stated as

follows:

Where, m = number of possible states of nature

pi= probability of occurrence of state of nature, Ni

pij= payoff associated with state of nature Ni and course of action, Sj

The Procedure

1. Construct a payoff matrix listing all possible courses of action and

states of nature. Enter the conditional payoff values associated with each

possible combination of course of action and state of nature along with the

probabilities of the occurrence of each state of nature. munotes.in

## Page 130

130

Operation Research 2. Calculate the EMV for each course of action by multiplying the

conditional payoffs by the associated probabilities and adding these

weighted va lues for each course of action.

3. Select the course of action that yields the optimal EMV.

Example 5.4 Mr X flies quite often from town A to town B. He can use

the airport bus which costs Rs 25 but if he takes it, there is a 0.08 chance

that he will miss the flight. The stay in a hotel costs Rs 270 with a 0.96

chance of being on time for the flight. For Rs 350 he can use a taxi which

will make 99 per cent chance of being on time for the flight. If Mr X

catches the plane on time, he will conclude a business transaction that will

produce a profit of Rs 10,000, otherwise he will lose it. Which mode of

transport should Mr X use? Answer on the basis of the EMV criterion.

Solution: Computation of EMV associated with various courses of action

is shown in Table.

States of

Nature Courses of Action

Bus Stay in Hotel Taxi

Cost Prob. Expected

Value Cost Prob. Expected

Value Cost Prob. Expected

Value

Catches

the Flight 1000

-25

=

9975 0.92 9177 10000

-270

=

9730 0.96 9340.80 10000 –350 =

9650 0.99 9553.50

Miss th e

Flight - 25 0.08 - 2.00 - 270 0.04 - 10.80 - 350 0.01 - 3.5

Expected

Monetary

Value

(EMV) 9175 9330 9550

Since EMV associated with course of action ‘Taxi’ is largest (= Rs 9,550),

it is the logical alternative.

5.8 DECISION TREES FOR MAKING DECISI ON

Decision -making problems discussed earlier were limited to arrive at a

decision over a fixed period of time. That is, payoffs, states of nature,

courses of action and probabilities associated with the occurrence of states

of nature were not subject to c hange. However, situations may arise when

a decision -maker needs to revise his previous decisions due to availability

of additional information. Thus he intends to make a sequence of

interrelated decisions over several future periods. Such a situation is c alled

a sequential or multiperiod decision process . For example, in the process

of marketing a new product, a company usually first go for ‘Test

Marketing’ and other alternative courses of action might be either munotes.in

## Page 131

131

Decision Theory ‘Intensive Testing’ or ‘Gradual Testing’. Gi ven the various possible

consequences – good, fair, or poor, the company may be required to

decide between redesigning the product, an aggressive advertising

campaign or complete withdrawal of product, etc. Based on this decision

there might be an outcome that leads to another decision and so on.

A decision tree analysis involves the construction of a diagram that shows,

at a glance, when decisions are expected to be made – in what sequence,

their possible outcomes, and the corresponding payoffs. A decision tree

consists of nodes, branches, probability estimates, and payoffs . There are

two types of nodes:

Decision (or act) node: A decision node is represented by a square

and represents a point of time where a decision -maker must select one

alternative course of action among the available. The courses of action are

shown as branches or arcs emerging out of decision node.

Chance (or event) node: Each course of action may result in a chance

node . The chance node is represented by a circle and indicates a point of

time where the decision -maker will discover the response to his decision.

Branches emerge from and connect various nodes and represent either

decisions or states of nature. There are two types of branches:

Decision branch: It is the branch leading away from a decision node

and represents a course of action that can be chosen at a decision point.

Chance branch: It is the branch leading away from a chance node and

represents the state of nature of a set of chance events. The assumed

probabilities of the s tates of nature are written alongside their respective

chance branch.

Terminal branch: Any branch that makes the end of the decision tree

(not followed by either a decision or chance node), is called a terminal

branch. A terminal branch can represent eith er a course of action. The

terminal points of a decision tree are supposed to be mutually exclusive

points so that exactly one course of action will be chosen.

The payoff can be positive (i.e. revenue or sales) or negative (i.e.

expenditure or cost) and it can be associated either with decision or chance

branches.

An illustration of a decision tree is shown in Fig. below. It is possible for a

decision tree to be deterministic or probabilistic. It can also further be

divided in terms of stages – into single stage (a decision under condition

of certainty) and multistage (a sequence of decisions).

munotes.in

## Page 132

132

Operation Research

The optimal sequence of decisions in a tree is found by starting at the

right -hand side and rolling backwards . At each node, an expected return is

calculated (call ed position value). If the node is a chance node , then the

position value is calculated as the sum of the products of the probabilities

or the branches emanating from the chance node and their respective

position values. If the node is a decision node, then the expected return is

calculated for each of its branches and the highest return is selected. This

procedure continues until the initial node is reached. The position values

for this node correspond to the maximum expected return obtainable from

the dec ision sequence.

Example 5.5 You are given the following estimates concerning a

Research and Development programme:

Decision

(Di) Probability

of Decision

Di Given

Research R

P(Di | R ) Outcome

Number Probability

of Outcome

xi Given Di )

P(xi|Di ) Payoff

Value of

Outcome, xi

(Rs ’000)

Develop 0.5 1 0.6 600

2 0.3 -100

3 0.1 0

0.5 1 0.0 600

Do not

develop 2 0.0 -100

3 1.1 0

munotes.in

## Page 133

133

Decision Theory Construct and evaluate the decision tree diagram for the above data. Show

your workings for evaluation.

Solution: The decis ion tree of the given problem along with necessary

calculations is shown in Fig.

Example 5.6 A glass factory that specializes in crystal is developing a

substantial backlog and for this the firm’s management is considering

three courses of action: To a rrange for subcontracting ( S1), to begin

overtime production ( S2), and to construct new facilities ( S3). The correct

choice depends largely upon the future demand, which may be low,

medium, or high. By consensus, management ranks the respective

probabiliti es as 0.10, 0.50 and 0.40. A cost analysis reveals the effect upon

the profits. This is shown in the table below:

Demand Probability Course of Action

S1 S2 S3

Subcontracting Begin

Overtime Construct

facilities

Low (L) 0.1 10 -20 -50

Medium

(M) 0.5 50 60 20

High (H) 0.4 50 100 200

Solution: A decision tree that represents possible courses of action and

states of nature is shown in Fig. In order to analyze the tree, we start

working backwards from the end branches. The most preferred decision at

the decision node 0 is found by calculating the expected value of each

decision branch and selecting the path (course of action) that has the

highest value. munotes.in

## Page 134

134

Operation Research

Since node 3 has the highest EMV, therefore, the decision at node 0 will

be to choose the course of action S3, i.e. construct new facilities.

5.9 SUMMARY

Decision Theory provides us with the framework and methods for

analysing decision problems under uncertainty. A decision problem under

uncertainty is characterized by different alternative courses of action and

uncertain outcomes corresponding to each action. The problems can

involve a single stage or a multi -stage decision process. Marginal Analysis

is helpful in solving single stage problems, whereas the Decision Tree

Approach is useful for solving m ulti-stage problems. In this unit we

examined Optimism (Maximax or Minimin) criterion, Pessimism

(Maximin or Minimax) criterion, Equal probabilities (Laplace) criterion,

Coefficient of optimism (Hurwiez) criterion and Regret (salvage) criterion

and the dec ision tree analysis.

5.10 EXERCISES

Exercise Example 1. The manager of a flower shop promises its

customers delivery within four hours on all flower orders. All flowers are

purchased on the previous day and delivered to Parker by 8.00 am the next

morning. The daily demand for roses is as follows.

Dozens of roses: 70 80 90 100

Probability: 0.1 0.2 0.4 0.3

The manager purchases roses for Rs 10 per dozen and sells them for Rs

30. All unsold roses are donated to a local hospital. How many dozens of

roses should Parker order each evening to maximize its profits? What is

the optimum expected profit?

Solution: The quantity of roses to be purchased per day is considered as

‘course of action’ and the daily demand of the roses is considered as a

‘state of nature’ because demand is uncertain with known probability.

From the data, it is clear that the flower shop must not purchase less than 7

or more than 10 dozen roses, per day. Also each dozen roses sold within a munotes.in

## Page 135

135

Decision Theory day y ields a profit of Rs (30 – 10) = Rs 20 and otherwise it is a loss of

Rs 10.

Thus

Marginal profit (MP) = Selling price – Cost = 30 – 10 = Rs 20

Marginal loss (ML) = Loss on unsold roses = Rs 10

Using the information given in the problem, the various conditi onal profit

(payoff) values for each combination of decision alternatives and state of

nature are given by Conditional profit = MP × Roses sold – ML × Roses

not sold

Where, D = number of roses sold within a day and S = number of roses

stocked.

The result ing conditional profit values and corresponding expected

payoffs are computed in the table below:

States if

Nature

(Demand

per Day) Probability Conditional profit

(Rs.) due to courses

of action

(Purchase per Day) Conditional profit (Rs.) due to

courses of action

(Purchase per Day)

70 80 90 100 70 80 90 100

(1) (2) (3) (4) (5) (1)X(2) (1)X(3) (1)X(4) (1)X(5)

70 0.1 140 130 120 110 14 13 12 11

80 0.2 140 160 150 140 28 32 30 28

90 0.4 140 160 180 170 56 64 72 68

100 0.3 140 160 180 200 42 48 54 60

Expected Monetary

Value 140 157 168 167

Since the highest EMV of Rs 168 corresponds to the course of action 90,

the flower shop should purchase nine dozen roses every day.

Exercise Example 2: The probability of demand for hiring cars on any

day in a given city is as follows:

No. of cars demanded: 0 1 2 3 4

Probability: 0.1 0.2 0.3 0.2 0.2

Cars have a fixed cost of Rs 90 each day to keep the daily hire charges

(variable costs of running) Rs. 200. If the car -hire company owns 4 cars,

what i s its daily expectation? If the company is about to go into business

and currently has no car, how many cars should it buy? munotes.in

## Page 136

136

Operation Research Solution Given that Rs 90 is the fixed cost and Rs 200 is variable cost.

The payoff values with 4 cars at the disposal of decision -maker are

calculated as under:

No. of cars demanded :

0 1 2 3 4

Payoff (with 4 cars):

0 – 90 × 4 200 – 90 × 4 400 – 90 × 4 600 – 90 × 4 800 – 90 × 4

= – 360 = – 160 = 40 = 240 = 440

Thus, the daily expectation is obtained by multiplyi ng the payoff values

with the given corresponding probabilities of demand:

Daily Expectation =

(– 360)(0.1) + ( – 160)(0.2) + (40)(0.3) + (240)(0.2) + (440)(0.2) = Rs 80

The conditional payoffs and expected payoffs for each course of action are

shown in Ta bles.

Conditional Payoff Values

Demand

of Cars Probability Conditional Payoff (Rs.) due to Decision to

Purchase Cars

(Course of Action)

0 1 2 3 4

0 0.1 0 -90 -180 -270 -360

1 0.2 0 110 20 -70 -160

2 0.3 0 110 220 130 40

3 0.2 0 110 220 330 240

4 0.2 0 110 220 330 440

munotes.in

## Page 137

137

Decision Theory Expected Payoffs and EMV

Demand

of Cars Probability Conditional Payoff (Rs.) due to Decision to

Purchase Cars

(Course of Action)

0 1 2 3 4

0 0.1 0 -9 -18 -27 -36

1 0.2 0 22 4 -14 -32

2 0.3 0 33 66 39 12

3 0.2 0 22 44 66 48

4 0.2 0 22 44 66 88

EMV 0 90 140 130 80

Since the EMV of Rs 140 for the course of action 2 is the highest, the

company should buy 2 cars.

munotes.in

## Page 138

138 6

WAITING LINES MODEL

Unit Structure

6.0 Objectives

6.1 Introduction

6.2 Characteristics of a Waiting Line or a Queuing Model

6.3 Notations and Symbols

6.4 Statistical methods in queuing

6.5 The M/M/l System

6.6 Summary

6.7 Exercises (solved examples)

6.0 OBJECTIVES

After studying this unit, you should be able to:

Identify the occurrence of waiting line or queuing in real life

situations.

Describe the characteristics of a queuing problem.

Use the statistical methods necessary to analyse queuing problems.

Apply the common queuing models in suitable problems.

Estimate the optimum parameters of a queuing model with respect to

cost and service level for M/M/1 system.

6.1 INTRODUCTION

The waiting line models or the queuing problem is identified by the

presence o f a group of customers who arrive randomly to receive some

service. The customer upon arrival may be attended to immediately or

may have to wait until the server is free. The service time required to

serve the customers is also a statistical variable. This methodology can be

applied in the field of business (banks, booking counters), industries

(servicing of machines), government (railway or post -office counters),

transportation (airport, harbor) and everyday life (elevators, restaurants,

and doctor’s chamb er).

The waiting line or queuing models are basically relevant to service

oriented organisations and suggest ways and means to improve the

efficiency of the service. An improvement of service level is always

possible by increasing the number of employees. Apart from increasing

the cost an immediate consequence of such a step is unutilized or idle time munotes.in

## Page 139

139

Waiting Lines Model of the servers. In addition, it is unrealistic to assume that a large -scale

increase in staff is possible in an organisation. Queuing methodology

indicates th e optimal usage of existing manpower and other resources to

improve the service. It can also indicate the cost implications if the

existing service facility has to be improved by adding more servers.

The relationship between queuing and service rates can b e

diagrammatically illustrated using the cost curves shown in Figure.

At a slow service rate, queues build up and the cost of queuing increases.

An ideal service unit will minimise the operating cost of the entire system.

Many real -life situations in which study of queuing theory can provide

solution to waiting line problems are listed below:

Situation Customers Service Facilities

Petrol pumps (stations) Automobiles Pumps

Hospital Patients Doctors/Nurses/Rooms

Airport Aircraft Runways

Post office Letters Sorting system

Job interviews Applicants Interviewers

Cargo Trucks Loader/unloaders

Workshop Machines/Cars Mechanics/Floor space

Factory Employees Cafeteria/Punching Machine

6.2 CHARACTERISTICS OF A WAITING LIN E OR A

QUEUEING MODEL

A queuing system can be described by the following components:

Arrival

The statistical pattern of the arrival can be indicated through the

probability distribution of the number of arrivals in an interval. This is a

discrete random variable. Alternatively, the probability distribution of the

time between successive arrivals (known as inter -arrival time) can also

be studied to ascertain the stochastic aspect of the problem. This variable

is continuous in nature.

munotes.in

## Page 140

140

Operation Research

Cost Structure of a Queuing Problem

The probability distribution of the arrival pattern can be identified through

analysis of past data. The discrete random variable indicating the number

of arrivals in a time interval and the continuous random variable

indicating the time between two successive arrivals (interarrival time)

are obviously inter related. A remarkable result in this context is that if the

number of arrivals follows a Poisson distribution , the corresponding

interarrival time follows an exponential distribution. This property is

frequently used to derive elegant results on queuing problems.

Service

The time taken by a server to complete service is known as service time.

The service time is a statistical variable and can be studied either as the

number of services com pleted in a given period of time or the completion

period of a service. The data on actual service time should be analyzed to

find out the probability distribution of service time.

Server

The service may be offered through a single server such as a ticket counter

or through several channels such as a train arriving in a station with

several platforms.

Sometimes the service is to be carried out sequentially through several

phases known as multiphase service. In government, the papers move

through a number of phases in terms of official hierarchy till they arrive at

the appropriate level where a decision can be taken.

Time spent in the queuing system

The time spent by a customer in a queuing system is the sum of waiting

time before service and the service time . munotes.in

## Page 141

141

Waiting Lines Model Queue discipline

The queue discipline indicates the order in which members of the queue

are selected for service. It is most frequently assumed that the customers

are served on a first' come first serve basis. This is commonly referred to

as FIFO (first in, first out) system. Occasionally, a certain group of

customers receive priority in service over others even if they arrive late.

This is commonly referred to as priority queue; the queue discipline does

not always take into account the order of arrival. The server chooses one

of the customers to offer service at random. Such a system is known as

service in random order (SIRO). While allotting an item with high demand

and limited supply such as a test match cricketer share of a public limited

company, SIR O is the only possible way of offering service when it is not

possible to identify the order of arrival.

Size of a population

The collection of potential customers may be very large or of a moderate

size. In a railway booking counter the total number of po tential passengers

is so large that although theoretically finite it can be regarded as infinity

for all practical purposes. The assumption of infinite population is very

convenient for analysing a queuing model. However, this assumption is

not valid where the customer group is represented by a few looms in a

spinning mill that require operator facility from time to time. If the

population size is finite then the analysis of queuing model becomes more

involved.

Maximum size of a queue

Sometimes only a finit e number of customers are allowed to stay in the

system although the total number of customers in the population may or

may not be finite. For example, a doctor may make appointments with k

patients in a day. If the number of patients asking for appointmen t exceeds

k, they are not allowed to join the queue. Thus, although the size of the

population is infinite, the maximum number permissible in the system

is k.

Fig.: Schematic Representation of a Queuing Problem

munotes.in

## Page 142

142

Operation Research 6.3 NOTATIONS AND SYMBOL S

Kendall (Kendall, 1951) has introduced set of notations which have

become standard in the literature of queuing models. A general queuing

system is denoted by (a/b/c) : (d/e) where

a = probability distribution of the interarrival time.

b=probability distribution of the service time.

c=number of servers in the system.

d = maximum number of customers allowed in the system.

e= queue discipline.

In addition , the size of the population as mentioned in the previous section

is important for certain types of queui ng problem although not explicitly

mentioned in the Kendall's notation. Traditionally, the exponential

distribution in queuing problems is denoted by M. Thus (M/M/1) : (

/FIFO) indicates queuing system when the interarrival times and service

times are exponentially distributed having one server in the system with

first in first out discipline and the number of customers allowed in the

system can be infinite.

In general, the behaviour of a queuing system will depend upon time.

Such a system is said to be in a transient state. This usually occurs at an

early stage of formation of queues where its behavior is still dependent up

on the initial condition s. When sufficient time has elapsed since the

beginning of the operation (mathematically as the time approaches to

infinity) the behaviour of the system may become independent of time.

The system then is said to be in a steady state. Only steady state queuing

problems will be analyzed in this unit.

The following symbols will be used while studying queuing models.

n=number ofunitsinthesystemwhoarewaitingforserviceandwhoarebeingse

rved.

Pn(t)=transientstateprobabilitiesofexactlyncustomersinthesystemattimetass

umingthat the system has started its operation at time zero.

Pn=steady state probability of having n customers in the system.

£ =mean effective arrival rate (number of customer s arriving per unit time).

µ=mean service rate per busy server (number of custome rs served per unit

time)

C=number of parallel servers.

W(t)= density function of the waiting time. munotes.in

## Page 143

143

Waiting Lines Model Ws = expected waiting time per customer in the system including the

service time. Wq=expected waiting time per customer in the queue

excluding the service time.

Ls=expected number of customers in the system including those who are

receiving service.

Lq=expected number of customers in the queue excluding those who are

receiving service.

6.4 STATISTICAL METHODS IN QUEUEING

The arrival of customers, the departur e of customers after service and the

waiting time of a customer before being served in a queuing system are

random phenomena. In order to develop appropriate statistical model of

this problem the following assumptions are made:

1) If N(t) denotes the numbe r of arrivals or departures after service in the

timeinterval(0,t)thenN(t)has independentincrements. Thiscanbestatedst

atistically as follows. If t lare independent random variables

Thus, if the service comp onent is ignored the number of arrivals in the

interval (0,t) has the probability distribution of a Poisson variable with

parameter λ t which is the product of the arrival rate and the length of the

interval t. This probability law is known as the Poisson Process.

RelationshipbetweenPoissonProcessandExponentialProbabilityDistrib

ution

a) Consider a queuing model in which the number of arrivals in an interval

of length t follows a Poisson Process with arrival rate λ. If the

interarrival times are independent random variables, they must follow an

exponential distribution with density f(t) where

munotes.in

## Page 144

144

Operation Research It can be readily shown by integration that E(t) = 1 / £. Thus if the arrival

rate £=20/hour, the average time between two successive arrivals is 1/20

hour or 3 minut es.

b) If the interarrival times in a queuing system are independently,

identically distributed exponential random variables then the number of

arrivals in an interval follows a Poisson Process with arrival rate identical

with parameter of the exponential distribution.

c) Consider a random variable X with an exponential pr obability

distribution. Therefore , t>0

P(X>t+s | X>s) = P(X>t)

This property is important for solving queuing problems. Assuming that

when a customer arrives the service is in progress for s units of time. The

chance that the service will continue for at least an additional t unit is

identical with the probability that the service will prolong for at least t

units after a fresh start.

One way to look at this property is that the time alread y spent in the

system has no relevance to the additional time the customer i s likely to

spend in the system further. Thus, this property is sometimes referred to as

lack of memory or forgetfulness of the exponential distribution.

6.5 THE M/M/L SYSTEM

In this queuing model, it is assumed that the number of customers arriving

in a time interval t follows a Poisson Process with parameter λ.

Equivalently, the interval between any two successive arrivals is

exponentially distributed with parameter A. The time taken to complete a

single service is exponentially distributed with parameter µ. The numb er

of servers is one. Although not explicitly stated both the population and

the queue size can be infinity. The order of service is assumed to be FIFO.

Performance Measures of a Queuing System

The performance measures (operating characteristics) for the e valuation of

the performance of an existing queuing system, and for designing a new

system in terms of the level of service a customer receives as well as the

proper utilization of the service facilities are listed as follows:

1. Average (or expected) time spent by a customer in the queue and

system

Wq: Average time an arriving customer has to wait in a queue before

being served,

Ws: Average time an arriving customer spends in the system, including

waiting and service.

munotes.in

## Page 145

145

Waiting Lines Model 2. Average (expected) number of custo mers in the queue and system

Lq: Average number of customers waiting for service in the queue (queue

length)

Ls: Average number of customers in the system (either waiting for

services in the queue or being served ).

3. Value of time both for customers and s ervers

Pw : Probability that an arriving customer has to wait before being served

(also called blocking probability ).

ρ = λ / μ : Percentage of time a server is busy serving customers, i.e., the

system utilization.

Pn: Probability of n customers waiting fo r service in the queuing system.

Pd: Probability that an arriving customer is not allowed to enter in the

queuing i.e., system capacity is full.

4. Average cost required to operate the queuing system

• Average cost required to operate the system per unit o f time?

• Number of servers (service centres) required to achieve cost

effectiveness?

Transient -State and Steady -State

At the beginning of service operations, a queuing system is influenced by

the initial conditions, such as number of customers waiting for service and

percentage of time servers are busy serving customers, etc.

This initial period is termed as transient -state. However, after certain

period of time, the system becomes independent of the initial conditions

and enters into a steady -state condit ion.

To quantify various measures of system performance in each queuing

model, it is assumed that the system has entered into a steady -state.

Let Pn(t) be the probability that there are n customers in the system at a

particular time t. Any change in the va lue of Pn(t), with respect to time t,

is denoted by Pn′ (t). In the case of steady -state, we have:

munotes.in

## Page 146

146

Operation Research If the arrival rate of customers at the system is more than the service rate,

then a steady -state cannot be reached, regardless of the length of the

elapse d time.

Queue size, also referred as line length represents average number of

customers waiting in the system for service.

Queue length represents average number of customers waiting in the

system and being served.

Notations The notations used for analyzin g of a queuing system are as

follows:

n = number of customers in the system (waiting and in service)

Pn= probability of n customers in the system

λ = average customer arrival rate or average number of arrivals per unit of

time

in the queuing system

μ = average service rate or average number of customers served per unit

time at the place of service

λ / μ = ρ= Average service completion time(1/ μ) / A verage interarrival

time(1/ λ)

ρ = traffic intensity or server utilization factor

P0 = probability of no customer in the system

s = number of service channels (service facilities or servers)

N = maximum number of customers allowed in the system

Ls= average number of customers in the system (waiting and in service)

Lq= average number of customers in the queue (queue length)

Ws= average waiting time in the system (waiting and in service)

Wq= average waiting time in the queue

Pw = probability that an arriving customer has to wait (system being

busy),

1 – P0 = (λ/μ)

For achieving a steady -state condition, it is necessary that, λ/μ < 1 (i.e. the

arrival rate must be less than the service rate). Such a situation arises when

the queue length is limited, generally because of space, capacity limitation

or customer s balk.

munotes.in

## Page 147

147

Waiting Lines Model Relationships among Performance Measures

The following basic relationships hold for all infinite source queuing

models.

The general relationship among various performance measures is as

follows:

(i) Average number of customers in the system is equal to the average

number of customers in queue(line) plus average number of customers

being served per unit of time (system utilization).

Ls=Lq + Customer being served

= Lq+ λ / μ

The value of ρ =λ / μ is true for a single server finite -source queuing

model.

(ii) Average waiting time for a customer in the queue (line)

Wq=Lq / λ

(iii) Average waiting time for a customer in the system including

average service time

Ws= Wq+1 / μ

(iv) Probabili ty of being in the system (waiting and being served) longer

than time t is given by:

Where, T = time spent in the system

t = specified time period

e = 2.718

(v) Probability of only waiting for service longer than time t is given by:

(vi) Probability of exactly n customers in the system is given by:

(vii) Probability that the number of customers in the system, n exceeds a

given number, r is given by:

munotes.in

## Page 148

148

Operation Research The general relationships among various performance measures are:

(M/M/1) System Examples

Example 1:

A petroleum company is considering expansion of its one unloading

facility at its refinery. Due to random variations in weather, loading delays

and other factors, ships arriving at the refinery to unload crude oil arrive at

a rate of 5 ships per week. The service rate is 10 ships per week. Assume

arrivals follow a Poisson Process and the service time is exponential.

a) Find the average time a ship must wait before beginning to deliver

its cargo to the refinery.

b) If a second berth is rented what will be the average number of ships

waiting before being unloaded?

c) What would be the average time a ship would wait before being

unloaded with two berths?

d) What is the average number of idle berths atany specified time?

Solution:

a) The expected waiting time Wq before a ship begins to unload crude

oil is:

munotes.in

## Page 149

149

Waiting Lines Model

Example 2: A television repairman finds that the time spent on his jobs

has an exponential distribution with a mean of 30 minutes. If he repairs

the sets in the order in which they came in, and if the arrival of sets

follows a Poi sson distribution with an approximate average rate of 10 per

8-hour day, what is the repairman’s expected idle time each day? How

many jobs are ahead of the average set just brought in ? [Rajasthan,

MCom, 2000; Delhi Univ., MCom 2002 ]

Solution: From the dat a of the problem, we have:

(a) Expected idle time of repairman each day

Since number of hours for which the repairman remains busy in an 8 -hour

day (traffic intensity) is given by:

Therefore, the idle time for a repairman in an 8 -hour day will be: (8 – 5) =

3 hours

(b) Expected (or average) number of TV sets in the system

munotes.in

## Page 150

150

Operation Research 6.6 SUMMARY

A common situation that occurs in everyday life is that of waiting in a line

either at bus stops, petrol pumps, restaurants, ticket booths, doctors’

clinics, bank counters, traffic lights and so on. Queues (waiting lines) are

also found in workshops where the machines wait to be repaired; at a tool

crib where the mechanics wait to receive tools; in a warehouse where

items wait to be used, incoming calls wait to mature in the telephone

exchange, trucks wait to be unloaded, airplanes wait either to take off or

land and so on.

In general, a queue is formed at a production/operation system when either

customers (human beings or physical entities) requiring service wait

because nu mber of customers exceeds the number of service facilities , or

service facilities do not work efficiently/take more time than prescribed to

serve a customer.

A queuing problem is characterised by a flow of customers arriving

randomly at one or more service facilities. The customers upon arriving at

the facility may be served immediately or, if willing, may have to wait

until the facility is available.

The arrivals are characterised by either by the number of arrivals time

in a specific period of time or by the time between two

successive arrivals, known as interarrival time . The number of arrivals is

a discrete random variable whereas the interarrival times are continuous

random variables.

The service is characterised either by the number of services complet ed

in a given time period or the time taken to complete the service. The

number of services completed is a discrete random variable while the

service time is a continuous random variable.

Other characteristics of a queuing model are the number of servers,

order of service, size of the population of the customers, maximum

size of the queue. The various characteristics of a queuing problem can

be expressed in terms of a suitable notation known as Kendall's notation.

The time spent by an incoming customer in a queuing system is a random

variable and is of interest to the decision maker. If the customer under

consideration is a down machine it is inoperative during the period of

service. There is, thus, a cost involved due to its lack of functioning. One

of the objectives of studying a queuing problem is to find out the optimum

service rate and the number of servers so that the average cost of being in

queuing system and the cost of service are minimized . The time a

customer spends in a system before the start of service is a random

variable known as waiting time. The probability distribution of waiting

time depends upon the probability distribution of interarrival time and

service time.

munotes.in

## Page 151

151

Waiting Lines Model Let Pn(t) indicate the probability of having n customers in the system at

time t. Then if P(t) depends upon t, the queuing system is said to be in the

transient state. After the queuing system has become operative for a

considerable period of time the probability P n(t) may become

independent of t. The probabilities are then known as steady state

probabilities.

When the number of arrivals in a time interval of length t follows a

Poisson distribution with mean Jet where A is the rate of arrival, the

arrivals are said to follow a Poisson Process. In this case, the interarrival

times are independently, identically distributed random variables with an

exponential probability distribution with parameter X and vice versa.

If the service times are independently, identically distributed exponential

random variables with parameter 11 and there is only one server in the

queuing model, t he resulting queuing model is denoted by M/M/1

according to Kendall's notation.

6.7 EXERCISES

Example 3: In a railway marshaling yard, goods trains arrive at a rate of

30 trains per day. Assuming that the int erarrival time follows an

exponential distribution and the service time (the time taken to hump a

train) distribution is also exponential with an average of 36 minutes.

Calculate:

(a) expected queue size (line length)

(b) probability that the queue size ex ceeds 10

If the input of trains increases to an average of 33 per day, what will be

the change in (i) and (ii)?

Solution to Exercise 3: From the data of the problem, we have

£=30/(60 * 24) =1/48 trains per minute and µ =1/36 trains per minute.

The traf fic intensity then is, ρ= £/μ = 36/48 = 0.75

(a) Expected queue size (line length):

(b) Probability that the queue size exceeds 10:

P (n ≥10) =ρ10=(0.75)10=0.06

If the input increases to 33 trains per day, then we have £ = 33/(60* 24 )=

11/480 trai ns per minute and µ = 1/36 trains per minute.

munotes.in

## Page 152

152

Operation Research Thus, traffic intensity,

Hence, recalculating the values for (a) and (bi)

Example 4 : Arrivals at telephone booth are considered to be Poisson with

an average time of 10minutes between one arrival and th e next. The length

of phone calls is assumed to be distributed exponentially , with a mean of 3

minutes.

(a) What is the probability that a person arriving at the booth will have to

wait?

(b) The telephone department will install a second booth when convinc ed

that an arrival would expect waiting for at least 3 minutes for a phone

call. By how much should the flow of arrivals increase in order to

justify a second booth?

(c) What is the average length of the queue that forms from time to time?

(d) What is the probability that it will take a customer more than 10

minutes altogether to wait for the phone and complete his call?

Solution : From the data of the problem, we have

λ = 1/10 = 0.10 person per minute and μ = 1/3 = 0.33 person per minute

(a) Probability that a person has to wait at the booth.

P (n > 0) = 1 − P0 = λ/μ = 0.10 / 0.33 = 0.3

(b) The installation of second booth will be justified only if the arrival rate

is mo re than the waiting time.

Let λ′ be the increased arrival rate. Then the expected waiting time in the

queue will be

Where, Wq= 3 (given) and λ = λ′ (say) for second booth. Hence, the

increase in the arrival rate is0.16 – 0.10 = 0.06 arrivals per minute.

munotes.in

## Page 153

153

Waiting Lines Model (c) Average length of non -empty queue:

(d) Probability of waiting for 10 minutes or more is given by

This shows that on an average 3 per cent of the arrivals will have to wait

for 10 minutes or more before they can use the phone.

munotes.in

## Page 154

154

7

SIMULATION - QUEUE SYSTEM,

INVENTORY AND DEMAND

SIMULATION

Unit Structure

7.0 Objectives

7.1 Introduction

7.2 Reasons for using simulation

7.3 Limitations of simulation

7.4 Steps in the simulation process

7.5 Simulation - queue system

7.6 Simulation - inventory

7.7 Simulation - demand

7.8 Summary

7.9 Exercises (solved examples)

7.0 OBJECTIVES

After studying this unit, you will be able to:

Discuss the need for simulation in management problems where it will

not be possible to use precise mathematical techniqu es

Explain that simulation may be the only method in situations where it

will be extremely difficult to observe actual environment

Describe the process of simulation based on a sound conceptual

framework

Apply simulation techniques in solving queuing and i nventory control

problems.

7.1 INTRODUCTION

Simulation is a quantitative procedure which describes a process by

developing a model of that process and then conducting a series of

organized experiments to predict the behaviour of the process over time.

Observing the experiments is very much like observing the process in

operation. To find out how the real process would react to certain changes, munotes.in

## Page 155

155

Simulation - Queue System,

Inventory and Demand

Simulation we can produce these changes in our model and simulate the reaction of

the real process to them.

For instance, in designing an airplane, the designer can solve various

equations describing the aerodynamics of the plane. Or, if these equations

are very difficult and complex to solve, scale model can be built and its

behaviour observed in a wind tunnel. In simulation, w e build

mathematical models which we cannot solve and run them on sample data

to simulate the behaviour of the -system. Thus, simulation involves

performing experiments on the model of a system.

Simulation is one of the widely used techniques by corporate m anagers as

an aid for decision -making. This technique uses a computer to simulate

(imitate) the operation of any system or process. It is also used to analyse

systems that operate indefinitely. In such a case, the computer randomly

generates and records the occurrence of the events that drive the system as

if it was physically operating. Recording the performance of the simulated

operation of the system for a number of alternative options of operating

procedures enables us to evaluate and compare these alte rnatives to

choose the most desired one.

7.2 REASONS FOR USING SIMULATION

In the case of number of problems, we have been able to find through

straight forward techniques, mathematical solutions to the situation. The

economic order quantity, the simplex s olution to a linear programming

problem, and a branch -and- bound solution to an integer programming

problem are some of the typical examples we can cite. However, in each

of those cases the problem was simplified by certain assumptions so that

the appropri ate mathematical techniques could be employed. It is not

difficult to think of managerial situations so complex that mathematical

solution is impossible given the current state of the art in mathematics. In

these cases, simulation offers a good alternative , If we insist that all

managerial problems have to be solved mathematically, then we may find

ourselves simplifying the situation so that it can he solved; sacrificing

realism to solve the problem can get us in real trouble. Whereas the

assumption of norm ality-in dealing with a distribution of inventory

demand may he reasonable, the assumption of linearity in a specific linear

programming environment may be totally unrealistic .

While in some cases the solutions which result from simplifying

assumptions are suitable for the decision -maker, in other cases, they

simply are not. Simulation is an appropriate substitute for mathematical

evaluation of a model in many situations.

Although it also involves assumptions, they are manageable. The use of

simulation enab les us to provide insight into certain management

problems where mathematical evaluation of a model is not possible.

Among the reasons why management scientists would consider using

simulation to solve management problems are the following: munotes.in

## Page 156

156

Operation Research Simulation may be the only method available because it is difficult to

observe the actual environment. (In space flight or the charting of

satellite trajectories, it is widely used).

It is not possible to develop a mathematical solution.

Actual observation of a system ma y be too expensive. (The operation

of a large computer centre under a number of different operating

alternatives might be too expensive to be feasible).

There may not be sufficient time to allow the system to operate

extensively. (If we were studying long -run trends in world population, for

instance, we simply could not wait the required number of years to see

results.)

Actual operation and observation of a system may be too disruptive. (If

you are comparing two ways of providing food service in a hospital, the

confusion that would result from operating two different systems for long

enough to get valid observations might be too great).

7.3 LIMITATIONS OF SIMULATION

Use of simulation in place of other techniques, like everything else,

involves a trade - off, and we should be mindful of the disadvantages

involved in the simulation approach. These include the facts that

Simulation is not precise. It is not optimization and does not yield an

answer but merely provides a set of the system's responses to different

operating conditions. In many cases, this lack of precision is difficult

to measure.

A good simulation model may -be very expensive. Often it takes years

to develop a usable corporate planning model.

Not all situations can be evaluated using simulation; only situations

involving uncertainty are candidates, and without a random

component, all simulated experiments would produce the same

answer.

Simulation generates a way of evaluating solutions but does not

generate solutions themselves. Managers must sti ll generate the

solutions they want to test.

7.4 STEPS IN THE SIMULATION PROCESS

All effective simulations require a great deal of planning and organization.

Although simulations vary in complexity from situation to situation, in

general you will have to go through these steps:

1. Define the problem or system you intended to simulate.

2. Formulate the model you intend to use.

3. Test the model; compare its behaviour with the behaviour of the

actual problem. munotes.in

## Page 157

157

Simulation - Queue System,

Inventory and Demand

Simulation 4. Identify and collect the data needed to test the model.

5. Run the simulation.

6. Analyze the results of the simulation and, if desired, change the

solution you are evaluating.

7. Rerun the simulation to test the new solution.

8. Validate the simulation; this involves increasing the chances of

the inferences you may draw abo ut the real situation from

running the simulation to become valid.

7.5 SIMULATION - QUEUE SYSTEM

Example: A dentist schedules all his patients for 30 -minute

appointments. Some of the patients take more 30 minutes some less,

depending on the type of dental work to be done. The following summary

shows the various categories of work, their probabilities and time actually

needed to complete the work:

Category of Service Time Required

(minutes) Probability of

Category

Filling 45 0.40

Crown 60 0.15

Cleaning 15 0.15

Extraction 45 0.10

Checkup 15 0.20

Simulate the dentist’s clinic for four hours and determine the average

waiting time for the patients as well as the idleness of the doctor. Assume

that all the patients show up at the clinic at exactly their s cheduled arrival

time starting at 8.00 a.m. Use the following random numbers for handling

the above problem:

40 82 11 34 25 66 17 79 [AMIE, 2005]

Solution: The cumulative probability distribution and random number

interval for service time are sho wn in Table:

munotes.in

## Page 158

158

Operation Research Category of

Service Time

Required

(minutes) Probability

of Category Cumulative

Probability Random

Number

Interval

Filling 45 0.40 0.40 00-39

Crown 60 0.15 0.55 40-54

Cleaning 15 0.15 0.70 55-69

Extraction 45 0.10 0.80 70-79

Checkup 15 0.20 1.00 80-99

The various parameters of a queuing system such as arrival pattern of

customers, service time, waiting time , in the context of the given

problem, are shown in below Tables:

Table: Arrival Pattern and Nature of Service

Patient

Number Scheduled

Arrival Random

Number Category of

Service Service

Time

(Minute)

1 8.00 40 Crown 60

2 8.30 82 Checkup 15

3 9.00 11 Filling 45

4 9.30 34 Filling 45

5 10.00 25 Filling 45

6 10.30 66 Cleaning 15

7 11.00 17 Filling 45

8 11.30 79 Extraction 45

munotes.in

## Page 159

159

Simulation - Queue System,

Inventory and Demand

Simulation Table: Computation of Arrivals, Departures and Waiting of Patients

Time Event

(Patient Number) Patient Number

(Time to Exit) Waiting

(Patient

Number)

8.00 1 arrive 1 (60) -

8.30 2 arrive 1 (30) 2

9.00 1 departs; 3 arrive 2 (15) 3

9.15 2 depart s 3 (45) -

9.30 4 arrive 3 (30) 4

10.00 3 departs; 3 arrive 4 (45) 5

10.30 6 arrive 4 (15) 5, 6

10.45 4 departs 5 (45) 6

11.00 7 arrive 5 (30) 6, 7

11.30 5 departs; 8 arrive 6 (15) 7, 8

11.45 6 departs 7 (45) 8

12.00 End 7 (30) 8

The dentist was not idle even once during the entire simulated period.

The waiting times for the patients were as follows:

Table: Computation of Average Waiting Time

Patient

Number Arrival Time Service Starts

at Waiting Time

(Minute)

1 8.00 8.00 0

2 8.30 9.00 30

3 9.00 9.15 15

4 9.30 10.00 30

5 10.00 10.45 45

6 10.30 11.30 60

7 11.00 11.45 45

8 11.30 12.30 60

280

Average Waiting Time = 280 / 8 = 25 minutes

munotes.in

## Page 160

160

Operation Research 7.6 SIMULATION - INVENTORY

Example: Using random numbers to simulate a sample, find the

probability tha t a packet of 6products does not contain any defective

product, when the production line produces 10 per cent defective products .

Compare your answer with the expected probability.

Solution Given that 10 per cent of the total production is defective and 90

per cent is non -defective, if we have 100 random numbers (0 to 99), then

90 or 90 per cent of them represent non -defective products and the

remaining 10 (or 10 per cent) of them represent defective products. Thus,

the random numbers 00to 89 are assigned t o variables that represent non -

defective products and 90 to 100 are assigned to variables that represent

defective products.

If we choose a set of 2 -digit random numbers in the range 00 to 99 to

represent a packet of 6 products as shown below, then we woul d expect

that 90 per cent of the time they would fall in the range 00 to 89.

It may be noted that out of ten simulated samples 6 contain one or more

defectives and 4 contain no defectives. Thus, the expected percentage of

non-defective products is 40 per c ent. However, theoretically the

probability that a packet of 6 products containing no defective product, is

(0.9)6 = 0.53144 = 53.14%.

Sample

Number Random Number

A 83 02 22 57 51 68

B 39 77 32 77 09 79

C 28 06 24 25 93 22

D 97 66 63 99 61 80

E 69 30 16 09 05 53

F 33 63 99 19 87 26

G 87 14 77 43 96 43

H 99 53 93 61 28 52

I 93 86 52 77 65 15

J 18 46 23 34 25 85

Example: A book store wishes to carry a particular book in stock. The

demand of the book is not certain and there is a lead time of 2 day s for

stock replenishment. munotes.in

## Page 161

161

Simulation - Queue System,

Inventory and Demand

Simulation

The probabilities of demand are given below:

Demand (units/day) : 0 1 2 3 4

Probability : 0.05 0.10 0.30 0.45 0.10

Each time an order is placed, the store incurs an ordering cost of Rs 10 per

order. The store also incurs a carrying cost of Re 0.5 per book per day.

The inventory carrying cost is calculated on the basis of stock at the end of

each day. The manager of the book store wishes to compare two options

for his inventory decision.

A : Order 5 books when the pr esent inventory plus any outstanding order

falls below 8 books.

B : Order 8 books when the present inventory plus any outstanding order

falls below 8 books.

Currently (beginning of 1st day) the store has a stock of 8 books plus 6

books ordered two days ago and are expected to arrive the next day.

Carryout simulation runs for 10 days to recommend an appropriate option .

You may use random numbers in the sequences, using the first number for

day one as given below:

89, 34, 78, 63, 61, 81, 39, 16, 13, 73 [AMIE, 2005 ]

Solution: Using the daily demand distribution, we obtain a probability

distribution, as shown in Table of daily demand distribution.

Daily Demand Probability Cumulative

Probability Random

Number

Intervals

0 0.05 0.05 00-04

1 0.10 0.15 05-14

2 0.30 0.45 15-44

3 0.45 0.90 45-89

4 0.10 1.00 90-99

The stock in hand is of 8 books and stock on order is 5 books (expected

next day).

munotes.in

## Page 162

162

Operation Research Table: Optimal A

Random

Number Daily

Demand Opening

Stock in

Hand Receipt Closing

Stock

in

Hand Order

Quantity Closing

Stock

89 3 8 - 8-3=5 5 5

34 2 5 5 5+5-

2=8 - 8

78 3 8 - 8-3=5 5 5

63 3 5 5 10-3=7 - 7

61 3 7 - 7-3=4 5 4

81 3 4 5 9-3=6 - 6

39 2 6 - 6-2=4 5 4

16 2 4 5 9-2=7 - 7

13 1 7 - 7-1=6 - 6

73 3 6 - 6-3=3 - 3

55

Since 5 books have been order ed four times as shown in Table above,

therefore, the total ordering cost is Rs (4 × 10) = Rs 40.

Closing stock of 10 days is of 55 books. Therefore, the holding cost at the

rate of Re 0.5 per book per day is Rs 55 × 0.5 = Rs 27.5

Total cost for 10 days = Ordering cost + Holding cost = Rs 40 + 27.5 =

Rs 67.5

munotes.in

## Page 163

163

Simulation - Queue System,

Inventory and Demand

Simulation Table: Optimal B

Random

Number Daily

Demand Opening

Stock in

Hand Receipt Closing

Stock

in

Hand Order

Quantity Closing

Stock

89 3 8 - 8-3=5 8 5

34 2 5 8 8+5-

2=11 - 11

78 3 11 - 11-3=8 - 8

63 3 8 - 8-3=5 8 5

61 3 5 8 13-

3=10 - 10

81 3 10 - 10-3=7 - 7

39 2 8 - 7-2=5 8 5

16 2 5 8 13-

2=11 - 11

13 1 11 - 11-

1=10 - 10

73 3 10 - 10-3=7 - 7

71

Eight books have been ordered three times, as shown in Table above,

when the inventory of books at the beginning of the day plus outstanding

orders is less than 8. Therefore, the total ordering cost is: Rs (3 × 10) =

Rs 30.

Closing stock of 10 days is of 71 books. Therefore, the holding cost , Re

0.5 per book per day is Rs 71 × 0.5 = Rs 35.5

The total cost for 10 days = Rs (30 + 35.5) = Rs 65.5. Since option B has a

lower total cost than option A, therefore, the manager should choose

option B.

7.7 SIMULATION - DEMAND

Example: A bakery keeps stock of a popular brand of cake. Previous

exper ience shows the daily demand pattern for the item with associated

probabilities, as given below:

Daily demand (number) : 0 10 20 30 40 50

Probability: 0.01 0.20 0.15 0.50 0.12 0.02 munotes.in

## Page 164

164

Operation Research Use the following sequence of random numbers to simulate the demand

for next 10 days.

Random numbers: 25, 39, 65, 76, 12, 05, 73, 89, 19, 49.

Also estimate the daily average demand for the cakes on the basis of the

simulated data.

Solution: Using the daily demand distribution, we first obtain a

probability distribut ion as shown in Table below:

Table: Daily Demand Distribution

Daily Demand Probability Cumulative

Probability Random

Number

Intervals

0 0.01 0.01 00

10 0.20 0.21 01-20

20 0.15 0.36 21-35

30 0.50 0.86 36-85

40 0.12 0.98 86-97

50 0.02 1.00 98-99

Next to conduct the simulation experiment for demand take a sample of 10

random numbers from a table of random numbers, which represent the

sequence of 10 samples. Each random sample number represents a sample

of demand.

The simulation calculations for a period of 10 days are given in Table

below:

Days Random

Number Simulated

Demand

1 40 30 Because random number 40 falls in

the interval 36 -85

2 19 10 Because random number 19 falls in

the interval 01 -20 and so on

3 87 40

4 83 30

5 73 30

6 84 30

7 29 20

8 09 10

9 02 10

10 20 10

Expected Demand = 220/10 = 22 units per day munotes.in

## Page 165

165

Simulation - Queue System,

Inventory and Demand

Simulation 7.8 SUMMARY

Simulation is a powerful and intuitive technique and uses computer to

simulate the operation of an entire system or process. Random numbers

are generated using a pr obability distribution to generate various outcomes

over a period of time. These outcomes provide at a glance view of

different configurations of the system at a least cost in comparison of

actually operating the system. Hence, many alternative system

configurations can be investigated and compared before selecting the most

appropriate one to use.

Simulation approach has applications to a wide variety of areas such as

queuing system, inventory system, and demand distribution, etc.

Spread sheet software is i ncreasingly being used to perform basic

computer simulations. The availability of such software enables decision

makers to use simulation approach for solving real -life decision problems.

A simulation imitates the operation of real world processes or syste ms

with the use of models. The model represents the key behaviours and

characteristics of the selected process or system while the simulation

represents how the model evolves under different conditions over time.

Simulations are usually computer -based, usi ng a software -generated

model to provide support for the decisions of managers and engineers as

well as for training purposes. Simulation techniques aid understanding and

experimentation, as the models are both visual and interactive.

Simulation systems in clude discrete event simulation, process simulation

and dynamic simulation. Businesses may use all of these systems across

different levels of the organisation.

7.9 EXERCISES

Example 1: A firm has a single channel service station with the following

arrival and service time probability distributions:

Interarrival

time in minutes Probability Service time

in minutes Probability

10 0.10 5 0.08

15 0.25 10 0.14

20 0.30 15 0.18

25 0.25 20 0.24

30 0.10 25 0.22

30 0.14

munotes.in

## Page 166

166

Operation Research The customer’s arrival at the servic e station is a random phenomenon and

the time between the arrivals varies from 10 to 30 minutes. The service

time varies from 5 minutes to 30 minutes. The queuing process begins at

10 a.m. and proceeds for nearly 8 hours. An arrival immediately, goes to

the service facility if it is free. Otherwise it waits in a queue. The queue

discipline is first -come first -served. If the attendant’s wages are Rs 10 per

hour and the customer’s waiting time costs Rs 15 per hour, then would it

be an economical proposition t o engage a second attendant? Answer using

Monte Carlo simulation technique.

Solution: The cumulative probability distributions and random number

interval, both for interarrival time and service time, are shown in the

following Tables:

Table: Interarrival T ime

Interarrival

time

in minutes Probability Cumulative

Probability Random

number

interval

10 0.10 0.10 00-09

15 0.25 0.35 10-34

20 0.30 0.65 35-64

25 0.25 0.90 65-89

30 0.10 1.00 90-99

Table: Service Time

Interarrival

time

in minutes Probability Cumulative

Probability Random

number

interval

5 0.08 0.08 00-07

10 0.14 0.22 08-21

15 0.18 0.40 22-39

20 0.24 0.64 40-63

25 0.22 0.86 64-85

30 0.14 1.00 86-99

munotes.in

## Page 167

167

Simulation - Queue System,

Inventory and Demand

Simulation

Table: Single Server Queuing Simulation for 15 Arrivals

Arrival

Number Random Number Interarrival Time

(min) Arrival

Time

(min) Service

Starts

(min) Waiting

Time Random Number Service Time Exit

Time Time

in

System

1 2 3 4 5 6 7 8 9 10= 6+8 1 20 15 10.15 10.15 0 26 15 30 15

2 73 25 10.40 10.40 0 43 20 60 20

3 30 15 10.55 11.00 5 98 30 90 35

4 99 30 11.25 11.30 5 87 30 120 35

5 66 25 11.45 12.00 15 58 20 140 35

6 83 25 12.10 12.20 10 90 30 170 40

7 32 15 12.25 1.05 35 94 25 195 60

8 75 25 12.50 1.30 40 60 20 215 60

9 04 10 1.00 1.50 50 08 10 225 60

10 15 15 1.15 2.00 45 50 20 245 65

11 29 15 1.30 2.20 50 37 15 260 65

12 62 20 1.50 2.35 45 42 20 280 65

13 37 20 2.10 2.55 45 28 15 295 60

14 68 25 2.35 3.10 35 84 25 320 60

15 94 30 3.05 3.35 30 65 25 345 55

From the 15 samples of waiting time, 225 minu tes, and the time spent, 545

minutes, by the customer in the system, we compute all average waiting

time in the system and average service time as follows:

Average waiting time = 380/15 = 25.3 minutes.

Average service time = 545/15 = 36.33 minutes

Thus, th e average cost of waiting and service is given by:

Cost of waiting = 15 × (25.30/60) = Rs 6.32 per hour

Cost of service = 10 × (36.33/60) = Rs 6.05 per hour

Since the average cost of service, per hour, is less than the average cost of

waiting per hour, therefore second attendant may be hired.

Example 2: A company trading in motor vehicle spare parts wishes to

determine the levels of stock it should carry for the items in its range. The

demand is not certain and there is a lead time for stock replenishment . For

an item A, the following information is obtained:

munotes.in

## Page 168

168

Operation Research Demand (units/day) : 3 4 5 6 7

Probability : 0.10 0.20 0.30 0.30 0.10

Carrying cost (per unit/day) : Rs 2

Ordering cost (per order) : Rs 50

Lead time for replenishment : 3 days

Stock on hand at the beginning of the simulation exercise was 20 units.

Carry out a simulation run over a period of 10 days with the objective of

evaluating the inventory rule:

Order 15 units when present inventory plus any outstanding order falls

below 15 units.

You may use random numbers in the sequence of: 0, 9, 1, 1, 5, 1, 8, 6, 3,

5, 7, 1, 2, 9, using the first number for day one. Your calculation should

include the total cost of operating this inventory rule for 10 days.

[AMIE, 2004 ]

Solution Let us begin s imulation by assuming that:

(i) Orders are placed at the end of the day and received after 3 days, at the

end of a day.

(ii) Back orders are accumulated in case of short supply and are supplied

when stock is available.

The cumulative probability distributi on and the random number range for

daily demand is shown in Table below:

Table - Daily Demand Distribution

Daily Demand Probability Cumulative

Probability Random

Number

Intervals

3 0.10 0.10 00

4 0.20 0.30 01-02

5 0.30 0.60 03-05

6 0.30 0.90 06-08

7 0.10 1.00 09

munotes.in

## Page 169

169

Simulation - Queue System,

Inventory and Demand

Simulation

The results of the simulation experiment conducted are shown in Table

below:

Table - Simulation Experiments

Days Opening

Stock Random

Number Resulting

Demand Closing

Stock Order

Placed Order

Delivered Average

Stock in

the

Evening 1 20 0 3 17 - - 18.5

2 17 9 7 10 15 - 13.5

3 10 1 4 6 - - 8

4 6 1 4 2 - - 4

5 2 5 5 0(-3)* 15 15 1

6 12 1 4 8 - - 10

7 8 8 6 2 - - 6

8 2 6 6 0(-4)* 15 15 1

9 11 3 5 6 - - 8.5

10 6 5 5 1 - - 3.5

* Negative figures indicate back orders.

Average ending stoc k = 78/10 = 7.8 units/day

Daily ordering cost = (Cost of placing one order) × (Number of orders

placed per day) = 50 × 3 = Rs l50

Daily carrying cost = (Cost of carrying one unit for one day) × (Average

ending stock) = 2 × 7.8 = Rs l5.60

Total daily invent ory cost = Daily ordering cost + Daily carrying cost =

150 + 15.60 = Rs 165.60.

Example 3: The manager of a warehouse is interested in designing an

inventory control system for one of the products in stock. The demand for

the product comes from numerous re tail outlets and the orders arrive on a

weekly basis. The warehouse receives its stock from a factory but the lead

time is not constant. The manager wants to determine the best time to

release orders to the factory so that stockouts are minimized, yet the

inventory holding costs are at acceptable levels. Any order from retailers,

not supplied on a given day, constitute lost demand. Based on a sampling

study, the following data are available:

munotes.in

## Page 170

170

Operation Research Demand per

week in

thousand Probability Lead time Probability

0 0.20 2 0.30

1 0.40 3 0.40

2 0.30 4 0.30

3 0.10

The manager of the warehouse has determined the following cost

parameters: Ordering cost (C 0) per order equals Rs 50, carrying cost (C h)

equals Rs 2 per thousand units per week, and shortage cost (C s) equals Rs

10 per thousand units.

The objective of inventory analysis is to determine the optimal size of an

order and the best time to place an order. The following ordering policy

has been suggested.

Policy : Whenever the inventory level becomes less than or equal to 2,000

units (reorder level), an order equal to the difference between current

inventory balance and the specified maximum replenishment level , is

equal to 4,000 units, is placed.

Simulate the policy for a week’s period assuming that the (i) th e beginning

inventory is 3,000 units, (ii) no back orders are permitted, (iii) each order

is placed at the beginning of the week, as soon as the inventory level is

less than or equal to the reorder level, and (iv) the replenishment orders

are received at the beginning of the week.

[AMIE, 2005 ]

Solution:

Using weekly demand and lead time distributions, assign an appropriate

set of random numbers to represent value (range) of variables as shown in

below respective Tables:

Table: Probabilities and Random number Interval for Weekly

Demand

Weekly

demand (in

thousand) Probability Cumulative

probability Random

number

interval

0 0.20 0.20 00-19

1 0.40 0.60 20-59

2 0.30 0.90 60-89

3 0.10 1.00 90-99

munotes.in

## Page 171

171

Simulation - Queue System,

Inventory and Demand

Simulation Table: Probabilities and Random number Interval for Lea d Time

Lead time in

weeks Probability Cumulative

probability Random

number

interval

2 0.30 0.30 00-29

3 0.40 0.70 30-69

4 0.30 1.00 70-99

The simulation experiment conducted for a 10 week period is shown in the

next Table. The simulation process begin s with an inventory level of

3,000 units. The following four steps occur in the simulation process:

1. Begin each simulation week by checking whether any order has just

arrived. If it has, increase the beginning (current) stock (inventory) by the

quantity received.

2. Generate a weekly demand from the demand probability distribution in

weekly demand Table given above by selection of a random number. This

random number is recorded in column 4. The demand simulated is

recorded in column 5.The random number 31 generates a demand of 1,000

units when it is subtracted from the initial inventory level value of 3,000

units. It yields an ending inventory of 2,000 units at the end of the first

week.

3. Compute the ending inventory every week and record it in column 7.

Ending inventory = Beginning inventory – Demand = 3,000 – 1,000 =

2,000

If on hand inventory is not sufficient to meet the week’s demand, then

record the number of units short in column 6.

4. Determine whether the week’s ending inventory has reached the r eorder

level. If it has, and if thereis no outstanding order (back orders), then place

an order.

Since the ending inventory of 2,000 units is equal to the reorder level,

therefore, an order for4,000 – 2,000 = 2,000 units is placed.

5. The lead time for the new order is simulated by first choosing a random

number and recording it in column 8. Finally, this random number is

converted into a lead time (column 9) by using the lead time distribution

in the earlier Table.

The random number 29 corresponds to a le ad time of 2 weeks, with 2,000

units to be held (carried) in stock. Therefore, the holding cost of Rs 4 is

paid and since there were no shortages, there is no shortage cost. munotes.in

## Page 172

172

Operation Research Summing these cost yields a total inventory cost (column 10) for week

one of Rs 54 .

The same step -by-step process is repeated for the remaining 10 weeks of

the simulation experiment.

Analysis of Inventory Cost

Average ending inventory = (1,000 total unit / 10 weeks) = 100 units per

week.

Average number of orders placed = (2 orders / 10 weeks) = 0.2 order per

week.

Average number of lost sales = (7,000 / 1,000 ) = 7 units per week.

Total average inventory cost = Ordering cost + Holding cost + Shortage

cost

= (Cost of placing one order) × (Number of orders placed per week)

+

(Cost of holding one unit for one week) × (Average ending inventory) +

(Cost per lost sale) × (Average number of lost sales per week)

= (100 / 10) + (16 / 10) + (70 / 10)

= 10 + 1.6 + 7

= Rs 18.6

Maximum Inventory Level = 4,000 units Reorder Level = 2 ,000 units

Week Order

Receipt Beginning

Inventory Random

Number Demand Ending

Inventory Quantity

Ordered Random

Number Lead

Time Total Cost

C0+ Ch+ Cs = TC

(R.)

1 0 3000 31 1000 2000 2000 29 2 50 4 - - 54

2 0 2000 73 2000 0 0 - - - - - = -

3 0 0 53 1000 (-1000) 0 - - 0 0 10 = 10

4 2000 2000 86 2000 0 4000 83 4 50 - - = 50

5 0 0 32 1000 (-1000) 0 10 = 10

6 0 0 78 2000 (-2000) 0 20 = 20

7 0 0 26 1000 (-1000) 0 10 = 10

8 0 0 64 2000 (-2000) 0 20 = 20

9 4000 4000 45 1000 3000 0 6 - = 6

10 0 3000 12 0 3000 0 6 - = 6

Total 1000 100 16 70

The negative figures in Table above enclosed in brackets indicate loss of

sales.

munotes.in