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.
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.
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.
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.
The graph of these inequalities looks as follows.
Feasible region
We now want to find corner points of the feasible region. Making use of your CAS calculator speeds up this process.
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.
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.
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
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.
To find the point that maximises (or minimises) the objective function $z=ax+by$z=ax+by:
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+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.
Feasible region
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
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.
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.
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.
The manufacturer is bound by the following constraints:
Express the three constraints as inequalities:
Graph the region defined by the inequalities $x\le150$x≤150, $y\le300$y≤300 and $400x+300y\le120000$400x+300y≤120000 in the first quadrant:
The region of possible solutions that you graphed in part (c) has been sketched more clearly below:
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{}$ |
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)$(,).
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:
Semi-Trailer Truck | Box Truck | |
---|---|---|
Annual maintenance cost |
$\$12500$$12500 | $\$11250$$11250 |
Payload | $20$20 tons | $3$3 tons |
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.
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:
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.