Descripción del modelo : USApHLPL
| Sitio: | knuth.uca.es |
| Curso: | Localización de concentradores o hubs 21-22 |
| Libro: | Descripción del modelo : USApHLPL |
| Imprimido por: | Invitado |
| Día: | martes, 3 de diciembre de 2024, 18:27 |
Descripción
Determinar p concentradores de entre n nodos donde a cada nodo se le asigna un único concentrador (asignación simple).
1. Introducción
Una vez presentado lo que es un problema de localización de concentradores y una aplicación de estos en la actualidad ( urban hubs ) vamos a implementar una aplicación de modo que introduciendo un número deseado de concentradores en una red nos devuelva, de entre todos los nodos que componen la red, los mejores candidatos a concentrador. Para ello, hemos utilizado el modelo USApHLPL.
Este modelo deriva de un modelo no lineal llamado Localización de p concentradores con asignación simple. La versión del problema como un problema de programación lineal se la debemos a Campbell. Así, el problema admite la siguiente formulación como problema de programación lineal entera binaria. En las siguientes páginas de este libro vamos a describir el modelo USApHLPL.
2. Inputs y variables
\(\textbf{INPUTS}\)
Factores de descuento:
- \(O\)= Factor de recolecta: Si la arista del grafo va desde un nodo a un concentrador.
- \(X\)= Factor del concentrador: Si una arista une un concentrador con otro concentrador.
- \(D\)= Factor de destino: Si la arista del grafo va desde un concentrador a un nodo.
\(O,X,D \geq 0\)
\( w_{ij} =\) cantidad de producto a transportar entre el nodo \(i\) y el nodo \(j\).
\( c_{ij} =\) costo de enviar una unidad de producto desde el nodo \(i\) al nodo \(j\).
\(p\) = número de concentradores que se quiere localizar.
En consecuencia, el coste de enviar \( w_{ij} \) unidades de producto desde el nodo de origen \(i\) hasta el nodo de destino \(j\) a través de los concentradores \(k\) y \(m\) (en este orden) es:
\(C_{ijkm}=w_{ij}(Oc_{ik}+Xc_{km}+Dc_{mj})\)
\(\textbf{VARIABLES}\)
\(x_{ijkm}\) es la fracción de flujo \(w_{ij}\) que se manda desde el origen \(i\) al nodo \(j\) a través de los concentradores \(k\) y \(m\) (en este orden)
\(y_{i}=\left\{\begin{matrix}
1 & \text{si el nodo } i \text{ es un concentrador } & \\
0 & cc \hspace{51 mm} &
\end{matrix}\right. \)
\(z_{ij}=\left\{\begin{matrix}
1 & \text{si el nodo } i \text{ esta asignado al nodo } j& \\
0 & cc \hspace{64 mm} &
\end{matrix}\right. \)
3. Función objetivo
\(\min \sum_{i,j,k,m} C_{ijkm}x_{ijkm} \)
Queremos minimizar el coste total.
Este coste vendrá dado por los costes de enviar un flujo \( w_{ij} \) del nodo \(i\) al nodo \(j\) a través de los concentradores \(k\) y \(m\)
4. Restricciones
\( \sum_{k,m} x_{ijkm} = 1 ,\ \ \ \forall i,j\): A cada nodo \(i\) que se conecta con el nodo \(j\) le asignamos un concentrador que va desde el concentrador \(k\) al \(m\) .
\( \sum_k y_k = p\): Obligamos a que haya \(p\) concentradores.
\(z_{ik} \leq y_k, \ \ \ \forall i,k\): No hay nodos asignados a concentradores sin usar.
\( \sum_{j.m}(w_{ij}x_{ijkm}+w_{ji}x_{jimk})=\sum_{j}(w_{ij}+w_{ji})z_{ik} , \forall i,k \) : Esta restricción provoca que la asignación sea simple.
\( 0 \leq x_{ijkm} \leq 1 , \ \ \ \forall i,j,k,m\)
\(y_i, z_{ik} \in \{0,1\} \ \ \ \forall i,k\)