LP outcomes
Concept
Fundamental Theorem of LP
Certificate
- proof of the solution by the solver
Feasibility
Proving infeasibility
Farkasโ Lemma
will be slightly different for different forms of LP
Optimality
Proving optimality
Unbounded
Proving unboundedness
-
construct a family of feasible solutions
and show that as increases, the function goes to infinity -
must be feasible for all
when
For
- infeasibility is certified by
and ; Farkasโ lemma says such exists whenever the system is infeasible; - unboundedness is certified by feasible
and a ray with and , since is feasible and improves forever; - optimality is certified by a feasible point attaining a valid objective bound, later supplied systematically by strong duality.
Application
Feasibility
Optimality
- infinite optimal solutions
there can be multiple optimal solutions
- feasible but no optimal, unbounded
Strict inequalities
Nonlinear objective function