Simplex method: Start to finish

Go to Part A: Introducing the simplex method

This tutorial: Part B: Simplex method: Start to finish

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

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

The simplex method for standard maximization problems: Start to finish

%%Note In %%lpTutA we discussed each of the following steps in the solution of a standard maximization problem:

Steps in the solution of a standard maximization problem

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 (sometimes called an indicator) 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 in %%gjtutB, 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.]#

#[To review or practice any of these steps in detail go back to %%lpTutA or the %%modulePage.][Para revisar o practicar cualquiera de estos pasos en detalle, vuelva a %%lpTutA o a los %%modulePage.]#

%%Example
#[Here is the complete solution to the LP problem we looked at in %%lpTutA.][Aquí está la solución completa al problema de LP que vimos en %%lpTutA]#

#[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$.

Convert the problem to equation form using slack variables.
$x + y + z + s = 10$ \\ $4x - 3y + z + t = 3$ \\ $2x + y - z + u = 10$ \\ $-2x + 3y - z + p = 0$.
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 in %%gjtutB, 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.
As there is still a negative entry in the bottom row of the $z$ column, we need to pivot in that column:
#[Therefore we pivot on the boxed 1.][Por lo tanto, pivotamos en la 1 encajada.]#

↓

As there are no more negative entries in the bottom row under the decision variables, we are done, so the solution to the LP problem is the current basic solution:

$x = 0$ \t (#[inactive][inactiva]#); \t $y = 0$ \t (#[inactive][inactiva]#); \\ $z = 3/1 = 3$; \t \t $s = 28/4 = 7$; \\ $t = 0$ \t (#[inactive][inactiva]#); \t $u = 26/2 = 13;$ \\ $p = 6/2 = 3$; \t (#[Maximum value of $p$][Valor má'ximo de $p$]#)

As the name of this part of the tutorial suggests, your main task in this tutorial to do a simplex method calculation from start to finish:

When things don't go according to plan

%%Q #[The step by step method above assumes it is always possible to go to the next step, but what could prevent that, and why?][El método paso a paso anterior asume que siempre es posible pasar al siguiente paso, pero ¿qué podría evitarlo y por qué?]#
%%A #[For the standard LP problems we are condiering here, the only thing that can go wrong, assuming you correctly follow each step, is that it is impossible to chosse a pivot in the column with a negative indicator in the bottom row becuase there are no positive entries in that column that can serve as a pivot, for instance in the following:][Para los problemas estándar de PL que estamos considerando aquí, lo único que puede salir mal, suponiendo que sigas correctamente cada paso, es que es imposible elegir un pivote en la columna con un indicador negativo en la fila inferior porque no hay entradas positivas en esa columna que pueden servir como pivote, por ejemplo en lo siguiente:]#

#[Notice that all the entries in the $z$-column are either zero or negative, so we cannot choose a positive pivot for Step 4. If this happens, it indicates that there is no maximum possible value of the objective variable $p$; it an be made as big as we like. Thus, the LP problem has no solution.][Observa que todas las entradas en la columna $z$ son cero o negativas, por lo que no podemos elegir un pivote positivo para el paso 4. Si esto sucede, indica que no hay un valor máximo posible de la variable objetivo $p$; se puede hacer tan grande como queramos. Por lo tanto, no hay solución para el problema de PL.]#

%%Q #[What if you get a negative test ratio? Do those also qualify for selecting the pivot?][¿Qué sucede si obtiene una razón de prueba negativa? ¿Califican también para seleccionar el pivote?]#
%%A #[The only way one could obtain a negative test ratio would be if either the candidate for the pivot were negative (which is not permitted) or if the corresponding value in the last column were negative, as illustrated below, which would indicate an error.][La única forma en que se podría obtener una razón de prueba negativa sería si el candidato para el pivote fuera negativo (lo cual no está permitido) o si el valor correspondiente en la última columna fuera negativo, como se ilustra más abajo, que indicaría un error.]#

#[We should never have arrived at a tableau like the one in the first place, as it indicates a non-feasible basic solution: Following the simplex method according to the instructions will never result in a negative right-most entry in any row (except possiby the bottom row). The only way this can happen, assuming you have not made an arithmetical error), is if you pivot on an entry whose test ratio is not the lowest, or if you do not use the specific types of row operation we indicate. Thus, you will need to locate the error you made in selecting the pivot in an earlier tableau and redo the necessary steps.][Nunca deberíamos haber llegado a una tabla como esta en primer lugar, ya que indica una solución básica no factible: Seguir el método símplex de acuerdo con las instrucciones nunca resultará en una última derecha entrada que es negativa (excepto posiblemente en la fila inferior). La única forma en que esto puede suceder, suponiendo que no haya cometido un error aritmético, es si pivotas en una entrada cuya razón de prueba no es la más baja, o si no utiliza los tipos específicos de operación de filas que le indicamos. Por lo tanto, deberás ubicar el error que cometiste al seleccionar el pivote en una tabla anterior y rehacer los pasos necesarios.]#

%%Q #[Can you ever get a negative value in the bottom row in the $p$column?][¿Alguna vez puedes obtener un valor negativo en la fila inferior de la columna $p$?]#
%%A #[Short answer: No; it would indicate that either you made an error doing row operations or were not using the specific kinds of row operation we indicate.][Respuesta corta: No; indicaría que has cometido un error al hacer operaciones de fila o no estabas usando los tipos específicos de operación de fila que indicamos.]#

%%Q #[Can you ever get a negative value in the bottom row in the rightmost column?][¿Alguna vez puedes obtener un valor negativo en en la parte inferior de la columna de la derecha?]#
%%A #[For standard maximization problems: no, as the value of $p$ cannot become negative in the process; it would indicate that either you made an error doing row operations or were not using the specific kinds of row operation we indicate.][Para problemas de maximización estándar: no, ya que el valor de $p$ no puede convertirse negativo durante el proceso; indicaría que has cometido un error al hacer operaciones de fila o no estabas usando los tipos específicos de operación de fila que indicamos.]#

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