Método Stepping Stone
El método stepping-stone llega a la solución óptima partiendo de una solución inicial e investigando si puede obtenerse alguna solución mejor. Como el método parte de una solución inicial, debemos encontrar una solución factible cualquiera para poder utilizar el método.
Existen diversos métodos que pueden utilizarse para obtener una solución inicial factible; todos ellos, sin embargo, se basan en la máxima cantidad que podrá asignarse a una celda cualquiera de la matriz de transportes.
Hecha la asignación, se elimina la fila (o columna) de la matriz en la que se alcanzó la oferta (demanda) y se procede a elegir otra celda para asignar, hasta que no haya más sobrantes de oferta y demanda.
Sin embargo, los métodos se diferencian en la elección de la celda. Hay tres métodos que normalmente se presentan en la literatura:
-
Método de la esquina noroeste
en este método, la celda elegida para la asignación es la que está lo más al noroeste posible y que aún dispone de oferta y demanda
-
Método del costo mínimo
en este método, la celda elegida es la de menor costo unitario de transporte y que aún dispone de oferta y demanda
-
Método de Vogel o de las penalidades
consiste en asignar la máxima cantidad de transporte a la celda cuya penalidad por no elegirla es máxima. Esta penalidad se asocia a cada fila y columna, y se estima mediante la diferencia entre los dos menores costos de cada fila y columna. La fila o columna con la mayor penalidad se usará para determinar la celda en la que se hará la asignación.
El programa DDM implementa el Método de la esquina noroeste.
Optimización
El algoritmo de optimización será:
-
Equilibrar ofertas y demandas
Si la sumatoria de las ofertas es mayor que la de las demandas, cree una demanda ficticia con la diferencia en valor absoluto; y si la sumatoria de las demandas es mayor que la de las ofertas, cree una oferta ficticia con la diferencia en valor absoluto.
-
Crear una solución inicial
Puede usarse el Método de la esquina noroeste:
-
Comenzar por la variable X11
-
Si aún hay oferta disponible, pasar a la variable Xi+1, j
-
Si solo hay demanda disponible, pasar a la variable Xi, j+1
-
Continuar hasta obtener todas las variables básicas (las que tienen un círculo); todas las otras variables (no básicas) serán cero.
-
Prueba de optimalidad
-
Asumiendo una solución básica:
-
Una Solución Básica Factible es óptima si y solo si:
Cij – Ui – Vj ≥ 0
para todo (i, j) en que Xij es variable no básica
Si la solución es óptima, detenga la ejecución; si no, continúe con el siguiente paso
-
Elegir la VB de entrada (VBE)
-
Como Cij – Ui – Vj representa la tasa a la que la función objetivo evolucionará a medida que la variable no básica Xij aumenta, la VBE deberá tener un coeficiente Cij – Ui – Vj negativo para disminuir el costo total.
-
La VBE será la que tenga el coeficiente Cij – Ui – Vj más negativo, es decir, X13
-
Elegir la VB de salida
-
Aumentar la VBE provocará una reacción en cadena, en la cadena que definimos.
-
Así, pasaremos a tener celdas receptoras y celdas proveedoras, representadas en el Cuadro de Transportes por los signos + y –
-
En este caso utilizaremos la cadena marcada en rojo
-
El valor que se transferirá de las celdas proveedoras a las receptoras está dado por el mínimo (x11 = 70, x23 = 75), es decir, 70
-
VBE = x11
-
Identificar la nueva solución básica factible
-
Volver al paso 1
-
Después de la ejecución del algoritmo, todas las variables estarán calculadas y la lista de variables básicas VB contendrá los valores de las cantidades que se transportarán