Assignment Problem Session2
Prof. Vikram H
Meaning of OR
Application of Quantitative Methods
Scientific Method
Solve practical problems in business
Session 1 Research on Operations
Review OR History
Applications / Scope of OR
Marketing and Sales
Production Management
Finance, Investment & Budgeting
HR
R&D
Case Study - GM
OR Books
OR Books
Assignment Concepts- What is Assignment Problem?
Formulation of Assignment Model
After Completing Methods of Assignment Problem
Session Hungarian Method to solve Assignment Problem
You Categories of assignment Problems
will Minimization Assignment Problem
Understand Maximization Assignment Problem
Balanced Assignment Problem
Unbalanced Assignment Problem
Prohibited / Constrained Assignment Problem
Deals with the allocation of the various resources to the various activities
What is on one to one basis.
Assignment Assignment of n different facilities to n different tasks
Problem? It does it in such a way that the cost or time involved in the process is
minimum and profit or sale is maximum
Formulation For all i, Resource available
of
Assignment
Problem For all j, Activity Requirement
Cij- Cost of assignment resource i to activity j
Two air conditioners need to be installed in the same week by two
different companies
Bids for each job are solicited from each company
To which company should each job be assigned?
Understanding
Assignment
A- Bldg.1 A- Bldg. 2
B- Bldg. 2 B- Bldg.1
Total = 53+ 87 =140 Total = 96+ 47 = 143
Three air conditioners need to be installed in the same week by
three different companies
Bids for each job are solicited from each company
To which company should each job be assigned?
Understanding
Assignment
Understanding
Assignment
Total Cost = 53 + 92+ 41 = 186
Formulation
of
Assignment
Problem
Formulation
of
Assignment
Problem
Consider I (resource)laborers to whom j (activity)tasks are assigned.
No laborer can either sit idle or do more than one task.
Formulation
Every pair of person and assigned work has a rating.
of
This rating may be cost, satisfaction, penalty involved or time taken to
Assignment finish the job.
Problem There will be N2 such combinations of persons and jobs assigned.
The optimization problem is to find such man- job combinations that
optimize the sum of ratings among all.
1. Subtract the smallest entry in each row from all the entries of its row.
2. Subtract the smallest entry in each column from all the entries of its
column
3. Draw minimum number of horizontal & vertical lines to cover all
Hungarian Method zeros at least one
to 4. If the minimum number of lines in matrix (n*n) is n, then we have an
optimal solution
Solve Assignment
Problems 5. If minimum number of lines in matrix (n*n) is less than n, then select
the smallest number that does not have a line through it, Subtract this
number from each uncovered row & add it to every element at the
intersection of the two lines.
6. Return to step 3 & 4 until a solution is find
Make sure that in the matrix each row and each column has at least one
zero element.
Assignment-
Hungarian Method Given an optimal solution make job assignment as below:
to Locate a row which contains only one zero element, Assign job
Solve Assignment corresponding this element to its corresponding person
Problems Cross the zero’s if any in the column corresponding to the element (which
indicate particular job & person are not available)
You work as a sales manager for a toy manufacturer and you currently
have three sales people are in Ahmadabad, Bangalore & Calcutta
You want them to fly to three other cities Delhi, Faridabad & Gujrat
The table below shows the cost of airplane tickets between these cities.
From /To D F G
Assignment Problem A 2500 4000 3500
1 B 4000 6000 3500
C 2000 4000 2500
Where should you send each of your sales people in order to minimize
air fare?
Step 1
Subtract the smallest entry in each row from all the entries of its
row
Assignment Problem Subtract 2500 from Row1, 3500 from Row 2 and 2000 from Row 3
1
Solution From/To D F G
A 0 1500 1000
B 500 2500 0
C 0 2000 500
Step 2
Subtract the smallest entry in each column from all the entries of its
column
Subtract 0 from Column1, 1500 from Column2, & 0 from
Assignment Problem Column3.
1 From / To D F G
Solution A 0 0 1000
B 500 1000 0
C 0 500 500
Assignment Problem Step 3
Draw minimum number of horizontal & vertical lines to cover all zeros at least one
1 From / To D F G
Solution A 0 0 1000
B 500 1000 0
C 0 500 500
No of lines = 3 , optimal solution
Assignment as below:
Assignment Problem
1 From / To D E F
Solution A 0 0 1000
B 500 1000 0
C 0 500 500
Assignment Problem
1
Solution
Answer :
A -- F
B -- G
C -- D
Minimize Air Fare=2000+4000+3500
= 9500
Solve the following assignment problem to minimize the total cost
represented as elements in the matrix (cost in thousand rupees).
Contractor
Assignment Building 1 2 3 4
Problem A
B
48
56
48
60
50
60
44
68
C 96 94 90 85
D 42 44 54 46
Step 1
Subtract the smallest entry in each row from all the entries of its
row
Assignment
Contractor
Problem Building 1 2 3 4
A 4 4 6 0
B 0 4 4 12
C 11 9 5 0
D 0 2 12 4
Step 2
Subtract the smallest entry in each column from all the entries of its
column
Assignment Contractor
Problem Building 1 2 3 4
A 4 2 2 0
B 0 2 0 12
C 11 7 1 0
D 0 0 8 4
Make sure that in the matrix each row and each column has at
least one zero element.
Step 3
Draw minimum number of horizontal & vertical lines to cover all
zeros at least one
Assignment Contractor
Problem Building 1 2 3 4
A 4 2 2 0
B 0 2 0 12
C 11 7 1 0
D 0 0 8 4
Step 4
Select the smallest number that does not have a line through it, Subtract
this number from each uncovered row & add it to every element at the
intersection of the two lines.
In this example we have 1, as the minimum element, subtract the same
from all the elements that do not have a line through them and add this
smallest element at the intersection of two lines
Assignment Contractor
Problem Building 1 2 3 4
A 4 2 2 0
B 0 2 0 12
C 11 7 1 0
D 0 0 8 4
Contractor
Building 1 2 3 4
A 3 1 1 0
Assignment B 0 2 0 13
Problem C 0 6 0 0
D 0 0 8 5
Contractor
Assign
Building 1 2 3 4
A 3 1 1 0
B 0 2 0 13
C 0 6 0 0
Assignment D 0 0 8 5
Problem
A- 4 (44)
B- 1 (56)
C- 3 (90)
D -2 (44)
Total = 234 Thousand
Construction Site
Crane 1 2 3 4
A 90 75 75 80
B 35 85 55 65
Solve C 125 95 90 105
D 45 110 95 115
Step 1 tep 4
S
Subtract the smallest entry in each row from all the entries of its row Crane 1 2 3 4
Construction Site A 35 0 0 0
Crane 1 2 3 4
B 0 30 0 5
A 15 0 0 5
B 0 50 20 30
C 55 5 0 10
C 35 5 0 15 D 0 45 30 45
D 0 65 50 70
Step 2
Subtract the smallest entry in each column from all the entries of its column tep 4
S
Solution Crane 1
Construction Site
2 3 4
Crane
A
1
40
2
0
3
5
4
0
A 15 0 0 0
B 0 25 0 0
B 0 50 20 25
C 35 5 0 10 C 55 0 0 5
D 0 65 50 65 D 0 40 30 40
Step 3
Draw minimum number of horizontal & vertical lines to cover all zeros at least one tep 4
S
Crane 1 2 3 4 Crane 1 2 3 4
A 15 0 0 0 A 40 0 5 0
B 0 50 20 25
B 0 25 0 0
C 35 5 0 10
C 55 0 0 5
D 0 65 50 65
D 0 40 30 40
A ssignment ssignment
A
Crane 1 2 3 4 Crane 1 2 3 4
A 40 0 5 0 A 40 0 5 0
B 0 25 0 0 B 0 25 0 0
C 55 0 0 5
C 55 0 0 5
D 0 40 30 40
D 0 40 30 40
Solution Crane A – 2 (75) Crane A – 4 (80)
Crane B – 4 (65) Crane B – 3 (55)
Crane C – 3 (90) Crane C – 2 (95)
Crane D – 1 (45) Crane D – 1 (45)
Total = 275 Total = 275
Objective of solution is maximization of final answer
Example- sales, revenue, profit
One need to convert maximization problem in minimization problem
Maximization This conversion is called Regret matrix
Assignment Steps to solve problem-
Problem Step1- Converting from Maximization to Minimization
Subtracting all elements from the largest element of matrix
Follow usual Hungarian procedure to solve the problem
Solve problem of assignment for the given table to maximize the sales
Maximization
Problem 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
Step1- Converting from Maximization to Minimization
Highest element is 41, subtracting all elements from 41
Maximization A B C D E
1 9 3 1 13 1
Problem 2 1 17 13 20 5
3 0 14 8 11 4
4 19 3 0 15 5
5 12 8 1 6 2
Step 2
Subtract the smallest entry in each row from all the entries of its row
Maximization A B C D E
Problem 1 8 2 0 12 0
2 0 16 12 19 4
3 0 14 8 11 4
4 19 3 0 15 5
5 11 7 0 5 1
Step 3
Subtract the smallest entry in each column from all the entries of its
column
Maximization A B C D E
1 8 0 0 7 0
Problem 2 0 14 12 14 4
3 0 12 8 6 4
4 19 1 0 10 5
5 11 5 0 0 1
Step 4
Draw minimum number of horizontal & vertical lines to cover all
zeros at least one
Maximization
Problem
A B C D E
1 8 0 0 7 0
2 0 14 12 14 4
3 0 12 8 6 4
4 19 1 0 10 5
5 11 5 0 0 1
Step 5
Select the smallest number that does not have a line through it,
Subtract this number from each uncovered row & add it to every
element at the intersection of the two lines.
In this example we have 1, as the minimum element, subtract the
same from all the elements that do not have a line through them and
add this smallest element at the intersection of two lines
Maximization
Problem 1
A
8
B
0
C
0
D
7
E
0
2 0 14 12 14 4
3 0 12 8 6 4
4 19 1 0 10 5
5 11 5 0 0 1
A B C D E
1 9 0 1 7 0
2 0 13 12 13 3
Maximization 3 0 11 8 5 3
Problem 4
5
19
12
0
5
0
1
9
0
4
1
No of lines = 4
Minimum element is 3. subtract the same from all the elements that do
not have a line through them and add this smallest element at the
intersection of two lines
A B C D E
1 12 0 1 7 0
Maximization 2 0 10 9 10 0
Problem 3 0 8 5 2 0
4 22 0 0 9 4
5 15 5 1 0 1
Assign as below:
A B C D E
Maximization 1 12 0 1 7 0
2 0 10 9 10 0
Problem 3 0 8 5 2 0
4 22 0 0 9 4
5 15 5 1 0 1
1- B 38
2- A 40
3- E 37
4- C 41
5- D 35
Total = 191
A company has 5 jobs to be done. Assign 5 jobs to 5 machines so as to
maximize the total expected profit
A B C D E
Maximization 1 5 11 10 12 4
Problem 2 2 4 6 3 5
3 3 12 5 14 6
4 6 14 4 11 7
5 7 9 8 12 5
Balanced Assignment Problem-
No. of rows & columns in the problem are equal
Balanced
& Unbalanced Assignment Problem-( Non Square Matrix)
Unbalanced No. of rows & columns in the problem are not equal
Assignment
Add row / column to make the square matrix
Problem
ABC Company Decided to organize training program for employees. A
careful study indicates that no. of employees who cannot attend a
seminar topic A,B,C &D on special day is as follows:
Solution
to
Unbalanced
Assignment Problem
Find the optimal schedule of the seminar.
Find out total number of employees missing at least one seminar
No. of Rows = 5
No. of Columns = 4
Unbalanced Problem
Balance it by adding column
Solution
to
Unbalanced
Assignment Problem
Zero in each row therefore there will be no change
Subtract the smallest entry in each column from all the entries of its
column
Solution
to A B C D E
Unbalanced Monday 40 20 50 0 0
Tuesday 30 10 30 10 0
Assignment Problem Wednesday 50 0 20 0 0
Thursday 20 10 10 10 0
Friday 0 0 0 10 0
Subtracting 10 from uncovered & adding at intersection
Solution
A B C D E
to 30 10 40 0 0
Monday
Unbalanced Tuesday 20 0 20 10 0
Assignment Problem Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 0 0 20 10
A B C D E
Monday 30 10 40 0 0
Solution Tuesday 20 0 20 10 0
to Wednesday 50 0 20 10 10
Unbalanced Thursday 10 0 0 10 0
Assignment Problem Friday 0 0 0 20 10
Prohibited / Constrained
Prohibited / In this there are one or more constrained (I ,j )
Constrained Solution-
Assignment Problem Assigning very high cost (M) to prohibit the entry of this into the final
solution