INVESTIGACION DE OPERACIONES 2

Programacin Dinmica Probabilstica

Ing. Manuel Snchez Tern

PROGRAMACION DINAMICA PROBABILISTICA

PDP
DEFINICIONES
LOGRO DE LA SESION:
Al trmino de la sesin el estudiante
resuelve problemas de programacin PROBLEMA 1
dinmica haciendo uso del clculo recursivo
incluyendo probabilidades, minimizando el
proceso de clculo al considerar solamente
los estados y las decisiones necesarias en PROBLEMA 2
cada etapa en que se divide el problema,
alcanzando la solucin ptima.
PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores
La Programacin Dinmica Probabilstica difiere de la
Hillier-Lieberman Determinstica en que el estado de la siguiente etapa
no est determinado por completo por el estado y la
Hamdy Taha poltica de decisin de la etapa actual. En su lugar
existe una distribucin de probabilidad para determinar
cul ser el siguiente estado. Sin embargo, esta
Richard Bronson distribucin de probabilidad si queda bien determinada
por el estado y la decisin de la etapa actual.
PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores
La Programacin Dinmica Probabilstica difiere de la
Hillier-Lieberman Determinstica en que los estados y los retornos o
retribuciones en cada etapa son probabilsticos.
Hamdy Taha

Richard Bronson
PROGRAMACION DINAMICA PROBABILISTICA

DEFINICIONES
Autores
Un proceso de decisin de N etapas es probabilstico,
Hillier-Lieberman si el rendimiento asociado con al menos una decisin
del proceso es aleatorio. Esta aleatoriedad
Hamdy Taha generalmente se presenta en una de dos formas:

Los estados son determinados exclusivamente por

Richard Bronson las decisiones, pero los rendimientos asociados
con uno o ms de los estados son inciertos.

Los rendimientos son determinados exclusivamente

por los estados, pero los estados que se presentan
a partir de una o ms de las decisiones son
inciertos.
PROGRAMACION DINAMICA PROBABILISTICA

ESTRUCTURA BASICA DE LA
PROGRAMACION DINAMICA DETERMINISTICA

Etapa Etapa
n n+1
C1
Estado: Sn Xn Sn+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 Xn p2 2 f *n+1 (2)
pm
fn(sn,xn)
Cm

Sea m el nmero 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 decisin xn en la etapa n. Si el sistema
cambia al estado i, Ci es la contribucin o costo de la etapa n a
la funcin objetivo.
PROGRAMACION DINAMICA PROBABILISTICA

PDP
DEFINICIONES

PROBLEMA 1

PROBLEMA 2
PROGRAMACION DINAMICA PROBABILISTICA

EJEMPLO 1 (Asignacin de cientficos)

Un proyecto de investigacin sobre cierto problema de ingeniera 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 cientficos
de alto nivel.

Segn la asignacin a los equipos, la probabilidad de fracaso cambia segn lo indicado en la tabla siguiente:

Probabilidad de fracaso de los equipos

# de cientficos
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

Solucin

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

Funcin: f = minimizar probabilidad de fracaso
Estado: s = # de cientficos adicionales disponibles
Variable: x = # de cientficos adicionales asignados

Etapa 3 (Equipo C)
f3(s3,x3) = p3 Solucin ptima
s3
x3 =0 x3 =1 x3 =2 f3*(s3) x 3*
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 Solucin ptima
s3
x3 =0 x3 =1 x3 =2 f3*(s3) x 3*
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) Solucin ptima
s2
x2 =0 x2 =1 x2 =2 f2*(s2) x 2*
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) Solucin ptima
s2
x2 =0 x2 =1 x2 =2 f2*(s2) x 2*
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) Solucin 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
PDP
DEFINICIONES

PROBLEMA 1

PROBLEMA 2
PROGRAMACION DINAMICA PROBABILISTICA

EJEMPLO 2 (Repartidor de leche)

Un repartidor compra a una ganadera 6 galones de leche a $1 por Demanda
galn. Cada galn lo vende a $2 y solamente comercia con 3 Probabilida
diaria
d
clientes. La ganadera est dispuesta a comprar los galones de (galones)
leche que el repartidor no alcance a vender pero solamente le 1 0.60
pagar la mitad de lo que l pag al inicio. Desafortunadamente Cliente
2 0.00
1
para el repartidor la demanda diaria de cada uno de sus clientes es 3 0.40
incierta, es por esto que llev el registro de sus ventas del ao 1 0.50
pasado y resumi la informacin en probabilidades de la siguiente Cliente
2 0.10
2
manera: 3 0.40
1 0.40
Cliente
2 0.30
Si lo que quiere el repartidor es asignar los 6 galones de leche 3
3 0.30
entre los tres clientes para maximizar los ingresos esperados (ya
que el costo siempre ser $6); sabiendo adems que de los galones
de leche enviados a un determinado cliente no se pueden enviar
los rechazados luego a otro cliente, utilice la programacin
dinmica para determinar cmo el repartidor debe asignar los 6
galones de leche entre sus tres clientes.
PROGRAMACION DINAMICA PROBABILISTICA

Solucin

La demanda de cualquier cliente nunca es ms de tres galones.

Etapas: Clientes
Estados: Galones de leche disponibles
Decisin: Cuntos 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)

Funcin 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 i n(x)

x Cliente1 Cliente2 Cliente3
0 i 1(0)=0 i 2(0)=0 i 3(0)=0
i 1(1)=(0.6)2.0+(0.0)2.0+(0.4) i 2(1)=(0.5)2.0+(0.1)2.0+(0.4)
i 3(1)=(0.4)2.0+(0.3)2.0+(0.3)2.0
1 2.0 2.0
=2.00
=2.00 =2.00
i 1(2)=(0.6)2.5+(0.0)4.0+(0.4) i 2(2)=(0.5)2.5+(0.1)4.0+(0.4)
i 3(2)=(0.4)2.5+(0.3)4.0+(0.3)4.0
2 4.0 4.0
=3.40
=3.10 =3.25
i 1(3)=(0.6)3.0+(0.0)4.5+(0.4) i 2(3)=(0.5)3.0+(0.1)4.5+(0.4)
i 3(3)=(0.4)3.0+(0.3)4.5+(0.3)6.0
3 6.0 6.0 Etapa 3 =4.35
=4.20 =4.35f 3(s 3,x 3)= i 3(x 3) Solucin ptima
s3
x 3 =0 x 3 =1 x 3 =2 x 3 =3 f 3*(s 3) x 3*
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
f 3(s 3,x 3)= i 3(x 3) Solucin ptima
s3
x 3 =0 x 3 =1 x 3 =2 x 3 =3 f 3*(s 3) x 3*
0 0 - - - 0 0
1 - 2 - - 2 1
2 - - 3.4 - 3.4 2
3 - - - 4.35 4.35 3

Etapa 2
f 2(s 2,x 2)= i 2(x 2)+f 3(s 2-x 2) Solucin ptima
s2
x 2 =0 x 2 =1 x 2 =2 x 2 =3 f 2*(s 2) x 2*
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
f 2(s 2,x 2)= i 2(x 2)+f 3(s 2-x 2) Solucin ptima
s2
x 2 =0 x 2 =1 x 2 =2 x 2 =3 f 2*(s 2) x 2*
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
f 1(s 1,x 1)= i 1(x 1)+f 2(s 1-x 1) Solucin ptima
s1
x 1 =0 x 1 =1 x 1 =2 x 1 =3 f 1*(s 1) 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 inversin 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

PDP
DEFINICIONES

PROBLEMA 1

PROBLEMA 2