24.05 Integer solutions to linear programming applications (Extended)

In the previous lesson, we introduced linear programming problems (LPP) which involved finding the optimal solution to an objective function, while keeping within the feasible region.

In practice, our constraint variables are often in terms of integer quantities—they might be the number of employees, the amount of stock at a store, and so on. Non-integer solutions to a linear programming problem are no longer viable for this type of problem.

Simply rounding our values to the nearest integer will not always work. Sometimes we can "exit" the feasible region, or "move" the solution in a direction that makes the resulting point suboptimal.

To overcome this, we need to check all the possible integer solutions that could optimise the feasible region.

Practice question

question 1

 

Worked example

Example 1

Consider the recycling company example that we visited in previous lessons.

It was fortunate that the optimal solution to the problem had integer values at the point $\left(8,3\right)$(8,3). We found that to maximise the waste capacity, the company should buy $8$8 Bin-it bins and $3$3 Fill-it-up bins, giving a total capacity of $100$100 m³.

Let's reformulate the question as below:

Imagine a recycling company that has two types of waste bins available for purchase. The Bin-it bin costs $\$100$$100 each and the Fill-it-up bin costs twice as much, and the amount available for purchases has to be no more than $\$1450$$1450 (which is more than before).

The Bin-it bins take up $6$6 m² of factory yard space and can hold $8$8 m³ of recyclable waste. The more expensive bins take up $8$8 m² of space but can hold $12$12 m³ of waste. The yard is fairly small, confined to $72$72 m² of useable area. How many of each bin type should you buy to maximise the total recycling storage?

Think: We can set up the constraint variables, inequalities and objective functions exactly as we did previously. The only difference is that we now have a maximum budget of $\$1450$$1450. This will mean that the graph of the feasible region will be slightly different.

Do: Let $x$x be the number of Bin-it bins, and $y$y be the number of Fill-it-up bins. The constraints are given below.

$100x+200y\le1450$100x+200y≤1450	(1)
$6x+8y\le72$6x+8y≤72	(2)
$x\ge0$x≥0	(3)
$y\ge0$y≥0	(4)

The objective function is:

$S=8x+12y$S=8x+12y

The next step is to draw the feasible region and identify all of the corner points, which has been given below. The corner points are $\left(0,7.25\right)$(0,7.25), $\left(7,3.75\right)$(7,3.75), $\left(12,0\right)$(12,0) and the origin.

So far finding the integer solution(s) to a linear programming problem is the same as before. We know that in a typical linear programming problem, the optimal solution is at the corner points (corner point principle). However in this case, some of the corner points don't have integer solutions.

When the corner points don't have integer solutions, we want to check all of the integer solutions "near" those corners. We can think of this as a generalisation of the corner point principle. In the special case that the corner points have integer solutions, then the nearest integer solutions are the corner points themselves, and so we check those.

The "nearest" integer solutions around each of the corner points are given below. Notice that we've omitted the corner point at the origin, since after all, having zero bins would mean there would be zero waste capacity!

A list of the possible integer solutions, and the total waste capacity $S$S for each possible solution is given below.

Integer solution	Substitute into objective function	Total storage (m3)
$\left(0,7\right)$(0,7)	$S=8\left(0\right)+12\left(7\right)$S=8(0)+12(7)	$84$84
$\left(6,4\right)$(6,4)	$S=8\left(6\right)+12\left(4\right)$S=8(6)+12(4)	$96$96
$\left(7,3\right)$(7,3)	$S=8\left(7\right)+12\left(3\right)$S=8(7)+12(3)	$92$92
$\left(8,3\right)$(8,3)	$S=8\left(8\right)+12\left(3\right)$S=8(8)+12(3)	$100$100
$\left(12,0\right)$(12,0)	$S=8\left(12\right)+12\left(0\right)$S=8(12)+12(0)	$96$96

The optimal integer solution occurs at the point $\left(8,3\right)$(8,3). This means we should buy $8$8 Bin-it bins and $3$3 Fill-it-up bins so that we maximise the total waste capacity, which is $100$100 m³.

Reflect: As suggested before, rounding the values at the corner point will not give the optimal integer solution. The corner point $\left(7,3.75\right)$(7,3.75) rounds to $\left(7,4\right)$(7,4) and lies outside of the feasible region.

Even rounding down gives the suboptimal solution of $\left(7,3\right)$(7,3).

Note that we can still use the the sliding line method introduced in the previous lesson. To apply the sliding line method for integer solutions, we plot the line for a fixed $S$S as before, and "slide" the line until it hits the last integer solution at $\left(8,3\right)$(8,3).

Practice questions

question 2

question 3