Advertisement Remove all ads

A company has a team of four salesmen and there are four districts where the company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts, - Mathematics and Statistics

Sum

A company has a team of four salesmen and there are four districts where the company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts, the company estimates that the profit per day in rupees for each salesman in each district is as below:

Salesman District
  1 2 3 4
A 16 10 12 11
B 12 13 15 15
C 15 15 11 14
D 13 14 14 15

Find the assignment of salesman to various districts which will yield maximum profit.

Advertisement Remove all ads

Solution

Step 1:
Since it is a maximization problem, subtract each of the elements in the table from the largest element, i.e., 16

Salesman District
  1 2 3 4
A 0 6 4 5
B 4 3 1 1
C 1 1 5 2
D 3 2 2 1

Step 2:
Row minimum Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:

Salesman District
  1 2 3 4
A 0 6 4 5
B 3 2 0 0
C 0 0 4 1
D 2 1 1 0

Step 3:
Column minimum Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.

Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.

Salesman District
  1 2 3 4
A 0 6 4 5
B 3 2 0 0
C 0 0 4 1
D 2 1 1 0

Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is equal to order of the matrix, i.e., 4.
∴ Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:

Salesman District
  1 2 3 4
A 0 6 4 5
B 3 2 0 0
C 0 0 4 1
D 2 1 1 0

Step 6:
The matrix obtained in step 5 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:

Salesman District Profit (in ₹)
A 1 16
B 2 15
C 3 15
D 4 15

∴ The maximum profit = 16 + 15 + 15 + 15 = ₹ 61.

  Is there an error in this question or solution?
Advertisement Remove all ads

APPEARS IN

Balbharati Mathematics and Statistics 2 (Commerce) 12th Standard HSC Maharashtra State Board
Chapter 7 Assignment Problem and Sequencing
Exercise 7.1 | Q 5 | Page 119
Advertisement Remove all ads
Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×