Assignment model problems

solved example: assignment model of operations research

1. Assignment Model Problems

2. A fast food chain wants to build four stores. In the past, the chain has used six different construction companies and, having been satisfied with each, has invited each to bid on each job. The final bids (in thousands of rupees) are show in the following table. Since the fast food chain wants to have each of the new stores ready as quickly as possible, it will award at most one job to a construction company. What assignment results in minimum total cost to the fast food chain? Construction Companies 1 2 3 4 5 6 Store 1 85.3 88 87.5 82.4 89.1 86.7 Store 2 78.9 77.4 77.4 76.5 79.3 78.3 Store 3 82 81.3 82.4 80.6 83.5 81.7 Store 4 84.3 84.6 86.2 83.3 84.4 85.5

3. Balancing the assignment problem

4. Construction Companies 1 2 3 4 5 6 Store 1 85.3 88 87.5 82.4 89.1 86.7 Store 2 78.9 77.4 77.4 76.5 79.3 78.3 Store 3 82 81.3 82.4 80.6 83.5 81.7 Store 4 84.3 84.6 86.2 83.3 84.4 85.5 Dummy 1 Dummy 2

5. 1 2 3 4 5 6 S1 85.3 88 87.5 82.4 89.1 86.7 S2 78.9 77.4 77.4 76.5 79.3 78.3 S3 82 81.3 82.4 80.6 83.5 81.7 S4 84.3 84.6 86.2 83.3 84.4 85.5 D1 D2

6. Applying the Hungarian method

7. 1 st Reduced Cost Matrix Subtracting the minimum element of each row from each element of that row

8. 1 2 3 4 5 6 S1 85.3–82.4 88–82.4 87.5–82.4 82.4–82.4 89.1–82.4 86.7–82.4 S2 78.9–76.5 77.4–76.5 77.4–76.5 76.5–76.5 79.3–76.5 78.3–76.5 S3 82–80.6 81.3–80.6 82.4–80.6 80.6–80.6 83.5–80.6 81.7–80.6 S4 84.3–83.3 84.6–83.3 86.2–83.3 83.3–83.3 84.4–83.3 85.5–83.3 D1 0–0 0–0 0–0 0–0 0–0 0–0 D2 0–0 0–0 0–0 0–0 0–0 0–0

9. 1 2 3 4 5 6 S1 2.9 5.6 5.1 6.7 4.3 S2 2.4 0.9 0.9 2.8 1.8 S3 1.4 0.7 1.8 2.9 1.1 S4 1 1.3 2.9 1.1 2.2 D1 D2

10. 2 nd Reduced Cost Matrix Subtracting the minimum element of each column from each element of that column

11. 1 2 3 4 5 6 S1 2.9–0 5.6–0 5.1–0 0–0 6.7–0 4.3–0 S2 2.4–0 0.9–0 0.9–0 0–0 2.8–0 1.8–0 S3 1.4–0 0.7–0 1.8–0 0–0 2.9–0 1.1–0 S4 1–0 1.3–0 2.9–0 0–0 1.1–0 2.2–0 D1 0–0 0–0 0–0 0–0 0–0 0–0 D2 0–0 0–0 0–0 0–0 0–0 0–0

12. 1 2 3 4 5 6 S1 2.9 5.6 5.1 6.7 4.3 S2 2.4 0.9 0.9 2.8 1.8 S3 1.4 0.7 1.8 2.9 1.1 S4 1 1.3 2.9 1.1 2.2 D1 D2

13. Striking off all 0’s using minimum number of vertical/horizontal lines

14. 1 2 3 4 5 6 S1 2.9 5.6 5.1 6.7 4.3 S2 2.4 0.9 0.9 2.8 1.8 S3 1.4 0.7 1.8 2.9 1.1 S4 1 1.3 2.9 1.1 2.2 D1 D2

15. Subtracting the minimum uncut element from other uncut elements, and adding it to elements at the intersections Since minimum number of lines required is less than the number of rows/columns

16. 1 2 3 4 5 6 S1 2.9 –0.7 5.6 –0.7 5.1 –0.7 6.7 –0.7 4.3 –0.7 S2 2.4 –0.7 0.9 –0.7 0.9 –0.7 2.8 –0.7 1.8 –0.7 S3 1.4 –0.7 0.7 –0.7 1.8 –0.7 2.9 –0.7 1.1 –0.7 S4 1 –0.7 1.3 –0.7 2.9 –0.7 1.1 –0.7 2.2 –0.7 D1 0+0.7 D2 0+0.7

17. 1 2 3 4 5 6 S1 2.2 4.9 4.4 6 3.6 S2 1 .7 0.2 0.2 2.1 1.1 S3 0.7 1.1 2.2 0.4 S4 0.3 0.6 2.2 0.4 1.5 D1 0.7 D2 0.7

18. Striking off all 0’s using minimum number of vertical/horizontal lines

19. 1 2 3 4 5 6 S1 2.2 4.9 4.4 6 3.6 S2 1 .7 0.2 0.2 2.1 1.1 S3 0.7 1.1 2.2 0.4 S4 0.3 0.6 2.2 0.4 1.5 D1 0.7 D2 0.7

20. Subtracting the minimum uncut element from other uncut elements, and adding it to elements at the intersections Since minimum number of lines required is less than the number of rows/columns

21. 1 2 3 4 5 6 S1 2.2–0.2 4.9–0.2 4.4–0.2 6–0.2 3.6–0.2 S2 1 .7 –0.2 0.2–0.2 0.2–0.2 2.1–0.2 1.1–0.2 S3 0.7 1.1 0+0.2 2.2 0.4 S4 0.3 –0.2 0.6 –0.2 2.2–0.2 0.4 –0.2 1.5–0.2 D1 0.7+0.2 D2 0.7+0.2

22. 1 2 3 4 5 6 S1 2 4.7 4.2 5.8 3.4 S2 1 .5 1.9 0.9 S3 0.7 1.1 0.2 2.2 0.4 S4 0.1 0.4 2 0.2 1.3 D1 0.9 D2 0.9

23. Striking off all 0’s using minimum number of vertical/horizontal lines

24. 1 2 3 4 5 6 S1 2 4.7 4.2 5.8 3.4 S2 1 .5 1.9 0.9 S3 0.7 1.1 0.2 2.2 0.4 S4 0.1 0.4 2 0.2 1.3 D1 0.9 D2 0.9

25. Subtracting the minimum uncut element from other uncut elements, and adding it to elements at the intersections Since minimum number of lines required is less than the number of rows/columns

26. 1 2 3 4 5 6 S1 2 4.7 4.2 5.8 3.4 S2 1 .5 1.9 0.9 S3 0.7 1.1 0.2 2.2 0.4 S4 0.1 0.4 2 0.2 1.3 D1 0.9 D2 0.9

27. 1 2 3 4 5 6 S1 2–0.1 4.7–0.1 4.2–0.1 5.8–0.1 3.4–0.1 S2 1 .5 0+0.1 1.9 0.9 S3 0.7 1.1 0.2 +0.1 2.2 0.4 S4 0.1 –0.1 0.4 –0.1 2–0.1 0.2–0.1 1.3–0.1 D1 0.9 +0.1 D2 0.9 +0.1

28. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1

29. Striking off all 0’s using minimum number of vertical/horizontal lines

30. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1

31. Making assignments Since minimum number of lines required is equal to the number of rows/columns

32. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1

33. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 ×

34. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 ×

35. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × ×

36. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × ×

37. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × ×

38. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × ×

39. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × ×

40. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × ×

41. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × × × ×

42. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × × × ×

43. Computing total cost

44. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × × × × 1 2 3 4 5 6 S1 85.3 88 87.5 82.4 89.1 86.7 S2 78.9 77.4 77.4 76.5 79.3 78.3 S3 82 81.3 82.4 80.6 83.5 81.7 S4 84.3 84.6 86.2 83.3 84.4 85.5 D1 D2

45. 1 2 3 4 5 6 S1 1.9 4.6 4.1 5.7 3.3 S2 1 .5 0.1 1.9 0.9 S3 0.7 1.1 0.3 2.2 0.4 S4 0.3 1.9 0.1 1.1 D1 1 D2 1 × × × × × × × × × × 1 2 3 4 5 6 S1 85.3 88 87.5 82.4 89.1 86.7 S2 78.9 77.4 77.4 76.5 79.3 78.3 S3 82 81.3 82.4 80.6 83.5 81.7 S4 84.3 84.6 86.2 83.3 84.4 85.5 D1 D2

46. 1 2 3 4 5 6 S1 85.3 88 87.5 82.4 89.1 86.7 S2 78.9 77.4 77.4 76.5 79.3 78.3 S3 82 81.3 82.4 80.6 83.5 81.7 S4 84.3 84.6 86.2 83.3 84.4 85.5 D1 D2 Optimum Assignment and Total Cost Construction Company Store Cost 1 4 Rs.84300 2 3 Rs.81300 3 2 Rs.77400 4 1 Rs.82400 5 - - 6 - - Total Cost Rs.325400

47. Ans : Optimum Assignment & Total Cost Construction Company Store Cost 1 4 Rs.84300 2 3 Rs.81300 3 2 Rs.77400 4 1 Rs.82400 5 - - 6 - - Total Cost Rs.325400

48. A firm wants to purchase three different types of equipment and five manufacturers have come forward to supply these machines. However, the firm’s policy is not to accept more than one machine from any of the manufacturers. The data relating to the price (in lakhs of rupees) quoted by the different manufacturers are given below. Determine how best the firm can purchase the three machines. Machines 1 2 3 Manufacturers A 2.99 3.11 2.68 B 2.78 2.87 2.57 C 2.92 3.05 2.80 D 2.82 3.10 2.74 E 3.11 2.90 2.64

49. A management consulting firm has a backlog of 4 contracts. Work on these contracts must be started immediately. 3 project leaders are available for assignment to the contracts. Because of varying work experience of the project leaders the profit of the consulting firm would vary based on the assignments as shown below. The unassigned contract can be completed by subcontracting it to an outside consultant. The profit from the subcontract is zero. Determine the assignment of project leaders to the contracts so as to maximise profits. Contracts 1 2 3 4 Project Leaders A 13 10 9 11 B 15 17 13 20 C 6 8 11 7