UNB/ CS/ David Bremner/ teaching/ cs6375/ assignments/ CS6375-FR01A Assignment 3

You are given the following linear program (LP) in equational form:

min -x₁ -x₂

s.t. 2x₁ + 3x₂  +x₃  = 12        (LP)
     x₁  + x₄        = 5
     x₁  + 4x₂  +x₅     = 16
     xᵢ ≥ 0
  1. Consider the point x₂=4,X₄=5,X₁=X₃=X₅=O. Is x feasible for (LP)? Is it a basic feasible solution (BFS)? Is it degenerate?

  2. Consider the point x₁=1,x₂=2,x₃=4,x₄=4,x₅=7. Use the construction of the proof of Theorem 4.2.3 to find a basic feasible solution with objective value no worse than this point.

  3. The Minkowski Difference X⊖Y of sets X and Y is defined as { x - y | x ∈ X, y ∈ Y }. Prove that if X and Y are convex then so is X ⊖ Y.

  4. Prove that even if P and Q are convex, P ∪ Q is not necessarily convex.

  5. Prove that for any LP, for any point z, the set of feasible points with the same objective value as z is convex.