Método del transporte

Concepto

El método del transporte es una aplicación singular de la programación lineal cuyo objetivo es determinar el esquema de transporte que minimice el coste total de este, conocidos los costes unitarios desde el origen i hasta el destino j. Además, se sabe que el producto está disponible en una determinada cantidad b_i en cada uno de los m orígenes, y es necesario que sea llevado a cada uno de los n destinos posibles en una cantidad demandada d_j.

La formulación de un problema de transporte, siguiendo un modelo de programación lineal será:

Donde:

• — Z: función de costes totales que se desea minimizar.
• — c_ij: coste de transportar una unidad de producto desde el origen i (i=1, 2,..., m) hasta el destino j (j=1, 2,..., n).
• — x_ij: cantidad transportada de producto desde el origen i hasta el destino j.
• — b_i: cantidad disponible de producto en cada origen i.
• — d_j: cantidad demandada de producto en cada destino j.

Los problemas de transporte pueden ser resueltos mediante el Algoritmo del Simplex. Sin embargo, dadas las peculiaridades de este problema han aparecido otros algoritmos específicos que facilitan el proceso. Para su implementación se representa el problema en una tabla de doble entrada:

Como premisa de partida se supone que la demanda total de un producto es igual a su disponibilidad:

Obtención de una solución inicial factible

Pueden emplearse cuatro métodos: Método de la esquina noroeste, Método del mínimo de filas, Método del mínimo de columnas y el Método de Vogel.

Si la solución factible contiene (m+n-1) variables básicas, se denomina no degenerada, y si está formada por menos de (m+n-1) variables básicas será degenerada.

Método de la esquina noroeste

Se empieza por el elemento de la esquina superior izquierda (x₁₁) y se elige entre el menor valor de su disponibilidad (b₁) y su demanda (d₁), es decir, x₁₁=Min (b₁, d₁). Se repite este proceso hasta completar el valor de la fila (disponibilidad) o de la columna (demanda), hasta alcanzar una solución inicial factible.

Entre las ventajas de su implementación se encuentra la rapidez y facilidad de este método, siendo su principal inconveniente que no tiene en cuenta los costes derivados del transporte en la asignación de rutas.

Para una mejor comprensión nos vamos a apoyar en un pequeño ejemplo. Imaginemos que una pequeña empresa textil fabrica su producto en dos centros de trabajo (A, B), de manera que en el primero se elaboran 300 unidades y en el segundo 500 unidades. Dicho producto es vendido en tres mercados, cuyas demandas son 150, 250 y 400 unidades, respectivamente.

La matriz de costes unitarios de transporte facilitada por la empresa es la siguiente:

En primer lugar construimos la tabla de transporte del problema:

Comenzamos por determinar el valor de la casilla superior izquierda: x₁₁=Min(b₁, d₁)=Min(300,150)=150, es decir, se transportan 150 unidades del origen 1 hasta el mercado 1, quedando satisfecha la demanda de dicho mercado.

Seguimos el proceso, por lo que tenemos que establecer el valor de la nueva esquina noroeste, en este caso la casilla x₁₂=Min(b₁, d₂)=Min(300-150,250)=150, quedando agotada la disponibilidad del producto en el primer centro de trabajo.

A continuación proseguimos con el proceso asignando el valor de la siguiente esquina noroeste: x₂₂=Min(b₂, d₂)=Min(500, 250-150)=100, resultando completada la demanda del segundo destino.

Completamos el proceso de búsqueda de la solución inicial factible asignando el último valor x₂₃=Min(b₂, d₃)=Min (500-100, 400-0)=400.

Como el número de variables básicas es igual a (m+n-1)=(2+3-1)=4, se trata de una solución no degenerada.

Conocidos los costes unitarios de transporte, el coste total generado sería:

Método del mínimo de filas

Se elige la casilla de menor coste unitario de la primera fila, y se asigna el valor de esa casilla como el menor entre su disponibilidad y su demanda, hasta completar la fila o la columna correspondiente.

Para aplicarlo al ejemplo anterior, partimos de la siguiente tabla de transporte, en la que se incluyen los costes (€ por unidad):

Comenzamos por la primera fila, siendo la casilla de menor coste la correspondiente a x₁₁(c₁₁=10), por lo que x₁₁=Min(b₁, d₁)=Min(300,150)=150, quedando la columna saturada.

Al completarse la primera columna, el siguiente valor a asignar es el correspondiente a x₁₃ (c₁₃=12), de manera que x₁₃=Min(b₁, d₃)=Min (300-150, 400)=150, por lo que la disponibilidad del primer centro de trabajo estaría agotada.

A continuación pasamos a la fila 2, siendo el valor de menor coste el correspondiente a la casilla x₂₃ (c₂₃=9), de manera que x₂₃=Min(b₂2, ₃3)=Min(500, 400-150)=250, quedando satisfecha la demanda del tercer destino.

Por último determinamos el valor de la última casilla ₂₂2=Min(₂2, ₂2)=Min (500-250, 250)=250, siendo la solución inicial no degenerada la siguiente:

El coste total del transporte resultante de la aplicación del método del mínimo de filas sería:

Método del mínimo de columnas

Es similar al método anterior, pero como su propio nombre indica, el procedimiento comienza por la primera columna.

Aplicando este método a la empresa que hemos tomado como ejemplo (ver Tabla 8), comenzaríamos por la casilla ₂₁1(₂₁1=8), por lo que ₂₁1=Min(₂2, ₁1)=Min(500,150)=150, quedando satisfecha la demanda del primer mercado.

Seguiríamos por la segunda columna, siendo el valor de menor coste el correspondiente a ₂₂2(₂₂2=10), de manera que ₂₂2=Min(₂2, ₂2)=Min (500-150, 250)=250, resultando saturado el segundo mercado.

Pasamos a la tercera columna, donde el menor coste es el correspondiente a la segunda fila ₂₃3(₂₃3=9), de manera que ₂₃3=Min(₂2, ₃3)=Min (500-150-250, 400)=100, por lo que la disponibilidad del segundo centro de trabajo estaría agotada.

Por último, se calcula el valor de la casilla ₁₃3=Min(₁1, ₃3)=Min (300, 400-100)=300.

Los costes asociados a esta solución inicial factible no degenerada son:

Resultando un coste superior al generado por el Método del mínimo de filas.

Método de Vogel

Es el método que genera una solución inicial factible más próxima a la óptima. Para aplicar este procedimiento se siguen los siguientes pasos:

• a) Se calculan las diferencias en valor absoluto entre los dos menores costes unitarios, para cada fila y columna, eligiendo aquella de mayor valor.
• b) En la fila o columna seleccionada, se elije la variable con menor coste unitario, y se asigna su valor hasta satisfacer la demanda o agotar la disponibilidad, no teniéndose en cuenta, una vez que ha sido completada, esa fila o columna en las siguientes iteraciones.
• c) Se continúa con el proceso hasta alcanzar una solución inicial factible.

Aplicado a la empresa que hemos tomado como ejemplo, iniciamos el procedimiento obteniendo las diferencias de coste para cada fila y columna.

Comenzamos por la columna 2, ya que es la diferencia de mayor valor, asignado la variable ₂₂2, por ser la de menor coste unitario. De manera que ₂₂2=Min(₂2, ₂2)=Min(500, 250)=250, quedando saturada la demanda del segundo mercado.

A continuación se calculan de nuevo las diferencias para cada fila y columna:

Como la mayor diferencia se encuentra en la columna 3, se determina el valor de la variable ₂₃3 por ser la de menor coste unitario: ₂₃3=Min(₂2, ₃3)=Min(500-250, 400)=250, quedando completada la disponibilidad del segundo centro de trabajo.

Por último, se alcanza la solución inicial factible (no degenerada) con las casillas ₁₁1 y ₁₃3, de manera que ₁₁1=Min(₁1, ₁1)=Min(300, 150)=150 y ₁₃3=Min(₁1, ₃3)=Min(300-150, 400-250)=150.

El coste total asociado a esta solución sería:

Prueba de optimalidad

Una vez que se ha alcanzado una solución inicial, se debe comprobar que es la óptima, es decir, si cumpliendo los condicionantes establecidos de disponibilidad de cada origen i y de demanda de cada destino j, la solución actual es la que genera el menor coste total de transporte. Para ello, se aplica el denominado Algoritmo Stepping-Stone o Algoritmo del escalón, cuyos principios se fundamentan en el Algoritmo de Simplex o Algoritmo de Dantzingg.

Como se trata de un problema que sigue el principio de ahorro, es decir, la minimización de los costes, se alcanzará la solución óptima cuando el rendimiento marginal de las variables no básicas (las que no forman parte de la ruta de transporte) sea no negativo. Por lo tanto, si algunas de estas variables no básicas tuviera un rendimiento marginal negativo, se incluiría dentro de la solución, ya que este hecho permitiría reducir el coste de la distribución de productos.

Para realizar la prueba de optimalidad siguiendo el Algoritmo Stepping-Stone, se parte de la solución inicial factible alcanzada por alguno de los métodos desarrollados con anterioridad. En nuestro caso, seguiremos con la empresa que hemos tomado como ejemplo, tomando como solución inicial factible la que se ha logrado con la aplicación del Método de la esquina noroeste, tal y como muestra la siguiente tabla de costes y cantidades transportadas.

Los costes asociados a esta solución son:

Para aplicar el Algoritmo Stepping-Stone se siguen las siguientes etapas:

• a) Determinación de la nueva variable básica: se calcula el rendimiento marginal de las variables que no forman parte de la solución básica, en nuestro caso, ₁₃3 y ₂₁1. Para ello, se determina la variación que se produce en la función objetivo ante un incremento unitario de estas variables.

  Aplicado al ejemplo, si la variable ₁₃3 toma el valor 1, se estaría transportando una unidad del centro de trabajo A al destino 3, sobrepasando la disponibilidad existente de dicho centro (₁1=150+150+1=301). Para evitar esta situación, se reduce en una unidad la cantidad transportada del centro de trabajo A al destino 2 (incluido en la ruta básica), no quedando satisfecha la demanda del mismo, por lo que se lleva una unidad desde el otro origen, es decir, desde el centro de trabajo B. Como consecuencia de este hecho, y como medida para no sobrepasar su disponibilidad, se detrae en una unidad la cantidad que se transporta de este centro al destino 3, estableciéndose el siguiente circuito:

• El transporte de una unidad del origen A al destino 3 supone un coste de 12 €. Para cumplir las restricciones del problema, se reduce en una unidad de transporte del origen A al destino 2, minorando el coste en 15 €. Se añade una unidad del origen B al destino 2, que supone un aumento del coste en 10 €, y se detrae una unidad de este origen al destino 3, que implica una reducción de 9 €. Por lo tanto el rendimiento marginal de la variable ₁₃3 sería: ₁₃3=12-15+10-9=-2 €, siendo recomendable modificar la solución inicial.
• b) Cálculo del nivel de utilización: a raíz de la información anterior, nos interesa transportar el mayor número de unidades del origen A al destino 3, de manera que se cumpla:

Por lo que la nueva ruta de transporte sería:

Esta ruta proporciona los siguientes costes:

A continuación aplicamos a esta nueva solución básica no degenerada la prueba de optimalidad, calculando los rendimientos marginales de las variables no básicas ₁₂2 y ₂₁1.

Para calcular el rendimiento marginal de ₁₂2, se incrementa en una unidad el valor de esta variable, se sigue el siguiente circuito:

De esta forma ₁₂2=15-10+9-12=2 €, por lo que esta opción no minoraría el valor de la función objetivo.

El rendimiento marginal de la variable no básica ₂₁1 se hallaría a través del siguiente circuito:

Por lo tanto, ₂₁1=8-9+12-10=1 €, por lo que al resultar positivo tampoco se conseguiría reducir el coste.

A la vista de los resultados obtenidos, dado que los rendimientos marginales de las variables que no forman parte de la ruta básica son no negativos (₁₂2 y ₂₁1), estamos ante la solución óptima del problema (ver Tabla 23), siendo el mínimo coste total que garantiza el suministro de 8.050 €.