Programación Entera Archivos - Página 6 de 8

Problema de Asignación aplicado a un Portal de Anuncios de Trabajos

En el siguiente artículo abordaremos un caso aplicado respecto a una situación real donde un sitio web de búsqueda de empleos en España desea determinar qué anuncios publicar en una zona preferente de exhibición dentro de su portal. Para ello será necesario formular y resolver un modelo de Programación Entera que corresponde a un caso particular del problema de asignación descrito en artículos anteriores.

Consideramos como premisa que existen más anuncios que espacios publicitarios y por tanto se debe decidir cuáles de ellos incorporar con el objetivo de maximizar el retorno de la asignación pero al mismo tiempo satisfacer una serie de criterios adicionales que se deseen imponer. Una representación de la situación descrita se resume en la tabla a continuación:

Por ejemplo el Aviso N°1 corresponde a un anuncio de trabajo en Madrid en la Categoría I, el cual fue publicado hace 15 días (antigüedad) y que provee un retorno estimado de 100 unidades monetarias. Por supuesto los datos son ficticios, no obstante, permite visualizar la extensión de esta problemática a una situación de esta naturaleza. Asumiremos adicionalmente que se desean cumplir las siguientes condiciones en la asignación:

Seleccionar un Máximo de 5 Anuncios (entre los 10 candidatos posibles).
El tiempo promedio de Publicación de los Anuncios que se seleccionen no debe superar los 7[días].
Por razones estratégicas se debe publicar al menos un Anuncio de Madrid.
Se impone un máximo de 2 Anuncios de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría I.
Se impone un mínimo de 1 Anuncio de la Categoría II.
Se impone un mínimo de 1 Anuncio de la Categoría III.

Un modelo de Programación Entera que permite encontrar una asignación para la situación descrita es el siguiente:

Variables de Decisión: Permite dar respuesta al problema de selección de anuncios publicitarios a incluir en la zona preferente. (i=1,…,10)

Función Objetivo: Maximizar el retorno total de la asignación, donde Ri es el retorno (en U.M.) asociadas al anuncio i.

Restricciones: Satisfacer las condiciones expuestas. Se detallan a continuación en el mismo orden en el que fueron detalladas. (Ti representa el tiempo de publicación (en días) del anuncio i).

Al implementar computacionalmente el problema con Solver de Excel se obtiene la siguiente solución óptima que otorga un valor óptimo de 465[U.M]. Con ello la empresa debería implementar los anuncios 1, 4, 5, 6 y 8.

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.

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:

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

Restricciones:

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

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:

Problema de Plan de Personal en un Call Center (Programación Entera)

Una línea aérea está considerando incorporar vuelos desde y hacia su aeropuerto base y por lo tanto necesita contratar más agentes de servicio al cliente. Sin embargo, no está claro cuántos más debe contratar. La administración reconoce la necesidad de controlar el costo y al mismo tiempo brindar un nivel de atención satisfactorio. Se ha realizado un análisis del número mínimo de agentes de servicio que deben encontrarse de guardia en diferentes momentos del día para proporcionar un nivel satisfactorio de servicio.

Se ha acordado que cada agente trabaje un turno de 8 horas en los turnos mostrados en la tabla anterior. Por ejemplo, el turno 3 va desde las 12:00 hasta las 20:00. Los sueldos de cada turno son diferentes debido a que unos son más deseables que otros. Por ejemplo, a cada agente que cumpla el turno 3 debemos pagarle diariamente $175.

Se busca formular y resolver un modelo Programación Entera que permita a la línea aérea encontrar el plan de asignación de agentes al menor costo posible y que cumpla los requerimientos impuestos.

1. Variables de Decisión: Establecer un plan de asignación de agentes a los distintos turnos de trabajo.

Xi: Número de Agentes asignados al Turno i con i=1,2,3,4,5 con Xi>=0 {Enteros}

2. Función Objetivo: Minimizar el costo total de la asignación de agentes.

Minimizar 170X1+160X2+175X3+180X4+195X5

3. Restricciones: Se busca garantizar que en cada período del día se cuenta con la cantidad mínima de agentes requeridos.

X1 >= 48
X1 + X2 >= 79
X1 + X2 >= 65
X1 + X2 + X3 >= 87
X2 + X3 >= 64
X3 + X4 >= 73
X3 + X4 >= 82
X4 >= 43
X4 + X5 >= 52
X5 >= 25

A continuación implementamos el modelo anterior en Solver. Notar que las celdas color amarillo son las asignadas a las variables de decisión y éstas a la vez vinculan las combinaciones posibles entre turnos y períodos atendidos.

Adicionalmente en la columna I se ha guardado el valor del lado izquierdo de las restricciones que garantizan el mínimo número de agentes por período.

Finalmente la función objetivo (celda color naranjo) corresponde a la suma producto entre las variables de decisión y los parámetros que representan el costo diario por agente en los respectivos turnos (SUMAPRODUCTO(C4:G4;C19:G19)).

La implementación del modelo anterior en la interfaz de Solver es la siguiente:

Alcanzando la solución óptima del problema que considera la asignación de 48, 31, 39, 43 y 25 personas a los turnos 1,2,3,4 y 5, respectivamente, con un costo total (mínimo) de $32.560.

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

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]Descargar Aquí Problema Agentes Call Center[/sociallocker]

Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte

¿Qué complemento de Excel es mejor para resolver un modelo de optimización: Solver, Premium Solver Pro o What’sBest!?. Esta consulta fue enviada por uno de nuestros seguidores de México y en este artículo trataremos de presentar algunos argumentos que permitan al lector formar una opinión al respecto. Para ello utilizaremos como caso aplicado la resolución del Problema de Localización y Transporte (Programación Entera Mixta). A continuación te presentamos los resultados que alcanzamos con Solver, Premium Solver Pro y What’sBest!.

Resolución con Solver: Se alcanza una solución factible con un costo total asociado de US$12.617.919.

Resolución con Premium Solver Pro: Se alcanza una solución factible con un costo total de US$12.414.340.

Resolución con What’sBest!: Se alcanza una solución factible con un costo total de US$12.414.340. Notar sin embargo que la solución óptima difiere de la alcanzada al implementar el modelo con Premium Solver Pro aun cuando tiene asociado idéntico valor de la función objetivo.

Comentarios: Se puede apreciar que la versión básica de Solver genera una solución factible con un costo mayor a la obtenida tanto con Premium Solver Pro y What’sBest!. Lo anterior sugiere la conveniencia de implementar este tipo de problemas con una herramienta de resolución mejorada. Adicionalmente, en la medida que un modelo de optimización crece en tamaño y complejidad es recomendable poder contrastar los resultados obtenidos con distintas herramientas de resolución de modo de tener una mayor claridad si las soluciones obtenidas son sólo factibles o eventualmente óptimas. A continuación encontrarás un tutorial que hemos subido a Youtube con la resolución del problema de localización y transporte.

Formulación de un Problema de Localización y Transporte (Programación Entera Mixta)

Un modelo de Programación Entera Mixta (PEM) es un híbrido entre la Programación Lineal (PL) y la Programación Entera (PE), es decir, corresponde a una categoría particular de modelamiento matemático con características similares a la Programación Lineal pero donde un subconjunto de las variables de decisión deben adoptar valores enteros o binarios. Este característica de la Programación Entera Mixta permite representar situaciones de naturaleza real como los problemas que consideran la inclusión de costos fijos. En este contexto el siguiente artículo aborda la formulación de un Problema de Localización y Transporte el cual se describe a continuación.

Una ciudad tiene 10 zonas o áreas urbanas cada una de los cuales genera una determinada cantidad de basura (en toneladas) durante el periodo de planificación según se describe a continuación:

La basura generada debe ser transportada a centros de depósitos o vertederos entre un total de 5 candidatos posibles, cada uno de los cuales tiene un costo fijo de construcción en dólares.

Adicionalmente se ha estimado el costo de transportar una tonelada de basura desde una zona a cada uno de los potenciales centros de depósito, el cual depende básicamente de la distancia a recorrer y el tipo de transporte seleccionado.

Formule un modelo de Programación Entera Mixta que permita seleccionar los centros de depósito a construir y la política de transporte de basura que minimiza los costos totales.

1. Variables de Decisión: Sea i=1,…,10 las Zonas y j=1,…,5 los Depósitos:

2. Función Objetivo: Con el propósito de trabajar con una notación compacta podemos definir el siguiente conjunto de parámetros para el modelo de optimización:

Tij: Costo de transportar una tonelada de basura desde la Zona i al Depósito j
Fj: Costo fijo de construcción del Depósito j

La función objetivo en consecuencia se puede representar a través de la siguiente expresión:

3. Restricciones:

Se debe despachar (transportar) la totalidad de la basura que genera cada Zona (definimos para ello el parámetro Ai como la cantidad de basura en toneladas que genera la Zona i).

Se debe respetar la capacidad de almacenamiento de basura para cada Depósito, utilizándolo sólo en caso que se decida su construcción. Para ello definimos el parámetro Cj como la capacidad de almacenamiento de basura en toneladas del Depósito j. Lo anteriormente expuesto explica la ponderación de la capacidad por la variable binaria para cada j.

Finalmente establecemos condiciones de no negatividad para Xij>=0 Para todo i,j y Yj{0,1} para todo j.

¿Quieres saber cuál es la solución de este problema?. Te recomendamos leer el siguiente artículo: Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte.