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
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?
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.
The
Minkowski Difference
X⊖Y
of setsX
andY
is defined as{ x - y | x ∈ X, y ∈ Y }
. Prove that ifX
andY
are convex then so isX ⊖ Y
.Prove that even if
P
andQ
are convex,P ∪ Q
is not necessarily convex.Prove that for any LP, for any point
z
, the set of feasible points with the same objective value asz
is convex.