*SOLVE THE QUESTION MANUALLY WITHOUT USING A SOFTWARE

a) Find the maximum flow from source to sink using the Ford-Fulkerson algorithm. The numbers on the arcs are the capacities of arcs. Show your work step by step. 2 2 7 8 So si 3 5 b) Find a cut in the network whose capacity equals the maximum flow in the network. c) Set up an LP that can be used to determine the maximum flow in the network. Write the model explicitly, not in compact form. d) Find the dual of the maximum flow problem in (c). Write the model explicitly, not in compact form. Use dual variables pi and dij for appropritae constraints in the primal model in (c). e) Now, define dij to take on the value of 1 if (i,j) is in the cut and 0, otherwise. Moreoever, let pi=0 if ie{T} and pi=1 if ies}. Take the cut you found in part b. Verify whether this assignment of variables satisfies the constraints in the dual problem for the cut you found and find the objective function value of the dual model. How can you interpret this result? What theorem applies in this case