Linear Programming: The Simplex Method
Buildup 1
Consider the following Linear Programming Problem for $x_{1} , x_{2} \ge 0$. $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix} $$ In other words, we want to maximize $x_{1} + x_{2}$ while satisfying all given constraints. To convert this into equation form, we introduce the so-called Slack Variable $x_{3}, x_{4}, x_{5} \ge 0$, so that it can be represented as $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & + & x_{3} & & & & & = & 1 \\ & & x_{1} & & & & & + & x_{4} & & & = & 3 \\ & & & & x_{2} & & & & & + & x_{5} & = & 2 \end{matrix} $$ Subsequently, expressing it again as a dictionary or tableau turns the original $x_{1}$, $x_{2}$ into Nonbasic Variables which stay on the right side, and $x_{3}$, $x_{4}$, $x_{5}$ become Basic Variables that move to the left side, $$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} $$ Here, $\zeta = \bar{\zeta} + x_{1} + x_{2}$’s $\bar{\zeta}$ 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 $\zeta$ to $-$. Therefore, when all nonbasic variables are substituted with $0$, $$ \zeta = \zeta_{?} - 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 $\zeta_{?}$ to increase, while all signs being $-$ means that there is no longer any way to increase $\zeta_{?}$. 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
$$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,0,1,3,2) \\ \bar{\zeta} = 0 $$
Let’s actually solve the above example using the simplex method.
Given the form of $\zeta$, both $x_{1}$, and $x_{2}$ can be increased, but knowing $x_{4} = 3 - x_{1}$ and $x_{5} = 2 - x_{2}$ from the constraints, it doesn’t seem to have much significance for now. Considering the condition for $x_{3}$, $$ x_{2} = 1 + x_{1} - x_{3} $$ the new dictionary is as follows.
$$ \begin{matrix} \zeta & = & & 1 & + & 2x_{1} & - & x_{3} \\ x_{2} & = & & 1 & + & x_{1} & - & x_{3} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 1 & - & x_{1} & + & x_{3} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 3 \right\} \\ \mathcal{B} = \left\{ 2, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,1,0,3,2) \\ \bar{\zeta} = 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 Step2, and the variables like $x_{2}$ that move from nonbasic to basic are called Entering Variables, while those like $x_{3}$ moving from basic to nonbasic are called Leaving Variables3. 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 $x_{1}$ appears to double the value of the objective function. Using the same reasoning, choosing $x_{5}$ as the entering variable, $$ x_{1} = 1 + x_{3} - x_{5} $$ results in: $$ \begin{matrix} \zeta & = & & 3 & + & x_{3} & - & 2x_{5} \\ x_{1} & = & & 1 & + & x_{3} & - & x_{5} \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{4} & = & & 2 & - & x_{3} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 3, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 4 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (1,2,0,2,0) \\ \bar{\zeta} = 3 $$
Since there’s still room for $x_{3}$ on the right side of $\zeta$ to increase, using $x_{3}$ as the entering variable yields: $$ x_{3} = 2 - x_{4} + x_{5} $$ and consequently: $$ \begin{matrix} \zeta & = & & 5 & - & x_{4} & - & x_{5} \\ x_{1} & = & & 3 & - & x_{4} & - & \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{3} & = & & 2 & - & x_{4} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 4, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 3 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (3,2,2,0,0) \\ \bar{\zeta} = 5 $$
Now, as all variable signs on the right side of $\zeta$ are $-$, touching any variable won’t increase $\zeta$ further, indicating that the optimization is complete. Indeed, by substituting $x_{1} = 3$ and $x_{2} = 2$ into the initially given linear programming problem $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix} $$ and recalculating, it can be confirmed that all given constraints are well satisfied and the value of the objective function is precisely $\zeta = \bar{\zeta} - 0 = 5$.