Return to the minimum cost network flow instance of Exercise 10-20. The figure below depicts the same instance with different values for the current flow, including many marked ‘?’ for unknown.

(a) Demonstrate that arcs with flow indicated as ‘?” form a basis of the corresponding LP.

(b) Compute the corresponding basic solution and establish that it is feasible.

(c) Explain why the basic solution of

(b) is degenerate.

(d) Start from the solution of (b), and apply Network Simplex Algorithm 10C to compute an optimal solution. Show details of reduced costs, stepsize computation, basis updates, etc.