Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

UNIDAD 1: PROGRAMACION DINAMICA

No description
by

Luis Marquez

on 18 February 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of UNIDAD 1: PROGRAMACION DINAMICA

Debe enfatizarse un ultimo punto cuando se formula un problema de programación dinámica. No importa cuales hayan sido los estados y las decisiones iniciales, las decisiones finales constituirán una política óptima.
1.2 Ejemplo de Modelos de programación Dinámica
Un repartidor de la tortillería “El Grano de Oro desea saber a que tiendas debe visitar para que su ruta sea la mas corta en distancia posible. En su viaje lleva 6 hieleras de tortillas y en cada tienda deja 2 hileras. Como restricción siempre debe visitar la tienda “J” así que debe seleccionar 2 tiendas de 8 posibles para en total visitar 3 tiendas. ¿Qué tiendas debe visitar para que su recorrido sea el más corto?
A continuación se muestra las diferentes rutas posibles con sus distancias en metros:

1.3 Programación Dinámica Determinista
Para ilustrar la naturaleza esencial de la programación dinámica deben establecerse varios conceptos básicos, es decir, los requisitos, para la formulación de un problema de programación dinámica.
En la formulación de un problema de programación dinámica esta incluido el concepto de las
decisiones
o
variables de decisión
, las cuales son oportunidades para cambiar las variables de estado (posiblemente en una forma probabilística).
1.1 Características de los problemas de programación dinámica
Esta técnica se llama programación dinámica, es una extensión de la técnica básica de programación lineal. Fue creada por Richard Bellman y G. B. Dantzig.

Se basa en el “principio de optimalidad”, el cual establece que una política optima está formada por subpoliticas optimas. Puede definirse como una técnica matemática que da la solución a una serie de decisiones secuenciales, cada una de las cuales afecta a las decisiones futuras.
UNIDAD 1:
programación dinámica

El primer concepto es una
"variable de estado"
, cuyo valor especifica la condición del proceso. Aunque el numero de variables de estado puede ser grande, la dificultad para resolver un problema aumenta considerablemente al incrementarse el numero de estas variables, por lo cual es ventajoso minimizar su numero.
El ultimo concepto para formular un problema de programación dinámica es la habilidad para tomar decisiones acerca del problema en las diversas
etapas
o puntos en el tiempo
En este tipo de programación dinámica, el estado de la siguiente etapa Está determinado por completo por el estado y la política de decisión de la etapa actual . El caso probabilístico es en el cual existe una distribución de probabilidad del valor posible del siguiente estado. Se analizará posteriormente
Requerimientos para la formulación de problemas
Equipo 2:
Cinthia Ortega
Brando Alvidrez
Manuel Gomez
Luis Marquez

En cada etapa del problema, se toma una decisión para cambiar el estado y con ello maximizar la ganancia.
Esta técnica llega a la solución trabajando hacia atrás partiendo del final del problema hacia el principio, por lo que un problema enorme e inmanejable se convierte en una serie de problemas más pequeños y manejables.

La idea de trabajar hacia atrás se introduce mediante la resolución de acertijos conocidos, luego se muestra cómo la programación dinámica es útil para solucionar redes, inventarios y problemas de asignación de recursos.

Ejemplo 2
Elementos de un Problema de Programación Dinámica
ETAPA
( n ) Es el período de tiempo, lugar, fase o situación en donde se produce un cambio debido a una decisión .
ESTADO
Muestra la situación actual del sistema cuando nos encontramos en la etapa n .
. También se puede decir que por estado se quiere dar a entender la información que se necesita en cualquier etapa para tomar una decisión óptima.

Variables de Decisión
Hacen referencia a toma de decisiones (o política de decisión)que se producen en una etapa y que produce un cambio en el estado actual del sistema.
Función Recurrente
Refleja el comportamiento del sistema en función de los estados y de las variables de decisión:
La recursión relaciona el costo o la contribución ganada durante alguna etapa con el costo o la contribución ganada en la etapa posterior de forma acumulativa

1.4 Programación Dinámica Probabilista
La programación dinámica probabilística difiere de la determinística en que los estados y los retornos o retribuciones en cada etapa son probabilísticos. La programación dinámica probabilística se origina en especial en el tratamiento de modelos estocásticos de inventario.
Modelos Probabilisticos de Inventarios
En estos modelos la demanda se describe mediante una distribución de probabilidades.

Se considera a un Modelo Estocástico cuando algunas variables están en función a un modelo de probabilidad de que el evento se lleve a cabo.

Existen dos modelos de control de inventarios estocásticos los cuales son:

1. Punto de reorden (cantidad fija, tiempo variable).
2. Revisión periódica (tiempo fijo, cantidad variable).

Modelo Probabilístico de cantidad de ordenar fija ciclo variable (punto de reorden).
Este método consiste en una estimación de la demanda, con lo cual se determina una cantidad de reabastecimiento para el próximo periodo, así como el momento en que debe realizarse el pedido en función a una cantidad fija.
Modelo Probabilístico de cantidad de ordenar variable, ciclo fijo
(Revisión periódica)
En este sistema los ciclos de abastecimiento están controlados por periodos preestablecidos.
El sistema de tiempo fijo y cantidades variables se aplica cuando la incertidumbre de las fluctuaciones, debidas a causas internas y externas, no permite establecer un patrón de cantidades de reorden uniformes.

1.5 Uso de Programas de Computación
Solver es una herramienta de análisis que tienes en el programa Excel, aplicado sobre todo en el mundo empresarial, que permite calcular el valor de una celda que depende de diversos factores o variables donde a la vez existen una serie de restricciones que han de cumplirse.

Más detenidamente lo que la herramienta Solver de Excel realiza son los cálculos para la resolución de problemas de programación lineal, en donde a partir de una función lineal a optimizar (encontrar el máximo o mínimo) y cuyas variables están sujetas a unas restricciones expresadas como inecuaciones lineales, el fin es obtener valores óptimos bien sean máximos o mínimos.

Fuentes de Consulta
Introducción a la investigación de operaciones – Robert J. Thierauf
Investigación de Operaciones (Aplicaciones y Algoritmos)
-Handy A. Taha. Investigación de Operaciones. Ed. Pearson, 7ª Edición.
Full transcript