Escalón
El problema resuelto por el algoritmo Stepping Stone es el siguiente:
Tomemos un ejemplo para mostrar cómo funciona el algoritmo. Considere cuatro orígenes y cinco solicitantes con costos y cantidad de acuerdo con la tabla:
vsij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | 7 | 12 | 1 | 5 | 6 | 12 |
O2 | 15 | 3 | 12 | 6 | 14 | 11 |
O3 | 8 | 16 | 10 | 12 | 7 | 14 |
O4 | 18 | 8 | 17 | 11 | 16 | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
Es posible realizar el algoritmo usando dos tablas (una para los costos, otra para los flujos). También es posible mostrar los dos valores en el mismo cuadro, ya que solo variará el flujo.
Trampolín - Paso 1: obtención de una solución base
Por la esquina noroeste
El principio es simple:
2. Ajustar los valores de oferta y demanda en la asignación de las respectivas filas y columnas.
3. Si se agota el suministro de la primera fila, baje a la primera celda de la siguiente fila.
4. Si se satisface la demanda de la primera celda, muévase horizontalmente a la siguiente celda.
5. Si para una celda la oferta es igual a la demanda, la siguiente asignación se puede realizar en la celda de la siguiente fila o columna.
6. Continúe con el procedimiento hasta que la cantidad total disponible se asigne por completo a las celdas, según sea necesario.
Fij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | 10 | 2 | – | – | – | 12 |
O2 | – | 9 | 2 | – | – | 11 |
O3 | – | – | 13 | 1 | – | 14 |
O4 | – | – | – | 4 | 4 | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
El costo total de la solución básica es: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395.
En muchos casos no es posible satisfacer la demanda, este método, aunque rápido, solo brinda una solución factible poco realista. Aquí no representamos los costos sino los flujos fij de la oferta I a la solicitud j.
Por el método mínimo
2. Si el costo mínimo no es único, puede elegir cualquier celda.
3. Elija el valor de x tanto como sea posibleij correspondiente, dependiendo de las limitaciones de capacidad y requisitos.
4. Repita los pasos 1 a 3 hasta que se cumplan todas las restricciones.
Por el método Vogel (o Balas-Hammer)
Este método utiliza la diferencia de transporte entre las dos mejores opciones para la oferta y la demanda. La solución básica suele estar muy cerca de la solución óptima.
1. Determine un costo de penalización para cada fila (columna) restando el costo de celda unitario más bajo en la fila (columna) del costo de celda unitario más bajo en la misma fila (columna).
3.
- Si queda exactamente una fila o columna con oferta o demanda cero, deténgase.
- Si queda una fila (columna) con una oferta (demanda) positiva, determine las variables básicas en la fila (columna) utilizando el método de mínimos. Parada.
- Si todas las filas y columnas que no han sido tachadas tienen una oferta o demanda (restante) de cero, use el método mínimo. Parada.
En todos los demás casos, vaya al paso 1.
La primera iteración del método da: DO1 = 4, DO2 = 3, DO3 = 1, DO4 = 3, DD1 = 1, DD2 = 5, DD3 = 9, DD4 = 1, DD5 = 2. Columna D3 tiene la diferencia de costo más grande, el costo más pequeño es 1, por lo que saturamos la intersección O1 con3 con el flujo mínimo (12, 15). La oferta de O1 por lo tanto, está saturado.
Fij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | X | X | 12 | X | X | 12 |
O2 | – | – | – | – | – | 11 |
O3 | – | – | – | – | – | 14 |
O4 | – | – | – | – | – | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
Para el nuevo cálculo de la diferencia de costo, ya no tendremos en cuenta los valores de la fila O1. Obtenemos después de 5 iteraciones a la siguiente configuración:
Fij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | – | – | 12 | – | – | 12 |
O2 | – | 11 | – | – | – | 11 |
O3 | 10 | – | – | – | 4 | 14 |
O4 | – | – | 3 | 5 | – | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
Trampolín - Paso 2: calcular los potenciales
Una vez que tenga una solución básica, la idea es modificar la solución para mejorarla. Es decir, es necesario modificar los flujos. Para esto, elegiremos un flujo que reduzca al máximo el costo total de transporte. El primer paso para determinar este flujo es calcular los potenciales. Los potenciales se calculan ÚNICAMENTE en las celdas con un flujo distinto de cero.
Luego podemos calcular otros potenciales. Los potenciales se calculan paso a paso. En nuestro caso, hemos calculado el potencial de la fila 1 a partir de c12, por lo tanto, es posible calcular el potencial de la columna 1 o la columna 2.
Tomemos el ejemplo nuevamente: para la columna 1, pD1 = c11 + PO1 = 7. Para la fila 2, pD2 = c12 + PO1 = 12. Lo mismo para las otras filas y columnas: pO2 = pD2 - vs22 = 12 -3 = 9; pagD3 = 21; pag03 = 11; PAGD4 = 23: PO4 = 12; PAGD5 = 28.
Trampolín - Paso 3: cálculo de la variación del costo unitario
Obtenemos la siguiente tabla:
vij | D1 | D2 | D3 | D4 | D5 | pagO |
O1 | – | – | -20 | -18 | -19 | 0 |
O2 | 17 | – | – | -8 | -5 | 9 |
O3 | 12 | 15 | – | – | -10 | 11 |
O4 | 23 | 8 | 8 | – | – | 12 |
pagD | 7 | 12 | 21 | 23 | 28 |
Trampolín - Paso 4: cálculo de la cantidad máxima de flujo
Por ejemplo para la casilla 01-D3, tomamos el siguiente circuito f13 -> f12 -> f22 -> f23 -> f13 con el caudal mínimo de 2. Obtenemos la siguiente tabla:
Fij | D1 | D2 | D3 | D4 | D5 | pagO |
O1 | – | – | 2 | 1 | 1 | 0 |
O2 | – | – | – | 1 | 1 | 9 |
O3 | – | – | – | – | 1 | 11 |
O4 | – | – | – | – | – | 12 |
pagD | 7 | 12 | 21 | 23 | 28 |
Multiplicando fij* vij, conocemos la variación del costo total por la modificación por el flujo fij. Elegimos la caja con la mayor fij* vij, aqui la caja O1-D3
Stepping Stone - Paso 5: actualice la tabla
El cálculo de la actualización del flujo se realiza mediante la regla “+ -” sin contar el retorno a la caja original. Entonces en el circuito: f13 + = 2, f12 - = 2, f22 + = 2 y f23 - = 2. La tabla es la siguiente:
Fij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | 10 | 2-2 = – | 0+2 = 2 | – | – | 12 |
O2 | – | 9+2 = 11 | 2-2 = – | – | – | 11 |
O3 | – | – | 13 | 1 | – | 14 |
O4 | – | – | – | 4 | 4 | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
El costo total de la solución básica es: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395. El costo de esta solución es: 10 * 7 + 11 * 3 + 2 * 1 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 355. Sea la solución básica menos f13* v13 = 2*20 = 40.
En nuestro ejemplo, finalmente tenemos la siguiente tabla:
Fij | D1 | D2 | D3 | D4 | D5 | oferta |
O1 | – | – | 12 | – | – | 12 |
O2 | – | 11 | – | – | – | 11 |
O3 | 10 | – | – | – | 4 | 14 |
O4 | – | – | 3 | 5 | – | 8 |
demanda | 10 | 11 | 15 | 5 | 4 |
Con un costo total de: 10 * 8 + 11 * 3 + 12 * 1 + 3 * 17 + 5 * 11 + 4 * 7 = 259.
Aparte
Hablamos de flujo porque el problema se resuelve como un problema de flujo de costo mínimo (flujo maximo al mínimo costo) en un grafico bipartito completo: un conjunto de fuentes conectadas a un conjunto de sumideros (de ahí la regla "+ -", ya que vamos una vez en la dirección del flujo y luego en la dirección opuesta en el circuito elegido).
ES 
FR 
EN