TALLERTALLER
PROGRAMACIÓN DINÁMICAPROGRAMACIÓN DINÁMICAYY
MODELO DE REDESMODELO DE REDES
PROBLEMA 1PROBLEMA 1. Programación Dinámica . Programación Dinámica
BP Amoco dispone de 4 millones de BP Amoco dispone de 4 millones de dólares para invertir en tres campos dólares para invertir en tres campos petroleros. Las utilidades que gana en el petroleros. Las utilidades que gana en el sitio i (i = 1, 2, 3) dependen de la cantidad sitio i (i = 1, 2, 3) dependen de la cantidad invertida en él, así:invertida en él, así:
siguesigue
UTILIDADES (Millones de dólares)UTILIDADES (Millones de dólares)CANTIDAD CANTIDAD INVERTIDAINVERTIDAMill de dólaresMill de dólares CAMPO 1CAMPO 1 CAMPO 2CAMPO 2 CAMPO 3CAMPO 3
00
44
11
22
33
44
1111
77
88
99
33
1414
66
1010
1212
33
1515
77
88
1313
siguesigue
Se supone que la cantidad invertida en Se supone que la cantidad invertida en cada campo debe ser un múltiplo exacto cada campo debe ser un múltiplo exacto de 1 millón de dólares. Determinar de 1 millón de dólares. Determinar mediante Programación Dinámica una mediante Programación Dinámica una política de inversiones que permita política de inversiones que permita maximizar las utilidades de BP Amoco en maximizar las utilidades de BP Amoco en sus tres campos petrolerossus tres campos petroleros..
Veamos
SOLUCIÓN:SOLUCIÓN:
Etapa n: Campo petrolero al cual se le va asignar unaEtapa n: Campo petrolero al cual se le va asignar una cantidad de millones como inversión (n = 1, 2, 3)cantidad de millones como inversión (n = 1, 2, 3)
Sn: Cantidad de millones disponibles para asignar a Sn: Cantidad de millones disponibles para asignar a los campos restantes.los campos restantes.
X n: Cantidad de millones invertidos en la etapa nX n: Cantidad de millones invertidos en la etapa n
UUii(x(xii):Utilidad obtenida en cada campo por asignarle ):Utilidad obtenida en cada campo por asignarle
XXii cantidad de dólares como inversión (i = 1, 2, 3) cantidad de dólares como inversión (i = 1, 2, 3)
Veamos
Función objetivo:Función objetivo:
)(:3
1
i
i
i xUMax
3
1
4:i
XiSujeta
Xi son enteros no negativosXi son enteros no negativos
siguesigue
LA FUNCIÓN DE RECURSIÓN SERÁ:LA FUNCIÓN DE RECURSIÓN SERÁ:
FFnn**(s(snn,x,xnn) = U) = Unn(x(xnn) + f) + f**
n+1n+1(s(snn - x - xnn))
CALCULO DE LA ETAPA 3: n=3CALCULO DE LA ETAPA 3: n=3
SS33 F F **(S(S33)) X X **33
0011
2233
33
7788
1313
00
11
22
3344151544
CALCULO DE LA ETAPA 2: n=2CALCULO DE LA ETAPA 2: n=2FF22
**(s(s22,x,x22) = U) = U22(x(x22) + f) + f**33(s(s22 - x - x22))
11
22
33
44
1515171714141616
1,31,3191917171919181819191818
1010 99
131313131111
1010
1313
1717
00
00 66
XX22SS22 4422 331100 ff22 **(S(S22)) XX**22
66 00
1,21,2
22
CALCULO DE LA ETAPA 1: n=1CALCULO DE LA ETAPA 1: n=1
FF11**(s(s11,x,x11) = U) = U11(x(x11) + f) + f**
22(s(s11 - x - x11))
44 1717
XX11SS11
00 2211 33 44 ff11 **(S(S11)) XX**11
2424 112323 2424 2121 1919
SOLUCIÓN:SOLUCIÓN:
XX**11= 1 CAMPO 1= 1 CAMPO 1
XX**22= 2 CAMPO 2= 2 CAMPO 2
XX**33= 1 CAMPO 3= 1 CAMPO 3
Conclusión
FF11(4)= 24(4)= 24
EL MÁXIMO DE UTILIDADES QUE EL MÁXIMO DE UTILIDADES QUE GANA BP AMOCO EN SUS TRES GANA BP AMOCO EN SUS TRES CAMPOS PETROLEROS SERÁ DE 24 CAMPOS PETROLEROS SERÁ DE 24 MILLONES DE DÓLARES, MILLONES DE DÓLARES, UTILIZANDO LA POLÍTICA DE UTILIZANDO LA POLÍTICA DE INVERSIÓN MOSTRADA PARA CADA INVERSIÓN MOSTRADA PARA CADA CAMPO.CAMPO.
CONCLUSIÓN:CONCLUSIÓN:
Determine la ruta crítica para el siguiente proyecto:
1 2
5
3
4
6 7
5
10
8
19
10
4
35
7
3
8
4
A
B
C
D
E
F
G
H
IJ
K
L
M
PROBLEMA 2PROBLEMA 2. Modelo de Redes. . Modelo de Redes.
La ruta crítica para el proyecto el la siguiente:
1 2
5
3
4
6 7
5
10
8
19
10
4
3
5
7
3
8
4
A
B
C
D
E
F
G
H
I J
K
L
M
La duración del proyecto es de 35 días.
TIPj = máx{TIPi + Dij} TTTi = mín{TTTj - Dij}
EEvveennttoo EEvveennttoo AAnntteerriioo
rr
TTiieemmppoo mmaass pprrooxxiimmoo
++ TTiieemmppoo aaccttiivviiddaadd
MMááxxiimmoo == ttiieemmppoo mmaass pprróóxxiimmoo
11 -- -- 00
22 11 00 ++ 1100 1100
33 22 1100 ++ 99 1199
44 11 33
00 1199
++ ++
11 33
2222
55 11 22
00 1100
++++
55 88
1188
66 22 33 44 55
1100 1199 2222 1188
++++++++
1100 44 55 77
2277
77 44 55 66
2222 1188 2277
++++++
44 33 88
3355
Tiempo más próximo de un evento.
EEvveennttoo EEvveennttoo iinnmmeeddiiaattoo SSuucceessoorr
TTiieemmppoo mmaass lleejjaannoo
-- TTiieemmppoo aaccttiivviiddaadd
MMíínniimmoo == ttiieemmppoo mmaass lleejjaannoo
77 -- -- 3355 66 77 3355 -- 88 2277 55 66
77 2277 3355
-- --
77 33
2200
44 66 77
2277 3355
-- --
55 44
2222
33 44 66
2222 2277
-- --
33 44
1199
22 33 55 66
1199 2200 2277
-- -- --
99 88
1100
1100
11 22 44 55
1100 2222 2200
-- -- --
1100 11 55
00
Tiempo más lejano de un evento.
Evento HOLGURA Actividad Holgura Lj - (Ei + tij)
1 0-0 = 0 A 20-(0+5) = 15
2 10-10 = 0 B 10-(0+10) = 0
3 19-19 = 0 C 22–(0+1) = 21
4 22-22 = 0 D 20-(10+8) = 2
5 20–18 =2 E 27-(10+10) = 7
6 27-27 = 0 F 19-(10+9) = 0
7 35-35 = 0 G 27-(18+7) = 2
H 27-(19+4) = 4
I 22-(19+3) = 0
J 27-(22+5) = 0
K 35-(18+3) = 14
L 35-(27+8) = 0
M 35-(22+ 4)= 9
TABLA DE HOLGURAS.
1 2
5
3
6 7
2
5
5
27
4
10
35
4
3
3
9
A
B
C
D
E
F
G
H
IJ
K
L
M
LA RUTA CRITICA SERÍA:
4
FINFIN
Recommended