- Problem 4. HL 10.7-1 (a)-(c). For 9.7-1, (a), change "C + A (a reverse arc)" to "AC; change "C + B also a reverse arc to B + C. There is still degeneracy in this problem (some basic variable has value 0, actually, XDE = 0 for this case). 2 p10.7-1. Consider the minimum cost flow problem shown below, where the b; values (net flows generated) are given by the nodes, the ci; values (costs per unit flow) are given by the arcs, and the Uj; values (arc capacities) are given between nodes C and D. Do the following work manually. (a) Obtain an initial BF solution by solving the feasible spanning tree with basic arcs AB, CE,DE, and C A (a reverse arc), where one of the nonbasic arcs (CB) also is a reverse arc. Show the resulting network (including bi, Cij, and uj) in the same format as the above one (except use dashed lines to draw the nonbasic arcs), and add the flows in parentheses next to the basic arcs. [20] 10] 6 1-30] S Are capacities A-C: 10 B-C: 25 Others: 2 B 10) [10] (b) Use the optimality test to verify that this initial BF solution is optimal and that there are multiple optimal solutions. Apply one iteration of the network simplex method to find the other optimal BF solution, and then use these results to identify the other optimal solutions that are not BF solutions. (c) Now consider the following BF solution. Basic Arc Flow Nonbasic Arc A-D A-C CE D-E 20 10 10 20 Starting from this BF solution, apply one iteration of the network simplex method. Identify the entering basic arc, the leaving basic arc, and the next BF solution, but do not proceed further. - Problem 4. HL 10.7-1 (a)-(c). For 9.7-1, (a), change "C + A (a reverse arc)" to "AC; change "C + B also a reverse arc to B + C. There is still degeneracy in this problem (some basic variable has value 0, actually, XDE = 0 for this case). 2 p10.7-1. Consider the minimum cost flow problem shown below, where the b; values (net flows generated) are given by the nodes, the ci; values (costs per unit flow) are given by the arcs, and the Uj; values (arc capacities) are given between nodes C and D. Do the following work manually. (a) Obtain an initial BF solution by solving the feasible spanning tree with basic arcs AB, CE,DE, and C A (a reverse arc), where one of the nonbasic arcs (CB) also is a reverse arc. Show the resulting network (including bi, Cij, and uj) in the same format as the above one (except use dashed lines to draw the nonbasic arcs), and add the flows in parentheses next to the basic arcs. [20] 10] 6 1-30] S Are capacities A-C: 10 B-C: 25 Others: 2 B 10) [10] (b) Use the optimality test to verify that this initial BF solution is optimal and that there are multiple optimal solutions. Apply one iteration of the network simplex method to find the other optimal BF solution, and then use these results to identify the other optimal solutions that are not BF solutions. (c) Now consider the following BF solution. Basic Arc Flow Nonbasic Arc A-D A-C CE D-E 20 10 10 20 Starting from this BF solution, apply one iteration of the network simplex method. Identify the entering basic arc, the leaving basic arc, and the next BF solution, but do not proceed further