Introduction to Linear Programming

A linear program (LP) is the problem of maximizing or minimizing a linear function of several variables, subject to a collection of linear inequality (or equality) constraints.

Every LP has three ingredients:

1. Decision variables -- the unknowns we control, usually written $x_1, x_2, \ldots, x_n$.
2. Objective function -- the linear quantity we wish to maximize or minimize, of the form $z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$.
3. Constraints -- linear inequalities (or equalities) the variables must satisfy, along with sign restrictions such as $x_i \ge 0$.

A complete LP is written like this:

$$\begin{aligned}\text{maximize} \quad & z = 3x_1 + 5x_2 \\ \text{subject to} \quad & x_1 + 2x_2 \le 8 \\ & 4x_1 + 3x_2 \le 12 \\ & x_1,\, x_2 \ge 0. \end{aligned}$$

Here the decision variables are $x_1$ and $x_2$, the objective coefficients are $3$ and $5$, the two functional constraints limit linear combinations of the variables, and the sign restrictions $x_1, x_2 \ge 0$ keep the variables nonnegative.

A solution to the LP is any assignment of values to the decision variables. The goal is to find a solution that satisfies all constraints and makes the objective as large (or as small) as possible.