Consider the minimum cost flow problem with nonnegativity constraints. Show that the dual problem is feasible, i.e., there exists a price vector p withnd only if all forward cycles have nonnegative cost. Hint: Assume without loss of generality that the primal is feasible (take si = 0 if necessary), and note that all forward cycles have nonnegative cost if and only if the primal problem is not unbounded (see the discussion near the beginning of Section 5.1). Alternatively
