Taller Modelo Transporte[1]
description
Transcript of Taller Modelo Transporte[1]
1
1
Problemas del transporte
Taller 5
2
PROBLEMA 8.2-10
Es necesario planear el sistema de energía de un nuevo edificio. Las tres fuentes posibles de energía son electricidad, gas natural, y una unidad de celdas solares.
Los requerimientos diarios de energía (todos medidos en las mismas unidades) en el edificio en cuanto a luz eléctrica, calefactores de agua y calefactores de ambiente son:
3
Electricidad 20 unidades
Calefactores de agua 10 unidades
Calefactores de ambiente 30 unidades
El tamaño 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 sólo comprando la energía eléctrica ( a un costo de $50 por unidad). Las otras dos necesidades energéticas se pueden cumplir mediante cualquier fuente o combinación 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 energía.
• Formule este problema como un problema de
transporte construyendo la tabla de costos y requerimientos apropiada.
• Utilice el método de aproximación de Vogel para obtener una solución BF inicial para este problema.
• A partir de la solución inicial BF, aplique en forma interactiva el método simplex de transporte para obtener una solución óptima.
6
Demanda
Oferta
50 80
? 50
? 40
20 30
∝∝
∝∝
30
90
60
30
10
Electricidad
Gas natural
Celdas solares
Ilumi-nación
Calefac-tores agua
AireAcondi
-cionado
2
7
Para construir la tabla de costos y requerimientos apropiada, debemos restringir la oferta de electricidad y gas natural.
ElectricidadLo máximo que estarían dispuestos a comprar sería 60
Gas NaturalLo máximo que estarían dispuestos a comprar sería 40
8
Demanda
Oferta
50 80
? 50
? 40
20 30
60
40
30
90
60
30
10
Electricidad
Gas natural
Celdas solares
Ilumi-nación
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-nación
4(F)Calefac-
tores agua
AireAcondi
-cionado
10
Es imposible obtener iluminación 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-nación
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
método 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-nación
4(F)Calefac-tores agua
Diferencia
porrenglón
AireAcondi-cionado
M-50 10 030
50
50
30
M - 50
20 40
Seleccionar X11=20
Eliminar
columna 1
3
13
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
porrenglón
AireAcondi
-cionado
10 030
80
50
30
Seleccionar X14=40
Eliminar
renglón 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
porrenglón
AireAcondi
-cionado
10 030
50
30
Seleccionar X24=30
Eliminar
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
porrenglón
AireAcondi-cionado
1030
10
10
Seleccionar X32=10
Eliminar
Columna 230
10 20
16
Diferencia
por columna
Demanda
Oferta
50
40
30
10
20
Gas natural
Celdas solares
Diferencia
porrenglón
AireAcondi-cionado
10
Seleccionar X23=10
Seleccionar 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-nación
Calefac-tores agua
AireAcondi-cionado
Electricidad
Gas natural
Celdas solares
20 40
30
10
10
20
Z= 2600
18
Después de obtener una S.B.F inicial, se verifica si
es óptima mediante la prueba de optimalidad.
4
19
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 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 básica.
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-nación
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 sólo si Cij - Ui - Vj ≥≥ 0
para toda i,j tal que Xij es V.N.B en la iteración 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-nación
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
Cómo todos los Cij - Ui - Vj ≥≥ 0 esta es la solución
óptima, y la mejor manera de asignar las fuentes
sería:
20 unidades IluminaciónElectricidad
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 camión 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 mínimo costo.
Veamos 24
Nueva York
3
1
3
1
St. Louis
2
Cleveland
4Dallas
2
2
Los Angeles
1
5
25
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 método 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 0 1
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 función objetivo si se incrementa la V.N.B Xij .
La que entra debe tener un Cij - Ui - Vjnegativo (se elige el más 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 reacción 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 reacción 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
6
31
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 solución 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