Introducing the simplex method
Game version
This tutorial: Part A: Introducing the simplex method
(This topic is also in Section 6.3 in Finite Mathematics and Applied Calculus)

Resources
Simplex method tool  Pivot and GaussJordan tool  Excel pivot and GaussJordan tool 
Standard maximization problems and slack variables
%%Note To follow this tutorial, you should know how systems of linear equations are solved by row reduction as described in Section 6.3 in Finite Mathematics and Applied Calculus or the %%gjtut. In particular, you should know how to represent systems of equations in matrix form, how to do row operations and, in particular, how to "pivot" or clear a column" in a matrix. You should revise that material if necessary.
%%Q Remind me what a linear programming problem is.%%A A linear programming (LP) problem is a problem in which we are asked to find the maximum (or minimum) value of a linear objective function
$p = a_1x_1 + a_2x_2 + ... + a_nx_n \qquad$ \t %%Example $p = 3x  2y + z$
subject to a set of linear constraints of the form
$b_1x_1 + b_2x_2 + ... + b_nx_n \leq c \qquad$ \t %%Example $x + y  3z \leq 12$
\\ #[or][o]#
\\ $b_1x_1 + b_2x_2 + ... + b_nx_n \geq c \qquad$ \t %%Example $3x+yz \geq 0$
where $b_1, b_2, ..., b_n, c$ are constants with $c$ nonnegative.
The desired largest (or smallest) value of the objective function is called the optimal value, and a collection of values of the unknowns $x_1, x_2, ..., x_n$ that gives the optimal value constitutes an optimal solution. The variables $x_1, x_2, ..., x_n$ are called the decision variables.
Standard maximization problems are special kinds of linear programming problems:
Standard maximization problem
A linear programming (LP) problem is called a standard maximization problem if:
A linear programming (LP) problem is called a standard maximization problem if:
 We are to find the maximum (not minimum) value of the objective function.
 All the decision variables $x_1, x_2, ..., x_n$ are constrained to be nonnegative.
 All further constraints have the form $bx_1 + bx_2 + ... + bx_n \bold{\color{#b50b0b}{\leq}} c$ (and not $\geq c$), and $c$ cannot be negative.
%%Examples
1. #[The following is a standard maximization problem:][El siguiente es un problema de maximización estándar:]#
2. #[The following LP problem is not standard as presented, but can be rewritten a standard maximization problem:][El siguiente problema de PL no es estándar como se presenta, pero se puede reescribirse como un problema de maximización estándar:]#
1. #[The following is a standard maximization problem:][El siguiente es un problema de maximización estándar:]#
#[Maximize][Maximizar]# \t $p = 2x  3y + z$ \t #[Objective function][Función objectiva]#
\\ #[subject to][sujeto a]# \t $3y + z \leq 0$
\\ \t $2x + y  z \leq 10$ \t #[Constraints][Restricciones]#
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
2. #[The following LP problem is not standard as presented, but can be rewritten a standard maximization problem:][El siguiente problema de PL no es estándar como se presenta, pero se puede reescribirse como un problema de maximización estándar:]#
#[Maximize][Maximizar]# \t $p = 3x3y8z$
\\ #[subject to][sujeto a]# \t $xz \geq 5$
\\ \t $3y+5z \geq 0$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
We can reverse the inequality in the first and second constraint by multiplying both sides by $1$ to obtain the following standard maximization problem:
#[Maximize][Maximizar]# \t $p = 3x3y8z$
\\ #[subject to][sujeto a]# \t $x + z \leq 5$
\\ \t $3y  5z \leq 0$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
One for you
Equation form of an LP problem
The method most frequently used to solve LP problems is the simplex method, which we discuss in the rest of this tutorial. The first step is to rewrite the entire problem as a system of linear equations:
Converting to equation form
Here is a trick to convert any inequality into an equation: If, for example,
Here is a trick to convert any inequality into an equation: If, for example,
$x \leq 5$,
then we can make the lefthand side equal to $5$ by adding something to it, called the slack.:
$x + s = 5 \qquad$ \t #[s is a nonnegative quantity called a slack variable.][s es una cantidad no negativa llamada una variable de holgura.]#
So, for instance, if $x = 1$ then $s$ would equal $4$ to give the result of 5. We use this technique to rewrite the entire LP problem as a system of equations as shown in the example below.
%%Example A
#[Consider the following LP problem.][Vamos a considerar el siguente problema PL:]#
%%A We omit the constraints $x \geq 0, y \geq 0, z \geq 0$ as the simplex method assumes that all decision variables are nonnegative. These include $x, y, z,$ and also $s, t, u$ as we commented above. One for you
#[Consider the following LP problem.][Vamos a considerar el siguente problema PL:]#
#[Maximize][Maximizar]# \t $p = 2x  3y + z$
\\ #[subject to][sujeto a]# \t $x + y + z \leq 10$
\\ \t $4x  3y + z \leq 3$
\\ \t $2x + y  z \leq 10$
\\ \t $x \geq 0, y \geq 0, z \geq 0$.
We first convert all the constraints except those in the last line to equations using slack variables (one for each inequality) as additional decision variables:
$x + y + z + s = 10$
\\ $4x  3y + z + t = 3$
\\ $2x + y  z + u = 10$
Then, as a last equation, we add the objective equation, but with all the unknowns brought to the lefthand side:
$2x + 3y  z + p = 0$.
So now we have a system of four linear equations in the 7 unknowns $x, y, z, s, t, u, p$:
$x + y + z + s = 10$
\\ $4x  3y + z + t = 3$
\\ $2x + y  z + u = 10$
\\ $2x + 3y  z + p = 0$.
Note The decision variables in this expanded problem are the original unknows $x, y, z$ together with the slack variables $s, t, u$. None of these quantities is permitted to be negative (although $p$, which is not a decision variable, may or may not be negative; for instance, $p$ could represent profit, so a negative value would indicate a loss).
%%Q What about the inequalities $x \geq 0, y \geq 0, z \geq 0$ in the last line of the LP problem? %%A We omit the constraints $x \geq 0, y \geq 0, z \geq 0$ as the simplex method assumes that all decision variables are nonnegative. These include $x, y, z,$ and also $s, t, u$ as we commented above. One for you
Simplex tableaus and basic solutions
Whenever we have a system of linear equations we can express it in matrix form using the augmented matrix of the system of equation as described in the %%gjtut. In the situation here, we typically have more equations than unknowns, so we can expect to see general solutions in which some of the variables can be chosen arbitrarily to get particular solutions (see %%gjtutC). Recall that we get the general solution as follows: Use pivoting operations to reduce the augmented matrix, then write the result in equation form, and finally solve for the first variable in each equation. The simplex method works by doing something similar, but not by first reducing the matrix in the usual way.
Take a look at the augmented matrix form of the system of equations we got in Example A above:
$s = 10  x  y  z$
\\ $t = 3  4x + 3y  z$
\\ $u = 10  2x  y + z$
\\ $p = 2x  3y + z$,
\\ $x, y, z$ #[arbitrary][arbitrarias]#
In the simplex method, we choose all the all the arbitrary variables to be zero (and call them inactive), giving us what we call a basic solution:
$s = 10$ \t Active variables
\\ $t = 3$
\\ $u = 10$
\\ $p = 0$,
\\ $x = 0, y = 0, z = 0$. \gap[20] \t Inactive variables
The variables that were not specified as arbitrary are those corresponding to the pivots, and we call them the active variables (they can also turn out to be zero, as we see in the case of the last one, $p$). Rather than rearranging the columns as we did above, we instead indicate the active variables by adding them as labels to each row:
Going from tableau to tableau: Choosing the pivot
In the simplex method, we go from one basic solution to the next by pivoting in such a way that the resulting value of $p$ keeps going up. When it cannot go any higher, we are done! The secret of the method is how we choose the pivot in order to make the value of $p$ increase. Here are the rules for selecting the pivot at any stage.
How to choose the pivot
To select each pivot entry, we will first select a column, then a specific entry in that column. Pivot column The rule for the selecting a pivot column is this: Look at all the numbers in the bottom row, excluding the last entry on the right (in the "answers" column). From these, choose the negative number with the largest magnitude; its column is the pivot column. If there are two or more candidates, choose any one. If there are no negative numbers to choose, then you are done! and the current basic solution is the optimal solution.
To select each pivot entry, we will first select a column, then a specific entry in that column. Pivot column The rule for the selecting a pivot column is this: Look at all the numbers in the bottom row, excluding the last entry on the right (in the "answers" column). From these, choose the negative number with the largest magnitude; its column is the pivot column. If there are two or more candidates, choose any one. If there are no negative numbers to choose, then you are done! and the current basic solution is the optimal solution.
%%Example
#[In the initial tableau of the demonstration LP problem, the negative entry in the bottom row with the largest numerical value is the −2, so the pivot column is the xcolumn. The actual pivot will be somewhere in this column.][En la tabla inicial del problema PL demonstración, la entrada negativa con el valor absoluto más grande en la última fila es la −2, así seleccionamos la columnax como la columna pivote. El pivote en sí estará en alguna parte de esta columna.]#
#[In the initial tableau of the demonstration LP problem, the negative entry in the bottom row with the largest numerical value is the −2, so the pivot column is the xcolumn. The actual pivot will be somewhere in this column.][En la tabla inicial del problema PL demonstración, la entrada negativa con el valor absoluto más grande en la última fila es la −2, así seleccionamos la columnax como la columna pivote. El pivote en sí estará en alguna parte de esta columna.]#
Selecting the pivot Use the following rules to decide which of the entries in the column you selected to use as the pivot:
 The pivot must always be a positive number (zeros or negative numbers are not permitted as pivots).
 For each positive entry $b$ in the pivot column, compute the ratio $a/b$, where $a$ is the number in the rightmost column in that row. We call this a test ratio.
 Of these ratios, choose the smallest one. The corresponding number $b$ is the pivot. (If there are more than one giving the lowest ratio, choose any one.)
%%Example
#[In the demonstration example we are working with, the pivot will be either the 4, the 1 or the 2 in the xcolumn. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será o la 4, la 1, o la 2 en la columnax. Aquí están las razones de prueba para estos candidatos:]# Because the smallest test ratio is in row 2, our pivot will be the 4 as shown.
#[In the demonstration example we are working with, the pivot will be either the 4, the 1 or the 2 in the xcolumn. Here are the test ratios for these candidates:][En el ejemplo demonstración con el que estamos trabajando, el pivote será o la 4, la 1, o la 2 en la columnax. Aquí están las razones de prueba para estos candidatos:]# Because the smallest test ratio is in row 2, our pivot will be the 4 as shown.
Going from tableau to tableau: Pivoting
Once we have selected a pivot entry, we then pivot on it by using the method discussed in %%gjtutB. That is, we clear its column using row operations of a specific type so that no fractions are introduced in our tableaus. (We do not first convert the pivot to a $1$ When our tableau consists of whole numbers, so as not to introduce fractions unnecessarily.) In situations where the tableau cannot be expressed with integers, or when we are using technology to do the pivoting, then traditional pivoting—converting the pivots to 1s—can be used.
Pivoting in the simplex method
A simplex method tableau is just an augmented matrix, so we pivot in exactly the same way as in %%gjtutB. Note that the rightmost column and bottom row are part of the matrix as well. The only difference is that the rows are labeled by active variables. For instance, in the following tableau the active variables are $s, t, u$.
#[If we pivot in the boxed entry shown above, we get :][Si pivotamos en la entrada encajada que se muestra, obtenemos]#
↓
How the simplex method works
#[Here, we have discussed all the steps needed to completely solve a standard maximization problem using the simplex method:][Hemos discudido aquí todos los pasos para resolver completametne un problema de maximización estándar usando el mé simplex:]#
 Convert the problem to equation form using slack variables. (Eliminate decimals and fractions of possible by either multiplying the both sides of the constraints by suitable positive integers, or by multiplying both sides of the resulting equations by suitable positive integers.)
 Set up the first tableau, where the active variables are the slack variables.
 Select a column of a decision variable whose entry in the bottom row is the most negative.
 In that column, select a positive pivot whose test ratio is the smallest among other such entries.
 Pivot on the selected entry using row operations of the specific type described above, remembering to also indicate the entering active variable in the pivot row.
 #[Repeat steps 3 to 5 until there are no negative numbers in the bottom row under the decision variables. The basic solution at that point gives a solution to the LP problem.][Repite los pasos 3 a 5 hasta que no haya números negativos en la fila inferior debajo de las variables de decisión. La solución básica en ese punto da una solución al problema de LP.]# #[In part (B) of this tutorial you will do a complete problem from start to finish!][¡En la parte (B) de este tutorial, resolverá un problema completo de principio a fin!]#
Now try some of the exercises in Section 6.3 in Finite Mathematics and Applied Calculus.
Copyright © 2022 Stefan Waner and Steven R. Costenoble