Note: If you know the book pls comment the book notes with your answers thx:)

10. Maximal/minimal flow in networks with lower bounds. The maximal flow algorithm given in this section assumes that all the arcs have zero lower bounds. In some models, the lower bounds may be strictly positive, and we may be interested in finding the maximal or minimal flow in the network (see case 6-3 in Appendix E). The presence of the lower bound poses difficulty because the network may not have a feasible flow at all. The objec- tive of this exercise is to show that any maximal and minimal flow model with positive lower bounds can be solved using two steps. Step 1. Find an initial feasible solution for the network with positive lower bounds. Step 2. Using the feasible solution in step 1, find the maximal or minimal flow in the original network. (a) Show that an arc (i, j) with flow limited by bj = Xij sui can be represented equiva- lently by a sink with demand li; at node i and a source with supply hij at nodej with flow limited by 0 S xj Sulij (b) Show that finding a feasible solution for the original network is equivalent to finding the maximal flow xij in the network after (1) modifying the bounds on Xij to Os xy S Wij - lij (2) "lumping" all the resulting sources into one supersource with outgoing arc capacities lij (3) "lumping" all the resulting sinks into one supersink with incoming arc capacities ly, and (4) connecting the terminal node to the source node s in the original network by a return infinite-capacity arc. A feasible solution exists if the maximal flow in the new network equals the sum of the lower bounds in the original network. Apply the procedure to the following network and find a feasi- ble flow solution: Arc (1,7) (1,2) (1,3) (2,3) (2,4) (3,4) (5,20) (0.15) (4, 10) (3, 15) (0,20) (c) Use the feasible solution for the network in (b) together with the maximal flow algo rithm to determine the minimal flow in the original network. (Hint: First compute the residue network given the initial feasible solution. Next, determine the maximum flow from the end node to the start node. This is equivalent to finding the maximum flow that should be canceled from the start node to the end node. Now, combining the fea- sible and maximal flow solutions yields the minimal flow in the original network.) (d) Use the feasible solution for the network in (b) together with the maximal flow model to determine the maximal flow in the original network. (Hint: As in part (c), start with the residue network. Next apply the breakthrough algorithm to the result- ing residue network exactly as in the regular maximal flow model.) 10. Maximal/minimal flow in networks with lower bounds. The maximal flow algorithm given in this section assumes that all the arcs have zero lower bounds. In some models, the lower bounds may be strictly positive, and we may be interested in finding the maximal or minimal flow in the network (see case 6-3 in Appendix E). The presence of the lower bound poses difficulty because the network may not have a feasible flow at all. The objec- tive of this exercise is to show that any maximal and minimal flow model with positive lower bounds can be solved using two steps. Step 1. Find an initial feasible solution for the network with positive lower bounds. Step 2. Using the feasible solution in step 1, find the maximal or minimal flow in the original network. (a) Show that an arc (i, j) with flow limited by bj = Xij sui can be represented equiva- lently by a sink with demand li; at node i and a source with supply hij at nodej with flow limited by 0 S xj Sulij (b) Show that finding a feasible solution for the original network is equivalent to finding the maximal flow xij in the network after (1) modifying the bounds on Xij to Os xy S Wij - lij (2) "lumping" all the resulting sources into one supersource with outgoing arc capacities lij (3) "lumping" all the resulting sinks into one supersink with incoming arc capacities ly, and (4) connecting the terminal node to the source node s in the original network by a return infinite-capacity arc. A feasible solution exists if the maximal flow in the new network equals the sum of the lower bounds in the original network. Apply the procedure to the following network and find a feasi- ble flow solution: Arc (1,7) (1,2) (1,3) (2,3) (2,4) (3,4) (5,20) (0.15) (4, 10) (3, 15) (0,20) (c) Use the feasible solution for the network in (b) together with the maximal flow algo rithm to determine the minimal flow in the original network. (Hint: First compute the residue network given the initial feasible solution. Next, determine the maximum flow from the end node to the start node. This is equivalent to finding the maximum flow that should be canceled from the start node to the end node. Now, combining the fea- sible and maximal flow solutions yields the minimal flow in the original network.) (d) Use the feasible solution for the network in (b) together with the maximal flow model to determine the maximal flow in the original network. (Hint: As in part (c), start with the residue network. Next apply the breakthrough algorithm to the result- ing residue network exactly as in the regular maximal flow model.)