Visita Tecnica

ÍNDICE DEL INFORME

INTRODUCCIÓN………………………………..……………………… 2

OBJETIVOS…………………………………………………………..... 2

FUNDAMENTO TEÓRICO……………...……………………………. 3

APLICACIONES PRÁCTICAS………………………………………. 7

CONCLUSIONES……………………………………………………... 11

REFERENCIAS BIBLIOGRÁFICAS……………………………….. 12

ANEXO………………………………………………………………………….. 13

INTRODUCCIÓN

La programación dinámica es un método de optimización de extraordinaria versatilidad. Si bien fue desarrollada especialmente para la resolución de problemas en procesos de decisión en múltiples pasos, diferentes investigaciones han mostrado que las mismas ideas pueden utilizarse en otro tipo de problemas de matemática aplicada, e incluso pueden ser útiles en el planteo de algunas cuestiones teóricas. Habiendo surgido en los inicios de la época de las computadoras, La Programación Dinámica fue, además, concebida con un ojo puesto en esta potente herramienta. La ecuación funcional que se obtiene para cada problema, a través del uso del principio de optimalidad de Bellman permite, con mayor o menor esfuerzo dependiendo del caso, establecer una recurrencia que es, en sí misma, un algoritmo que resuelve el problema en cuestión.

El objetivo de esta monografía es brindar un panorama relativamente amplio de las aplicaciones de la Programación Dinámica, de manera que resulte accesible para cualquier estudiantes de la especialidad de ingeniería Industrial, incluso para aquellos que no estén familiarizados con las áreas específicas de dichas aplicaciones. Persiguiendo este fin, procuramos, en la medida en que el espacio lo permite, exponer todos los pasos de cada razonamiento y los elementos teóricos básicos para su comprensión. Teniendo en cuenta que el presente trabajo abarcará la utilización de la programación dinámica en los casos reales.

OBJETIVOS

Conocer y entender los fundamentos teóricos y su contraste con las aplicaciones reales

Realizar propuestas de mejora para aumentar la productividad de alguna empresa.

FUNDAMENTO TEÓRICO

La programación dinámica 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 inimaginable 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.

A continuación se mostrara como trabajar hacia atrás para hacer de un problema aparentemente difícil uno casi trivial.

Ejemplo: (acertijo de las cerillas)

Supongamos que hay 30 cerillas sobre una mesa. Yo empiezo eligiendo 1,2 ò 3 cerillas. Luego mi contrincante debe tomar 1, 2 ò 3. Así continuamos hasta que alguno de los jugadores toma la última cerilla. Este jugador pierde. ¿Cómo puedo yo (el primer jugador) estar seguro de ganar el juego?

Solución:

Si puedo tener la certeza que le tocará el turno a mi oponente cuando quede una cerilla, claro que ganaré. Al regresar un paso hacia atrás, si yo puedo tener la seguridad de que le tocara su turno a mi contrario cuando queden 5 cerillas, yo puedo estar seguro de que cuando le toque el siguiente turno solo le quedara una cerilla. Por ejemplo, suponga que el turno de mi contrincante es cuando quedan 5 cerillas. Si mi contrario toma 2 cerillas, yo elegiré 2 y le dejare una cerilla, con lo que aseguro mi victoria. De manera similar, si soy capaz de obligar a mi contrincante a jugar cuando quedan 5, 9, 13, 17, 21, 25, ò 29 cerillas, tengo la victoria asegurada. Por lo tanto, no puedo perder si tomo 30- 29 = 1 la primera vez que me toque jugar. Luego simplemente me aseguro que mi contrario siempre se quede con 29, 25, 21, 17, 13, 9, ò 5 cerillas cuando le toque jugar.

Obsérvese que hemos resuelto este acertijo al ir hacia atrás desde el final hacia el principio del problema.

Otro ejemplo: (tazas de leche)

Tengo una taza de 9 onzas y otra de 4 onzas. Mi madre me pidió traer a casa exactamente 6 onzas de leche. ¿Cómo puedo cumplir lo pedido?

Solución:

Al empezar cerca del final del problema, me doy cuenta sagazmente de que el problema se puede resolver si soy capaz de poner de alguna manera una onza de leche en la tasa de 4 onzas. Luego lleno la tasa de 9 onzas y vierto 3 onzas de la leche de la tasa de 9 onzas en la taza parcialmente llena de 4 onzas. En este momento me quedo con 6 onzas de leche.

La solución del problema se podría describir como en la tabla anterior (la situación inicial se escribe al último, y la final se escribe primero).

LA PROGRAMACIÓN DINÁMICA

La programación dinámica se suele utilizar en problemas de optimización, donde una solución está formada por una serie de decisiones.

Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para subproblemas más pequeños.

Sin embargo, la programación dinámica no utiliza la recursividad, sino que almacena los resultados de los subproblemas en una tabla, calculando primero las soluciones para los problemas pequeños.

Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.

La Programación Dinámica intentar mejorar la eficiencia de cálculo de problemas descomponiéndolos en subproblemas de menor tamaño, más fáciles de resolver.

La Programación Dinámica está basada en el principio de Optimalidad de Bellman: “Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema, también debe ser óptima respecto al subproblema resuelto”.

La Programación Dinámica resuelve el problema en etapas (problemas multietápicos).

En cada etapa interviene una variable de optimización.

Los cálculos de las diferentes etapas se enlazan en forma recursiva para generar la solución óptima.

La Programación Dinámica se aplica en los problemas como calendarización (Scheduling), edición de cadenas, almacenamiento e inventarios.

...