43434_TallerdeTransporte

Vista previa del material en texto

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
Aire
Acondi
-cionado
2
7
Para construir la tabla de costos y requerimientos 
apropiada, debemos restringir la oferta de 
electricidad y gas natural.
Electricidad
Lo máximo que estarían 
dispuestos a comprar sería 60 
Gas Natural
Lo 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
Aire
Acondi
-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
Aire
Acondi
-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
Aire
Acondi
-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
por
renglón
Aire
Acondi
-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
por
renglón
Aire
Acondi
-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
por
renglón
Aire
Acondi
-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
por
renglón
Aire
Acondi
-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
por
renglón
Aire
Acondi
-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
Aire
Acondi
-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
Aire
Acondi
-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
Aire
Acondi
-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ón
Electricidad
40 unidades sin asignar
Gas Natural
10 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
4
Dallas
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 - Vj
negativo (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 M0
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 - Vj
para 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
7
37
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
Solución óptima
Z=3
38
La ruta será :
St. LouisNueva York Los Angeles