Exercise 7.20 (Duality and the max-flow min-cut theorem) Consider the maximum flow problem. (a) Let pi be a price variable associated with the flow conservation constraint at node i. Let qij be a price variable associated with the capacity constraint at arc (i,j). Write down a minimization problem, with variables pi and qij, whose dual is the maximum flow problem. 352 Chap. 7 Network flow problems (b) Show that the optimal value in the minimization problem is equal to the minimum cut capacity, and prove the max-flow min-cut theorem. Exercise 7.20 (Duality and the max-flow min-cut theorem) Consider the maximum flow problem. (a) Let pi be a price variable associated with the flow conservation constraint at node i. Let qij be a price variable associated with the capacity constraint at arc (i,j). Write down a minimization problem, with variables pi and qij, whose dual is the maximum flow problem. 352 Chap. 7 Network flow problems (b) Show that the optimal value in the minimization problem is equal to the minimum cut capacity, and prove the max-flow min-cut theorem