• Author / Uploaded
• ingsgtr

Citation preview

ALGORITMO DE PRUEBA DE OPTIMALIDAD PARA PROBLEMAS DE TRANSPORTE MÉTODO DE ESCALÓN La prueba de optimalidad empieza examinando las celdas vacias en el tablero de transporte que contiene el plan factible de envió inicial.Cada celda vacía (una celda vacía es una que contiene un envió cero) es evaluada para determinar si el costo de transporte es una unidad en esta celda, de una celda que contiene un envío positivo decrece. Si no podemos rebajar los costos de transporte total por relocalizacion de envíos entre las celdas, entonces el plan factible de envío actual es el óptimo.

EL MÉTODO DE ESCALÓN TIENE TRES PASOS: Paso 1. Determinar un plan de envío inicial, este puede darse usando ya sea el procedimiento de la esquina noroeste o el de la celda del mínimo costo. Paso 2. Calcule un evaluador de celda para cada celda vacía. Un evaluador de celda para cada celda vacía es determinado, calculando el costo neto de traslado de 1 unidad de una celda que contiene un envío positivo a las celdas vacías. A continuación, el signo de los evaluadores de celda es chequeado para la optimalidad. Paso 3. Si el plan de envió no es optimo, es decir si en un evaluador de celda falla la prueba de signo, determinamos un nuevo plan de envío con un costo total mas bajo. Esto se logra trasladando la máxima cantidad permitida a esa celda vacía, de tal manera que las restricciones de suministro o demanda no sean violadas, Entonces regresemos al paso 2. EJEMPLO : La CIA tiene cuartos fríos en sus almacenes localizados en Boston ,Nueva York y Washington. En cada almacén la CIA procesa y distribuye langosta para vendedores de pescado localizados en varias ciudades del país. La demanda estima por pedidos de langosta es como sigue: Demanda de langosta de la próxima semana Ciudad

Número de Caja

Miami Chicago Filadelphia Dallas

30 50 65 55 Total

200

Los costos de transportes aéreo por caja entre las plantas y los vendedores son como sigue: Costo de transporte (S/. por caja de langosta)

Miami

Chicago

Filadelphia

Dallas

Boston Desde

14

16

12

20

Nueva York

12

14

10

8

Washington

10

16

8

15

Hacia

En la próxima semana se espera tener el siguiente suministro de langosta disponible

Planta

Suministro

Boston

100

Nueva York

40

Washington

60 200

Solución Planteando la tabla de costos

Miami

Chicago Filadelphia

Dallas

Suministro

Hacia

Boston Desde

30

14

50

16

20

12

20

100

70

8

40

0

15 55 0

60 200

55

Nueva York

12

14

40

10

Washington Demanda

10 30 0

16 50 0

5

8 65 45 5 0

55

20

0

0

Por el método de la esquina Noroeste Miami Boston 30 Nueva York 0 Washington D.C. 0 Requisitos (Demanda)

Chicago Filadelphia Dallas Suministro(ofertas) 14 16 12 20 100 50 20 0 12 14 10 8 40 0 40 0 10 16 8 15 60 0 5 55

30

50

65

55

200

Costo total del plan de envío Factible es: Boston:

30*14 + 50*16 + 20*12 + 0*20= 1460

Nueva York: 0*12 + 0*14 + 40*10 + 0*8

= 400

Washington: 0*10 + 0*16 + 5*8 + 55*15

= 865 S/. 2,725

Usando procedimiento de celda de mínimo costo (verificar)

Miami

Chicago Philadelphia

Dallas

Suministro

Hacia

Boston Desde

30

14

50

16

Nueva York

12

14

Washington

10

16

0

0

Demanda

5

60

12

15

20

100

0

10

40

8

40

0

8

15

60

0

50 0

15 0

200

DESDE Boston DESDE Nueva York DESDE Washington Envios Costos Envios Costos Envios Costos X11 = 30 30x14 X21 = 0 0 X31 = 0 0 X12 = 50 50x16 X22 = 0 0 X32 = 0 0 X13 = 5 5x12 X23 = 0 0 X33 = 60 60x8 X14 = 15 15x20 X24 = 40 40x8 X34 = 0 0 100 S/. 1,580 40 S/. 320 60 S/. 480 Costos total = 1580 + 320 + 480 = S/.2,380

Paso 1. Plan factible de envío inicial determinado por el procedimiento de la celda de mínimo costo D1

D2

Miami

D3

D4

Chicago Philadelphia

Dallas

Suministro

Hacia

O1 Boston Desde

30

14

50

16

O2 Nueva York

12

14

O3 Washington Demanda

10 30

16 50

5

60

12

15

20

100

10

40

8

40

15 55

60 200

8 65

Paso 2. Hay 6 celdas vacías en la matriz. Ellas son (2,1) envío de O2 a D1 (2,2) envío de O2 a D2 (2,3) envío de O2 a D3 (3,1) envío de O3 a D1 (3,2) envío de O3 a D2 (3,4) envío de O3 a D4 Vamos a considerar el traslado de 1 unidad a la celda (2, 1), Tenemos que tomar 1 unidad de la celda (2,4), es decir las 40 unidades tiene que decrecer a 39 con el fin de mantener restricción de suministro de 40 unidades (fila 2) también tenemos que hacer decrecer el envío de 30 cajas de la columna 1 (celda 1,1) para mantener la restricción de demanda D1 en 30 cajas. Tenemos que sumar + 1 a la celda (1,4) para mantener la restricción de suministro de 100 cajas para S1. Estos 4 traslados de 1 unidad son mostradas en la siguiente. Tablero simplex, las flechas indican las transferencias de 1 unidad de (1,1) a (2,1) y una unidad de (2,4) a (1,4). D1

D2 Miami

D3

Chicago

D4

Philadelphia

Dallas

Suministro

Hacia Desde

O1 Boston O2 Nueva York O3 Washington Demanda Boston NY Wash.

30+1 `+ 1

14

50

16

12

14

10 30

16 50

5

60

29x14 + 50x16 + 5x12+16x20 1x12 + 0x14+ 0x10 + 39x8 0x10 + 0x16 + 60x8 + 0x15

12

15+1

20

100

10

40-1

8

40

15 55

60 200

8 65 = 1586 = 324 = 480 S/. 2,390

Es costo de traslado de 1 unidad en (2,1) (evaluador de celda para la celda (1,2)) es: S/.12 x 1 + S/.20 x 1 celda (2.1) celda (1.4)

(S/. 14 x 1 + S/.8 x 1) celda (1.1) celda (2.4)

= 10

Por tanto, es traslado de una unidad a la celda vacía (2,1) incrementa el costo S/.10, es decir, este traslado incrementará no disminuirá los costos totales de transporte. Obsérvese que tenemos un ciclo cerrado esto tiene que suceder siempre en las evaluaciones de celdas vacías. Análogamente calculamos el evaluador de celda para la celda (3,4) reproduciendo el tablero anterior, obtenemos. D1

D2 Miami

D3

Chicago

D4

Philadelphia

Dallas

Suministro

Hacia Desde

O1 Boston

30

14

50

16

O2 Nueva York

12

14

O3 Washington Demanda

10 30

16 50

Boston NY Wash.

5+1

El evaluador es: (15+12) - (20+8) = -1

15-1

20

100

10

40

8

40

´+1

15 55

60 200

8

60-1

30x14 + 50x16 + 6x12+14x20 0x12 + 0x14+ 0x10 + 40x8 0x10 + 0x16 + 59x8 + 1x15

12

65 = 1572 = 480 320 = 487 S/. 2,379

Trasladando 1 unidad de la celda (3,1)disminuye el costo en S/ 1.

Los evaluadores de celdas son ciclos cerrados, se muestran a continuación: Celda vacía

Ciclo cerrado

Costo

Evaluador

(2,1) (2,2) (2,3) (3,1) (3,2) (3,4)

(2,1) ->(2,4) ->(1,4) ->(1,1) (2,2) ->(2,4) ->(1,4) ->(1,2) (2,3) ->(2,4) ->(1,4) ->(1,3) (3,1) ->(3,3) ->(1,3) ->(1,1) (3,2) ->(3,3) ->(1,3) ->(1,2) (3,4) ->(1,4) ->(1,3) ->(3,3)

(12+20)-(8+14) (14+20)-(8+16) (10+20)-(8+12) (12+12)-(8+14) (16+12)-(8+16) (15+12)-(20+8)

= = = = = =

S/. 10 S/. 10 S/. 10 S/. 0 S/. 4 S/. -1 (falla)

Solamente el evaluador de la celda (3.4) es negativo. Entonces por el traslado de 1 unidad a la celda (3,4) podemos hacer decrecer la celda en S/. 1

PASO 3. Del paso 2 sabemos que los costos de transporte disminuyen por el traslado de 1 unidad a la celda (3.4) Ahora hacemos la cantidad de traslado tan grande como sea posible. Pero no podemos violar ninguna restricción de suministro ó demanda. Sea S la cantidad trasladada a la celda vacía (3,4) en la figura de abajo. Observe que el mayor valor que podemos asignar a S es 15u. Si escogiéramos S > 5 (digamos S=20) entonces en la celda (1,4) tendrá un envío negativo. Por tanto en la celda (3,4) tenemos S =15u. , es decir X 14 = 15 D1

D2

Miami

D3

D4

Chicago Philadelphia

Dallas

Suministro

Hacia Desde

5+s

O1 Boston

30

14

50

16

12

15-s

20

100

10

40

8

40

´+s

15 55

60 200

O2 Nueva York

12

14

O3 Washington Demanda

10 30

16 50

60-s

8 65

El nuevo plan factible se muestra en: D1

D2

Miami

D3

D4

Chicago Philadelphia

Dallas

Suministro

Hacia

O1 Boston Desde

30

14

50

16

O2 Nueva York

12

14

O3 Washington Demanda

10 30

16 50

20

12 10

45

8

20

100

40

8

40

15

15 55

60 200

65

Ahora regresamos al paso 2 y chequeamos los signos de todos los evaluadores de celdas vacías. Paso 2: Los evaluadores de celdas vacías junto con los ciclos cerrados se muestran a continuación: Celda vacía

Ciclo cerrado

Costo

Evaluador

(1,4) (2,1)

(1,4) ->(1,3) ->(3,3) ->(3,4) (2,1) ->(1,1) ->(1,3) ->(3,3) -> (3,4) ->(2,4) (2,2) ->(1,2) ->(1,3) ->(3,3) -> (3,4) ->(2,4) (2,3) ->(3,3) ->(3,4) ->(2,4) (3,1) ->(1,1) ->(1,3) ->(3,3) (3,2) ->(1,2) ->(1,3) ->(3,3)

(20+8)-(12+15)

= S/. 1

(12+12+15)-(14+8+8)

= S/. 9

(14+12+15)-(16+8+8) (10+15)-(8+8) (10+12)-(14+8) (16+12)-(16+8)

= = = =

(2,2) (2,3) (3,1) (3,2)

S/. 9 S/. 9 S/. 0(sol alterna) S/. 4

Observe que todos los evaluadores de celda en la tabla anterior son cero o positivos, el plan óptimo de envío es óptimo.

O1 O2 O3

DESDE O1 DESDE O2 DESDE O3 DESDE O4 Envios Costos Envios Costos Envios Costos Envios Costos X11 = 30 30x14 X12 = 50 50*16 X13 = 20 20*12 X14 = 0 0 X12 = 0 0 X22 = 0 0 X23 = 0 0 X24 = 40 40*8 X13 = 0 0 X32 = 0 0 X33 = 45 45*8 X34 = 15 15*15 420 800 600 545 Costos total = 420 + 800 + 600 + 545 = S/.2365

Con un costo total de transporte z= S/.2365 Usando el método en el ejemplo anterior Paso 1. Plan factible envío inicial D1

D2 20

O1 5 O2

D4 10

D3

30 5

60

5

Suministro(ofertas) 20 20

5

30

50

40

10

40

70

6 O3

20 9

Requisitos (Demanda)

5

20

5

5

6 9 35

Paso 2. Evaluaciones de celdas vacías. Hay 6 celdas vacías en el tablero del paso 1. Considere la celda (2,4). El ciclo cerrado para esta celda es (2,4) -> (1,4)-> (1,2) ->(2,2) Como muestra la figura D1

D2 20

O1

D4 10

D3

30

Suministro(ofertas) 20 20

5+S

5 O2

5 60

30 6-S

O3 Requisitos (Demanda)

40

S

20 9 5

5-S

50

10 20

40 5

70 5

6 9 35

El evaluador de celdas es (40 + 30) – (20 + 30) = S/.20 Por tanto cada unidad que traslademos a la celda (2,4) incrementa el costo en S/.20

Los evaluadores de celda para cada celda vacía, junto con los ciclos cerrados se muestran a continuación Celda vacía

Ciclo cerrado

Costo

Evaluador

(2,4) (2,1) (2,3) (3,1) (3,3) (3,4)

(2,4) ->(1,4) ->(1,2) ->(2,2) (2,1) ->(2,2) ->(1,2) ->(1,1) (2,3) ->(1,3) ->(1,2) ->(2,2) (3,1) ->(3,2) ->(1,2) ->(1,1) (3,3) ->(1,3) ->(1,2) ->(3,2) (3,4) ->(2,4) ->(2,2) ->(3,2)

(40+30)-(20+30) (60+30)-(30+20) (50+30)-(10+30) (20+30)-(10+20) (40+30)-(10+10) (70+30)-(40+10)

= = = = = =

S/. 20 S/. 40 S/. 40 S/. 20 S/. 50 S/. 50

Ya que todos los evaluadores de celdas son positivos el plan optimo de envío es óptimo. SOLUCIONES ALTERNATIVAS OPTIMAS En la solución optima de ejemplo de la CIA, la celda vacía (3,1) tiene una evaluación de costo de S/.0. Esto quiere decir que si trasladamos una unidad a la celda (3,1), los costos de transporte disminuirán en una cantidad de 1 x S/.0 = 0. Es decir los costos totales de transporte no cambian. Hagamos un traslado a la celda (3,1) y vemos que pasa usando el tablero D1

D2 14

O1

D4 12

D3

16

Suministro 20 100

30-S O2

50 12

20+S 14

O3

10

16 45-S

S Demanda

30

50

10 40 8 15

65

8 15 55

40 60 200

Haciendo S igual a 30, tenemos el tablero Luego: D1

D2 14

O1

D4 12

D3

16

Suministro 20 100

0 O2 O3

50 12

14

50

10

16

30 Demanda

30

15 50

65

10 40 8 15

8 15 55

40 60 200

Sol 1

Sol 2 30

X11 X12

50

X11 X12

0 50

X13 X14 X21 X22 X23 X24

50 0 0 0 0 40

X31 X32

30 0

X33 X34

15 15 S/. 2,365

20 X13 X14 X21 X22 X23 X24

0 0 0 0 40 0

X31 X32

0 45

X33 X34

15 S/. 2,365

Observe que los dos planes de envío son diferentes en 4 celdas (ó 4 envíos) pero el mínimo costo total es el mismo. Por tanto, podemos concluir que hay múltiples soluciones optimas. NOTA: Si un plan optimo de envío existe una celda vacía (o un envío cero) con un evaluador de celda igual a cero, y si podemos trasladar una unidad de producto a esta celda vacía sin violar cualesquiera de las restricciones de suministro o demanda entonces hay múltiples soluciones optimas.

DEGENERACIÓN DE PROBLEMAS DE TRANSPORTE Aplicando cualquiera de los procedimientos de esquina noroeste de celda de mínimo costo para un problema de transporte con m orígenes y n destinos a menudo terminamos con una solución que contenga de m+n-1 envíos positivos (# variables básicas) Una solución así se llama degenerada Ejemplo: Considere el siguiente problema con m = 2 orígenes y n = 3 destinos. D1

D2 1

O1 10

Suministro 3 15

2

1

5

O2

3

Requisitos

D3 2

10

5

10

10

25

Observe que tenemos un plan envío con tres envíos por tanto la sol es degenerada. Necesitamos tener m + n - 1, 2 + 3 -1= 4 envíos positivos con el fin de aplicar los procedimientos del método del escalón. Para remediar esta situación arbitrariamente asignamos un número pequeño positivo D a cualquiera de las celdas vacías (digamos D = 10 -8) y agregamos D al suministro o la demanda apropiada. Esto se muestra en: D1

D2 1

O1 10

5

O2

3

D3 2 D 2

Suministro 3 15+D 1

10

10 Requisitos

10

20

10 + D

25+D

Observe que ahora hay 4 celdas con envíos positivos. Ahora tenemos un plan factible de envío al cual podemos aplicar los procedimientos apropiados del evaluador de celda. D1

D2 0

O1

D3 2

Suministro 0 1 5

5 O2

2

1 5

O3

2

4 5

Requisitos

5

10

5

3

5

0

5

5

5

10

0

0

5 0

Sol. Inicial: X11 = 5, X22=5, X23=5, X33=5 (n+m-1) sol básica. 5, falta un valor => sol. Degenerada

C= 5*(0) + 5*(1) +5*(5)+5*(3) = 45

0

Sea D: cantidad muy pequeña tiende a cero(en una celda vacía) D1

D2 0 D 2 5 2

O1 5 O2 O3

D3 2

Suministro 5+D 1

1

5 5

4

Celdas Vacías (1,3) (2,1) (3,1) (3,2)

3 5

Requisitos

5

5+D

D1

D2 0

O1

20+D

10 D3 2

Suministro 5+D 1

D-Ø 5 O2

Ø 1 5-Ø 4

2 5+Ø 2

O3

5

10

3

5

5 Requisitos

5

5+D

10

5-Ø >= 0

Ø es 5

D-Ø >= 0

Ø es D

Ø=D

Celda vacía

Ciclo cerrado

Costo

Evaluador

(1,3) (2,1) (3,1)

(1,3) ->(1,2) ->(2,2) ->(2,3) (2,1) ->(2,2) ->(1,2) ->(1,1) (3,1) ->(3,3) ->(2,3) ->(2,2) ->(1,2)->(1,1) (3,2) ->(3,3) ->(2,3) ->(2,2)

(1-2)+(1-5) (2-1)+(2-0)

= S/. -5 < 0 = S/. 3

(2-3)+(5-1)+(2-0) (9-3)+(5-1)

= S/. 5 = S/. 5

(3,2)

C = 5*0 + 2*D +5*1 + 5*5 + 5*3 = 45 + 2*D D1

D2 0

O1 5 O2

2 5+D 2

O3

D3 2 D 1 5-D 4

Suministro 1 5+D

5 Requisitos

5

5+D

10

5

10

3

5