Definición del problema de asignación.
Primero
que nada, es importante empezar con el pie derecho al definir un tema
importante como el que veremos a continuación.
El
problema de asignación se puede definir fácilmente como “Asignar la mejor persona para el puesto”.
Pero
veremos que este tipo de problema no se dedicara solamente a la asignación de
personas así que daremos una definición más formal para el problema de
asignación:
El
problema de asignación es un
tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan
a la realización de tareas.
Ejemplos
Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a máquinas, asignados que pueden ser empleados a quienes se tiene que dar trabajo, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.
Como observamos en algunos ejemplos los asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas.
En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos, como ¿qué candidato es el idóneo para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es el mejor para ejecutar determinada tarea?
Supuestos que debe de cumplir un problema de asignación.
Para que se ajuste a la
definición de un problema de asignación, es necesario que este tipo de aplicaciones
se formule de manera tal que se cumplan los siguientes supuestos.
1. El número de asignados
es igual al número de tareas. (Este número se denota por n.)
2. A cada asignado se le
asigna sólo una tarea.
3. Cada tarea debe
realizarla sólo un asignado.
4. Existe un costo cij
asociado con el asignado i (i= 1, 2, . . ., n) que realiza la
tarea j (j= 1,2, . . ., n).
5. El objetivo es
determinar cómo deben hacerse las n asignaciones para minimizar los
costos totales.
Es
importante mencionar que muchas
aplicaciones potenciales no se adaptan por completo al problema de asignación.
Con frecuencia es posible reformular el problema para hacerlo que se ajuste.
Por ejemplo, muchas veces se pueden usar asignados ficticios o tareas ficticias con este fin.
Formas de representar el modelo y restricciones.
El modelo
general de asignación con n trabajadores y n puestos se
representa en la tabla siguiente:
El elemento cij representa
el costo de asignar al trabajador i al puesto j (i, j = 1,
2, .., n).
El modelo
matemático para manejar el problema de asignación utiliza las siguientes
variables de decisión:
para i = 1, 2, . . . , n y
j = 1, 2, . . . , n. Entonces, cada xij es una variable
binaria que toma valores 0 o 1. Las variables binarias son importantes en
investigación de operaciones para representar las decisiones de sí o no.
En
este caso, las decisiones de sí o no son: ¿debe el asignado i realizar
la tarea j ? Si Z es el costo total, el modelo del problema de
asignación es:
sujeta
a:
y
El
primer conjunto de restricciones funcionales especifica que cada asignado
realice sólo una asignación, mientras que el segundo conjunto requiere que cada
asignación sea realizada sólo por un asignado.
Las
restricciones funcionales del modelo de asignación evitan que las variables
sean mayores que 1, y las restricciones de no negatividad impiden que existan
valores menores que cero. Por tanto, si se elimina la restricción binaria para
poder resolver el problema de asignación como un problema de programación
lineal, las soluciones que se obtienen (incluso la solución óptima final) satisfacerán
en forma automática la
restricción binaria.
El
problema de asignación puede describirse de manera similar, como se ve en la
figura que se muestra abajo. En este caso la primera columna enumera los n asignados
y la segunda las n tareas. Los números entre corchetes indican el número
de asignados que se proporcionan en ese lugar de la red, por lo cual los valores
de la izquierda son 1 de manera automática, mientras que los valores de -1 de
la derecha indican que cada tarea utiliza un asignado.
 |
| Representación de red del problema de asignación |
Referencias
Lieberman, G., & Hillier, F. (2010). Problema de asignación. En G. J. Frederick S. Hillier, Introducción
a la Investigación de operaciones (Novena ed., pp. 309-312). México: Mc
Graw Hill.
Taha, H. (2004). El Modelo de asignación. En H. A. Taha, Investigación
de operaciones (Séptima ed., p. 196). México: Pearson.
No hay comentarios.:
Publicar un comentario