2. Maximum flow problem (35 pts). Consider the network shown below. 2 Source Sink 3 3 a) (20 pts) Use the augmenting path algorithm to find the maximum flow from the source to the sink. The numbers show the forward capacities of the arcs, and the backward capacities are all zero. In every iteration, clearly identify the augmenting path and flow amount. Give the optimal solution (flow on each arc and maximum flow amount). b) (15 pts) Formulate this maximum flow problem as a linear programming problem. 3. Transportation problem (25 pts). Consider the following transportation tableau. The solution values and supply, demand and cost parameters are depicted on the tableau. 1 800 20 600 4 0 Supply 50 Source 1 Destination 2 3 700 400 20 10 800 500 10 20 20 50 Source 2 Demand 0 40 40 20 a) (5 pts) Explain why this solution is a basic feasible solution. b) (20 pts) Starting with the initial solution given, apply the transportation simplex method for one iteration. Show your work! 2. Maximum flow problem (35 pts). Consider the network shown below. 2 Source Sink 3 3 a) (20 pts) Use the augmenting path algorithm to find the maximum flow from the source to the sink. The numbers show the forward capacities of the arcs, and the backward capacities are all zero. In every iteration, clearly identify the augmenting path and flow amount. Give the optimal solution (flow on each arc and maximum flow amount). b) (15 pts) Formulate this maximum flow problem as a linear programming problem. 3. Transportation problem (25 pts). Consider the following transportation tableau. The solution values and supply, demand and cost parameters are depicted on the tableau. 1 800 20 600 4 0 Supply 50 Source 1 Destination 2 3 700 400 20 10 800 500 10 20 20 50 Source 2 Demand 0 40 40 20 a) (5 pts) Explain why this solution is a basic feasible solution. b) (20 pts) Starting with the initial solution given, apply the transportation simplex method for one iteration. Show your work