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?