topic badge
Middle Years

10.04 Application of linear programming

Lesson

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

Corner point principle

The optimal solution of a linear programming problem will be found at a corner point (vertex)
of the feasible region.

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+t540 (maximum number of bookings)
  2. $c+t\ge300$c+t300 (minimum bookings in order to open)
  3. $t\ge c$tc (the number of tourists is at least the number of conference attendees)
  4. $t\le2c$t2c (the number of tourists is never more than double the number of conference attendees)
  5. $t\ge0$t0, $c\ge0$c0 (we can never have negative attendees of either kind)

The graph of these inequalities looks as follows.

Feasible region

The graph of the constraints.

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=abx+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.

The family of lines $y=-\frac{a}{b}x+\frac{z}{b}$y=abx+zb, for different values 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.

Feasible region

Family of lines over the feasible region.

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.

 

Summary - sliding line method

To find the point that maximises (or minimises) the objective function $z=ax+by$z=ax+by:

  1. Express the objective function with $y$y as the subject.
  2. Fix $z$z, and draw a line that has the same gradient ($-\frac{a}{b}$ab) that passes through the feasible region.
  3. Slide the line in the direction (up or down) so that it either maximises or minimises the value of $z$z.
  4. Determine the point(s) where the line intercepts the feasible region just before it exits the feasible region. (This is typically a corner point)
  5. Also state the maximum (or minimum) value of the objective function by substituting the point(s) found in part 4 into the objective function.

 

 

Worked example

example 2

Consider the recycling company example from Constraints and objective functions 14.03.

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 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: 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+200y1400 (1)
$6x+8y\le72$6x+8y72 (2)
$x\ge0$x0 (3)
$y\ge0$y0 (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.

Feasible region

A graph of the constraint inequalities.

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=23x+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).

Feasible region

Sliding line method.

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

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

A television manufacturer makes rear-projection and plasma televisions. The profit per unit is $\$75$$75 for the rear-projection televisions and $\$150$$150 for the plasma televisions.

  1. Let $x$x be the number of rear-projection televisions sold in a month and $y$y be the number of plasma televisions sold in a month. Write the objective function that models the total monthly profit $z$z.

  2. The manufacturer is bound by the following constraints:

    1. Equipment in the factory allows for making a maximum of $150$150 rear-projection televisions in one month.
    2. Equipment in the factory allows for making a maximum of $300$300 plasma televisions in one month.
    3. The cost to manufacture per unit is $\$400$$400 for the rear-projection televisions, and $\$300$$300 for the plasma televisions. Total monthly costs cannot exceed $\$120000$$120000.

    Express the three constraints as inequalities:

    1. $\editable{}\le\editable{}$
    2. $\editable{}\le\editable{}$
    3. $\editable{}\le\editable{}$
  3. Graph the region defined by the inequalities $x\le150$x150, $y\le300$y300 and $400x+300y\le120000$400x+300y120000 in the first quadrant:

    Loading Graph...

  4. The region of possible solutions that you graphed in part (c) has been sketched more clearly below:

    Loading Graph...

    Evaluate the objective function for total monthly profit at each of the corners of the region. Give your answer to the nearest dollar.

    Points Total Monthly Profit (dollars)
    $\left(0,0\right)$(0,0) $\editable{}$
    $\left(0,300\right)$(0,300) $\editable{}$
    $\left(75,300\right)$(75,300) $\editable{}$
    $\left(150,200\right)$(150,200) $\editable{}$
    $\left(150,0\right)$(150,0) $\editable{}$
  5. Use the region of possible solutions graphed above to help you determine the maximum monthly profit and the coordinates of the point it occurs on:

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

Question 2

Oliver is opening a new cross-state shipping company. He has the option to buy semi-trailer trucks or box trucks. To help in his decision, Oliver analyzed the following data:

  • The annual maintenance cost should not exceed $\$562500$$562500.
  • The total payload had to be at least $300$300 tons.
  • Only $30$30 semi-trailer trucks are available.
  Semi-Trailer Truck Box Truck

Annual maintenance cost

$\$12500$$12500 $\$11250$$11250
Payload $20$20 tons $3$3 tons
  1. The average profit made by a semi-trailer truck is $\$12000$$12000 per year and the average profit made by a box trucks is $\$13000$$13000 per year. Find how many of each type of truck Oliver has to buy in order to maximize his annual profit.

    The maximum annual profit is $\editable{}$ dollars, if Oliver buys $\editable{}$ semi-trailer trucks and $\editable{}$ box trucks.

Question 3

Food and clothing are shipped to survivors of a hurricane. Each box of food will feed $4$4 people, while each box of clothing will help $6$6 people. Each $1.0$1.0 m3 box of food weighs $5$5 kg and each $0.6$0.6 m3 box of clothes weighs $8$8 kg. The planes transporting food and clothing are bound by the following constraints:

  • The total weight per plane cannot exceed $2000$2000 kg, and the total volume must be less than $300$300 m3.
  1. How many boxes of food and how many boxes of clothing should be sent with each plane shipment to maximize the number of people that are helped?

    $\editable{}$ boxes of food and $\editable{}$ boxes of clothing should be sent to help $\editable{}$ people.

What is Mathspace

About Mathspace