Page 175 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes Travelling Salesman Problem: The problem in combinatorial optimization in which, given a
number of cities and the costs of travelling from one to the other, it is required to determine the
cheapest route that visits each city once and then returns to the initial city.

8.8 Review Questions

1. Discuss the variations in assignment problem.
2. Can there be multiple optimal solutions to an assignment problem? How would you
identify the existence of multiple solutions if any?
3. How would you deal with the assignment problems, where the objective function is to be
maximized?

4. What is an unbalanced assignment problem? Explain with the help of an example.
5. How is the Hungarian method applied for obtaining a solution if the matrix is rectangular?

Problems

6. A manufacturer of garments plans to add 4 regional warehouses to meet increased demand.
The following bids in lakhs of rupees have been for construction of the warehouses.

Warehouse
Contractor
A B C D
1 30 27 31 39
2 28 18 28 37
3 33 17 29 41
4 27 18 30 43
5 40 20 27 36

Explain why each warehouse contract cannot simply be given to the contractor who bids
cheapest. How will you then determine the optimal contract?
7. 5 operators have to be assigned to 5 machines. The assignment costs are given in the table.

Machine
Operator I II III IV V
A 5 5 - 2 6
B 7 4 2 3 4
C 9 3 5 - 3
D 7 2 6 7 2
E 6 3 7 9 1

Operator A cannot operate machine II and operator C cannot operate machine IV. Find the
optimal assignment schedule.

170 LOVELY PROFESSIONAL UNIVERSITY