Consider the following linear programming problem: max 2x1+x2

s.t. 2x1 x2 10

2x1 + x2 16

x1,x2 0.

1. Sketch the graph of the feasible region for this linear programming problem, and determine the coordinates of the vertices.

2. Formulate the dual of this linear programming problem.

3. Represent the feasible region of the dual problem graphically and determine the coordinates of the vertices.

4. Use the simplex algorithm to solve the primal problem (that is, the original problem, not the dual problem) starting from the basis of slacks.

5. Identify the sequence of basis solutions that the simplex algorithm uses to find the optimal solution on the picture you drew in Part 1.

6. At each iteration of the simplex algorithm, record the reduced costs (negative of the coefficients in the top row/objective row of the tableau) of the slack variables. Represent these points on the graph you drew in Part 3. From this, you can infer that each iteration of the simplex algorithm also corresponds to a point in the dual problem (although the point in the dual problem will not be a feasible solution until the final tableau; or in other words, simplex gives you an optimal solution to both the primal and the dual problem).