Problema de transporte

Problema de transporte

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

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_ij 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_ij 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

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 arrollo

Para que un problema de transporte pueda ser resuelto a través de éste método debe cumplir con las caracterizticas que se mencionaran, si no es posible, se deben resolver por el método simplex.

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

Algoritmo

• Crear tabla de transporte

	Proveedor 1	Proveedor 2	Proveedor n
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 ésto: Noreste y sus variaciones(Suroeste, Suroeste, etc), y Costo minimo. 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 ultimos dos pasos hasta que la oferta y la demanda de todas las filas y columnas sea igual a 0

• Calcular indices de mejora

Todos los lugares que no contienen un valor se les considera agua y los valores asignados piedras los indices 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 indices de mejora

Si se encuentra un indice negativo en los circuitos, se busca el de los -1 el menor y se le suma o resta segun el signo a todo los circuitos

Obtenido de "Problema de transporte"