Linear Programming: The Simplex Method
📂OptimizationLinear Programming: The Simplex Method
Buildup
Consider the following Linear Programming Problem for x1,x2≥0.
Maximizesubject to−x1x1x1++x2x2x2≤≤≤132
In other words, we want to maximize x1+x2 while satisfying all given constraints. To convert this into equation form, we introduce the so-called Slack Variable x3,x4,x5≥0, so that it can be represented as
Maximizesubject to−x1x1x1++x2x2x2+x3+x4+x5===132
Subsequently, expressing it again as a dictionary or tableau turns the original x1, x2 into Nonbasic Variables which stay on the right side, and x3, x4, x5 become Basic Variables that move to the left side,
ζx3x4x5====0132++−x1x1x1+−−x2x2x2
N={1,2}B={3,4,5}
Here, ζ=ζˉ+x1+x2’s ζˉ is the function value of the objective function for the optimal solution, which essentially means how optimized it is currently. By performing variable substitutions with the equations below, it might be possible to unify the signs of the nonbasic variables on the right side of ζ to −. Therefore, when all nonbasic variables are substituted with 0,
ζ=ζ?−x?1−x?2
this form will yield the largest value. In other words, this is obtaining a feasible basis. The existence of a sign like + among the nonbasic variable signs signifies that there is still potential for ζ? to increase, while all signs being − means that there is no longer any way to increase ζ?. This is the idea behind the Simplex Method. Although it seems like the problem is being solved algebraically, the term simplex is used because introducing the slack variable to create the equation form results in a solution space that is a simplex.
Practical Application
ζx3x4x5====0132++−x1x1x1+−−x2x2x2
N={1,2}B={3,4,5}(x1,x2,x3,x4,x5)=(0,0,1,3,2)ζˉ=0
Let’s actually solve the above example using the simplex method.
Given the form of ζ, both x1, and x2 can be increased, but knowing x4=3−x1 and x5=2−x2 from the constraints, it doesn’t seem to have much significance for now. Considering the condition for x3,
x2=1+x1−x3
the new dictionary is as follows.
ζx2x4x5====1131++−−2x1x1x1x1−−+x3x3x3
N={1,3}B={2,4,5}(x1,x2,x3,x4,x5)=(0,1,0,3,2)ζˉ=1
As can be seen in the equation, we have increased the value of the objective function by 1 compared to before. This process of revising the dictionary is called Pivot Step, and the variables like x2 that move from nonbasic to basic are called Entering Variables, while those like x3 moving from basic to nonbasic are called Leaving Variables. It’s important not to get confused here; we’ve never actually changed the objective function itself, nor will we ever do so. As from the very beginning in the buildup, existing variables merely represent other variables, and only now do constant terms that weren’t visible before come into view.
Our current task in the dictionary seems quite clear at this point. Increasing x1 appears to double the value of the objective function. Using the same reasoning, choosing x5 as the entering variable,
x1=1+x3−x5
results in:
ζx1x2x4====3122++−x3x3x3−−−+2x5x5x5x5
N={3,5}B={1,2,4}(x1,x2,x3,x4,x5)=(1,2,0,2,0)ζˉ=3
Since there’s still room for x3 on the right side of ζ to increase, using x3 as the entering variable yields:
x3=2−x4+x5
and consequently:
ζx1x2x3====5322−−−x4x4x4−−−+x5x5x5
N={4,5}B={1,2,3}(x1,x2,x3,x4,x5)=(3,2,2,0,0)ζˉ=5
Now, as all variable signs on the right side of ζ are −, touching any variable won’t increase ζ further, indicating that the optimization is complete. Indeed, by substituting x1=3 and x2=2 into the initially given linear programming problem
Maximizesubject to−x1x1x1++x2x2x2≤≤≤132
and recalculating, it can be confirmed that all given constraints are well satisfied and the value of the objective function is precisely ζ=ζˉ−0=5.
