Escalón

Escalón

El problema resuelto por el algoritmo Stepping Stone es el siguiente:

Son de diferentes orígenes, proponiendo una determinada oferta cuantificable; y destinos que requieran una determinada cantidad; se asigna un costo de transporte para cada combinación de origen y destino; ¿Cómo satisfacer mejor la demanda al menor costo?

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
 La idea de trampolín es partir de una solución básica factible (no óptima) para mejorarla iterativamente hasta obtener una solución no optimizable. No hay mejor solución, por lo que es óptima. Es importante comprobar que la oferta y la demanda son iguales, de no ser así es necesario agregar una demanda ficticia de costo significativo para cada oferta.

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:

1. Seleccione la celda de la esquina noroeste y asigne tantas unidades como sea posible (requisitos mínimos) disponibles para la oferta y la demanda.
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

1. Identifique la caja con el costo unitario mínimo de transporte cij.
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.
transporte3
 

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).

2. Identifique la fila o columna con el mayor costo de penalización. Romper los empates arbitrariamente (si los hay). Asigne tanto como sea posible a la variable con el costo unitario más bajo en la fila o columna seleccionada. Ajuste la oferta y la demanda y tache la fila o columna que ya está satisfecha. Si una fila y una columna se satisfacen simultáneamente, tache solo una de las dos y asigne una oferta o demanda de cero a la restante.
 

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.

Establezcamos un potencial de 0 en la línea con la celda con el flujo de mayor costo. Aquí tomaremos la solución básica proporcionada por el método de la esquina noroeste: pO1 = 0.

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.

 Para calcular los potenciales aplicamos la siguiente regla: pD + pO = cij lo que da N ecuaciones con N incógnitas.

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

Para cada celda con flujo cero, calculamos vij sumando el potencial del origen asociado al costo unitario de la caja y restando el potencial del destino correspondiente: vij = cij - pagOi - pagDJ.

Obtenemos la siguiente tabla:

vij
D1
D2
D3
D4
D5
pagO
O1
-20
-18
-19
0
O2
17
-8
-5
9
O3
1215
-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

Ahora conocemos la variación en el costo de una unidad según el origen y el destino en comparación con la solución inicial. Ahora debemos determinar los circuitos de flujo que permitan reducir el costo total. Este cálculo se realiza solo para el vij negativo.
 Para llenar una celda vacía, debe vaciar una celda llena. Al buscar un circuito (un "bucle"), debemos asegurarnos de que una celda con un flujo siempre sucede a la última celda elegida en el circuito. Así, el circuito se compone de una caja vacía y cajas llenas. El flujo máximo que se puede mover para llenar la celda vacía es el mínimo de los flujos de las celdas distintas de cero.

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
44
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.

Repetimos los pasos 2 a 5 hasta que no haya más vij negativo. Sabemos entonces que no existe un circuito para reducir el costo total, por lo que tenemos una solución óptima.

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 máximo a costo mínimo) en un gráfico bipartito completo: un conjunto de fuentes vinculadas a un conjunto de sumideros (de ahí la regla "+ -" desde que vamos una vez en la dirección del flujo y luego en la dirección opuesta en el circuito elegido).

Escalón

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: