Etiqueta: infactible

En el artículo anterior nos referimos a Cómo resolver un modelo de Programación Lineal con el Método Simplex Dual, siendo ésta una alternativa de resolución cuando al llevar un modelo de Programación Lineal a su forma estándar no se dispone de una solución básica factible inicial.

A continuación tomaremos el mismo ejemplo pero aplicaremos una metodología conocida como Método Simplex de 2 Fases que como el nombre lo sugiere consiste en una variante del Método Simplex que permite abordar esta clase particular de problemas.

Ejemplo Método Simplex de 2 Fases

Para llevar el problema a la forma estándar agregamos las variables de exceso no negativas X4 y X5 para la primera y segunda restricción, respectivamente. El problema queda como sigue:

Sabemos que las variables X4 y X5 no tienen la estructura de la identidad para utilizarlas como variables básicas y en consecuencia no provee un punto de partida válido para realizar las iteraciones.

¿Qué podemos hacer?. Una alternativa es aplicar el Método Simplex Dual pero también podemos utilizar el Método Simplex de 2 Fases. Para ello agregaremos 2 variables artificiales (o variables auxiliares) no negativas que llamaremos X6 y X7 (una para cada restricción) que nos permitirá tener una solución básica factible inicial.

Luego, el método en su Fase I minimiza la suma de las variables auxiliares (en este caso 2 variables). En consecuencia, el problema de la Fase I queda definido por:

Construimos la tabla inicial de la Fase 1:

Para utilizar X6 y X7 como variables básicas necesitamos llevar sus costos reducidos a cero. Para ello realizamos operaciones fila multiplicando la fila 1 por -1 y luego sumando a la fila 3. Repetimos el procedimiento multiplicando por -1 la fila 2 y sumando a la fila 3. La tabla actualizada corresponde a:

Continuando con las iteraciones del Método Simplex ingresamos la variable X3 a la base (criterio: variable no básica con costo reducido más negativo) y realizamos el mínimo cuociente: Min{1/4; 3/2/2}=1/4 ==> el pivote se encuentra en la fila 1 por tanto deja la base la variable básica X6 (variable básica asociada a la fila 1).

Se realiza una iteración del Método Simplex y se actualiza la tabla:

Ahora las variables no básicas con costo reducido negativo son X1 y X4. Hacemos entrar a la base a la variable X1 y calculamos el mínimo cuociente: Min{1/4/1/2; 1/1}=1 ==> el pivote esta en la fila 1 y por tanto la variable X3 deja la base. En este punto es importante destacar un aspecto: «es una situación inusual (pero no por ello incorrecto) que una variable que en una iteración previa haya ingresado a la base, deje ésta inmediatamente en la iteración posterior». Si bien este es el caso al cual nos enfrentamos continuaremos con las iteraciones del Método Simplex:

IMPORTANTE: El lector podrá identificar que la variable no básica con costo reducido más negativo en la tabla anterior es X2 y por tanto dicha variable debería ser la que ingrese a la base. No obstante de forma involuntaria se omitió dicha situación y se incorporó a la base la variable X1 como se muestra en la tabla a continuación. El efecto de esta decisión sólo tiene que ver con la rapidez de convergencia del Método Simplex y no afecta en absoluto los resultados finales. Esto se puede corroborar revisando tanto este artículo como el que trata sobre Criterios para la Rapidez de Convergencia del Método Simplex. Sin embargo, cabe destacar que no hay garantías que incorporando la variable no básica con el costo reducido más negativo el Método Simplex alcance la solución óptima (de existir) de forma más rápida.

Para seguir con las iteraciones podemos seleccionar tanto la variable X2 como X4 como variables que ingresan a la base (ambas con similar costo reducido negativo). En este caso optaremos por la variable X2 y calculamos el mínimo cuociente: Min{1/2/1/2; 1/2/1}=1/2 ==> X7 deja la base. Actualizamos la tabla obteniendo lo siguiente:

Notar que ahora tenemos una solución básica factible con las variables X1=1/4 y X2=1/2. Adicionalmente todas las variables no básicas (X3, X4, X5, X6, X7) tienen costos reducidos mayores o iguales a cero. Por último y muy importante el valor de la función objetivo al finalizar la Fase I es cero, condición indispensable para seguir a la Fase II del método.

Si el valor de la función objetivo al concluir la Fase I del Método Simplex de 2 Fases es distinto a cero el problema es infactible, es decir, no tiene solución (su dominio de soluciones factibles es vacío).

Para seguir con la Fase II eliminamos la(s) columna(s) asociadas a las variables artificiales y actualizamos el vector de costos reducidos considerando la función objetivo original. Se obtiene en consecuencia la siguiente tabla:

Buscamos ahora llevar a cero el costo reducido a cero para las variables X1 y X2 (variables básicas al finalizar la Fase I). Para ello desarrollamos operaciones fila multiplicando la fila 1 por -1 y luego sumando a la fila 3 (también multiplicamos por -1 la fila 2 y sumando a la fila 3).

Finalmente se logra conservar la estructura de variables básicas para las variables X1 y X2 y las variables no básicas tienen costos reducidos mayores o iguales a cero. En consecuencia estamos frente a la solución óptima del problema con X1=1/4 y X2=1/2.

Te recomendamos verificar que la solución alcanzada es similar a la obtenida a través del Método Simplex Dual pero evidentemente con un esfuerzo en la resolución distinto.