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:

antecedentes-productivos-mi

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:

demanda-puertos

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:

variables-minas-y-puertos

Parámetros:

parametros-minas-y-puertos

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.

funcion-objetivo-minas-y-pu

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.

capacidad-minas

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

demanda-carbon-puertos

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.

maximo-ceniza-puertos

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%).

maximo-sulfuro-puertos

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

no-neg-minas-y-puertos

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:

solucion-minas-y-puertos-so

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]

Error Porcentual Absoluto Medio (MAPE) en un Pronóstico de Demanda

El Error Porcentual Absoluto Medio (MAPE o Mean Absolute Percentage Error) es un indicador del desempeño del Pronóstico de Demanda que mide el tamaño del error (absoluto) en términos porcentuales. El hecho que se estime una magnitud del error porcentual lo hace un indicador frecuentemente utilizado por los encargados de elaborar pronósticos debido a su fácil interpretación. Incluso es útil cuando no se conoce el volumen de demanda del producto dado que es una medida relativa. Por ejemplo, afirmar que el «error porcentual promedio es de un 4%» es más fácil de comprender que cuando se dice «el error absoluto medio por período es de 1.000 unidades» (que sería la información que podríamos obtener del MAD y que en abstracto no provee información si esta magnitud de error es aceptable o no).

La fórmula para el cálculo del MAPEError Porcentual Absoluto Medio es:

formula-mape

La siguiente imagen representa una serie de tiempo de 12 meses donde At representa la demanda real de un producto cualquiera y Ft el pronóstico utilizando una Regresión Lineal. La ecuación de la regresión ajustada es y=5,6993*x+217,12 donde la variable y representa la demanda y la variable x el período (mes).

regresion-lineal-mape

El detalle de los resultados se presenta a continuación donde en la columna D se muestran los datos reales y en la columna E los pronósticos. Por ejemplo para el mes de Enero (mes 1) el pronóstico se obtiene como F1=5,6993*1+217,12=223 (aproximado arbitrariamente al entero más cercano).

excel-calculo-mape

Luego obtenemos el error porcentual absoluto para cada mes del período de evaluación (celdas amarillas de la tabla anterior). Notar que en el ejemplo dicho cálculo correspondería para el mes de Enero en la fórmula F3/D3 donde el numerador (F3) es el error absoluto del período y el denominador (D3) la demanda real del mes. Finalmente se repite el procedimiento para cada uno de los meses lo cual se facilita al hacer uso de una planilla Excel.

calculo-mape

En conclusión el Error Porcentual Absoluto Medio es de un 14,56%. De forma complementaria se puede calcular el MAD y la Señal de Rastreo (TS) de modo de tener un mayor número de indicadores para interpretar de forma adecuada el desempeño del pronóstico.

tabla-mape-mad-y-ts

Es conveniente graficar tanto el comportamiento del MAD como la Señal de Rastreo (TS) para facilitar la interpretación de los resultados. A continuación se presentan los resultados:

grafico-mad-y-ts

Notar que la magnitud media absoluta del error aumenta en los últimos períodos. En cuanto al comportamiento de la señal de seguimiento o TS si bien ésta varía en el rango comúnmente aceptable de [-4,4] MADs, las sub estimaciones sucesivas del valor real de la demanda de los meses de Agosto, Septiembre y Octubre marcan una tendencia creciente en su comportamiento, lo cual se compensa luego con las sobre estimaciones de los meses de Noviembre y Diciembre. A continuación un vídeo de nuestro canal de Youtube con la implementación en Excel del ejemplo descrito en este artículo:

¿Quieres tener el archivo Excel con el cálculo del Error Porcentual Absoluto Medio (MAPE) de este Ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Ejemplo del Problema del Flujo Máximo en Programación Entera resuelto con Solver

Este tipo de problemas (Problema del Flujo Máximo) es similar al Problema de Ruta más Corta, pero ahora se busca determinar el flujo máximo entre un nodo fuente y un nodo destino, los que están enlazados a través de una red, con arcos con capacidad finita, tal como se presenta en la siguiente figura. Notar que los números asignados a cada uno de los arcos representan los flujos máximos o capacidades correspondientes a cada arco.

ruta-flujo-maximo

Problema del Flujo Máximo

Desde el punto de vista de la Programación Entera podemos plantear la situación de la siguiente forma:

Variables de Decisión:

variables-flujo-maximo

Función Objetivo: Maximizar las unidades que salen del nodo de origen (1) a los que éste conecta (2, 4 y 5) o alternativamente maximizar las unidades que llegan al nodo de destino (8) desde los que conectan a él (3, 6 y 7).

funcion-flujo-maximo

Restricciones:

Restricciones de Flujo Máximo: La cantidad de unidades que sale de cada nodo de origen a un nodo de destino no puede superar la capacidad detallada en el arco, por ejemplo, del nodo 1 al nodo 2 sólo se pueden enviar 7 unidades.

restricciones-flujo-maximo

Restricciones de Balance de Flujo en los Nodos: Debe existir un equilibrio entre la cantidad de unidades que llega a un nodo y las que de éste salen, por ejemplo el número de unidades que se envía desde el nodo 1 al 4 (si es que así fuese el caso) debe ser igual a lo que desde el nodo 4 se envían al nodo 3 y 6.

balance-flujo-maximo

No Negatividad e Integralidad: Las variables de decisión de decisión deben cumplir las condiciones de no negatividad. Adicionalmente exigiremos que éstas adopten valores enteros aún cuando se podría flexibilizar dicha situación lo que daría origen a un problema de Programación Lineal.

no-negatividad-flujo-maximo

Luego de implementar el modelo de optimización anterior con Solver se alcanza la siguiente solución óptima y valor óptimo:

solucion-flujo-maximo

Notar que el flujo máximo de unidades que puede llegar al nodo de destino son 32 unidades (valor óptimo) donde cualquiera de las funciones objetivos propuestas proporciona el mismo resultado (en particular hemos utilizado la primera de ellas). Los valores de las celdas en color amarillo representan la solución óptima, es decir, la cantidad de unidades que fluyen en cada combinación de un nodo origen destino.

En el siguiente tutorial de nuestro canal de Youtube se detalla la implementación computacional que permite alcanzar los resultados anteriormente expuestos:

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google+ o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre «Descarga el Archivo» se mostrará abajo una vez que nos hayas recomendado).

[l2g name=»Descarga el Archivo» id=»4352″]

Problema de Asignación de Horas Académicas a Profesores aplicado a una Universidad Online

El desarrollo de las tecnologías de información ha favorecido un crecimiento sostenido en la oferta académica de las instituciones de educación superior, lo cual ha permitido sumar a la tradicional formación presencial la posibilidad de obtener grados académicos a través de una formación no presencial (online). En este contexto, en la actualidad existen numerosas «Universidades Online» las cuales deben programar horas de apoyo académico de sus distintos cursos por parte de los profesores o docentes hacia los alumnos, con el objetivo de favorecer la comprensión de los contenidos.

Problema de Asignación de Horas Académicas a Profesores

En el siguiente artículo consideraremos un problema de asignación para cubrir las necesidades de apoyo académico para un curso de Economía. Asumiremos que se desea tener exactamente un profesor de turno (para responder preguntas de los alumnos en tiempo real a través de un foro o chat) de Lunes a Viernes de 08:00 AM hasta las 23:00 PM. Los Sábados y Domingo también se desea ofrecer el servicio pero de 08:00 AM hasta las 20:00 PM. Actualmente se cuenta con 10 profesores que cuentan con los conocimientos necesarios para desarrollar los servicios de tutorias y su remuneración (en dólares por hora) depende básicamente de la experiencia en el curso y grado académico. Adicionalmente, debido a los compromisos que tienen dichos profesores con otros cursos de la Universidad, han manifestado su disponibilidad máxima (en horas) para atender los distintos requerimientos según se detalla en la siguiente tabla:

tabla-sueldo-y-disponibilid

Por ejemplo el profesor 1 recibe un salario de 50 dólares la hora y puede trabajar como máximo 5 horas el Lunes, 6 horas el Miércoles y Viernes, 3 horas el Sábado y 2 horas el Domingo. Los días Martes y Jueves el profesor 1 no tiene disponibilidad de tiempo. En base a esta información la Universidad desea determinar una asignación de horas académicas a los profesores de modo de cubrir las necesidades de atención de alumnos al menor costo posible al mismo tiempo de garantizar un mínimo de 5 horas por profesor a la semana. Para enfrentar dicha situación formularemos el siguiente modelo de Programación Lineal:

Variables de Decisión:

variables-problema-profesor

Con i=1,…,10 representando a los profesores y j=1,…,7 los días de la semana don j=1 es el día Lunes y j=7 el día Domingo.

Parámetros:

parametros-problema-profeso

Función Objetivo:

funcion-objetivo-profesores

Se busca minimizar los costos totales de la asignación que considera la ponderación para cada profesor de la cantidad de horas que trabaja durante la semana por el salario por hora (en dólares).

Restricciones:

Se debe cumplir con la cantidad de horas para cada día de la semana (15 horas para cada día de Lunes a Viernes y 12 horas para el Sábado y Domingo).

minimo-horas-dia-profesores

Se desea asignar al menos 5 horas académicas semanales a cada profesor.

minimo-horas-semanales-prof

Se debe respetar la disponibilidad horaria de los profesores durante la semana.

restriccion-de-demanda-prob

Condiciones de no negatividad para las variables de decisión.

no-negatividad-problema-avi

Luego de implementar computacionalmente el modelo de optimización con Solver de Excel se obtiene la siguiente solución óptima con valor óptimo V(P)=US$4.639.

solucion-optima-profesores

El siguiente tutorial de nuestro canal de Youtube muestra la resolución del problema anterior:

Ejemplo del Problema del Camino Más Corto en Programación Entera

El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.

La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.

Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

diagrama-ruta-mas-corta

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:

  • Ruta 1-2-5-7-8: 4+8+17+9=38[km]
  • Ruta 1-3-4-7-8: 3+12+20+9=44[km]
  • Ruta 1-3-4-6-8: 3+12+2+22=39[km]
  • Ruta 1-3-4-8: 3+12+15=30[km]
  • Ruta 1-3-6-8: 3+4+22=29[km]

La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].

A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:

Variables de Decisión:

variable-binaria-ruta-mas-c

Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:

funcion-objetivo-ruta-mas-c

Restricciones:

restricciones-ruta-mas-cort

  1. La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
  2. La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
  3. La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
  4. La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
  5. La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
  6. La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
  7. La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
  8. Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.

Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:

solucion-optima-ruta-mas-co

Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).

El tutorial a continuación disponible en nuestro canal de Youtube muestra en detalle la implementación y resolución computacional de este problema: