Page 171 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes (ii) Modified Matrix – 2
To A B C D E
From
a - 0 1 0 0
b 0 - 0 0 1
c 2 2 - 6 0
d 0 0 2 - 3
e 2 0 0 6 -

Note: This alternative cannot be worked out as no unique zero remains in the third row
after choosing next minimum element '1' in the II row.
(3) Calculation of Travelling Expenses.

From To Travelling Expenses (`)
a 3 12
b 4 5
c 5 3
d 1 5
e 2 2
Total Expenses 27

Inference
The minimum travelling expenses with an unique and optimum solution to the above problem
works to be ` 27.

(4) Modified Matrix-1.
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 

Note: There are three alternative solutions to the above matrix.
(5) (a) Alternative 1 (b) Alternative - 2 (c) Alternative - 3
From To From To From To
a B a D a D
b D b A b C
c E c E c E
d A d B d A
e C e C e B

Note: Observe there is presence of looping in all the three solutions. Hence, they are not
the unique solutions to travelling salesman problem. Further, the matrix is to be modified.

166 LOVELY PROFESSIONAL UNIVERSITY