24.04 Application of linear programming (Extended)

So far we've looked at how to construct feasible regions, and objective functions. Typically, the objective function describes some profit (or cost) in terms of the constraint variables, and so it would make sense to maximise (or minimise) the objective function.

The objective function provides a sense of "preference" for the points satisfying the feasible region. We "prefer" the point in the feasible region that maximises (or minimises) the objective function. A problem of this type is called a linear programming problem.

There are two main methods for determining the values in the feasible region that optimise the objective function.

Method 1: Corner point principle

If the boundaries of the feasible region are solid lines, the points in the feasible region that optimise the objective function are always the corner points. 

To find the optimal solution we substitute each of the corner points into the objective function. The corner point that optimises the objective function is the optimal solution.

It's worth mentioning that there are sometimes more than one optimal solutions. It's possible that the family of lines in the sliding line method is parallel to one of the edges of the feasible region. If we slide the line up or down so that it lies on top of this edge, then all the points on this edge maximises or minimises the objective function.

A way of identifying this situation is if two adjacent corner points both optimise the objective function. In this case, all the points along the edge joining the two corner points also optimise the objective function.

Worked example

Example 1

A hotel and conference centre at a holiday destination can cater for a maximum of $540$540 tourists and conference attendees per month but does not open for business in any month in which the number of bookings is less than $300$300. The number of tourist bookings is always at least the number of conference attendees but never more than twice as many.

The profit made per tourist per month is $\$16$$16 while the profit made per conference attendee per month is $\$19$$19. What mix of conference attendees and tourists should the centre aim for to maximise the profit? What is the maximum profit?

Think: Let $c$c be the number of conference attendees and $t$t be the number of tourists. We first want to express the objective function and constraints in terms of $c$c and $t$t. Then we want to use either the sliding line method, or the corner point principle to find the optimal solution.

Do: If $P$P is the total profit, then the objective function can be written as $P=19c+16t$P=19c+16t.

The constraints along with their description are given below.

1. $c+t\le540$c+t≤540 (maximum number of bookings)
2. $c+t\ge300$c+t≥300 (minimum bookings in order to open)
3. $t\ge c$t≥c (the number of tourists is at least the number of conference attendees)
4. $t\le2c$t≤2c (the number of tourists is never more than double the number of conference attendees)
5. $t\ge0$t≥0, $c\ge0$c≥0 (we can never have negative attendees of either kind)

The graph of these inequalities looks as follows.

We now want to find corner points of the feasible region. Making use of your CAS calculator speeds up this process.

1. $t=2c$t=2c and $c+t=540$c+t=540 gives $c=180$c=180 and $t=360$t=360.
2. $t=2c$t=2c and $c+t=300$c+t=300 gives $c=100$c=100 and $t=200$t=200.
3. $t=c$t=c and $c+t=540$c+t=540 gives $c=t=270$c=t=270.
4. $t=c$t=c and $c+t=300$c+t=300 gives $c=t=150$c=t=150.

Now substitute each vertex point into the objective function $P=19c+16t$P=19c+16t and find the maximum value for $P$P.

$19\times180+16\times360$19×180+16×360	$=$=	$9180$9180
$19\times100+16\times200$19×100+16×200	$=$=	$5100$5100
$19\times270+16\times270$19×270+16×270	$=$=	$9450$9450
$19\times150+16\times150$19×150+16×150	$=$=	$5250$5250

 

The maximum profit is $\$9450$$9450 when there are $270$270 conference attendees and $270$270 tourists.

 

Method 2: Sliding line

Usually the objective function will be in the form $z=ax+by$z=ax+by. In any case, we can always make $y$y the subject of the equation, which gives us:

$y=-\frac{a}{b}x+\frac{z}{b}$y=−ab​x+zb​

If we make $z$z a constant, then the equation above describes a line with gradient $-\frac{a}{b}$−ab​. For a different value of $z$z, we create a new line, one with the same gradient and a new $y$y-intercept. If we consider all the values of $z$z, then we create a family of lines that are all parallel with the same gradient of $-\frac{a}{b}$−ab​ and each with a different $y$y-intercept depending on the value of $z$z.

We can think of the family of lines as a single line that "slides" up and down. As it slides, the value of $z$z changes.

Now let's consider this family of lines over a feasible region as shown below. We can see that some of these lines pass through the feasible region, while others stay clear of it. If we slide our line up or down so that it increases (or decreases) $z$z, then the point just before it leaves the feasible region will be the point in the feasible region that maximises (or minimises) the objective function.

If we slide the line up and down, we can see two points where the line still intercepts the feasible region. One point will maximise the objective function, while the other minimises the objective function. This method we described above is called the sliding line method.

Use the following applet to create your own feasible region, and objective function. Notice how the value of the objective function changes according to the position of line.

 

 

 

Worked example

example 2

Consider the recycling company example from the previous lesson.

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 $\$1400$$1400. 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: As we did in the previous section, let $x$x be the number of Bin-it bins and $y$y be the number of Fill-it-up bins. The constraints are then:

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

And the objective function $S$S is:

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

The next task is to identify which of the two methods we want to use. Let's use the sliding line method.

Do: To use the sliding line method, we want to draw the feasible region satisfying the constraint inequalities. This means we construct the boundary lines as usual, and indicate the feasible region with a key as shown below.

The corner $\left(8,3\right)$(8,3) is found as the point of intersection of the lines $100x+200y=1400$100x+200y=1400 and $6x+8y=72$6x+8y=72. The remaining corner points are the $x$x and $y$y-intercepts of the boundary lines.

To use the sliding line method, we rewrite the objective function so $y$y is the subject. This gives us the equation:

$y=-\frac{2}{3}x+\frac{S}{12}$y=−23​x+S12​

If we fix $S$S, we can see that the gradient of the equation is $-\frac{2}{3}$−23​. We then draw a line with a gradient of $-\frac{2}{3}$−23​ that goes through the feasible region. Since $\frac{S}{12}$S12​ is the $y$y-intercept, as we slide the line up, this will increase the value of $S$S. We slide the line up until it's just about to exit the feasible region. At this stage, the line intercepts the feasible region at the corner point $\left(8,3\right)$(8,3).

So we say that $\left(8,3\right)$(8,3) is the optimal solution. The total recycling storage can be found by evaluating the objective function at this point:

$S$S	$=$=	$8x+12y$8x+12y	Writing the objective function
	$=$=	$8\times8+12\times3$8×8+12×3	Substituting the point $\left(8,3\right)$(8,3)
	$=$=	$100$100 m3	Simplifying

 

This means that to maximise the total recycling storage, $8$8 Bin-it bins and $3$3 Fill-it-up bins should be purchased. This will give a maximum recycling storage of $100$100 m³.

Reflect: We could alternatively use the corner principle method instead. It would save us from having to draw the feasible region and the sliding line, but it would mean that we would have to substitute each of the corner points into the objective as shown below.

Corner Point	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(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

We can see that among the corner points, $\left(8,3\right)$(8,3) maximises the total storage.

Practice questions

Question 1

Question 2

Question 3