Linear programming

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.