Método simplex: de principio a fin

Versión juego adaptivo

	⊠

Ir a Parte A: Introducción al método símplex

Este tutorial: Parte B: Método simplex: de principio a fin

(Se puede encontrar este tema en la Sección 6.3 en el libro Matemáticas finitas y cálculo aplicado)

¿Qué es un tutorial juego adaptivo?  ▶

No me gusta este tutorial. ¡Llévame de vuelta a la versión antigua!

Recursos

Herramienta método simplex

Herramienta pivotar Gauss-Jordan

Herramienta pivotar Gauss-Jordan Excel

%%Note En %%lpTutA discutimos cada uno de los siguiented pasos en la solución de un problema de maximización estándar:

Como sugiere el nombre de esta parte del tutorial, tu tarea principal en este tutorial es hacer un cálculo del método simplex de principio a fin:

%%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.]#