Page 173 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes (2) Column-wise Reduced Matrix.
To A B C D
From
a - 1 1 0
b 1 - 0 0
c 1 0 - 1
d 0 0 4 -

(3) The Route Chosen for Journey are:
From To Journey Time
a D 3
b C 6
c B 6
d A 3
Total time 18

Note: There is looping in the above solution. Hence, it is not a unique solution to the travelling
salesman problem. Hence, requires further modification.
(4) Modified Matrix - 1

A B C D
a - 1 1 0
b 1 - 0 0
c 1 0 - 1
d 0 0 4 -

(5) Calculation of Minimum Total Time Required to complete the journey.

From To Journey Time
a D 3
b C 6
c A 7
d B 3
Total time 19

Inference

The unique and optimum solution shows that the minimum time required is 19 hours.

Task For a salesman who has to visit n cities, which of the following are the ways of his
tour plan

a. n! b. (n+1)!
c. (n-1)! d. n

168 LOVELY PROFESSIONAL UNIVERSITY