método simplex Archivos - Página 5 de 7

Cambio de Variables en un Modelo de Programación Lineal

Cuando se desea resolver un modelo de Programación Lineal es importante tener en cuenta que generalmente se dispone de varias alternativas las cuales difieren en dificultad y por tanto es necesario evaluar cada una en su mérito para luego decidir qué estrategia algorítmica utilizar.

Este concepto es válido tanto para la resolución de pequeños modelos de optimización lineales como los que usualmente se consideran para fines académicos, como también para modelos de mayor tamaño, donde seleccionar una estrategia adecuada favorece los tiempos y confiabilidad de la resolución computacional.

A continuación presentaremos un problema de Programación Lineal en 2 variables que resulta de interés su resolución:

Notar que existen distintas estrategias que nos permiten abordar el problema anterior. Por ejemplo, lo podríamos resolver gráficamente (Método Gráfico en Programación Lineal) o utilizar el Método Simplex de 2 Fases, agregando variables de holgura para las restricciones 1, 2 y 3 y variables de exceso y auxiliares para las restricciones 4 y 5. También por cierto se podría definir el Problema Dual del ejemplo anterior y luego intentar su resolución, lo que a primera vista no sería de mayor ayuda.

Ahora bien, si una variable de decisión x debe cumplir la restricción x≥a, para una constante a positiva, se puede imponer un cambio de variables y=x-a, que define una nueva variable y que tiene solo una restricción de no negatividad y simplifica imponer la primera como una restricción general en la aplicación del Método Simplex.

El concepto anterior nos permite hacer lo siguiente: Y1=X1-20>=0; Y2=X2-20>=0. Es decir X1=Y1+20 y X2=Y2+20. En consecuencia podemos reescribir el modelo original de la siguiente forma:

Reduciendo términos semejantes se obtiene:

Notar que este nuevo modelo de optimización se puede resolver de forma directa a través del Método Simplex, incorporando las variables no negativas Y3, Y4 e Y5 como holguras de las restricciones 1, 2 y 3, respectivamente. De esta forma el problema en su forma estándar proporciona la siguiente tabla inicial: (Notar que el valor de la función objetivo inicialmente es 1.100 debido a que dicha constante se obtiene luego de realizar el cambio de variables)

La variable Y1 entra a la base al ser la variable no básica con el costo reducido más negativo. Luego para determinar la variable básica que deja la base calculamos el mínimo cuociente: Min {420/6; 140/1; 160/2} = 70 ==>Y3 sale de la base. Se realiza una iteración del Método Simplex:

Ahora Y2 entra a la base al ser la única variable no básica con costo reducido negativo. A continuación la variable que deja la base se determina a través del criterio del mínimo cuociente: Min {70/1/2; 70/3/2; 20/1} = 20 ==>Y5 sale de la base. Se realiza una nueva iteración:

Se ha alcanzado la tabla óptima donde Y1=60 e Y2=20 con valor óptimo V(P)=3.400. Reemplazando en las variables originales se obtiene la solución óptima del problema original: X1=60+20=80 y X2=20+20=40. Se puede corroborar que esta solución óptima al ser evaluada en la función objetivo del problema inicial proporciona el valor óptimo del modelo de programación lineal: Max 30*(80)+25*(40)=3.400, lo que permite garantizar la equivalencia del procedimiento utilizado.

Incorporar Nueva Restricción (Análisis Postoptimal Programación Lineal)

Una vez resuelto un modelo de Programación Lineal puede resultar de interés si la actual solución óptima y valor óptimo se conservaran si se decide incorporar una nueva restricción al problema. Esta restricción generalmente representa una condición que en primera instancia se omite de forma voluntaria para dar una mayor flexibilidad a la resolución del modelo original o alternativamente su no inclusión en el modelo original puede también deberse a una simple omisión (involuntaria).

Consideremos el siguiente modelo de Programación Lineal que hemos resuelto en un artículo previo a través del Método Simplex:

La tabla final óptima que considera las variables s1, s2 y s3 como las respectivas holguras de las restricciones del problema es:

Por ejemplo, consideremos que se desea incorporar una nueva restricción definida por la siguiente expresión: 3X+Y<=600. ¿Cambia la actual solución óptima y valor óptimo?.

Para responder a lo anterior se recomienda evaluar la actual solución óptima en la nueva restricción; si ésta se cumple entonces el modelo conserva su solución óptima y valor óptimo; en caso contrario la solución óptima actual será infactible y se debe incorporar esta situación en el modelo original para encontrar la nueva solución del mismo. Notar que también puede suceder que al agregar una nueva restricción que no satisface la solución actual el problema podría resultar ser infactible al tener un dominio de soluciones factibles vacío.

En nuestro ejemplo al evaluar obtenemos: 3(100)+(350)<=600, es decir, la solución óptima actual es infactible al incorporar esta nueva restricción.

Para incorporar esta modificación en la tabla final del Método Simplex agregamos una nueva fila y una nueva columna asociada a una variable s4>=0 que será la holgura de la nueva restricción. La tabla queda de la siguiente forma:

Las variables básicas del problema original son x, s2 e y, respectivamente. Al incorporar la nueva restricción (fila) tanto x como y pierden la estructura de la identidad característica de las variables básicas. Por ello para formar la base podemos realizar operaciones fila multiplicando por -3 la fila 1 y sumando ésta a la fila 4. Posteriormente multiplicar por -1 la fila 3 y sumar a la fila 4:

Ahora las variables básicas son x, s2, y, s4 (enumeradas en el orden en el cual aparecen en la identidad), sin embargo, la variable s4 toma un valor de -50 lo cual no corresponde a una solución básica factible.

¿Cómo continuar con las iteraciones?. Utilizando el Método Simplex Dual se recomienda corroborar que la nueva solución óptima corresponde a x=250/3 e y=350.

Adicionalmente podemos utilizar un enfoque de Resolución Gráfica para el problema anterior. El siguiente gráfico representa la resolución del escenario inicial donde la solución básica factible óptima se alcanza en el vértice C con x=100 e y=350.

Al incorporar la nueva restricción (recta color rojo) el dominio de soluciones factibles se ve reducido, donde ahora ya no son factibles los puntos en el polígono con área achurada color verde (donde se puede verificar que el vértice C es infactible).

Si se resuelve gráficamente sobre el nuevo dominio (área achurada color naranjo) las curvas de nivel de la función objetivo (recta punteada color azul) pasa por última vez en el vértice F donde x=250/3 e y=350 como solución óptima del nuevo problema.

Incorporar nueva variable en un Modelo (Análisis de Sensibilidad en Programación Lineal)

Una vez resuelto un modelo de Programación Lineal a través del Método Simplex puede resultar de interés analizar si cambia la solución óptima y valor óptimo del problema luego de incluir una nueva variable de decisión.

Por ejemplo, en un Problema de Producción esta nueva variable generalmente representa la evaluación de un nuevo producto no considerado inicialmente donde es útil saber cuál sería su impacto en los resultados del modelo sin la necesidad de reoptimizar.

Este tipo de análisis corresponde al Análisis de Sensibilidad en Programación Lineal y a continuación presentaremos un ejemplo de este escenario.

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:

Consideremos adicionalmente que las variables x e y representan 2 productos y sus respectivos coeficientes en la función objetivo representan el ingreso asociado a su venta. En este contexto, en el plan actual se producen 100 unidades de x y 350 unidades de y, con un ingreso total de $3.100 (valor óptimo).

Asumamos que nos interesa analizar si conviene la fabricación de un tercer producto (llamado z) que tiene un ingreso unitario por venta de $5 y que para su fabricación requiere de 3, 1 y 1 unidad de los recursos asociados a las restricciones R1, R2 y R3, respectivamente.

Más aún, nos interesa dar respuesta a esta interrogante sin tener que resolver desde cero este nuevo problema. Si este es nuestro objetivo podemos utilizar el Análisis Postoptimal donde en particular calcularemos el costo reducido de esta nueva variable dado sus parámetros.

Si dicho costo reducido resulta ser negativo implica que la solución óptima actual deja de serlo al considerar este cambio y por tanto se puede buscar el nuevo óptimo utilizando la solución actual como punto de partida.

La fórmula del costo reducido para la nueva variable está dada por:

Donde la notación corresponde a:

Aplicando las definiciones anteriores a nuestro ejemplo se obtiene lo siguiente:

Notar que el costo reducido para esta nueva variable es 3/2>=0 lo que significa que la solución óptima actual se mantiene si se incluye esta nueva variable al modelo (donde la variable z sería una variable no básica con valor cero).

¿Cuánto debería ser como mínimo el ingreso asociado a la nueva variable z de modo que si sea conveniente su producción y por tanto cambie la solución óptima actual?.

Responder esta interrogante consiste en determinar cuál debiera ser el valor de Cj para que Rj<0 y entonces la variable z al tener costo reducido negativo entra a la base y se continua con las iteraciones.

Por simple inspección y evaluando en la fórmula anterior se puede corroborar que el ingreso mínimo para dicha variable debería ser un valor mayor a 13/2. Por ejemplo, asumamos ahora que el ingreso unitario de la variable z es $7. El nuevo costo reducido sería -1/2 y se actualiza la tabla final del Método Simplex quedando de la siguiente forma:

Se pueden continuar con las iteraciones del Método Simplex incorporando la variable z a la base y luego calculando el mínimo cuociente entre {400/2; 350/1}=200 ==> s1 deja la base. Al actualizar la tabla se obtiene la nueva solución básica factible óptima y valor óptimo:

Ahora x=200, y=150, z=200, con valor óptimo V(P)=3.200. Puedes corroborar los resultados revisando nuestro tutorial Cómo resolver un modelo de Programación Lineal con el Método Simplex.

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:

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.