MÉTODO SIMPLEX PASOS DEL MÉTODO DE LA GRAN M

MÉTODO SIMPLEX

PASOS DEL MÉTODO  DE LA GRAN M

Se utiliza cuando un programa de programación lineal se encuentra con restricciones con signos de igual o mayor o igual. La M es un valor muy grande, cercano a infinito, usada para penalizar el surgimiento de variables artificiales R.

1. Acomodar el modelo en forma canónica, (completar cada restricción):

1. Si la restricción contiene una igualdad, únicamente sumar una variable artificial R.
2. Si la restricción tiene un signo mayor o igual, restar una variable de holgura S, además agregar una variable artificial R.
3. Si la restricción tiene un signo menor o igual (es normal), por lo que únicamente se le sumará una variable de holgura S;  no se requiere agregar la variable artificial R.

1. En base a lo anterior, se agregan las variables artificiales en la función objetivo con el coeficiente M acompañando a cada variable artificial R que se ha agregado a las restricciones.  Si el problema es de maximizar, deberán agregarse –M como coeficiente de la variable artificial en el función objetivo, y si es de minimizar, deberán agregarse +M.
2. Igualar la función objetivo a cero.
3. Formar la tabla colocando todas las variables en el renglón principal, incluyendo la columna de lado derecho; en la columna principal colocar únicamente Z y las variables de holgura y artificiales.
4. Al acomodar en la tabla, convertir los coeficientes –M o +M a cero, auxiliándose de las restricciones que los generaron.  Se multiplica por M cada uno de los coeficientes del renglón de cada una de las restricciones que generaron las variables artificiales y se suman con el renglón de Z; el resultado se coloca en el renglón de Z.  Los renglones que generaron las variables artificiales, no se modifican.
5. Seleccionar la columna con el valor más negativo en caso de estar maximizando; y el valor más positivo en caso de estar minimizando. Y a esta columna le ponemos una etiqueta de “entra”.
6. Seleccionar un renglón que se obtiene de dividir el lado derecho sobre la columna seleccionada sin tomar en cuenta ceros y negativos, y el renglón que dé el cociente menor será el que debemos seleccionar y será la variable que sustituyamos por la que tiene la etiqueta de “entra”.
7.  Identificar el elemento pivote que es el número que queda en la intersección de la columna y renglón seleccionados. Si éste es 1 entonces pasamos todo el renglón a la segunda tabla en el renglón con la nueva variable que entro.
8. En caso de que el elemento pivote no sea uno, entonces multiplicamos todo el renglón por su recíproco y ponemos los resultados en el renglón nuevo de la siguiente tabla.
9.  Convertir a cero los demás elementos que están en la columna del elemento pivote. Sacándolos de la tabla con el signo contrario y multiplicarlos por el elemento que les corresponde de la siguiente tabla y sumarlos al elemento del cual salieron.
10. Regresar al paso tres, hasta ya no encontrar más positivos o negativos en z, según sea el caso.
11.  Verificar la solución óptima que está formada por las variables de la columna principal y los valores del lado derecho.

...