Problem 1: (50 points) Given the network shown below, where the labels next to the nodes are the supplies/demand and the labels on the edges are the costs, capacities). We wish to minimize the cost of this transshipment problem. a. Find a feasible spanning tree for this problem. b. Given this spanning tree, use the network simplex algorithm to determine the dual prices for this spanning tree and the associated reduced costs of all non-basic arcs. c. Is the spanning tree optimal? If not, indicate the entering arc, the leaving arc and how much flow would be increased/decreased on this arc and perform one pivot. If it is optimal, prove that it is by stating the optimality conditions, i.e., show that there are no violating non-basic arcs. 3 $5,5 $2,4 $6,3 $4,4 $1,2 b $3,4 $6,3 $3,2 $2,3 3