Optimization

Linear Programming

Optimize a linear objective subject to linear equality and inequality constraints: the most widely used class of optimization.

Standard form

A linear program (LP) minimizes c dot x subject to A x = b and x >= 0. Any LP with inequalities, free variables, or maximization can be converted to this form by adding slack variables and splitting free variables. The feasible region is a polyhedron, a convex set with flat faces and vertices.

Geometry of the optimum

Because both objective and constraints are linear, the optimum, if it exists and is finite, is attained at a vertex (extreme point) of the polyhedron. This fundamental fact reduces a continuous search to a search over finitely many vertices and underlies the simplex method.

Solution methods

The simplex method walks along edges from vertex to vertex, improving the objective each step.
Interior-point methods cut through the interior and reach the optimum in polynomial time.
Both are mature; large industrial LPs with millions of variables are solved routinely.

Duality

Every LP has a dual LP whose optimal value equals the primal optimal value (strong duality holds whenever either is feasible and bounded). The dual variables are shadow prices measuring the sensitivity of the optimum to each constraint, which is central to economic and engineering interpretation.

Applications

LP models resource allocation, scheduling, transportation, blending, and network flow. Many nonlinear problems are approximated by sequences of LPs. LP relaxations also provide bounds for integer programming, where variables are restricted to integers and the problem becomes NP-hard.

python

from scipy.optimize import linprog
# min c^T x s.t. A_ub x <= b_ub, x >= 0
res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None))

Linear and mixed-integer programming schedule construction sequences, allocate limited resources, and plan logistics for complex engineering programs.