Cuando necesitamos asignar recursos escasos a determinadas funciones y dichos recursos no son fraccionables, la utilización de modelos de Programación Entera resultan ser de utilidad para la toma de decisiones. En este contexto los problemas de asignación de personal a determinadas tareas es una aplicación típica de la Programación Entera que a continuación desarrollaremos a través de un ejemplo.
Problema de Asignación
Consideremos una empresa que dispone de 5 ingenieros que deben desarrollar 7 proyectos. La tabla a continuación resume el tiempo que demora cada ingeniero (en horas) en completar un determinado proyecto. El problema consiste en determinar una asignación óptima que permita realizar cada uno de los proyectos con la limitante que por motivos estratégicos cada ingeniero debe desarrollar al menos un proyecto y en ningún caso hacer más de 2 proyectos. Por supuesto se busca que el tiempo requerido para realizar los 7 proyectos sea el menor posible.
Una alternativa sería buscar intuitivamente una asignación que cumpla con los requisitos de la empresa y tenga un bajo tiempo asociado. Sin embargo, este tipo de estrategias de resolución queda claramente acotada a problemas de tamaño menor y ni siquiera en ese tipo de situaciones nos asegura la mejor solución posible. Por ello definiremos el siguiente modelo de optimización de Programación Entera:
1. Variables de Decisión: Utilizamos las siguientes variables de decisión binarias
2. Función Objetivo: Minimizar el tiempo total requerido para completar los proyectos
Donde Tij (parámetros) es el tiempo (en horas) requerido por el ingeniero i en realizar el proyecto j. Por ejemplo T(A,P5)=7.
3. Restricciones:
Cada proyecto debe ser realizado por un solo ingeniero:
Cada ingeniero debe ser al menos un proyecto y no puede hacer más de 2:
El siguiente tutorial muestra cómo resolver este problema de asignación con Solver de Excel:
Se puede observar que para efectos de Solver, las variables de decisión binarias se deben definir como una restricción adicional. También puede resultar que luego de resolver Solver no encuentre inmediatamente la mejor solución posible. Para enfrentar esta situación se puede «volver a resolver» sobre la solución que el programa nos haya proporcionado hasta el momento para verificar si se puede lograr algo mejor. Esta situación es la que sucedió en el tutorial y a continuación se muestra la solución óptima (final) encontrada por Solver.
En total se requieren 56 horas para realizar los 7 proyectos. El ingeniero A realiza el P7, el ingeniero B el P3 y P5, el ingeniero C el P6, el ingeniero D el P2 y P4 y el ingeniero E el P1. Notar que cada proyecto es realizado por un ingeniero y cada ingeniero al menos realiza un proyecto, pero no más de 2 proyectos.