A precise definition, three forms, one toy problem.
Chapter: 0 — LP theory · lesson id lp-what · theory lesson
Optimisation is everywhere: schedule a fleet of trucks, blend petroleum, dose chemotherapy, route data through a network. The trick that makes a particular slice of these problems tractable is $linearity$. If the objective and every constraint are linear in the decisions, we have a $linear\ program$, and we get an elegant theory and decades of polished algorithms in return.
Definition (Linear program (standard form)). A linear program in standard form is the problem $$\min_{x \in \mathbb{R}^n} ; c^{\top} x \quad \text{subject to} \quad A x = b, ; x \geq 0,$$ where $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$ are given. The feasible set ${x \in \mathbb{R}^n : Ax = b, ; x \geq 0}$ is the $feasible\ region$. A point in it is $feasible$; a point achieving the minimum is $optimal$.
There is nothing sacred about standard form. Real LPs come with inequality constraints, free variables, mixed signs, and the optimisation sense flips between $\min$ and $\max$. Every such variant rewrites into the form above:
A $\leq$ inequality $a^{\top} x \leq \beta$ becomes equality $a^{\top} x + s = \beta$ by introducing a $slack\ variable$ $s \geq 0$. A free variable $x \in \mathbb{R}$ becomes $x = x^{+} - x^{-}$ with $x^{\pm} \geq 0$. A maximisation $\max c^{\top} x$ becomes $-\min (-c)^{\top} x$. The transformations are routine; do not let "standard form" make you uneasy.
Definition (Canonical form). It is often more convenient to work with $$\min_{x \geq 0} c^{\top} x \quad \text{subject to} \quad A x \geq b.$$ This is called $canonical\ form$. Standard and canonical forms are equivalent up to slack variables and sign flips.
You can make two products. Each unit of product 1 needs $1$ hour of labour and $2$ units of raw material; each unit of product 2 needs $3$ hours and $1$ unit of material. You have $12$ hours and $8$ units of material. Product 1 sells for $$3$ per unit, product 2 for $$5$. How much of each should you make?
$$ \begin{aligned} \max ; & 3 x_{1} + 5 x_{2} \ \text{s.t.} ; & x_{1} + 3 x_{2} \leq 12 \ & 2 x_{1} + x_{2} \leq 8 \ & x_{1}, x_{2} \geq 0 \end{aligned} $$
Every term in every inequality is either a constant or a constant times a decision variable. Same for the objective. $Linear$ programs.
[feasible-region diagram: Feasible region of the toy LP: the polygon bounded by the labour and material constraints in the first quadrant.]
The shaded polygon is the feasible region. The dashed lines are the objective contours; they are parallel because the objective is linear. The optimum sits where the contour with the highest value still touches the polygon, which (we will prove next lesson) is always at a $corner$.
Quick check. Which of the following is not a linear program?
When you hand an LP to a solver, exactly one of three things happens:
$1.\ Optimal$: the feasible region is non-empty and the objective is bounded; the solver returns the optimal value and an optimal $x^{*}$.
$2.\ Infeasible$: the feasible region is empty. The constraints contradict each other. Example: $x \geq 5$ and $x \leq 2$.
$3.\ Unbounded$: the feasible region is non-empty but the objective can be made arbitrarily small (for $\min$) or large (for $\max$). Example: $\max\ x$ with no upper bound.
Every solver you will ever use must report one of these three statuses. The hands-on course covers reading them in detail; for now just know there are three.
Quick check. You have the LP $\max\ x_{1} + x_{2}$ subject to $x_{1} - x_{2} \leq 0$ and $x_{1}, x_{2} \geq 0$. The solver reports:
Recap.
Read this through MCP: read with path: "lessons/lp-what", or resource hlpl://lessons/lp-what.