---
tag: 32CP806EHX
kind: definition
name: Linear programming
msc: [90C05, 52B55]
defines: VNMXB0J2KA
uses: [0VD9ZSWWJG]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_programming
---

## Definition

Let $A$ be a real $m \times n$ [[matrix|0VD9ZSWWJG]], let $b \in \R^m$ and let $c \in \R^n$.
For vectors $u, w \in \R^m$, write $u \le w$ when $u_i \le w_i$ for every $i$.
The *linear program* given by $(A, b, c)$ is the problem
$$\text{maximize } c^T x \quad \text{subject to} \quad A x \le b, \quad x \in \R^n.$$
A point $x$ with $A x \le b$ is a *feasible solution*, and the set of them is the *feasible region*.
A feasible solution $x^*$ is *optimal* if $c^T x^* \ge c^T x$ for every feasible solution $x$, and then $c^T x^*$ is the *optimal value*.
*Linear programming* is the study and solution of linear programs.

## Remarks

Example: maximize $x + y$ subject to $x \ge 0$, $y \ge 0$, $x + 2y \le 4$ and $3x + y \le 6$.
The feasible region is the quadrilateral with vertices $(0,0)$, $(2,0)$, $(8/5, 6/5)$ and $(0,2)$.
The objective takes the values $0$, $2$, $14/5$ and $2$ at these vertices, so the optimal value is $14/5$, attained at $(8/5, 6/5)$.

Non-example: maximizing $x + y$ subject to $x^2 + y^2 \le 1$ is not a linear program, because the constraint is not a linear inequality.

Every linear program is of exactly one of three kinds: infeasible, unbounded (the objective is not bounded above on the feasible region), or with an optimal solution.
Other standard forms, such as maximizing $c^T x$ subject to $A x = b$ and $x \ge 0$, are equivalent to this one after adding slack variables or splitting free variables.
The dual of the program above is to minimize $b^T y$ subject to $A^T y = c$ and $y \ge 0$.
If one of the two programs has an optimal solution, so does the other, with the same optimal value.