Problema de transporte

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas y economía, un problema de transporte es un caso particular de problema de programación lineal en el cual se debe minimizar el coste del abastecimiento a una serie de puntos de demanda a partir de un grupo de puntos de oferta —posiblemente de distinto número—, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda.

Planteamiento[editar]

Se disponen n \in \mathbb{N} puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y m \in \mathbb{N} puntos de demanda o mercados de demanda determinada (vector M):

F \in \mathbb{R}^n;\; F = (F_1, F_2, F_3, \cdots, F_n)
M \in \mathbb{R}^m;\; M = (M_1, M_2, M_3, \cdots, M_m)

Además se dispone como dato de una matriz de precios, C, de forma que C_{i j} es el precio de envío por unidad desde la factoría F_i al mercado M_j:

C \in \mathcal{M}_{n \times m}(\mathbb{R})

El objetivo es calcular una nueva matriz, X, de forma que X_{i j} sea el número de unidades que se envían de la factoría F_i al mercado M_j.

X \in \mathcal{M}_{n \times m}(\mathbb{R})

Con estos datos podemos formular las condiciones que se han de cumplir:

\sum_{i = 1}^{n} X_{i j} \geq M_j \;\; \forall j \in \mathbb{N} / 1 \leq j \leq m
\sum_{j = 1}^{m} X_{i j} \leq F_i \;\; \forall i \in \mathbb{N} / 1 \leq i \leq n
X_{i j} \geq 0 \;\; (i, j \in \mathbb{N}; 1 \leq i \leq n; 1 \leq j \leq m)

El precio total a pagar por el transporte, C_T, que se ha de minimizar, se determinará por la suma de los productos del precio de cada unidad por el coste de envío por unidad de cada fábrica a cada mercado:

C_T = \sum_{i = 1}^{n} \sum_{j = 1}^{m} X_{i j} \cdot C_{i j}
\min \; C_T

Problemas balanceados[editar]

Se dice que el problema está balanceado cuando se cumple que:

\sum_{i = 1}^{n} F_i = \sum_{j = 1}^{m} M_j

(o, abreviadamente, \sum F = \sum M, es decir, la oferta es igual a la demanda).

En caso de que \sum F > \sum M, se incorporaría un mercado adicional al problema, el mercado artificial, M_a, de forma que su demanda sea el excedente y el coste de envío a este mercado sea nulo:

C_{i a} = 0 \;\; \forall i \in \mathbb{N} / 1 \leq i \leq n.

Solución con método de cruce del arroyo[editar]

Para que un problema de transporte pueda ser resuelto a través de éste método debe cumplir con las características que se mencionarán. Si no es posible, se deben resolver por el método simplex.

  • Ser un problema balanceado.
  • Contar con (n+m-1) variables de decisión, siendo n los puntos de demanda y m los puntos de oferta.

Algoritmo[editar]

  • Crear tabla de transporte
Proveedor 1 Proveedor 2 Proveedor m
Punto de oferta 1 costo(i, j) costo(i, j+1) costo(i, j+m) Oferta 1
Punto de oferta 2 costo(i+1,j) costo(i+2,j+1) costo(i+n, j+m) Oferta 2
Punto de oferta n costo(i, j) costo(i+1,j+1) costo(i+n, j+m) Oferta n
Demanda 1 Demanda 2 Demanda m
  • Establecer solución inicial

Existen varios métodos para hacer esto: Noreste y sus variaciones(Suroeste, Suroeste, etc), y Costo mínimo. Para el de costo mínimo:

    • Ordenar los costos de mayor a menor
    • En la celda (i, j) asignar el mínimo entre la demanda j, y la oferta i
    • Restar a la oferta j y la demanda i el valor asignado
    • repetir los últimos dos pasos hasta que la oferta y la demanda de todas las filas y columnas sea igual a 0
  • Calcular índices de mejora

Todos los lugares que no contienen un valor se les considera agua y los valores asignados piedras los índices se calculan para todos los lugares que contienen agua, de tal forma que se busca moverse por fila y columna hasta generar un circuito, se multioplican los costos por +1,-1...

  • Si existe una mejora realizarla y volver al paso de calcular los índices de mejora

Si se encuentra un índice negativo en los circuitos, se busca el de los -1 el menor y se le suma o resta según el signo a todo los circuitos