the Simplex algorithm 3: tight constraints, Optimal Shortcut, + Windup by 1
This is the third article in a series that I’m doing on the Simplex algorithm and its use to solve maximization problems. Essentially, I’m looking for maximization scenarios that can be solved without the Simplex algorithm.
We’ll start with a little recap of my first two articles. In “Simplex algorithm 1: recognizing tight constraints“ I used a residential construction example with three types of housing: condos, townhouses, and detached houses. The builder’s resources are particularly limited. How do we recognize that? There are three constraints, and in two of them at least one variable must be zeroed out. More generally, when dealing with constraints in a <= form, we can say a constraint is tight if at least one variable must be zeroed out in order to meet the sum total. In my second Simplex article, “Simplex algorithm 2: recognizing the Optimal Shortcut“, I explore maximization problems where a solution can be obtained with only one pivot (or no pivoting whatsoever). In my third article, the one you’re currently reading, we’ll put these two scenario types together along with an alternative algorithm that I call “Windup by 1“.
Lets return to our first residential construction example, with the original set of tight constraints.
P = $20000x1 + $18000x2 + $24000x3
Each residence type has the following requirements:
$60000x1 + $60000x2 + $80000x3 <= $80000 in capital
4000x1 + 3000x2 + 4000x3 <= 4000 labour hours
In this example, the constraints are so tight that there’s not much room for variation. Personally, I would say that these constraints are right on the edge of absurdity. Yes, there is a solution but if the goal is to construct housing then we can’t really get much done. That also means there’s no pivoting required to obtain the solution for maximization. The biggest payout in the objective function belongs to x3, which happens to use up our very limited resources in the second and third constraint. We can set x3=1, which gives us the maximum solution but no other types of housing can be constructed.
In article 1, we saw what happens when we loosen up these constraints a little:
3000x1 + 1000x2 + 4000x3 <= 4000 labour hours
Again, this reduction in labour hours for condos and townhouses is not very realistic but we want to see what kind of impact this change has on our solution. If we were to follow the Simplex algorithm with our revised numbers, we’d find the same Basic Feasible Solution as before: x3 = 1, P = $24000(1). We’d continue pivoting through x2, then x1 where we’d find the maximum solution by setting x1 = 1, and x2 = 1, x3 = 0.
P = 20000(1) + 18000(1) + 24000(0) = $38000
Is it possible to obtain this solution without all that pivoting? Yes!
INTRODUCING WINDUP BY 1
We already know that we’re dealing with tight constraints, so the next thing we want to do is a check for the Optimal Shortcut. Does the variable with the greatest coefficient in the objective function also use the least of the constraint (or row) with a minimum quotient? For this example, x3 has the biggest coefficient in the objective function. We find the minimum quotient for x3 in the third row (or constraint). In this row, x3 happens to have the largest value, which means it uses more of this constraint than any other variable. Therefore, the Optimal Shortcut is not in effect. If it were, we’d set x3 to the min. quotient value and we’d get our maximum solution. Instead, we’ll set this variable to 1 and see if it meets all constraints. It does, so this is our Basic Feasible Solution. If it didn’t then we’d proceed to the variable with the next greatest coefficient in the objective function, set it to 1, and check if all constraints are met. We proceed through all remaining variables in the objective function in this manner until a Basic Feasible Solution is found. If there’s no feasible solution then you know constraints are too tight.
Back to our current example, we’ve got a B.F.S. Now what? We check to see if any other variables can be added to that solution. Proceed to the variable with the lowest coefficient in the objective function, set it to 1, and check whether it can be added without exceeding constraint totals. If so, then continue the same procedure using the variable with the next lowest coefficient in the objective function.
If you find that no other variables can be added to the B.F.S., then you must zero out that variable. This is the case with our current example. When this happens, proceed to the variable with the next highest coefficient in the objective function and set it to 1. Does it meet all constraints? If so, then it’s the next feasible solution. See if any other variables can be added to it without exceeding constraints. When all variables have been tested, then add 1 to the variable with the lowest objective function coefficient. Continue this procedure until constraints are exceeded. When this occurs, your previous solution was the maximum solution.
That’s a lot of explanation, lets see this algorithm in action with our current example.
1) Check for the Optimal Shortcut. x3 has the greatest objective function coefficient. In the constraint where the minimum quotient is found, x3 has the greatest value, therefore the Optimal Shortcut is not in effect.
2) Find the Basic Feasible Solution. We set x3 = 1, which meets all constraints. The B.F.S. is P = 24000(1).
3) Add to B.F.S. or substitute.
With our current example, no other variables can be added to the B.F.S.. Therefore, set that variable to 0. Proceed to the variable with the next highest objective function coefficient, set it to 1 and see if any other variable can be added to it.
We set x3 = 0.
x1 has the next highest objective function coefficient. We’ll consider it the next feasible solution if it satisfies all constraints.
We set x1 = 1. This satisfies all constraints.
Test out addition to the variable with the lowest objective function coefficient.
We set x2 = 1. Can we add this variable without exceeding constraints? Yes.
P = 20000(1) + 18000(1) + 24000(0) = 38000
These values could be our maximum solution.
4) Windup by 1 and check constraints.
Add 1 to the variable with the lowest objective function coefficient. Then see if that variable can be added to the feasible solution. If not then the solution obtained in the last step is the maximum.
x1 = 1, x2 = 2
We quickly discover that these values exceed our second and third constraints.
60000(1) + 60000(2) + 80000(0) = 180000
3000(1) + 1000(2) + 4000(0) = 5000
5) One last check!
Keep that wound up variable, zero out the previous feasible solution, and check all constraints. If all constraints are met, then check the objective function to make sure this amount doesn’t exceed our current maximum solution.
x1 = 0, x2 = 2
Meets all constraints, but still less than our current maximum solution.
P = 20000(0) + 18000(2) + 24000(0) = 36000
Therefore, our maximum solution was obtained in step 3).
P = 20000(1) + 18000(1) + 24000(0) = 38000
CONCLUSION
When constraints are tight, and one is dealing with discrete units, this Windup by 1 algorithm can be used to obtain the solution to maximization problems where the Simplex algorithm may lead to an incorrect solution. More specifically, Windup by 1 can be used to find a correct solution in cases where the same minimum quotient value is found for multiple rows and it’s difficult to know which row to use for pivoting. With tight constraints, Windup by 1 is a viable alternative as not much winding can occur before exceeding a constraint, and a maximization solution can be found relatively easily.