Linear Programming

Linear programming is a branch of mathematical optimization concerned with maximizing or minimizing a linear objective function subject to finitely many linear equalities and inequalities. Its decision variables ordinarily take continuous real values, rather than being restricted to whole numbers. Linear programming is a special case of convex optimization and provides a framework for allocating resources, organizing production, and analyzing economic decisions. Here, “programming” originally refers to planning, not writing computer code. (courses.csail.mit.edu)

Mathematical formulation

A common formulation is

The vector $x$ contains the decision variables; $c$ contains their objective coefficients; the matrix $A$ specifies how variables enter the constraints; and $b$ gives the constraint limits. Vector inequalities are interpreted componentwise. The objective is a linear combination of the variables, so products between decision variables, powers such as $x_j^2$, and variable-dependent coefficients are excluded. (courses.csail.mit.edu)

Equivalent formulations use minimization, equality constraints, or unrestricted variables. Maximization becomes minimization by negating the objective. An unrestricted variable can be written as the difference of two nonnegative variables. A constraint $a^{T}x\leq b$ becomes $a^{T}x+s=b$ by introducing a nonnegative slack variable. These transformations produce the frequently used standard form $Ax=b,\ x\geq0$; terminology for “standard” and “canonical” forms varies between texts. (courses.csail.mit.edu)

Geometry and possible outcomes

The feasible set consists of all variable assignments satisfying the constraints. Each linear inequality defines a half-space, while an equality defines a hyperplane when its coefficient vector is nonzero. Their intersection is a polyhedron and a convex set: every line segment between feasible points remains feasible. A bounded polyhedron is commonly called a polytope. (courses.csail.mit.edu)

A linear program has three principal outcomes: it is infeasible, it attains a finite optimum, or it is unbounded in the improving direction. An unbounded feasible set does not necessarily imply an unbounded objective. Several points may share the optimal value; their convex combinations are then also optimal. (courses.csail.mit.edu)

For a standard-form problem with a finite optimum, at least one optimal solution is a basic feasible solution, corresponding to an extreme point of the feasible polyhedron. This vertex property underlies the simplex method. It requires qualification for general formulations: a polyhedron containing a line may have no extreme points, even though an objective attains its optimum. (courses.csail.mit.edu)

A production example

Consider a hypothetical workshop producing divisible quantities $x$ and $y$ of two products. Their unit profits are 3 and 2, respectively, and resource limits give

The assignment $x=2,\ y=2$ is feasible and yields profit 10. It is optimal because every feasible assignment satisfies

This constructed example illustrates both a feasible production plan and a certificate that no feasible plan can improve its objective value.

Duality and sensitivity

Associated with the maximization formulation above is the dual problem

Here $A^{T}$ is the transpose of $A$. This relationship is an instance of Lagrangian duality. Weak duality states that every dual feasible solution bounds every primal feasible objective from above. Strong duality states that, when the primal has a finite optimum, the dual also attains an optimum with the same value. (math.mit.edu)

Complementary slackness characterizes optimal primal–dual pairs:

Thus a strictly unused resource has zero corresponding dual multiplier, and a positive decision variable has a tight corresponding dual constraint. (math.mit.edu)

In resource-allocation models, dual multipliers are often interpreted as shadow prices. Sensitivity analysis studies how solutions and objective values change when coefficients or resource limits change. A multiplier measures a resource’s marginal value only within an appropriate range; larger changes can alter the optimal basis and the applicable marginal value. (web.mit.edu)

Solution methods

The simplex method operates on bases of the constraint system, using pivot operations to move among basic feasible solutions. Geometrically, nondegenerate steps move along polyhedron edges. Degeneracy can permit pivots without objective improvement and can cause cycling unless suitable pivot rules are used. Although widely effective in practice, familiar simplex variants can require exponentially many steps on specially constructed instances. (courses.csail.mit.edu)

The ellipsoid method and interior-point methods provide polynomial-time algorithms. Interior-point approaches typically use barrier functions and a sequence of problems leading toward optimality rather than traversing vertices. Their complexity guarantees for rational inputs depend on the encoded input length, including coefficient bit lengths. (courses.csail.mit.edu)

Development and applications

Leonid Kantorovich developed early resource-allocation methods in 1939. George Dantzig devised the simplex method in 1947. Kantorovich and Tjalling Koopmans jointly received the 1975 Nobel Memorial Prize in Economic Sciences for contributions to optimal resource allocation. (nobelprize.org)

Applications include transportation, blending, production planning, and game theory, particularly finite zero-sum games. When quantities must be whole numbers, the model becomes integer programming. Removing integrality requirements yields a linear relaxation whose optimum bounds the integer optimum, but rounding its solution need not preserve feasibility or optimality. (web.mit.edu)