Exercise 6 [U] [G] . ...... . . 10 points CO 3 4 7 4 2 3 CO 1 6 9 2 12 5 4 1 2Consider the uncapacitated network ow problem shown in the gure above. The label next to each arc is its cost. Consider the spanning tree indicated by the dashed arcs in the gure and the associated basic solution. (a) (1 point) What are the values of the arc ows corresponding to this basic solution? Is this a basic feasible solution? (b) (1 point) For this basic solution, nd the reduced cost of each arc in the network. (c) (1 point) Is this basic solution optimal? (d) (1 point) Does there exist a nondegenerate optimal basic feasible solution? (e) (1 point) Find an optimal dual solution. (f) (2 points) By how much can we increase (:55 (the cost of arc (5, 6)) and still have the same optimal basic feasible solution? (g) (2 points) If we increase the supply at node 1 and the demand at node 9 by a small positive amount 6, what is the change in the value of the optimal cost? (h) (1 point) Does this problem have a special structure that allows us to solve it by solving few instances of a different network optimization problem seen in class