132934728 21324275 S1 A Programacion Dinamica Deterministica

S1 – Programación Dinámica
Determinista
Ing. en Sistemas Computacionales
Modelos Probabilísticos
Paul Ramírez De la Cruz
23 ene 2007

Contenido




Introducción
Ejemplo prototipo
Referencias

23ene2007

Programación Dinámica Determinista

2

Introducción









La investigación de operaciones es un área de las
matemáticas surgida durante la Segunda Guerra Mundial
La investigación deoperaciones se refiere al diseño y
aplicación de modelos matemáticos con el fin de obtener la
mejor solución posible a un problema, dadas ciertas
limitaciones de recursos
La programación dinámica es un método de investigación de
operaciones que permite resolver un problema de n variables
dividiéndolo en n problemas de una variable cada uno
La solución particular de cada etapa depende del contexto,por lo que no hay un modelo general para programación
dinámica
La solución óptima de cada etapa se utiliza como variable de
entrada de la etapa siguiente

23ene2007

Programación Dinámica Determinista

3

Ejemplo prototipo




Supongamos que una
corporación tiene un
presupuesto de $5
millones para hacer
ampliaciones en tres
de sus plantas
Cada
planta
tiene
varias propuestas de
inversión, juntocon su
costo de expansión (c)
y el retorno (beneficio)
total esperado (r)

23ene2007

Planta 1

Planta 2

Planta 3

Propuesta

c1

r1

c2

r2

c3

r3

1

0

0

0

0

0

0

2

1

5

2

8

1

4

3

2

6

3

9

-

-

4

-

-

4

12

-

-

 

Programación Dinámica Determinista

4

Ejemplo prototipo






Supongamos que a cada planta se le permitirá
realizar una de sus propuestas
El objetivo esmaximizar el beneficio de la
compañía al invertir los $5 millones por completo
Una forma poco eficiente de realizar la selección de
la propuesta adecuada para cada planta es realizar
un análisis exhaustivo
En esta situación, habrá 3(4)(2) = 24
combinaciones posibles



23ene2007

Algunas no son factibles, por ejemplo: (3,3,2) requiere de
una inversión de $6 millones
Otras son factibles, pero conun beneficio bajo, por
ejemplo: (1,1,2) produce un retorno de sólo $4 millones
Programación Dinámica Determinista

5

Ejemplo prototipo


Otras dificultades que enfrentar:






23ene2007

Si se tiene un problema con muchas más
opciones, el análisis exhaustivo se hace aún
más ineficiente
La información obtenida de combinaciones
examinadas previamente no se utiliza para
eliminar nuevascombinaciones que sean
peores o infactibles
El problema no se puede formular como
programación lineal, porque el beneficio
obtenido no es una función lineal de la inversión
Programación Dinámica Determinista

6

Planteamiento


Dividamos el problema en tres etapas, cada una de las cuales
representa el dinero que se asigna a una sola planta







Etapa 1: Dinero asignado a la planta 1
Etapa 2:Dinero asignado a las plantas 1 y 2
Etapa 3: Dinero asignado a las plantas 1, 2 y 3
En este caso la numeración de las etapas es arbitraria

Observemos que cada etapa tiene un conjunto de estados
que puede asumir:




23ene2007

{0,1,2,3,4,5}: La cantidad de dinero gastada en la planta 1, x1
{0,1,2,3,4,5}: La cantidad de dinero gastada en las plantas 1 y 2,
x2
{5}: La cantidad de dinero gastada enlas plantas 1, 2 y 3
(porque se debe gastar todo), x3

Programación Dinámica Determinista

7

Planteamiento





Notemos que a diferencia de la
programación lineal, aquí las xi, son una
representación de los posibles estados de
cada etapa
Cada estado tiene asociado un beneficio
Observemos también que a fin de tomar una
decisión en la tercera etapa, sólo
requerimos conocer cuánto se gastó enlas
dos etapas previas y no cómo se gastó

23ene2007

Programación Dinámica Determinista

8

Planteamiento



Determinemos el beneficio
asociado con cada estado
Comenzando con la primera
planta:






23ene2007

Si el capital disponible, x1, es
de
cero,
entonces
la
propuesta que maximiza el
beneficio para dicho capital es
la propuesta uno, y el
beneficio en la etapa uno será
de cero
Si el...