Question 1: (30 pts) Consider the figure below. Only movement from smaller numbered nodes to higher numbered nodes are allowed. 40 10 40 30 10 15 45 a) (15 points) Find the minimal spanning tree using the algorithm given in class and report the optimal solution. b) (15 points) Find the shortest path using the algorithm given in class and report the shortest path from 1 to all the other nodes. Question 2: (20 pts) Karkargo is a parcel delivery company located in Turkey. The managers are considering opening an office in some of 6 districts of Istanbul. The concern of the managers is that there should be an office located within 20 kilometers of each district. The annual operating cost of the offices along with the distance between each district is given below. Distances 3 4 5 6 10 1 16 10 21 10 Districts Operating cost 470000 410000 575000 2 24 28 25 15 Ngo | | | 3 16 14 26 4 410000 10 13 WCOW 10 29 23 5 21 25 14 0 570000 460000 12 0 6 10 15 26 12 The managers are willing minimize total operating cost. Formulate a linear programming model that will help the managers in their decision