11

Problemas del transporte

Taller 5

2

PROBLEMA 8.2-10

Es necesario planear el sistema de energa de un nuevo edificio. Las tres fuentes posibles de energa son electricidad, gas natural, y una unidad de celdas solares.

Los requerimientos diarios de energa (todos medidos en las mismas unidades) en el edificio en cuanto a luz elctrica, calefactores de agua y calefactores de ambiente son:

3

Electricidad 20 unidades

Calefactores de agua 10 unidades

Calefactores de ambiente 30 unidades

El tamao del techo limita la unidad de celdas solares a 30 unidades pero no hay limite en la disponibilidad de electricidad y gas natural. Las necesidades de luz se pueden satisfacer slo comprando la energa elctrica ( a un costo de $50 por unidad). Las otras dos necesidades energticas se pueden cumplir mediante cualquier fuente o combinacin de fuentes.

4

Electricidad Gas natural Celdas solares

Calefactores de agua

Calefactores

de ambiente

$ 90 $ 60 $ 30

$ 80 $ 50 $ 90

5

El objetivo es minimizar el costo total de cumplir con las necesidades de energa.

Formule este problema como un problema de transporte construyendo la tabla de costos y requerimientos apropiada.

Utilice el mtodo de aproximacin de Vogel para obtener una solucin BF inicial para este problema.

A partir de la solucin inicial BF, aplique en forma interactiva el mtodo simplex de transporte para obtener una solucin ptima.

6

Demanda

Oferta

50 80

? 50

? 40

20 30

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

Ilumi-nacin

Calefac-tores agua

AireAcondi

-cionado

27

Para construir la tabla de costos y requerimientos apropiada, debemos restringir la oferta de electricidad y gas natural.

ElectricidadLo mximo que estaran dispuestos a comprar sera 60

Gas NaturalLo mximo que estaran dispuestos a comprar sera 40

8

Demanda

Oferta

50 80

? 50

? 40

20 30

60

40

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

Ilumi-nacin

Calefac-tores agua

AireAcondi-cionado

Vemos que la oferta es mayor que la demanda y por ello debemos crear un nodo ficticio de demanda 4(F)

9

El nodo ficticio de demanda debe absorber las unidades que no se asignan.

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

Demanda

Oferta

50 80 ?

? 50 ?

? 40 ?

20 30 70

60

40

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

Ilumi-nacin

4(F)Calefac-

tores agua

AireAcondi

-cionado

10

Es imposible obtener iluminacin a partir de gas natural

y celdas solares, por lo que este costo debe ser M.

Demanda

Oferta

50 80 0

M 50 0

M 40 0

20 30 70

60

40

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

Ilumi-nacin

4(F)Calefac-

tores agua

AireAcondi

-cionado

El no asignar unidades no debe costar nada.

11

Debemos obtener una S.B.F inicial mediante el

mtodo de Vogel

12

Diferencia

por columna

Demanda

Oferta

50 80 0

M 50 0

M 40 0

20 30 70

60

40

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

Ilumi-nacin

4(F)Calefac-tores agua

Diferencia

porrengln

AireAcondi-cionado

M-50 10 030

50

50

30

M - 50

20 40

Seleccionar X11=20Eliminar

columna 1

313

Diferencia

por columna

Demanda

Oferta

80 0

50 0

40 0

30 70

40

40

30

90

60

30

10

Electricidad

Gas natural

Celdas solares

4(F)Calefac-

tores agua

Diferencia

porrengln

AireAcondi

-cionado

10 030

80

50

30

Seleccionar X14=40Eliminar

rengln 1

8040

30

14

Diferencia

por columna

Demanda

Oferta

50 0

40 0

30 30

40

30

60

30

10

Gas natural

Celdas solares

4(F)Calefac-

tores agua

Diferencia

porrengln

AireAcondi

-cionado

10 030

50

30

Seleccionar X24=30Eliminar

Columna 4

5030 10

15

Diferencia

por columna

Demanda

Oferta

50

40

30

10

30

60

30

10

Gas natural

Celdas solares

Calefac-tores agua

Diferencia

porrengln

AireAcondi-cionado

1030

10

10

Seleccionar X32=10Eliminar

Columna 230

10 20

16

Diferencia

por columna

Demanda

Oferta

50

40

30

10

20

Gas natural

Celdas solares

Diferencia

porrengln

AireAcondi-cionado

10

Seleccionar X23=10Seleccionar X33=20

10

20

20

17

Veamos como qued la S.B.F Inicial

Demanda

Recur-sos

50 80 0

M 50 0

M 40 0

20 30 70

60

40

30

90

60

30

10

4(F)

Vj

UiIlumi-nacin

Calefac-tores agua

AireAcondi-cionado

Electricidad

Gas natural

Celdas solares

20 40

30

10

10

20

Z= 2600

18

Despus de obtener una S.B.F inicial, se verifica si

es ptima mediante la prueba de optimalidad.

419

PRUEBA DE OPTIMALIDAD.

Una S.B.F es ptima si y slo si Cij - Ui - Vj 0 para toda i,j tal que Xij es V.N.B en la iteracin actual.

Como el valor de Cij - Ui - Vj debe ser cero si Xij es V.B, Ui y Vj satisfacen el conjunto de ecuaciones Cij = Ui + Vj para cada (i,j) tal que Xij es bsica.

20

Miremos los Ui y Vj

0

50 40 0

0

50

-10

Demanda

Recur-sos

50 80 0

M 50 0

M 40 0

20 30 70

60

40

30

90

60

30

10

4(F)

Vj

UiIlumi-nacin

Calefac-tores agua

AireAcondi-cionado

Electricidad

Gas natural

Celdas solares

20 40

30

10

10

20

Z= 2600

21

Una S.B.F es ptima si y slo si Cij - Ui - Vj 0 para toda i,j tal que Xij es V.N.B en la iteracin actual.

0

50 40 0

0

50

-10

Demanda

Recur-sos

50 80 0

M 50 0

M 40 0

20 30 70

60

40

30

90

60

30

10

4(F)

Vj

UiIlumi-nacin

Calefac-tores agua

AireAcondi-cionado

Electricidad

Gas natural

Celdas solares

20 40

30

10

10

20

Z= 2600

50

M-50

M-40

20

30

10

22

Cmo todos los Cij - Ui - Vj 0 esta es la solucin ptima, y la mejor manera de asignar las fuentes

sera:

20 unidades IluminacinElectricidad

40 unidades sin asignar

Gas Natural10 unidades Aire acondiconado

30 unidades sin asignar

Celdas solares

10 unidades Calefactores agua

20 unidades Aire acondiconado

23

EL PROBLEMA DE LA RUTA MINIMA

Un camin debe viajar de Nueva York a los Angeles. Se debe formular un problema de transporte balanceado, que pueda usarse para encontrar la ruta de Nueva York a Los Angeles que utiliza el mnimo costo.

Veamos 24

Nueva York

3

1

3

1

St. Louis

2

Cleveland

4Dallas

2

2

Los Angeles

1

525

MATRIZ DE COSTOS

N.Y CL St. LD L.A Destinos

0 2 3 1 M 1+1

M

M

M

M

0 4 1 3 1

Origen

M 0 1 2 1

M M 0 2 1

M MM 0

11

1

1 1 1+1

N.Y

CL

D

St. L

L.A

26S.B.F inicial obtenida mediante el mtodo de la esq. nor.

Origen

Destino

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

1

1

0

1

0 2 3 0 1

-1M M M M 0

1 1 01

1 0

1

1

1

0

1

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

27

Iteraciones.

Paso 1:

Se determina Cij - Ui - Vj para seleccionar la variable que entra a la base.

Cij - Ui - Vj representa la tasa a la cual cambia la funcin objetivo si se incrementa la V.N.B Xij .

La que entra debe tener un Cij - Ui - Vjnegativo (se elige el ms negativo).

Veamos 28

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

En este caso entra X33

1 1 0

1 0

1

1

1

0

-3M-1

1

1

0

1

0 2 3 0 1

-1

M-1

M-1

M+1

M-3

M-3

M-1

-4

-1

1

1

M-4

M-2

M-1

M+1

29

Iteraciones.

Paso 2:

Al incrementar el valor de una variable (entrarla a la base) , se genera una reaccin en cadena, de forma tal que se sigan satisfaciendo las restricciones.

La primera V.B que disminuya su valor hasta cero ser la variable que sale.

sigue 30

Solamente existe una reaccin en cadena que incluye a la V.B entrante, y algunas V.B actuales.

Existen celdas donadoras y celdas receptoras. Luego para saber en cuanto se puede incrementar la V.B entrante, se escoge el menor valor entre las celdas donadoras y esta es la que sale de la base (en caso de empates se elige arbitrariamente).

Veamos

631

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 1 0

1 0

1

1

1

0

-3M-1

1

1

0

1

0 2 3 0 1

-1

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M-1

M-1

M+1

M-3

M-3

M-1

-4

-1

1

1

M-4

M-2

M-1

M+1

+

-

+

-1

0 1

32

Iteraciones.

Paso 3:

Para determinar si la solucin es ptima, se debe calcular nuevamente Ui y Vj , y luego para cada V.N.B, Cij - Ui - Vj .

Se detiene cuando todos los Cij - Ui - Vjpara las V.N.B sean positivos.

Veamos

33

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 1 0

1

1

0

-3M-1

-3

1

0

-3

0 2 3 0 5

-5

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M+3

M+3

M+5

M+1

M+1

M+3

3

-3

1

M

M+2

M-5

M+5

1

0 1

4

En este caso entra X22

34

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 1 0

1

1

0

-3M-1

-3

1

0

-3

0 2 3 0 5

-5

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M+3

M+3

M+5

M+1

M+1

M+3

3

-3

1

M

M+2

M-5

M+5

1

0 1

4

+

-

+

-0

1 0

35

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 1 0

1

1

0

M+2

-3

-2

0

-3

0 2 3 3 5

-5

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M+3

M+3

M+5

M+1

M+1

M+3

0

0

-2

M

M+2

M-5

M+2

1

1

1

0 3

En este caso entra X14

36

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 1 0

1

1

0

M+2

-3

-2

0

-3

0 2 3 3 5

-5

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M+3

M+3

M+5

M+1

M+1

M+3

0

0

-2

M

M+2

M-5

M+2

1

1

1

0 3+

-

+

-

10

1

737

0 3 1 M

M 4 1 3

M 0 1 2

M M 0 2

1 1 1 2

2

1

1

1

1

2

0

M

M

1

Vj

Ui

M M M M 0

1 0 0

1

1

0

M+2

-3

-2

0

-3

0 2 3 1 5

-5

Origen

Destino

Vj

N.Y CL St. LD L.A

N.Y

CL

D

St. L

L.A

M+3

M+3

M+5

M+1

M+1

M+3

2

0

M

M+2

M-5

M+4

1 3

1 3

1

2

Solucin ptima

Z=338

La ruta ser :

St. LouisNueva York Los Angeles