the Simplex algorithm 2: recognizing the Optimal Shortcut
Generally, I’m not a fan of shortcuts. When you get in the habit of skipping steps it’s easy to make inaccurate assumptions that result in incorrect solutions. At the same time, I believe that if you observe a systematic way to improve efficiency then you ought to share it. That’s what “recognizing the Optimal Shortcut“ is about: recognizing a general case where the Simplex algorithm can be avoided when solving maximization problems. Did I mention that my favourite kind of computer science can be practiced without a computer? Sometimes the best improvements in algorithm efficiency can be recognized with nothing other than a plain, old-fashioned, human brain.
To illustrate these optimal conditions I’ll use a concrete example. ;)
Imagine a landscaper whose business is focused on building breakwalls along the shorelines of Lake Erie and Lake Ontario. These structures help to protect buildings on the shore from storms and soil erosion. This landscaper wants to know whether it’s worth expanding the area served to other Great Lakes (e.g., Lake Huron). Given existing constraints on resources, what’s the maximum profit that can be expected? In other words, if the landscaper used up all resources in the most efficient way possible, what would the maximum profit be? We’ll start by assigning variables.
Let x1, x2, and x3
represent the different landscaping services offered.
We're looking to determine the optimal combination of
services to offer per week.
Each service must pass through three stages for completion.
There are constraints on each stage for the maximum number of
labour hours per week.
x1 = the number of hybrid breakwall units constructed
x2 = the number of revetment breakwall units constructed
x3 = the number of simple breakwall units constructed
Here’s our profit statement (objective function):
P = $10000x1 + $9000x2 + $8000x3
The coefficient for each variable represents the profit made on the service offered (per unit). Here are the labour constraints for each service offered.
x1: every hybrid breakwall unit requires 7 hours of digging, 6 hours of fitting, and 7 labour hours for setting the final product.
x2: every revetment breakwall unit requires 6 hours of digging, 7 hours of fitting, and 8 hours for setting the final product.
x3: every simple breakwall unit requires 7 hours of digging, 8 hours of fitting, and 9 hours for setting the final product.
Each week, the landscaper has limitations on the number of labour hours available per service: a total of 21 hours for digging, 36 hours for fitting, and 42 labour hours for setting the final product. Given all of these constraints, is it possible to obtain an optimal solution without using the Simplex algorithm to pivot through a matrix? Yes!
For the sake of illustration we’ll enter our constraints into a matrix.
| x1 | x2 | x3 | TOTAL | ||
|---|---|---|---|---|---|
| DIGGING | 7 + | 8 + | 7 | <= | 22 |
| FITTING | 6 + | 7 + | 8 | <= | 36 |
| SETTING | 7 + | 8 + | 9 | <= | 42 |
Before we go further, lets do a quick tight-constraint check. Are we required to zero out any variables to meet each constraint? The answer is no. There’s enough room within each constraint to build at least 1 unit for every type of breakwall. This makes our task more difficult: what value do we assign to each variable so we use our resources in the most efficient way? Luckily, our numbers happen to be aligned with an optimal shortcut :)
If we were going to use the Simplex algorithm, we’d first determine the variable with the largest coefficient in our objective function. In this example, it’s x1 (where the coefficient is 10000). Then we’d determine the row to use for pivoting by obtaining a minimum quotient using each constraint’s sum total.
DIGGING constraint total: 22/7 = 3.14…
FITTING constraint total: 36/6 = 6
SETTING constraint total: 42/7 = 6
We can see that the minimum quotient when considering x1 values is in ROW 1, or the first constraint. When we look at the other values in this constraint we see that x1 has the lowest value when compared to those for x2 and x3. This is our optimal shortcut check! What we’ve spotted is that there would only be one pivot for this scenario. The other values in the row we’d choose for pivoting use up just as big a portion of the sum total (or more!). Therefore, things literally can’t get any better for this case. We take that minimum quotient we obtained and substitute its value in for x1. For our breakwall example, we’ll keep the units discrete and aim to build 3 hybrid wall units a week.
P = $10000(3) + $9000(0) + $8000(0) = $30000
This tells our landscaper how much weekly profit could be made if output was maximized given current resource constraints. If the landscaper isn’t reaching maximum output in the existing region of service then it may be worth expanding to other regions.
If you practice the first few steps of the Simplex algorithm enough, you may find that it gets easier to spot when only one pivot would be required.
1) Which variable has the greatest coefficient in the objective function? Focus on that variable!
2) Find the constraint where the value for this variable gives you a minimum quotient when divided into the sum total.
3) Look at this constraint closely! Does your chosen variable have the lowest value? If so, then you’re done! In the objective function, substitute the minimum quotient value in for your chosen variable and you’ll have maximized this function.
Feeling like that went a little too quickly? Try the optimal shortcut check again on the example in my first Simplex article where three variables represent different types of residential construction: condo, townhouse, and detached housing units.
P = $20000x1 + $18000x2 + $24000x3
Because we want to pass the tight-constraint check, we’ll use a somewhat loosened version of this example. Our building contractor is dealing with the following limitations on resources.
| x1 | x2 | x3 | TOTAL | ||
|---|---|---|---|---|---|
| acres | 1 + | 1 + | 2 | <= | 10 |
| capital | 80000 + | 60000 + | 50000 | <= | 120000 |
| labour hours | 3000 + | 2000 + | 1000 | <= | 5000 |
Again, my numbers here are probably off here but we’re exploring how to spot (what I call) the optimal shortcut. In this example, x3 has the greatest coefficient in the objective function so we look at values in this column. When determining the minimum quotient we find the following values:
10/2 = 5
120000/50000 = 2.4
5000/1000 = 5
Therefore, the second constraint has the minimum quotient of 2.4. The lowest value in this constraint corresponds with x3. In other words, x3 has the lowest value in this constraint. It’s impossible to use up less of this constraint, so this is as good as it gets!
We’ll keep our housing units discrete (by rounding down), and substitute the value 2 in for x3 to maximize our objective function:
P = $20000(0) + $18000(0) + $24000(2) = $48000
CONCLUSION
The optimal shortcut can be used in linear maximization problems when the variable with the greatest coefficient in an objective function is the same variable with the lowest value in the constraint with a minimum quotient. This quotient value can be substituted into that variable to maximize the objective function.
You may be wondering, how useful is this optimal shortcut? Well, that depends on how many variables your maximization problem has. As the number of variables increases, the frequency of this optimal shortcut decreases… but that’s another article for another day.