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.

Contenido 1 Planteamiento 1.1 Problemas balanceados 1.2 Solución con método de cruce del arrollo 2 Algoritmo

Planteamiento

Se disponen puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y puntos de demanda o mercados de demanda determinada (vector 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:

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.

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

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:

Problemas balanceados

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

(o, abreviadamente, , es decir, la oferta es igual a la demanda).

En caso de que , 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:

.

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