Problema de Asignación en Programación Entera resuelto con Solver

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.

Tabla Asignación

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

Variables de Decisión Asignación

2. Función Objetivo: Minimizar el tiempo total requerido para completar los proyectos

Función Objetivo Asignación

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:

Restricción Asignación

Cada ingeniero debe ser al menos un proyecto y no puede hacer más de 2:

Restricción Asignación Ingenieros

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.

Solución Óptima Problema de Asignación

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.

Rating: 4.7. From 3 votes.
Please wait...

, , , , , ,

11 Comentarios para Problema de Asignación en Programación Entera resuelto con Solver

  1. lucia 16/11/2013 en 11:55 #

    hola como deduces que cada ingeniero no puede hacer mas de 2 proyectos?

  2. lucia 16/11/2013 en 11:59 #

    o quizá esas ya eran las restricciones de tus problemas 😕

    • GEO Tutoriales 16/11/2013 en 18:53 #

      @lucia. Es un supuesto que hemos asumido para la formulación del modelo. Es parte de la descripción del problema.

  3. Annie 03/02/2016 en 11:15 #

    ¿Qué significa las iniciales L.I y L.D?. Gracias

    • GEO Tutoriales 03/02/2016 en 11:34 #

      @Annie. Es sólo una abreviación, L.I representa el lado izquierdo de las restricciones y L.D. el lado derecho de las restricciones.

  4. Luis Yari 22/11/2016 en 18:54 #

    ¿Qué pasaría si agrego que el proyecto 5 no lo puede realizar el ingeniero B?, ¿cómo cambiaría la restricción?

    • GEO Tutoriales 24/11/2016 en 14:04 #

      @Luis. Si el ingeniero B no puede realizar el proyecto 5 se puede imponer como restricción adicional X(B,P5)=0.

  5. Diego 28/11/2016 en 0:09 #

    ¿Cómo dedujiste que la función objetivo de este problema quedaría en minimizar z?

    • GEO Tutoriales 25/08/2017 en 21:08 #

      @Diego. Simplemente en base a la información detallada en la problemática donde naturalmente se busca completar los proyectos en el menor tiempo posible.

  6. Javier 11/05/2017 en 8:05 #

    Hola. ¿Cómo podrías asignar prioridades a cada proyecto?

    • GEO Tutoriales 25/08/2017 en 21:06 #

      @Javier. En la formulación propuesta se deben desarrollar todos los proyectos. No obstante no siempre se dispone de los recursos necesarios para abordar la totalidad de proyectos que puedan estar en cartera. En este contexto se puede “penalizar” en la función objetivo el no considerar un proyecto al momento de tomar una decisión y esa penalización puede ser diferenciada entre proyectos de modo de asignar una importancia relativa.

Deja un comentario