Investigacion de operaciones

Clase # 20

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.

Programación dinámica determinística

Etapa n Contribución fn (Sn, Xn) de Xn

Etapa n+1

Sn

Sn+1 f *n+1 (Sn+1)
20-2

20-1

EJEMPLO - Distribución de brigadas médicas.
El WORLD HEALTH COUNCIL, sededica 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.Brigadas médicas 0 1 2 3 4 5

Miles de años - persona de vida adicionales País

1 0 45 70 90 105 120

2 0 20 45 75 110 150

3 0 50 70 80 100 130 Veamos la formulación

20-3

20-4

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

Diagrama

0 1 2 3 4

0 1 2 3 4 5

0

S1 = 5 S2 = S1 - X1 S3 = S2 - X2

20-5

5

5

20-6

1

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

Ecuación de recursividad. fn(Sn, Xn) = cs , xn + fn+1 * (Xn)fn(Sn, Xn) = Pn (Xn) + fn +1 * (Sn - Xn)
Etapa n=3 País 3

Genérica

Max Z = 3 s.a

Σ Xi = 5 i=1

Σ Pi (Xi ) i=1

3

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

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

Debemos asignar todas las brigadas que estén disponibles en este momento.
f 3 (S3 )= P3 (X3) + f 4* 0 50 70 80 100 130

Etapa n=2 País 2

S3 0 1 2 3 4 5

f3 * (S3 ) X3*
0 50 70 80 100 130 0 1 2 3 4 5
20-9

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

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

2
0

20

1 2

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

20-10

En generalpara la etapa 2 se tiene:

Etapa n=1 País 1

S2

X2 f2(S2 ,X2) = P2 (X2) +
0 1 2 3 4 5 0 0 50 70 80 100 1 2 3

f 3* (S2 -X2) 4 5

f 2* (S2) 0 50 70 95 125 160

X2*
0 0 0ó1 2 3 4
20-11

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

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

20 70 45 90 95 75 100 115 125 110

5
0

45

4 5

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

130 120 125 145 160 150

20-12

2

Veamos la tabla:
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

EJEMPLO - Distribución de científicos. X1*
1 Un proyecto espacial necesita investigar un problema de ingeniería para mandar seres humanos a Marte. Existen 3 equiposque 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.
20-13 20-14

Así la asignación óptima será: X1* = 1X2* = 3 X3* = 1 S1 - X1 = 4 = S2 S2 - X2 = 1 = S3 Z = 170000 años

¿Como adicionar los científicos de tal forma que se minimice la probabilidad de fracaso?

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.

Número científicos 0 1 2

Probabilidad de Fracaso Equipo 2 1...