programación entera Archivos - Página 3 de 9

Problema de Inclusión de Costos Fijos en Programación Entera

La estructura de cobro utilizadas en general por las compañías de servicios donde el cliente debe pagar un valor fijo sólo por su utilización (independiente del nivel de consumo y/o eventualmente acotado a un máximo permitido) y un valor variable proporcional al consumo, son una práctica común en el esquema de fijación de precios. Esto suele ser el caso de las compañías de luz, agua, gas, teléfono, entre otras, donde el sólo hecho de tener una red operativa genera costos para la empresa los cuales son traspasados en parte o en su totalidad a los usuarios en un cargo fijo o de mantención más un cargo variable por consumo.

El artículo que presentamos a continuación busca, desde la perspectiva del cliente, minimizar el pago asociado a una cuenta telefónica mensual a través de un modelo de Programación Entera, lo que constituye un problema de inclusión de costos fijos. Cabe destacar que la complejidad del problema es menor y dado los datos se podría resolver por simple inspección, no obstante, nuestro interés es mostrar un marco de análisis pertinente a este tipo de problemas.

Ejemplo Inclusión de Costos Fijos en Programación Entera

Tres empresas telefónicas pidieron que me suscribiera a su servicio de larga distancia dentro del país. MaBell cobra US$16 fijos por mes, más US$0,25 por minuto. PaBell cobra US$25 por mes, pero el costo por minuto se reduce a US$0,21. Y con PhoneBell, la tarifa fija es de US$18 y el costo por minuto de US$0,22. Suelo hacer un promedio de 200 minutos de llamadas de larga distancia al mes. Suponiendo que no pague el cargo fijo si no hago llamadas y que puedo repartir a voluntad mis llamadas entre las tres empresas, ¿Cómo debo repartir las llamadas entre las tres empresas para minimizar la cuenta telefónica mensual?.

Variables de Decisión:

Función Objetivo:

Donde $F_{i}$ representa el costo fijo mensual asociado a la compañía i y $V_{i}$ el costo variable por minuto de larga distancia nacional correspondiente a la compañía i. Para mayor claridad se ha marcado con color amarillo y verde los elementos de costos fijos y variables (respectivamente) en la función objetivo.

Restricciones:

Donde (1) garantiza que se satisfaga el consumo mensual de llamadas, (2) que se realizan llamadas sólo a través de la(s) compañía(s) donde se asume el cargo fijo mensual y (3) impone las condiciones de no negatividad para las variables continuas $X_{i}$ .

A continuación se muestra los resultados de la implementación computacional en Solver para el problema de telefonía que considera la inclusión de costos fijos.

La solución óptima consiste en $X_{1}=0$ , $X_{2}=0$ , $X_{3}=200$ , $Y_{1}=0$ , $Y_{2}=0$ , $Y_{3}=1$ , es decir, se utiliza exclusivamente la compañía 3 (PhoneBell) y se cursan los 200 minutos mensuales de llamadas de larga distancia a través de dicha compañía. El valor óptimo es de US$62 que representa el costo mínimo de la cuenta telefónica mensual (US$18+200*US$0,22).

¿Quieres tener el archivo Excel con la implementación en Solver del Problema de Inclusión de Costos Fijos en Programación Entera?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Optimización de una Red Logística de Transporte y Localización de Centros de Distribución

Los problemas de optimización que modelan el desempeño de una red logística o cadena de suministro admiten distintas extensiones que permiten representar la particularidad de distintos escenarios. Es así como en el Blog hemos abordado anteriormente el Problema de Transporte que simplemente aborda el transporte de productos desde oferentes a demandantes al mínimo costo y una extensión al mismo como el Problema de Transporte con Transbordo que incorpora intermediarios en dicho proceso con un objetivo similar. En el siguiente artículo se propone un problema de transporte con transbordo que incorpora adicionalmente la decisión de utilizar centros de distribución que operan como intermediarios entre los oferentes (plantas) y los demandantes (mercados).

Una compañía tiene una red logística que consta de dos plantas y dos centros de distribución (CD). Una de las plantas tiene una capacidad de producción de 150.000 unidades semanales y la otra de sólo 95.000 unidades semanales. Por otra parte la capacidad de despacho en cada ruta es de 65.000 unidades semanales (por ejemplo de la primera planta al segundo CD no se pueden enviar más de 65.000 unidades, lo mismo ocurre desde cualquier CD a cualquier mercado).

La compañía debe entregar sus productos semanalmente en tres mercados diferentes con demandas de 50.000, 80.000 y 45.000, respectivamente (no considerar el valor de demanda de 35.000 para el Mercado 2 que se observa en la imagen a continuación). El siguiente diagrama muestra los costos unitarios de transporte entre las distintas ubicaciones (por ejemplo el costo de transportar una unidad de la planta 1 al centro de distribución 2 cuesta $5).

Existe un costo fijo semanal por concepto de arriendo asociado a utilizar un centro de distribución correspondiente a $2.000 y $3.000, para el centro de distribución 1 y 2, respectivamente. El pago de dicho costo fijo habilita al centro de distribución para recibir productos de las plantas y despachar productos a los mercados (en caso de no asumir el costo fijo de un centro de distribución, éste no se podrá utilizar).

Formule y resuelva un modelo de optimización que permita escoger la política de producción y transporte de los productos, además del arriendo de centros de distribución que minimice los costos totales.

Variables de Decisión:

Parámetros:

Función Objetivo: Se desea minimizar los costos totales asociados a la logística de transporte desde las plantas a los centros de distribución, como de éstos hacia los mercados. Adicionalmente los costos de arriendo de los centros de distribución que se decidan utilizar.

Restricciones:

Capacidad de Producción de las Plantas (Semanal): la cantidad de unidades que puede enviar cada planta a los distintos centros de distribución no puede superar la capacidad de producción de la respectiva planta.

Disponibilidad de los Centros de Distribución: un centro de distribución puede recibir unidades desde las plantas en la medida que se decida su utilización (arriendo). En dicho caso se podrá recibir como máximo 130.000 unidades (2*M), en caso contrario no recibe nada.

Demanda de los Mercados: cada mercado debe recibir las unidades que demanda semanalmente desde los centros de distribución.

Máximo a Despachar en cada Ruta: en cada ruta (combinación de transporte de una planta a un centro de distribución o de un centro de distribución a un mercado) no se podrá enviar más de 65.000 unidades (representado por el parámetro M).

Balance en los Centros de Distribución: la cantidad de unidades que recibe un centro de distribución desde las plantas debe ser igual a las unidades que éste envíe a los mercados.

No Negatividad: se debe respetar las no negatividad para las variables de decisión continuas que representan la logística de transporte (eventualmente se podría exigir adicionalmente que adopten valores enteros)

La implementación del problema anterior haciendo uso de OpenSolver, permite alcanzar los resultados que se observan a continuación:

En la solución óptima de este problema de red logística de transporte y localización de centros de distribución se deben arrendar los 2 centros de distribución. La planta 1 produce 110.000 unidades semanales de las cuales envía 65.000 al centro de distribución 1 y 45.000 unidades al centro de distribución 2. Por otra parte la planta 2 produce sólo 65.000 unidades las cuales envía en su totalidad al centro de distribución 2. El centro de distribución 1 envía 50.000 unidades al mercado 1 y 15.000 unidades al mercado 2 (en el caso del centro de distribución 2, éste envía 65.000 y 45.000 unidades al mercado 2 y 3, respectivamente). Se puede apreciar que se satisfacen las condiciones anteriormente expuestas y se minimiza el costo total semanal que corresponde a $790.000 (valor óptimo).

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

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Problema de Arriendo de Camiones y Distribución de Carga en Programación Entera

Los problemas de optimización asociados a redes logísticas de distribución o cadenas de suministro, admiten distintas variantes que buscan representar los aspectos más relevantes de estas problemáticas. Tal es el caso del problema de localización y transporte, problema de producción y transporte, problema de transporte con transbordo, entre otros. En el siguiente artículo presentamos la formulación y resolución con Solver de Excel de un problema de arriendo de camiones y distribución de carga, que por su naturaleza se puede clasificar como un modelo de Programación Entera Mixta.

Una empresa debe transportar grava a tres construcciones. La empresa puede comprar hasta 18 toneladas de grava al norte de la ciudad (Foso 1) y hasta 14 toneladas al sur de la ciudad (Foso 2). Se necesitan 10, 5 y 10 toneladas de grava en las construcciones 1, 2 y 3, respectivamente. Los costos de transporte por tonelada desde cada foso a cada construcción y el precio de compra por tonelada de material en cada foso están dados en la siguiente tabla:

Adicionalmente, suponga que los camiones necesarios para el transporte de dicho material deben ser arrendados. Cada camión puede ser usado para llevar grava de un solo foso a una sola construcción. El arriendo de un camión es de $5 por camión. Un camión puede transportar 5 toneladas pero no tiene que ir necesariamente lleno. Formule y resuelva un modelo de programación lineal entera-mixta que permita tomar una decisión óptima del número de camiones a usar y la cantidad de material que va a transportar cada uno.

Variables de Decisión: Se debe establecer las toneladas de grava a transportar desde cada foso a cada construcción y adicionalmente especificar la cantidad de camiones utilizados para transportar grava para cada combinación origen destino.

Función Objetivo: Se busca minimizar los costos totales de compra, la logística de distribución y arriendo de camiones. En color amarillo se observan los costos de compra, con color verde los costos de transporte y con color celeste el costo de arriendo de los camiones.

Restricciones: A continuación se detallan las condiciones que deben satisfacer las variables de decisión para este problema.

Demanda de las Construcciones: cada construcción (1, 2 y 3, respectivamente) debe recibir las toneladas de grava.

Capacidad de Abastecimiento de los Fosos: la cantidad de toneladas de grava que cada foso puede despachar a las distintas construcciones no puede superar el máximo de compra.

Capacidad de Transporte de los Camiones: cada camión puede transportar como máximo 5 toneladas de grava. En consecuencia las toneladas de grava que como máximo se pueden transportar en cada combinación origen destino estará limitada a la cantidad de camiones contratados en dicho trayecto. Por ejemplo, si se arriendan 2 camiones para transportar grava desde el foso 1 a la construcción 1 (el lector podrá apreciar que en efecto eso es lo que sucede en la solución óptima que se detalla más abajo) la cantidad máxima a transportar serán 10 toneladas.

No Negatividad y Enteros: el número de camiones contratados para transportar grava en cada combinación origen destino necesariamente deberá ser un número entero mayor o igual a cero.

No Negatividad: las toneladas de grava a transportar desde cada foso a cada construcción deberá respetar las condiciones de no negatividad (se permite transportar fracciones de tonelada de grava).

Al implementar el modelo de optimización anterior haciendo uso de Solver de Excel se alcanza la siguiente solución óptima y valor óptimo.

Se observa que se arriendan en total 5 camiones (por un total de $25 por concepto de costo de arriendo): 2 camiones para llevar grava del foso 1 a la construcción 1 (transportando 10 toneladas), un camión para llevar grava del foso 2 a la construcción 2 (transportando 5 toneladas), un camión para transportar grava del foso 1 a la construcción 3 (transportando 5 toneladas) y un camión del foso 2 a la construcción 3 (transportando 5 toneladas). En consecuencia el costo de transporte total es de $90, asumiendo adicionalmente un costo de compra de $270. Finalmente el costo total (valor óptimo) es de $385 (sumatoria de los costos de arriendo de camiones, costo de transporte y costo de compra).

Problema de Inversión y Selección de Proyectos

Los modelos de Programación Entera constituyen una alternativa eficiente para apoyar la toma de decisiones en aquellos problemas donde se debe implementar (o no) una alternativa o curso de acción que no admite soluciones intermedias. Tal es el caso del Problema de Selección de Cartera de Proyectos donde no es razonable, por ejemplo, si se destina la mitad de los fondos requeridos para un proyecto, asumir que de éste se obtendrá la mitad de sus beneficios o Valor Presente Neto (VPN). Dicho de otro modo, el cumplimiento del supuesto de la proporcionalidad de la Programación Lineal no es adecuado.

El problema que se presenta a continuación aborda estos aspectos y adicionalmente se busca proponer distintas alternativas al momento de establecer las restricciones o condiciones del problema.

Problema de Inversión y Selección de Proyectos

Una empresa está pensando invertir en cuatro proyectos diferentes, cada proyecto se finaliza a lo más en 3 años. Los flujos de caja requeridos en cada año junto con el Valor Presente Neto (VPN) de cada proyecto, concluidos los años de ejecución, y las disponibilidades de recursos financieros se resumen en la siguiente tabla:

Interesa determinar en cuáles proyectos invertir de modo de conseguir el mayor VPN de la inversión.

Variables de Decisión: Se desea determina en cuáles proyectos invertir de las 4 alternativas posibles.

Función Objetivo: Maximizar la sumatoria del Valor Presente Neto (VPN) de los proyectos en los cuales se decida invertir.

Restricciones: Se proponen 3 escenarios para definir las restricciones del problema.

Alternativa 1: Reinvirtiendo el dinero no utilizado en un período, es decir, el dinero que eventualmente quede disponible al final del año 1 y año 2 se puede considerar como parte del presupuesto disponible para el año siguiente. Lo anterior se representa a través de las variables $s_{1}$ y $s_{2}$ , respectivamente.

La implementación computacional del problema haciendo uso de Solver de Excel nos entrega los siguientes resultados:

Se debe invertir en los proyectos 1 y 4. El VPN total es de $51.

Alternativa 2: Sin invertir el dinero no utilizado en un período, pero utilizando el retorno de los proyectos concluidos.

En este caso se debe invertir en los proyectos 1, 2 y 4, alcanzando un VPN total de $69.

Alternativa 3: Reinvirtiendo el dinero no utilizado en un período y también el retorno de los proyectos concluidos.

En este caso la solución óptima y valor óptimo es equivalente al escenario planteado en la Alternativa 3.

Cabe destacar que la Alternativa 3 es la que provee mayor flexibilidad (en cuanto a los presupuestos para inversión) en comparación a las Alternativas 1 y 2, en consecuencia era razonable esperar en este caso que el VPN total de la Alternativa 3 sea mayor o igual que los VPN de las Alternativas 1 y 2.

Notar que el conjunto de las soluciones factibles es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros). En el ejemplo, el número de soluciones factibles no supera el número de las soluciones binarias del problema (variables restringidas sólo a valores 0 o 1) que son $2^{4}=16$ , dado el número de variables utilizadas, de hecho las soluciones factibles son menos de 16 pues en particular $x_{i}=1$ para i=1,2,3,4 no satisface las disponibilidades de capital en cualquiera de las tres alternativas.

Problema de Arriendo de Buses para Transporte de Pasajeros en Programación Lineal

El siguiente problema de Programación Lineal consiste en determinar una política óptima de arriendo de buses para el transporte de pasajeros que minimice los costos asociados a su arriendo y satisfaga los requerimientos de transporte y otras condiciones adicionales que se deseen imponer.

El Centro de Alumnos de Ingeniería Industrial de una respetada universidad desea celebrar el día del alumno en la playa. Este paseo está planificado para 1.200 alumnos como mínimo. Una empresa de transporte ofrece 2 tipos de buses pero solo cuenta con 28 conductores. La tabla de abajo indica la capacidad y el costo de arriendo de cada tipo de bus:

Para mantener el equilibrio de su flota, la empresa de transporte impone la condición de que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. Formule y resuelva un modelo de Programación Lineal que permita determinar cuántos buses de cada tipo hay que arrendar para el paseo de modo que resulte lo más económico para el Centro de Alumnos.

Variables de Decisión:

$x$ : Cantidad de Buses Tipo A arrendados
$y$ : Cantidad de Buses Tipo B arrendados

Función Objetivo:

Minimizar $80.000x+110.000y$

Restricciones:

Cantidad de Alumnos: $40x+60y\geq 1.200$
Cantidad de Conductores: $x+y\leq 28$
Condición de Flota: $x-y\geq 0$
No Negatividad: $x,y\geq 0$

El dominio de soluciones factibles del problema esta dado por el polígono ABC según se detalla a continuación (representación gráfica realizada con el software Geogebra). En particular la solución óptima corresponde al vértice A donde $x=12$ e $y=12$ , con valor óptimo $V(P)=80.000*12+110.000*12=2.280.000$ .

Notar que si bien el problema fue modelado como uno de Programación Lineal, dadas las características del problema sería deseable obtener una solución entera para las variables de decisión (dado que no es posible arrendar una fracción de buses y asumir por ejemplo que el costo del mismo es proporcional a la capacidad ocupada). No obstante en el ejemplo propuesto la solución óptima obtenida cumple de forma natural con las condiciones de integralidad, lo que indica que sus resultados son idénticos al problema de Programación Entera asociado (es decir, aquel al cual se le agregan de forma explícita las condiciones de enteros para las variables de decisión).

De forma complementaria al análisis anterior se pueden responder las siguientes preguntas correspondientes al análisis de sensibilidad o postoptimal:

1. Determine cuánto podría variar el costo de arriendo del Bus tipo A que conserve la solución óptima. Si C1 (costo arriendo del Bus tipo A) varía en el intervalo entre [73.333,3 , ∞[ se conserva la actual solución óptima.

2. Determine el impacto en el valor óptimo del problema si se elimina la condición que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. El precio sombra de la restricción de condición de flota es 4.000. Luego si se elimina la condición de flota la solución óptima se alcanza en la mínima variación $(x,y)=(0,20)$ para una reducción permisible del lado derecho de dicha restricción en 20 unidades. Luego el nuevo valor óptimo es $V(P)=2.280.000+(-20-0)*4.000=2.200.000$ .