Download - PROGRAMACIÓN DINÁMICA DETERMINISTA.docx
PROGRAMACIN DINMICA DETERMINISTAEn la programacin determinista el estado en la siguiente etapa est Completamente determinado por el estado y la poltica de decisin de la etapa actual. El enfoque de programacin dinmica en los problemas determinsticos, en donde el estado en la siguiente etapa est completamente determinado por el estado y la poltica de decisin de la etapa actual. El caso probabilstico en el que existe una distribucin de probabilidad para el valor posible del siguiente estado este se analizara ms adelante.Una manera de clasificar los problemas de programacin dinmica deterministicas es con base en la forma de funcin objetivo. Por ejemplo puede ser minimizar la suma de las contribuciones en cada etapa individual-como en el problema de la diligencia- o maximizar esa suma, o bien minimizar el producto de los terminnos, etc. Otra clasificacin se puede hacer en trminos de la naturaleza del conjunto de estados en las respectivas etapas.La programacin dinmica deterministas se puede escribir en forma de diagrama como se ve en la figura 1.2
Figura 1.2 Estructura bsica para programacin dinmica deterministaEn la etapa n el proceso se encontrara en algn estado Sn. Al tomar la decisin Xn se mueve a algn estado Sn+1.El valor de la funcin objetivo para la poltica optima de ese punto en delante de ese punto en adelante se calculo previamente como fn+1(Sn+1). La poltica de decisin tambin hace una contribucin a la funcin objetivo. Al combinar estas dos cantidades en la forma apropiada se proporciona a la funcin objetivo fn (Sn,Xn) la contribucin de la etapa n en adelante. La optimizacin respecto a Xn proporciona entonces fn(Sn)= fn (Sn,Xn).Una vez encontramos Xn y fn(Sn) para cada valor posible de Sn, el procedimiento de solucin se mueve hacia atrs una etapa.Una manera de clasificar los problemas de programacin determinista es por la forma de la funcin objetivo. El objetivo puede ser minimizar la suma de las contribuciones de cada una de las etapas individuales, o maximizar esa suma, o bien minimizar el producto de los trminos, etc. Otra clasificacin se puede hacer en trminos de la naturaleza del conjunto de estados en las respectivas etapas. En particular, los estados Sn pueden estar representados por una variable de estado discreta, o por una variable de estado continua.Manera de Clasificar los Problemas de Programacin Dinmica: Forma de la funcin objetiva. Minimizar la suma de las contribuciones en cada una de las etapas individuales, o maximizar esa suma, o bien minimizar el producto de los trminos, etc. Naturaleza del conjunto de estados en las respectivas etapas. Los estados si pueden estar representados por:1- Una variable discreta2- Una variable de estado Continua3- O un vector de estado (ms de una variable)Para resolver un problema de programacin dinmica debemos al menos: Identificacin de etapas, estados y variable de decisin: Cada etapa debe tener asociado una o ms decisiones (problema de 0ptimizacion), cuya dependencia de las decisiones anteriores est dada exclusivamente por las variables de estado. Cada estado debe contener toda la informacin relevante para la toma de decisin asociada al perodo. Las variables de decisin son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la prxima etapa. Descripcin de ecuaciones de recurrencia: Nos deben indicar como se acumula la funcin de beneficios a optimizar (funcin objetivo) y como varan las funciones de estado de una etapa a otra. Resolucin Debemos optimizar cada subproblema por etapas en funcin de los resultados de la resolucin del subproblema siguiente. Notar que las para que las recurrencias estn bien definidas requerimos de condiciones de borde
Algunas de las aplicaciones de programacin dinmica determinista son: Modelo de Volumen-Carga Mochila Modelo del tamao de la fuerza de trabajo Modelo de reposicin de equipos Modelo de inversin Modelos de inventarios
A continuacin se presentarn algunas de estas aplicaciones, cada una de las cuales muestra una nueva idea en la puesta en prctica de la PD.A medida que se presente cada aplicacin, es importante prestar atencin a los tres elementos bsicos de un modelo de PD:
Definicin de las etapas Definicin de las polticas o alternativas Definicin de los estados para cada etapa
De los tres elementos, la definicin del estado por lo comn es la ms sutil.Las aplicaciones que se presentan a continuacin muestran que la definicin de estado vara dependiendo de la situacin que se est modelando.
El estado en la siguiente etapa est completamente determinado por: el estado y la decisin de la etapa actual.
PROGRAMACIN DINMICA PROBABILSTICALa programacin dinmica probabilstica (PDP) es una tcnica matemticamente til para la toma de decisiones interrelacionadas, se presenta cuando el estado en la siguiente etapa no est determinado por completo por el estado y la poltica de decisin de la etapa actual. La programacin dinmica probabilstica difiere de la determinacin en que el estado de la siguiente etapa no est completamente determinado por el estado la poltica de decisin de la etapa actual. En su lugar existe una distribucin de probabilidad para determinar cul ser el siguiente estado. En su lugar existe una distribucin de probabilidad para determinar cul ser el siguiente estado. Sin embargo, esta distribucin de probabilidad si queda bien determinada por el estado y la poltica de decisin en la etapa actual. Por consiguiente la diferencia entre la programacin dinmica probabilstica y la programacin dinmica determinsta (PDD) est en que los estados y los retornos o retribuciones en cada etapa son probabilsticos. La programacin dinmica probabilstica se origina en especial en el tratamiento de modelos estocsticos de inventarios y en los procesos markovianos de decisin. En este apartado se presentar algunos ejemplos generales, con objeto de hacer resaltar la naturaleza estocstica de la programacin dinmica.En la figura 1.3 se describe con un diagrama la estructura bsica que resulta en los problemas de programacin dinmica probabilstica.En lo que se refiere a este diagrama, sea s el nmero de estados posibles en la etapa n+1 y etiquete estos estados al lado derecho por 1,2 S.El sistema cambia al estado i con la probabilidad pi(i=1,2S) dados el estado Sn y la decisin Xn en la etapa n. Si el sistema cambia al estado i,Ci es la contribucin de la etapa n a la funcin objetivoCuando se expande la figura 1.3 para concluir todos los estados y las decisiones posibles en todas las etapas, se obtienen lo que con frecuencia se conoce como un rbol de decisin. Si este rbol de decisin no es muy grande, proporciona una forma til de resumir estas probabilidades.Debido a la estructura probabilidades la relacin entre fn(Sn,Xn) y fn+1 (Sn+1) necesariamente es ms complicada que para el caso deterministico. La forma exacta de esta relacin depender de la forma global de la funcin objetivo.
Figura 1.3 Estructura bsica para programacin dinmica probabilstica
Aplicaciones de programacin dinmica probabilstica
Algunas de las aplicaciones de programacin dinmica probabilstica son:
Un juego aleatorio Problema de inversin Maximizacin del evento de lograr una meta.
INVOP2 Programacin Dinmica Deterministica
PROBLEMA 1 (Modelo: Volumen de carga)Un barco de 4 toneladas es cargado con uno o ms de tres artculos. La tabla siguiente muestra el peso unitariopn, en toneladas y el ingreso por unidadin, en miles de $, para el artculon. Cmo se debe cargar el barco para maximizar los ingresos totales?
Artculonpnin
1231
2347
3114
Tener en cuenta que el barco puede cargar estos artculos en cualquier orden, adems, como el peso unitario y el peso permisible son enteros, las variables slo deben tener valores enteros.
Solucin:Etapa: Cada tipo de artculo hace referencia a una etapa.Estado: La disponibilidad respecto a la capacidad del barcoDecisin: Cuntas unidades de cada tipo de artculo llevarFuncin recursiva: Representa el total de ingreso que se quiere maximizar.
Etapa 3
s3f3(s3,x3)=14x3Solucin ptima
x3=0x3=1x3=2x3=3x3=4f3*(s3)x3*
014(0)=0----00
114(0)=014(1)=14---141
214(0)=014(1)=1414(2)=28--282
314(0)=014(1)=1414(2)=2814(3)=42-423
414(0)=014(1)=1414(2)=2814(3)=4214(4)=56564
s3=0; significa que el barco est lleno, disponibilidad cero.s3=4; significa que el barco est vaco, disponibilidad 4 ton.
Etapa 2
s2f2(s2,x2)=47x2+f3*(s2-3x2)Solucin ptima
x2=0x2=1f2*(s2)x2*
047(0)+0=0-00
147(0)+14=14-140
247(0)+28=28-280
347(0)+42=4247(1)+0=47471
447(0)+56=5647(1)+14=61611
Etapa 1
s1f1(s1,x1)=31x1+f2*(s1-2x1)Solucin ptima
x1=0x1=1x1=2f1*(s1)x1*
031(0)+0=0--00
131(0)+14=14--140
231(0)+28=2831(1)+0=31-311
331(0)+47=4731(1)+14=45-470
431(0)+61=6131(1)+28=5931(2)+0=62622
Para obtener la solucin ptima, se observa que el mximo ingreso generado en la etapa 1, es decir $62 mil, se produce cuando se decide llevar 2 unidades del artculo 1.
PROBLEMA 2 (Modelo: Fuerza laboral)Un contratista constructor estima que la fuerza de trabajo necesaria durante las prximas 5 semanas ser de 5, 7, 8, 4 y 6 trabajadores, respectivamente. La mano de obra en exceso que se conserve le costar $300 por trabajador semanalmente, y la nueva contratacin en cualquier semana tendr un costo fijo de $400 ms $200 por trabajador y por semana. Sugiera un plan de contratacin para minimizar los costos en los que se incurren.
Solucin:Seaxnla mano de obra asignada a cada semana.Searnla mano de obra requerida para cada semana, entonces:r1=5,r2=7,r3=8,r4=4yr5=6
Costo de exceso de mano de obra: 300(xnrn)cuando:xn>rnCosto de contratacin:400 + 200(xnsn)cuando:xn>sn
Etapa 5 (r5= 6)
s5f5(s5,x5)=300(x5- 6)+[400+200(x5-s5)]Solucin ptima
x5=6f5*(s5)x5*
4300(0)+[400+200(2)]=8008006
5300(0)+[400+200(1)]=6006006
6300(0)+[0]=006
Etapa 4 (r4= 4)
s4f4(s4,x4)=300(x4- 4)+[400+200(x4-s4)]+f5*(x4)Solucin ptima
x4=4x4=5x4=6f4*(s4)x4*
8300(0)+[0]+800=800300(1)+[0]+600=900300(2)+[0]+0=6006006
Etapa 3 (r3= 8)
s3f3(s3,x3)=300(x3- 8)+[400+200(x3-s3)]+f4*(x3)Solucin ptima
x3=8f3*(s3)x3*
7300(0)+[400+200(1)]+600=120012008
8300(0)+[0]+600=6006008
Etapa 2 (r2= 7)
s2f2(s2,x2)=300(x2- 7)+[400+200(x2-s2)]+f3*(x2)Solucin ptima
x2=7x2=8f2*(s2)x2*
5300(0)+[400+200(2)]+1200=2000300(1)+[400+200(3)]+600=190019008
6300(0)+[400+200(1)]+1200=1800300(1)+[400+200(2)]+600=170017008
7300(0)+[0]+1200=1200300(1)+[400+200(1)]+600=150012007
8300(0)+[0]+1200=1200300(1)+[0]+600=9009008
Etapa 1 (r1= 5)
s1f1(s1,x1)=300(x1- 5)+[400+200(x1-s1)]+f2*(x1)Solucin ptima
x1=5x1=6x1=7x1=8f1*(s1)x1*
0300(0)+[400+200(5)]+1900=3300300(1)+[400+200(6)]+1700=3600300(2)+[400+200(7)]+1200=3600300(3)+[400+200(8)]+900=380033005
PROBLEMA 3 (Modelo: Reposicin de equipo)En el transcurso de los cuatro siguientes aos, durante cierto proceso de produccin, se desea saber cundo remplazar una mquina o seguir conservndola con la finalidad de encontrar lo ms beneficioso para la empresa. Inicialmente se tiene una mquina con tres aos de antigedad trabajando en la produccin. Los datos respecto a la maquina los obtenemos en la siguiente tabla:
tI(t)C(t)R(t)
Tiempo(aos)Ingreso(miles de $)Costo deoperacin ( $ )Valor deRecuperacin ( $ )
020000200-
11900060080000
218500120060000
317200150050000
415500170030000
514000180010000
61220022005000
Considerar que:El costo de una mquina nueva es $100000.Toda mquina con 6 aos de antigedad debe reemplazarse.Terminado el horizonte de planeacin, la mquina debe venderse.
Como esta es la ltima etapa, la mquina debe venderse, y no hay contribuciones posteriores.El estado de la etapa n es la antigedad t de la mquina al inicio del ao n, entonces:
Etapa 4
ts4ConservarReemplazarSolucin ptima
I(t)-C(t)+R(t +1)I(0)+R(t)+R(1)- 100000 -C(0)f4*(s4)x4*
119000-600+60000=7840020000+80000+80000-100000-200=7980079800R
218500-1200+50000=6730020000+60000+80000-100000-200=5980067300C
317200+1500+30000=4570020000+50000+80000-100000-200=4980049800R
6Se debe reemplazar20000+5000+80000-100000-200=48004800R
Etapa 3
ts3ConservarReemplazarSolucin ptima
I(t)-C(t)+f4(t +1)I(0)+R(t)- 100000 -C(0)+f4*(1)f3*(s3)x3*
119000-600+67300=8570020000+80000-100000-200+79800=7960085700C
218500-1200+49800=6710020000+60000-100000-200+79800=5960067100C
514000-1800+4800=1700020000+10000-100000-200+79800=960017000C
Etapa 2
ts2ConservarReemplazarSolucin ptima
I(t)-C(t)+f3(t +1)I(0)+R(t)- 100000 -C(0)+f3*(1)f2*(s2)x2*
119000-600+67100=8550020000+80000-100000-200+85700=8550085500C o R
415500-1700+17000=3080020000+30000-100000-200+85700=3550035500R
Etapa 1
ts1ConservarReemplazarSolucin ptima
I(t)-C(t)+f2(t +1)I(0)+R(t)- 100000 -C(0)+f2*(1)f1*(s1)x1*
317200-1500+35500=5120020000+50000-100000-200+85500=5530055300R
PROBLEMA 4Una empresa requiere 28, 30, 25, 29 y 20 trabajadores para los prximos 5 aos respectivamente. En la actualidad hay 30 empleados en la empresa. Cada trabajador gana 16000 soles al ao. Al empezar cada ao se puede contratar o despedir trabajadores.Cuesta 1000 soles contratar un trabajador y 15000 soles despedirlo, debido a los seguros y beneficios que se tienen que pagar. Por lo fatigoso que es el trabajo, cada ao renuncian 3 trabajadores (los cuales no cobran los 15000 soles de despido). Mediante el uso de programacin dinmica encontrar la poltica ptima definiendo las etapas, estados y variables de decisin; adems explicar la funcin recursiva. Tener en cuenta que, de ser econmico, sera ideal tener el nmero exacto de trabajadores necesarios en cada semana; adems, la empresa trata en lo posible de evitar los costos de contratacin o despido.
Solucin:rn: Requerimiento de ao nxn: Trabajadores asignados el ao nEtapa: aoEstado: trabajadores que quedan al inicio del presente perodo.fn(sn,xn)= min{16000(xn) + 1000(xn-sn) + 15000(sn-xn) +fn+1(sn+1) } o tambinfn(sn,xn)= min{16000(xn) + 1000(xn-sn) + 15000(sn-xn) + fn+1(xn-3) }teniendo en cuenta que: 1000(xn-sn); xn>sny15000(sn-xn); sn>xn
Por practicidad los costos en las tablas se encuentran en miles de soles
Etapa 5 (r5= 20)
s5f5(s5,x5)=16000(x5)+15000(s5-x5)Solucin ptima
x5=20f5*(s5)x5*
29-3=2616(20)+15(6)=41041020
Etapa 4 (r4= 29)
s4f4(s4,x4)=16000(x4)+1000(x4-s4)+f5(x4-3)Solucin ptima
x4=29f4*(s4)x4*
25-3=2216(22)+1(7)+410 =76976929
27-3=2416(24)+1(5)+410=79979929
Etapa 3 (r3= 25)
s3f3(s3,x3)=16000(x3)+15000(s3-x3)+f4(x3-3)Solucin ptima
x2=25x2=27f3*(s3)x3*
30-3=2716(25)+15(2)+769=119916(27)+ 799=1231119925
Etapa 2 (r2= 30)
s2f2(s2,x2)=16000(x2)+1000(x2-s2)+f3(x2-3)Solucin ptima
x2=30f2*(s2)x2*
28-3=2516(30)+1(5)+1199 =1754175430
30-3=2716(30)+1(3)+1199 =1724172430
Etapa 1 (r1= 28)
s1f1(s1,x1)=16000(x1)+15000(s1-x1)+f2(x1-3)Solucin ptima
x1=28x1=30f1*(s1)x1*
3016(28)+15(2)+1754=223216(30)+1724=2204220430
PROBLEMA 5Una empresa requiere tener una mquina que trabaje durante los 5 aos siguientes. En la actualidad tiene una mquina nueva. La compaa podra conservar la mquina o venderla al empezar cada ao y comprar una nueva. Una mquina nueva cuesta 5000 dlares. Los ingresos obtenidos con la mquina, el costo de mantenimiento y el valor de salvamento que se puede obtener al venderla al final del ao, dependen de la edad de la mquina (vase tabla). Puede utilizarse una mquina hasta un mximo de tres aos de antigedad.
Utilice la programacin dinmica para maximizar la utilidad neta ganada durante los seis aos siguientes.
AO 0-1AO 1-2AO 2-3
Ingresos ($)450030001500
Costos de operacin ($)5007001100
Valor de salvamento al final del ao30001800500
ETAPAS: AosESTADOS: Edad de la mquinaALTERNATIVAS: Conservar, Reemplazar
Como esta es la ltima etapa, la mquina debe venderse, y no hay contribuciones posteriores.El estado de la etapa n es la antigedad t de la mquina al inicio del ao n, entonces:
Etapa 6
ts6ConservarReemplazarSolucin ptima
I(t)-C(t)+R(t +1)I(0)+R(t)+R(1)- 5000 -C(0)f6*(s6)x6*
13000-700+1800=41004500+3000+3000-5000-500=50005000R
21500-1100+500=9004500+1800+3000-5000-500=38003800R
3Se debe reemplazar4500+500+3000-5000-500=25002500R
Etapa 5
ts5ConservarReemplazarSolucin ptima
I(t)-C(t)+f6*(t +1)I(0)+R(t)- 5000 -C(0)+f6*(1)f5*(s5)x5*
13000-700+3800=41004500+3000-5000-500+5000=70007000R
21500-1100+2500=29004500+1800-5000-500+5000=58005800R
3Se debe reemplazar4500+500-5000-500+5000=45004500R
Etapa 4
ts4ConservarReemplazarSolucin ptima
I(t)-C(t)+f5*(t +1)I(0)+R(t)- 5000 -C(0)+f5*(1)f4*(s4)x4*
13000-700+5800=81004500+3000-5000-500+7000=90009000R
21500-1100+4500=49004500+1800-5000-500+7000=78007800R
3Se debe reemplazar4500+500-5000-500+7000=65006500R
Etapa 3
ts3ConservarReemplazarSolucin ptima
I(t)-C(t)+f4*(t +1)I(0)+R(t)- 5000 -C(0)+f4*(1)f3*(s3)x3*
13000-700+7800=101004500+3000-5000-500+9000=1100011000R
21500-1100+6500=69004500+1800-5000-500+9000=98009800R
Etapa 2
ts2ConservarReemplazarSolucin ptima
I(t)-C(t)+f3*(t +1)I(0)+R(t)- 5000 -C(0)+f3*(1)f2*(s2)x2*
13000-700+9800=121004500+3000-5000-500+11000=1300013000R
Etapa 1
ts1ConservarReemplazarSolucin ptima
I(t)-C(t)+f2*(t +1)I(0)+R(t)- 5000 -C(0)+f2*(1)f1*(s1)x1*
03000-700+13000=15300-15300C
Programacin Dinmica Probabilstico
1.- Considere una cadena de supermercados con 3 locales. La cadena debe comprar 6 litros de leche diariamente a un proveedor y distribuirlos en sus tres locales. Si un local vende un litro de leche recibe una utilidad de $2, y por cada litro sobrante diario se obtiene una utilidad de $0.50 al devolverlo al proveedor, por ejemplo, si en un da existen 3 litros en un local y se venden 2 litros, se obtiene una utilidad de $4 por los dos litros vendidos, ms $0.50 por el litro devuelto al proveedor. Sin embargo la demanda de leche en cada local no es conocido con anterioridad y la siguiente tabla muestra los valores posibles de ella.
Determine cuantos Determine la distribucin de los litros de leche.Examinando tenemos ::
Si no sabes que significan los smbolos lete primerolos conceptos en este artculoPrecio de utilidad PU =2Precio de devolucin PD= 0.5
>>como son tres tiendas debo decidir cuanta leche dejar en cada una , de aqu saco que vas aser 3 etapas y que la variable de decisin ( x ) indicara cuanta leche dejar en cada tienda
Xi :cuantos litros de leche dejar en cada tienda
>>Adems , mi estado ser cuanta leche me quede ( y )
Yi:la cantidad de litros de leche que me queda
>> Mi variable de estado cambiara deacuerdo a cuanta leche deje , entonce se formularia as
FT :Yi+1 =Yi - Xi
::Lo que se busca ::
MaxU(x) =2 sum(Di) + 0.5 sum(Xi-Di) donde i={1,2,3}
Fr:Fi(Yi)=Max{ Ui(Xi) + Fi+1(Ui+1) }
::Condiciones de borde ::
Y1=6 , F4(Y4)=0
>> ahora , si leyeron elpost pasadodije que si no te dan una tabla de utilidad tenias que armarla pues aqu se hace o lo puedes calcular al paso , pero mas fcil es tener la tabla y armada
Bien solo indicare como hacer para la tienda 3 , la 2 y 1 la hace ustedes:P
U(0)=0
U(1)=2>
U(2)=3.4
U(3)= ( 2 + 1) 0.4 + ( 4 + 0.5 ) 0.3 + (6)0.3 = 4.35
Igual para la tienda 1 y 2
Quedaria asiU2(0)= 0U2(1)=2U2(2)=3.25U2(3)=4.35
U1(0)=0U1(1)=2U1(2)=3.1U1(3)=4.2
::: Ahora si las iteraciones :::
Para la tienda 3
OBS :solo se le puede asignar asta 3 pues es lo mximo de mi demanda
Para la tienda 2 :
OBS :no siempre la decisin 0 va tomar como valor 0 , ojo.
Para la tienda 1 :
:: Solucin ::Se tienen dos soluciones
X1=1, X2=3,X3=2X1=1, X2=2,X3=2