Programación Lineal Archivos - Página 12 de 16

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.

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.

Cómo lograr un buen desempeño en un curso de Investigación de Operaciones

¿Cómo lograr un buen desempeño en un curso de Investigación de Operaciones?. Esta es una pregunta que usualmente recibimos de nuestros usuarios y probablemente te represente. En el Equipo de Gestión de Operaciones estamos convencidos que esto depende de varios factores y en este artículo te compartiremos nuestra visión al respecto.

1. Participa activamente en la sala de clases: Te recomendamos ser un ente activo del proceso de enseñanza. Si tienes dudas de las materias que el docente este explicando no dejes de preguntar. De seguro tu profesor no tendrá problemas en explicar nuevamente algo que no haya quedado suficientemente claro.

2. Apoya tus estudios con un libro guía: Disponer de un texto guía es una gran ayuda cuando se requiere profundizar en un aspecto teórico de las materias y adicionalmente para revisar casos y ejercicios resueltos. Si cursas un curso introductorio de Investigación de Operaciones te recomendamos conseguir un libro que cubra las principales temáticas del área como la Programación Lineal, Programación Entera, Programación No Lineal y Cadenas de Markov. En nuestra experiencia docente te recomendamos los siguientes textos que los puedes adquirir a precios económicos: Investigacion de Operaciones – Hillier y Lieberman y Investigación de Operaciones, Taha 7° Edición.

3. Explota el potencial de Excel: El tamaño (cantidad de variables de decisión y restricciones) de los modelos de optimización que te sean asignados en clases son generalmente para un fin académico y por tanto no deberías tener inconvenientes en poder implementarlo en Solver o What’sBest!. En nuestro Blog podrás encontrar una serie de artículos que hemos dedicado a estas poderosas herramientas de resolución.

4. Descarga el Libro de Apuntes de Programación Lineal: Nuestro objetivo es ser un apoyo para tus estudios formales de Gestión e Investigación de Operaciones y en este contexto hemos desarrollado un libro de apuntes de programación lineal el cual podrás descargar de forma gratuita si nos recomiendas en las redes sociales.

5. Accede a Recursos Gratuitos para la Investigación de Operaciones: Te recomendamos leer nuestro artículo 7 Recursos Gratuitos para el estudiante de Investigación de Operaciones donde podrás encontrar datos útiles para tus estudios.

Esperamos que estos consejos te ayuden a lograr el objetivo de aprender y en consecuencia aprobar las materias de Investigación de Operaciones.