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

Cambio en el Lado Derecho de las Restricciones (Programación Lineal)

El vector del lado derecho asociado a las restricciones de un modelo de Programación Lineal puede tener distintas interpretaciones prácticas como, por ejemplo, la disponibilidad de insumos para la fabricación de determinados productos, limitantes de capacidad, requisitos de demanda, entre otros.

En consecuencia resulta de interés analizar el impacto del cambio de uno o varios coeficientes del vector de lado derecho sobre los resultados originales del modelo sin la necesidad de reoptimizar, es decir, sin que tener que resolver nuevamente un modelo que incorpore los cambios propuestos.

En este contexto, si en particular se verifica que:

Se puede afirmar que se conserva la actual base óptima. Lo anterior implica que las variables básicas del modelo lo seguirán siendo bajo este nuevo escenario y por tanto la nueva solución óptima del problema se podrá encontrar a través de la resolución del mismo sistema de ecuaciones original (se conservan las restricciones activas originales).

Ahora bien, si alguno de los coeficientes en el cálculo del vector de variables básicas adopta un valor negativo, estamos frente a una solución básica infactible, lo que nos obliga a realizar una actualización de los resultados del modelo para encontrar la nueva solución, base óptima y valor óptimo, pero que no pase por la reoptimización del mismo.

Consideremos el siguiente modelo de optimización:

Al resolver este modelo de Programación Lineal con el Método Simplex se alcanza la siguiente tabla final, donde s1, s2 y s3 son las variables de holgura de las restricciones 1, 2 y 3, respectivamente:

Las variables básicas son x=100, s2=400, y=350, donde todas satisfacen las condiciones de no negatividad (es decir es una solución básica factible) y además el costo reducido de las variables no básicas (s1 y s3) son mayores o iguales a cero, condición necesaria y suficiente junto a lo anterior para garantizar que nos encontramos frente a la solución óptima del problema (solución básica factible óptima).

Adicionalmente y en relación a la proposición anterior se pueden corroborar los resultados obtenidos:

Consideremos ahora que el lado derecho de la restricción 1 cambia de su valor original 1600 a 1650. ¿Cambia la actual base óptima?. Para ello recalculamos el vector de las variables básicas:

Se puede apreciar que todos los coeficientes del vector de variables básicas (Xb) son mayores o iguales a cero, es decir, se conserva la base óptima (idénticas variables básicas) pero la solución óptima cambia a x=125, s2=250, y=350.

Adicionalmente el valor óptimo ahora es V(P)=3.175. Sin embargo, no es necesario seguir realizando iteraciones del Método Simplex (dado que estamos frente a una solución básica factible óptima) y nos ahorramos el trabajo de la reoptimización.

La pregunta natural es ¿Qué sucede si al actualizar el vector de las variables básicas al menos una de las variables toma un valor negativo?. Modifiquemos ahora en forma simultanea los lados derechos de las restricciones 1 y 2 a 2.000 y 1.500, respectivamente. El nuevo vector de variables básicas queda definido de la siguiente forma:

Notar que ahora la variables básica s2=-1.000 adopta un valor que no satisface la condición de no negatividad para las variables de decisión. Al definir lo anterior una situación de infactibilidad es necesario actualizar la tabla final del Método Simplex con el valor de las variables básicas y el valor de la función objetivo:

Para encontrar la solución óptima de este problema a partir de la tabla anterior se puede aplicar el Método Simplex Dual. La variable básica que deja la base es s2 (variable básica asociada a la fila 2 donde encontramos el «lado derecho» negativo).

Para determinar la variable que entra a la base calculamos el mínimo cuociente: Min{-3/2/-3}=1/2 ==> s1 entra a la base. Actualizamos la tabla del Método Simplex obteniendo lo siguiente:

Se puede apreciar que sólo fue necesario realizar una iteración adicional para poder obtener la solución óptima del nuevo escenario (x=400/3, s1=1.000/3, y=350) con un valor óptimo de V(P)=3.200.

El siguiente gráfico realizado con el software Geogebra permite visualizar la nueva solución óptima y estructura del problema, donde ahora la solución óptima se encuentra con las restricciones 2 y 3 activas (el problema original en su solución óptima consideraba la restricción 1 y 3 como activas):

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.

Método Simplex Dual en Programación Lineal (Ejercicios Resueltos)

El Método Simplex Dual nos ofrece una alternativa algorítmica para abordar la resolución de modelos de Programación Lineal. En particular este método se puede utilizar cuando luego de llevar a la forma estándar un modelo de Programación Lineal no se dispone de una solución básica factible inicial con la cual se pueda dar inicio a las iteraciones del algoritmo. En este contexto a continuación se presenta un ejemplo con los detalles de la aplicación de este procedimiento.

Ejemplo del Método Simplex Dual

Consideremos el siguiente problema para ilustrar sobre la aplicación del Método Simplex Dual:

Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de exceso no negativas para la restricción 1 y 2, que llamaremos respectivamente X4 y X5. De esta forma el problema en su formato estándar queda definido por:

Luego construimos la tabla inicial del Método Simplex:

¿Cómo continuar con las iteraciones del Método Simplex?. Antes de ello es necesario disponer de una solución básica factible inicial. En este contexto si quisiéramos usar X4 y X5 como variables básicas (y en consecuencia X1, X2 y X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales a cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por tanto no se dispone de la identidad (matriz con «1» como diagonal y el resto de coeficientes igual a cero).

En consecuencia para formar la identidad podemos multiplicar por «-1» la fila 1 y 2, obteniendo lo siguiente:

En la tabla anterior se tiene una solución básica (infactible en las variables primales), pero al tener costos reducidos no negativos esto define una solución básica factible en el dual.

Ahora X4 y X5 son variables básicas y adoptan los valores de -1 y -3/2, respectivamente, lo que claramente no satisface las condiciones de no negatividad para las variables de decisión, es decir, no corresponde a una solución básica factible.

Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como alternativa de resolución. Para ello seleccionaremos una variable que deje la base y adoptaremos como criterio de selección aquella variable básica asociada al lado derecho «más negativo» (con esto se busca favorecer la rapidez de convergencia).

En el ejemplo dicha variable es X5. Luego para determinar que variable entra a la base realizamos un mínimo cuociente entre el negativo del costo reducido de las variables no básicas y las entradas estrictamente menores a cero para las variables no básicas en la fila 2 (fila asociada al lado derecho más negativo).

Es decir: Min{-160/-2; -120/-2; -280/-2}=60 ==> el cuociente mínimo se alcanza en la segunda columna asociada a la variable no básica X2, por tanto dicha variable entra a la base.

En cada iteración del Método Simplex Dual se escoge un lado derecho con valor negativo, identificando la respectiva variable básica primal, quien deja la base.

Finalmente se realiza una iteración realizando las operaciones filas que sean necesarias, de modo de ingresar X2 a la base al mismo tiempo que X5 deja la base. Los resultados serían:

Notar que ahora las variables básicas son X4 y X2 donde sólo X4=-1/4 lo que no satisface la condición de ser una solución básica factible. Por lo tanto realizamos una nueva iteración, en este caso sacando de la base a la variable X4 y calculamos el mínimo cuociente: Min{-40/-1; -160/-3; -60/-1/2}=40 ==> el cuociente mínimo está en la primera columna por tanto la variable X1 entra a la base.

En consecuencia se actualiza la tabla quedando lo siguiente:

Las variables básicas ahora son X1=1/4 y X2=1/2 (que cumplen las condiciones de no negatividad). Adicionalmente el costo reducido de las variables no básicas también es mayor o igual a cero, por tanto estamos frente a la solución óptima del problema.

Se puede reconocer adicionalmente que el valor óptimo es V(P)=100 que se obtendría al evaluar la solución óptima del problema en la función objetivo, sin embargo, en el procedimiento dicho valor se obtiene con signo cambiado.

El ejemplo anterior nos permitió apreciar cómo a través del Método Simplex Dual se puede abordar la resolución de un modelo de Programación Lineal que luego de ser llevado a la forma estándar no provee una solución básica factible inicial.

Cabe destacar que el Método Simplex Dual que no es la única alternativa algorítmica a la cual podemos recurrir para resolver el problema propuesto. Por ejemplo, podríamos haber alcanzado idénticos resultados aplicando el Método Simplex de 2 Fases con algo más de trabajo.

Alternativamente podríamos definir el modelo dual al problema propuesto y resolverlo por el Método Simplex para posteriormente utilizar las condiciones del Teorema de Holguras Complementarias.

En resumen ante un modelo de optimización contamos con varias alternativas de resolución y es deber de quien resuelve evaluar los distintos caminos en términos de su complejidad y representación.