CICLO 2020-1

INVESTIGACION DE OPERACIONES II

Mg. Luis Alberto Ulfe Vega

PROGRAMACIÓN DINÁMICA
PROBABILISTICA

Mg. Luis Alberto Ulfe Vega

2
 PROGRAMACION DINAMICA PROBABILISTICA

PPD
DEFINICIONES
LOGRO DE LA SESION:
Al término de la sesión el estudiante
resuelve problemas de programación PROBLEMA 1
dinámica haciendo uso del cálculo
recursivo incluyendo probabilidades,
minimizando el proceso de cálculo al
considerar solamente los estados y las PROBLEMA 2
decisiones necesarias en cada etapa en
que se divide el problema, alcanzando la
solución óptima.
 PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores
La Programación Dinámica Probabilística difiere de la
Hillier-Lieberman 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
Hamdy Taha 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.
Richard Bronson
 PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores

Hillier-Lieberman

La Programación Dinámica Probabilística difiere de la

Hamdy Taha Determinística en que los estados y los retornos o
retribuciones en cada etapa son probabilísticos.

Richard Bronson
 PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores

Hillier-Lieberman 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
Hamdy Taha una de dos formas:

• Los estados son determinados exclusivamente por las

Richard Bronson 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.

Ver Diagrama
 PROGRAMACION DINAMICA PROBABILISTICA

ESTRUCTURA BASICA DE LA
PROGRAMACION DINAMICA DETERMINISTICA

Etapa Etapa
n n+1
X C1 Sn+
Estado: Sn
n 1

fn(sn,xn) f *n+1(sn+1)
 PROGRAMACION DINAMICA PROBABILISTICA

ESTRUCTURA BASICA DE LA
PROGRAMACION DINAMICA PROBABILISTICA
Etapa
n+1

C1 1 f *n+1 (1)
Etapa
n p1
C2
Estado: Sn X p2 2 f *n+1 (2)
n
pm
fn(sn,xn)

…
Cm
Sea m el número de estados posibles en la etapa n+1. El
m f *n+1 (m)
sistema cambia al estado i con probabilidad pi ( i=1, 2, …
m) dados el estado sn y la decisión xn en la etapa n. Si el
sistema cambia al estado i, Ci es la contribución o costo
de la etapa n a la función objetivo.
 PROGRAMACION DINAMICA PROBABILISTICA

PPD
DEFINICIONES

PROBLEMA 1

PROBLEMA 2
 PROGRAMACION DINAMICA PROBABILISTICA

EJEMPLO 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.40)(0.6)(0.8) = 0.192. (Un 19.2%). El objetivo es minimizar la
probabilidad de fracaso de los 3 equipos, y por ello, se asignaran 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:
# de Probabilidad de fracaso de los equipos
científicos
adicionales A B C
asignados
0 0.40 0.60 0.80
1 0.20 0.40 0.50
2 0.15 0.20 0.30
 PROGRAMACION DINAMICA PROBABILISTICA

Solución

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

Función: f = minimizar probabilidad de fracaso
Estado: s = # de científicos adicionales disponibles
Variable: x = # de científicos adicionales 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
 PROGRAMACION DINAMICA PROBABILISTICA

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
 PROGRAMACION DINAMICA PROBABILISTICA

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
 PROGRAMACION DINAMICA PROBABILISTICA

PPD
DEFINICIONES

PROBLEMA 1

PROBLEMA 2
 PROGRAMACION DINAMICA PROBABILISTICA

EJEMPLO 2
Un repartidor compra a una ganadería 6 galones de Demanda
leche a $1 por galón. Cada galón lo vende a $2 y Probabilid
diaria
solamente comercia con 3 clientes. La ganadería está ad
(galones)
dispuesta a comprar los galones de leche que el
1 0.60
repartidor no alcance a vender pero solamente le Client
pagará la mitad de lo que él pagó al inicio. 2 0.00
e1
Desafortunadamente para el repartidor la demanda 3 0.40
diaria de cada uno de sus clientes es incierta, es por 1 0.50
Client
esto que llevó el registro de sus ventas del año pasado 2 0.10
y resumió la información en probabilidades de la e2
3 0.40
siguiente manera: 1 0.40
Client
2 0.30
Si lo que quiere el repartidor es asignar los 6 galones de e3
leche entre los tres clientes para maximizar los ingresos 3 0.30
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.
 PROGRAMACION DINAMICA PROBABILISTICA

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-xn)}

 PROGRAMACION DINAMICA PROBABILISTICA

Tabla de ingresos esperados in(x)

x Cliente1 Cliente2 Cliente3
0 i1(0)=0 i2(0)=0 i3(0)=0
i1(1)=(0.6)2.0+(0.0)2.0+(0.4)2.0 i2(1)=(0.5)2.0+(0.1)2.0+(0.4)2.0 i3(1)=(0.4)2.0+(0.3)2.0+(0.3)2.0
1
=2.00 =2.00 =2.00
i1(2)=(0.6)2.5+(0.0)4.0+(0.4)4.0 i2(2)=(0.5)2.5+(0.1)4.0+(0.4)4.0 i3(2)=(0.4)2.5+(0.3)4.0+(0.3)4.0
2
=3.10 =3.25 =3.40
i1(3)=(0.6)3.0+(0.0)4.5+(0.4)6.0 i2(3)=(0.5)3.0+(0.1)4.5+(0.4)6.0 i3(3)=(0.4)3.0+(0.3)4.5+(0.3)6.0
3
=4.20 =4.35 =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
 PROGRAMACION DINAMICA PROBABILISTICA

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

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
 PROGRAMACION DINAMICA PROBABILISTICA

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) x1*
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 Cliente 2:3 Cliente3:2
No se incluye 2 en la primera etapa por tener probabilidad = 0
 PROGRAMACION DINAMICA PROBABILISTICA

PPD
DEFINICIONES

PROBLEMA 1

PROBLEMA 2