09a Programacion Dinamica Probabilistica

PROGRAMACION DINAMICA PROBABILÍSTICA
Ing. Manuel Sánchez Terán

INVESTIGACION DE OPERACIONES II
PROGRAMACION DINAMICA PROBABILISTICA (PDP)
 INTRODUCCION
La Programación Dinámica Probabilística difiere de la Determinística en que el estado de la siguiente etapa no

está determinado por completo por el estado y la política de decisión de la etapa actual. En su lugar
existe una distribución de probabilidad para determinar cuál será el siguiente estado. Sin embargo, esta
distribución de probabilidad si queda bien determinada por el estado y la decisión de la etapa actual.
Hillier-Lieberman
La Programación Dinámica Probabilística difiere de la Determinística en que los estados y los retornos o
retribuciones en cada etapa son probabilísticos.
Hamdy Taha
Un proceso de decisión de N etapas es probabilístico, si el rendimiento asociado con al menos una decisión
del proceso es aleatorio. Esta aleatoriedad generalmente se presenta en una de dos formas:
 Los estados son determinados exclusivamente por las decisiones, pero los rendimientos
asociados con uno o más de los estados son inciertos.
 Los rendimientos son determinados exclusivamente por los estados, pero los estados que se
presentan a partir de una o más de las decisiones son inciertos.
Richard Bronson
Debido a la estructura probabilística, la relación entre las funciones de costo o contribución entre las
etapas necesariamente es más complicada que en el caso determinístico.
Tomando como referencia el modelo de inventario trabajado en programación dinámica determinística,

éste supone, al comienzo del problema, la demanda de cada período como conocida. Sin embargo, en la
realidad la demanda del período n es una variable aleatoria cuyo valor no se conoce hasta después de
tomar la decisión de producción en el período n. Aún si se conoce el nivel de inventario (estado actual) y
la cantidad a producir en el presente período (decisión), el estado del siguiente período y el costo del
período actual serán variables aleatorias cuyos valores no se conocen hasta que se conozca la demandadel
período actual.
1
c1 *
f n+1(1)
p1
Estado: sn Decisión xn p2 c2 2
*
f n(s n,xn) f n+1(2)

pm
Sea m el número de estados posibles en la

etapa n+1. El sistema cambia al estado i
cm
con probabilidad pi ( i=1, 2, … m) dados el
m
estado sn y la decisión xn en la etapa n. Si el
sistema cambia al estado i, Ci es la f (m)
*
n+1
contribución o costo de la etapa n a la

función objetivo.
Ing. Manuel Sánchez Terán 1

PROBLEMA 1
Un proyecto de investigación sobre cierto problema de ingeniería tiene 3 equipos de investigadores que
buscan resolver el problema desde 3 puntos de vista diferentes. Se estima que en las circunstancias actuales la
probabilidad de que los equipos A, B, C fracasen es de: 0.40, 0.60 y 0.80 respectivamente. Así, la probabilidad
de que los 3 equipos fracasen es de: 0.40x0.6x0.8 = 0.192. (Un 19.2%). El objetivo es minimizar la probabilidad
de fracaso de los 3 equipos y por ello se asignarán al proyecto 2 nuevos científicos de alto nivel.
Según la asignación a los equipos, la probabilidad de fracaso cambia según lo indicado en la tabla siguiente.
Probabilidad de fracaso
# de científicos de los equipos
adicionales asignados A B C
0 0.40 0.60 0.80
1 0.20 0.40 0.50
2 0.15 0.20 0.30
¿Cómo deben asignarse los 2 nuevos científicos para minimizar la probabilidad de que los 3 equipos fracasen?
Solución:
Etapas: N = 3 (tres equipos A, B y C)

Función: f = minimizar probabilidad de fracaso
Estado: s = # de científicos disponibles
Variable: x = # de científicos asignados
Etapa 3 (Equipo C)
f3(s3,x3) = p3 Solución óptima
s3 x3 =0 x3 =1 x3 =2 f3*(s3) x3*
0 0.8 - - 0.8 0
1 - 0.5 - 0.5 1
2 - - 0.3 0.3 2
Etapa 2 (Equipo B)
f2(s2,x2) = p2 * f3(s2-x2) Solución óptima
s2
x2 =0 x2 =1 x2 =2 f2*(s2) x2*
0 (0.6)(0.8)=0.48 - - 0.48 0
1 (0.6)(0.5)=0.30 (0.4)(0.8)=0.32 - 0.30 0
2 (0.6)(0.3)=0.18 (0.4)(0.5)=0.20 (0.2)(0.8)=0.16 0.16 2
Etapa 1 (Equipo A)
f1(s1,x1) = p1 * f2(s1-x1) Solución óptima
s1
x1 =0 x1 =1 x1 =2 f1*(s1) x1*
2 (0.4)(0.16)=0.064 (0.2)(0.3)=0.06 (0.15)(0.48)=0.072 0.06 1
Asignación adicional: Equipo A: 1; Equipo B: 0; Equipo C: 1

2
PROBLEMA 2
Un repartidor compra a una ganadería 6 galones de leche a $1 por

galón. Cada galón lo vende a $2 y solamente comercia con 3 Demanda diaria
Probabilidad
clientes. La ganadería está dispuesta a comprar los galones de leche (galones)
que el repartidor no alcance a vender, pero solamente le pagará 1 0.60
la mitad de lo que él pagó al inicio. Desafortunadamente para el Cliente 1 2 0.00
repartidor la demanda diaria de cada uno de sus clientes es incierta, 3 0.40
1 0.50
es por esto que llevó el registro de sus ventas del año pasado y Cliente 2 2 0.10
resumió la información en probabilidades de la siguiente manera: 3 0.40
1 0.40
Cliente 3 2 0.30
3 0.30
Si lo que quiere el repartidor es asignar los 6 galones de leche entre los tres clientes para maximizar los
ingresos esperados (ya que el costo siempre será $6); sabiendo además que de los galones de leche enviados a
un determinado cliente no se pueden enviar los rechazados luego a otro cliente, utilice la programación
dinámica para determinar cómo el repartidor debe asignar los 6 galones de leche entre sus tres clientes.
Solución:
La demanda de cualquier cliente nunca es más de tres galones.

Etapas: Clientes
Estados: Galones de leche disponibles
Decisión: ¿Cuántos galones enviar a cada cliente?
Variables: xn = Galones enviados al cliente n (no necesariamente el cliente cogerá todos)
dn = Demanda del cliente n (galones comprados por el cliente)
Función recursiva: Ingreso esperado obtenido

in(xn)=2dn + 0.5(xn-dn)
fn(sn,xn) = max{2dn + 0.5(xn-dn) + fn+1(sn+1)} ó fn(sn,xn) = max{2dn + 0.5(xn-dn) + fn+1(sn-xn)}
Tabla de ingresos esperados in(x)

x Cliente1 Cliente2 Cliente3
0 i1(0)=0 i2(0)=0 i3(0)=0
1 i1(1)=(0.6)2.0+(0.0)2.0+(0.4)2.0=2.00 i2(1)=(0.5)2.0+(0.1)2.0+(0.4)2.0=2.00 i3(1)=(0.4)2.0+(0.3)2.0+(0.3)2.0=2.00
2 i1(2)=(0.6)2.5+(0.0)4.0+(0.4)4.0=3.10 i2(2)=(0.5)2.5+(0.1)4.0+(0.4)4.0=3.25 i3(2)=(0.4)2.5+(0.3)4.0+(0.3)4.0=3.40
3 i1(3)=(0.6)3.0+(0.0)4.5+(0.4)6.0=4.20 i2(3)=(0.5)3.0+(0.1)4.5+(0.4)6.0=4.35 i3(3)=(0.4)3.0+(0.3)4.5+(0.3)6.0=4.35
Etapa 3
f3(s3,x3)= i3(x3) Solución óptima

s3 x3 =0 x3 =1 x3 =2 x3 =3
*
f3 (s3) x3
*
0 0 - - - 0 0
1 - 2 - - 2 1
2 - - 3.4 - 3.4 2
3 - - - 4.35 4.35 3
Ing. Manuel Sánchez Terán 3

Etapa 2
f2(s2,x2)= i2(x2)+f3(s2-x2) Solución óptima
s2
x2 =0 x2 =1 x2 =2 x2 =3 f2*(s2) x2*
3 0+4.35=4.35 2+3.4=5.40 3.25+2-=5.25 4.35 5.40 1

4 - 2+4.35=6.35 3.25+3.4=6.65 4.35+2=6.35 6.65 2
5 - - 3.25+4.35=7.60 4.35+3.4=7.75 7.75 3
6 - - - 4.35+4.35=8.70 8.70 3
Etapa 1
f1(s1,x1)= i1(x1)+f2(s1-x1) Solución óptima
s1
x1 =0 x1 =1 x1 =2 x1 =3 f1*(s1) x*1
6 0+8.70=8.70 2+7.75=9.75 3.10+6.65=9.75 4.20+5.40=9.60 9.75 1 (no 2)
$9.75 es el ingreso esperado (en el cual se consideraron las probabilidades), para determinar la utilidad recuerde que la cantidad
de inversión es siempre $6.
Asignar: Cliente1: 1 C l i e n t e 2:3 Cliente3:2
No se incluye 2 en la primera etapa por tener probabilidad = 0

4

09a Programacion Dinamica Probabilistica

Cargado por

Copyright:

Formatos disponibles

09a Programacion Dinamica Probabilistica

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

09a Programacion Dinamica Probabilistica

Cargado por

Copyright:

Formatos disponibles

PROGRAMACION DINAMICA PROBABILÍSTICA

Ing. Manuel Sánchez Terán

PROGRAMACION DINAMICA PROBABILISTICA (PDP)

La Programación Dinámica Probabilística difiere de la Determinística en que el estado de la siguiente etapa no

Tomando como referencia el modelo de inventario trabajado en programación dinámica determinística,

f n(s n,xn) f n+1(2)

Sea m el número de estados posibles en la

contribución o costo de la etapa n a la

Ing. Manuel Sánchez Terán 1

Etapas: N = 3 (tres equipos A, B y C)

Asignación adicional: Equipo A: 1; Equipo B: 0; Equipo C: 1

Ing. Manuel Sánchez Terán

Un repartidor compra a una ganadería 6 galones de leche a $1 por

La demanda de cualquier cliente nunca es más de tres galones.

Función recursiva: Ingreso esperado obtenido

Tabla de ingresos esperados in(x)

f3(s3,x3)= i3(x3) Solución óptima

Ing. Manuel Sánchez Terán 3

3 0+4.35=4.35 2+3.4=5.40 3.25+2-=5.25 4.35 5.40 1

Asignar: Cliente1: 1 C l i e n t e 2:3 Cliente3:2

No se incluye 2 en la primera etapa por tener probabilidad = 0

Ing. Manuel Sánchez Terán

También podría gustarte