Programación dinamica
Páginas: 6 (1291 palabras)
Publicado: 17 de febrero de 2012
INSTITUTO TECNOLOGICO SUPERIOR DE CALKINI
EN EL ESTADO DE CAMPECHE
INGENIERIA INDUSTRIAL
MATERIA:
INVESTIGACIÓN DE OPERACIONES II
SÉPTIMO SEMESTRE
GRUPO: B
DOCENTE:
ING. RICARDO GOMÉZ KU
TRABAJO:
PROGRAMACIÓN DINAMICA DETERMINÍSTICA
PRESENTA:
ROSA LIZVIANEY POOT PECH 1744
CALIFICACION DE EXPOSICION
DE LA UNIDAD:
CALIFICACION DE LAINESTIGACION
DOCUMENTAL:
CALKINI CAMPECHE A DE 8 DE SEPTIEMBRE DEL 2010
Introducción
La Programación Dinámica Determinística es una técnica que se utiliza para resolver diversos problemas de optimización. 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 un serie deproblemas mas pequeños y manejables.
La programación dinámica determina la solución óptima de un problema de n variables descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PD es el principio deoptimalidad, un marco de referencia para descomponer el problema en etapas.
La programación dinámica es una técnica que se puede aplicar para resolver muchos problemas de optimización. La mayor parte de las veces, la programación dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en unaserie de problemas más pequeños y más tratables.
Desarrollo
Programación Dinámica Determinística
Aplicaciones de programación dinámica
Tres elementos básicos de un modelo de programación dinámica.
1.- Definición de las etapas.
2.- Definición de las alternativas.
3.- Definición de los estados para cada etapa.
Problema de lamochila/equipo de vuelo/carga del contenedor.
El modelo clásico de la mochila tiene que ver con el caso de un soldado (o un montañista) que debe decidir cuales son los artículos más valiosos que debe llevar en su mochila. Este problema parafrasea un modelo general de asignación de recursos en el que un solo recurso limitado se asigna a varias alternativas (por ejemplo, fondos limitados asignadosa proyectos) con objeto de maximizar el ingreso total.
Al problema de la mochila también se le llama problema de conjunto de fuga o equipo de vuelo, en el que un piloto de avión a reacción debe determinar los artículos más valiosos (de emergencia) que debe llevar a bordo.
Y problema de carga de flete o del contenedor, en el que un barco con capacidad limitada de volumen opeso se carga con los fletes más valiosos.
Parece que estos tres nombres se acuñaron en las tres ramas de las fuerzas armadas estadounidenses:
La fuerza aérea, el ejército y la marina.
La ecuación recursiva (en reversa) se desarrolla para el problema general de una mochila de:
W libras, con n artículos.
Sea:
[pic] : La cantidad de unidades del artículo i en lamochila.
[pic] : El ingreso por unidad del articulo i.
[pic]: El peso por unidad del articulo i.
El problema general se representa con el siguiente programa lineal entero:
[pic]
Sujeto a:
[pic]
Los tres elementos del modelo son:
1.- La etapa i se presenta con el articulo i, i =1, 2,…, n.
2.- Las alternativas en la etapa i se presentan por [pic] la cantidad de unidades delartículo i que entran en la mochila. El ingreso correspondiente es [pic]
Si se define [pic] como el máximo entero menor o igual a [pic]se ve que [pic]
3.- El estado en la etapa i se presenta por [pic] el peso total asignado a las etapas (artículos) i, i+1,…, y n. Esta definición refleja el que la restricción del peso es la única que vincula entre sí a toda la n etapas.
Definiremos a:...
EN EL ESTADO DE CAMPECHE
INGENIERIA INDUSTRIAL
MATERIA:
INVESTIGACIÓN DE OPERACIONES II
SÉPTIMO SEMESTRE
GRUPO: B
DOCENTE:
ING. RICARDO GOMÉZ KU
TRABAJO:
PROGRAMACIÓN DINAMICA DETERMINÍSTICA
PRESENTA:
ROSA LIZVIANEY POOT PECH 1744
CALIFICACION DE EXPOSICION
DE LA UNIDAD:
CALIFICACION DE LAINESTIGACION
DOCUMENTAL:
CALKINI CAMPECHE A DE 8 DE SEPTIEMBRE DEL 2010
Introducción
La Programación Dinámica Determinística es una técnica que se utiliza para resolver diversos problemas de optimización. 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 un serie deproblemas mas pequeños y manejables.
La programación dinámica determina la solución óptima de un problema de n variables descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La ventaja en el aspecto de los cálculos es que optimizaremos una sola variable, en vez de subproblemas de n variables. La principal contribución de la PD es el principio deoptimalidad, un marco de referencia para descomponer el problema en etapas.
La programación dinámica es una técnica que se puede aplicar para resolver muchos problemas de optimización. La mayor parte de las veces, la programación dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en unaserie de problemas más pequeños y más tratables.
Desarrollo
Programación Dinámica Determinística
Aplicaciones de programación dinámica
Tres elementos básicos de un modelo de programación dinámica.
1.- Definición de las etapas.
2.- Definición de las alternativas.
3.- Definición de los estados para cada etapa.
Problema de lamochila/equipo de vuelo/carga del contenedor.
El modelo clásico de la mochila tiene que ver con el caso de un soldado (o un montañista) que debe decidir cuales son los artículos más valiosos que debe llevar en su mochila. Este problema parafrasea un modelo general de asignación de recursos en el que un solo recurso limitado se asigna a varias alternativas (por ejemplo, fondos limitados asignadosa proyectos) con objeto de maximizar el ingreso total.
Al problema de la mochila también se le llama problema de conjunto de fuga o equipo de vuelo, en el que un piloto de avión a reacción debe determinar los artículos más valiosos (de emergencia) que debe llevar a bordo.
Y problema de carga de flete o del contenedor, en el que un barco con capacidad limitada de volumen opeso se carga con los fletes más valiosos.
Parece que estos tres nombres se acuñaron en las tres ramas de las fuerzas armadas estadounidenses:
La fuerza aérea, el ejército y la marina.
La ecuación recursiva (en reversa) se desarrolla para el problema general de una mochila de:
W libras, con n artículos.
Sea:
[pic] : La cantidad de unidades del artículo i en lamochila.
[pic] : El ingreso por unidad del articulo i.
[pic]: El peso por unidad del articulo i.
El problema general se representa con el siguiente programa lineal entero:
[pic]
Sujeto a:
[pic]
Los tres elementos del modelo son:
1.- La etapa i se presenta con el articulo i, i =1, 2,…, n.
2.- Las alternativas en la etapa i se presentan por [pic] la cantidad de unidades delartículo i que entran en la mochila. El ingreso correspondiente es [pic]
Si se define [pic] como el máximo entero menor o igual a [pic]se ve que [pic]
3.- El estado en la etapa i se presenta por [pic] el peso total asignado a las etapas (artículos) i, i+1,…, y n. Esta definición refleja el que la restricción del peso es la única que vincula entre sí a toda la n etapas.
Definiremos a:...
Leer documento completo
Regístrate para leer el documento completo.