Programacion dinamica determinista

INSTITUTO TECNOLOGICO SUPERIOR PURHEPECHA
EDUCACION A DISTANCIA
INGENIERIA INDUSTRIAL
QUINTO SEMESTRE
INVESTIGACION DE OPERACIONES II
UNIDAD -1
PROGRAMACION DINAMICA
ACTIVIDAD -1
CUADRO SINOPTICO

PROFESOR: CRISEIDA RUIZ AGUILAR
ALUMNO: ROGELI0 BAUTISTA ORTIZ
MATRICULA: 101121

09 DE SEPTIEMBRE DEL 2012 URUAPAN MICHOACAN

Ejemplos de modelo deprogramación dinámica
Ejemplos de modelo de programación dinámica
1.-Naturaleza secuencial de las decisiones: el problema puede ser dividido en etapas
2.-cada etapa tiene un número de etapas de estados asociados a ella
3.-la decisión óptima de cada etapa depende solo del estado actual y no de las decisiones anteriores
4.- la decisión tomada de una etapa determinada cual será el estado dela etapa siguiente

1.-Naturaleza secuencial de las decisiones: el problema puede ser dividido en etapas
2.-cada etapa tiene un número de etapas de estados asociados a ella
3.-la decisión óptima de cada etapa depende solo del estado actual y no de las decisiones anteriores
4.- la decisión tomada de una etapa determinada cual será el estado de la etapa siguiente

Características de losproblemas de programación dinámica
Características de los problemas de programación dinámica
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro(denominadas estados), y a las decisiones que se plantearán en el futuro.

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a lasdecisiones que se plantearán en el futuro.

PROGRAMACION DINAMICA
PROGRAMACION DINAMICA


Existen tres modelos diferentes manejados por WINQSB.
* Problema de la diligencia (Stagecoach Problem)
* Problema de la mochila (Snapsack Problem)
* programación de producción e inventarios (Production and Inventory Scheduling)
EL PROBLEMA DE LA DILIGENCIA
Ejemplo-- 1:
Considérese el gráficoque contempla las rutas posibles para ir desde la ciudad 1 hasta la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial disponible. La tabla recoge el costo asociado al desplazamiento entre cada par de nodos para cada una de las etapas. Supondremos que todos los desplazamientos tienen la misma duración, y que el viaje ha de realizarse en cuatro etapas. Cada una de ellasse corresponde con un único desplazamiento entre un par de nodos del grafo, así al finalizar la primera etapa estaremos en una de las ciudades 2, 3 ó 4. La segunda etapa finalizará en la ciudad 5, la número 6 ó la número7. La tercera jornada nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el viaje en la ciudad 10.
El problema contiene 10 nodos claramenteidentificados:
Al pulsar OK podremos ingresar el resto de información, el cual se basa en las relaciones existentes entre los nodos:
Los valores van de acuerdo a la red establecida en el problema:
Para resolver el problema pulsamos la opción Resolver el problema (Solve the Problem) del menú Resolver y analizar (Solve and Analyze).
La ventana siguiente permite identificar los nodos de inicio y fin:Al pulsar SOLVE generamos la solución al problema:
Si queremos una solución detallada debemos pulsar sobre Mostrar solución detallada (Show Solution Detail) en el menú Resultados (Results):

2.- PROBLEMA DE LA MOCHILA O CANASTA DE EQUIPAJE
La idea básica es que existen N tipos distintos de artículos que pueden cargarse en una mochila; cada artículo tiene asociados un peso y un valor. El...