LP outcomes

Work in Progress

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