Programación Dinámica

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 .

Clase # 20

Programación dinámica
determinística

Etapa
n

Etapa
n+1

Sn

Sn+1

Contribución
fn (Sn, Xn) de Xn

f *n+1 (Sn+1)

20-1

EJEMPLO - Distribución de brigadas médicas.

20-2

El WORLD HEALTHCOUNCIL, se dedica a
mejorar la atención médica en los países
subdesarrollados del mundo.

País

1

2

3

0

0

0

0

1

45

20

50

2

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.

Miles de años - persona de vida adicionales

Brigadas
médicas

70

45

70

3

90

75

80

4

105

110

100

5

120

150

130
Veamos la
formulación

20-3

Formulación.

1
2

3

3

4

• Variable de decisión: Xn : Número de brigadas
asignadas alpaís n.

0

2

• 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).

0
1

Diagrama

4

5

5

20-4

0

• 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-5

5

20-6

1

Ecuación derecursividad.

Sea Pi (X i ) la medida del desempeño por
asignar Xi brigadas médicas al país i, entonces

fn(Sn, Xn) = cs , xn + fn+1 * (Xn)
fn(Sn, Xn) = Pn (Xn) + fn +1 * (Sn - Xn)

3

Σ Pi (Xi )
i=1

Max Z =
3
s.a

Σ Xi = 5
i=1

Etapa n=3 País 3

Como el estado final (cero brigadas para
asignar) se alcanza al terminar la etapa 3,
entonces f4* = 0

Xi ≥ 0 para Xi∈enteros
Se usará el algoritmo hacia atrás.

sigue

20-7

f 3 ( S3 ) = P3 ( X3) + f 4*

0
50
70
80
100
130

0
1

5

+ f3* (0,X2) = P 2 (2) + f3*( 0) = 45

+ f3* (1,X2) = P 2 (1) + f3*(1 ) = 70

2

0
1
2
3
4

130

5

Para ilustrar como proceder, supongamos
que nos quedan 2 brigadas disponibles en este
momento:

f3 * (S3 ) X3*

0
50
70
80
100

+ f3* (2,X2)= P 2 (0) + f3*( 2) = 70
sigue

45

20

2
0

20-9

X2 f2(S2 , X2) = P2 ( X2) +

S2

1

2

3

4

5

20-10

Etapa n=1 País 1

En general para la etapa 2 se tiene:

f 3* ( S2 - X2)

20-8

Etapa n=2 País 2

Debemos asignar todas las brigadas que estén
disponibles en este momento.

S3
0
1
2
3
4

Genérica

f 2* ( S2)

X2*

0
1
2
3
4

0
0
5070
80
100

20
70 45
90 95 75
100 115 125 110

0
50
70
95
125

0
0
0ó1
2
3

5

130 120 125 145 160 150

160

4

En este caso, el único estado que debe
considerarse es el inicial, S1 = 5
0

+ f2* (0,X1) = P 1 (5) + f2*( 0) = 120

4

+ f2* (4,X1) = P 1 (1) + f2*(4 ) = 170

5

+ f2* (5,X1) = P 1 (0) + f2*( 5) = 160
sigue

0
12

45

5
0

20-11

20-12

2

Veamos la tabla:

EJEMPLO - Distribución de científicos.

X1 f 1( S1 , X1) = P1 ( X1) + f 2* ( S1 - X1) f * ( S )
1
1
S1
1
2
3
4
5
0
170
5 160 170 165 160 155 120

X1*
1

Así la asignación óptima será:
X1* = 1

En las circunstancias actuales, la probabilidad de
que los equipos 1,2,3, fracasen es 0.4, 0.6 y 0.8
respectivamente.

S1 - X1 = 4 = S2

X2* = 3S2 - X2 = 1 = S3

X3* = 1

Z = 170000 años

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.
20-13

0

Probabilidad de Fracaso
Equipo
2
1

20-14

Formulación.
• Etapas: Equipos a los cuales se debe adicionar
los científicos. ( n=1,2,3 ).

¿Como adicionar...