Linear Programming - Feasible Regions
Continuing with our example, we recall the question as:
Imagine a recycling company that needs to buy two types of waste bins. The 'Bin-it' bin costs $$100$100 each but 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 square metres of factory yard space and can hold $8$8 cubic metres of recyclable waste. The more expensive bins take up $8$8 square metres of space but can hold $12$12 cubic metres of waste. The yard is fairly small, confined to $72$72 square metres of useable area. How many of each bin type should you buy to maximise the total recycling storage?
We defined the variables as:
Let $x$x be the number of Bin-it bins
Let $y$y be the number of Fill-it-up bins
We determined the constraints as:
| $100x+200y\le1400$100x+200y≤1400 | (1) |
|---|---|
| $6x+8y\le72$6x+8y≤72 | (2) |
| $x\ge0$x≥0 | (3) |
| $y\ge0$y≥0 | (4) |
We determined the objective function as:
$S=8x+12y$S=8x+12y
Now we need to determine the feasible region:
5. The Feasible Region
Our next task is to identify the feasible region. In this instance this a region in the first quadrant that contains $\left(x,y\right)$(x,y) points that satisfy ALL of our inequalities in the constraints table. To do this we first draw the straight line borders of the feasible region defined by the four equations corresponding to these inequalities. Namely $100x+200y=1400$100x+200y=1400, $6x+8y=72$6x+8y=72, $x=0$x=0 and $y=0$y=0.
The first boundary line $100x+200y=1400$100x+200y=1400 has a $y$y intercept of $7$7 and an $x$x intercept of $14$14. The second boundary line $6x+8y=72$6x+8y=72 has a y intercept of $12$12 and an $x$x intercept of $9$9.
The feasible region is then shown as the area bounded by these lines and the x and y intercepts as shown in the diagram. Note that anything outside the feasible region has been shaded out.
You can check that any point $\left(x,y\right)$(x,y) inside or on the boundary of the feasible region will satisfy all constraints.
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.
Since the first of these equations can be written $x+2y=14$x+2y=14, we know that $x=14-2y$x=14−2y.
Substituting this into the second equation shows that, at the intersection, $6\left(14-2y\right)+8y=72$6(14−2y)+8y=72.
By expanding $84-12y+8y=72$84−12y+8y=72 and thus $4y=12$4y=12 and $y=3$y=3. So $x+6=14$x+6=14 and hence $x=8$x=8.
You can check that $\left(8,3\right)$(8,3) satisfies both equations.
6. Determining the optimal solution.
Now it can be shown that the optimal solution must occur at one of the four corner points of the feasible region.
Of course we can immediately rule out the point $\left(0,0\right)$(0,0), so the best solution - the one that maximises the total recycling storage - will be found at either $\left(0,7\right)$(0,7), $\left(8,3\right)$(8,3)or $\left(12,0\right)$(12,0).
That is the best solution will be either $7$7 Fill-it-up bins only, $8$8 Bin-it bins and $3$3 Fill-it-up bins or $12$12 Bin-it bins only.
All we need do is to substitute these quantities into the objective function as shown in the following table:
| Corner Point | Substitute into Objective Function | Total Storage |
|---|---|---|
| $\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 |
Clearly the best solution is found by buying $8$8 Bin-it bins and $3$3 Fill-it-up bins, storing a total $100$100 cubic metres of recycling material.
The cost of buying these bins is $100\left(8\right)+200\left(3\right)=1400$100(8)+200(3)=1400 dollars.
The graphical method outlined can only be used when there are two variables.