1. Ciencia

PROBLEMA 1 .
TALLER DE PROGRAMACIÓN
DINÁMICA
BP Amoco dispone de 4 millones de
dólares para invertir en tres campos
petroleros. Las utilidades que gana en el
sitio i (i=1,2,3) dependen de la cantidad
invertida en el, así:
sigue
CANTIDAD
INVERTIDA
Mill de dólares
UTILIDADES (Millones de dólares)
CAMPO 1
CAMPO 2
CAMPO 3
0
4
3
3
1
7
6
7
2
8
10
8
3
9
12
13
4
11
14
15
Si Se supone que la cantidad invertida en
cada campo debe ser un múltiplo exacto
de 1 millón de dólares. Determinar con
programación dinámica una política de
inversiones que eleva al máximo las
utilidades que gana BP Amoco con sus
tres campos petroleros.
sigue
SOLUCIÓN:
Veamos
Función objetivo:
Etapa n: Campo petrolero al cual se le va asignar una
cantidad de millones como inversión (n=1,2,3).
Sn: Cantidad de millones disponibles para asignar a
los campos restantes.
X n: Cantidad de millones invertidos en la etapa
3
Max : ∑ U i ( xi )
i =1
3
Sujeta: ∑ Xi = 4
i=1
Ui(x i):Utilidad obtenida en cada campo por asignarle
x i cantidad de dólares como inversión (i=1,2,3).
Veamos
Xi son enteros no negativos
sigue
1
CALCULO DE LA ETAPA 3: n=3
LA FUNCIÓN DE RECURSIÓN SERÁ:
S3
Fn* (sn,xn) = U n(xn) + f* n+1 (sn - xn)
0
0
6
1
10
9
2
11
13
13
3
16
14
17
15
4
18
19
18
19
1
2
3
X *3
3
0
1
2
3
4
0
1
2
3
4
CALCULO DE LA ETAPA 2: n=2
F2 * (s2,x2 ) = U2 (x 2 ) + f*3 (s2 - x2 )
S2 X2
F *(S3)
7
8
13
15
CALCULO DE LA ETAPA 1: n=1
F1 * (s1,x1 ) = U1 (x 1 ) + f*2 (s1 - x1 )
4
17
f 2 *(S2 ) X*2
X1
S1
4
0
1
2
3
4
23
24
21
19
17
6
0
10
0
13
1,2
17
2
X*1= 1
CAMPO 1
19
1,3
X*2= 2
CAMPO 2
X*3= 1
CAMPO 3
f 1 *(S1 ) X*2
24
1
SOLUCIÓN:
Conclusión
CONCLUSIÓN:
EL MÁXIMO DE UTILIDADES QUE
GANA BP AMOCO EN SUS TRES
CAMPOS PETROLEROS SERÁ DE 24
MILLONES
DE
DÓLARES,
UTILIZANDO LA POLÍTICA DE
INVERSIÓN MOSTRADA PARA CADA
CAMPO.
F1(4)= 24
PROBLEMA 2.
Una fábrica de papel ha recibido solicitudes
de cuatro diferentes litografías, de la siguiente
manera:
Solicitud 1: 6 rollos de 2.5 mts a $3.10/rollo
Solicitud 2: 5 rollos de 4 mts a $5.25/rollo
Solicitud 3: 4 rollos de 3 mts a $4.4/rollo
Solicitud 4: 8 rollos de 2. mts a $2.50/rollo
sigue
2
La fábrica solo tiene 7 metros de papel para
atender estas órdenes. Ordenes parciales
pueden ser satisfechas. Cuáles órdenes y
cuanto de cada una se deben satisfacer para
maximizar el beneficio total.
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 al
final de cada etapa.
3. Variable de decisión dn : Cantidad de rollos equivalentes en
metros , a entregar en cada etapa
4. Ecuación de estado: Sn = S n-1 - d n.
5 .Función de retorno: Ventas máximas = Rn
Veamos
SE RESOLVERÁ POR EL ALGORITMO HACIA DELANTE:
6. Restricciones:
o ≤≤
o ≤≤
o ≤≤
o ≤≤
d1 ≤≤
d2 ≤≤
d3 ≤≤
d4 ≤≤
ETAPA 1: Solicitud 1 Función recursiva: F1 ( S1)= Max{R1(d1)
(rollos de 2.5 metros)
6 rollos
5 rollos
4 rollos
8 rollos
S1 mt
S0 mt
2
7
2
6.20
6.20
2
4.5
7
1
3.10
3.10
1
7
7
0
0.0
0.0
0
o ≤≤ Sn ≤≤ 7 metros.
d2
0.5 4.5
1
4.5
2
3
7
4.5
2
7
7
0
0
1
0
R2 (d2) F1 (S1 ) R2+F1 F2 (S2 )
5.25
0.0
0.0
5.25
0.0
3.10
3.10
6.20
5.25
0.0
8.35
3.10
6.20
5.25
0.0
8.35
3.10
F2 (S2)
R3 +F2
F3 (S3)
8.35
8.35
8.35
0
0
0
0
6.20
6.20
6.20
3.0
0
0
5.25
5.25
5.25
0
0
3.0
1
4.4
5.25
9.65
9.65
3.10
0
d2 *
S3 mt
S2 mt
d3
0.5
0.5
0
1
2.0
2.0
3.0
0
0
6.20
0
5.25
1
0.0
F1 (S1 ) d1 * rollos
ETAPA 3: Solicitud 3
(rollos de 3 metros)
Función recursiva: F 3 (S3 )=Max{R3(d3 , S3) + F2 (S2 )
ETAPA 2: Solicitud 2
(rollos de 4 metros)
Función recursiva: F2 ( S2)= Max{R1(d2, S 2) + F1(S1 )
S2 mt S1 mt
d1 rollos R1 (d1)
0
R3 (d3)
d3 *
1
4.5
4.5
0
0
3.10
3.10
1.5
4.5
1
4.4
3.10
7.50
7.50
13
7.0
7.0
0
0
0
0
0
4.0
7.0
1
4.4
0
4.4
4.4
0
1
1.0
7.0
2
8.8
0
8.8
8.8
2
3
ETAPA 4: Solicitud 4
(rollos de 2 metros)
Función recursiva: F 4 (S4 )=Max{R4(d4 , S4) + F3 (S3 )
ETAPA 4
S3 mt
4.0
d4
1
R4 ( d4)
F3(S3)
R4 +F 3
2.0
2.5
4.40
6.90
0
4.0
2
5.0
4.40
9.40
4.5
4.5
0
0
3.10
3.10
2.5
4.5
1
2.5
3.10
5.60
0.5
4.5
2
5.0
3.10
8.10
S4 mt
R4 +F 3
F4 *( S4)
9.65
9.65
9.65
8.35
8.35
8.80
8.80
0
7.5
7.5
0
0
6.20
6.20
2.0
1
2.5
6.20
3.0
3.0
0
0
1.0
3.0
1
2.5
4.0
4.0
0
0
4.40
4.40
S4 mt
d4
R4 ( d4)
F3(S3)
0
S3 mt
0
0
0
0.5
0.5
1.0
1.0
0
0
0
0
1.5
1.5
0
2.0
2.0
0
d4*
0
7.0
7.0
0
0
0
0
8.70
1.0
7.0
3
7.5
0
7.5
5.25
5.25
3.0
7.0
2
5.0
0
5.0
5.25
7.75
1
2.5
0
2.5
5.0
7.0
F4* ( S4)
d4*
Veamos
sigue
SOLUCIÓN
SOLICITUD
ENTREGA
1
0 Rollos/2.5mt
0.0
2
1 Rollos/4 mt
5.25
3
1 Rollos/3 mt
4.4
4
0 Rollos/2 mt
0.0
TOTAL
7 Metros
COSTO
FIN
9.65
4