Pagina principal

1 Definicion del problema

El problema de asignación clásico se ocupa de compaginar un conjunto a los trabajadores que previamente a la asignación se conoce que presentan diversas habilidades con los trabajos que deberán ser asignados. Se sabe que la variación de la habilidad afecta el costo de asignar un trabajo a un trabajador, dicho lo anterior el objetivo del problema es determinar la asignación de los trabajadores a los trabajos minimizando el costo total.

El problema de asignación se puede encontrar de varios tipos. El problema de asignación general con n trabajadores y m trabajos está representado en la siguiente figura. El elemento cij representa el costo de asignar el trabajador i al trabajo j.

  • Balanceados: Asignación uno a uno, donde \(|A| = |B|\)

  • Desbalanceados: Asignación uno a uno o uno a varios.

    • En la fuente, donde \(|A| < |B|\).

  • En la los destinos, donde \(|A| > |B|\).

2 Modelación matemática.

El problema de asignación puede ser formulado matemáticamente así:

1. Conjuntos.

  • \(A_{i}:=\) Conjunto de trabajadores/elementos a asignar, \(\: i \in \{1, 2, ... ,n\}\)

  • \(B_{j}:=\) Conjunto de Trabajos/ ubicaciones a llenar, \(\: j \in \{1, 2, ... ,m\}\)

2. Parámetros.

  • \(c_{ij}:=\) Costo de asignar el trabajador/elemento i, al trabajo/ubicacion j, \(i \in A, j \in B\)

3. Variables de decisión.

  • \[x_{ij}:= \left\{\begin{matrix} \textrm{1, si el trabajo/ubicacion j es asignado al trabajador/ elemento i} \ i \in A, j \in B \\ \textrm{0, en caso contrario} \end{matrix}\right.\]

4. Función objetivo.

\[ Min \: C_{Total}= \sum_{i \in A}\sum_{j \in B} c_{ij} \times x_{ij} \]

5. Restricciones.

5.1. Asignación de trabajadores/elementos: A cada trabajador/elemento \(i\) se le debera asignar un unico trabajo/ubicacion \(j\).

\[\sum_{j \in B} x_{ij} = 1, \: \forall \: i \in A\] 5.2. Asignación de trabajos/ubicaciones: A cada trabajo/ubicacion \(j\) se le debera asignar un unico trabajador/elemento \(i\).

\[\sum_{i \in A} x_{ij} = 1, \: \forall \: j \in B\]

5.3. Dominio de variables: Las asignaciones son representadas a traves de variables binarias.

\[ x_{ij} \in \{0,1\} \: \: \forall \: i \in A, j \in B\]