Pagina principal

1 Problema básico

El problema de transporte puede ser formulado matemáticamente así:

1.1. Conjuntos.

  • \(O:=\) Conjunto de orígenes, \(\: i \in \{1, 2, ... ,n\}\)

  • \(D:=\) Conjunto de destinos, \(\: j \in \{1, 2, ... ,m\}\)

1.2. Parámetros.

  • \(d_{j}:=\) Demanda del destino j, \(j \in D\)

  • \(k_{i}:=\) Capacidad del origen i, \(i \in O\)

  • \(c_{ij}:=\) Costo de trasportar una unidad desde el origen i, al destino j, \(i \in O, j \in D\).

1.3. Variables de decisión.

  • \(x_{ij}:=\) Cantidad de unidades a transportar desde el origen i, al destino j, \(i \in O, j \in D\\\)

1.4. Función objetivo.

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

1.5. Restricciones.

1.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes \(i\).

\[\sum_{i \in O} x_{ij} = d_j, \: \forall \: j \in D\] 1.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad.

\[\sum_{j \in D} x_{ij} \leq k_i, \: \forall \:i \in O\] 1.5.3. Dominio de variables: La cantidad unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).

\[ x_{ij} \geq 0 \: \: \forall \: i \in O, j \in D\]

2 Problema de Transbordo

El problema de transbordo es un extensión del problema original de transporte. En esta extension existe la posibilidad de transportar unidades desde un nodo origen a nodos intermedios, para luego realizar envios desde dichos nodos intermedios hasta los nodos destinos. Tal como muestra la grafica a continuación:

2.1. Conjuntos.

  • \(V:=\) Conjunto de todos los nodos de la red.

  • \(O:=\) Conjunto de orígenes.

  • \(I:=\) Conjunto de intermedios.

  • \(D:=\) Conjunto de destinos.

  • \(E:=\) Conjunto de aristas

2.3. Parámetros.

  • \(d_{j}:=\) Demanda del destino j, \(j \in D\)

  • \(k_{i}:=\) Capacidad del origen i, \(i \in O\)

  • \(c_{ij}:=\) Costo de trasportar una unidad desde el nodo i, al nodo j, \((i,j) \in E\).

2.3. Variables de decisión.

  • \(x_{ij}:=\) Cantidad de unidades a transportar desde el nodo i, hasta el nodo j, \((i,j) \in E\)

2.4. Función Objetivo:

\[C_{Total}= \sum_{(i,j) \ \in \ E} c_{ij} \times x_{ij}\]

2.5. Restricciones.

2.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes\(i\), siempre que exista una conexion entre \(i\) y \(j\).

\[\sum_{(i,j) \ \in \ E} x_{ij} = d_j, \: \forall \: j \in D\]

2.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad, siempre que exista una conexion entre \(i\) y \(j\).

\[\sum_{(i,j) \ \in \ E} x_{ij} \leq k_i, \: \forall \:i \in O\] 2.5.3 Conservación del flujo: La cantidad de unidades que entra a los nodos intermedio a traves de los nodos origenes, debe ser estrictamente igual a la cantidad de unidades que salen desde los nodos intermedios hacia los destinos.

\[\sum_{(i,k) \ \in \ E}x_{ik} = \sum_{(k,j) \ \in \ E} x_{kj} \: \: \forall \:k \in I\]

2.5.4. Dominio de variables: La cantidad de unidades enviadas desde los origenes \(i\) hacia los destinos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).

\[ x_{ij} \geq 0 \: \: \forall \: (i,j) \in E\]

3 Alternativa de modelación problema de transbordo.

3.1. Conjuntos.

  • \(V:=\) Conjunto de todos los nodos de la red.

  • \(O:=\) Conjunto de orígenes.

  • \(I:=\) Conjunto de intermedios.

  • \(D:=\) Conjunto de destinos.

  • \(E:=\) Conjunto de aristas

3.3. Parámetros.

  • \(d_{j}:=\) Demanda del destino j, \(j \in D\)

  • \(k_{i}:=\) Capacidad del origen i, \(i \in O\)

  • \(c_{ij}:=\) Costo de trasportar una unidad desde el nodo i, al nodo j, \(i \in V, j \in V\).

3.3. Variables de decisión.

  • \(x_{ij}:=\) Cantidad de unidades a transportar desde el nodo i, hasta el nodo j, \(i \in V, j \in V\\\)

3.4. Función Objetivo:

\[C_{Total}= \sum_{(i,j) \ \in \ E} c_{ij} \times x_{ij}\]

3.5. Restricciones.

3.5.1. Cumplimiendo de la demanda: Para cada destino \(j\) se debe satisfacer la demanda en su totalidad por la oferta de todos los orígenes\(i\), siempre que exista una conexion entre \(i\) y \(j\).

\[\sum_{i \ \in \ I} x_{ij} = d_j, \: \forall \: j \in D\]

3.5.2. Limitación de la capacidad: La cantidad de unidades enviadas desde cada origen \(i\) hacia todos los destinos \(j\) no debe exceder a su capacidad, siempre que exista una conexion entre \(i\) y \(j\).

\[\sum_{j \ \in \ I} x_{ij} \leq k_i, \: \forall \:i \in O\] 3.5.3 Conservación del flujo: La cantidad de unidades que entra a los nodos intermedio a traves de los nodos origenes, debe ser estrictamente igual a la cantidad de unidades que salen desde los nodos intermedios hacia los destinos.

\[\sum_{i \ \in \ O}x_{ik} = \sum_{(k,j) \ \in \ E} x_{kj} \: \: \forall \:k \in I\]

3.5.4. Dominio de variables: La cantidad de unidades enviadas desde el nodo \(i\) hacia los nodos \(j\) debe ser un un numero real positivo \({\mathbb R}^{+}\).

\[ x_{ij} \geq 0 \: \: \forall \: i \in (O \ \cup I) , j \in (i \ \cup \ D)\]