Metodo del transporte

Clase # 16

Recordemos los procedimientos que habíamos enunciado para hallar una S.B.F inicial.
• Regla de la esquina noroccidental. • Método de Vogel. • Método de Russel

Solución a problemas del transporte.

16-1

16-2

1.Regla de la esquina noroccidental
1 Se toma la celda para la variable X11 (esquina noroccidental) y se asigna el mínimo entre la oferta y la demanda. Si Xij fue laúltima V.B seleccionada, la siguiente elección será Xi, j+1 , si quedan recursos en el origen i. De lo contrario se elige Xi +1, j . En caso de que se satisfagan simultáneamente la oferta y la demanda se presenta una solución degenerada y se escoge arbitrariamente. Veamos
16-3

1 2
Origen

16 30 14

2 16 20 14 0 19 0 20

Destino 3 4 13 22 13 60 20 M 70 10 10 23 0 30 30 19

5 17 15 M 010

Recursos

Ui

20 50 60 50 10 40

3 19 M 30

4(F)
Demanda

Vj

50 50 60 50 Z =2470 + 10M

16-4

2. Método de Vogel. Para cada columna y cada renglón elegible, calcule la diferencia, entendida como la diferencia aritmética entre el menor costo y el que le sigue en orden incremental, en este renglón. En el renglón o columna, donde exista la mayor diferencia, se selecciona lavariable que entra como la de menor costo entre las que quedan. (En caso de empates se elige arbitrariamente). Veamos
1 1 Origen 2 3 16 14 19 2

Destino 3 13 13 20 M 70 0 4 22 19 23 30 0 30 5 17 15 M 0

Diferencia por Recursos renglón

16 14 19 0 20 14

50 60 50 20 50

3 1 0 0

4(F) M Demanda 30
Diferencia por columna
16-5

60 Seleccionar X44=30
Eliminar columna 4
16-6

2

1915

1

Destino
Recursos

1 1 Origen 2 3 16 14 19

2 16 14 19 0 20 14

3 13 13 20 M 70 0

5 17 15 M 20 0 50 60 50 20 50

Diferencia por renglón

Destino 1 2 16 14 19 20 2 3 13 50 13 20 70 20 0 5 17 15 M

Diferencia por Recursos renglón

3 1 0 0

1 Origen 2 3

16 14 19

50 60 50

3 3 1 0

4(F) M Demanda 30
Diferencia por columna

60 Seleccionar X45=20 40 15Eliminar renglón 4(F)
16-7

Demanda 30
Diferencia por columna

2

40 Seleccionar X13=50 2
Eliminar renglón 1
16-8

2

Destino
Recursos

1 2 Origen 3 19 14

2 14 19 20 5

3 13 20 70 20 7

5 40 15 M 60 20 50

Diferencia por renglón

Destino
Recursos

1 2 Origen 3 14 19

2 14 19 20 5

3 13 20 20 20 0 7 20 50

Diferencia por renglón

1

1

0

0

Demanda 30Diferencia por columna

40 Seleccionar X25=40
M-15 M-5 Eliminar columna 5
16-9

Demanda 30
Diferencia por columna

5

5

Seleccionar X23=20 Eliminar renglón 2
16-10

Destino 1 2 3

Diferencia por Recursos renglón

Origen 3

19 30

19 20

20 0

50

Demanda 30
Diferencia por columna

20

0

Seleccionar X31=30 Seleccionar X32=20 Seleccionar X33=0

Destino Recur- Ui3 4 5 sos 16 13 22 17 1 50 50 14 14 13 19 15 60 2 40 20 Origen 19 20 23 M 50 3 19 30 20 0 M 0 M 0 0 4(F) 30 20 50 Demanda 30 20 70 30 60 1 2 16
Z=2460

Vj

Veamos como quedó la S.B.F Inicial

16-11

16-12

2

3. Método de Russel.
Para cada renglón elegible, debe determinarse Ui el mayor costo unitario Cij para el renglón seleccionado i. Para cada columna elegible j, debedeterminarse Vj el mayor costo unitario de los Cij presentes en esa columna. Para cada variable Xij, que no haya sido seleccionada en estos renglones o columnas se calcula ∆ ij = Cij - Ui - Vj La variable que entra es la de mayor valor negativo (en términos absolutos).

Iter U1 U2 U3 U4 V1 V2 V3 V4 V5
1 2 3 4 5 22 19 M 22 19 M 22 19 23 19 23 19 23 M M 19 19 19 19 19 M 23 19 20 23 19 20 23 19 20 23 19 23M M

∆ ij ∆ 45=-2M X45 =50 ∆ 15=-5-M X15 =10 ∆ 13=-29 X13 =40 ∆ 23=-26 X23 =30 ∆ 21=-24 * X21 =30
Irrelevante

Valor mas negativo Asignado

6

Veamos
16-13

X31 =0 X22 =20 X34 =30 Z= 2570
16-14

* El empate se rompe arbitrariamente

PRUEBA DE OPTIMALIDAD. •Una S.B.F es óptima si y sólo si Cij - Ui - Vj ≥ 0 para toda i,j tal que Xij es V.N.B en la iteración actual. •Como el valor...