Extensiones al problema de asignación
Yelky Castro Jiménez
Víctor Mario Noble Ramos
2022-09-02
1 Maximizar la afinidad de las asignaciones.
El problema de asignación tiene diferentes extensiones que dependerán de cada situacion que se quiera modelar. A continuación se presenta la formulación cuya extensión tiene como objetivo maximizar la afinidad de los recursos a asignar entre los conjuntos. El modelo original se altera desde la funcion objetivo, y el cambio de parametros que se hacen necesarios para esta extensión.
1.1. Conjuntos.
\(A:=\) Conjunto de elementos a asignar, \(\: i \in \{1, 2, ... ,n\}\)
\(B:=\) Conjunto de ubicaciones a llenar, \(\: j \in \{1, 2, ... ,n\}\)
1.2. Parámetros.
- \(Af_{ij}:=\) Afinidad entre el elemento i y la ubicacion j, \(i \in A, j \in B\)
1.3. Variables de decisión.
- \[x_{ij}:= \left\{\begin{matrix} \textrm{1, si la ubicacion j es asignado al elemento i} \ i \in A, j \in B \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
1.4. Función objetivo.
\[ Max \: Afin_{Total}= \sum_{i \in A}\sum_{j \in B} Af_{ij} \times x_{ij} \]
1.5. Restricciones.
1.5.1. Asignación de elementos: A cada elemento \(i\) se le debera asignar una unica ubicacion \(j\).
\[\sum_{j \in B} x_{ij} = 1, \: \forall \: i \in A\] 1.5.2. Asignación de las ubicaciones: A cada ubicacion \(j\) se le debera asignar un unico elemento \(i\).
\[\sum_{i \in A} x_{ij} = 1, \: \forall \: j \in B\]
1.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\]
2 Desbalance en los elementos y/o ubicaciones
2.1. Conjuntos.
\(A:=\) Conjunto de elementos a asignar, \(\: i \in \{1, 2, ... ,n\}\)
\(B=\) Conjunto de ubicaciones a llenar, \(\: j \in \{1, 2, ... ,m\}\)
2.2. Parámetros.
- \(Af_{ij}:=\) Afinidad entre el elemento i y la ubicacion j, \(i \in A, j \in B\)
2.3. Variables de decisión.
- \[x_{ij}:= \left\{\begin{matrix} \textrm{1, si la ubicacion j es asignado al elemento i} \ i \in A, j \in B \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
2.4. Función objetivo.
\[ Max \: Afin= \sum_{i \in A}\sum_{j \in B} Af_{ij} \times x_{ij} \]
2.5. Restricciones.
2.5.1. Asignación de elementos: A cada elemento \(i\) se le debera asignar al menos una ubicacion \(j\).
\[\sum_{j \in B} x_{ij} \geq 1, \: \forall \: i \in A\]
2.5.2. Asignación de las ubicaciones: A cada ubicacion \(j\) se le debera asignar al menos un elemento \(i\).
\[\sum_{i \in A} x_{ij} \geq 1, \: \forall \: j \in B\]
2.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\]
3 Capacidad en las ubicaciones, volumen en los elementos
En esta extensión se presenta un volumen previamente definido en cada uno de los elementos, se debe garatizar que el volumen(es) de el/los elemento(s) a asignar en una ubicación no sobrepase su capacidad.
3.1. Conjuntos.
\(A:=\) Conjunto de elementos a asignar, \(\: i \in \{1, 2, ... ,n\}\)
\(B:=\) Conjunto de ubicaciones a llenar, \(\: j \in \{1, 2, ... ,n\}\)
3.2. Parámetros.
- \(Af_{ij}:=\) Afinidad entre el elemento i y la ubicacion j, \(i \in A, j \in B\)
- $v_{i}:= $ Volumen del elemento i, \(i \in A\)
- $Cap_{i}:= $Capacidad de la ubicación j, \(j \in B\)
3.3. Variables de decisión.
- \[x_{ij}:= \left\{\begin{matrix} \textrm{1, si la ubicacion j es asignado al elemento i} \ i \in A, j \in B \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
3.4. Función objetivo.
\[ Max \: Afin_{Total}= \sum_{i \in A}\sum_{j \in B} Af_{ij} \times x_{ij} \]
3.5. Restricciones.
3.5.1. Asignación de elementos: A cada elemento \(i\) se le debera asignar una unica ubicacion \(j\).
\[\sum_{j \in B} x_{ij} = 1, \: \forall \: i \in A\] 3.5.2. Asignación de las ubicaciones: A cada ubicacion \(j\) se le debera asignar un unico elemento \(i\).
\[\sum_{i \in A} x_{ij} = 1, \: \forall \: j \in B\]
3.5.3. Respetar capacidad de las ubicaciones: El volumen de cada elemento \(i\) no debe superar la capacidad de la ubicacion \(j\) donde será asignada.
\[\sum_{i \in A} v_{i} \times x_{ij} = Cap_{j} \: \forall \: j \in B\]
3.5.4. Dominio de variables: Las asignaciones son representadas a traves de variables binarias.
\[ x_{ij} \in \{0,1\} \: \: \forall \: i \in A, j \in B\]
4 Multiperiodos
4.1. Conjuntos.
\(A:=\) Conjunto de elementos a asignar.
\(B:=\) Conjunto de ubicaciones a llenar.
\(T:=\) Conjunto de periodos.
4.2. Parámetros.
- \(Af_{ij}:=\) Afinidad entre el elemento i y la ubicacion j, \(i \in A, j \in B\)
4.3. Variables de decisión.
- \[x_{ijt}:= \left\{\begin{matrix} \textrm{1, si el elemento i es asignado a la ubicación j en el periodo t} \ i \in A, j \in B, t \in T \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
4.4. Función objetivo.
\[ Max \: Afin_{Total}= \sum_{i \in A}\sum_{j \in B}\sum_{t \in T} Af_{ij} \times x_{ijt} \]
4.5. Restricciones.
4.5.1. Asignación de elementos: A cada elemento \(i\) se le debera asignar una unica ubicacion \(j\) en cada periodo \(t\).
\[\sum_{j \in B} x_{ijt} = 1, \: \forall \: i \in A, t \in T\]
4.5.2. Asignación de las ubicaciones: A cada ubicacion \(j\) se le debera asignar un unico elemento \(i\) en cada periodo \(t\) .
\[\sum_{i \in A} x_{ijt} = 1, \: \forall \: j \in B, t \in T\]
4.5.3. Dominio de variables: Las asignaciones son representadas a traves de variables binarias.
\[ x_{ijt} \in \{0,1\} \: \: \forall \: i \in A, j \in B, t \in T\]
5 Asignación de asignaciones (Asignación multinivel)
El problema de asignación en varios niveles se conoce en la literatura como problema de asignación generalizada multinivel, es una extensión del clásico problema de asignación, en donde se introduce diferentes niveles de eficiencia asociados a cada agente para realizar cada tarea. Ahora, los n elementos se pueden asignar a m ubicaciones con un numero de l niveles de eficiencia.
5.1. Conjuntos.
\(E:=\) Conjunto de todos los elementos a asignar.
\(U:=\) Conjunto de todas las ubicaciones a llenar.
\(GE:=\) Conjunto de grupos de elementos.
\(GU:=\) Conjunto de grupos de ubicaciones
5.2. Subconjuntos.
\(A_{e}:=\) subconjunto de elementos \(i\) que pertenecen al grupo de elementos \(e\), \((e \in GE) \subset E\)
\(B_{u}:=\) subconjunto de ubicaciones \(j\) que pertenecen al grupo de ubicaciones \(u\), \((u \in GU) \subset U\)
5.2. Parámetros.
\(W_{eu}:=\) Afinidad entre el grupo de elemento \(e\) y grupo de ubicacion \(u\), \(E \in GE, u \in GU\)
\(w_{ij}:=\) Afinidad entre el elemento i y la ubicacion j, \(i \in E, j \in U\)
5.3. Variables de decisión.
\[y_{eu}:= \left\{\begin{matrix} \textrm{1, si el grupo de elementos e es asignado al grupo de ubicaciones u.} \ e \in GE, u \in GU \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
\[x_{ij}:= \left\{\begin{matrix} \textrm{1, si elemento i es asignado a la ubicacion j.} \ i \in E, j \in U \\ \textrm{0, en caso contrario} \end{matrix}\right.\]
5.4. Función objetivo.
\[ Max \: Afin_{Total}= \sum_{e\in GE} \sum_{u \in GU} (W_{eu} \times y_{eu}) \ + \ \sum_{i \in A_e}\sum_{j \in B_u} (w_{ij} \times x_{ij}) \]
5.5. Restricciones.
Asignación asociada al primer nivel
5.5.1. Asignación de grupos de elementos: A cada grupo de elementos \(e\) se le debera asignar un unico grupo de ubicacion \(j\).
\[\sum_{u \in GU} y_{eu} = 1, \: \forall \: e \in GE\]
5.5.2. Asignación de grupos de ubicaciones: A cada grupo de ubicacion \(u\) se le debera asignar un unico grupo de elemento \(e\).
\[\sum_{e \in GE} y_{eu} = 1, \: \forall \: u \in GU\]
Asignación asociada al segundo nivel
5.5.4. Asignación de elementos: A cada elemento \(i\) se le asignará una unica ubicación \(j\) quien pertenece a un grupo de ubicaciones u, si y solo si en el primer nivel, el elemento \(i\) pertenece al grupo de elementos \(e\) que le fue asignado al grupo de ubicaciones \(u\).
\[\sum_{j \in B_{u}} x_{ij} = y_{eu}, \: \forall \: i \in E, u \in GU, e \in GE, i \in A_{e}\] 5.5.5. Asignación de ubicaciones: A cada ubicacion \(j\) se le asignará un unico elemento \(i\) quien pertenece a un grupo de elementos e, si y solo si en el primer nivel, la ubicación \(j\) pertenece al grupo de ubicaciones \(u\) que le fue asignado al grupo de elementos \(e\).
\[\sum_{i \in A_{e}} x_{ij} = y_{eu}, \: \forall \: j \in U, u \in GU, e \in GE, j \in B_{u}\]
5.5.3. Dominio de variables: Las asignaciones son representadas a traves de variables binarias.
\[ y_{eu} \in \{0,1\} \: \: \forall \: e \in E, \in B\]
\[ x_{ij} \in \{0,1\} \: \: \forall \: i \in E, j \in U\]