1. Write the dual of the above max-?ow problem.

2. Solve both problems with AMPL, and for each print the values of the vari- ables and the values of the dual variables (if a problem has a constraint c1, its dual value can be displayed with the command "display c1.dual;"). Verify that the numbers correspond between primal and dual, and that the optimal solution of the primal and the dual is in accordance with duality.

3. Show the minimum cut that results from solving the dual problems.

4. Consider replacing the objective function in the max cut problem with max x_s1+x_s2 which gives an equivalent formulation of the max-?ow prob- lem. How does the dual formulation change? Explain why it is equivalent to the ?rst dual problem.

max x_2t + x_3t

x_s1 = x₁₂ + x₁₃

x_s2 + x₁₂ = x_2t

x₁₃ = x_3t

0 ≤ x_s1 ≤ 2

0 ≤ x_s2 ≤ 3

0 ≤ x₁₂ ≤ 3

0 ≤ x₁₃ ≤ 4

0 ≤ x_2t ≤ 2

0 ≤ x_3t ≤ 1