A linear program optimizes a linear objective subject to linear equality and inequality constraints. A standard minimization form is

$$\min_x c^T x$$

subject to

$$Ax\le b.$$

Each linear inequality defines a half-space. Their intersection is a convex polyhedron, which is the feasible set of the problem.

Because both the objective and feasible set are convex, every local optimum is global.

When the feasible set is a bounded polyhedron, or polytope, a linear objective that attains an optimum has at least one optimal solution at an extreme point, or vertex. This geometric fact motivates algorithms that move between vertices rather than searching every feasible point.

Linear programming models resource allocation, blending, transportation and many planning problems whenever both costs and constraints can be represented linearly.