Subject Name: Operation Research
Assignment Problems
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Q-2 Following matrix represents the time taken by Five people A,B,C,D,E to perform 5
jobs P,Q,R,S,T. Give the optimum assignments so as to minimize the total time.
P Q R S T
A 85 75 65 125 75
B 90 78 66 132 78
C 75 66 57 114 69
D 80 72 60 120 72
E 76 64 56 112 68
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Check-I Balance Check- A Problem is balanced if no. of rows and columns
are equal if they are not equal we need to add a dummy row or dummy
column with all values as zero.
This is a Balanced problem because no. of rows and columns are equal.
Check-II Minimization Check-After balance check ensure it is a
minimization problem. If it is a maximization problem convert it into
minimization by subtracting all the values from the highest value of the
matrix.
This is already a minimization problem,
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Step-I Subtract Least element of each row from other corresponding elements of that row.
P Q R S T
A 85 75 65 125 75
B 90 78 66 132 78
C 75 66 57 114 69
D 80 72 60 120 72
E 76 64 56 112 68
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 20 10 0 60 10
B 24 12 0 66 12
C 18 9 0 57 12
D 20 12 0 60 12
E 20 8 0 56 12
Step-II Subtract Least element of each column from other
corresponding elements of that column.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 2 2 0 4 0
B 6 4 0 10 2
C 0 1 0 1 2
D 2 4 0 4 2
E 2 0 0 0 2
Step-III Cover all the Zeros in minimum no. of Horizontal &
Vertical lines
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 2 2 0 4 0
B 6 4 0 10 2
C 0 1 0 1 2
D 2 4 0 4 2
E 2 0 0 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
If the minimum no. of lines is equal to order of the
matrix, Solution is ready for assignment.
If they are not equal then follow the below step:
The minimum no of lines covering all zeros is 4
which is less than the order of the matrix (5*5)
Hence subtract the least uncovered element from
all other uncovered elements and add that element
at the intersection of two lines.
The uncovered least element is 1 here.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 3 2 1 4 0
B 6 3 0 9 1
C 0 0 0 0 1
D 2 3 0 3 1
E 3 0 1 0 2
Still all zeros are covered in 4 lines, hence again deduct the least
uncovered element 2 & add at the intersection
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Now all zeros can be covered in minimum 5 lines, which is = order of
the matrix hence solution is ready for assignment.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
2
A 1 0 1 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 00 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 00 2 0 3
D 0 1 0 1 1
E 3 0 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
P Q R S T
A 1 0 1 2 0
B 4 1 0 7 1
C 0 0 2 0 3
D 0 1 0 1 1
E 3 00 3 0 2
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Alternate Answer
A-T 75 A-T 75
B-R 66 B-R 66
C-S 114 C-Q 66
D-P 80 D-P 80
E-Q 64 E-S 112
------------ ------------
Total 399 min Total 399 min
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Q. 3 A company plans to assign 5 salesmen to 5 districts. Estimates of Sales revenue in
thousands of Rupees for each salesman in different districts are given in the following table.
What should be the placement of salesmen so as to maximize the expected sales revenue?
Salesman /
D1 D2 D3 D4 D5
District
S1 40 46 48 36 48
S2 48 32 36 29 44
S3 49 35 41 38 45
S4 30 46 49 44 44
S5 37 41 48 43 47
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Check-I Balance Check- This is a Balanced problem
Check-II This is a maximization problem, we need to convert it into
minimization problem by subtracting all the elements from the highest
element of the matrix.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 9 3 1 13 1
S2 1 17 13 20 5
S3 0 14 8 11 4
S4 19 3 0 5 5
S5 12 8 1 6 2
Step-I Subtract Least element of each row from other corresponding elements of that row.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman/District D1 D2 D3 D4 D5
S1 8 2 0 12 0
S2 0 16 12 19 4
S3 0 14 8 11 4
S4 19 3 0 5 5
S5 11 7 0 5 1
Step-II Subtract Least element of each column from other corresponding elements of that column.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 8 0 0 7 0
S2 0 14 12 14 4
S3 0 12 8 6 4
S4 19 1 0 0 5
S5 11 5 0 0 1
Step-III Cover all the Zeros in minimum no of Horizontal & Vertical lines
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 8 0 0 7 0
S2 0 14 12 14 4
S3 0 12 8 6 4
S4 19 1 0 0 5
S5 11 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
The minimum no of lines covering all zeros is 4 which is less than the
order of the matrix (5*5)
Hence subtract the least uncovered element from all other uncovered
elements and add that element at the intersection of two lines.
The uncovered least element is 4 here.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
S2 0 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
S2 0 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Now all zeros can be covered in minimum 5 lines
which is = order of the matrix
hence solution is ready for assignment.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / District D1 D2 D3 D4 D5
S1 12 0 0 7 0
0
S2 10 8 10 0
S3 0 8 4 2 0
S4 23 1 0 0 5
S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Salesman / Salesman /
District
D1 D2 D3 D4 D5 D1 D2 D3 D4 D5
District
S1 12 0 00 7 0 S1 12 0 00 7 0
0 0 0
S2 10 8 10 00 S2 10 8 10 0
0 0
S3 0 8 4 2 0
0 S3 0 8 4 20 0
S4 23 1 0 0 5
0 S4 23 1 00 0 5
S5 15 5 0 0 1
S5 15 5 0 0 1
Salesman / Salesman /
District
D1 D2 D3 D4 D5 District
D1 D2 D3 D4 D5
S1 12 0 00 7 00 S1 12 0 00 7 0
0 0 0 0
S2 10 8 10 0 S2 10 8 10 0
0 0
S3 0 8 4 2
0 0 S3 0 8 40 2 0
S4 23 1 00 0 5 S4 23 1 0 00 5
S5 15 5 0 0 1 S5 15 5 0 0 1
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
S1-D2 46 S1-D2 46 S1-D2 46
S1-D2 46
S2-D1 48 S2-D5 44 S2-D5 44
S2-D1 48
S3-D5 45 S3-D1 49 S3-D1 49
S3-D5 45
S4-D4 44 S4-D3 49 S4-D4 44
S4-D3 49
S5-D3 48 S5-D4 43 S5-D3 48
S5-D4 43
------------ -------------- -------------
--------------
Total 231000
Total 231000 Total 231000 Total 231000
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Assignment Problem
Q-5 To stimulate interest and provide an atmosphere for intellectual discussion,
the finance faculty in a management school decides to hold special seminars on
four contemporary topics – leasing, portfolio management, private mutual funds,
swaps and options. Such seminars would be held once per week in the
afternoons. However, scheduling these seminars (one for each topic, and not
more than one seminar per afternoon) has to be done carefully so that the
number of students unable to attend is kept to a minimum. A careful study
indicates that the number of students who cannot attend a particular seminar on
a specific day is as follows: find the optimal assignment.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and
Leasing
Management Mutual funds Options
Monday 50 40 60 20
Tuesday 40 30 40 30
Wednesday 60 20 30 20
Thursday 30 30 20 30
Friday 10 20 10 30
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Check-1 Balance Check- As no. of rows and columns are not equal we need to add a
dummy column to make it a balance problem.
Private
Portfolio Swaps and
Leasing Mutual Dummy
Management Options
funds
Monday 50 40 60 20 0
Tuesday 40 30 40 30 0
Wednesday 60 20 30 20 0
Thursday 30 30 20 30 0
Friday 10 20 10 30 0
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Check-2 Minimization Check-
As no. of absentees is to be reduced, it is a minimization problem.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Step-I Subtract Least element of each row from other corresponding elements of that row.
As 0 is the least value in each row, we will get the same matrix
Private
Portfolio Swaps and
Leasing Mutual Dummy
Management Options
funds
Monday 50 40 60 20 0
Tuesday 40 30 40 30 0
Wednesday 60 20 30 20 0
Thursday 30 30 20 30 0
Friday 10 20 10 30 0
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Step-II Subtract Least element of each column from other corresponding elements
of that column.
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 40 20 50 0 0
Tuesday 30 10 30 10 0
Wednesday 50 0 20 0 0
Thursday 20 10 10 10 0
Friday 0 0 0 10 0
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Step-III Cover all the Zeros in minimum no. of Horizontal & Vertical lines
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 40 20 50 0 0
Tuesday 30 10 30 10 0
Wednesday 50 0 20 0 0
Thursday 20 10 10 10 0
Friday 0 0 0 10 0
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Step-III Cover all the Zeros in minimum no. of Horizontal & Vertical lines
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 40 20 50 0 0
Tuesday 30 10 30 10 0
Wednesday 50 0 20 0 0
Thursday 20 10 10 10 0
Friday 0 0 0 10 0
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
The minimum no. of lines covering all zeros is 4 which is less than the order of
the matrix (5*5)
Hence subtract the least uncovered element from all other uncovered elements
and add that element at the intersection of two lines.
The least uncovered element is 10 here.
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 0
Tuesday 20 0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 0 0 20 10
Repeat step-III
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 0
Tuesday 20 0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 0 0 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Now all zeros can be covered in minimum 5 lines
which is = order of the matrix
hence solution is ready for assignment.
The first assignment should be given in the zero which is single in
entire row & column then move to single zero either in row or column
& so on. Once we give assignment in any zero cancel all other zeros
of that row & column
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 0
Tuesday 20 0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 0 0 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 00
Tuesday 20 0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 0 0 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 00
Tuesday 20 0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 0 0 10 0
Friday 0 00 00 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 00
Tuesday 20 0
0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 00 0 10 0
Friday 0 00 00 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 00
Tuesday 20 0
0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 00 0 10 00
Friday 0 00 00 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Portfolio Private Swaps and Dummy
Leasing
Management Mutual funds Options
Monday 30 10 40 0 00
Tuesday 20 0
0 20 10 0
Wednesday 50 0 20 10 10
Thursday 10 00 0 10 00
Friday 0 00 00 20 10
Unit 4 Assignment Problem Centre for Distance and Online Education
Subject Name: Operation Research
Monday Swaps & Options 20
Tuesday Dummy 0
Wednesday Portfolio Mgmt 20
Thursday Private Mutual Funds 20
Friday Leasing 10
-------------------------------------
Total 70
Unit 4 Assignment Problem Centre for Distance and Online Education
