Método del Cruce del arroyo

El método del Cruce del Arroyo, Trampolín, o de Salto de Piedra en Piedra (Stepping Stone) es un método de resolución de problemas de transporte en programación lineal que consiste en calcular cuál sería la variación del costo del envío a través de las ruta posibles, es decir asignar cierta cantidad de artículos desde varios orígenes (fábricas/fuentes) a un conjunto de destinos (clientes/depósitos) de tal manera que se disminuyan los costos, hasta optimizar el objetivo. Se parte de una solución factible de Costo Mínimo, Vogel, o Esquina Noroeste.

El Método del Cruce del Arroyo, se basa en una solución inicial y mediante un proceso repetitivo sobre las celdas vacías (en el que se salta) buscando llegar a una solución óptima más conveniente que la hallada por los métodos mencionados. Si la solución de partida no es relativamente favorable en costos, el método requerirá una mayor cantidad de repeticiones para llegar a la solución óptima.

PASOS DEL MÉTODO DE CRUCE DEL ARROYO:

1. Partir de una solución con cualquiera de los métodos ya mencionados (Costo Mínimo, Vogel, o Esquina Noroeste).
2. Definir las celdas que son de agua y las que son de piedras, las celdas de agua son aquellas a los que no le hemos asignado un valor, mientras que las de piedra son aquellas a las que le hemos asignado un valor de transporte.
3. Calcular los costos relativos de las celdas de agua, mediante el salto de piedra en piedra en dirección vertical y/o horizontal (no en diagonal) realizando un procedimiento de sumas y resta de los costos de los nodos de salto.
4. De los costos relativos obtenidos de las celdas de agua se debe seleccionar el más negativo. En caso de ser todos positivos ya estamos ante una solución óptima.
5. Asignamos los nuevos valores al conjunto de celdas de saltos seleccionadas para la celda de agua más negativa.
6. Recalculamos los costos relativos para las celdas de agua en función de la nueva matriz, nuevamente si se presenta algún valor negativo se debe realizar el cálculo de costos relativos de las celdas de agua y repetir el proceso hasta lograr que todos sean positivos, una vez logrado esto no hay posibilidades de mejorar el resultado de la función objetivo.

DESARROLLO DE UN EJERCICIO (CASO PRÁCTICO):

Para explicar el método vamos a partir de un ejercicio de transporte de tres fabricas y cuatro depósitos en el que se cuenta con una determinada producción y demanda de distribución resuelta por el método de costo mínimo:

El primer paso es identificar a las celdas de agua (vacías) y las celdas de piedra (llenas), desde las celdas de agua que están vacías y serán positivas, deberemos partir, saltando y pisando siempre en celdas de piedra siguiendo una secuencia de paridad para completar + y - (negativo y positivo) siempre en forma vertical u horizontal como veremos a lo largo del ejemplo.

Identificación de celdas de agua:

Realizamos el método para la primer celda de agua correspondiente a la Fabrica A, Departamento 3:

Realizamos el método en la celda Fabrica B, Departamento 2:

Realizamos el método en la celda Fabrica B, Departamento 4:

Realizamos el método en la celda Fabrica C, Departamento 1:

Realizamos el método en la celda Fabrica C, Departamento 2:

Realizamos el método en la celda Fabrica C, Departamento 3:

Como podemos apreciar existe un solo camino o ruta negativa, así que lo seleccionamos, en caso de que existieran varios se parte de la selección del más negativo.
Por lo tanto, volvemos a la ruta del camino seleccionado:

De las celdas negativas de la ruta que son Fabrica B Deposito 1 y Fabrica A Deposito 2 tomamos la menor en cantidad que es Fabrica B Deposito 1 y realizamos el traslado de Fabrica B Deposito 1 cuyo valor es 27 a Fabrica B Deposito 2 por lo tanto:

Entonces para cumplir con los 35 de la columna Deposito 2 en Fabrica A Deposito 2 modifico el valor y en Fabrica A Deposito 1 también para cumplir con los 30 del Deposito 1 por lo tanto:

Una vez ajustados los valores, volvemos a definir las celdas en función de la nueva estructura, y nos quedan las siguientes celdas de piedra y de agua:

Una vez definidas las celdas de agua y de piedra repetimos nuevamente el método para ubicar una ruta o camino negativo o confirmar que estamos ante una solución óptima:

El método del cruce del arroyo, nos confirma que la solución es óptima puesto que todos los valores son positivos; 2, 1, 6, 9, 4 y 13 y hemos mejorado de $558 a $531.-

MATERIAL MULTIMEDIA:

Tutoriales en vídeo de la aplicación del método de cruce del arroyo: