Linear programming optimizes a linear objective subject to linear constraints. Despite this restricted form, linear programs describe production planning, transportation, scheduling, resource allocation, network flows, portfolio constraints, and many subproblems inside more elaborate optimization methods.
The central idea is geometric: each linear constraint cuts space with a hyperplane, the feasible points form a convex polyhedron, and a linear objective moves parallel level sets across that polyhedron until no further improvement is possible.
The Optimization Model
Let \(\mathbf{x}\in\mathbb{R}^n\) be the vector of decision variables. A linear program has the form
\[ \begin{aligned} \operatorname{maximize}\quad & \mathbf{c}^{\mathsf T}\mathbf{x}\\ \operatorname{subject\ to}\quad & A_{\le}\mathbf{x}\le\mathbf{b}_{\le},\\ & A_{= }\mathbf{x}=\mathbf{b}_{=},\\ & \boldsymbol{\ell}\le\mathbf{x}\le\mathbf{u}. \end{aligned} \]
Every part has a distinct role:
- \(\mathbf{x}\) contains the quantities that may be chosen.
- \(\mathbf{c}\) assigns an objective coefficient to each decision variable.
- The rows of \(A\) encode resource, balance, or coupling constraints.
- \(\mathbf{b}\) contains the corresponding limits or requirements.
- \(\boldsymbol{\ell}\) and \(\mathbf{u}\) impose lower and upper bounds.
A point satisfying every constraint is feasible. The set of all such points is the feasible set \(P\). An optimal solution \(\mathbf{x}^*\) is a feasible point whose objective value is at least as large as that of every other feasible point:
\[ \mathbf{x}^*\in P, \qquad \mathbf{c}^{\mathsf T}\mathbf{x}^* =\max_{\mathbf{x}\in P}\mathbf{c}^{\mathsf T}\mathbf{x}. \]
A minimization problem is equally linear. Multiplying the objective by \(-1\) converts it into a maximization problem because
\[ \operatorname{minimize}_{\mathbf{x}\in P}\mathbf{c}^{\mathsf T}\mathbf{x} \quad\Longleftrightarrow\quad \operatorname{maximize}_{\mathbf{x}\in P}-\mathbf{c}^{\mathsf T}\mathbf{x}. \]
A Complete Two-Variable Example
Suppose two products use two limited resources. Let \(x_1\) and \(x_2\) denote their production quantities. Their profits are \(3\) and \(2\), while their resource requirements lead to
\[ \begin{aligned} \operatorname{maximize}\quad & 3x_1+2x_2\\ \operatorname{subject\ to}\quad & x_1+x_2\le4,\\ & 2x_1+x_2\le5,\\ & x_1,x_2\ge0. \end{aligned} \]
The feasible polygon is bounded by the coordinate axes and the two resource constraints. Moving an objective line in the improving direction makes it last touch the polygon at \((1,3)\).
The four vertices and their objective values are
\[ \begin{array}{c|c} (x_1,x_2) & 3x_1+2x_2\\ \hline (0,0) & 0\\ (0,4) & 8\\ (1,3) & 9\\ (2.5,0) & 7.5 \end{array} \]
Hence \(\mathbf{x}^*=(1,3)^{\mathsf T}\) and the optimal value is \(9\).
Why the Feasible Set Is Convex
Consider one inequality \(\mathbf{a}^{\mathsf T}\mathbf{x}\le b\). If \(\mathbf{x}\) and \(\mathbf{y}\) satisfy it, then every point on the line segment between them also satisfies it. For \(0\le\lambda\le1\),
\[ \begin{aligned} \mathbf{a}^{\mathsf T}\bigl(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\bigr) &=\lambda\mathbf{a}^{\mathsf T}\mathbf{x} +(1-\lambda)\mathbf{a}^{\mathsf T}\mathbf{y}\\ &\le\lambda b+(1-\lambda)b=b. \end{aligned} \]
Equalities and variable bounds have the same property. Since an intersection of convex sets is convex, every linear-programming feasible set is convex. With finitely many linear constraints it is a polyhedron; if it is also bounded, it is a polytope.
Convexity rules out isolated local optima that are worse than the global optimum. If a feasible direction improves the objective locally, moving along it continues to improve the same linear objective until another constraint becomes active.
Objective Hyperplanes and Vertices
For a fixed value \(z\), the equation
\[ \mathbf{c}^{\mathsf T}\mathbf{x}=z \]
describes a hyperplane perpendicular to \(\mathbf{c}\). Increasing \(z\) translates this hyperplane in the direction of \(\mathbf{c}\) without rotating it. Over a nonempty polytope, the last contact occurs on a face. At least one vertex of that face is therefore optimal.
This vertex principle is the geometric basis of the simplex method. It does not imply that the optimum is always unique: if an objective hyperplane is parallel to an edge or a higher-dimensional face, every point on that face can be optimal.
Equality Standard Form
Algorithms need one consistent representation. Here, standard form means
\[ \begin{aligned} \operatorname{maximize}\quad & \mathbf{c}^{\mathsf T}\mathbf{x}\\ \operatorname{subject\ to}\quad & A\mathbf{x}=\mathbf{b},\\ & \mathbf{x}\ge\mathbf{0}. \end{aligned} \]
Some books use the name for an inequality form instead. The mathematics is unchanged, but stating the convention matters because the conversion rules and simplex notation depend on it.
Changing the Optimization Direction
Replace a minimization objective by its negative:
\[ \operatorname{minimize}\;z \quad\Longleftrightarrow\quad \operatorname{maximize}\;(-z). \]
The feasible set is untouched, and the minimizer of \(z\) is the maximizer of \(-z\).
Normalizing a Negative Right-Hand Side
Multiplying an entire constraint by \(-1\) reverses its inequality:
\[ -2x_1+4x_2-x_3\ge-9 \quad\Longleftrightarrow\quad 2x_1-4x_2+x_3\le9. \]
This operation is useful before introducing slack variables. Multiplying only one side, or forgetting to reverse the inequality, changes the feasible set.
Slack and Surplus Variables
For a constraint \(\mathbf{a}^{\mathsf T}\mathbf{x}\le b\), define its nonnegative slack
\[ s=b-\mathbf{a}^{\mathsf T}\mathbf{x}\ge0. \]
The inequality is then equivalent to
\[ \mathbf{a}^{\mathsf T}\mathbf{x}+s=b, \qquad s\ge0. \]
The value of \(s\) is the unused amount of the constrained resource. Conversely, for \(\mathbf{a}^{\mathsf T}\mathbf{x}\ge b\), define the surplus \(s=\mathbf{a}^{\mathsf T}\mathbf{x}-b\ge0\), giving
\[ \mathbf{a}^{\mathsf T}\mathbf{x}-s=b, \qquad s\ge0. \]
A surplus variable makes the equation equivalent to the original inequality, but it does not automatically provide an initial simplex basis. That separate issue is handled by Phase I.
Free and Bounded Variables
A variable unrestricted in sign can be represented as the difference of two nonnegative variables:
\[ x_j=x_j^+-x_j^-, \qquad x_j^+,x_j^-\ge0. \]
Every real value is representable: use \((x_j^+,x_j^-)=(x_j,0)\) when \(x_j\ge0\), and \((0,-x_j)\) otherwise. The representation is not unique, but all representations produce the same value of \(x_j\).
A finite lower bound can be absorbed by a shift:
\[ x_j\ge\ell_j \quad\Longleftrightarrow\quad x_j=\ell_j+y_j, \qquad y_j\ge0. \]
Similarly, an upper-bounded variable can be written as \(x_j=u_j-y_j\) with \(y_j\ge0\). When both bounds are finite, shifting the lower bound leaves the additional inequality \(y_j\le u_j-\ell_j\).
Percentage and Mixture Constraints
Let \(x_j\ge0\), let \(T=\sum_{j=1}^n x_j\), and assume \(T>0\). Requiring component \(k\) to make up at least a fraction \(p\in[0,1]\) of the total gives
\[ \frac{x_k}{T}\ge p \quad\Longleftrightarrow\quad x_k\ge p\sum_{j=1}^n x_j \quad\Longleftrightarrow\quad (1-p)x_k-p\sum_{j\ne k}x_j\ge0. \]
For example, requiring \(x_2\) to be at least \(30\%\) of three components means
\[ 0.7x_2-0.3x_1-0.3x_3\ge0. \]
Replacing \(\ge\) by \(\le\) expresses an upper percentage limit instead. The condition \(T>0\) is essential for the ratio itself; if the all-zero point must be excluded, the model needs a positive lower bound on \(T\).
Converting the Example to Standard Form
Adding one slack variable to each resource constraint gives
\[ \begin{aligned} x_1+x_2+s_1 &=4,\\ 2x_1+x_2+s_2 &=5,\\ x_1,x_2,s_1,s_2 &\ge0. \end{aligned} \]
In matrix form,
\[ \underbrace{ \begin{pmatrix} 1 & 1 & 1 & 0\\ 2 & 1 & 0 & 1 \end{pmatrix}}_{A} \underbrace{ \begin{pmatrix}x_1\\x_2\\s_1\\s_2\end{pmatrix}}_{\mathbf{x}} = \underbrace{ \begin{pmatrix}4\\5\end{pmatrix}}_{\mathbf{b}}. \]
The slack columns form the identity matrix. Setting \(x_1=x_2=0\) immediately gives the feasible solution \((s_1,s_2)=(4,5)\), which is the natural starting vertex for the simplex method.
Basic Feasible Solutions
Assume \(A\in\mathbb{R}^{m\times n}\) has row rank \(m\). Choose \(m\) linearly independent columns of \(A\) and collect them in a square basis matrix \(B\). The remaining columns form \(N\). Partitioning the variables accordingly gives
\[ B\mathbf{x}_B+N\mathbf{x}_N=\mathbf{b}. \]
Set the nonbasic variables to zero and solve for the basic variables:
\[ \mathbf{x}_N=\mathbf{0}, \qquad \mathbf{x}_B=B^{-1}\mathbf{b}. \]
If \(B^{-1}\mathbf{b}\ge\mathbf{0}\), this is a basic feasible solution. Algebraically, a basis selects enough active constraints to isolate a candidate point. Geometrically, every basic feasible solution is a vertex of the feasible polyhedron, and every vertex has at least one corresponding basis.
A basic feasible solution is degenerate when at least one basic variable is zero. Several different bases may then describe the same vertex.
Deriving a Simplex Step
For a current basis, solve the equality constraints for \(\mathbf{x}_B\):
\[ \mathbf{x}_B =B^{-1}\mathbf{b}-B^{-1}N\mathbf{x}_N. \]
Partitioning the objective coefficients into \(\mathbf{c}_B\) and \(\mathbf{c}_N\) gives
\[ \begin{aligned} z &=\mathbf{c}_B^{\mathsf T}\mathbf{x}_B +\mathbf{c}_N^{\mathsf T}\mathbf{x}_N\\ &=\mathbf{c}_B^{\mathsf T}B^{-1}\mathbf{b} +\left(\mathbf{c}_N^{\mathsf T} -\mathbf{c}_B^{\mathsf T}B^{-1}N\right)\mathbf{x}_N. \end{aligned} \]
The row vector
\[ \bar{\mathbf{c}}_N^{\mathsf T} =\mathbf{c}_N^{\mathsf T}-\mathbf{c}_B^{\mathsf T}B^{-1}N \]
contains the reduced costs. For this maximization convention, a positive reduced cost identifies a nonbasic variable that can initially improve the objective. If every reduced cost is nonpositive, the current basic feasible solution is optimal.
Choosing the Leaving Variable
Suppose nonbasic variable \(x_j\) enters the basis and is increased by \(\theta\ge0\). Let \(\mathbf{u}=B^{-1}\mathbf{a}_j\), where \(\mathbf{a}_j\) is its column. Then
\[ \mathbf{x}_B(\theta)=B^{-1}\mathbf{b}-\theta\mathbf{u}. \]
Feasibility requires every component to remain nonnegative. Therefore
\[ \theta^* =\min_{i:u_i>0}\frac{(B^{-1}\mathbf{b})_i}{u_i}. \]
The minimizing basic variable reaches zero and leaves the basis. If no component of \(\mathbf{u}\) is positive, \(x_j\) can increase indefinitely while preserving feasibility; a positive reduced cost then certifies that the objective is unbounded above.
Simplex Steps for the Example
Start with \(s_1=4\) and \(s_2=5\). Variable \(x_1\) has positive objective coefficient and may enter. Its column is \((1,2)^{\mathsf T}\), so the ratio test gives
\[ \min\left\{\frac{4}{1},\frac{5}{2}\right\}=\frac{5}{2}. \]
Thus \(s_2\) leaves and the next vertex is \((x_1,x_2)=(2.5,0)\), with objective value \(7.5\). Along the now active second constraint,
\[ 2x_1+x_2=5 \quad\Longrightarrow\quad x_1=\frac{5-x_2}{2}. \]
Substitution into the objective gives
\[ 3x_1+2x_2 =\frac{3}{2}(5-x_2)+2x_2 =7.5+0.5x_2. \]
Increasing \(x_2\) therefore improves the objective until the first constraint also becomes active. Solving \(x_1+x_2=4\) together with \(2x_1+x_2=5\) gives \((x_1,x_2)=(1,3)\), matching the geometric solution.
Finding an Initial Basis: Phase I
Slack variables provide an obvious initial basis only when the resulting right-hand side is nonnegative. Equality constraints and surplus variables often do not. The two-phase simplex method resolves this by introducing nonnegative artificial variables and solving an auxiliary problem.
- Add artificial variables where necessary to construct an initial basis.
- Minimize the sum of the artificial variables in Phase I.
- If the minimum is positive, the original constraints are infeasible.
- If the minimum is zero, remove the artificial variables and optimize the original objective in Phase II.
Artificial variables are an algorithmic device, not part of the original model. A zero Phase-I optimum proves that they can all vanish simultaneously.
Duality
For the primal inequality form
\[ \begin{aligned} \operatorname{maximize}\quad & \mathbf{c}^{\mathsf T}\mathbf{x}\\ \operatorname{subject\ to}\quad & A\mathbf{x}\le\mathbf{b},\\ & \mathbf{x}\ge\mathbf{0}, \end{aligned} \]
the dual problem is
\[ \begin{aligned} \operatorname{minimize}\quad & \mathbf{b}^{\mathsf T}\mathbf{y}\\ \operatorname{subject\ to}\quad & A^{\mathsf T}\mathbf{y}\ge\mathbf{c},\\ & \mathbf{y}\ge\mathbf{0}. \end{aligned} \]
Weak Duality
Let \(\mathbf{x}\) be primal feasible and \(\mathbf{y}\) be dual feasible. Nonnegativity and the two systems of inequalities imply
\[ \mathbf{c}^{\mathsf T}\mathbf{x} \le\mathbf{y}^{\mathsf T}A\mathbf{x} \le\mathbf{y}^{\mathsf T}\mathbf{b} =\mathbf{b}^{\mathsf T}\mathbf{y}. \]
Every dual feasible value is therefore an upper bound on every primal feasible value. If a primal and dual feasible pair has equal objective values, both solutions are optimal.
The Dual of the Example
The dual of the production problem is
\[ \begin{aligned} \operatorname{minimize}\quad & 4y_1+5y_2\\ \operatorname{subject\ to}\quad & y_1+2y_2\ge3,\\ & y_1+y_2\ge2,\\ & y_1,y_2\ge0. \end{aligned} \]
The dual point \((y_1,y_2)=(1,1)\) is feasible and has value \(4+5=9\). Since the primal point \((x_1,x_2)=(1,3)\) also has value \(9\), weak duality already proves that both are optimal. Strong duality states that if either problem has a finite optimum, then the other also has an optimum and their optimal values are equal.
Complementary Slackness
At a primal-dual optimum,
\[ y_i\left(b_i-\mathbf{a}_i^{\mathsf T}\mathbf{x}\right)=0, \qquad x_j\left((A^{\mathsf T}\mathbf{y})_j-c_j\right)=0. \]
A positive dual variable requires the corresponding primal constraint to be tight. A positive primal variable requires its dual constraint to be tight. Economically, dual variables act as marginal values or shadow prices for the constrained resources.
Possible Outcomes
A linear program has three principal statuses:
- Optimal: the feasible set is nonempty and the objective attains a finite best value.
- Infeasible: no point satisfies all constraints simultaneously.
- Unbounded: feasible points exist and the objective can improve without limit.
An unbounded feasible set does not necessarily imply an unbounded objective. The objective may be constant or may attain a finite optimum on an unbounded polyhedron. Unboundedness is always a statement about a feasible improving direction, not merely about the shape of the feasible set.
Degeneracy and Cycling
If the ratio test returns \(\theta^*=0\), the basis changes without moving to a different point. This is a degenerate pivot. Degeneracy is common and usually harmless, but an unfortunate sequence of pivot choices can cycle through previously visited bases. Bland's rule prevents cycling by consistently selecting the eligible entering and leaving variables with the smallest indices.
Numerical Practice
The formulas use \(B^{-1}\) to explain the algebra, but implementations should not form the inverse explicitly. They solve systems with \(B\), maintaining a factorization as the basis changes. Practical solvers also apply presolve reductions, scaling, bound propagation, sparse matrix methods, anti-degeneracy rules, and carefully chosen feasibility and optimality tolerances.
Interior-point methods provide another polynomial-time approach and are often preferable for very large sparse problems. The simplex method remains important because it exploits warm starts well, returns an explicit basis, and often performs efficiently in practice.
Summary
- A linear program optimizes a linear functional over a polyhedron.
- Linearity makes the feasible set convex and places an optimum, when appropriate, on an exposed face.
- Slack, surplus, shifted, and split variables convert general models into equality standard form.
- Basic feasible solutions give the algebraic representation of vertices.
- The simplex method moves between bases using reduced costs and the ratio test.
- Duality provides bounds, optimality certificates, and an interpretation of resource values.
References
- [Dantzig1963]George B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.
- [Chvatal1983]Vaclav Chvatal, Linear Programming, W. H. Freeman, 1983.
- [Schrijver1986]Alexander Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.