Algoritmo Stepping Stone

Vista previa del material en texto

Prueba de optimalidad con 
algoritmo STEPPING-STONE en 
Métodos de Transporte 
Autor : Ing. Germán D. Mendoza R. 
PROBLEMAS DE 
TRANSPORTE 
Algoritmos de 
solución 
básica Inicial: 
• Método de la esquina 
Noroeste 
• Método del mínimo costo 
• Médoto de Vogel 
Prueba de 
Optimalidad 
• Salto de la piedra (Stepping-Stone) 
• Multiplicadores FASE 2: 
FASE 
1: 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : ALGORITMO STEPPING-STONE PASO A PASO. 
Para explicar sencillamente el algoritmo STEPPING-STONE tomaremos la siguiente 
tabla la cual es el resultado o tabla final de un problema resuelto por algún algoritmo 
básico inicial en la fase 1 como el de Esquina Noroeste, Costo mínimo o el de Vogel: 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 2 2 0 
4 
 3 1 
C2 
1 1 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
ACLARACIONES PREVIAS : 
Las casillas que contengan unidades asignadas son las variables básicas y las que no (vacias(0)) son las NO básicas. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 2 2 0 
4 
 3 1 
C2 
1 1 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
Ejemplo de 
Variable NO 
Básica 
Ejemplo de 
Variable 
Básica 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 1 
•Seleccionar una (1) variable no básica (preferiblemente en orden para evitar confusiones) 
y tres (3) o más básicas para formar un circuito cerrado con esquinas a 90 grados. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 2 2 0 
4 
 3 1 
C2 
1 1 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 2 
Hacer movimiento en línea recta (como de la torre en el ajedrez) hasta enlazar 
la variables seleccionadas formando un circuito cerrado. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 2 2 0 
4 
 3 1 
C2 
1 1 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 3 
•Asignar signos positivo y negativo de manera alternada a las variables del 
circuito iniciando con positivo (+) en la variable NO básica. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 4 
Obtener el costo relativo del circuito, el cual se halla tomando las cantidades asignadas 
 y multiplicándolas por el costo asociado y sumando o restando las otras casillas del circuito 
 según los signos asignados en el anterior paso. 
 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
Coordenada de la 
variable no básica 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 5 
Continuamos con otra variable NO básica: para este caso, el circuito no se puede hacer con sólo 3 
varibales básicas, así que debemos buscar la forma de hacerlo con más, utilizando para doblar a 90º 
una básica (movimiento como la torre en el ajedrez). 
CR-C1Ficticia = (0x0) – (2x0) + (1x2) – (3x3) + (2x1) – (1x2)= -7 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 2 + 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 + 2 - 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 6 
Siguiente variable NO básica (resumimos varios pasos en una sola diapositiva para no volver tan 
extensa la presentación) 
CR-C2F1 = (0x1) – (3x2) + (1x2) – (2x1) = -6 
 F1 F2 F3 Ficticia Oferta 
C1 
- 2 + 2 2 0 
4 
 3 1 
C2 
+ 1 - 1 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
 F1 F2 F3 Ficticia Oferta 
C1 
2 2 2 0 
4 
 3 1 
C2 
1 1 - 3 + 0 
5 
 2 3 
C3 
2 2 + 2 - 0 
3 
 1 2 
Demanda 3 3 4 2 
7 
Siguiente variable NO básica: 
CR-C2Ficticia = (0x0) – (2x0) + (1x2) – (3x3) = -7 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 8 
Siguiente variable NO básica 
CR-C3F1 = (0x0) – (3x2) + (1x2) – (2x1)+(3x3)-(1x2) = 1 
 F1 F2 F3 Ficticia Oferta 
C1 
- 2 + 2 2 0 
4 
 3 1 
C2 
1 - 1 + 3 0 
5 
 2 3 
C3 
+ 2 2 - 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 9 
Siguiente variable NO básica 
CR-C3F2 = (0x2) – (2x1) + (3x3) – (1x2) = 5 
 F1 F2 F3 Ficticia Oferta 
C1 
2 2 2 0 
4 
 3 1 
C2 
1 - 1 + 3 0 
5 
 2 3 
C3 
2 + 2 - 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 10 
Analizar lo siguiente: Si todos los costos relativos son positivos el algoritmo termina y 
quiere decir que es la distribución óptima y no se conseguirá otro resultado mejor. 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
CR-C1Ficticia = (0x0) – (2x0) + (1x2) – (3x3) + (2x1) – (1x2)= -7 
CR-C2F1 = (0x1) – (3x2) + (1x2) – (2x1) = -6 
CR-C2Ficticia = (0x0) – (2x0) + (1x2) – (3x3) = -7 
CR-C3F1 = (0x0) – (3x2) + (1x2) – (2x1)+(3x3)-(1x2) = 1 
CR-C3F2 = (0x2) – (2x1) + (3x3) – (1x2) = 5 
•Si al menos uno de los costos es negativo (como es el caso de este ejemplo donde hay 4 
Valores negativos) se tiene que continuar con los siguientes pasos: 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 11 
•Tomar el costo relativo más negativo y del circuito correspondiente tomar la variable no básica como la variable 
entrante. Para nuestro ejemplo sería -9 : 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
NOTA: Si hay empate en los valores (costo relativo más negativo), 
se toma uno de esos circuitos empatados de manera arbitraria. 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
12 •Para hallar la variable saliente se hace lo siguiente: 
•Tomar las casillas con signo negativo de ese circuito y de ellas la que tenga menos unidades asignadas( 
• y esa es la variable saliente). 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 2 3 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
13 
•Hacemos t= unidades asignadas en la variable saliente. 
t = 1 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 - 1 0 + 1 
C2 
1 + 1 - 3 0 
5 
 2 + 1 3 - 1 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
CR-C1F3 = (0x2) – (3x3) + (2x1) – (1x2) = -9 
 14 
•A cada una de las casillas del circuito se le suma o resta el valor de “t” dependiendo del signo asignado. 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 15 
•Con esto la tabla inicial cambió y a esta nueva tabla se le debe repetir todos los pasos desde el 1. 
•El algoritmo termina cuando en alguna tabla todos los costos relativos sean positivos. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 3 2 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 16 
Esta es la nueva tabla a la cual se le debe aplicar todo el algoritmo DE 
PRUEBA DE OPTIMALIDAD nuevamente desde el paso 1. 
Recuerde : El algoritmo termina cuando TODOS los costos relativossean positivos. 
 F1 F2 F3 Ficticia Oferta 
C1 
 2 - 2 + 2 0 
4 
 3 1 
C2 
1 + 1 - 3 0 
5 
 3 2 
C3 
2 2 2 0 
3 
 1 2 
Demanda 3 3 4 2 
ALGORITMO STEPPING-STONE PASO A PASO. 
PASO : 
GRACIAS