topic badge
Middle Years

10.05 Integer solutions to linear programming applications

Lesson

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

Identify the integer coordinate pairs that satisfy the following feasible region.

Loading Graph...

 Feasible region

  1. Write each coordinate pair on the same line, separated by commas.

 

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 m3.

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 m2 of factory yard space and can hold $8$8 m3 of recyclable waste. The more expensive bins take up $8$8 m2 of space but can hold $12$12 m3 of waste. The yard is fairly small, confined to $72$72 m2 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+200y1450 (1)

$6x+8y\le72$6x+8y72

(2)
$x\ge0$x0 (3)
$y\ge0$y0 (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.

Feasible region

Graph of the constraint inequalities.

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!

Feasible region

Possible integer solutions.

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 m3.

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).

Feasible region

Graph of the sliding line intercepting $\left(8,3\right)$(8,3).

Practice questions

question 2

A tutoring company offers private tuition for English and Mathematics. An English student takes one tuition which is broken up into two sections that cover each of the modules. The same goes for a Mathematics student, but with a different amount of hours covering each module. The company decides to set a maximum number of hours dedicated to each module according to its relevance in the syllabus.

Let $x$x represent the number of students that take English per week, and let $y$y represent the number of students that take Mathematics per week.

  Module $A$A Module $B$B
English $3$3 hours $1$1 hour
Mathematics $2$2 hours $3.5$3.5 hours
Available time allocated in a week $24$24 hours $14$14 hours
  1. Finish the set of constraint inequalities below:

    1. $x\ge0$x0
    2. $y\ge0$y0
    3. $\editable{}+\editable{}\le24$+24
    4. $\editable{}+\editable{}\le\editable{}$+
  2. Construct the region defined by inequalities 3 and 4 in the first quadrant (shade the required region).

    Loading Graph...

  3. If English tuition is charged at $\$50$$50 per hour and Mathematics is charged at $\$40$$40 per hour, write the objective function that models the weekly profit $z$z.

  4. The region of possible solutions constructed in part (b) is shown in more detail below:

    Loading Graph...

     Feasible region

    Which of the following is a set of integer solutions that could minimise the objective function in part (c)? 

    $\left(0,0\right),\left(2,1\right),\left(3,2\right),\left(6,1\right)$(0,0),(2,1),(3,2),(6,1)

    A

    $\left(0,0\right),\left(7,0\right),\left(5,2\right),\left(3,2\right)$(0,0),(7,0),(5,2),(3,2)

    B

    $\left(2,4\right),\left(7,2\right),\left(6,3\right)$(2,4),(7,2),(6,3)

    C

    $\left(0,4\right),\left(8,0\right),\left(6,2\right)$(0,4),(8,0),(6,2)

    D
  5. Complete the table below to determine the profit corresponding to each possible coordinate pair:

    Possible solutions Profit (dollars)
    $\left(0,4\right)$(0,4) $\editable{}$
    $\left(7,0\right)$(7,0) $\editable{}$
    $\left(6,2\right)$(6,2) $\editable{}$
  6. Complete the following sentences:

    The maximum weekly profit is $\editable{}$ dollars, and occurs at the point $\left(\editable{},\editable{}\right)$(,).

    That is to say, if $\editable{}$ English students and $\editable{}$ Mathematics students enrol then the company achieves their maximum profit.

question 3

Consider the following feasible region.

Loading Graph...

 Feasible region

  1. What are the integer coordinate pairs that satisfy the region?

    Write each coordinate pair on the same line, separated by commas.

  2. Consider the objective function $z=-\frac{x}{3}+\frac{y}{3}+7$z=x3+y3+7.

    What is the integer coordinate pair that maximises the objective function?

What is Mathspace

About Mathspace