programación lineal Archivos - Página 12 de 17

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.

Relaciones de Dualidad en Programación Lineal (Pasar de Primal a Dual)

El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal.

En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

Primal Minimización – Dual Maximización

Por ejemplo, leyendo la tabla desde izquierda a derecha, es decir, pasar de un problema primal de minimización a un problema dual de maximización, tenemos:

Si el problema primal es de minimización, entonces su correspondiente dual será uno de maximización.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Primal Maximización – Dual Minimización

De forma análoga, interpretando la tabla desde derecha a izquierda, es decir, pasar de un problema primal de maximización a un problema dual de minimización, tenemos:

Si el problema primal es de maximización, entonces su correspondiente dual será uno de minimización.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Ejemplo Relaciones de Dualidad en Programación Lineal

A continuación presentamos un modelo de optimización que consideraremos como el problema primal y que en un artículo previo fue resuelto a través del Método Simplex de 2 Fases.

Como en este caso el problema primal es de minimización, para definir su respectivo problema dual leeremos la tabla que resume las relaciones de dualidad desde izquierda a derecha. En consecuencia, el problema dual será uno de maximización.

Adicionalmente la primera y segunda restricción del problema primal definirán las variables de decisiones (variables duales) en el problema dual (Y1 e Y2, respectivamente), siendo los coeficientes en la función objetivo los actuales valores de los lados derechos de las restricciones del problema primal.

De esta forma la función objetivo del problema dual queda definida por la siguiente expresión:

Luego por cada variable en el problema primal vamos a tener la misma cantidad de restricciones en el problema dual. En este caso las variables X1, X2 y X3 definirán la estructura de las restricciones 1, 2 y 3 en nuestro problema dual. Por ejemplo la primera restricción del problema dual (asociada a la variable primal X1) sería 2Y1+2Y2<=160.

Notar que los coeficientes que ponderan a las variables duales son los parámetros asociados a la variable X1 en el primal en la primera y segunda restricción, respectivamente. La restricción en el dual es del tipo “<=” debido a que la variable X1 en el problema primal de minimización tiene la condición de no negatividad (“>=0”). Por último el lado derecho de la restricción es el coeficiente que tiene la variable X1 en la función objetivo del problema primal. Siguiendo el procedimiento las restricciones del problema dual serían:

Finalmente como las 2 primeras restricciones del problema primal son del tipo “>=” en el problema primal de minimización, las respectivas variables duales asociadas en el problema de maximización serán no negativas. De esta forma el problema dual es:

Ejercicio Propuesto: Utilizando las relaciones de dualidad en Programación Lineal, dado un problema primal P, demuestre que su correspondiente dual D queda definido de acuerdo a:

En lo que sigue, combinaremos las distintas restricciones del problema primal, ponderando por los valores no negativos $\pi_{1},\pi_{2}$ y $\pi_{3}$ cada una, respectivamente, de modo de obtener la mejor cota superior del valor óptimo del problema P). Vale decir:

De modo de garantizar que el lado derecho de esta última desigualdad sea una cota superior de la función objetivo del problema primal se debe cumplir que:

$2\pi_{1}+\pi_{2}+\pi_{3}\geq 40$

$\pi_{1}+\pi_{2}+3\pi_{3}\geq 60$

La mejor elección de esta cota se obtendría al resolver el siguiente problema de optimización:

Este problema se conoce como el problema “Dual” D) asociado al problema “Primal” P).

También resulta que al formular el problema dual de D) se obtiene el problema primal P) (o uno equivalente). Cualquiera de los dos entrega la misma información y el valor óptimo alcanzado es el mismo.

Modelo de Transporte con Transbordo resuelto con Solver de Excel

Una de las aplicaciones clásicas de la Investigación de Operaciones y en particular de la Programación Lineal es proponer alternativas óptimas para el proceso logístico o transporte de insumos o productos desde un conjunto de oferentes hasta un conjunto de destinatarios o demandantes.

Cuando consideramos que en este proceso de transporte pueden participar intermediarios estamos frente a una extensión del modelo básico de transporte el cual es comúnmente conocido como Modelo de Transporte con Transbordo. A continuación presentaremos un caso aplicado de dicho modelo.

Ejemplo Problema de Transporte con Transbordo

Se deben transportar 20 millones de barriles de petróleo desde Dhahran en Arabia Saudita a las ciudades de Rotterdam, Marsella y Nápoles en Europa. Las demandas de estas tres ciudades son 4, 12 y 4 millones de barriles, respectivamente. A continuación se presenta un diagrama con las posibles rutas:

Observe que para cada ciudad existe la posibilidad directa de envío, es decir, que los barriles sean transportados directamente desde Dhahran. Sin embargo, la ruta que une Dhahran y Marsella no puede transportar más de 3 millones de barriles debido a ciertos acuerdos comerciales.

Por otro lado, existe la posibilidad que se realice una detención, ya sea en el puerto de Alejandría o Suez, donde la capacidad de almacenamiento es de 8 y 10 millones respectivamente.

Por último, observe que es posible enviar barriles de petróleo desde Marsella a Nápoles. Sin embargo, le está prohibido a Nápoles recibir más petróleo de Marsella que directamente de Dhahran. Formule y resuelva un modelo de Programación Lineal que permita hallar la política óptima de transporte para cumplir con los requerimientos de demanda de los puertos.

Variables de Decisión:

X1: Barriles transportados desde Dhahran a Rotterdam
X2: Barriles transportados desde Dhahran a Marsella
X3: Barriles transportados desde Dhahran a Nápoles
X4: Barriles transportados desde Dhahran a Alejandría
X5: Barriles transportados desde Dhahran a Suez
X6: Barriles transportados desde Alejandría a Rotterdam
X7: Barriles transportados desde Alejandría a Marsella
X8: Barriles transportados desde Suez a Marsella
X9: Barriles transportados desde Suez a Nápoles
X10: Barriles transportados desde Marsella a Nápoles

Función Objetivo:

Minimizar los costos totales de transportes dados por la siguiente expresión: 7X1 + 8X2 + 15X3 + 6X4 + 5X5 + 8X6 + 7X7 + 2X8 + 6X9 + 1X10

Restricciones:

Satisfacer la Demanda en los Puertos:

X1 + X6 = 4.000.000 (Rotterdam)
X2 + X7 + X8 – X10 = 12.000.000 (Marsella)
X3 + X9 + X10 = 4.000.000 (Nápoles)

Notar que Marsella eventualmente podría recibir más de 12 millones de barriles de petróleo (su demanda) debido a que este Puerto tiene la posibilidad de abastecer a Nápoles.

Balance en el Transbordo:

X4 = X6 + X7 (Alejandría)
X5 = X8 + X9 (Suez)

La cantidad de barriles que recibe Alejandría y Suez debe ser igual a lo que cada uno de ellos despacha a los Puertos, es decir, los intermediarios no acumulan inventario al final del periodo de planificación. En este punto es importante destacar que si se considera un modelo extendido donde se busca satisfacer los requerimientos de demanda de varios periodos podría ser admisible almacenar inventario en Alejandría y Suez, cambiando en este caso la forma del modelo de optimización.

Capacidad de Procesamiento en el Transbordo:

X4 <= 8.000.000 (Alejandría)
X5 <= 10.000.000 (Suez)

Tanto Alejandría como Suez no pueden recibir una cantidad de barriles mayor a la que pueden procesar.

Capacidad Ruta entre Dhahran y Marsella:

X2 <= 3.000.000

La ruta que une Dhahran y Marsella no puede transportar más de 3 millones de barriles por acuerdos comerciales.

Cantidad Recibida por Nápoles:

X3 >= X10

Está prohibido a Nápoles recibir más petróleo de Marsella que directamente de Dhahran.

No Negatividad:

Xi >= 0 Para todo i

Al implementar el modelo anterior con Solver de Excel se obtienen los siguientes resultados:

Donde la solución alcanzada tiene la siguiente estructura (sobre los arcos se detalla el valor de la solución óptima):

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.

Hemos Alcanzado 1.000 Suscritos al Newsletter de Gestión de Operaciones!

En esta oportunidad desarrollaremos un tema que se podría considerar “off-topic” dado que no aborda un tema en particular de la Gestión o Investigación de Operaciones pero que para nuestro equipo nos parece muy importante compartir con nuestros valiosos usuarios. Con fecha 31 de Marzo de 2013 hemos alcanzado la cantidad de 1.000 suscritos a nuestro newsletter, quienes han decidido formar parte de nuestra comunidad de usuarios al descargar en forma gratuita el Libro de Apuntes de Programación Lineal. Los suscritos al newsletter además reciben en forma periódica información útil para sus estudios como planillas de cálculo, ejercicios resueltos, sugerencias, entre otros. Esta información la enviamos sin ningún costo para el usuario y con una frecuencia aproximada de un correo a la semana a través de los servicios de Email Marketing de AWeber.

Para dar testimonio de este importante hito para nuestro sitio hemos realizado una captura de pantalla de nuestro contador de suscritos:

Nuestros suscritos son principalmente estudiantes de países de habla hispana que cursan estudios de las asignaturas de Investigación de Operaciones y Gestión de Operaciones. Naturalmente los nombres de los cursos pueden variar dependiendo de cada casa de estudios y país pero en esencia representan lo mismo. Diariamente recibimos correos con consultas y comentarios los cuales agradecemos y nos incentiva a seguir adelante con esta iniciativa. Si aún no te has suscrito lo puedes completando el formulario a continuación:

Adicionalmente te puedes suscribir a los nuevos artículos del Blog ingresando tu email en el formulario que aparece en la barra lateral derecha de nuestro sitio. De esta forma cada vez que se publique un nuevo artículo serás notificado en tu correo.

Finalmente te queremos informar que hace un par de días hemos habilitado una herramienta que permite compartir y recomendar los contenidos del Blog a través de las redes sociales. Esta opción la podrás encontrar en el resumen de la publicación de cada artículo y al final de cada uno de ellos. Se verá como la imagen a continuación:

Si los contenidos de nuestro sitio te han resultado útiles en alguna medida te queremos pedir un favor: “Comparte y recomienda nuestros artículos con tus compañeros de curso o amigos”. Saber que el Blog es valioso para nuestros usuarios y que al mismo tiempo éste comienza a ganar popularidad es para nosotros el principal incentivo para seguir adelante. También puedes enviar tus comentarios completando el formulario al final de este artículo!. Adelante! queremos escuchar tu opinión.

Saludos y Gracias!

El Equipo de Gestión de Operaciones

Importante: Si tienes un sitio web sobre cualquier temática y te interesa ver el potencial de un newsletter te recomendamos crear una cuenta en AWeber accediendo a través del siguiente banner. Actualmente con 1.000 suscritos pagamos US$29 mensuales (US$19 la mensualidad más US$10 mensual por tener más de 500 suscritos). Las ventajas y beneficios al contar con una lista de suscriptores superan largamente el costo económico del servicio.