$9\mathrm{.}16.$ Figure $9\mathrm{.}21($b$)$ shows the optimal solution of the minimum cost flow problem shown in Figure $9\mathrm{.}21($a$).$ First, verify that $x^{**}$ is a feasible flow.

$($a$)$ Draw the residual network $G(x^{**})$ and show that it contains no negative cycle.

$($b$)$ Specify a set of node potentials $$ that together with $x^{**}$ satisfy the reduced cost optimality conditions. List each arc in the residual network and its reduced cost.

Figure $9\mathrm{.}21$ Minimum cost flow problem: $($a$)$ problem data; $($b$)$ optimal solution.

$348$

Minimum Cost Flows: Basic Algorithms

Chap. $9$

$($c$)$ Verify that the solution $x^{**}$ satisfies the complementary slackness optimality conditions. To do so$,$ specify a set of optimal node potentials and list the reduced cost of each arc in $A.$