La Programacin DinmicaEn informtica, la programacin dinmica es un mtodo para reducir el tiempo de ejecucin de un algoritmo mediante la utilizacin de subproblemas superpuestos y subestructuras ptimas, como se describe a continuacin. El matemtico Richard Bellman invent la programacin dinmica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados. Programacin Dinmica nos puede ofrecer una solucin aceptable. La eficiencia de esta tcnica consiste en resolver los subproblemas una sola vez, guardando sus soluciones en una tabla para su futura utilizacin. La Programacin Dinmica no slo tiene sentido aplicarla por razones de eficiencia, sino porque adems presenta un mtodo capaz de resolver de manera eficiente problemas cuya solucin ha sido abordada por otras tcnicas y ha fracasado.

Identificacin de los elementos de la P.D.Para resolver un problema de programacin dinmica debemos al menos cumplir con:Identificacin de etapas, estados y variable de decisin: Cada etapa debe tener asociado una o ms decisiones (problema de optimizacin), cuya dependencia de las decisiones anteriores est dada exclusivamente por las variables de estado. Cada estado debe contener toda la informacin relevante para la toma de decisin asociada al perodo. Las variables de decisin son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la prxima etapa.

Definicin de Ecuaciones RecursivasEcuaciones de Recurrencia Las relaciones de recurrencia pueden considerarse como tcnicas avanzadas de conteo. Resuelven problemas cuya solucin no puede obtenerse usando variaciones, permutaciones, combinaciones, etc. Para introducir la teora de las relaciones de recurrencia tomemos la conocida sucesin de Fibonacci, donde cada trmino, a partir del tercero, se obtiene sumando los dos anteriores, esto es: f n =f n-1 +f n+2 si n3 Una expresin de este tipo, en la que el trmino general de la sucesin se escribe en funcin de algunos otros trminos anteriores, recibe los nombres de relacin de recurrencia, ecuacin de recurrencia o ecuacin de diferencias.

Definicin de los Elementos que conforman una Ecuacin RecursivaUn problema que pueda ser definido en funcin de su tamao, sea este N, pueda ser dividido en instancias ms pequeas (< N) del mismo problema y se conozca la solucin explcita a las instancias ms simples, lo que se conoce como casos base, se puede aplicar induccin sobre las llamadas ms pequeas y suponer que estas quedan resueltas.Para que se entienda mejor a continuacin se exponen algunos ejemplos:Factorial: Se desea calcular n! \, (el factorial de n \,, que se define como el producto de todos los enteros positivos de 1 \, a n \,). Se puede definir el problema de forma recurrente como n(n-1)! \,; como (n-1)! \, es menor que n! \, podemos aplicar induccin por lo que disponemos del resultado. El caso base es 0! \, que es 1 \,.Algoritmo de ordenacin por fusin: Sea v un vector de n elementos, podemos separar el vector en dos mitades. Estas dos mitades tienen tamao n/2 por lo que por induccin podemos aplicar la ordenacin en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de cero o un elemento, que est trivialmente ordenado y no hay que hacer nada.

PROGRAMACIN DINMICA DETERMINSTICA En este caso se profundiza sobre el enfoque de programacin dinmica en los problemas determinsticos, en donde el estado en la siguiente etapa est completamente determinado por el estado y la poltica de decisin de la etapa actual. El caso probabilstico en el que existe una distribucin de probabilidad para el valor posible del siguiente estado este se analizara ms adelante.

PROGRAMACION DINAMICA PROBABILISTICA

La programacin dinmica probabilstica difiere de la programacin dinmica determinstica en que el estado de la etapa siguiente no queda completamente determinado por el estado y la decisin de la poltica en el estado actual. En lugar de ello existe una distribucin de probabilidad para lo que ser el estado siguiente. Sin embargo, esta distribucin de probabilidad todava est completamente determinada por el estado y la decisin de la poltica del estado actual. En la siguiente figura se describe diagramticamente la estructura bsica que resulta para la programacin dinmica probabilstica, en donde N denota el nmero de estados posibles en la etapa n+1.

Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe el nombre de rbol de decisin. Si el rbol de decisin no es demasiado grande, proporciona una manera til de resumir las diversas posibilidades que pueden ocurrir.

Problemas de demandas de Inventarios

Un inventario es un recurso inempleado pero til que posee valor econmico. El problema se plantea cuando una empresa expendedora o productora de bienes y servicios no produce en un momento determinado la cantidad suficiente para satisfacer la demanda, por lo que debe realizar un almacenamiento protector contra posibles inexistencias. El objetivo estriba en definir el nivel de inventario. Estas decisiones consisten en dar normas que nos precisen en que instante se deben efectuar los pedidos del producto considerado y la cantidad que se debe pedir. En trminos generales un inventario es un conjunto de recursos tiles que se encuentran ociosos en algn momento. El objetivo de los problemas de inventario es minimizar los costes (totales o esperados) del sistema sujetos a la restriccin de satisfacer la demanda (conocida o aleatoria). Entre los diferentes costes que puede haber en un problema de inventario estn: 1.- Costes de fabricacin. 2.- Costes de mantenimiento o almacenamiento. 3.- Costes de penalizacin o rotura por no satisfacer la demanda. 4.- Rendimientos o ingresos. (Puede o no incluirse en el modelo). 5.- Costes de recuperacin o salvamento. (El valor de recuperacin representa el valor de desecho del artculo para la empresa, quiz a travs de una venta con descuento). 6.- Tasa de descuento. La tasa de descuento toma en cuenta el valor del dinero en el tiempo. Cuando una empresa compromete capital en inventarios, no puede usar este dinero para otros fines. El problema bsico es determinar cunto y cundo hay que producir. Los problemas de inventarios suelen clasificarse en: - Determinsticos: demanda fija. - Aleatorios: demanda es una variable aleatoria con distribucin conocida. Otra clasificacin tiene en cuenta la forma de revisin del inventario: - Modelos de revisin continua: se hacen pedidos cuando el inventario baja de cierto lmite. - Modelos de revisin peridica: si los pedidos se hacen a intervalos de tiempo discretos.

Identificacin de Problema de DecisinEn teora de la computacin, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes tambin de longitud finita. Un problema de decisin es un problema en donde las respuestas posibles son s o no. Un ejemplo tpico de problema de decisin es la pregunta: Es un nmero entero dado primo? Una instancia de este problema sera: Es 17 primo?

Un problema de decisin tambin se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, tambin llamado lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los nmeros primos se puede ver tambin como el lenguaje de todas las frases en el alfabeto {0, 1,..., 9} tales que el entero correspondiente es primo.

Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible. Cuando existe un algoritmo que puede responder positivamente cuando la frase est en el lenguaje, pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible. En Teora de la computabilidad, se estudia qu lenguajes son decidibles con diferentes tipos de mquinas. En teora de la complejidad computacional se estudia cuntos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, nmero de procesadores, tipo de mquina, etc.).

Desarrollo de problemas de inventarioUn inventario es un recurso empleado pero til que posee valor econmico. El problema se plantea cuando una empresa expendedora o productora de bienes y servicios no produce en un momento determinado la cantidad suficiente para satisfacer la demanda, por lo que debe realizar un almacenamiento protector contra posibles inexistencias.

El objetivo radica en definir el nivel de inventario. Estas decisiones consisten en dar normas que nos precisen en que instante se deben efectuar los pedidos del producto considerado y la cantidad que se debe pedir.

En trminos generales un inventario es un conjunto de recursos tiles que se encuentran ociosos en algn momento. El objetivo de los problemas de inventario es minimizar los costes (totales o esperados) del sistema sujetos a la restriccin de satisfacer la demanda (conocida o aleatoria). Entre los diferentes costes que puede haber en un problema de inventario estn:

1.- Costes de fabricacin.2.- Costes de mantenimiento o almacenamiento.3.- Costes de penalizacin o rotura por no satisfacer la demanda.4.- Rendimientos o ingresos. (Puede o no incluirse en el modelo).5.- Costes de recuperacin o salvamento. (El valor de recuperacin representa el valor de desecho del artculo para la empresa, quiz a travs de una venta con descuento).6.- Tasa de descuento. La tasa de descuento toma en cuenta el valor del dinero en el tiempo. Cuando una empresa compromete capital en inventarios, no puede usar este dinero para otros fines. Referencia: Investigacin de operaciones HANDY TAHA

REPUBLICA BOLIVARIANA DE VENEZUELAMINISTERIO DEL PODER POPULAR PARA LA EDUCACION SUPERIORINSTITUTO UNIVERSITARIO POLITECNICO SANTIAGO MARIOBARINAS EXTENSION BARINAS

INVESTIGACION DE OPERACIONES II

PROFESOR: ALUMNOS:JOSE LUQUECOIRAN MARIA GRMAN DOUGLAS 24.013.604

INVESTIGACION DE OPERACIONES II SECCION (S6)INTRODUCCION

La Programacin Dinmica est comprendida dentro de un conjunto de tcnicas matemticas que a su vez forman parte de un rea ms amplia, conocida como Investigacin de Operaciones. Esta ltima puede definirse como una ciencia interdisciplinaria que tiene por objeto la bsqueda de estrategias que permitan obtener resultados ptimos en el desarrollo de actividades por parte de sistemas hombre-mquina (estos sistemas pueden estar formados exclusivamente por hombres, por mquinas o por una combinacin de los dos).Son caractersticas esenciales de la P.D. por un lado, la versatilidad con respecto a la amplia gama de problemas que puede atacar y, por otra parte, que la P.D. se limita a aportar un esquema de solucin (ya mencionado arriba) dejando al ingenio de quien resuelva el problema la construccin del modelo matemtico para realizar la optimizacin de cada caso en particular. En este sentido el trabajo en P.D. est ms en relacin directa con la labor del matemtico que del ingeniero, pues este ltimo no necesita comprender la base terica en la cual descansa el procedimiento, sino nicamente conocer el algoritmo propio del problema particular que pretende resolver

CONCLUSIONProgramacin Dinmica nos puede ofrecer una solucin aceptable. La eficiencia de esta tcnica consiste en resolver los subproblemas una sola vez, guardando sus soluciones en una tabla para su futura utilizacin. La Programacin Dinmica no slo tiene sentido aplicarla por razones de eficiencia, sino porque adems presenta un mtodo capaz de resolver de manera eficiente problemas cuya solucin ha sido abordada por otras tcnicas y ha fracasado. El objetivo es ms presentar la potencia de la P.D. que proponerla como la panacea de los mtodos de Investigacin de Operaciones, pues tambin se ver que aunque funciona, en ocasiones la tcnica puede resultar imprctica al momento de resolver problemas de cierta envergadura.