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.

problema-de-personal

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

problema-de-personal-solver

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

solver-problema-call-center

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.

solucion-optima-call-center

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

solver-pem

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

solver-premium-pro-pem

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.

whatsbest-pem

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.

Problema de Corte de Rollos en Programación Entera (Premium Solver)

En el artículo anterior abordamos una aplicación clásica de la Programación Entera conocida como el Problema de Corte de Rollos («Cutting Stock Problem») el cual en esta oportunidad resolveremos utilizando la versión Premium de Solver. Si bien el tamaño y complejidad del modelo permitiría enfrentar su resolución sin mayores inconvenientes con la versión tradicional de Solver, utilizaremos Premium Solver Pro para efectos ilustrativos del uso de esta herramienta mejorada.

En este contexto recordemos las características del modelo de optimización de corte de rollos que consiste en minimizar una función de pérdida de material sujeta a restricciones que permiten satisfacer la demanda de rollos de menor tamaño y que incluye adicionalmente condiciones de no negatividad e integralidad para las variables de decisión:

funcion-objetivo-corte-de-r

  • 2X1+X2+X3+X8+X9+X13>=150
  • X2+3X4+2X5+X6+X8+2X10+X11+X14>=200
  • X2+3X3+2X5+3X6+5X7+X9+X10+2X11+4X12+X14+3X15>=175
  • Xi>=0 Enteros (i=1,…,15)

Con el objetivo de implementar en Premium Solver Pro el problema anterior creamos en Excel una estructura que resuma la información del problema y que facilite su resolución. La imagen a continuación considera en las celdas con color amarillo las variables de decisión (15 variables) y en la celda J20 (color celeste) la función objetivo.

A continuación para definir las variables de decisión seleccionamos «Decision» y luego «Normal». Notar que previamente se ha seleccionado el rango de celdas que queremos definir como variables de decisión (en este ejemplo las 15 celdas en color amarillos).

variables-premium-solver

Para restringir el valor que adopten las variables de decisión a números enteros se debe ir a «Constraints», «Variable Type/Bound», «Integer» como muestra la siguiente imagen:

variables-enteras-premium-s

Ahora nos posicionamos en la celda J20 que contiene la función objetivo (esta celda contiene una fórmula que es la sumaproducto de la pérdida de material en [cm] asociada a cada patrón de corte ponderada por la cantidad de veces que se utiliza un esquema de corte definido). Luego en «Objective» seleccionamos «Min».

funcion-objetivo-premium-so

En el siguiente paso corresponde incorporar las restricciones de demanda para el problema. Notar que dado que las restricciones de demanda de rollos de 45[cm], 30[cm] y 18[cm] son todas del tipo «>=» las podemos incorporar todas de forma simultanea tal se muestra a continuación:

restriccion-mayor-o-igual-p
mayor-o-igual-solver

Finalmente estamos en condiciones de poder resolver el modelo de optimización con Premium Solver Pro. A la derecha de la planilla de cálculo encontraremos la interfaz del programa que resume las características del problema que hemos implementado.

premium-solver-interfaz

Seleccionamos el icono con flecha verde que esta en la esquina superior derecha de la imagen anterior para resolver el modelo, obteniendo la solución óptima y valor óptimo que se muestra a continuación:

solucion-optima-premium-sol

La solución óptima consiste en utilizar 150 veces el patrón de corte 3 (X3=150) y 100 veces el patrón de corte 10 (X10=100), omitiéndose el uso de los otros esquemas de corte. Con esto la pérdida de material (total) asciende a 350[cm] de papel, logrando satisfacer la demanda para cada tipo de rollo (notar que para el caso de los rollos de 18[cm] se producen 550[u] siendo la demanda de 175[u]). En nuestro canal de Youtube puedes revisar la implementación y resolución computacional del modelo anterior.

Cómo descargar e instalar Premium Solver en Excel 2010

Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.

En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.

Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.

A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.

Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.

registro-solver-premium

Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos «Download Now».

descargar-premium-solver

Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo «Acerca de Microsoft Excel».

excel-2010-64-bits

Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).

correo-con-password-premium

Paso 4: Una vez completada la descarga ejecuta el archivo «SolverSetup64.exe» (o el nombre que corresponda según la versión de Excel que estés utilizando).

solversetup64

A continuación se desplegará el asistente para la instalación del programa. (Seleccionar «Next»).

solver-installshield

Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:

password-activation-solver

Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar «Next».

acuerdo-licencia-solver

En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando «OK».

activacion-solver-premium

Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que  el programa selecciona por defecto.

carpeta-destino-solver

Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado «Premium Solver Pro» que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.

seleccion-premium-solver-pr

El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado («Install»).

listo-para-instalar-solver

Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.

instalacion-completa-solver

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:

transporte-con-transbordo

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:

solucion-transporte-con-tra

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

solucion-transbordo-diagram