Modelo de Asignación

 

Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o no.  Así es que podemos representar éstas posibilidades con los valores 0 (no) y 1 (si), y aprovechar las matemáticas para que nos den una mano ante decisiones difíciles; a esto es lo que solemos llamar -por obvias razones- Programación Binaria.


Una de las muchísimas aplicaciones de la Programación Binaria, es el problema de la Asignación.  Este método analiza el problema de asignar un cierto número de recursos a un determinado número de tareas, con base en algún tipo de valoración para cada recurso. Cada recurso, podrá ser asignado a una sola tarea. 


Se debe asignar el recurso i a la tarea j ? Si o no? He ahí la cuestión, =p

 


Ejemplo:

 

Se tienen tres personas (recurso) para asignarlos a tres labores diferentes. Cada uno de ellos puede efectuar cualquiera de las tareas existentes, pero con diferente nivel de especialidad. Sus respectivos jefes los han calificado de 1 a 10, para cada tarea en particular. Por supuesto el objetivo es el de asignar a las personas de manera tal que la calificación en conjunto sea la máxima.  Ver tabla de calificaciones abajo.


Calificación de Operario por Tarea

  Tarea 1 Tarea 2 Tarea 3
Operario 1 8 6 4
Operario 2 9 7 3
Operario 3 6 5 7

Nota: También funciona para minimizar. Por ejemplo, en vez de calificación podrían ser tiempos de manufactura de cualquier tipo de productos, y el objetivo sería el de minimizar el tiempo total de manufactura.

Xij = 1 si asignamos el operario i a la tarea j, de lo contrario 0


En éste orden de ideas, nuestro deseo es maximizar la calificación total al asignar los operarios a las diferentes tareas.


Max Z =  8X11 + 6 X12 + 4 X13 + 9X21 +7 X22 +3X33 +6X31 +5X32 +7X33
            Sujeto a:
            1. Cada operario sólo puede tener una tarea asignada
                X11 +X12 +X13 = 1  (Es decir, sólo se puede responder Si una sóla vez.)
                X21 +X22 +X23 = 1
                X31 +X32 +X33 = 1
    2. Cada tarea puede tener un sólo operario asignado (la restricción anterior no necesariamente                   garantiza esto, seguro!)
                X11 + X21 + X31 = 1
                X12 + X22 + X32 = 1
                X13 + X23 + X33 = 1
   3. La obvia: Xij = 0,1 para toda i y toda j.


Ahora en Excel...


Este puede ser el formato:

 

Las variables de decisión, están localizadas en el rango de celdas B4:D6, como ya habíamos dicho son binarias, van a tomar el valor de 1 si se asigna ese operario a esa tarea, cero de lo contrario. La calificación que se logre está en la celda B2, y es el resultado de sumar el producto de dichas variables con su respectiva calificación en la matriz de abajo. Ya se había dicho que esto se logra facílmente así: =SUMAPRODUCTO(B4:D6,B9:D11). Como un operario sólo se puede asignar a una tarea, colocamos una columna de Suma (E), ésta es por ejemplo para la celda E4: =B4+C4+D4. Cuando agreguemos las restricciones, ésta columna debe ser igual a uno, pues sólo se puede responder que si una vez, ni más, ni menos. De igual manera agregamos una fila (7), para asegurarnos que a una tarea sólo se asigne un operario, por ejemplo la celda B7: =B4+B5+B6 Deberá ser igual a 1.  Ahora en el cuadro de diálogo de los parámetros de Solver, lo colocamos así:

 

 

Luego de hacer click en resolver...

 

La calificación máxima lograda es de 22.  Y se asignó el operario 1 a la tarea 2, el operario 2 a la tarea 1 y el operario 3 a la tarea 3.  Fácil, no?
Para los programas Lineales enteros es muy importante que Solver, esté debidamente configurado para un número suficiente de iteraciones, de tiempo,  de precisión y de convergencia, para esto ver los detalles de Solver.

 

 

Contenido :

Social