Programación Entera Archivos - Página 2 de 9

Qué es la Programación Entera

¿Qué es la Programación Entera?: Un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo incorporar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

En este sentido los algoritmos de resolución de los modelos de Programación Entera difieren a los utilizados en los modelos de Programación Lineal, destacándose entre ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch & Cut, Planos Cortantes, Relajación Lagrangeana, entre otros.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta (PEM) y Programación Entera Pura (PEP).

Programación Entera Mixta (PEM)

A esta categoría pertenecen aquellos problemas de optimización que consideran variables de decisión enteras o binarias pero no de forma exclusiva. De esta forma un problema de PEM puede considerarse como un híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel que considera la mezcla de variables enteras y variables continuas (estas últimas características de los modelos de Programación Lineal). A modo de ejemplo los siguientes artículos que hemos abordado en el Blog dan cuenta de modelos de Programación Entera Mixta:

Programación Entera Pura (PEP)

En esta categoría encontramos aquellos modelos de Programación Entera que consideran exclusivamente variables de decisión que adoptan valores enteros o binarios. Un ejemplo de ello son las siguientes aplicaciones:

Problema de Asignación
Problema de Corte de Rollos
Selección de Invitados a una Boda
Programación de la Explotación Forestal
Problema de la Mochila

Notar que en los problemas anteriores (PEP) el conjunto de las soluciones factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A continuación se presentan 2 modelos de optimización que se diferencian únicamente en que al segundo de ellos (PE) se le exige que las variables de decisión adopten valores enteros.

Para los problemas propuestos realizamos una representación gráfica haciendo uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal (PL) corresponde al área achurada de color verde. Por otro lado el dominio de soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es un subconjunto del dominio de factibilidad del PL). En este caso en particular la solución óptima de ambos problemas coincide (en el vértice C), no obstante, perfectamente podrían ser distintas (bastaría con modificar los parámetros del problema).

En este contexto y dada la naturaleza de los problemas propuestos, el valor óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del Problema Entero (PE). También se concluye que el dominio de soluciones factibles de un modelo de Programación Lineal (cuando existe) representa un conjunto convexo (los problemas de Programación Lineal son convexos) y en el caso del problema de Programación Entera Pura su conjunto de soluciones factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en cuenta que en la utilización de software para la resolución computacional del modelos de Programación Entera no tendremos acceso a los reportes de sensibilidad como en el caso de la implementación de modelos de Programación Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados ante la modificación de los parámetros del problema será necesario reoptimizar ante la información que brinde el o los nuevos escenarios.

Es importante destacar que las aplicaciones de la Programación Entera no reemplaza la versatilidad que ofrece el disponer de modelos de Programación Lineal. Más aún, se pueden considerar estas categorías de modelamiento matemático como complementarias en el ámbito de la Investigación de Operaciones.

En este sentido en términos abstractos los modelos de Programación Entera imponen un desafío mayor al momento de la resolución en comparación a las propiedades simplificadoras que están asociadas a los problemas de Programación Lineal. De esta forma se espera que el tomador de decisiones sea capaz de evaluar la relación rigurosidad del modelado con el costo (complejidad) de la resolución del mismo.

Qué es la Programación Estocástica

La Programación Estocástica reúne aquellos modelos de optimización en donde uno o más parámetros del problema son modelados a través de variables aleatorias. Una manera de enfrentar esta aleatoriedad consiste en reemplazar los parámetros aleatorios por su valor esperado, lo cual lleva a resolver un problema determinístico de programación matemática, los cuales son de especial interés en cursos introductorios de Investigación de Operaciones y donde la variabilidad inherente a los parámetros se aborda a través del Análisis de Sensibilidad o Postoptimal.

No obstante, la solución obtenida de esta manera puede no ser representativa de la realidad, al no considerar la dispersión de los valores que toman los parámetros en torno al valor esperado, lo cual entre otras cosas puede invalidar su implementación al resultar finalmente escenarios muy diferentes del promedio.

De este modo y en general, una forma de incorporar esta situación de incertidumbre es considerar un número finito de posibles realizaciones o escenarios para los parámetros aleatorios.

El impacto de la incorporación explicita de la incertidumbre en modelos de programación matemática afecta la factibilidad y optimalidad del sistema en estudio. En efecto, la solución que entrega la resolución de un modelo determinista que considera reemplazar los parámetros aleatorios por su valor esperado, puede ser infactible para un escenario en particular.

En este contexto la connotación que tiene el término factibilidad en programación estocástica es más extensa que en el caso determinista, debido a que no se puede garantizar que la solución del modelo estocástico sea factible para todas las posibles realizaciones de la variable aleatoria. Frecuentemente se incluye términos de penalización en la función objetivos que castigan estas posibles infactibilidades ponderada por un cierto costo según se constata por ejemplo en las investigaciones de Sen, S. and Higle, J.L. (1999). Introductory Tutorial on Stochastic Linear Programming Models. Interfaces 29, No.2, 33-61.

En cuanto al impacto que tiene la incertidumbre sobre la optimalidad del modelo formulado se puede observar que a mayor variabilidad de los parámetros aleatorios, el valor que alcanza la función objetivo varía en torno a una media en mayor magnitud. En este sentido la literatura reúne una serie de indicadores que cuantifica este impacto (Birge, J and Louveaux, F (1997). Introduction to Stochastic Programming, Springer – Verlag, New York, USA) de la incorporación explícita de la incertidumbre en la formulación del modelo y permite al tomador de decisiones dilucidar el real impacto de ésta.

Clasificación de los modelos de Programación Estocástica

Los modelos de optimización estocástica se dividen en dos grandes categorías, estos son: Modelos con Restricciones Probabilísticas y Modelos con Recurso. Una referencia general al respecto lo constituye un tutorial desarrollado por Sen y Higle (1999) sobre programación estocástica para el caso lineal y libros como el de Birge y Louveaux (1997).

Modelos con Recursos en 2 Etapas

En un modelo con recurso en dos etapas se pueden distinguir aquellas variables de decisión que son implementadas antes de la realización particular del parámetro aleatorio denominadas de primera etapa o here and now, que se debe tomar antes de conocer la realización de la variable aleatoria, es decir que se escoge tomando en cuenta la aleatoriedad de los parámetros, pero cuyo valor es independiente de la realización particular que finalmente vaya a tomar dicha variable aleatoria. Las variables de primera etapa pueden ser vistas como decisiones proactivas y están asociadas frecuentemente a decisiones estratégicas como la planificación y expansión de sistemas de producción.

En tanto las variables que son determinadas una vez conocida la realización particular de la variable aleatoria son llamadas de segunda etapa o de recurso, es decir, su valor es tomado en respuesta al medio. En este sentido las variables de segunda etapa son de naturaleza reactiva y generalmente están asociadas a decisiones operativas.

Formulación de un Problema de Programación de Explotación Forestal resuelto con Solver de Excel

En el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP) describimos un problema de explotación forestal reducido en términos de la complejidad de un caso de esta naturaleza (de modo de representarlo gráficamente), el cual a continuación extenderemos a través de la incorporación de una serie de decisiones en el tiempo respecto a la actividad de producción, planificación de personal, gestión de inventarios, compra, entre otros. En este contexto considere el caso de una compañía forestal que cosecha (tala) árboles los primeros meses del año. La compañía tiene una serie de pedidos que debe satisfacer cada mes. Estos datos se resumen a continuación:

Al 1 de Enero hay un total de 40 trabajadores y no hay árboles en inventario. La jornada laboral es de 40 horas semanales y 4 semanas laborales al mes. Para cosechar un árbol se requiere 4 horas hombre. Independiente de lo anterior la forestal tiene una capacidad de cosecha de 3.000 árboles mensuales lo cual está dado por la maquinaria disponible.

El sueldo mensual de cada trabajador es de M$400 (el sueldo se paga de forma íntegra ante todo evento, es decir, trabajando la totalidad de horas al mes o menos). La política de la gerencia es no utilizar horas extraordinarias pero si podría comprar árboles a otra forestal cercana a un costo unitario de M$18. Adicionalmente se ha convenido no contratar trabajadores por una fracción de una jornada de trabajo normal (160[horas/mes]). Esto implica que si se contrata un trabajador debe ser por 160[horas/mes] a un costo de M$400 pero no es válido, por ejemplo, contratar un trabajador por 80[horas/mes] a un costo de M$200. El costo de contratar un trabajador es de M$200 y el costo de despedir un trabajador se estima en M$600.

Almacenar un árbol en bodega tiene un costo de M$10 de un mes a otro. Sin embargo, en la bodega no hay espacio para almacenar más de 500 árboles.

Formule y resuelva un modelo de Programación Entera para este problema que permita hallar una política óptima de explotación para la forestal. Indique claramente las variables de decisión del modelo y detalle explícitamente la función objetivo y cada una de las restricciones del modelo.

Variables de Decisión:

Donde t=1,…,6 con t=1 Enero y t=6 Junio.

Función Objetivo: Minimizar los costos durante el período de planificación asociado a las remuneraciones, contratación, despido, compra y mantenimiento de inventario (respectivamente).

Restricciones:

Balance de Trabajadores: Por ejemplo la cantidad de trabajadores disponibles al final del mes de Marzo para labores de cosecha son aquellos que terminaron trabajando al final del mes de Febrero, más los contratados en el mes de Marzo y menos los despedidos en Marzo.

Satisfacer Demanda de Árboles: Donde $D_{t}$ representa la demanda (parámetros) de árboles para el mes t.

Capacidad Tala (Mano de Obra): Talar cada árbol requiere 4 horas hombre y un trabajador aporte 160 horas hombre en un mes. Luego, cada trabajador puede talar como máximo 40 árboles mensuales.

Capacidad Tala (Máquinas): Se puede talar como máximo 3.000 árboles mensuales dada la capacidad de las máquinas.

Capacidad Bodega: La bodega tiene una capacidad máxima de almacenamiento de 500 árboles.

No Negatividad y Enteros: Se deben satisfacer las condiciones de enteros para las variables de decisión no negativas.

Al implementar en Solver de Excel el modelo anterior se alcanza la solución óptima (celdas en color amarillo) con un valor óptimo de M$152.360.

Se recomienda al lector verificar que la solución alcanzada satisface las restricciones anteriormente expuestas. Notar adicionalmente que el plan óptimo actual no despide trabajadores durante la planificación y contrata trabajadores en Febrero y Abril (11 y 19, respectivamente), los mismos meses donde adicionalmente compra árboles (10 y 110) a la forestal cercana. Naturalmente al final de la planificación no existen incentivos para mantener árboles en bodega.

¿Quieres tener el archivo Excel con la implementación computacional de este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Problema de Explotación de Minas y Transporte de Carbón a Puertos

Es frecuente reconocer en los problemas de optimización que representan una estructura productiva, un componente de costo fijo asociado a la utilización de un recurso (dentro de un intervalo de producción relevante) y un costo variable que que asume proporcional al nivel de actividad que represente la unidad productiva (por ejemplo, lo que se refiere a costos de producción, costos de transporte en una red logística, entre otros). Por ejemplo, el Problema de Inclusión de Costos Fijos en Programación Entera representa una situación muy sencilla de lo anteriormente descrito.

En este contexto a continuación se presenta un problema de operación de minas de carbón que su simple utilización tiene asociado un costo fijo, además de incurrir en costos variables por concepto de producción y transporte a distintos puertos demandantes, que adicionalmente tienen requerimientos particulares sobre la calidad del producto recepcionado.

Problema de Explotación de Minas y Transporte

La compañía ABC puede explotar hasta tres minas de carbón y debe realizar envíos a tres puertos. El costo por tonelada de producción (en dólares), el costo fijo de operación en dólares (en caso de ser utilizada), los contenidos de una cierta clase de ceniza y de sulfuro por tonelada y las capacidades de producción (en toneladas de carbón) se resumen en la siguiente tabla:

Por su parte, las toneladas demandadas que deben ser enviadas a cada puerto, conjuntamente con los costos de transporte (en dólares por tonelada) se dan en la siguiente tabla:

Formule y resuelva un modelo de optimización que permita determinar la eventual operación de cada mina y sus niveles de producción, de modo de satisfacer los requerimientos de demanda y que las cantidades enviadas a cada puerto contenga a los más un 4,5% de ceniza y a lo más un 3% de sulfuro.

Variables de Decisión:

Parámetros:

Función Objetivo: Se desea minimizar los costos asociados a la explotación de las minas, el costo de producción del carbón y los costos de transporte del carbón enviado desde las minas a los puertos.

Restricciones:

Capacidad de Producción de las Minas: cada mina puede operar a su capacidad máxima de producción para abastecer los requerimientos de los distintos puertos en caso en que se decida realizar funciones de explotación en la misma.

Demanda de Carbón los Puertos: cada puerto debe recibir la cantidad de toneladas de carbón que demanda.

Máximo Porcentaje de Ceniza admitido por cada Puerto: cada puerto esta dispuesto a recibir como máximo un 4,5% de ceniza en los envíos de carbón que recibe desde las minas. En este caso se expresa dicha condición de forma general a través de parámetros.

Máximo Porcentaje de Sulfuro admitido por cada Puerto: similar al caso anterior pero estableciendo un límite máximo al porcentaje de sulfuro que admite cada puerto (en el ejemplo un 3%).

No Negatividad: las toneladas producidas en las minas y transportadas a los puertos naturalmente deben satisfacer las condiciones de no negatividad.

A continuación de presenta un extracto de la implementación computacional del modelo anterior haciendo uso de Solver de Excel junto a un tutorial de nuestro canal de Youtube con los detalles de la resolución:

Se puede observar que sólo se utilizan las minas 1 y 3. La mina 1 envía 35, 45 y 30 toneladas al Puerto 1, 2 y 3, respectivamente. En el caso de la mina 3, ésta envía 35, 35 y 30 toneladas a los Puertos 1, 2 y 3, respectivamente. La demanda en toneladas de carbón es satisfecha en los puertos y se respeta adicionalmente la capacidad máxima de producción de las minas. Adicionalmente se puede observar en color verde el porcentaje de ceniza o sulfuro (según sea el caso) que recibe cada puerto lo cual satisface las condiciones expuestas. Finalmente el valor óptimo, es decir, el costo mínimo asociado al plan de producción y transporte descrito es de 14.550 dólares.

¿Quieres tener el archivo Excel con la implementación computacional de este problema?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

¿Cómo elegir los invitados de una Boda o Matrimonio con un modelo de Programación Entera?

Elegir los invitados a una boda (matrimonio) no es asunto fácil. Se debe respetar un presupuesto, cumplir compromisos familiares, compatibilizar los invitados de las distintas familias, incluir amigos y compañeros de trabajo y evitar incompatibilidades entre los invitados. El siguiente problema corresponde a una aproximación simplificada a la situación anterior a través de un modelo de Programación Entera. Por cierto las condiciones a incorporar en un problema de esta naturaleza pueden considerar aspectos adicionales como los comentados anteriormente.

Asuma que usted trabaja en una consultora matrimonial y su tarea es seleccionar los invitados para una boda. Tanto la novia como el novio están muy complicados porque tienen amigos que no pueden estar juntos. Los novios han asignado a cada invitado un valor en unidades matrimoniales (u.m) según lo siguiente:

Existen ciertas incompatibilidades que se deben considerar en la planificación que usted como consultor propondrá:

Juan Pérez no asistirá al menos que Luis Toro asista.
Juan Pérez no asistirá si tanto Pedro Soto y María González asisten.
Pedro Soto no asistirá si Gloria Pérez asiste.
Pedro Soto sólo asistirá si María González y Luis Toro asisten.

Formule y resuelva un modelo de Programación Entera que permita determinar a qué personas invitar de modo de lograr la mayor puntuación en unidades matrimoniales.

Variables de Decisión:

Con i=1,2,3,4,5 que representan a Juan Pérez, Pedro Soto, María González, Luis Toro y Gloria Pérez, respectivamente.

Función Objetivo:

Se desea encontrar la selección de invitados a la boda que permita maximizar la puntuación en u.m.

Restricciones:

Juan Pérez no asistirá al menos que Luis Toro asista: $X_{1}\leqslant X_{4}$
Juan Pérez no asistirá si tanto Pedro Soto y María González asisten: $2-(X_{2}+X_{3})\geq X_{1}$
Pedro Soto no asistirá si Gloria Pérez asiste: $X_{2}+X_{5}\leq 1$
Pedro Soto sólo asistirá si María González y Luis Toro asisten: $X_{2}\leqslant X_{3}$ y $X_{2}\leqslant X_{4}$ . En este conjunto de restricciones se entiende que si María González y Luis Toro asisten, Pedro Soto podría asistir. Si al menos uno de los 2 falta (María o Luis) entonces Pedro no asiste.

Al implementar el modelo anterior en Solver de Excel se alcanza un valor óptimo de 800 u.m el cual corresponde a invitar a Pedro Soto, María González y Luis Toro (solución óptima).