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.

  • \(q_{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 q_{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} q_{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} q_{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}^{+}\).

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

2 Extensión Limitar conexiones.

El problema consiste en que la red estará desconectada entre algunos nodos, lo que conlleva a la imposibilidad de transportar desde uno/unos nodos origenes i a uno/unos nodos destinos j.

Para lo anterior se deberá crear conjuntos auxiliares e indexados que modelen las conexiones posibles.

2.1. Conjuntos.

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

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

2.2. Subcojuntos

  • \(Od_{j}:=\) Subconjuntos de origenes que pueden atender al destino j, \(j \in D\).

  • \(Do_{i}:=\) SubConjuntos de destinos que pueden ser atendidos por el origen i, \(i \in O\).

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 origen i, al destino j, \(i \in O, j \in D\).

2.3. Variables de decisión.

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

2.4. Función Objetivo: Se pueden presentar dos alternativas para la funcion objetivo

  • Alternativa 1.

    \[ C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D_i} c_{ij} \times q_{ij} \]

  • Alternativa 2.

    \[ C_{Total}= \sum_{i \ \in \ O_j}\sum_{j \ \in \ D} c_{ij} \times q_{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 \in O_i} q_{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_{j \in D_j} q_{ij} \leq k_i, \: \forall \:i \in O\]

2.5.3. 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}^{+}\).

\[ q_{ij} \geq 0 \: \: \forall \: i \in O, j \in D_i\]

Ejercicio: Construya los subcojuntos \(Do_{i}\) y \(Od_{j}\) , teniendo en cuenta el grafico y los conjuntos que se muestran a continuación:

\[ O: \left\lbrace A, B, C \right\rbrace \]

\[ D: \left\lbrace 1, 2, 3, 4, 5, 6, 7, 8 \right\rbrace \]

Solución

  • Subcojuntos \(Do_{i}\)

    • \(Do_{A}: \left\lbrace 1, 2, 6, 7, 8 \right\rbrace\).
    • \(Do_{B}: \left\lbrace 2, 3, 5, 6, 7 \right\rbrace\).
    • \(Do_{C}: \left\lbrace 1, 2, 3, 4 \right\rbrace\).
      .

  • Subcojuntos \(Od_{j}\)

    • \(Od_{1}: \left\lbrace A, C \right\rbrace\).
    • \(Od_{2}: \left\lbrace A, B, C \right\rbrace\).
    • \(Od_{3}: \left\lbrace B, C \right\rbrace\).
    • \(Od_{4}: \left\lbrace C \right\rbrace\).
    • \(Od_{5}: \left\lbrace B \right\rbrace\).
    • \(Od_{6}: \left\lbrace A, B \right\rbrace\).
    • \(Od_{7}: \left\lbrace A, B \right\rbrace\).
    • \(Od_{8}: \left\lbrace A \right\rbrace\).

3 Extensión número de viajes.

El problema considera los mismos supuestos del problema basico. Adicionalmente se debe determinar cuantos viajes son necesarios para transportar todas las unidades requeridas por los destinos. Para esto se debe:

  • Crear una variable entera que permita medir cuantos viajes son necesarios. (obligatorio)
  • Crear un nuevo parámetro que determine la capacidad maxima por viaje. (obligatorio)
  • Crear un nuevo parámetro que determine el costo por viaje. (opcional)
  • Crear un nuevo parámetro que determine el Lote/volumen/peso/valor minimo enviado por viaje. (opcional).

3.1. Conjuntos.

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

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

3.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\).

  • \(L:=\) Capacidad maxima por viaje.

3.3. Variables de decisión.

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

  • \(n_{ij}:=\) Número de viajes realizados desde el nodo i hacia el nodo j, \(i \in O, j \in D\\\).

3.4. Función objetivo.

\[ Min \: C_{Total}= \sum_{i \ \in \ O}\sum_{j \ \in \ D} c_{ij} \times q_{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\).

\[\sum_{i \in O} q_{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.

\[\sum_{j \in D} q_{ij} \leq k_i, \: \forall \:i \in O\]

3.5.3 Determinación del numero de viajes: El numero de viajes necesarios puede ser calculado como la cantidad de unidades que se envien desde el nodo i al nodo j entre la capacidad maxima que se puede enviar.

\[ \frac{q_{ij}}{L} \leq n_{ij} \: \: \forall \: i \in O, j \in D \]

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

\[ q_{ij} \geq 0 \: \: \forall \: i \in O, j \in D\] 3.5.5. Dominio de las variables \(n_{ij}\): El numero de viajes realizados desde los origenes \(i\) hacia los destinos \(j\) debe ser un numero entero positivo \({\mathbb Z}^{+}\).

\[ n_{ij} \in {\mathbb Z}^{+} \: \: \forall \: i \in O, j \in D\]

Observación 1: Si existe un parámetro asociado al costo por viaje entonces la funcion objetivo cambia a minimizar el costo total de viajes:

\(v_{ij}:\) Costo de de un viaje desde el nodo i al nodo j, \(i \in O, j \in D\)

\[ Min \: Cost\_Viaj= \sum_{i \ \in \ O}\sum_{j \ \in \ D} v_{ij} \times n_{ij}\] Observación 2: Si hay un Lote/volumen/peso/valor minimo enviado por viaje Se debe agregar dicho parámetro y una restricción:

\(L_{min}:=\) Lote/volumen/peso/valor minimo que se debe enviar en cada viaje.

3.5.6 Garantizar lote minimo: La cantidad de unidades a enviar desde el nodo i al nodo j debe ser mayor o igual al numero de viajes por la cantidad de Lote/volumen/peso/valor minimo que se puede enviar en cada viaje.

\[ q_{ij}\geq L_{min} \times n_{ij} \: \: \:\forall \: i \in O, j \in D\]