Page 172 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 8: Assignment Problem – Unbalanced

(6) Modified Matrix 2. Notes
To A B C D E
From
a  0 2 0 1
b 0  0 0 1
c 1 0  2 0
d 0 0 3  5
e 0 0 0 4 

(7) Calculation of Minimum Total Time Required for Travelling.
From To Travelling Time (Hours)
a E 4
b D 3
c B 6
d A 3
e C 5
Total Time 21

Inference
The minimum time required to complete the travel programme with the above unique solution
works out to be 21 hours.

Example: A salesman has to visit 4 cities A, B, C, and D. The distance (100 kms) between
4 cities is:

To
From A B C D
a - 4 7 3
b 4 - 6 3
c 7 6 - 7
d 3 3 7 -

If the salesman starts from city 'A' and comes back to city 'A', which route should he select so that

total distance travelled by him is minimum?
Solution:

Application of Reduction Theorem Rules
(1) Row-wise Reduced Matrix.

To A B C D
From
a - 1 4 0
b 1 - 3 0
c 1 0 - 1
d 0 0 7 -

LOVELY PROFESSIONAL UNIVERSITY 167