Linear Programming (LP)

Linear programming is the problem class max c^T x s.t. Ax ≤ b, x ≥ 0 in canonical form, where c ∈ R^n is the cost vector, A ∈ R^(m×n) the constraint matrix, b ∈ R^m the right-hand side, and x ∈ R^n the continuous real decision variables. The feasible region X = {x : Ax ≤ b, x ≥ 0} is a convex polytope, and a linear objective attains its optimum at a vertex (basic feasible solution). The discipline was founded by George B. Dantzig's simplex algorithm in 1947, motivated by US Air Force planning problems (whence the term 'programming', predating its computer-science usage). Duality theory (von Neumann 1947) associates a dual LP to every primal LP, and the strong duality theorem states that if either is feasible and bounded their optimal objective values coincide; shadow prices are read from the dual variables. Complexity: Klee and Minty (1972) showed the simplex method is exponential in the worst case; Khachiyan (1979) gave the first polynomial-time LP algorithm via the ellipsoid method (theoretical); Karmarkar (1984) introduced an interior-point method that is polynomial and practical. Modern solvers combine revised simplex and interior-point algorithms, with presolve, sparse LU factorization, and crash starts, solving million-variable problems in seconds. Practical application domains include production planning, blending, transportation, cash-flow management, and the diet problem.