Exercise 7.10

.10 Consider the uncapacitated network flow problem shown in Fig Exercise ure 7.38. The indicated by the label next to each arc is its cost. Consider the spanning tree dashed arcs in the figure and the associated basic solution. ar hat are the values of the are lows corresponding to this basic solution? For this basic solution, find the reduced cost of each are in the network. ls this a basic feasible solution? (e) Is this basic solution optimal? d) Does there exist a nondegenerate optimal basic feasible solution? e) Find an optimal dual solution. (f) By how much can we increase css (the cost of arc (5,6) and still have the same optimal basic feasible solution? positive amount 6, what is the change in the value of the optimal cost? general uncapacitated net work flow problem? g) If we increase the supply at node 1 and the demand at node 9 by a small ansportation problem with two source nodes s1,s2, and n demand nodes 1,... n. 18) are assumed to be present and to have infinite capacity: Let D be the total demand. Let the supply at each source node be equal Al arcs (j) /2. Assume that d, > 0 for all i. (a) How h many basic variables are there in a basic feasible solution? b) Show w that there exists a degenerate basic feasible solution if and only if exists some set S {1, , n} such that es d' = D/2. .10 Consider the uncapacitated network flow problem shown in Fig Exercise ure 7.38. The indicated by the label next to each arc is its cost. Consider the spanning tree dashed arcs in the figure and the associated basic solution. ar hat are the values of the are lows corresponding to this basic solution? For this basic solution, find the reduced cost of each are in the network. ls this a basic feasible solution? (e) Is this basic solution optimal? d) Does there exist a nondegenerate optimal basic feasible solution? e) Find an optimal dual solution. (f) By how much can we increase css (the cost of arc (5,6) and still have the same optimal basic feasible solution? positive amount 6, what is the change in the value of the optimal cost? general uncapacitated net work flow problem? g) If we increase the supply at node 1 and the demand at node 9 by a small ansportation problem with two source nodes s1,s2, and n demand nodes 1,... n. 18) are assumed to be present and to have infinite capacity: Let D be the total demand. Let the supply at each source node be equal Al arcs (j) /2. Assume that d, > 0 for all i. (a) How h many basic variables are there in a basic feasible solution? b) Show w that there exists a degenerate basic feasible solution if and only if exists some set S {1, , n} such that es d' = D/2