Linear programming and integer decisions

What you’ll learn

• Define variables, constraints and a linear objective.
• Find a feasible region and compare its vertices.
• Check integer feasibility without blindly rounding.

Understand the idea

Define decision variables with their units before writing constraints. Resource limits usually become upper-bound inequalities, minimum requirements become lower bounds, and non-negativity must be stated when negative quantities have no meaning. The objective function expresses the quantity to maximise or minimise.

For two variables, draw the boundary lines and identify their common feasible region. A bounded linear objective achieves an optimum at a feasible vertex, unless an entire feasible edge shares the same optimum value. Solve boundary intersections accurately and substitute every candidate into all constraints. An objective line can also be moved parallel to itself until it last touches the feasible region.

If decisions must be integers, the continuous optimum is only a bound. Rounding its coordinates can violate a constraint or miss a better nearby integer point. Examine feasible integer candidates systematically, using bounds on each variable to keep the search complete.

Key formulae

$$\text{maximise }P=ax+by$$

$$a_ix+b_iy\leq c_i$$

$$x\geq0,\qquad y\geq0$$

$$x,y\in\mathbb Z\quad\text{when whole units are required}$$

Worked example

Maximise $P=5x+4y$ subject to $x+y\leq8$, $2x+y\leq10$, $x\geq0$ and $y\geq0$. Variables may be continuous.

1. The axis vertices are $(0,0)$, $(5,0)$ and $(0,8)$.
2. Solve $x+y=8$ and $2x+y=10$: subtraction gives $x=2$, then $y=6$. This intersection is feasible.
3. Evaluate $P$ at the four vertices: $0,25,32,34$ respectively.
4. The greatest value is 34 at $(2,6)$.

Answer: Maximum $P=34$ at $x=2$, $y=6$.