Taller Programacion Dinamica
-
Upload
dnetwarrior -
Category
Documents
-
view
235 -
download
0
Transcript of Taller Programacion Dinamica
8/9/2019 Taller Programacion Dinamica
http://slidepdf.com/reader/full/taller-programacion-dinamica 1/4
1
TALLER DE PROGRAMACIÓNDINÁMICA
PROBLEMA 1.
BP Amoco dispone de 4 millones dedólares para invertir en tres campospetroleros. Las utilidades que gana en elsitio i (i=1,2,3) dependen de la cantidadinvertida en el, así:
sigue
UTILIDADES (Millones de dólares)CANTIDADINVERTIDAMill de dólares CAMPO 1 CAMPO 2 CAMPO 3
0
4
1
2
3
4
11
7
8
9
3
14
6
10
12
3
15
7
8
13
sigue
Si Se supone que la cantidad invertida encada campo debe ser un múltiplo exactode 1 millón de dólares. Determinar conprogramación dinámica una política deinversiones que eleva al máximo lasutilidades que gana BP Amoco con sustres campos petroleros.
Veamos
SOLUCIÓN:
Etapa n: Campo petrolero al cual se le va asignar unacantidad de millones como inversión (n=1,2,3).
Sn: Cantidad de millones disponibles para asignar alos campos restantes.
X n: Cantidad de millones invertidos en la etapa
Ui(x i):Utilidad obtenida en cada campo por asignarlexi cantidad de dólares como inversión (i=1,2,3).
Veamos
Función objetivo:
)(:3
1
i
i
i xU Max ∑=
∑=
=3
1
4:i
XiSujeta
Xi son enteros no negativos
sigue
8/9/2019 Taller Programacion Dinamica
http://slidepdf.com/reader/full/taller-programacion-dinamica 2/4
2
LA FUNCIÓN DE RECURSIÓN SERÁ:
Fn*(sn,xn) = Un(xn) + f *n+1(sn - xn)
CALCULO DE LA ETAPA 3: n=3
S3 F *(S3) X *3
0123
3
78
13
012
34154
CALCULO DE LA ETAPA 2: n=2F2
*(s2,x2) = U2(x2) + f *3(s2 - x2)
1
2
3
4
15171416
1,3191719181918
10 9
131311
10
13
17
0
0 6
X2S2 42 310 f 2 *(S2) X*2
6 0
1,2
2
CALCULO DE LA ETAPA 1: n=1F1
*(s1,x1) = U1(x1) + f *2(s1 - x1)
4 17
X1S10 21 3 4 f 1 *(S1) X*
2
24 123 24 21 19
SOLUCIÓN:
X*1= 1 CAMPO 1
X*2= 2 CAMPO 2
X*3= 1 CAMPO 3
Conclusión
F1(4)= 24
EL MÁXIMO DE UTILIDADES QUEGANA BP AMOCO EN SUS TRESCAMPOS PETROLEROS SERÁ DE 24MILLONES DE DÓLARES,
UTILIZANDO LA POLÍTICA DEINVERSIÓN MOSTRADA PARA CADACAMPO.
CONCLUSIÓN:PROBLEMA 2.
Una fábrica de papel ha recibido solicitudesde cuatro diferentes litografías, de la siguientemanera:
Solicitud 1: 6 rollos de 2.5 mts a $3.10/rolloSolicitud 2: 5 rollos de 4 mts a $5.25/rollo
Solicitud 3: 4 rollos de 3 mts a $4.4/rollo
sigue
Solicitud 4: 8 rollos de 2. mts a $2.50/rollo
8/9/2019 Taller Programacion Dinamica
http://slidepdf.com/reader/full/taller-programacion-dinamica 3/4
3
La fábrica solo tiene 7 metros de papel paraatender estas órdenes. Ordenes parcialespueden ser satisfechas. Cuáles órdenes y
cuanto de cada una se deben satisfacer paramaximizar el beneficio total.
Veamos
SOLUCIÓN:
1. Etapa n: Litografía a la que asignara una
cantidad de rollos equivalentes en metros (n= 1,2,3,4).
2. Variable de estado Sn: Cantidad de metros disponibles alfinal de cada etapa.
3. Variable de decisión dn : Cantidad de rollos equivalentes enmetros , a entregar en cada etapa
4. Ecuación de estado: Sn= S n-1 - dn.
5 .Función de retorno: Ventas máximas = Rn
6. Restricciones:
o ≤≤ d1 ≤≤ 6 rolloso ≤≤ d2 ≤≤ 5 rolloso ≤≤ d3 ≤≤ 4 rolloso ≤≤ d4 ≤≤ 8 rollos
o ≤≤ Sn ≤≤ 7 metros.
SE RESOLVERÁ POR EL ALGORITMO HACIA DELANTE:
ETAPA 1: Solicitud 1 Función recursiva: F1 (S1)=Max{R1(d1)(rollos de 2.5 metros)
S1 mt S0 mt d1 rollos F1 (S1) d1*rollosR1 (d1)
2 7 2 6.20 6.20 2
4.5 7 3.10 3.101 1
7 7 0 0.0 00.0
ETAPA 2: Solicitud 2 (rollos de 4 metros)Función recursiva: F2 (S2)=Max{R1(d2, S2) + F1(S1 )
S2 mt S1 mt d2 d2*
0.5 4.5 1 1
4.5 4.5 0 02 2 0
F1 (S1)
3.106.20 0
R2 (d2)
5.25
0.00.0
R2+F1 F2 (S2)
3 7
7 7
1
0
5.25
0.0
3.10
5.25
0.0
8.35
3.106.20
5.25
0.0
8.35
3.106.20
5.25
0.0
1
0
ETAPA 3: Solicitud 3 (rollos de 3 metros)Función recursiva: F3 (S3)=Max{R3(d3, S3) + F2(S2)
S3 mt S2 mt d3 d3*
0.5 0.5 0 0
0
F2(S2)R3 (d3)
0
0
R3+F2 F3 (S3)
8.35 8.35
2.0 2.0 06.20 6.20
8.35
6.20
3.0 3.0 0 5.25 00 5.25 5.25
0 3.0 1 4.4 5.25 9.65 9.65 14.5 4.5 0 0 3.10 3.10 3.10 0
1.5 4.5 1 4.4 3.10 7.50
7.0 7.0 0 0 0 0 0
4.0 7.0 1 4.4 0 4.4 4.4 1
1.0 7.0 2 8.8 0 8.8 8.8 2
137.50
0
8/9/2019 Taller Programacion Dinamica
http://slidepdf.com/reader/full/taller-programacion-dinamica 4/4
4
ETAPA 4: Solicitud 4 (rollos de 2 metros)Función recursiva: F 4 (S4)=Max{R4(d4, S4) + F3(S3)
S4 mt S3 mt d4 d4*
0 0 0
0
F3(S3)R4 (d4)
0
0
R4+F3 F4*(S4)
9.650.5 0.5 8.35
1.0 1.0 0 8.800
1.5 1.5 0 0 7.5 7.5
2.0 2.0 0 0 6.20
0 2.0 1 2.5 6.20 8.70
3.0 3.0 0 0 5.25 5.25
1.0 3.0 1 2.5 5.25
4.0 4.0 0 0 4.40
9.658.35
8.80
6.20
7.75
4.40
9.65 0
sigue
S4 mt S3 mt d4 d4*
2.0 4.0 1
2
F3(S3)R4 (d4)
2.5
5.0
R4+F3 F4* (S4)
4.40 6.90
0 4.0 4.40 9.40
4.5 4.5 0 3.100 3.10
2.5 4.5 1 2.5 3.10 5.60
0.5 4.5 2 5.0 3.10 8.10
7.0 7.0 0 0 0 0
1.0 7.0 3 7.5 0 7.5
3.0 7.0 2 5.0 0 5.0
5.0 7.0 1 2.5 0 2.5
ETAPA 4
Veamos
SOLUCIÓN
SOLICITUD E NTREGA C OS TO
1
2
3
4
1 R ollos/4 mt
1 R ollos/3 mt
0 Rollos/2 mt
0 Rollos/2.5mt 0.0
5.25
4.4
0.0
TOTAL 7 Metros 9.65
FIN