programacion-dinamica-2-ili-292-2006-2

Vista previa del material en texto

1
20-1
Clase # 20
Programación dinámica 
determinística
20-2
En la programación dinámica determinística, 
el estado en la siguiente etapa está 
completamente determinado por el estado y 
la política de decisión de la etapa actual.
Sn Sn+1
Etapa
n
Etapa
n+1
Contribución
de Xnfn (Sn, Xn) f 
*
n+1 (Sn+1)
20-3
EJEMPLO - Distribución de brigadas médicas.
El WORLD HEALTH COUNCIL, se dedica a 
mejorar la atención médica en los países 
subdesarrollados del mundo.
Dispone de 5 brigadas médicas para asignarlas a 
tres de estos países. 
El consejo necesita determinar cuántas brigadas 
debe asignar a cada país (si lo hace) para 
maximizar la medida de la eficiencia de las 
brigadas, la cual será el incremento en el promedio 
de vida esperado en años, multiplicado por la 
población de cada país. 20-4
Brigadas 
médicas
Miles de años - persona de vida adicionales
País
2 31
0 00
20 5045
45 7070
75 8090
110 100105
150 130120
0
1
2
3
4
5
Veamos la 
formulación
20-5
Formulación.
• Etapas: Países a los cuales se les debe asignar las 
brigadas. ( n=1- País1 ); ( n=2 –País 2 ); ( n=3 -País 3).
• Variable de decisión: Xn : Número de brigadas 
asignadas al país n.
• Estado: ¿ Qué es lo que cambia de una etapa a otra?
Sn : Número de brigadas médicas disponibles para 
asignarse a los países restantes
S1 = 5
S2 = S1 - X1
S3 = S2 - X2
20-6
0
5
Diagrama 0
1
2
3
4
5
0
1
2
3
4
5
2
20-7
Sea Pi (Xi) la medida del desempeño por 
asignar Xi brigadas médicas al país i, entonces
Max Z = ΣΣ Pi (Xi ) i=1
3
s.a ΣΣ Xi = 5
3
i=1
Xi ≥≥ 0 para Xi ∈∈ enteros
Se usará el algoritmo hacia atrás.
20-8
Ecuación de recursividad.
fn(Sn, Xn) = cs , xn + fn+1 
* (Xn) Genérica
fn(Sn, Xn) = Pn (Xn) + fn+1 
* (Sn - Xn)
Como el estado final (cero brigadas para 
asignar) se alcanza al terminar la etapa 3, 
entonces f4
* = 0
Etapa n=3 País 3
sigue
20-9
Debemos asignar todas las brigadas que estén 
disponibles en este momento.
S3
f3 (S3) = P3 (X3) + f4
*
f3
*(S3) 
0
50
X3
*
70
80
100
130
0
50
70
80
100
130
0
1
2
3
4
5
0
1
2
3
4
5
20-10
Para ilustrar como proceder, supongamos 
que nos quedan 2 brigadas disponibles en este 
momento:
2
0
1
2
45
20
0
+ f3
*(0,X2) = P2 (2) + f3
*(0) = 45 
+ f3
*(1,X2) = P2 (1) + f3
*(1) = 70
+ f3
*(2,X2) = P2 (0) + f3
*(2) = 70
sigue
Etapa n=2 País 2
20-11
En general para la etapa 2 se tiene:
S2
f2(S2 ,X2) = P2 (X2) + f3
* (S2 -X2) f2
*(S2) X2
*
0
0
50
70
95
125
160
0
0
0 ó 1
2
3
4
0
1
2
3
4
5
0
50
70
80
100
130
20
70
90
100
120
45
95
115
125
75
125
145
110
160 150
1 2 3 4 5
X2 
20-12
En este caso, el único estado que debe 
considerarse es el inicial, S1 = 5
+ f2
*(0,X1) = P1 (5) + f2
*(0) = 120 
+ f2
*(4,X1) = P1 (1) + f2
*(4) = 170
+ f2
*(5,X1) = P1 (0) + f2
*(5) = 160
sigue
5
0
4
5
120
45
0
Etapa n=1 País 1
3
20-13
Veamos la tabla:
Así la asignación óptima será:
X1
* = 1 S1 - X1 = 4 = S2
X2
* = 3 S2 - X2 = 1 = S3
X3
* = 1 Z = 170000 años
S1
f1(S1 ,X1) = P1 (X1) + f2
* (S1 -X1) f1
*(S1) X1
*
0
170 15 160
1 2 3 4 5
170 165 160 155 120
X1
20-14
Un proyecto espacial necesita investigar un 
problema de ingeniería para mandar seres 
humanos a Marte. Existen 3 equipos que analizan el 
problema desde 3 puntos de vista diferentes.
En las circunstancias actuales, la probabilidad de 
que los equipos 1,2,3, fracasen es 0.4, 0.6 y 0.8 
respectivamente. 
La probabilidad de que los tres equipos fracasen es 
0.192. Se debe minimizar la probabilidad de 
fracaso, por los cual se decide adicionar 2 científicos 
de alto nivel.
EJEMPLO - Distribución de científicos.
20-15
¿Como adicionar los científicos de tal forma 
que se minimice la probabilidad de fracaso?
Número 
científicos
Probabilidad de Fracaso
Equipo
2 31
0.6 0.80.4
0.4 0.50.2
0.2 0.30.15
0
1
2
20-16
Formulación.
• Etapas: Equipos a los cuales se debe adicionar 
los científicos. ( n=1,2,3 ).
• Variable de decisión: Xn : Número de 
investigadores asignados al equipo n.
• Estado: ¿ Que es lo que cambia de una etapa a 
otra? Sn : Número de científicos aún disponibles 
para asignarse a los equipos restantes.
S1 = 2
S2 = 2 - X1
S3 = S2 - X2
20-17
Sea Pi (Xi) la probabilidad de fracaso al 
asignar Xi científicos al equipo i, entonces
Min Z = ΠΠ Pi (Xi ) i=1
3
s.a
ΣΣ Xi = 2
3
i=1
Xi ≥≥ 0 para Xi ∈∈ enteros
Se usará el algoritmo hacia atrás.
20-18
Ecuación de recursividad.
fn(Sn, Xn) = Pn (Xn) * fn+1 
* (Sn - Xn)
Como el estado final (cero científicos para 
asignar) se alcanza al terminar la etapa 3, 
entonces f4
* = 1
sigue
fn(Sn, Xn) = Pn (Xn) *min ΠΠ Pi (Xi ) Genéricai=n+1
3
Etapa n=3 Equipo 3
4
20-19
f3 (S3,X3) = P3 (X3) * f4
*
S3
f3
*(S3) = P3 (X3) * f4
*
f3
*(S3) 
0.8
0.5
X3
*
0.3
0
1
2
0
1
2
0.8
0.5
0.3
Debemos asignar todas los científicos que 
estén disponibles en este momento.
20-20
S2
f2(S2 ,X2) = P2 (X2) * f3
* (S2 -X2) f2
*(S2) 
X2 X2
*
0
0
0
2
0
1
2
0.48
0.30
0.18
1 2
0.32
0.20 0.16
0.48
0.30
0.16
Etapa n=2 Equipo 2
Etapa n=1 Equipo 1
S1
f1(S1 ,X1) = P1 (X1) * f2
* (S1 -X1) f1
*(S1) 
X1 X1
*
0
0.060 12 0.064
1 2
0.060 0.072
20-21
Así la asignación óptima será:
X1
* = 1 S1 - X1 = 1 = S2
X2
* = 0 S2 - X2 = 1 = S3
X3
* = 1 Z = 0.06