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

Maximal assingment problem

	A	B	C	D
P	11	11	9	9
Q	13	16	11	10
R	12	17	13	8
S	16	14	16	12

To convert this problem into minimisation problem, subtract all th element from maximum value i.e. 17

Our new matris

	A	B	C	D
P	6	6	8	8
Q	4	1	6	7
R	5	0	4	9
S	1	3	1	5

Now reduce minimum value of row from all elements

	A	B	C	D
P	0	0	2	2
Q	3	0	5	6
R	5	0	4	9
S	0	3	0	5

Now subtract minimum value of column from all elements

	A	B	C	D
P	0	0	2	0
Q	3	0	5	4
R	5	0	4	7
S	0	3	0	3

Number of crossing line(bolded row and column)$=3$

But order of matrix $=4$

$3<4$ (not optimal solution)

Now subtract uncrossed minimum element from uncrossed(unbolded element) and add at the T - point(Junction of bolded row and bolded column)

	A	B	C	D
P	0	3	2	0
Q	0	0	2	1
R	2	0	1	4
S	0	6	0	3

Number of crossing line(bolded row and column)$=4$

But order of matrix $=4$

$4=4$ (optimal solution)

assigmnrnt of job

$P\to D$

$Q\to Q$

$R\to B$

$S\to C$

So maximum time $9+13+17+12=51$