USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

THE TRAVELLING SALESMAN PROBLEM

One of the major applications of the assignment models is in the travelling salesman problem. Let us say that a salesman has to visit n destinations. He starts from a particular city, visits destination once -and then comes back to the city from where he started. Here the objective would minimise the time this salesman takes to visit all the destinations. The problem is to select that sequence which all the destinations are visited in such a manner that the time taken is minimised. This problem similar to the assignment problems already seen except that there is an additional restriction that salesman starting from a particular city, visits each destinations only once and returns to his city from he started.

FORMULATION OF TRAVELLING SALESMAN PROBLEM

Let us define the variables Xjj k as (notice constraint k has been added in addition to i and j already there) 

where dij is the distance from city i to city j.

Example 6.3. A salesman has to visit five cities A, B, C, D and E. The intercity distances are tabulated below:

To         From

A

B

C

D

E

A

-

12

25

26

16

B

7

-

17

19

8

C

10

11

-

19

12

D

15

18

23

-

17

E

12

14

24

26

-

‘The above distances in KM between two cities need not be same both ways.

Which route would you advise the salesman to take so that the total distance travelled by him is minimum, if the salesman starts from city A and has to come back to city ‘A’?

Sol. Step 1. Select the smallest element in each row and subtract it from every element of that row. Row reduction results in the following matrix.

To         From

A

B

C

D

E

A

-

0

13

14

4

B

0

-

10

12

1

C

0

1

-

9

2

D

0

3

8

-

2

E

0

2

12

14

-

 

Step II. Select the minimum element in each column and subtract this element from every element in that column, we get

To         From

A

B

C

D

E

A

-

0

5

5

3

B

0

-

2

3

0

C

0

1

-

0

1

D

0

3

0

-

1

E

0

2

4

5

-

Step III. Draw minimum number of lines to cover all the zeros.

To         From

A

B

C

D

E

A

-

0

5

5

3

B

0

-

2

3

0

C

0

1

-

0

1

D

0

3

0

-

1

E

0

2

4

5

-

Since the number of lines = order of matrix (5), this gives the optimal solution.

Step IV. Making assignment in zero positions does not satisfy the constraints of the problem. He the following assignment are made by hit and trial.

To         From

A

B

C

D

E

A

-

0

5

5

3

B

0

-

2

3

0

C

0

1

-

0

1

D

0

3

0

-

1

E

0

2

4

5

-

Optimal schedule is A → B,

B →C,

C → D,

D → E,

E → A

involving distance 12 + 17 + 19 + 17 + 12 = 77 km.

This route satisfies the travelling salesman problem.

Unbalanced Problems

Example 6.4. A transport corporation has three vehicles in three cities. Each of vehicles can be assigned to any of the four other cities. The distance differs from one city to the other as under.

1

2

3

4

A

33

40

43

32

B

42

30

31

24

C

40

31

37

31

you are required

a)     To assign a vehicle to a city in such a way that the total distance travelled is minimised.

b)    Formulate a mathematical model of the problem.

Sol. Step I. Introduce a dummy vehicle in city D as the problem is not balanced and take 0 distances as follows.

1

2

3

4

A

33

40

43

32

B

42

30

31

24

C

40

31

37

31

D

0

0

0

0

Step II. Subtract the minimum element of each row from all the elements of that row. There is no need to subtract 0 from each column. The matrix is

1

8

11

0

18

6

7

0

9

0

6

0

0

0

0

0

Step III. Draw minimum number of lines to cover all zero. It can be seen that number of lines = 3, order of matrix = 4. Hence this is not an optimal solution and we have to take steps to increase number of zeros.

1

8

11

6

18

6

7

0

9

0

6

0

0

0

0

0

Step IV. Subtract the minimum uncovered element (1) from all the uncovered elements and adding it elements at the intersection point. Draw minimum number of lines to cover all the zeros we get

0

7

10

0

17

5

6

0

9

0

6

1

0

0

0

1

Now, number of lines = 4, and is equal to the order of the matrix hence, this matrix will provide an optimal solution.

Step V. Assignments can be made as shown below.

0

7

10

0

17

5

6

0

9

0

6

1

0

0

0

1

Step VI. Minimum distance can be worked out as follows.

City

Vehicle

Distance

A

1

33

B

4

24

C

2

31

D

3

0

Total

88

(b) Formulation of LPP

x11

33

X12

40

x13

43

X14

32

X21

42

X22

30

X23

31

X24

24

X31

40

X32

31

X33

37

X34

31

X41

0

X42

0

X43

0

X44

0

 

Minimise Z = 33 x11 + 40 x12 + 43 x13 + 32 x14 + 42 x21 + 30 x22 + 31 x23 + 24 x24 + 40 x31 + 31 x32 + 37 x33 + 31 x34 + 0 x41 + 0 x42 + 0 x43 + 0 x44

Subject to x11 + x12 + x13 + x14 = 1

x21 + x22 + x23+ x24 = 1

x31 + x32 + x33 + x34 = 1

x41 + x42 + x43 + x44= 1

xij ≥ 0.

Example 6.5Solve the following unbalanced assignment problem of minimising total time for doing all the jobs.

Operator

Jobs

1

2

3

4

5

A

8

3

6

3

7

B

3

6

9

8

8

C

9

9

7

9

8

D

7

2

3

5

6

E

10

3

8

9

7

F

5

7

4

7

8

Sol. Step-I. Introducing dummy job 6 to make the problem balanced allotting 0 timing.

Operator

 

Jobs

1

2

3

4

5

6

A

8

3

6

3

7

0

B

3

6

9

8

8

0

C

9

9

7

9

9

0

D

7

2

3

5

6

0

E

10

3

8

9

7

0

F

5

7

4

7

8

0

Step II. Since 0 is in each row, there is no need of row deduction, column deduction is done by subtracting the minimum element of each column from all the elements of that column, we have

Operator

 

Jobs

1

2

3

4

5

6

A

5

1

3

0

1

6

B

0

4

6

5

2

0

C

6

7

4

6

3

0

D

4

0

0

2

0

0

E

7

1

5

6

1

0

F

2

5

1

4

2

0

Draw minimum number of lines to cover all the zeros, since lines = 4 is less than the order of the matrix (6) this is not an optimal solution.

Step III. Subtracting the minimum uncovered element (1) from all uncovered elements and adding it to the elements of intersection points of the lines, we have

Operator

 

Jobs

1

2

3

4

5

6

A

5

1

3

0

1

1

B

0

4

6

5

2

1

C

5

6

3

5

2

0

D

4

0

0

2

0

1

E

6

0

4

5

0

0

F

1

4

0

3

1

0

Since number of lines-drawn (6) = order of matrix, this is the optimal solution,

Step IV. Assignments are made as shown below.

Operator

 

Jobs

1

2

3

4

5

6

A

5

1

3

0

1

1

B

0

4

6

5

2

1

C

5

6

3

5

2

0

D

4

0

0

2

0

1

E

6

0

4

5

0

0

F

1

4

0

3

1

0

Step V. Computing the minimum time.

Operator

Job

Time

A

4

3

B

1

3

C

6

0

D

5

6

E

2

3

F

3

4

Total = 19

Example 6.6. Four operators A, B, C and D are available to a manager who has to get four jobs J – I, J – 2, J – 3 and J – 4, done by assigning one job to each operator. Given the time needed by different operators for different jobs as per the following matrix.

J-1

J-2

J-3

J-4

A

10

8

10

9

B

12

10

14

10

C

6

8

16

6

D

8

9

7

7

How should the manager assign the jobs so that the total time needed for all four jobs is minimum?

Sol. Subtract the minimum element of each row from all the elements of that row, we have

Step I

J-1

J-2

J-3

J-4

A

2

0

2

1

B

2

0

4

0

C

0

2

10

0

D

1

2

0

0

Step II. Subtract the minimum element of each column from all elements of that column. Since all columns have zero, there will be no change in the matrix.

Step III. Draw minimum number oflines to cover all the zeros, the matrix is as follows.

J-1

J-2

J-3

J-4

A

2

0

2

1

B

2

0

4

0

C

0

2

10

0

D

1

2

0

0

As the number of lines (4) is equal to the order of matrix, this is the optimal solution.

Step IV. Making the assignments

J-1

J-2

J-3

J-4

A

2

0

2

1

B

2

0

4

0

C

0

2

10

0

D

1

2

0

0

Step V. Computing the minimum time

Operator

Job

Time

A

J-2

8

B

J-4

10

C

J-1

6

D

J-3

7

Total = 31

Example 6.7. A manufacturing company has four zones Z – 1, Z -2, Z – 1 and Z – 4 and four sales engineers A, B, C and D respectively for assignments. The zones are not equally rich in sales potential and it is estimated that a particular engineer operating in a particular zone will yield the following sales.

Z-1      :           4,50,000

Z-2      :           3,40,000

Z-3      :           3,00,000

Z-4      :           4,60,000

The engineers have different sales ability. Working under the same conditions their yearly sales are proportional to 15, 10, 12, 8 respectively. The criteria of maximum expected total sales is to be met by assigning the best engineer to the richest zone, the next best to the second richest zone and 5.0 on.

Find the optimal assignment and the maximum sales.

Sol. Step I. The revenue matrix is as shown below. 

 

 

The matrix, after multiplications is reduced to

 

Z-1

Z-2

Z-3

Z-4

A

150

114

100

154

B

100

75.5

(76)

67

102

C

120

90.5

(91)

80

123

D

80

60.5

(61)

53.5

(54)

82

 

Step II. Now the problem can be reduced to minimisation i.e. loss matrix can be formulated by acting all elements from the largest value i.e., 154.

 

Z-1

Z-2

Z-3

Z-4

A

4

40

54

0

B

54

78

87

52

C

34

63

74

31

D

74

93

100

72

 

Subtract the minimum elements of each row from all elements of that row, we have

 

Z-1

Z-2

Z-3

Z-4

A

4

40

54

0

B

2

26

35

0

C

3

32

43

0

D

2

21

28

0

 

Step IV. Subtract the minimum element of each column from all elements of that column and draw minimum number of lines to cover all zeros, we get

 

Z-1

Z-2

Z-3

Z-4

A

2

19

26

0

B

0

5

7

0

C

1

11

15

0

D

0

0

0

0

 

Since there are 3 lines and order of matrix is four, this matrix does not provide .the optimal solution.

 

Step V. Subtract the minimum uncovered element (1) from all uncovered elements and add the elements at the intersection points of the lines and again draw minimum number of lines to cover all zeros.

 

Z-1

Z-2

Z-3

Z-4

A

1

18

25

0

B

0

5

7

1

C

0

10

14

0

D

0

0

0

0

 

Again there are 3 lines hence it is not optimal solution, so subtract the minimum uncovered element from all elements which are uncovered and add to the elements at the intersection points, we get

 

Z-1

Z-2

Z-3

Z-4

A

1

13

20

0

B

0

0

2

1

C

0

5

9

0

D

5

0

0

6

 

Now number of lines = order of matrix, so this will give us the optimal solution.

 

Step VI. Making the assignments in the usual manner, we have

 

Z-1

Z-2

Z-3

Z-4

A

1

13

20

0

B

0

0

2

1

C

0

5

9

0

D

5

0

0

6

 

Step VII. Computing the maximum sides 

It can be seen from above assignments that the best engineer A has been assigned the richest zone Z – 4, the next-best engineer C has been assigned the next richest zone Z – 1, and so on.

Example 6.8. MIS Steadfast Enterprise has four plants each of which can manufacture anyone of the four products. Product costs differ from one plant to another as follows:-

Product

Plant

P

Q

R

S

1

33

40

43

32

2

45

28

30

23

3

42

29

35

29

4

27

42

45

38

Find out which product each plant should produce to minimise cost. Also, formulate a LPP.

Sol. Step I. Subtracting the minimum element of each row from all the elements of that row.

1

8

11

0

12

5

7

0

13

0

6

0

0

15

18

11

Step II. Subtracting the minimum elements of each column of the above matrix from all the elements of that column.

1

8

5

0

12

5

1

0

13

0

0

0

0

15

12

11

Step III. Draw minimum number of lines (horizontal/vertical) to cover all the zero.

1

8

5

0

12

5

1

0

13

0

0

0

0

15

12

11

Since the number of lines, drawn is (3) less than the order of the matrix (4), we have to take steps to increase zeros and present solution is not optimal solution.

Step IV. Subtract the minimum uncovered element (1) from all the uncovered elements and add it to the elements at intersection point, we get the matrix.

0

7

4

0

11

4

0

0

13

0

0

1

0

15

12

12

Step V. Draw the minimum number of lines to cover all the zeros, we get

0

7

4

0

11

4

0

0

13

0

0

1

0

15

12

12

Since the number of lines drawn (4) is equal to the order of the matrix (4),the above matrix gives optimal solution.

Step VI. Select a row containing exactly one unmarked zero and put a ⎕ around it and draw a vertical line through the column containing this zero. Repeat this till no such row is left. Then select column containing exactly one unmarked zero and put a ⎕ around it and draw a horizontal line through the row containing this zero. Repeat this process till no such column is left.

P

Q

R

S

1

0

7

4

0

2

11

4

0

0

3

13

0

0

0

4

0

5

12

12

Step VII. Optimal assignment is

1 → S =32

2 → R=30

3 → Q=29

4 → P = 27

Minimum cost = 118

Formulation of LPP

x11

33

x12

40

x13

43

x14

32

x21

45

x22

28

x23

30

x24

23

x31

42

x32

29

x33

35

x34

29

x41

27

x42

42

x43

45

x44

38

 

Maximise Z = 33 x11 + 40 x12 + 43 x13 + 32 x14 +

45 x21 + 28 x22 + 30 x23 + 23 x24 +

42 x31 + 29 x32 + 35 x33 + 29 x34 +

27 x41 + 42 x42 + 45 x43 + 38 x44

X11 + x12 + x13 + x14 = 1

x21 + x22+ x23 + x24 = 1

x31 + x32 + x33 + x34 = 1

x41 + x42 + x43 + x44= 1

xij≥ 0.

Example 6.9. A Company is faced with assigning 5 jobs to 5 operators. Each job must be performed by one operator. The cost of processing of each job by each operator is given below in Rs.

Operators

P

Q

R

S

T

A

7

5

9

8

11

Jobs

B

9

12

6

11

10

C

8

5

4

6

8

D

7

3

6

8

5

E

5

6

7

5

11

Determine the assignment of jobs to the operators so that it will result in minimum cost.

Sol. Step I. Select the minimum element in each row and subtract the is element from every other element in that row.

P

Q

R

S

T

A

B

C

D

E

2

3

4

4

0

0

6

1

0

1

4

0

0

3

2

3

5

2

5

0

6

4

4

2

6

 

Step II. Now select the minimum element in each column and subtract this element from every other element in tat row element of that column, we get the following matrix.

P

Q

R

S

T

A

B

C

D

E

2

3

4

4

0

0

6

1

0

1

4

0

0

3

2

3

5

2

5

0

4

2

2

0

4

 

Step III. In row A, there is a single zero so assignment is made in cell AQ. In row B, there is a single zero, so assignment is made in cell BR. While making assignment in row AQ, the other zero appearing in the column Q i.e., in element DQ is crossed out. Similarly when assignment is made in row B in cell BR, the other zero in column R i.e., in cell CR is crossed out. 

While inspecting rows, row D has a single zero, assignment can be made in cell DT. No assignment can be made in row E, since it has two zeros.

Now inspect columns, column P has single zero, so assignment can be made in cell EP and other zero in row E i.e., in cell ES can be crossed out.

Since it is possible only to make 4 assignments against 5, so optimum solution is not reached. Number of lines drawn is equal to the number of assignments made.

Step IV. Examine the elements not covered by the lines and select the smallest element, in this ease 2 and subtract this from all the uncovered elements and add this to the elements lying at the intersection of the two lines. This gives us the following matrix.

 

Step V. Make assignment in row C where there is a single zero. Hence assignment in cell CS is made. Step VI. Optimum solution

A → Q=5

B → R=6

C → S=6

D → T=5

E → P=5

Minimum Total cost = Rs 27.

Example 6.10. The following is the cost matrix of assigning 4 professors to 4 key courses. Class preparation time in hours for different topics varies from professor to professor and is given in the table below. Each professor is assigned only one course so as to minimise the total preparation time for all courses.

Professor

Courses

C1

C2

C3

C4

A

B

C

D

2

15

13

4

10

4

14

15

9

14

16

13

7

8

11

9

 

Sol. Step I. Select minimum element’ from each row and subtract it from other elements of that row, we get

Courses

C1

C2

C3

C4

Professors

A

B

C

D

0

11

2

0

8

0

3

11

7

10

5

9

5

4

0

5

 

Step II. Select minimum element from each column and subtract it from other elements of that column.

 Courses

C1

C2

C3

C4

Professors

A

B

C

D

0

11

2

0

8

0

3

11

2

5

0

4

5

4

0

5

 

Step III. In first row, as there is a single zero, assignment can be made in cell AC1 and crossing out other zeros in column C1. In second row assignment can be made in cell 8C2, as there is a single zero. Similarly, assignment can be made in cell CC3 as follows.

Courses

C1

C2

C3

C4

Professors

A

B

C

D

0

11

2

8

8

0

3

11

2

5

0

4

5

4

0

5

 

As the number of assignment is less than the order of matrix, we have to proceed further as it is not the optimum solution. Also, draw minimum lines to cover all the zeros, we have

Courses

C1

C2

C3

C4

Professors

A

B

C

D

0

11

2

0

8

0

3

11

2

5

0

4

5

4

0

5

 

Step IV. Select the minimum number-out of the uncovered elements (2) subtract it from the uncovered elements and add to the elements at the intersection of lines, we get

Courses

C1

C2

C3

C4

Professors

A

B

C

D

0

13

4

0

6

0

3

9

0

5

0

2

3

4

0

3

 

Step V. Make fresh assignments 

Now the number of assignments is equal to the order of the matrix hence, this is the optimal solution.

Professor

Course

Time

A

C3

9

B

C2

4

C

C4

11

D

C1

4

Total minimum course duration = 28 minutes

Ex. 6.11. In a modification of plant layout of a factory four new machines are to be installed in a machine shop. There are five vacant sheds A, B, C, D & E available. Because of limited space machine 2 cannot be placed at C and M3 cannot be placed at A. The cost is shown below. Find optimum assignment schedule.

A

B

C

D

E

M1

M2

M3

M4

9

12

-

14

11

9

11

8

15

-

14

12

10

10

11

7

11

9

7

8

 

Cost.

M1 is given A = 9

M2 is given B = 9

M3 is given E = 7

M4 is given D = 7

M5 is given C = 0

Total = 32

As the no of lines equals the assigned zero, optimal solution has been obtained.

Example 6.12. Consider a problem of assigning four clerks to four tasks. The time required is give below.

A

B

C

D

Clerks

1

2

3

4

4

-

3

6

7

8

-

6

5

7

5

4

6

4

3

3

 

Clerk 2 cannot be assigned to task A and clerk 3 cannot be assigned to task B. Find all the optimum assigned schedules.

Sol. The procedure is same as of earlier example.

Subtracting the minimum element of each row from all its elements we get 

1 – B

2 – D

3 – A

4 – C

7 + 4 + 3 + 4 = 18.

Example 6.13. A national car rental service has a surplus of one car in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one car in each of the cities 7, 8, 9, 10, 11, 12. The distance in miles between cities with a surplus and cities with a deficit are displayed in the table below. How’ should the. cars be dispatched so as to minimise total mileage travelling?

7

8

9

10

11

12

1

2

3

4

5

6

41

22

27

45

29

82

72

29

39

50

40

40

39

49

60

48

39

40

52

65

51

52

26

60

25

81

32

37

30

51

51

50

32

43

33

70

 

Sol. Row Reduction

7

8

9

10

11

12

1

2

3

4

5

6

16

0

0

8

3

42

47

7

12

13

14

0

14

27

33

11

13

0

27

43

24

15

0

20

0

59

5

0

4

11

26

28

5

6

7

30

 

Column Reduction &making assignments 

The number of lines is less than the number of assignment.

Further Reduction will take place.

The smallest element will be subtracted from all the values from that particular element and added where two lines intersect and elements on line will remain same. 

Still the no. of lines is 5 as against required 6.

Second Reduction will take place; 

Row Reduction

7

8

9

10

11

12

1

2

3

4

5

6

16

0

0

8

3

49

47

7

12

13

14

0

14

27

33

11

13

0

27

43

24

15

0

20

0

59

5

0

4

11

26

28

5

6

7

30

 

Column Reduction & making assignments

Now mark the unmarked row which is Row IVth. See the marked zero in that column. Draw lines on rest of the rows.

1- 11 = 25

2-8= 2

3-7=27

4-12=43

5 – 10 = 26

6-9 = 40

Total = 190

Ex. 6.14. Five lathes are to be allotted to five operators, the following table gives weekly output figures.

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

20

19

23

21

24

22

23

28

24

28

27

29

35

31

31

32

34

39

37

36

36

40

34

42

41

 

Profit per piece is 25%. Find the maximum profit per week.

Sol. As the given problem is a maximisation problem, we convert it into an opportunity loss matrix by subtracting all the elements of the given table from the highest element of table i.e., 42. Opportunity loss matrix is as follows :-

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

22

23

19

21

18

20

19

14

18

14

15

13

7

1

11

10

8

3

5

6

6

2

8

0

1

 

Row Reduction

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

16

21

16

21

17

14

17

11

18

13

9

11

4

11

10

4

6

0

5

5

0

0

5

0

0

 

Column Reduction

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

0

5

0

5

1

3

6

0

7

2

5

7

0

7

6

4

6

0

5

5

0

0

5

0

0

 

Therefore, the minimum number of lines to cover all zeros is 3 which is less than 5, the above matrix will not give optimal solution,

Therefore, subtract the least uncovered element which is 1 from all uncovered elements and add it to all elements lying at the intersection of two lines, we get the following matrix.

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

0

4

0

4

0

3

5

0

6

1

5

6

0

6

5

4

5

0

4

4

1

0

6

0

0

 

Therefore, the minimum lines drawn to cover all zero is 3. Repeating the above procedure, the matrix is

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

0

4

1

4

0

2

4

0

5

0

4

5

0

5

4

3

4

0

3

3

1

0

7

0

0

 

The minimum number of Lines to cover all zero is 4 which is less than 5 the resultant matrix is

L1

L2

L3

L4

L5

Operator

P

Q

R

S

T

0

1

1

1

0

2

1

0

2

0

4

2

0

2

4

3

1

0

0

3

4

0

10

0

3

 

Therefore, the minimum number of lines to cover all zeros is 5.

Hence the above matrix will give optimal solution. 

 

and the assignment of operator setting lathe time is given by

P → L1 = 20

Q → L2 = 40

R → L3 = 35

S → L4 = 37

L → L5 = 28

The maximum profit per week 25 × 160= 4000.

Example 6.15. The Captain of a cricket team has to allot five middle batting positions to five batsmen. The average runs scored by each batsman at these positions are as follows.

Batting Positions

I

II

III

IV

V

Batsman

P

Q

R

S

T

40

42

50

20

58

40

30

48

19

60

35

16

40

20

59

25

25

60

18

55

50

27

50

25

53

 

(i)                           Find the assignment of batsman to positions which would give maximum number of runs.

(ii)                        If another batsman U with the following average runs in batting positions as given below.

Batting positions I II III IV V
Average Runs 45 52 38 50 49

is added to the team, should be included to play in the team? If so who will be replaced by whom?

Sol. (i) Convert the profit matrix into opportunity cost matrix by subtracting all the elements from the highest element 60 of given matrix, we obtain the following opportunity loss matrix.

I

II

III

IV

V

P

Q

R

S

T

20

18

10

40

2

20

30

12

41

0

25

44

20

40

1

35

35

0

42

5

10

33

10

35

7

 

Row Reduction

I

II

III

IV

V

P

Q

R

S

T

10

0

10

5

2

10

12

12

6

0

15

26

20

5

1

25

17

0

7

5

0

15

10

0

7

 

Column Reduction &Making Assignment 

Therefore, the no of assignment is 5, the solution is optimum.

P → V → 50

Q → I → 42

R → IV → 60

S → III → 20

L → II → 60

Total : 232

(a) If we introduce a new batsman U then number of batsmen is not equal to number of batting positions. So a dummy batting position is created and the matrix will become.

I

II

III

IV

V

Dummy

P

Q

R

S

T

U

40

42

50

20

58

45

40

30

48

19

60

52

35

16

40

20

59

38

25

25

60

18

55

50

50

27

50

25

53

49

0

0

0

0

0

0

 

Convert the profit matrix into opportunity cost matrix by subtracting all the elements from the highest element i.e. 60 of the given matrix.

I

II

III

IV

V

Dummy

P

Q

R

S

T

U

20

18

10

40

2

15

20

30

12

41

0

8

25

44

20

40

1

22

35

35

0

42

5

10

10

33

10

35

7

11

60

60

60

60

60

60

 

Row Reduction

I

II

III

IV

V

Dummy

P

Q

R

S

T

U

10

0

10

5

2

7

10

12

12

6

0

0

15

26

20

5

1

14

25

17

0

7

5

2

0

15

10

0

7

3

50

42

60

25

60

52

 

Column Reduction & Making Assignment

I

II

III

IV

V

Dummy

P

Q

R

S

T

U

10

0

10

5

2

7

10

12

12

6

×

0

14

25

19

4

0

13

25

17

0

7

5

2

0

15

10

×

7

3

25

17

35

0

35

27

 

P → V → 50

Q → I → 42

R → IV → 60

S → Dummy  0

T → III → 59

U → II →52

Total : 263

Ex 6.16. A small school has five teachers teaching five different subjects. All the five teachers an capable of teaching all the five subjects. The output per day of the teacher and course coverage (%) for each subjects are given below.

Teachers

1

2

3

4

5

A

B

C

D

E

7

4

8

6

7

9

9

5

5

8

4

5

7

8

10

8

7

9

10

9

6

8

8

10

9

Course Coverage %

2

3

2

3

4

If teacher D is not available will your answer be different?

Sol. We can multiply the output of teachers for different subjects with coverage of course (%), the resultant matrix is shown as:-

Teachers

1

2

3

4

5

A

B

C

D

E

14

8

16

12

14

27

27

15

15

24

8

10

14

16

20

24

21

27

30

27

24

32

32

40

36

 

Therefore, the problem is of maximisation.

Therefore, will deduct the maximum element i.e., 40. The resultant loss matrix will be

Subject

Teachers

1

2

3

4

5

A

B

C

D

E

26

32

24

28

26

13

13

25

25

16

32

30

26

24

20

16

19

13

10

13

16

8

8

0

4

 

Row Reduction

1

2

3

4

5

A

B

C

D

E

13

24

16

28

22

0

5

17

25

12

19

22

18

24

16

3

11

5

10

9

3

0

0

0

0

 

Column Reduction

Now subtracting the main elements of each column from all its elements.

Teachers

1

2

3

4

5

A

B

C

D

E

0

11

3

15

9

0

5

17

25

12

3

6

2

8

0

0

8

2

7

6

3

0

0

0

0

 

Therefore, there are 3 lines, this is not the optimal solution.

So, we will follow the deduction method.

Teachers

1

2

3

4

5

A

B

C

D

E

0

9

1

13

9

0

3

15

23

12

3

4

0

6

0

0

6

0

5

6

5

0

0

0

2

 

Still the number of lines is less

Therefore, again the same procedure will be followed.

Teachers

1

2

3

4

5

A

B

C

D

E

0

6

1

10

9

0

0

15

20

12

3

1

0

3

0

0

3

0

2

6

8

0

3

0

5

 

Optimum solution is obtained. 

 

A → 1=14

B → 2 =27

C → 4 =27

D → 5 =40

E → 3 =20

Total : 128

REVIEW

  1. 1.   (a) Show that assignment model is a special case of transportation model.

(b) Consider the problem of assigning five operators to five machines.
given below.

Operators

Machines

I

II

III

IV

V

A

B

C

D

E

10

3

10

5

7

5

9

7

11

9

13

18

2

7

4

15

3

2

7

4

16

6

2

12

12

 

Assign the operators to different machines so that total cost is minimised.

  1. 2.   (a) If in an assignment problem we add a constant to every element of a row (or column) in the effectiveness matrix, prove that an assignment that minimises the total effectiveness in one matrix also minimises the total effectiveness in the other matrix.

(b) A national car-rental service has a surplus of one car in each of the cities I, 2, 3, 4, 5, 6 and a deficit of one car in each of the cities 7, 8, 9, 10, 11, 12. The distance in miles between cities with a surplus and cities with a deficit are displayed in matrix. How should the cars be despatched so as to minimise the total mileage travelled.

To

7

8

9

10

11

12

1

41

72

39

52

25

51

2

22

29

49

65

81

50

3

27

39

60

51

32

32

4

45

50

48

52

37

43

5

29

40

39

26

30

33

6

82

40

40

60

51

30

  1. 3.   (a) Distinguish between transportation model and assignment model.

(b) Four different jobs are to be done on four different machines. The set up and production times are prohibitively high for change over. Tables indicates the cost of producing job i on machine j in rupees.

Machines

1

2

3

4

Jobs

1

5

7

11

6

2

8

5

9

6

3

4

7

10

7

4

10

4

8

3

 

Assign jobs to different machines so that the total cost is minimised.

  1. 4.   Six machines M1, M2, M3, M4, M5 and M6 are to be located in six places P1, P2, P3, P4, P5 and P6. Cij the cost of locating machine Mi at place Pj is given the matrix below.

P1

P2

P3

P4

P5

P6

M1

20

23

18

10

16

20

M2

50

20

17

16

15

11

M3

60

30

40

55

8

7

M4

6

7

10

20

25

9

M5

18

19

28

17

60

70

M6

9

10

20

30

40

55

 

Formulate an LP model to determine an optimal assignment. Write the objective function and the constraints in detail. Define any symbol used. Find an optimal layout by assignment techniques of linear programming.

  1. 5.   (a) Discuss assignment model, Indicate a method of solving an assignment problem.

(b) A Company is faced with the problem of assigning six different machines to five different jobs. The costs estimated in hundreds of rupees are given in the table below.

1

2

3

4

5

1

2.5

5

1

6

2

2

2

5

1.5

7

3

3

3

6.5

2

8

3

4

3.5

7

2

9

4.5

5

4

7

3

9

6

6

6

9

5

10

6

 

Solve the problem assuming that the objective is to minimise the total cost.

  1. 6.   Five new machines are to be located in machine shop. There are five possible locations in which machines can be located. Cij the cost of placing machine i in place j is given in the table below.

Jobs

1

2

3

4

5

1

1

15

10

25

25

10

2

1

8

10

20

2

Machine

3

8

9

17

20

10

4

14

10

25

27

15

5

10

8

25

27

12

 

It is required-to place the machines at suitable places so as to minimise the total cost.

(i)                           Formulate an LP model to find an optimal assignment.

(ii)                        Solve the problem by assignment technique of L.P.

  1. 7.   Solve the following assignment problem

 

I

II

III

IV

V

1

11

17

8

16

20

2

9

7

12

6

15

3

13

16

15

12

16

4

21

24

17

28

26

5

14

10

12

11

15

 

  1. 8.   A team of 5 horses and 5 riders has entered a jumping show contest. The number of penalty points to be expected when each rider rides anv horse is shown below.

R1

R2

R3

R4

R5

Horse

H1

5

3

4

7

2

H2

2

3

7

6

5

H3

4

1

5

2

4

H4

6

8

1

2

3

H5

4

2

5

7

1

 

How should the horses be allotted to the riders so as to minimise the expected loss of the team?

  1. 9.   Find the minimum cost solution for the 5 × 5 assignment problem whose cost coefficients are A given below.

1

2

3

4

5

1

-2

-4

-8

-6

-1

2

0

-9

-5

-5

-4

3

-3

-8

-9

-2

-6

4

-4

-3

-1

0

-3

5

-9

-5

-8

-9

-5

 

  1. 10.                A company has four machines on which to do three jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following table.

Machines

W

X

Y

Z

Job

A

18

24

28

32

B

8

13

17

19

C

10

15

19

22

 

What are the job assignments which will minimise the cost?

  1. 11.                Assign four trucks 1, 2, 3 and 4 to vacant spaces 7, 8, 9, 10, 11 and 12 so that the distance travelled is minimised. The matrix below shows the distance.

1

2

3

4

7

4

7

3

7

8

8

2

5

5

9

4

9

6

9

10

7

5

4

8

11

6

3

5

4

12

6

8

7

3

 

  1. 12.                A Company has five jobs to be done. The following matrix shows the return in rupees of assigning ith machine (i = 1, 2, …. 5) to the job (j = 1, 2, …. 5). Assign the five jobs to the five machines so as to maximise the total expected profit.

Job

1

2

3

4

5

Machine

1

2

3

4

5

5

2

3

6

7

11

4

12

14

9

10

6

5

4

8

12

3

14

11

12

4

5

6

7

5

 

  1. 13.                The owner of a small machine shop has four machinists available to assign to jobs for the day. Five jobs are offered with the expected profit in rupees for each machinist on each job being as follows. Find the assignment of machinists to jobs that will return in a maximum profit. Which job should be declined?

Job

1

2

3

4

5

Machine

1

2

3

4

6.20

7.10

8.70

4.80

7.80

8.40

9.20

6.40

5.00

6.10

11.10

8.70

10.00

7.30

7.10

7.70

8.20

5.90

8.10

8.00

 

  1. 14.                An airline that operates seven days a week has time-table as shown below. Crew must have a minimum layover of 5 hours between flights. Obtain the pairing of flights that minimises layover time away from home. For any given pairing, the crew will be based at the city that results in smaller layover.

Delhi-Jaipur

Jaipur-Delhi

Flight No.

Depart

Arrive

Flight No

Depart

Arrive

1

7.00 AM

8.00 AM

101

8.00AM

9.15 AM

2

8.00 AM

9.00 AM

102

8.30 AM

9.45 AM

3

1.30 AM

2.30 AM

103

12.00 Noon

1.15 PM

4

6.30 PM

7.30 PM

104

8.00 PM

6.45 PM

 

For each pair also mention the town where the crew should be based.

  1. 15.                A company has four territories open and four salesman available for assignment. The territories are not equally rich in their sales potential; it is estimated that a typical salesman operating in each territory would bring in the following annual sales:

 

Territory

Annual Sales (Rs.)

I

60,000

II

50,000

III

40,000

IV

30,000

 

The four salesmen are also considered to differ in ability, it is estimated that working under the same conditions their yearly sales will be proportionately as follows.

Salesmen

Proportion

A

7

B

5

C

5

D

4

 

  1. 16.                If the criterion is maximum expected total sales, the intuitive answer is to assign the best salesman to the richest territory, the next best salesman to the second richest and so on. Verify this answer by the assignment technique.
  2. 17.                (a) State mathematical model of assignment problem.

(b) The personnel manager of a medium size company decided to recruit two employees D and E in a particular section of the organisation. The section has five fairly defined tasks 1, 2, 3, 4 and 5 and three employees A, B and C are already employed in the section. Looking at the rather specialised nature of task 3 and the special qualifications of the recruit D for task 3, the manager decided to assign task 3 to employee D and then assign the remaining tasks to remaining employees so as to maximise the total effectiveness. The index of effectiveness of each employee for different task is as under.

Tasks

Employee

1

2

3

4

5

A

25

55

60

45

30

B

45

65

55

35

40

C

10

35

45

55

65

D

40

30

70

40

60

E

55

45

40

55

10

Assign the tasks for maximising total effectiveness. Critically examine whether the decision of the manager to assign task 3 to employee D was correct.

  1. 18.            Enumerate various steps involved in Hungarian method of solving assignment problem.
  2. 19.                Discuss briefly the Hungarian method of solving an assignment problem.
  3. 20.                Write a method of solving an assignment problem. Illustrate with an example.
  4. 21.                A Departmental head has 4 subordinates and 4 tasks to be performed, the subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimate of the times each man would take to perform each task is given below in the matrix:

Tasks/ Subordinates

I

II

III

IV

A

B

C

D

8

13

38

19

26

28

19

26

17

4

18

24

11

26

15

10

 

How should the tasks to be located to subordinates so as to minimize the total
man-hours?

  1. 22.                . A car hire company has one car at each of 5 depots a, b, c, d and e. A customer each of five cities A, B, C, D and E require a car. The distance (in kms.) he depots and the cities are as follows:

Tasks/ Subordinates

a

b

c

d

D

A

B

C

D

E

160

135

140

50

55

130

120

110

50

35

175

130

155

80

70

190

160

170

80

80

200

175

185

110

105

 

  1. 23.                How should the cars be assigned to the customers so as to minimize the distance travelled?
  2. 24.                Find the assignment of men to jobs that will minimize the total time:

Jobs

J1

J2

J3

J4

MEN

M1

M2

M3

M4

8

13

38

19

26

28

19

26

17

4

18

24

11

26

15

10

 

  1. 25.                Three customers in a certain sales territory have requested technical assistance from available 3 technicians. Distance between the technicians and customers is reported below. Using assignment problems techniques assign the technicians to the customers for minimum cost of travel per km is Rs. 2

Customers

I

II

III

Technicians

A

B

C

37

38

88

58

92

55

41

74

43

 

  1. 26.                Given the following cost matrix (in ’000 Rs.) contract

Bidder

Diff

Weapon

Subsystems

I

II

III

IV

A

B

C

D

17

15

17

14

20

21

18

22

13

14

17

12

21

18

21

22

 

Assign the 4 diff weapon subsystems, one each to bidder so as to minimize cost.

  1. 27.                Using following cost matrix, assign the different contractors to different jobs so as to minimize the total cost:

A

B

C

D

JOBS

X

Y

Z

L

17

15

17

14

20

21

18

22

13

14

17

12

21

18

21

22

 

  1. 28.                Using following cost matrix of cost of three jobs on three machines, assign one job to each machine so that the total cost is minimum.

Machine

X

Y

Z

Job

A

25

31

35

B

15

20

24

C

22

19

17

 

  1. 29.                Solve the following Assignment Problem of maximization:

5

6

8

9

2

3

4

5

6

5

3

4

9

8

8

9

6

5

4

2

3

1

2

2

3

  1. 30.                Determine the optimum solution to each of the following problem:

Jobs

Operator

1

2

3

4

5

1

2

3

4

5

6

6

2

7

6

9

4

2

5

8

2

3

7

5

8

6

3

8

4

2

7

9

4

9

6

6

7

8

5

7

8

 

  1. 31.                Assign the operators to machines to minimize costs for the following:

Machines

Operator

I

II

III

IV

V

A

B

C

D

E

5

7

9

7

6

5

4

3

2

5

-

2

5

6

7

2

3

-

7

9

6

4

3

2

1

 

  1. 32.                Find the optimal solution for the assignment problem:

 

I

II

III

IV

V

A

B

C

D

E

11

9

13

21

14

17

7

16

24

10

8

12

15

17

12

16

6

12

28

11

20

15

16

26

15

 

  1. 33.                For a given profit matrix, find the optimal assignments:

Machines

Job

1

2

3

4

5

A

B

C

D

E

11

9

13

21

14

17

7

16

24

10

8

12

15

17

12

16

6

12

28

11

20

15

16

26

15

 

  1. 34.                Assigns five operators to five machines to minimise total cost:

Machines

Operator

I

II

III

IV

V

A

B

C

D

E

5

7

9

7

6

5

4

3

2

5

-

2

5

6

7

2

3

-

7

9

6

4

3

-

1

 

  1. 35.                Solve the assignment problem:

From/To

A

B

C

D

E

A

B

C

D

E

-

7

6

8

4

7

-

8

5

6

6

8

-

9

7

8

5

9

-

8

4

6

7

8

-

 

  1. 36.                What is Unbalance Assignment Problem? How it is solved by HAM? (Take any imaginary problem). HAM-Hungarian Assignment Method.
  2. 37.                Suggest optimum assignment to sales territories, where the estimates of sales to be made by each salesman in different territories are given below:

Territories

Salesman

I

II

III

IV

V

A

B

C

D

10

6

12

8

15

18

5

11

17

10

13

16

14

12

13

10

14

16

6

12

 

If salesman B cannot be assigned to territory II for certain reasons, will the optimum assignment change? If so, what will be the new assignment schedule and the total sales?

  1. 38.                Unbalanced assignment problem’
  2. 39.                Distinguish between Assignment and Transportation problem.
  3. 40.                Enumerate various steps involved in Hungarian method of solving assignment problem.
  4. 41.                Write a method of solving a assignment problem Illustrate with an example.
  5. 42.                Find the assignment of men to jobs that will minimize the total time:

 

Jobs

Men

J1

J2

J3

J4

M1

M2

M3

M4

8

13

38

19

26

18

19

26

17

4

18

24

11

26

15

10

 

  1. 43.                Three customers in a certain sales territory has requested technical assistance from available 3 technicians. Distance between the technicians and customers is reported below. Using assignment problems techniques assign the technicians to the ‘customers for minimum cost of travel per km. is Rs. 2.

Technicians

Customers

I

II

III

A

B

C

37

38

38

58

92

55

41

74

43

 

  1. 44.                Given the following cost matrix (in ’000 Rs.) contract:

Bidder

Diff. Weapons subsystems

I

II

III

IV

A

B

C

D

17

15

17

14

20

21

18

22

13

14

17

12

21

18

21

22

 

Assign the 4 Different weapon subsystems, one each to each bidder so minimize cost.

  1. 45.             Using following cost matrix, assign the different contractors to different jobs to minimize the total cost:

Jobs

Contractors

A

B

C

D

X

Y

Z

L

17

15

17

14

20

21

18

22

13

14

17

22

21

18

21

22

 

  1. 46.                Using following cost matrix of cost of three jobs on three machines, assign one job to each machine so that total cost is minimum.

Job

Machine

X

Y

Z

A

B

C

25

15

22

31

20

19

35

24

17

 

  1. 47.                A process can be carried out on any of the 4 machines by one of the operators. The average time taken by any operator on any specific machine is tabulated below. A proposal to replace one of the existing machines by a new machine is under consideration. The estimated timing to carry out the process on the new machine are also included in the table. Is it worthwhile to use new machinery?

Operator

I

Machines

II

III

IV

New

A

B

C

D

12

11

10

14

14

12

9

15

8

12

9

8

8

12

9

8

12

9

8

7

11

10

7

6

 

  1. 48.                Consider the problem of assigning the five jobs to five persons. The assignment costs are given as follow:

Jobs

 

1

2

3

4

5

Persons

A

B

C

D

E

8

0

3

4

9

4

9

8

3

5

2

5

9

1

8

6

5

2

0

9

1

4

6

3

5

 

  1. 49.                Assign the jobs to machines for maximizing profits given in table.

Machines

 

A

B

C

D

E

Jobs

I

II

III

IV

V

32

40

41

22

39

38

24

27

38

33

40

28

33

41

40

28

21

30

36

35

40

36

37

36

39

 

  1. 50.                Assign machine to give jobs, you are given costs (in Rs.)

Jobs

 

1

2

3

4

5

Machine

1

2

3

4

5

6

2.5

2

3

3.5

4

6

5

5

6.5

7

7

9

1

1.5

2

2

3

5

6

7

8

9

9

10

1

3

3

4.5

6

6

 

  1. 51.                A firm wants to purchase three different types of equipment and manufactures have come forward to supply one or all the three machines. However, the firm’s policy is to purchase one machine from one manufacturer only. The data relating to price (in lacs of Rs.) quoted by the different manufactures is given on next page.

 

Machines

 

1

4

5

Manufacture

A

B

C

D

E

2.99

2.78

2.92

2.82

3.11

3.11

2.87

3.05

3.10

2.90

2.68

2.57

2.80

2.74

2.62

 

Determine how best the firm can purchase three machines, assuming- machines of different manufactures have the same capacity.

  1. 52.                A departmental head has 4 subordinates and 4 tasks to be performed, the
    subordinates differ in efficiency and the task differ in their intrinsic difficulty. His estimate of the times each man would take to perform each task is given below is the matrix :

I

II

III

IV

A

B

C

D

8

13

38

19

26

28

19

26

17

4

18

24

11

26

15

10

 

How should the tasks to be allocated to subordinates so as to minimize the total man-hours?

  1. 53.                A car hire company has one car at each of 5 depots a, b, c, d and .e. A customer in each of five cities, A, B, C, D and E require a car. The distance (in kms.) between depots and the cities are as follows:

a

b

c

d

e

A

B

C

D

E

160

135

140

50

55

130

120

110

50

35

175

130

155

80

70

190

160

170

80

80

200

175

185

110

105

How should the cars be assigned to the customers so as to minimize the distance travelled?

  1. 54.                Solve the foil lowing assignment problem:

J1

J2

J3

J4

J5

P1

P2

P3

P4

27

31

20

20

18

24

17

28

X

21

20

20

20

12

X

16

21

21

16

27

 

  1. 55.                Solve the following assignment (minimisation) problem:

Machines

Jobs

A

B

C

D

1

2

3

4

5

12

12

8

8

10

7

5

4

6

11

9

10

9

7

9

10

11

7

5

7

 

  1. 56.                Solve the following Assignment problem:

Sales in Rs. 000’S

Salesman → Territory ↓

S1

S2

S3

S4

A

B

C

D

50

70

90

60

48

72

80

48

47

70

85

52

45

60

82

55

 

  1. 57.                Solve the following assignment problem. The district wise sales of ’5 salesmen is given as under

Districts

Sales in Rs. 000’s

Salesman

1

2

3

4

5

A

B

C

D

E

38

49

50

28

39

44

33

36

44

40

47

37

40

48

48

35

30

39

45

45

50

42

46

43

46

 

  1. 58.                A company has a team of four salesmen and there are four districts where the
    company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts the company estimates that the profit per day in rupees for each salesman in each district is as below:

Districts

Salesman

1

2

3

4

A

B

C

D

16

14

15

13

10

11

15

12

14

15

13

14

11

15

12

15

 

  1. 59.                Following table gives the weekly output of five operators working on 5 lathes. Do the assignment of operators on the lathes so as to maximize total production:

Lathe Weekly output

Operators

L1

L2

L3

L4

L5

P

Q

R

S

T

20

19

23

21

24

22

23

28

24

28

27

29

35

31

31

32

34

39

37

36

36

40

34

42

41

 

  1. 60.                (i) Assignment Problem is a special case of Transportation Problem Discuss.

(ii) Using following cost matrix assign jobs to different machines so as to minimise total cost:

Machines

1

2

3

4

A

B

C

D

10

5

12

8

12

10

14

15

19

7

13

11

11

8

11

9

 

  1. 61.                A company is faced with the problem of assigning 4 machines to 6 different jobs (One machine to one job only). The profits are estimated as follows:

Machine

Jobs

A

B

C

D

1

2

3

4

5

6

3

7

3

6

5

5

6

1

8

4

2

7

2

4

5

3

4

6

6

4

8

7

3

4

 

Solve the problem to maximise the profit.