método simplex de 2 fases Archivos - Página 2 de 2

Método de la M Grande (o Gran M) en Programación Lineal

En el contexto de la aplicación del Método Simplex no siempre es inmediata la obtención de una solución básica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son el Método Simplex de 2 Fases y el Método de la M Grande (o Gran M) el cual abordaremos en este artículo. Para ello consideremos el siguiente modelo de Programación Lineal en 2 variables:

A continuación agregamos las variables no negativas $x_{3}$ (holgura restricción 1), $r_{1}$ (auxiliar restricción 2), $x_{4}$ (exceso restricción 3) y $r_{2}$ (auxiliar restricción 3). El modelo ahora es:

Donde el parámetro M es una constante positiva suficientemente grande para representar una penalización adecuada en la función objetivo. La tabla inicial del método esta dada por:

Antes de continuar con las iteraciones se debe procurar que el costo reducido de las variables $r_{1}$ y $r_{2}$ sean ceros. Para ello multiplicamos por -M la fila 2 y la fila 3 y luego sumamos a la fila 4, obteniendo lo siguiente:

Ahora debemos seleccionar que variable no básica ingresa a la base. El menor costo reducido corresponde a la variable $x_{1}$ en consecuencia dicha variable ingresa a la base. Luego calculamos el mínimo cuociente en dicha columna: $Min \begin{Bmatrix}{\frac{27/10}{3/10}, \frac{6}{1/2}, \frac{6}{3/5}}\end{Bmatrix}=9$ , el cual se alcanza en la fila 1, por tanto la variable $x_{3}$ deja la base. Se actualiza la tabla:

Siguiendo con las iteraciones ahora la variable $x_{2}$ entra a la base. El criterio de factibilidad indica que: $Min \begin{Bmatrix}{\frac{9}{1/3}, \frac{3/2}{1/3}, \frac{3/5}{1/5}}\end{Bmatrix}=3$ la variable $r_{2}$ abandona la base (el pivote se encuentra en la fila 3). Actualizamos la tabla:

Una nueva iteración indica que $x_{3}$ ingresa a la base. El mínimo cuociente en la respectiva columna es: $Min \begin{Bmatrix}{\frac{8}{20/3}, \frac{1/2}{5/3}}\end{Bmatrix}=3/10$ (recordar que se omiten denominadores menores a cero). Ahora el pivote se encuentra en la fila 2 y en consecuencia $x_{4}$ deja la base. Se actualiza la tabla:

Se ha alcanzado la solución óptima con $x_{1}=15/2$ y $x_{2}=9/2$ . Notar que las variables auxiliares (r1 y r2) son no básicas en el óptimo. El valor óptimo es 21/4 (notar que el signo esta cambiado).

Para una mejor comprensión de los resultados alcanzados a continuación se presenta la resolución gráfica del problema haciendo uso del software Geogebra. El dominio de soluciones factibles corresponde a la recta que une los vértices A y B. Adicionalmente se muestra la curva de nivel que pasa por la solución óptima (vértice B).

Teóricamente se espera que en la aplicación del Método de la M Grande las variables auxiliares sean no básicas en el óptimo. Si el modelo de Programación Lineal es infactible (es decir, si las restricciones no son consistentes), la iteración del Método Simplex final incluirá al menos una variable artificial como básica.

Adicionalmente la aplicación de la técnica de la M Grande implica teóricamente que M tiende a infinito. Sin embargo al usar la computadora M debe ser finito, pero suficientemente grande. En específico M debe ser lo bastante grande como para funcionar como penalización, al mismo tiempo no debe ser tan grande como para perjudicar la exactitud de los cálculos del Método Simplex, al manipular una mezcla de números muy grandes y muy pequeños.

Cómo detectar que un Problema de Programación Lineal es infactible con el Método Simplex de 2 Fases

Un problema infactible en Programación Lineal es una situación que se detecta cuando en la aplicación del Método Simplex de 2 Fases el valor óptimo del problema de la Fase 1 es distinto a cero (para continuar a la Fase 2 se requiere que el valor óptimo de la Fase 1 sea cero). Cabe recordar que un problema infactible es aquel cuyo dominio de soluciones factibles es vacío.

Consideremos el siguiente modelo de Programación Lineal en 2 variables que nos permitirá representar dicha situación:

Agregamos las siguientes variables al modelo para aplicar el Método Simplex de 2 Fases: $x_{3} (holgura), x_{4} (exceso), x_{5} (auxiliar)$ .

Definiendo el problema inicial de la Fase 1:

A continuación llevamos el costo reducido de la variable $x_{5}$ a cero, multiplicando por -1 la fila 2 y sumando ésta a la fila 3:

Para favorecer la rapidez de convergencia del método $x_{2}$ entra a la base. Luego calculamos el criterio del mínimo cuociente: $Min \begin{Bmatrix}{\frac{2}{1}, \frac{12}{4}}\end{Bmatrix}=2$ por tanto $x_{3}$ deja la base. Actualizamos la tabla:

Notar que todas las variables no básicas $x_{1}, x_{3}, x_{4}$ tienen costos reducidos mayores o iguales a cero. Adicionalmente las variables básicas $x_{2}, x_{5}$ cumplen con las condiciones de no negatividad. En consecuencia hemos finalizado la Fase 1 del Método Simplex de 2 Fases, sin embargo, el valor de la función objetivo es distinto de cero (en el ejemplo es -4) lo que determina que el problema es infactible.

La siguiente representación gráfica del problema anterior se puede realizar con Geogebra. El área achurada color rojo corresponde a la intersección de los conjuntos de factibilidad definido por la restricción 1 y las de no negatividad. Por otra parte el área achurada color azul es la intersección de los conjuntos de factibilidad definido por la restricción 2 y las de no negatividad. Luego resulta evidente que la intersección de dichos conjuntos (rojo y azul) es vacío, por tanto no existen valores que puedan adoptar las variables de decisión y satisfacer de forma simultanea todas las restricciones del problema.

Método Simplex de 2 Fases en Programación Lineal (Ejercicios Resueltos)

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.