Page 168 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 8: Assignment Problem – Unbalanced

Notes
Example: Solve the following travelling salesman problem with the following matrix.

Travelling Expenses
To
From 1 2 3 4 5
I - 6 12 6 4
II 6 - 10 5 4
III 8 7 - 11 3
IV 5 4 11 - 5
V 5 2 7 8 -

Solution:

Apply Reduction Theorem Rules
1. Row-wise Reduced Matrix.

To
From 1 2 3 4 5
I - 2 8 2 0
II 2 - 6 1 0
III 5 4 - 8 0
IV 1 0 7 - 1
V 3 0 5 6 -
2. Column-wise Reduced Matrix.

To
From 1 2 3 4 5
I - 2 3 1 0
II 1 - 1 0 0
III 4 4 - 7 0
IV 0 0 2 - 1
V 2 0 0 5 -
L1 L2
Note: Used Hungarian approach and get the improvised matrices.

3. Modified Matrix – 1.

To
From 1 2 3 4 5
I - 1 2 1 0
II 0 - 0 0 0
III 3 3 - 7 0
IV 0 0 2 - 0
V 2 0 0 6 0
L1 L2

LOVELY PROFESSIONAL UNIVERSITY 163