Introducing the simplex method

Adaptive game version

This tutorial: Part A: Introducing the simplex method

Go to Part B: Simplex method: Start to finish

(This topic is also in Section 6.3 in Finite Mathematics and Applied Calculus)

What is an adaptive game tutorial? ▶

I don't like this new tutorial. Take me back to the older tutorial!

Resources

Simplex method tool

Pivot and Gauss-Jordan tool

Excel pivot and Gauss-Jordan 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+y-z \geq 0$

where $b_1, b_2, ..., b_n, c$ are constants with $c$ non-negative.

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:

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 non-negative.
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:]#

#[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 = 3x-3y-8z$ \\ #[subject to][sujeto a]# \t $x-z \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 = 3x-3y-8z$ \\ #[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,

$x \leq 5$,

then we can make the left-hand 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:]#

#[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 left-hand 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:

This particular tabular layout is called a tableau, and the variables listed across the top are sometimes called the decision variables.

Important note: Avoiding fractions and decimals We prefer to work entirely with whole numbers where possible as we do in %%gjtutB. Thus, if there are any fractions or rational decimals at all in your tableau, you should first eliminate them if possible by multiplying each row containing fractions by a suitable integer. (See "Step 1: Clear all fractions and/or Decimals" in that tutorial.)

#[Notice something funny: if we reorder the columns of the matrix with those of the last four variables $s, t, u$, and $p$ first, we get][Nota algo extraño: si reordenamos las columnas de la matriz con las de las últimas cuatro variables $s, t, u$, y $p$ primero, obtenemos]#

which is already in reduced form! (the boxed entries whose columns are cleared are called the pivots). As in the %%gjtutC we can translate back to equations and so obtain the general solution of this system in the following form:

$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:

#[Each row label is the active variable coresponding to its pivot. We can directly read off the values of the active variables as shown:][Cada etiqueta de fila es la variable activa que corresponde a su pivote. Podemos leer directamente los valores de las variables activas como se muestra:]#

The tableau above is a very special one with the last four variables the active ones and their pivots all equal to 1. In the simplex method we will obtain tableaus that look different by pivoting (clearing the column of a selected "pivot" entry; see %%gjtutB to review). Suppose for instance, we pivot on the $4$ in the $x$ column. Then we get a new tableau as shown.

Notice that the boxed $4$ is now the pivot in the second row. As this row's pivot is now in the $x$ column, we change the row label from $s$ to $x$, which enters as a new active variable in place of $s$ (the departing variable.)

Note In our approach to the simplex method, we will not insist that the pivots be turned into 1s, thereby introducing fractions; instead we consider it mathematically more elegant (and a lot easier!) to work with integers as we did in the %%gjtut. So, we just read off the basic solutions as fractions if necessary, as we saw above.

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.

%%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 x-column. 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 columna-x 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 x-column. 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 columna-x. 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 right-most 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.]#

Now try some of the exercises in Section 6.3 in Finite Mathematics and Applied Calculus.

←	Previous Next → Non-game version All tutorials Main page Everything for calc Everything for finite math Everything Español