Metodo De La Gran M

Aquí detallaremos el Método de la Gran M.

Definimos la letra M como un número muy grande pero finito para usarlo como coeficiente de las variables artificiales en la función objetivo y con sentido contrario a la misma para penalizar de manera muy grande la existencia de las mismas en la solución. Si el objetivo es minimizar las variables artificiales entraran con M positivo y si es maximizar las variables artificiales se usaran como -M.

Ejemplo:

Min Z = 2X1 + X2 + 3X3

Sujeto a:

3X1 + X2 + 2X3 <= 10

X1 - 2X2 + 3X3 >= 6

2X1 + 3X2 - X3 <= 9

X1 + X2 +2X3 = 7

C.N.N

1. Convertir al Modelo Estándar:

Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera. Con las restricciones de tipo <=, es supremamente fácil. Simplemente se agrega una en cada restricción con coeficiente 1 en la misma restricción y con coeficiente cero en la función objetivo. Por ejemplo:

3X1 + X2 + 2X3 <= 10 queda:

3X1 + X2 + 2X3 + S1 = 10

Se puede leer así: el uso de la primera restricción no puede superar la disponibilidad de 10 unidades, lo que equivale a decir que lo usado mas lo que sobre (s1) es igual a 10. Para las restricciones de tipo mayor o igual, la lógica es la misma, de esta manera decir:

X1 - 2X2 + 3X3 >= 6

Se puede leer como: el uso de la restricción 2 debe ser como mínimo 6 unidades. Eso significa que el uso podría ser 6.1 o tal vez 7 u 8... etc. Podríamos escribirlo también como 6+0.1 o 6+1 o 6+2 ... o en términos generales:

X1 - 2X2 + 3X3 = 6 + S2 que es equivalente a decir: lo usado en la restricción2es igual al mínimo requerido que es 6 mas el adicional que esta en S2. Esto lo podemos reescribir como:

X1 - 2X2 + 3X3 - S2 = 6

Sin embargo para el método simplex, cuando aparece esta restricción tipo >= es necesario adicionar una variable comodín, llamada Variable Artificial, sin ningún significado físico, sólo como artificio matemático. Lo sumamos al lado izquierdo de la restricción como se muestra a continuación:

X1 - 2X2 + 3X3 - S2 + A1 = 6

Al usar una variable artificial debemos penalizar la función objetivo allí la vamos a incluir con un coeficiente muy grande, llamado M, al estar minimizando la sumamos + .MA1.

La tercera restricción es de tipo <=, por lo que no tenemos ningún problema con ella:

2X1 + 3X2 - X3 <= 9 queda

2X1 + 3X2 - X3 + S3 = 9

La cuarta restricción es de tipo =. Para este tipo de restricción simplemente adicionamos una variable artificial al lado izquierdo:

X1 + X2 +2X3 = 7 queda:

X1 + X2 +2X3 + A2 = 7

Recordemos: las variables de holgura quedan con coeficiente 0 en la función objetivo y las variables artificiales con coeficiente M. Positiva si es minimizando o negativa si es maximizando.

En resumen el modelo queda de la siguiente manera:

Min Z = 2X1 + X2 + 3X3 + 0S1 + 0S2 + MA1 + 0S3 + MA2

Sujeto a:

3X1 + X2 + 2X3 + S1 = 10

X1 - 2X2 + 3X3 - S2 + A1 = 6

2X1 + 3X2 - X3 + S3 = 9

X1 + X2 + 2X3 + A2 = 7

C.N.N (Condición de No Negatividad)

2. Escribir en formato de Tabla Simplex.

Si lo escribimos como una matriz, indicando los nombres de las variables en negro queda asi:

Fig 1

X1 X2 X3 S1 S2 A1 S3 A2

Min Z 2 1 3 0 0 M 0 M RHS

R1 3 1 2 1 0 0 0 0 10

R2 1 -2 3 0 -1 1 0 0 6

R3 2 3 -1 0 0 0 1 0 9

R4 1 1 2 0 0 0 0 1 7

Dónde X1, X2, X3 son las variables de decisión, S1, S2 y S3 son las variables de Holgura. R1, R2, R3, R4 son las restricciones y RHS son las disponibilidades o Requerimientos de las restricciones, (RHS= Right Hand Side: "el lado derecho" es decir los valores numéricos).

3. Definir la Variable que entra

Recordemos que tenemos un grupo de variables que llamamos base a las que tenemos en cuenta en cada iteración para dar la solución, las demás variables las llamamos No Básicas y se toman con valor cero (de manera análoga a cuando resolvemos un sistema de ecuaciones que tiene más variables que ecuaciones, tenemos que hacer cierta cantidad de estas variables iguales a cero).

En la primera iteración la regla para escoger las variables que estarán en la base es la siguiente:

-Si hay variables de decisión y de holgura, se toma la de holgura.

-Si hay variables de decisión, de holgura y artificiales se toma la variable artificial.

-Si hay variables de decisión y artificiales se toma la variable artificial.

Por esta razón para la primera restricción dónde hay variables de decisión (Xi) y la de holgura S1, tomamos la S1 para la base, en la segunda restricción hay de holgura, de decisión y artificial, tomamos la artificial A1, en la tercera hay de decisión y de holgura, tomamos la de holgura S3 y por último en la cuarta restricción hay de decisión y artificial, por lo que tomamos la A2 para la base. Todas las demás se asumen en la primera iteración con valor cero.

Llenar la tabla inicial. Tal como se ve en la tabla de abajo. Hay muchos formatos de tablas, pero en esencia son el mismo. Esta el listado de variables que se tienen en la base (en la segunda columna rotulada como base), en la primera columna están los coeficientes de las variables básicas, luego vienen las restricciones con sus coeficientes, las disponibilidades/requerimientos de las restricciones en la columna RHS, una columna vacía llamada Theta que ya llenaremos. Las dos ultimas filas son para determinar que variable va a entrar a la base. Algunas personas omiten la fila Z. Realmente no es necesaria, sólo para dar un poco más de claridad a la iteración.

...