q 4

ASSIGNMENT PROBLEM (40 points) Q1. a) Formulate the following assignment problems as LPs (special case of the transportation problem) (10 points each) b) Solve the two problems using the Hungarian method. Show all the steps. (10 points each) 78 677 5 24 21 6 5 2 75 6 1586 6 3 2 75 12 3 2 5 7 98 2 103 4 9 7 3 3 8 4 12 35 6 10 146 NETWORK MODEL (70 points each) Q2. Formulation 6.15 (pg.292 of the textbook, 10th edition). (10 points) Q3. For the following networks, consider the networks as undirected networks and compute the Minimal Spanning Tree. (10 points each) Q4. For the following networks, consider the problems as Shortest Paths start from node 1: a) Formulate the problems as LPs, consider the destination nodes as 8 for network I and 7 for network 2. (10 points each) b) Compute the shortest Paths from node 1 to all other nodes. (10 points each) NOTE: Show all iterations with all steps clearly. Network 1: 2 8 3 8 8 Network 2: 2 12 5 6 5 2 14 3 12 7 4 7 6 3 3