242 Operations Research

○
○
FlightNo. 201 202 203 203

○
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

101 0 0 0 0

○
○
102 0 0 0 0

○
○
○ ○ 103
○ ○ ○ ○ ○ ○ ○ ○ 0 ○ ○ ○ ○ 4 ○ ○ ○ ○ 10 ○ ○ ○ ○ 2
○ ○ ○ ○ ○

○
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

○
104 0 0 0 24

○
○
FlightNo. 201 202 203 204
101 0 0 0 0*
102 0 0* 0 0
103 0 4 10 2
104 0 0 0* 24
Assignment:
Flight No. Leaves as Based at
101 204 Bangalore
102 202 Bangalore
103 201 Chennai
104 203 Bangalore.

Total layover time: 10 + 22 + 20 + 5 = 67 hours.

5.6. TRAVELING SALESMAN PROBLEM

Just consider how a postman delivers the post to the addressee. He arranges all the letters in an order
and starts from the post office and goes from addressee to addressee and finally back to his post
office. If he does not arrange the posts in an order he may have to travel a long distance to clear all the
posts. Similarly, a traveling sales man has to plan his visits. Let us say, he starts from his head office
and go round the branch offices and come back to his head office. While traveling he will not visit the
branch already visited and he will not come back until he visits all the branches.
There are different types of traveling salesman's problems. One is cyclic problem. In this problem,
he starts from his head quarters and after visiting all the branches, he will be back to his head quarters.
The second one is Acyclic problem. In this case, the traveling salesman leaves his head quarters and
after visiting the intermediate branches, finally reaches the last branch and stays there. The first type of
the problem is solved by Hungarian method or Assignment technique. The second one is solved by
Dynamic programming method.
Point to Note: The traveling salesman's problem, where we sequence the cities or branches
he has to visit is a SEQUENCING PROBLEM. But the solution is got by Assignment technique.
Hence basically, the traveling salesman problem is a SEQUENCING PROBLEM; the objective
is to minimize the total distance traveled.
The mathematical statement of the problem is: Decide variable xij = 1 or 0 for all values of I and
j so as to:
Linear Programming - III Assignment Model 243

n n

Minimise Z = ∑ ∑C ij for all i and j = 1,2…..n Subject to

i =1 j =1

∑X
J =1
ij = 1 for i = 1,2,….n (Depart from a city once only)

∑X
i =1
ij = 1 for j = 1,2,….n (Arrive at a city once only)

And all xij ≥ 0 for all i and j

This is indeed a statement of assignment problem, which may give to or more disconnected
cycles in optimum solution. This is not permitted. That is salesman is not permitted to return to the
origin of his tour before visiting all other cities in his itinerary. The mathematical formulation above
does not take care of this point.
A restriction like Xab + Xbc + Xca ≤ 2 will prevent sub-cycles of cities A, B, C and back to A. It
is sufficient to state at this stage that all sub- cycles can be ruled out by particular specifications of
linear constraints. This part, it is easy to see that a variable xij = 1, has no meaning. To exclude this
from solution, we attribute very large cost to it i.e. infinity or big M, which is very larger than all the
elements in the matrix.
In our solutions big M is used.

Problem 5.14.
A salesman stationed at city A has to decide his tour plan to visit cities B, C, D, E and back to city
A I the order of his choice so that total distance traveled is minimum. No sub touring is permitted. He
cannot travel from city A to city A itself. The distance between cities in Kilometers is given below:
Cities A B C D E
A M 16 18 13 20
B 21 M 16 27 14
C 12 14 M 15 21
D 11 18 19 M 21
E 16 14 17 12 M

Instead of big M we can use infinity also. Or any element, which is sufficiently larger than all the
elements in the matrix, can be used.
Solution
COCM:
Cities A B C D E
A M 3 5 0 7
B 7 M 2 13 0
C 0 2 M 3 9
D 0 7 8 M 10
E 4 2 5 0 M
244 Operations Research

TOCM:

○
○
Cities A B C D E

○
A M 1 3 0 7

○
○
B 7 M 0 13 0

○
○
C 0 0 M 3 9

○
○
D 0 5 6 M 10

○
○
E 4 0 3 0 M

○
○
We can make only 4 assignments. Hence modify the matrix. Smallest element in the uncovered
cells is 3, deduct this from all other uncovered cells and add this to the elements at the crossed cells. Do
not alter the elements in cells covered by the line.
TOCM
○

○
Cities A B C D E
○

○
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
○

○
A M 1 3 0 7
○

○
○

○
B 7 M 0 13 0
○

○
○

○
C 0 0 M 3 9
○

○
○

D 0 5 6 M 10
○

E 4 0 3 0 M
○

○
○

○
○

We can make only 4 assignments. Hence once again modify the matrix.
Sequencing: A to C, C to B, B to E, E to D, and D to A. As there is a tie
TOCM:
Cities A B C D E
A M 1 0 0 4
B 10 M 0 16 0
x
C 0x 0 M 3 6
D 0 5 3 M 7
E 4 0x 0 0 M

Sequencing: A to C, C to B, B to E, E to D and D to A. as there is a tie between the zero cells, the

problem has alternate solution. The total distance traveled by the salesman is: 18 + 14 + 14 + 11 + 12
= 69 Km.
A to C to B to E to D to A, the distance traveled is 69 Km.
Note: See that no city is visited twice by sales man.

Problem 5.15.
Given the set up costs below, show how to sequence the production so as to minimize the total
setup cost per cycle.
Linear Programming - III Assignment Model 245

Jobs A B C D E
A M 2 5 7 1
B 6 M 3 8 2
C 8 7 M 4 7
D 12 4 6 M 5
E 1 3 2 8 M

Solution
COCM:
Jobs A B C D E
A M 1 4 6 0
B 4 M 1 6 0
C 4 3 M 0 3
D 8 0 2 M 1
E 0 2 1 7 M

TOCM:
Jobs A B C D E
A M 1 3 6 0
B 4 M 0 6 0x
C 4 3 M 0 3
D 8 0 1 M 1
E 0 2 0x 7 M

We can draw five lines and make assignment. The assignment is:
From A to E and From E to A cycling starts, which is not allowed in salesman problem. Hence
what we have to do is to select the next higher element than zero and make assignment with those
elements. After assignment of next higher element is over, then come to zero for assignment. If we
cannot finish the assignment with that higher element, then select next highest element and finish
assigning those elements and come to next lower element and then to zero. Like this we have to finish
all assignments. In this problem, the next highest element to zero is 1. Hence first assign all ones and
then consider zero for assignment. Now we shall first assign all ones and then come to zero.
TOCM:
Jobs A B C D E
A M 1 3 6 0x
B 4 M 0 6 0x
C 4 3 M 0 3
D 8 0 1 M 1
E 0 2 0x 7 M
246 Operations Research

The assignment is A to B, B to C, C to D and D to E and E to A. (If we start with the element DC

then cycling starts.
Now the total distance is 5 + 3 + 4 + 5 + 1 = 18 + 1 + 1 = 20 Km. The ones we have assigned are
to be added as penalty for violating the assignment rule of assignment algorithm.

Problem 5.16.
Solve the traveling salesman problem by using the data given below:
C12 = 20, C13 = 4, C14 = 10, C23 = 5, C34 = 6, C25 = 10, C35 = 6, C45 = 20 and Cij = Cji . And there
is no route between cities 'i' and 'j' if a value for Cij is not given in the statement of the problem. (i and
j are = 1,2,..5)

Solution
Cities 1 2 3 4 5
1 M 20 4 10 M
2 20 M 5 M 10
3 4 5 M 6 6
4 10 M 6 M 20
5 M 10 6 20 M

Now let us work out COCM/ROCM and TOCM, and then make the assignment.
TOCM:
Cities. 1 2 3 4 5
1 M 12 0 0x M
2 11 M 0x M 0
3 0x 1 M 0 1
4 0 M 0x M 9
5 M 0 0x 8 M

The sequencing is: 1 to3, 3 to 4, 4 to 1 and 1 to 3 etc., Cycling starts. Hence we shall start
assigning with 1 the next highest element and then assign zeros. Here also we will not get the sequencing.
Next we have to take the highest element 8 then assign 1 and then come to zeros.
TOCM:
Cities. 1 2 3 4 5
1 M 12 0 0 M
2 11 M 0 M 0
3 0 1 M 0 1
4 0 M 0 M 9
5 M 0 0 8 M

Sequencing is: 1 to 3, 3 to 2, 2 to 5, 5 to 4 and 4 to 1.

The optimal distance is : 4 + 10 + 5 + 10 + 20 = 49 + 1 + 8 = 58 Km.
Linear Programming - III Assignment Model 247

Problem 5.17.
A tourist organization is planning to arrange a tour to 5 historical places. Starting from the head
office at A then going round B, C, D and E and then come back to A. Their objective is to minimize the
total distance covered. Help them in sequencing the cities. A, B, C, D and E as the shown in the figure.
The numbers on the arrows show the distances in Km.

Solution
The distance matrix is as given below:
Places A B C D E
A M 20 M 10 10
B 20 M 30 M 35
C M 30 M 15 20
D 10 M 15 M 20
E 10 35 20 20 M

COCM
Places A B C D E
A M 10 M 0 0
B 0 M 10 M 15
C M 15 M 0 5
D 0 M 5 M 10
E 0 25 10 10 M

TOCM:
○

○
○

Places A B C D E
○

○
○

○
○

A M 0 M 0 0
○

○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
○
○

○
○

B 0 M 5 M 15
○

○
○

○
○

C M 5 M 0 5
○

○
○

○
○

D 0 M 0 M 10
○

○
○

E 0 15 5 10 M
○
○

○
○

○
○

○
248 Operations Research

TOCM:

○
○
○
Places A B C D E

○
○
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

A M 0 M 5 0

○
○

○
○
B 0 M 5 M 10

○
○

○
○
○ ○

C ○ ○ ○ ○ ○

M ○ ○ ○ ○

0 ○ ○ ○ ○

M ○ ○ ○ ○

0 ○ ○ ○

0 ○ ○ ○ ○

○
○

○
○
D 0 M 0 M 5

○
○

○
E 0 10 5 10 M

○
○

○
○
TOCM:

○
○
Places A ○
○
B C D E
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

A M 0 M 5 0
○
○

B 0 M 5 M 5
○
○

○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

C M 0 M 0 0
○

○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
○

D 0 M 0 M 0
○

E 0 5 5 5 M
○
○
○

Places A B C D E
A M 0 M 5 0x
B 0x M 0 M 0x
C M 0x M 0 0x
D 5 M 0x M 0
E 0 0x 0x 0x M

The sequencing is: A to B, B to C, C to D, D to E and E to A.

The total distance is: 20 +30 +15 + 20 + 10 = 95 Km.

5.7. SENSITIVITY ANALYSIS

In fact there is very little scope for sensitivity analysis in Assignment Problem because of the mathematical
structure of the problem. If we want to avoid high cost assigning a facility ( i th) to a job (j th), then we
can do it by giving a cost of assignmat say infinity or Big M to that cell so that it will not enter into
programme. In case of maximisaton model, we can allocate a negative element to that cell to avoid it
entering the solution. Further, if one facility (man) can do two jobs i.e. 2 jobs are to be assigned to the
facility, then this problem can be dealt with by repeating the man's or facility's column and introducing
a dummy row to maintain the square matrix. Similarly, if two similar jobs are there, write two identical
rows of the two jobs separately and then solve by making a square matrix. Besides these, the addition
of a constant throughout any row or column does not affect the optimal solution of the assignment
problem.