Simplex method for standard LP problems Método simplex (problemas PL estándar)
Step 1: Convert the LP problem to a system of linear equations.
Paso 1: Convierte el problema PL en un sistema de ecuaciones lineales.
We do this by turning each constraint inequality into a linear equation by adding new variables we call slack variables, and rewriting the objective function with all the unknowns on the left.
Lo hacemos por convertir cada desigualdad restricción en una ecuación lineal por añadir nuevas variables llamadas variables de holgura, y por reescribir la función objetiva con todos las desconocidos a la izquierda:
Step 2: Represent the system of equations obtained above in the form of an augmented matrix.
Paso 2: Representa el sistema de ecuaciones obtenido más arriba en la forma de una matriz ampliada.
This matrix is called the first tableau.
Ésta matriz se llama la tabla inicial.
Step 3: Select a pivot column.
Paso 3: Escoge una columna pivote.
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 Answer 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.
La regla para escoger una columna pivote is la siguiente: Mira todos los números en el último renglón, excluyendo la última entrada a la derecha (en la columna Resultado). Entre aquellos, escoge el número negativo con el valor absoluto más grande; su columna es entonces la columna pivote. Si hay dos o más candidatos, escoge alguno de aquellos. Si no hay números negativos a escoger, entonces estás terminado, y la solución del problema PL es la corriente solución básica.
Step 5: Use the pivot to clear the pivot column in the normal manner. This gives the next tableau.
Paso 5: Usa el pivote para despejar su columna en la manera usual. Así obtenemos la tabla siguiente.
Step 6: Repeat Steps 3–5 until there are no more negative numbers in the bottom row (with the possible exception of the Answer column).
Paso 6: Repita Pasos 3–5 hasta que no hay ningunos números negativos en el último renglón (con la excepci—n posible de la columna reultado).
That is, we take the most negative number in the bottom row of the current tableau (excluding the rightmost entry) and clear its column using a pivot selected as per Step 4 to obtain the next tableau, and so on, until there are no more negative numbers in the bottom row (excluding the rightmost entry). At that point, we are done, and the solution to the LP problem is the corresponding basic solution.
Es decir, tomamos el número más negativo en el renglón mas bajo de la tabla corriente (excluyendo la entrada más a la derecha) y despejamos su columna a través de un pivote seleccionado según Paso 4 para obtener la tabla siguiente, y así en modo parecido hasta que no quedan ningunos números negativos en el último renglón (excluyendo la entrada más a la derecha). LLegado aquel momento, hemos terminado; la solución del problema PL es entonces la solución básica correspondiente.