Trampolín: sistemas complejos e inteligencia artificial

Contenido

Escalón

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

Bien de diferentes orígenes, ofreciendo una determinada oferta cuantificable; y destinos que requieren una cierta cantidad; se asigna un costo de transporte para cada combinación origen-destino; ¿Cuál es la mejor manera de satisfacer 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:

vs_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	7	12	1	5	6	12
O₂	15	3	12	6	14	11
O₃	8	16	10	12	7	14
O₄	18	8	17	11	16	8
demanda	10	11	15	5	4

La idea de trampolín es partir de un solución básica factible (no óptimo) para mejorarlo 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, si no es así hay que añadir una demanda ficticia de coste 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 ambos valores en el mismo recuadro ya que solo variará el caudal.

Trampolín – Paso 1: obtención de una solución básica

Por la esquina noroeste

El principio es simple:

1. Seleccione la celda de la esquina noroeste y asigne tantas unidades como sea posible (necesidades mínimas) disponibles para la oferta y la demanda.
2. Ajuste los valores de oferta y demanda en la asignación respectiva de fila y columna
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, ya sea en 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.

F_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	10	2	–	–	–	12
O₂	–	9	2	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	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 f_ij 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 c_ij.
2. Si el costo mínimo no es único, puede elegir libremente cualquier celda.
3. Elija el valor de x tanto como sea posible_ij correspondiente, dependiendo de las limitaciones de capacidad y requerimiento.
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).

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.

Si queda exactamente una fila o columna con cero oferta o demanda, 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: D_O1 = 4, D_O2 = 3, D_O3 = 1, D_O4 = 3, D_D1 = 1, D_D2 = 5, D_D3 = 9, D_D4 = 1, D_D5 = 2. Columna D₃ tiene la diferencia de costo más grande, el costo más pequeño es 1, entonces saturamos la intersección O₁ con₃ con la corriente min(12, 15). La oferta O₁ por lo tanto, está saturado.

F_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	X	X	12	X	X	12
O₂	–	–	–	–	–	11
O₃	–	–	–	–	–	14
O₄	–	–	–	–	–	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 O₁. Obtenemos después de 5 iteraciones a la siguiente configuración:

F_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	3	5	–	8
demanda	10	11	15	5	4

Trampolín – Paso 2: cálculo de potenciales

Una vez que tenga una solución básica, la idea es modificar la solución para mejorarla. Es decir, las ondas deben ser modificadas. Para ello, elegiremos un flujo que reduzca al máximo el coste total del transporte. El primer paso para determinar este flujo es calcular los potenciales. ¡Los potenciales se calculan SOLAMENTE en los cuadrados 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: p_O1 = 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 c₁₂, por lo tanto, es posible calcular el potencial de la columna 1 o la columna 2.

Para calcular los potenciales aplicamos la siguiente regla: p_D + p_O = c_ijlo que da N ecuaciones con N incógnitas.

Tomemos el ejemplo de nuevo: para la columna 1, p_D1 = c₁₁ + P_O1 = 7. Para la fila 2, p_D2 = c₁₂ + P_O1 = 12. Lo mismo para las otras filas y columnas: p_O2 = p_D2 - contra₂₂ = 12 -3 = 9; pag_D3 = 21; pag₀₃ = 11; PAG_D4 = 23: P_O4 = 12; PAG_D5 = 28.

Trampolín – Paso 3: cálculo de la variación del costo unitario

Para cada celda con flujo cero, calculamos v_ij sumando el potencial del origen asociado al costo unitario de la caja y restando el potencial del destino correspondiente: v_ij = c_ij -pag_Oi -pag_DJ.

Obtenemos la siguiente tabla:

v_ij	D₁	D₂	D₃	D₄	D₅	pag_O
O₁	–	–	-20	-18	-19	0
O₂	17	–	–	-8	-5	9
O₃	12	15	–	–	-10	11
O₄	23	8	8	–	–	12
pag_D	7	12	21	23	28

Trampolín – Paso 4: calcular 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 v_ij 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 0₁-D₃, tomamos el siguiente circuito f₁₃ -> f₁₂ -> f₂₂ -> f₂₃ -> f₁₃ con el caudal mínimo de 2. Obtenemos la siguiente tabla:

F_ij	D₁	D₂	D₃	D₄	D₅	pag_O
O₁	–	–	2	1	1	0
O₂	–	–	–	1	1	9
O₃	–	–	–	–	1	11
O₄	–	–	–	–	–	12
pag_D	7	12	21	23	28

Multiplicando f_ij* v_ij, conocemos la variación del costo total por la modificación por el flujo f_ij. Elegimos la caja con la mayor f_ij* v_ij, aqui la caja O₁-D₃

Trampolín – Paso 5: Tabla actualizada

El cálculo de actualización de flujo se realiza mediante la regla “+ –” sin contar el retorno a la caja original. Así en el circuito: f₁₃ + = 2, f₁₂ - = 2, f₂₂ + = 2 y f₂₃ - = 2. La tabla es la siguiente:

F_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	10	2-2 = –	0+2 = 2	–	–	12
O₂	–	9+2 = 11	2-2 = –	–	–	11
O₃	–	–	13	1	–	14
O₄	–	–	–	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 f₁₃* v₁₃ = 2*20 = 40.

Repetimos los pasos 2 a 5 hasta que no queden más v_ij negativo. Entonces sabemos que no hay ningún circuito para reducir el costo total, por lo que tenemos una solución óptima.

En nuestro ejemplo, finalmente tenemos la siguiente tabla:

F_ij	D₁	D₂	D₃	D₄	D₅	oferta
O₁	–	–	12	–	–	12
O₂	–	11	–	–	–	11
O₃	10	–	–	–	4	14
O₄	–	–	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).