Programación dinámica_Componentes de Sistema

Problemas Programación Dinámica_Taha

El problema de programación de la producción de un producto las 3 semanas siguientes. El costo unitario de producción es de $100 para las 2 primeras semanas y $150 para las dos últimas. Las demás semanas son 5,3 y 8 unidades respectivamente y tienen que ser satisfechas. Las plantas pueden producir un máximo de 7 semanales. Además, se pueden emplear horas extras durante 2 últimas semanas, esto incrementa la producción en 2 unidades por semana, pero el costo de producción sube en $20 por unidad extra. El exceso de producción se puede almacenar a un costo unitario de $3 por semana. Si al inicio se tiene 1 unidad de inventario y se desea tener al final 2 unidades ¿Cuál debe ser el plan de producción?

Problemas de Programación Dinámica Determinística

Problema 1:  Cierto estudiante desea destinar los siete días de la semana próxima a estudiar cuatro cursos. Necesita al menos un día para cada curso y el puntaje que puede lograr se da en la siguiente tabla:

Días de estudio	Curso 1	Curso 2	Curso 3	Curso 4
1	13	15	12	16
2	15	15	12	16
3	16	16	17	19
4	17	19	18	19

¿Cuántos días debe estudiar cada curso para lograr un puntaje?

Richard Bellman y la Programación Dinámica

Richard Ernest Bellman (1920 - 1984) fue un matemático aplicado, célebre por su invención de la programación dinámica en 1953, y sus importantes contribuciones en otros campos de las matemáticas.

Biografía

Bellman nació en 1920 en Nueva York, donde su padre John James Bellman tenía una tienda de abarrotes en Bergen Street, cerca de Prospect Park en Brooklyn. Bellman completó sus estudios en la Abraham Lincoln High School en 1937, y estudió matemáticas en el Brooklyn College, donde obtuvo su licenciatura en 1941. Más tarde obtuvo una maestría de la Universidad de Wisconsin-Madison. Durante la Segunda Guerra Mundial trabajó para un grupo de Física Teórica de la División de Los Álamos. En 1946 recibió su doctorado en Filosofía (Ph.D.) de Princeton bajo la supervisión de Salomón Lefschetz. A partir de 1949 Bellman trabajado durante muchos años en la corporación RAND y fue durante este tiempo que él desarrolló de programación dinámica.

Fue profesor en la Universidad del Sur de California, miembro de la Academia Americana de las Artes y las Ciencias (1975), y miembro de la Academia Nacional de Ingeniería (1977).

Fue galardonado con la Medalla de Honor del IEEE en 1979, "por sus contribuciones a los procesos de decisión y la teoría de sistemas de control, en particular por la creación y aplicación de la programación dinámica". Su obra fundamental es la ecuación de Bellman.

Trabajo

Ecuación de Bellman: Programación Dinámica

Una ecuación de Bellman, también conocida como la ecuación de programación dinámica, es una condición necesaria para la optimalidad asociado con el método de optimización matemática conocida como la programación dinámica. Casi cualquier problema que se puede resolver utilizando la teoría de control óptimo también se puede resolver mediante el análisis de la correspondiente ecuación de Bellman. La ecuación de Bellman se aplicó por primera vez a la teoría de la ingeniería de control y otros temas de matemáticas aplicadas, y, posteriormente, se convirtió en una herramienta importante en la teoría económica.

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos.

 En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1.     Dividir el problema en subproblemas más pequeños.

2.     Resolver estos problemas de manera óptima usando este proceso de tres pasos     recursivamente.

 3.    Usar estas soluciones óptimas para construir una solución óptima al problema original.

Ecuación de Hamilton-Jacobi-Bellman

La ecuación de Hamilton-Jacobi-Bellman (HJB) es una ecuación diferencial parcial que es fundamental para la teoría de control óptimo. La solución de la ecuación HJB es la "función de valor", que da a la óptima función de los costos un determinado sistema dinámico con una función de costos asociados. Clásicos problemas variacionales, por ejemplo puede resolverse utilizando este método.

La ecuación es el resultado de la teoría de programación dinámica que fue creado en los 50’s por Richard Bellman y compañeros de trabajo. La ecuación correspondiente en tiempo discreto que normalmente se conoce como la ecuación de Bellman. En tiempo continuo, el resultado puede ser visto como una extensión del trabajo anterior en la física clásica en la ecuación de Hamilton-Jacobi por William Rowan Hamilton y Carl Gustav Jacob Jacobi.

Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford, a veces conocido como el algoritmo de corrección de la etiqueta, calcula un solo proveedor o caminos más cortos en un digrafo ponderado (donde algunos de los valores pueden ser negativos). El algoritmo de Dijkstra logra el mismo problema con un tiempo de baja en ejecución, pero requiere de pesos ventaja de ser no-negativas.

Publicaciones

A lo largo de su carrera ha publicado 619 artículos y 39 libros. Aquí una pequeña selección:

1957. Programación Dinámica
1959. Comportamiento asintótico de las soluciones de las ecuaciones diferenciales
1961. Introducción a las desigualdades
1961. Control de Procesos Adaptativos: Un Tour guiado
1962. Programación Dinámica Aplicada
1967. Introducción a la Teoría Matemática de Control de Procesos
1970. Algoritmos, Grafos y equipos
1972. Programación Dinámica y Ecuaciones Diferenciales Parciales
1982. Aspectos matemáticos de Programación y Aplicaciones
1983. Métodos Matemáticos en Medicina
1984. Ecuaciones Diferenciales Parciales
1984. Ojo del huracán: publicación de una autobiografía, Mundo Científico.
1985. Inteligencia Artificial
1995. Ecuaciones Diferenciales Elementales modernas
1997. Introducción a Análisis de matrices

Ejemplo de Programación Dinámica

El espejo del líder - David Fischman

Vivimos en una era de cambio constante. Para que las organizaciones continúen siendo competitivas deben realizar mejoras a través del cambio y del aprendizaje, esto es algo que siempre nos recordaba mi profesor del curso de Recursos Humanos;los recursos materiales se pueden innovar o rediseñar; pero lo que resulta difícil es el recurso humano que debe enfrentar el cambio.

Ahora les presento lo que aprendí leyendo un gran libro como es "El espejo del líder" escrito por David Fischman:
La premisa de la que parte este libro es que un líder es ante todo un observador: tiene que conocerse a sí mismo, saber mirarse en el espejo y conocer a la gente con la que trabaja. El espejo del líder ayuda a vernos a nosotros mismos a través del “espejo” que es el primer paso para auto-liderar el cambio que nos permita ser mejores y liderar nuestras vidas, aquí lo que se requiere:

Control del ego

Con este primer paso, me quede impresionada pues según la psicología el ego es el yo, sin embargo la definición de ego que se utiliza en el libro está relacionada con la autoestima.

El ego es una personalidad inferior que se crea cuando la persona tiene una autoestima baja, trata de ocultar a toda costa que la persona se siente poco valorada o insegura.

Claro que el ego es inherente al ser humano, lasí que lo que se tiene que hacer con él es mantenerlo bajo control y dejar de pensar en nosotros mismos, en destacar o en figurar y pensemos mejor en todo lo que podemos hacer para ayudar y permitir crecer a las personas de nuestro entorno.

Equilibrio

Para ser exitosos en los estudios y en los negocios no necesitamos vivir en estrés. Al contrario, mientras más equilibrados estemos, mejores decisiones tomaremos. De la misma forma en que se le da mantenimiento a una máquina, se le tiene que dar mantenimiento al cuerpo y a la mente.

Una forma de hacerlo es cuidando lo que entra en nuestra mente, tenemos que hacer pasar los pensamientos que nos permitan crecer y desarrollarnos. Otra de las formas es no pensar durante unos minutos al día y sólo relajarnos para darnos cuenta de que dentro de nosotros existe un lindo lugar lleno de paz y felicidad.

Desapego

Este es uno de los más difíciles (sobretodo para mi) pues tenemos apego a los bienes materiales o a nuestras metas, creemos que es normal pero no lo es cuando nos convencemos de que sin lograr obtenerlas no podemos ser felices. 
El desapego implica alejarnos de las cosas vanales y entender que nuestra existencia es cíclica. Lograr el desapego es saber que dentro de nosotros tenemos todo lo que Dios nos dio para ser felices y que lo exterior es solo un complemento de nuestra vida.

Responsabilidad

Y nos preguntamos por qué nos cuesta ser responsables...Es aquí donde se interrelaciona los capítulos anteriores del libro: Cuando no estamo en equilibrio, cuando el ego nos controla y cuando nos apegamos a las metas; es más difícil tener libertad para ser responsables de nuestros actos.

El liderazgo  es un camino de desarrollo personal y empieza por tener la capacidad de dirigirse a uno mismo. No se puede liderar a otros si no puedo dar primero el ejemplo.

Trabajo en equipo

Cuando se tiene lo anteriormente descrito en el libro de Fischman, las personas están listas para trabajar en equipo.

También se requiere de una comunicación abierta y sincera para crear un ambiente que favorezca discutir diversos puntos de vista.

Los miembros de un equipo también dependen unos de otros, así que para lograr un equipo exitoso debemos involucrarnos y orientarnos al servicio de nuestros compañeros con humildad.

Destrezas Gerenciales

Lo que hace excelente a tu artista o grupo favorito no es la destreza en el baile ni el rango de su voz...¿sabes lo que realmente es? ...la pasión y el amor que le pone. Lo mismo ocurre en una organización, no basta con ser eficientes y productivos, porque la competencia puede igualarnos en eso, lo que hará a la empresa competitiva y diferente es el compromiso y la pasión de su recurso humano.

Para lograr despertar la pasión del personal, se debe trabajar con una visión que todos compartan y saber comunicarla: motivando, entrenando y retroalimentando al personal, dando el ejemplo con integridad.

¿Que tal?. Parecen unos sencillos pasos, pero sabemos que nos costaría un poco (o bastante) lograr ir escalando cada uno de ellos. Es una cuestión de decisión y aprendizaje continuo, quienes quieren seguir mejorando y comprometerse a pensar en los demás antes que en sí mismos, este libro en un valioso instrumento para llegar a ser el líder que todos queremos ser y seguir en la constante búsqueda de nuestra maestría personal.