CG6–CG8 - Linear programming

You already know

A linear inequality in two variables describes a half-plane. Its boundary is a straight line. Use a solid boundary for $\le$ or $\ge$, a dashed boundary for $<$ or $>$, and a test point to select the correct side.

Constraint

A constraint is a condition restricting the allowed values of the variables. A linear constraint uses only constant multiples of the variables and a constant, as in $2x+y\le8$. The condition $xy\le8$ is not linear.

Worked example 1: limited resources

Question. Write the constraints for the workshop described above.

Plan. Add the time used by the two fabrics for each process, compare with the available time, and include non-negative lengths.

Why not use $x+y\le8$ for both processes? The two products use different amounts of each resource, so the coefficients must reflect those amounts.

Answer. $2x+y\le8$, $x+2y\le8$, $x\ge0$, $y\ge0$.

Check. Making $x=2$, $y=2$ uses $6$ minutes of each process, so it satisfies every constraint.

Worked example 2: a minimum requirement

Question. A production plan requires at least $8$ finishing minutes but allows no more than $8$ cutting minutes. Write its constraints for the same two fabrics.

Plan. Keep the same time expressions and change only the direction of the finishing inequality.

Why keep equality in both? Exactly $8$ minutes meets both “at least” and “no more than”.

Answer. $2x+y\le8$, $x+2y\ge8$, $x\ge0$, $y\ge0$.

Check. $x=0$, $y=4$ uses $4$ cutting minutes and $8$ finishing minutes, so it is allowed.

Watch out

Wrong: “at least $8$” becomes $x+2y>8$. That excludes exactly $8$. Right: $x+2y\ge8$. “More than $8$” would use the strict inequality.

Feasible point and feasible region

A feasible point satisfies every constraint. The feasible region is the set of all such points. A vertex is a corner formed where boundary lines meet, provided their intersection satisfies all the other constraints too. An intersection outside the common region is not one of its vertices.

Worked example 3: the workshop's feasible polygon

Question. Find the vertices of the region $2x+y\le8$, $x+2y\le8$, $x\ge0$, $y\ge0$.

Plan. Find the permitted axis endpoints, then solve the two sloping boundaries simultaneously.

The origin also satisfies every inequality, giving four vertices in all. Draw the boundary lines through their intercepts and keep the common portion in the first quadrant.

Why check both inequalities on an axis? The tighter constraint, not the first one you happen to read, fixes the endpoint.

Answer. $(0, 0)$, $(4, 0)$, $(\frac83, \frac83)$, $(0, 4)$.

Check. At the non-axis corner, $2(\frac83)+\frac83=8$ and $\frac83+2(\frac83)=8$. The first panel below shows the resulting quadrilateral.

Worked example 4: a moved constraint

Question. Find the vertices for $2x+y\le8$, $x+2y\le10$, $x\ge0$, $y\ge0$.

Plan. Recheck the axes, then solve the changed pair of boundary equations.

Why not keep the old corner? A point at the intersection must satisfy the new equality as well as the unchanged one.

Answer. $(0, 0)$, $(4, 0)$, $(2, 4)$, $(0, 5)$.

Check. $(2, 4)$ gives $2(2)+4=8$ and $2+2(4)=10$, and both coordinates are non-negative.

Watch out

Wrong: include $(0, 8)$ as a vertex in Worked example 3 because it lies on $2x+y=8$. It violates $x+2y\le8$, giving $16>8$. Every proposed vertex must pass every constraint.

Objective function

An objective function is the quantity to be maximised or minimised, written in terms of the decision variables. If the profits per metre are £$3$ for A and £$2$ for B, the profit in pounds is $P=3x+2y$. The constraints restrict production; they do not themselves state its value.