Question

Solve the following maximal assignment problem :

Branch Manager	Monthly Business ( Rs. lakh)
	A	B	C	D
P	11	11	9	9
Q	13	16	11	10
R	12	17	13	8
S	16	14	16	12

 

Answer 1

Branch Manager	Monthly Business ( Rs. lakh)
	A	B	C	D
P	11	11	9	9
Q	13	16	11	10
R	12	17	13	8
S	16	14	16	12

Step 1 : Since it is a maximization problem subtract each of the element in the table from the largest element.

Branch Manager	Monthly Business ( Rs. lakh)
	A	B	C	D
P	6	6	8	8
Q	4	1	6	7
R	5	0	4	9
S	1	3	1	5

Step 2 : Minimum element of each row is subtracted from every element in that row.

Branch Manager	Monthly Business ( Rs. lakh)
	A	B	C	D
P	0	0	2	2
Q	3	0	5	6
R	5	0	4	9
S	0	2	0	4

Step 3 : Minimum element of each column is subtracted from every element in that column.

Branch Manager	Monthly Business ( Rs. lakh)
	A	B	C	D
P	0	0	2	0
Q	3	0	5	4
R	5	0	4	7
S	0	2	0	2

Step 4 : Zero elements are covered With minimum number of straight lines.

Step 5 : Selecting the smallest element not covered by the lines and subtracting it from each uncovered element and add it to the intersection of the lines.

Step 6 : Covering all zeros by minimum  number of straight lines.

Minimum number of lines = order of matrix. so optimal solution has reached.
Step 7 : Making assignment at single zero of  the row and then at single zero of the column.

The optimal assignment is
P → D
Q → A
R →  B
S →  C
Maximum Profit = 9 + 13 + 17 + 16 = 55 lakhs.