A Apom

Presentation report
On
Assignment problem multiple solution
Sub: Advance Production And Operation

Management
SUBMITTED TO:
ASST .Prof. Sweta Agrawal
SUBMITTED BY:
Group Number : 30
1.Sangani Dhruv 43
2.Raval Darshan 28
3.Shah Anushka 13
4.Ganatra Arjavi 14
5.Trivedi Dhanvi 40
Introduction 2
Mathematical Formulation of 3
the Assignment Problem
steps 4-6
Multiple solution 7
example 8-10
Conculusion 11
Biblography 12
 Assignment problem:
 An assignment problem is a particular case of

transportation problem where the objective is to assign a
number of resources to an equal number of activities so as to
minimise total cost or maximize total profit of allocation.
 The problem of assignment arises because available

resources such as men, machines etc. have varying degrees
of efficiency for performing different activities, therefore,
cost, profit or loss of performing the different activities is
different.
 Thus, the problem is “How should the assignments be made

so as to optimize the given objective”. Some of the problem
where the assignment technique may be useful are
assignment of workers to machines, salesman to different
sales areas.
 Definition of Assignment Problem:
 Suppose there are n jobs to be performed and n persons are

available for doing these jobs. Assume that each person can
do each job at a term, though with varying degree of
efficiency, let cij be the cost if the i-th person is assigned to
the j-th job. The problem is to find an assignment (which job
should be assigned to which person one on-one basis) So that
the total cost of performing all jobs is minimum, problem of
this kind are known as assignment problem.
 The assignment problem can be stated in the form of n x n

cost matrix C real members as given in the following table:
 Mathematical Formulation of the Assignment Problem:
 Assignment Problems :
Step :1 Choose the least element in each row and subtract it from
all the elements of that row.
Step :2 Choose the least element in each column and subtract it

from all the elements of that column. Step 2 has to be performed
from the table obtained in step 1.
Step:3 Check whether there is atleast one zero in each row and

each column and make an assignment as follows.
(i) Examine the rows successively until a row with exactly one
zero is
found. Mark that zero by , that means an assignment is made

there . Cross ( ×) all other zeros in its column. Continue this until
all the rows have been examined.
Examine the columns successively until a columns with exactly

one zero is found. Mark that zero by , thaExamine the columns
successively until a columns with exactly one zero is found. Mark
that zero by , that means an assignment is made there . Cross
( × ) all other zeros in its row. Continue this until all the columns
have been examinedt means an assignment is made there . Cross (
× ) all other zeros in its row. Continue this until all the columns
have been examined.
Step :4 If each row and each column contains exactly one
assignment, then the solution is optimal.
 Multiple solution:
 Sometimes, it is possible to cross out all the zeros in the

reduced matrix in two or more ways.
 If you can choose a zero cell arbitrarily, then there will

be multiple optimal solutions with the same total pay-off for
assignments made. In such a case, the management may
select that set of optimal assignments, which is more suited
to their requirement.
Example: Multiple Optimal Solutions
The Spicy Spoon restaurant has four payment counters. There

are four persons available for service. The cost of assigning each
person to each counter is given in the following table.
Assign one person to one counter to minimize the total cost.
Job
Person 1 2 3 4
A 1 8 15 22
B 13 18 23 28
C 13 18 23 28
D 19 23 27 31
Step 1
person 1 2 3 4
A 0 7 14 21
B 0 5 10 15
C 0 5 10 15
D 0 4 8 12
Step 2
person 1 2 3 4
A 0 3 6 9
B 0 1 2 3
C 0 1 2 3
D 0 0 0 0
Step 3
Person / 1 2 3 4
A 0 2 5 8
B 0 0 1 2
C 0 0 1 2
D 1 0 0 0
Step 4
Person 1 2 3 4
A 0 2 4 7
B 0 0 0 1
C 0 0 0 1
D 2 0 0 0
Step 5
Person 1 2 3 4
A 0 2 4 7
B 0 0 0 1
C 0 0 0 1
D 2 0 0
The person B&C may be assigned either to job 2or3.
The two alternative assignments are:
A1+B2+C3+D4 A1+B3+C2+D4
1+18+23+31=73 1+23+18+31=73
 Bibilography
• https://www.engineeringenotes.com/project-management-2/
operations-research/assignment-problem-meaning-methods-
and-variations-operations-research/15652
• http://www.universalteacherpublications.com/univ/ebooks/
or/Ch6/mlpass.htm
Thank You

A Apom

Uploaded by

Copyright:

Available Formats

A Apom

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

A Apom

Uploaded by

Copyright:

Available Formats

Presentation report

Assignment problem multiple solution

Sub: Advance Production And Operation

ASST .Prof. Sweta Agrawal

 An assignment problem is a particular case of

 The problem of assignment arises because available

 Thus, the problem is “How should the assignments be made

 Suppose there are n jobs to be performed and n persons are

 The assignment problem can be stated in the form of n x n

Step :2 Choose the least element in each column and subtract it

Step:3 Check whether there is atleast one zero in each row and

found. Mark that zero by , that means an assignment is made

Examine the columns successively until a columns with exactly

 Sometimes, it is possible to cross out all the zeros in the

 If you can choose a zero cell arbitrarily, then there will

Example: Multiple Optimal Solutions

The Spicy Spoon restaurant has four payment counters. There

Assign one person to one counter to minimize the total cost.

The person B&C may be assigned either to job 2or3.

The two alternative assignments are:

You might also like