Using the modified rij values we will find an optimal solution and can prove theorem 6.10
Theorem 6.10 (Generalized Max-Flow Min-Cut Theorem). If the capacity of an s-t cut [s, ] in a network with both lower and upper bounds on arc flows is defined by (6.7), the maximum value of flow from node s to node t equals the minimum capacity among all s-t cuts.
How find a feasible flow?
First transform to a circulation problem.
(t, s) with uts =
Find a flow satisfying
let xij = xij - lij
Like feasible flow in application 6.1.
The maximum flow problem has a feasible solution iff the circulation has a feasible flow.
Can show theorem 6.11