Linear Programming, Practice Questions

Turn each resource limit into an inequality, and remember that quantities cannot be negative.

These four inequalities together define the feasible region.

The corners are where the boundary lines meet. Start with the axes.

Origin gives $(0,0)$. On the x-axis $(y=0)$, the tighter limit is $x+y\le 10$, giving $(10,0)$, check $x+2y=10\le 14$.

On the y-axis $(x=0)$, the tighter limit is $x+2y\le 14$, giving $(0,7)$, check $x+y=7\le 10$.

The last corner is where the two sloping lines cross. Subtract $x+y=10$ from $x+2y=14$:

The vertices are $(0,0)$, $(10,0)$, $(6,4)$ and $(0,7)$.

For a linear objective, the maximum lies at a vertex, so test each corner from Question 2.

The largest value is $34$, at $(6,4)$. So making 6 tables and 4 chairs gives the maximum profit of $34$.

With "greater than or equal" constraints the region is open at the top, but a minimum still sits at a vertex. Find the corners.

On the y-axis the binding line is $2x+y\ge 10$ at $(0,10)$; on the x-axis the binding line is $x+y\ge 8$ at $(8,0)$.

The interior corner is where $x+y=8$ and $2x+y=10$ cross. Subtract: $x=2$, then $y=6$.

The minimum is $18$, at $(2,6)$.

First find the vertices of the region $x+y\le 12$, $y\le 2x$, $x\ge 2$, $y\ge 0$. The line $x+y=12$ meets $y=2x$ where $x+2x=12$, so $x=4,\ y=8$.

The line $y=2x$ meets $x=2$ at $(2,4)$. The line $x+y=12$ meets $x=2$ at $(2,10)$?

Check $y\le 2x=4$: $10>4$, so that point is outside; instead the region is bounded by $x=2$, $y=2x$, $x+y=12$ and $y\ge 0$.

The vertices are $(2,0)$, $(12,0)$, $(4,8)$ and $(2,4)$. Evaluate $E=200x+300y$:

The maximum is $3200$, running 4 small classes and 8 large classes.

You cannot run a fraction of a class, so $x$ and $y$ must be whole numbers; here the optimal vertex $(4,8)$ already has whole-number coordinates, so no adjustment is needed. Testing only the vertices is enough because the objective $E=200x+300y$ is linear: as you move along any edge of the feasible region, $E$ changes steadily and so its largest value on that edge is always at one of its ends.

The greatest value over the whole region therefore occurs at a corner, which is exactly why the vertex method works.