Linear programming

Summary

Linear programming is the optimization of a linear function over the set of solutions of finitely many linear inequalities. The feasible set is a convex polyhedron. When an optimum exists, it is attained on a face, and at a vertex when the polyhedron has vertices. Each linear program has a dual program. If one of the two has an optimal solution, so does the other, with the same optimal value; this is tied to Farkas' lemma. Linear programs are solved in practice by the simplex algorithm and by interior point methods. The ellipsoid method and interior point methods solve them in polynomial time.