Assignment problem A plant manager has four employees, A-D, and four tasks, I-IV, to be performed. The employees differ in efficiency and the tasks differ in their intrinsic difficulty. The effectiveness matrix below gives this estimate of the times each man would take to perform each task. I II III IV A 8 26 17 11 B 13 28 4 26 38 19 18 15 24 D 19 26 10 How should the tasks be allocated, one to a man, so as to minimize the total man hours? 1. Write the LP model of the above problem 2. Use the Hanagrian method to solve this problem 3. Solve using Excel Transportation Two bread factories, 01 and 02, make the daily bread in a city. The bread is delivered to the three bakeries of the city: D1, D2 and D3. The supplies of bread factories, the demands of bakeries and the per unit transportation costs are displayed in the following graph: D 1500 8 2000 0 6 10 D2 2000 10 4 2500 02 9 D3 1000 1. Write the LP model of the above problem 2. Solve using Excel Minimum cost flow problem The following graph shows the supply and demand at each node in the network using brackets. For example, the supply at node A is 20, while the demand at node E is 30. Node C is just a transhipment node. The number along the arrows shows the shipping costs while the capacities of the arcs are written between nodes C and D. [20] [O] 6 A 3 [-30] 5 Arc capacities: AC: 10 B - C:25 Others: 0 2 E 3 4 B D 5 [10] [0] 1. Formulate this problem as a minimum cost flow problem a. Note: you can ignore the capacity constraint for arcs having infinite capacities. 2. Solve using Excel Shortest path The following network shows distances between nodes A-E 6 A 3 5 2 E B D 5 1. Use Dijekstra algorithm to find the shortest path from node A to all other nodes in the network 2. Formulate an LP model to find the minimum distance between node A and E a. Solve your LP model using EXCEL b. Check your answer in 1 Maximal flow Assume that the number over the arrows represent shipping capacities along these routes. 6 A 3 5 5 2 2 E 4 B D 5 1. Find the maximum amount of products that can be shipped from node A to node E 2. Solve using Excel