Simplex method: Start to finish
Adaptive game version
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.]#
%%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]#
#[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$]#)
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:]#
%%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.]#
%%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.
Copyright © 2022 Stefan Waner and Steven R. Costenoble