Problema de transporte

Un problema de transporte^[1]​ es, en matemáticas y economía, 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.

Se disponen ${displaystyle nin mathbb {N} }$ puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y ${displaystyle min mathbb {N} }$ 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 ${displaystyle C_{ij}}$ es el precio de envío por unidad desde la factoría ${displaystyle F_{i}}$ al mercado ${displaystyle M_{j}}$:

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

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

El precio total a pagar por el transporte, ${displaystyle 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:

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

(o, abreviadamente, ${displaystyle sum F=sum M}$, es decir, la oferta total es igual a la demanda total).

En caso de que ${displaystyle sum F>sum M}$ (Oferta total sea mayor a la demanda total) se incorporaría un centro de consumo adicional al problema, el centro de consumo artificial, ${displaystyle M_{a}}$, de forma que su demanda sea el excedente ( ${displaystyle M_{a}=sum F-sum M}$) y el coste de envío a este mercado sea nulo:

En caso de que ${displaystyle sum F<sum M}$ (Demanda total mayor a la oferta total) se incorporaría una factoría adicional al problema, la factoría artificial, ${displaystyle M_{b}}$, de forma que su oferta sea el excedente (${displaystyle M_{b}=sum M-sum F}$ ) y el coste de envío de esta factoría sea nulo:

Se muestra la presentación gráfica del problema de transporte donde:

La estructura del problema de transporte permite una representación compacta del problema utilizando el formato de tabla de transporte como se muestra a continuación.^[3]​

Cabe mencionar que los costes deben ser colocados en la esquina superior derecha.

Entre cada representación existe una equivalencia que se menciona a continuación:

El problema de transporte puede ser resuelto de las siguientes formas:

Para que un problema de transporte pueda ser resuelto a través de la técnica de transporte debe cumplir con las características:

Para aplicar la técnica de transporte se utiliza la tabla de transporte equilibrada. Los pasos son los mismo del método simplex, los cuales contemplan:

Existen varios métodos para hacer esto: Noreste y sus variaciones(Suroeste, Suroeste, etc), y Costo mínimo o el método de Vogel:^[3]​ Con cualquiera de estos métodos se debe obtener una solución que contemple ${displaystyle n+m-1}$ variables básicas.

Para encontrar la variable de entrada se utilizará los criterios ya establecidos del método simplex para un caso minimizado. Y se encontrará la variable utilizando el método de multiplicadores o método de u-v. Dicho método utiliza el modelo dual del modelo de programación lineal. El método calcula los valores de las variables duales ${displaystyle u_{i}}$ y ${displaystyle v_{j}}$ (cada renglón tendrá un ${displaystyle u_{i}}$ y cada columna tendrá un ${displaystyle v_{j}}$). Estos multiplicadores se obtienen de las ecuaciones: ${displaystyle u_{i}+v_{j}=c_{i,j}}$ para cada variable básica ${displaystyle x_{i,j}}$

En total se tendrán n+m-1 ecuaciones y m+n multiplicadores. Es necesario utilizar un valor arbitrario para uno de ellos y de ahí encontrar los demás valores de los multiplicadores.

Para encontrar el ${displaystyle z_{j}-c_{j}}$ de las variables no básicas se utiliza la relación:

Suponga que ${displaystyle x_{s,r}}$ es la variable no básica, entonces se calcula con ${displaystyle u_{s}+v_{r}-c_{s,r}}$.

Si al calcular estos valores alguno es positivo, se elige al valor más grande del ${displaystyle z_{j}-c_{j}}$ como la variable de entrada. En el caso de que todos sean ${displaystyle z_{j}-c_{j}<0}$, entonces la solución actual es la óptima.

Para identificar la variable de salida será necesario construir un circuito. Los circuitos se construyen a partir de la solución básica factible. Un circuito debe contener únicamente variables básicas con excepción de la variable de entrada. Suponga un ejemplo con la siguiente tabla con 3 factorías y 4 mercados, en este caso se tendrán 6 variables básicas (3+4-1) y una posible solución inicial podría ser (se pone B para indicar que es variable básica):

Suponga que la variable entrada es la casilla (3,1), esta variable deberá tomar un valor de ${displaystyle + u }$, esto ocasiona un reajuste de las demás casillas básicas, el análisis se realiza por columna y por renglón, por tanto el reajuste será:

Para determinar el valor de la variable de entrada ${displaystyle x_{i,j}}$ y establecer la variable de salida:

${displaystyle x_{i,j}=minleft{X_{p,q}/X_{p,q}- u X_{p,q}b{acute {a}}sica ight}}$

En este caso el valor de la variable de entrada ${displaystyle u }$ se encuentra en los valores de las casillas (1,1), (2,2) y (3,4) de estos se elige el valor más pequeño (esta casilla será la variable de salida). Una vez que se tenga el valor ${displaystyle u }$ se hace las sumas y las restas de las demás casillas del circuito. Se regresa al paso de la variable de entrada.