Definición:
La programación dinámica, es una técnica que permite la resolución de problemas que tratan de alcanzar determinados fines, a través, de una serie de etapas o fases compuestas de diversos estados, de estos es necesario hacer una elección, de tal manera que se alcance la máxima efectividad global, también podemos decir, que es una técnica matemática que trata con la optimización de procesos de decisión. La optimización es por fases en vez de simultánea.
Elementos que intervienen en un problema de programación dinámica:
1.- ETAPAS:
Se pueden definir como cada uno de los pasos que se deben seguir para llegar al objetivo. Las representamos por líneas discontinuas.
2.- ESTADOS:
Son las diversas condiciones posibles en la que el sistema podría estar en esa etapa del problema. Se representan por círculos.
3.- POLÍTICA:
Es cualquiera de los caminos que llevan de la primera a la última etapa.
4.- SUBPOLÍTICA:
Es un subconjunto de la política.
Ejemplo:
Luego, por el
Teorema de Optimidad, podemos afirmar lo siguiente:
"Una política óptima sólo puede estar formada por subpolíticas óptimas".
Este teorema es suceptible de ser demostrado:
Una subpolítica de la política óptima, si esa subpolítica no es óptima, existe otra mejor, la cual completada con el resto de la política, permitirá mejorar esta, por lo tanto, nos daría otra política óptima y por lo señalado, sería contrario a la hipótesis.
BELLMAN enunció el Teorema de la Optimidad, bajo la forma de un principio general:
" Una política es óptima, sí en un período dado, cualesquiera que sean las decisiones que se tomen, constituyan una política óptima teniendo en cuenta los resultados de las decisiones precedentes".
Características de las aplicaciones de programación dinámica
1 El problema se puede dividir en etapas; cada etapa requiere una decisión. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.
2 Cada etapa tiene un número de estados asociados con ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
3 La decisión tomada en cualquier etapa indica cómo se transforma el estado en la etapa actual en el estado en la siguiente etapa. En muchos problemas, una decisión no determina con certeza el estado de la siguiente etapa; en lugar de ello, la decisión actual sólo determina la distribución de probabilidad del estado en la etapa siguiente.
4 Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de estados previamente alcanzados o de decisiones previamente tomadas. A esta idea se le conoce como principio de optimalidad.
5 Si los estados del problema se han clasificado en uno de N etapas, debe haber una fórmula recursiva que relacione el costo o beneficio durante las etapas n, n+1,…, N con el costo o beneficio de las etapas n+1, n+2,…,N. En esencia, la fórmula recursiva formaliza el procedimiento de marcha atrás.
Ejercicios
PREGUNTA N° 1
Los datos corresponden a los costos que le significa a una empresa enviar unidades de cierto artículo de una ciudad a otra. Se pide determinar la ruta óptima de envío desde la ciudad A a la ciudad N.
PREGUNTA N° 2
Una empresa desea determinar cual es la mejor alternativa para invertir US$3.000.000, en tres proyectos, la inversión debe realizarse por unidades de
US$500.000, la información relevante se resume a continuación:
¿ Como invertiría Ud. Los US$ 3.000.000 ?
PREGUNTA N° 3
Una empresa desea determinar su programa de compra para los próximos 4 meses. Se dispone de una capacidad de almacenamiento de 30 unidades, el costo de inventario es de $ 3 por unidad – mes, se cuenta con una existencia inicial de 4 unidades y la final debe ser de 4 unidades. La información faltante se resume en la tabla siguiente:
Determine el programa óptimo de compra.
PREGUNTA N° 4
Una empresa desea determinar cual es la mejor alternativa para invertir US$ 3.000.000, en cuatro proyectos, la inversión debe realizarse por unidades de US$ 500.000, la información relevante se resume a continuación:
¿Cómo invertiría Ud. los US$ 3.000.000?
PREGUNTA N° 5
Una empresa desea determinar su programa de compra para los próximos 4 trimestres. Se dispone de una capacidad de almacenamiento de 30 unidades, el costo de inventario es de $ 3 por unidad – trimestre, se cuenta con una existencia inicial de 4 unidades y la final debe ser de 4 unidades. La información faltante se resume en la tabla siguiente:
Determine el programa óptimo de compra.
PREGUNTA N° 6
Una empresa desea determinar cual es la mejor alternativa para invertir US$ 2.500.000, en tres proyectos, la inversión debe realizarse por unidades de US$ 500.000, la información relevante se resume a continuación:
¿Cómo invertiría Ud. Los US$ 2.500.000 ?
PREGUNTA N° 7
Una empresa desea determinar su programa de compra para los próximos 4 trimestres. Se dispone de una capacidad de almacenamiento de 30 unidades, el costo de inventario es de $ 2 por unidad – mes, se cuenta con una existencia inicial de 3 unidades y la final debe ser de 5 unidades. La información faltante se resume en la tabla siguiente:
Determine el programa óptimo de compra.
PREGUNTA N° 8
Una empresa desea determinar cual es la mejor alternativa para invertir US$ 2.500.000, en cuatro proyectos, la inversión debe realizarse por unidades de US$ 500.000, la información relevante se resume a continuación:
¿Cómo invertiría Ud. los $ 2.500.000?
PREGUNTA N° 9
Una empresa desea determinar cual es la mejor alternativa para invertir US$ 2.500.000, en cuatro proyectos, la inversión debe realizarse por unidades de US$ 500.000, la información relevante se resume a continuación:
¿Cómo invertiría Ud. los $ 2.500.000?
PREGUNTA N° 10
Una empresa desea determinar cual es la mejor alternativa para invertir US$ 2.500.000, en cuatro proyectos, la inversión debe realizarse por unidades de US$ 500.000, la información relevante se resume a continuación:
¿Cómo invertiría Ud. los $ 2.500.000?
PREGUNTA N° 11
Una empresa desea determinar su programa de compra para los próximos cuatro meses. Se dispone de una capacidad máxima de almacenamiento de 25 unidades, el costo de mantener inventario es de $ 3 por unidad-mes, se cuenta con una existencia inicial de 5 unidades y la existencia final debe ser de 2 unidades. La información faltante se resume en la tabla siguiente:
Determine el programa óptimo de compra.
PREGUNTA N° 12
Una empresa desea determinar su programa de compra para los próximos cuatro trimestres. Se dispone de una capacidad máxima de almacenamiento de 35 unidades, el costo de mantener inventario es de $ 3 por unidad-mes, se cuenta con una existencia inicial de 3 unidades y la existencia final debe ser de 2 unidades. La información faltante se resume en la tabla siguiente:
Determine el programa óptimo de compra.
PREGUNTA N° 13
Una compañía de máquinas vendedoras opera normalmente una máquina con dos años de uso en cierto lugar. Las estimaciones de mantenimiento, costo de reemplazo e ingresos (todo en miles de $ ) para cualquier máquina en este sitio, en función de la edad de la máquina se resume a continuación:
De acuerdo a una política establecida, ninguna máquina se conserva después que cumple seis años y solamente se reemplazan por máquinas nuevas. Determine una política de reemplazo que maximice el beneficio total para este sitio durante los próximos cuatro años.
PREGUNTA N° 14
Una pequeña compañía constructora tiene actualmente un camión de volteo de un año de antigüedad. En la tabla siguiente se dan estimaciones del mantenimiento, costos de reemplazo y de los beneficios que se pueden esperar en dinero, junto con datos similares para camiones nuevos que podrían comprarse en el futuro; todas las cantidades están expresadas en unidades de US$ 1.000. Los camiones nunca se conservan durante más de tres años y los reemplazos se hacen sólo por modelos nuevos. Determínese una política de reemplazo de beneficio máximo para este camión durante los próximos 5 años.
Programación Dinámica Probabilística.
En la programación dinámica probabilística, el estado en la etapa siguiente no queda completamente determinado por el estado y la decisión de la subpolítica en el estado actual, sino que existe una distribución de probabilidad para lo que sería el estado siguiente.
Gráficamente tenemos:
donde:
1 N es el número de estados posibles de la etapa n + 1
2 p1, p2, …, pN. Distribución de probabilidad de lo que será el estado,
dados Sn y Xn en la etapa n.
3 ci : es la contribución resultante de la función objetivo.
Por ejemplo, si el objetivo es minimizar la suma esperada de las contribuciones de las etapas individuales, la función objetivo quedaría:
Donde esta minimización se toma sobre los valores factibles de Xn + 1
Ejemplo 1
Una compañía ha recibido un pedido para surtir un solo artículo muy especial y de una calidad tan rigurosa que es posible que el fabricante tenga que producir más de un artículo para obtener uno aceptable. La probabilidad estimada para que sea aceptable es 1/3 y de que sea defectuoso sin posibilidad de reparación 2/3. Por lo tanto la probabilidad de producir cero artículos aceptables en un lote de tamaño L es (2/3)L.
Los costos marginales de producción son de $ 100 por artículo, incluso si es defectuoso (los artículos en exceso no tienen valor). El costo de preparación es $ 200, cada vez que se monte el proceso de producción de este artículo, el cual puede hacerlo como máximo 3 veces. Si no se ha obtenido un artículo aceptable al final de la tercera serie de producción, el costo por ventas perdidas y de penalización será de $ 1500. El objetivo es determinar la política referente al tamaño del lote para las series de producción de manera de minimizar el costo total esperado.
Solución:
Etapas: Series de producción (1, 2, 3).
Variables de decisión: Xn: Son el tamaño del lote producción en la etapa n.
Estados: Sn : puede suceder que, Sn =0 si el articulo aceptable se logro en la etapa anterior. o Sn =1 que significa que en la etapa anterior no se logró el articulo aceptable.
f*n (Sn) = Mín fn(Sn,Xn)
Xn = 0, 1, …, L (tamaño del lote, costo marginal)
Donde:
f*n (0) = 0 y S = 0 , cuando se ha obtenido en la etapa anterior un artículo aceptable, por lo tanto f*n (0) = 0, en esta etapa no es necesario que se incurra en gastos adicionales.
(Prob. de 0 art. acept. ( prob de 1 art. Acept.)
f*n (Sn,Xn) = K + Xn + (2/3)Xn fn + 1 (1) + ( 1- (2/3)Xn) fn + 1 (0)
donde:
( 1- (2/3)Xn) fn + 1 (0) = 0 costo marginal
luego
f*n (1,Xn) = K + Xn + (2/3)Xn f*n + 1 (1).
Considerando $ 100 como unidad monetaria y definiendo
0 Si Xn = 0
K =
2 Si Xn ? 0 (costo de preparación)
(ETAPA ANTERIOR NO SE LOGRO ART. ACEPTABLE)
f*4 (1) = 15 , que es el costo de no obtener un artículo aceptable y perder la venta.
f*4 (0) SI SE LOGRO ART.ACEPT.
Luego, para n = 3 tendríamos:
Luego la solución del problema es la siguiente:
En la primera serie de producción deben fabricarse 3 artículos, si se obtiene un articulo aceptable, X2 = X3 = 0. Si son defectuosos en la segunda se debe fabricar 3 artículos, si se obtiene un articulo aceptable X3 = 0. Si son defectuosos en la tercera serie de producción deben fabricarse 4 artículos, todo con un costo esperado de $ 727.-
Ejemplo 2.-
Un joven estadístico cree que ha desarrollado un sistema para ganar en un juego de las vegas. Sus colegas no creen que esto sea posible, de modo que hacen una gran apuesta con él de que, empezando con dos fichas no podrá tener 5 o más fichas después de 4 jugadas.
Cada jugada comprende la apuesta de cualquier Nº deseado de fichas, se gana o se pierde lo apostado, él estadístico cree que su sistema le dará una probabilidad de 2/3 de ganar cada jugada.
Suponiendo que él estadístico está en lo correcto, se debe determinar cuántas fichas apostar en cada una de las cuatro jugadas.
El objetivo es maximizar la probabilidad de ganar la apuesta.
Solución:
Etapas: jugadas ( 1, 2, 3 y 4 )
Variable de decisión Xn : Nº de fichas que deben apostarse en la etapa n
Estados: Sn : Nº de fichas disponibles para apostar en esa etapa.
f*n (S ) = máx fn ( Sn, Xn )
Xn = 0, 1, …, 5
fn( Sn, Xn ) = 1/3 f*n + 1 ( Sn – Xn ) + 2/3 f*n + 1 ( Sn + Xn )
f*4(S) = 0 , Si S < 5 ? Pierde la apuesta;
f*4(S) =1 , Si S ? 5 ? Gana la apuesta.
La relación recursiva es:
f* n( Sn) =Max ? 1/3 f*n + 1 ( Sn – Xn ) + 2/3 f*n + 1 ( Sn + Xn )?
Xn = 0, 1, 2, …, 5
Para n = 4 se tiene:
Para n = 3 (3 ra apuesta)
Para n = 2
Para n = 1
Para x1=0
S1 s2 s3 s4
(5) (5)
(4) G (gana AP) G( gana AP)
G x3=1
(2) (2) P (x4=2)
(3) P(pierde AP)
X1=0 x2=2 (0) (1)
P (pierde AP)
Las políticas óptimas serían:
4 X*1 = 0 ? X*2 = 2
5 Si perde X*2 = 2 pierde apuesta
6 Si gana X*2 = 2 queda con 4……. X*3 = 1
7 Si gana X*3 = 1 gana la apuesta
8 Si pierde X*3 = 1 queda con 3…. X*4 = 2
9 Si gana X*4 = 2 gana apuesta.
10 Si pierde X*4 = 2 `pierde la apuesta.
para x1 = 2..
Este esquema se repite para las otras dos posibilidades.
PROBLEMA 3
Un apostador desea saber cómo debería distribuir su apuesta en un determinado juego para ganar $ 100.000 efectuando tres jugadas. El juego consiste en apostar unidades de $20.000 y se puede ganar o perder lo apostado, pero también se puede dar la posibilidad de empatar, es decir, se le devuelve el dinero apostado. El cree que la probabilidad de ganar es del 40%, la perder es de un 45% y la de empatar es del 15%. Si inicia el juego con $ 40.000.
¿Cómo debería apostar su dinero para obtener los $ 100.000 de ganancia, maximizando la probabilidad de cumplir su objetivo?
PROBLEMA 4
Un proyecto espacial del gobierno, lleva a cabo una investigación sobre cierto problema de ingeniería que debe resolverse antes de que seres humanos puedan viajar a salvo a Marte. Por el momento, cuatro equipos de investigación tratan de resolver el problema desde tres puntos de vista diferentes. Se estima que en las circunstancias actuales, la probabilidad de que los respectivos equipos – llámense 1, 2, 3 y 4 – fracasen es de 0,60, 0,40, 0,80 y 0,70 respectivamente. Así, la probabilidad actual de que los cuatro equipos fracasen es (0,6*0,4*0,8*0,7)= 0,1344. Como el objetivo es minimizar la probabilidad de fracaso, se asignarán al proyecto dos científicos más, de alto nivel.
La tabla siguiente da la probabilidad estimada, de que los equipos respectivos fracasen si se les asigna 0, 1, o 2 científicos para colaborar con ellos. Sólo se consideran números enteros de científicos puesto que cada uno de ellos deberá dedicar su atención completa a su equipo
¿ Cómo asignaría Ud. a los científicos adicionales de manera de minimizar la probabilidad de que los cuatro equipos fracasen?
PROBLEMA 5
Un apostador desea saber cómo debería distribuir su apuesta en cada jugada en un determinado juego para ganar $ 100.000 efectuando tres jugadas. El juego consiste en apostar unidades de $20.000 y se puede ganar o perder lo apostado, pero también existe la posibilidad de empatar, es decir, se le devuelve el dinero apostado. El cree que la probabilidad de ganar es de 3/8, la de perder es de 4/8 y la de empatar es de 1/8. Si inicia el juego con $ 40.000.
¿ Cómo debería apostar su dinero para obtener los $ 100.000 de ganancia, maximizando la probabilidad de cumplir con su objetivo.
PROBLEMA 6
Un apostador desea saber cómo debería distribuir su apuesta en un determinado juego para ganar $ 100.000 efectuando tres jugadas. El juego consiste en apostar cualquier número de unidades de $20.000 y se puede ganar o perder lo apostado. El cree que la probabilidad de ganar es del 40% y la de perder es de un 60%. Si inicia el juego con $ 40.000.
¿ Cómo debería apostar su dinero para obtener los $ 100.000 de ganancia, maximizando la probabilidad de cumplir con su objetivo.
PROBLEMA 7
Una persona tiene $ 2.000 disponibles para invertir y se le presentan dos oportunidades, A y B. Ambas oportunidades son riesgosas, la tabla siguiente muestra los posibles rendimientos anuales por cada $ 1.000 invertidos y las probabilidades de obtener estos rendimientos.
Determínese una estrategia de inversión para los próximos cuatro años que maximice las cantidades finales esperadas, si existe la restricción de que cada año se han de invertir unidades múltiplos $ 1.000.
PROBLEMA 8
Un apostador desea saber cómo debería distribuir su apuesta en un determinado juego para obtener $ 100.000 efectuando tres jugadas. El juego consiste en apostar unidades de $20.000 y se puede ganar o perder lo apostado, pero también se puede dar la posibilidad de empatar, es decir, se le devuelve el dinero apostado. El cree que la probabilidad de ganar es del 40%, la perder es de un 45% y la de empatar es del 15%. Si inicia el juego con $ 40.000.
¿ Cómo debería apostar su dinero para obtener los $ 100.000, maximizando la probabilidad de cumplir con su objetivo?
PROBLEMA 9
Un inversionista dispone de $ 3.000.000 para invertir en una oportunidad de negocios redituable a 1 año. La oportunidad es arriesgada en el sentido que la utilidad puede ser del: 40 %, 10% y -60% con probabilidades del 20 %, 30% y 50% respectivamente (estimadas con base a resultados pasados).
Determine una estrategia de inversión para los próximos tres años que le permita obtener una utilidad $ 2.500.000 maximizando la probabilidad de cumplir con el objetivo, las inversiones deben efectuarse en unidades enteras de $ 1.000.000.
PROBLEMA 10
Una compañía de computadoras tiene la capacidad de fabricar hasta cuatro computadoras cada semana. La demanda de computadoras es variable y se comporta según la siguiente distribución de probabilidades.
Los costos de producción son una función del número de computadoras fabricadas y se dan a continuación: (en miles de US$).
Las computadoras pueden entregarse a los clientes al concluir la semana de fabricación o pueden almacenarse para entrega futura, con un costo semanal de US$ 4.000 por computadora. Las órdenes que no se entregan durante la semana en que se efectúan, tienen un costo de US$ 2.000 por computadora y deben cubrirse tan pronto como sea posible durante la siguiente semana.
¿Cuántas computadoras deberá producir la compañía en la próximas tres semanas para minimizar el costo total esperado y cubrir la demanda, sí el inventario actual es cero?
Solución ejercicio 7:
Caso A. Unidad de inversión $ 1.000
Sea uj = unidades disponibles para la inversión en el estado j.
mj (uj) = cantidad máxima esperada al final del proceso, iniciado en la etapa j.
dj(uj) = Cantidad invertida en la etapa j que obtiene mj (uj).
Si se entra a la etapa j con uj unidades, entonces pueden invertirse x unidades (x= 0, 1, 2, . . ., uj ) dejando en reserva uj – x si la cantidad invertida se cuadriplica, habrá.
4x + (uj – x) = 3x + uj unidades disponibles para la siguiente etapa; si las unidades invertidas se pierden, entonces solamente estarán disponibles para la siguiente etapa las unidades de reserva de (uj – x). El mejor rendimiento a partir de este punto es de mj+1 (3x + uj ) o mj+1 (uj – x), siendo el valor esperado de este mejor rendimiento.
0,4*mj+1 (3x + uj ) + 0,6*mj+1 (uj – x)
La selección óptima para x es aquella que maximiza la expresión anterior:
(1)
La ecuación (1), fórmula de recursión para el proceso, se cumple para j = 1, 2, 3; también se cumple para j=4, bajo la condición final m5(u)=u. Es obvio que m5 es una función lineal creciente, también lo son m4, . . .,m1. Realizando la maximización (1), se obtiene.
m4(u4)=1,6u4, m3(u3)=1,6*1,6u3, m2(u2)=1,6*1,6*1,6u2, m1(u1)=1,6*1,6*1,6*1,6u1.
Con dj(uj)=4, 3, 2, 1. Entonces la cantidad óptima esperada es:
m1(2)=1,6*1,6*1,6*1,6*2=13,1072 unidades.
CASO B. Unidad de inversión $ 1.000
Sea uj = unidades disponibles para la inversión en el estado j.
mj (uj) = cantidad máxima esperada al final del proceso, iniciado en la etapa j.
dj(uj) = Cantidad invertida en la etapa j que obtiene mj (uj).
Si se entra a la etapa j con uj unidades, entonces pueden invertirse x unidades (x= 0, 1, 2, . . ., uj ) dejando en reserva uj – x si la cantidad invertida se triplica, habrá.
3x + (uj – x) = 2x + uj unidades disponibles para la siguiente etapa; si las unidades invertidas se duplican, entonces estarán disponibles para la siguiente etapa las siguientes unidades 2x + (uj – x) = uj + x. El mejor rendimiento a partir de este punto es de mj+1 (2x + uj ) o mj+1 (uj + x), siendo el valor esperado de este mejor rendimiento.
0,2*mj+1 (2x + uj ) + 0,8*mj+1 (uj + x)
La selección óptima para x es aquella que maximiza la expresión anterior:
(1)
La ecuación (1), fórmula de recursión para el proceso, se cumple para j = 1, 2, 3; también se cumple para j=4, bajo la condición final m5(u)=u. Es obvio que m5 es una función lineal creciente, también lo son m4, . . .,m1. Realizando la maximización (1), se obtiene.
m4(u4)=2,2u4, m3(u3)=2,2*2,2u3, m2(u2)=2,2*2,2*2,2u2, m1(u1)=2,2*2,2*2,2*2,2u1.
Con dj(uj)=4, 3, 2, 1. Entonces la cantidad óptima esperada es:
m1(2)=2,2*2,2*2,2*2,2*2=46,8512 unidades.
Luego, la mejor alternativa es considerar la oportunidad B.
Autor:
PabloTurmero