Formulating a linear programming problem

Decision variables: name the unknown quantities. For the dealer, x tables and y chairs.

Non-negative restrictions: counts cannot be negative, so x ≥ 0 and y ≥ 0. These belong to every problem and are easy to forget.

Constraints: each limit in the story becomes a linear inequality. Money: 2500x + 500y ≤ 50000, which simplifies to 5x + y ≤ 100. Storage: x + y ≤ 60.

Objective function: the quantity to be optimised, written Z = ax + by with constants a and b. For the dealer, Z = 250x + 75y, to be maximised.

The full problem: maximise Z = 250x + 75y when x ≥ 0, y ≥ 0, x + y ≤ 60 and 5x + y ≤ 100.

A linear programming problem, then, asks for the optimal (maximum or minimum) value of a linear objective function over all plans that obey a list of linear inequalities with no variable negative. "Linear" says every relation is of the first degree; "programming" means choosing a plan of action.

Words to signs: "at most", "cannot exceed", "no more than" give ≤; "at least", "not less than" give ≥.