Lista de Exercícios Resolvidos - Modelo de Designação em Pesquisa Operacional

TP052 Pesquisa Operacional I 5ª Lista de Exercícios Designação Elaborado por Anderson Kenji Hirose 1 ASSIGNMENT MODEL 1 A machine tool company decides to make four subassemblies through four contractors Each contractor is to receive only one subassembly The cost of each subassembly is determined by the bids submitted by each contractor and is shown in the following table hundreds of rupees Contractors 1 2 3 4 Subassemblies 1 15 13 14 17 2 11 12 15 13 3 13 12 10 11 4 15 17 14 16 a Formulate the mathematical model for the problem b Show that the assignment model is a special case of the transportation model c Assign the different subassemblies to contractors so as to minimize the total cost PUBE Elect Oct 1993 NIIFT Mohali 2000 Answers a TP052 Pesquisa Operacional I 5ª Lista de Exercícios Designação Elaborado por Anderson Kenji Hirose 2 b Comparing this model with the transportation mode we find that and Thus the assignment model can be represented as in the following table Contractors Supply 1 2 3 4 Subassemblies 1 15 13 14 17 1 2 11 12 15 13 1 3 13 12 10 11 1 4 15 17 14 16 1 Demand 1 1 1 1 Therefore the assignment model is a special case of the transportation model in which All righthand side constants in the constraints are unity ie All coefficients of in the constraints are unity c 1 2 3 4 1 2 0 1 3 2 0 1 4 1 3 3 2 0 0 4 1 3 0 1 Minimum total cost Rs 4900 TP052 Pesquisa Operacional I 5ª Lista de Exercícios Designação Elaborado por Anderson Kenji Hirose 3 2 Four different jobs can be done on four different machines The set up and take down time costs are assumed to be prohibitively high for changeovers The matrix below gives the cost in rupees of producing a job i on machine j Machines Jobs 5 7 11 6 8 5 9 6 4 7 10 7 10 4 8 3 How should the jobs be assigned to the various machines so that the total cost is minimized PUB Com April 2007 BE CScE Dec 2004 PTU MBA May 2002 Answer 0 0 0 0 5 0 0 2 0 1 0 2 8 0 0 0 Optimum cost Rs 23 TP052 Pesquisa Operacional I 5ª Lista de Exercícios Designação Elaborado por Anderson Kenji Hirose 4 3 A company has one surplus truck in each of the cities A B C D and E and one deficit truck in each of the cities 1 2 3 4 5 and 6 The distance between the cities in kilometers is shown in the matrix below Find the assignment of trucks from cities in surplus to cities in deficit so that the total distance covered by vehicles is minimum 1 2 3 4 5 6 A 12 10 15 22 18 8 B 10 18 25 15 16 12 C 11 10 3 8 5 9 D 6 14 10 13 13 12 E 8 12 11 7 13 10 NIIFT Mohali 1999 KUBE Mech 1993 PUB Com Sept 2004 Answer 1 2 3 4 5 6 A 6 0 5 12 8 0 B 0 4 11 1 2 0 C 12 7 0 5 2 8 D 0 4 0 3 3 4 E 5 5 4 0 6 5 Dummy 4 0 0 0 0 2 Minimum distance traveled 38 km TP052 Pesquisa Operacional I 5ª Lista de Exercícios Designação Elaborado por Anderson Kenji Hirose 5 4 As fastfood chain wants to build four stores In the past the chain has used six different constructions companies and having been satisfied with each has invited them to bid for each job The final bids in thousands of rupees are shown in the following table Construction Companies 1 2 3 4 5 6 Stores 1 853 90 875 824 891 913 2 789 845 994 804 893 884 3 82 313 285 665 804 1097 4 843 346 862 833 85 855 Since the fastfood chain wants to have each of the new stores ready as quickly as possible it will allot at most one job to a construction company What assignment will result in the minimum total cost Answer 1 2 3 4 5 6 1 29 76 51 0 67 89 2 0 56 205 15 104 95 3 535 28 0 380 519 812 4 497 0 516 487 504 509 0 0 0 0 0 0 0 0 0 0 0 0 Minimum total cost Rs 224400