Método de la Gran MINVESTIGACIÓN OPERATIVA

Introducción:

Mientras que los Programas  Lineales que solo tienen restricciones de <= se pueden resolver sólo usando variables de holgura, para aquellos programas lineales que involucren restricciones de tipo >= e = es necesario como ya lo habíamos comentado, usar variables artificiales.

Las  variables  artificiales no tenían ninguna representación física y que sólo son usadas como un comodín matemático para ayudar en la solución del problema. Pues bien, cuando tenemos que usar variables artificiales al tener restricciones de >= e = debemos usar uno de las siguientes variantes del simplex:

- Método de la gran M

- Método de las dos fases

Definición:

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

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 así:

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. 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.

Llenar la tabla inicial.

Tal como se ve en la tabla de abajo.

Hay muchos formatos de tablas,

pero en esencia son el mismo.

4. Definir la Variable que sale

Para establecer que variable debe salir de la base, hacemos un cociente entre la disponibilidad (RHS) y la columna de la variable que entra, en nuestro caso, acabamos de decir que es la variable X3. Este cociente lo vamos a llamar Theta. Algunos libros lo llaman 'ratio'. 

   10 /2 = 5

   6 / 3  = 2

   9 / -1 = ... bueno, en caso que dividamos por un valor negativo, no lo vamos a tener en cuenta para salir, por lo que lo rotulamos como M.

   7/2   = 3.5

 

La variable que más nos restringe, por lo tanto la que el valor de theta es menor (pero positivo) es de 2, correspondiendo a la variable A1. Por lo tanto sale A1 y entra X3.

5. Iteración Gauss-Jordan

Luego que se ha encontrado que variable sale de la base, y cual entra y que por lo tanto ya tenemos una celda pivote, es necesario realizar la eliminación gaussiana. Ello lo podemos resumir como: 

  Convertir la celda pivote en 1, dividiendo toda la fila por ella misma

  Convertir todas las celdas por  encima y por debajo de la celda pivote en cero.

Vamos paso por paso: Convertir la celda pivote en 1.

Llenamos un formato vacío simplex,  la fila que contiene el pivote la vamos a pasar al nuevo formato convertida mediante la siguiente operación: dividimos toda la fila por el valor del pivote. (Para convertir el pivote en 1).

1/3  =  0.33

-2/3 =  -0.67

3/3  = 1(Pivote)

0/3= 0

-1/3= -0.33

1/3=0.33

0/3=0

0/3=0

6/3= 2 (En la columna del RHS) 

 Y la pasamos al nuevo formato (fig 3).

Esta nueva fila que hemos calculado va a servir para convertir las demás celdas por la columna del pivote en cero, como es el requisito del método.

Fijémonos un momento en la fig 2, en el pivote en verde, que contiene el 3, precisamente el que acabamos de convertir en 1. Por encima encontramos el 2 y por debajo encontramos el -1 y el 2. Estos valores son los que debemos convertir en ceros. 

6. Prueba de Optimidad

 La prueba de optimidad se debe hacer cada vez que se evalúa si hay una variable que debe entrar a la base. Y es sencillamente lo siguiente. Se hace la pregunta: Hay alguna variable que al entrar mejora la solución?

Ello lo vemos en la fila Cj-Zj. Si al calcular esta fila aún hay valores negativos y estamos minimizando, entonces es posible mejorar aún más la solución. Lo mismo para el caso de la maximización. Si hay valores positivos en la fila Cj-Zj y estamos maximizando, aún no hemos llegado al óptimo. 

En la fig 2 nos damos cuenta que habían todavia valores negativos en Cj-Zj, por lo tanto no se había terminado, ahora en la fig 3, aún quedan valores negativos, el más negativo de ellos esta en la variable X2 por lo tanto debe entrar.

Continuando el algoritmo en la fig3 evaluamos que la variable A2 debe salir, la reemplazamos en el tablero de la figura 4. Hacemos gauss-jordan, luego calculamos Z y calculamos Cj-Zj. 

Aquí en el tablero de la figura 4, evaluamos si hay algun valor negativo en la fila Cj-Zj, nos damos cuenta que no, por lo que no hay ninguna variable que al entrar mejore la solución.

Hemos llegado al óptimo: La solución es Z=9.8571 X1=0 (Por que no estaba en la base.)  X2= 1.29, X3=2.86