r54606

3. Método simplex simplificado para el problema de transporte

Tabla simplex para el problema de transporte

Ui es el precio sombra de la restricción de recursos iVj es el precio sombra de la restricción de demanda j

Dr. Juan M. Camacho

Procedimientos para construir una solución inicial básica factible

1 R l d l i t1. Regla de la esquina noroeste2. Método de aproximación de Vogel3. Método de aproximación de Russell

1. Regla de la esquina noroeste

La primera elección es x11. De ahí en adelante, si xij fue la última variable

Destino

jseleccionada. La siguiente elección es xi,j+1(siguiente columna) si quedan recursos en el origen i. De otra manera se elige xi+1,j (siguiente fila)

500 750 300 450

650 800 400 600

Recursos ui

12

Destino

1

4

210

1 2 3

650 800 400 600

400 700 500 550 11

17Origen 2

3 1 10

8 9

Z=22500Demandavj

10 10 10 10

Dr. Juan M. Camacho

Prueba de optimalidad

Una solución básica factible es óptima si y solo siUna solución básica factible es óptima si y solo si

Para toda (i,j), tal que xij es no básica.

0≥−− jiij vuc

Para una variable básica xij:Para una variable básica xij:0=−− jiij vuc

Entonces ui y vj satisfacen el conjunto de ecuaciones:

vuc += jiij vuc +=Asignamos una ui o vj igual a cero y a partir del sistema de ecuaciones determinamos las otras ui y vj.

Dr. Juan M. Camacho

500 750 300 4502

ui1 2 3 4

1 10 12

RecursosDestino

650 800 400 600

400 700 500 550

10Demanda 10 10 10

1 10 11

2 8 9Origen

3

17

10 Z=22500vjDemanda 10 10 10

Hagamos u3=055044334 =⇒+= vvuc 900=⇒+= vvuc55044334 ⇒+ vvuc50033333 =⇒+= vvuc

10023223 −=⇒+= uvuc

90022222 =⇒+= vvuc15012112 −=⇒+= uvuc

65011111 =⇒+= vvuc10023223 ⇒+ uvuc 65011111 ⇒+ vvuc

Destino Recursos ui1 2 3 4500 750 300 450

650 800 400 600

400 700 500 550

9 17 -100

12 -150

Origen

1 10 2

2 8

400 700 500 550

10 Z=22500vj 650 900 500 550Demanda 10 10 10

1 10 11 03

Dr. Juan M. Camacho

Encontremos los valores

jiij vuc −−de las variables no básicas

500 750 300 450-50 50 12 1501 10 2

Destino Recursos ui1 2 3 4

650 800 400 600

400 700 500 5501 10 11 0

9 150 17 -100

50 50 12 -150

Origen

1 10 2

2 -100 8

3 -250 -200

10 Z=22500vj 650 900 500 550Demanda 10 10 10

1 10 11 03 250 200

Dr. Juan M. Camacho

Variable que entra:

jiij vuc −− Representa la tasa a la cual cambia la función objetivo si se incrementa en una unidad la variable no básica.

E t l i bl l d b tEntonces la variable que sale debe tener un negativo (se elige el más negativo).

jiij vuc −−


650 800 400 6009 150 17 100

-50 50 12 -150

Origen

1 10 2

2 -100 8

1 2 3 4

400 700 500 550

10 Z=22500j 650 900 500 550Demanda 10 10 10

1 10 11 0

-100g

3 -250 -200

vj 650 900 500 550

Dr. Juan M. Camacho

500 750 300 45050 50 121 10 2


650 800 400 600

400 700 500 5501 10 11

9 150 17 -100

-50 50 12 -150

Origen

1 10 2

2 -100 8

3 250 200

10 Z=22500vj 650 900 500 550Demanda 10 10 10

1 10 11 03 -250 -200

500 750 300 450-- + 121 9 3


650 800 400 600-- +

400 700 500 550+ -- 0 10 11

10 17Origen 2 7

3 1

10 Z=22500vjDemanda 10 10 10

( ) 2505007508004005004001ΔZ ( )2225025022500

2505007508004005004001=−=

−=−+−+−+=Δ

nuevaZZ

Dr. Juan M. Camacho

500 750 300 450


650 800 400 600

400 700 500 550

10 -100 17 150

-50 -200 12 100

Origen

1 9 3

2 100 7

400 700 500 550

10 Z=22500vj 400 650 250 550Demanda 10 10 10

250 10 11 03 1 50

500 750 300 450+ 9 12 1001 0 3


-- +650 800 400 600

400 700 500 550+ -- 1 11 0

10 17 150

100

Origen 2 7

3 10+ --10 Z=20450vj 400 650 250 550

Demanda 10 10 100

( ) 18005004005504509ΔZ ( )20450180022250

18005004005504509=−=

−=−+−+=Δ

nuevaZZ

Dr. Juan M. Camacho

500 750 300 450


650 800 400 600

400 700 500 550

10 100 17 50

-50 9 12 0

Origen

1 200 3

2 300 7

400 700 500 550

10 Z=20450vj 300 750 350 450Demanda 10 10 10

50 1 11 1003 10 -150

500 750 300 450-- + 10 12

01 2


650 800 400 600

400 700 500 550+ -- 0 11

100

10 1750

0

Origen 2 7

3 10 1+ --10 Z=20300vj 300 750 350 450

Demanda 10 10 10100

( ) 1507504505507001ΔZ ( )2030015022450

1507504505507001=−=

−=−+−+=Δ

nuevaZZ

Dr. Juan M. Camacho


650 800 400 60010 100 17 800

-50 10 12 750

Origen

1 50 2

2 150 7

1 2 3 4

400 700 500 550

10 Z=20300vj -300 0 -400 -300Demanda 10 10 10

200 150 11 7003 10 1

500 750 300 450-- + 2 10 12 7501 0


-- +650 800 400 600

+ --400 700 500 550 11 700

8 17 800

750

Origen 2 9

3 10 1

10 Z=20200vj -300 0 -400 -300Demanda 10 10 10

700

( ) 1007508004003002ΔZ ( )2020010022300

1007508004003002=−=

−=−+−+=Δ

nuevaZZ

Dr. Juan M. Camacho

500 750 300 450


650 800 400 600

400 700 500 550

8 50 17 0

2 10 12 -100

Origen

1 100 50

2 150 9

400 700 500 550

10 Z=20200vj 500 800 400 550Demanda 10 10 10

200 100 11 -1003 10 1

Prueba de optimalidad

Una solución básica factible es óptima si y solo si0≥−− jiij vuc

Una solución básica factible es óptima si y solo si

Para toda (i,j), tal que xij es no básica.

Dr. Juan M. Camacho

500 750 300 450

650 800 400 6008 50 17

2 10 12 -100

Origen

1 100 50

2 150 9

Destino Recursos ui1 2 3 4Solución

1Valladolid

400 700 500 550

10 Z=20200vj 500 800 400 550Demanda 10 10 10

200 100 11 -100

8 50 17 0Origen 2 150 9

3 10 1

11 Mérida

Valladolid

12

10

2Tizimin 10

2

109

32

Campeche

17 8 3CancunTicul

4

1010 1

3 4Chetumal11

10

Dr. Juan M. Camacho

Problema de Transporteob e a de a spo tePowerCo Tiene tres centrales eléctricas que cubren las necesidades de cuatro ciudades. Cada central suministra los numeros de kilowatts-hora mostrados en la tabla junto con las demandas de potencia pico en estas ciudades que ocurren aldemandas de potencia pico en estas ciudades, que ocurren al mismo tiempo. Los costos por enviar un millón de kwh de electricidad de una planta a otra dependen de la distancia que debe viajar la electricidad.

ASuministros (millones de

kwh)De Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 kwh)

Planta 1 $8 $6 $10 $9 35

Planta 2 $9 $12 $13 $7 50Planta 2 $9 $12 $13 $7 50

Planta 3 $14 $9 $16 $5 40

Demanda 45 20 30 30Demanda (millones de kwh)

45 20 30 30

Dr. Juan M. Camacho

Destino Recursos ui

1

Recursos ui1 2 3 4

2Origen

3

Demanda Z .vj

Dr. Juan M. Camacho

EjercicioEjercicio

• En tres centros de distribución se embarcan automóviles a cinco agencias. El costo d t t b l di t i t l f t l d tide transporte se basa en la distancia entre las fuentes y los destinos, y es independiente de si los camiones van con carga parcial o total. En la siguiente tabla se ven las distancias entre los centros de distribución y las agencias, junto con las ofertas y demandas, expresadas en números de autos. El costo de transporte por

ill d ió d $25milla de camión es de $25.

Agencia

1 2 3 4 5

1 100 150 200 140 35

Oferta

400Centro 2 50 70 60 65 80

3 40 90 100 150 130

200

150

demanda 100 200 150 160 140demanda 100 200 150 160 140

Dr. Juan M. Camacho

r54606

Documents