Por qué no aparece el Informe de Confidencialidad (o Informe de Sensibilidad) en Solver de Excel

Cuando resolvemos un modelo de Programación Lineal en Solver de Excel tenemos la posibilidad de generar una serie de informes de respuesta entre los cuales destaca el denominado «Confidencialidad» (o «Sensibilidad» en versiones de Excel anteriores) que resume los principales resultados relativos al análisis de sensibilidad. Lo anterior es fácilmente accesible en el módulo de Resultados de Solver en una interfaz similar como la que se presenta a continuación:

resultados-de-solver-confid

Sin embargo la opción de obtener el Informe de Confidencialidad no siempre está disponible. Para ello consideremos que nos interesa resolver el siguiente modelo de Programación Entera:

modelo-de-programacion-ente

A continuación desarrollamos la implementación computacional según se muestra en la imagen a continuación:

carga-modelo-entero-en-solv

Se puede apreciar que la celda E3 es la fórmula de la función objetivo que representa la ponderación de los parámetros de la misma (10 y 16) por los valores que adquirirán las celdas que definiremos como variables de decisión (B3 y C3). Adicionalmente las celdas D6 y D7 también son fórmulas que considera la ponderación de los parámetros del lado izquierdo de las restricciones por las variables de decisión. Luego, se carga el modelo en Solver de Excel en la interfaz «Parámetros de Solver»:

parametros-de-solver-modelo

Para obtener los resultados sólo es necesario presionar «Resolver» donde se actualizará en la planilla los resultados con la solución óptima X=2 e Y=2 y valor óptimo V(PE)=52. Notar sin embargo que el informe de Confidencialidad ya no se encuentra disponible.

resultados-de-solver-sin-co

¿Por qué sucede ésto?. Básicamente por qué los informes de sensibilidad en Solver se pueden obtener si el problema que se implementa es de naturaleza continua (como lo que sucedería en este mismo problema si se omiten las condiciones de integralidad para las variables de decisión lo que daría lugar a un modelo de Programación Lineal). Por el contrario un modelo de Programación Entera como el que hemos utilizado en este artículo tiene un dominio de factibilidad discreto. Lo anterior queda en evidencia en la siguiente representación gráfica del problema realizada con Geogebra:

contraste-dominio-discreto-

El dominio de factibilidad continuo del modelo de Programación Lineal (omitiendo las condiciones de enteros para las variables de decisión) corresponde al área achurada denotada por el polígono que tiene por los vértices A, B, C y D. En cuanto al modelo de Programación Entera el dominio de factibilidad es discreto y se puede enumerar, lo cual corresponde a las coordenadas que representan los puntos A, E, F, B, I, H, G, J, K, C, M, L y D. En este contexto se debe recordar que uno de los supuestos básicos de la Programación Lineal es la proporcionalidad el cual ya no es admisible cuando nos enfrentamos a un problema de Programación Entera.

En consecuencia, si en la utilización de Solver de Excel queremos analizar el impacto que tiene la modificación de los parámetros del modelo en la resolución de un modelo de Programación Entera (principalmente en lo que se refiere a la solución óptima y valor óptimo) se propone reoptimizar modificando la(s) celda(s) que sean necesarias y ejecutar el programa nuevamente.

Cómo secuenciar n Trabajos en una Máquina para minimizar Setup

El orden o secuencia en el cual se programan n trabajos en una máquina es significativo a la hora de estimar los tiempos de setup para pasar de un determinado trabajo a otro o incluso comenzar con cualquiera de ellos al inicio de la planificación.

En este contexto se reconoce formalmente como tiempo de setup la cantidad de tiempo necesario para preparar una máquina para realizar una operación diferente y cumplir con las especificaciones del cliente (estos tiempos de setup pueden representar por ejemplo calibración de la máquina, cambio de formatos, limpieza, mantención preventiva, etc).

En el siguiente artículo formularemos y resolveremos un modelo de Programación Entera que permita encontrar una secuenciación óptima de n trabajos en una máquina, lo cual será contrastado con la solución que se puede obtener por simple enumeración de secuencias, naturalmente para un número de trabajos «pequeño» (para fines académicos).

En general si se deben programar n trabajos en una máquina, la cantidad de secuencias posibles son n!.

Por ejemplo si tenemos 3 trabajos (n=3) que debemos asignar a una máquina la cantidad de secuencias posibles son 6 (3!=3*2*1). Lo anterior implica que aún para centros de trabajos pequeños es útil contar con un procedimiento que permita identificar aquella secuencia que minimice el makespan sin tener la necesidad de hacer una evaluación exhaustiva de cada una de ellas.

Consideremos un conjunto de trabajos que necesitan ser asignados a una cierta máquina, todos los cuales están disponibles al inicio de la programación y se conoce los tiempos de proceso y fechas de entrega como muestra la siguiente tabla:

tabla-tiempos-procesos-y-en

Sin embargo, el tiempo de setup, correspondiente al tiempo requerido para preparar la máquina antes de cada trabajo, depende del trabajo que le precede. A continuación se indica los tiempos de setup aij cuando al trabajo j le precede el trabajo i:

tabla-tiempos-de-setup

Adicionalmente hay un tiempo de setup a0j asociado al primer trabajo a programar de acuerdo a los siguientes valores:

tiempos-de-setup-inicial

El objetivo entonces es programar las actividades de modo de minimizar el tiempo de utilización de la máquina (makespan) como resultado de la asignación propuesta. Notar que según lo descrito anteriormente el problema admite 6 secuencias posibles las cuales se enumeran a continuación para poder obtener el makespan de la programación.

  • Secuencia 1-2-3: 1+9+1+13+3+10=37[t]
  • Secuencia 1-3-2: 1+9+0+10+1+13=34[t]
  • Secuencia 2-1-3: 3+13+2+9+0+10=37[t]
  • Secuencia 2-3-1: 3+13+3+10+3+9=41[t]
  • Secuencia 3-1-2: 4+10+3+9+1+13=40[t]
  • Secuencia 3-2-1: 4+10+1+13+2+9=39[t]

Naturalmente la secuencia óptima es 1-3-2 con un makespan de 34[t]. Como el trabajo 1 es el que inicia la secuencia tiene un setup inicial de a01=1 y requiere de 9[t] para ser completado. A continuación sigue el trabajo 3 que dura 10[t] y como es el trabajo 1 el que le precede no se requiere tiempo de setup (a13=0). Finalmente se realiza el trabajo 2 con duración de 13[t], necesitándose 1[t] para pasar del trabajo 3 al trabajo 2 (a32=1).

Para abordar el problema anterior a través de un modelo de optimización definiremos el siguiente problema de Programación Entera que claramente permite extender su aplicación a problemas de mayor tamaño (número de trabajos):

Variables de Decisión:

variables-de-decision-probl

Para i=1,2,3j=0,1,2,3 con i≠j. Por ejemplo si X10=1 esto indica que el trabajo 1 es el que se realiza inmediatamente después del trabajo 0, es decir, el trabajo 1 es el que inicia la secuencia.

Función Objetivo:

En la implementación computacional con Solver de Excel la función objetivo se representa a través de la siguiente fórmula:

formula-funcion-objetivo-pr

Para mayor claridad a continuación un extracto de la pantalla del modelo computacional:

formula-funcion-objetivo-se

Se busca minimizar el makespan de la secuencia. Notar que se suman las constantes asociadas al tiempo de proceso de cada trabajo (las cuales son independientes de la secuencia y justifican que inicialmente el valor de la celda que representa la función objetivo sea igual a 32[t]) y que eventualmente se pueden omitir de la función objetivo (en dicho caso el valor óptimo representaría la sumatoria de los tiempos de setup de la secuencia y no el makespan de la programación).

Restricciones:

Se deben realizar los 3 trabajos:

se-deben-realizar-los-traba

A lo más una tarea sigue a la j-ésima al menos que sea la última de la secuencia:

a-lo-mas-una-tarea-sigue-a-

Alternativas infactibles: (celdas color rojo en la planilla de cálculo)

alternativas-infactibles-se

Debe existir un trabajo inicial en la secuencia:

trabajo-inicial-setup

Luego de resolver con Solver el problema anterior se alcanza la siguiente solución óptima y valor óptimo:

solucion-optima-problema-se

Donde se corrobora que la secuencia óptima es 1-3-2 con un makespan de 34[t]. A continuación puedes descargar el archivo Excel con la resolución del problema anterior en el siguiente enlace: Minimizar Tiempos de Setup.

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:

tabla-portal-empleos

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:

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

variable-decision-asignacio

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

funcion-objetivo-maximizaci

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

restricciones-asignacion-po

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.

solucion-optima-asignacion-

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:

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]