UNB/ CS/ David Bremner/ teaching/ cs6375/ assignments/ CS6375-FR01A Assignment 4
  1. 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*.

  2. 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.

  3. 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

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

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

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