Introduction to the simplex method

To any dictionary there is an associated solution of the system of equations: just set all the non-basic variables to zero and compute the values of the basic variables from the dictionary. For the above dictionary the associated solution is \[ x_1 = x_2 = x_3 = 0, x_4 = 14, x_5 = 28, x_6 = 30. \]

The solution associated to a dictionary certainly satisfies all of the constraints that are equations, but may fail to satisfy the positivity constraints. When it does also satisfy the positivity constraints it is said to be a feasible solution and the dictionary is called feasible too.

Here the initial dictionary is feasible because the LP we started with happened to have all the right-hand sides of constraints non-negative. This needn’t always happen and later on we will cover what to do when some constraints have negative right-hand sides; but for now, let’s focus on the case when the initial dictionary is feasible, like in this example.

In the dictionary we have, the \(z\)-row is \(z=0+x_1+2x_2-x_3\). This tells us that for the solution associated to the dictionary, the objective function has the value \(0\); and it also tells us, for each non-basic variable, whether increasing that variable will increase or decrease \(z\). Since \(x_1\) and \(x_2\) have positive coefficients, increasing them would increase \(z\). On the other hand, increasing \(x_3\) will decrease \(z\).

So, to increase \(z\) we will choose either \(x_1\) or \(x_2\) to enter the basis.

Either one would be a valid choice and make some progress toward solving the LP, but we’ll use a definite rule to pick one:

Standard rule⁴ for picking the entering variable: among the non-basic variables that have a positive coefficient in the objective function, choose the one with the largest coefficient. If more than one variable is tied for largest coefficient, pick the one with smallest index (e.g., if both \(x_4\) and \(x_2\) had a coefficient of \(3\), and \(3\) was the largest, you’d pick \(x_2\)).

This is not done for mathematical reasons but for logistical reasons! By having a standard rule for the course, I can make sure that when you solve an LP you don’t get crazy numbers, and the course grader has an easier time, too.

We’ve settled on putting \(x_2\) in the basis and now we need to decide which basic variable to swap it with. The solution associated to our current dictionary has \(x_2=0\). The idea now is to increase the value of \(x_2\) as much as possible while keeping the resulting dictionary feasible. Let’s focus on how the values of the basic variables depend on \(x_2\) (keeping \(x_1=x_3=0\)):

\[\begin{array}{rrr} x_4 = & 14 & -x_2\\ x_5 = & 28 & -2 x_2\\ x_6 = & 30 & -5 x_2\\ z = & 0 & +2 x_2\\ \end{array}\]

We see that:

• To keep \(x_4 \ge 0\), we can only increase \(x_2\) up to \(14\).
• To keep \(x_5 \ge 0\), we can only increase \(x_2\) up to \(14\).
• To keep \(x_6 \ge 0\), we can only increase \(x_2\) up to \(6\).

So, to keep all variables non-negative, we can only go up to \(6\). Since \(x_6\) had the strictest requirement on the entering variable \(x_2\), we pick \(x_6\) as the exiting variable.

In case two variable are tied for strictest bound on the entering variable we need a tie breaking rule:

Standard rule for picking the exiting variable: In case of ties, pick the variable with the smallest index.

At this point you know how to pivot to increase the objective function while keeping the dictionary feasible. For example, in the last feasible dictionary we can pivot by having \(x_1\) enter. Either \(x_4\) or \(x_5\) would have to exit and our tie-breaking rule has us choose \(x_4\). After pivoting we get:

\[\begin{array}{*{10}{r}} x_1 = & 5 & & -\frac{5}{8} x_4& +\frac{1}{8} x_6\\ x_2 = & 4 & -x_3& +\frac{1}{4} x_4& -\frac{1}{4} x_6\\ x_5 = & 0 & -x_3& +2 x_4\\ z = & 13& -3 x_3& -\frac{1}{8} x_4& -\frac{3}{8} x_6\\ \end{array}\]

This new dictionary has all of the coefficients in the \(z\)-row negative, so we can’t pick a new entering variable. This means we are done with this problem and \(z=13\) is the maximum value of the objective function. The solution associated to this dictionary, \(x_3=x_4=x_6=0, x_1=5, x_2=4, x_5=0\) is an optimal solution.

Why exactly is \(z=13\) the maximum? Clearly the Simplex Method stops here, since there is no way to pick variables for the next pivot according to the rules, but can’t there be a sneaky way to increase \(z\), say, by doing a pivot that’s against the rules because it decreases \(z\), followed by a pivot that makes \(z\) even bigger than \(13\)?

There’s no need to worry, that can’t happen and the dictionary tells us why: we have \(z = 13 -3 x_3 -\frac{1}{8} x_4 -\frac{3}{8} x_6\) and each variable has a positivity constraint, so that equation really tells us that \(z = 13 - {}\) (something non-negative) \(\le 13\).

Additionally we learn that \(z=13\) only when \(x_3=x_4=x_6=0\). And having those variable be zero tells us that \(x_1=5, x_2=4, x_5=0\), so that the optimal solution we found is the only optimal solution.