Let

*x*^{*}be a non-degenerate basic feasible solution to some LP.Explain how to construct the corresponding simplex tableau (dictionary) from

*x*^{*}.Explain when the resulting tableau provides a proof of the optimality of

*x*^{*}.

Let

*Γ*_{2}be an LP with*n*variables. Prove that if feasible point*x*^{*}satisfies*n*linearly independent constraints with equality,*x*^{*}is a vertex of the feasible region of*Γ*_{2}.Construct simplex stage I problem (auxiliary problem) for the following LP, and give a feasible solution to the auxiliary problem.

max x₁ + x₂, -3 ≤ x₁ ≤ -1, 0 ≤ x₂ ≤ 1

Prove that (feasible) simplex tableaus are in one to one correspondence with feasible bases.

Give a geometric interpretation of the simplex ratio test. Consider both the unbounded and the bounded case.

Describe in detail how to choose an entering and leaving variable to do a simplex pivot. What special cases can arise?