cosass

















INVESTIGACIÓN OPERATIVA II









Profesor Asociado:
Roberto Jiménez Ramírez
Magister en Ingeniería Industrial
Doctor (c) en Administración y Dirección de Empresas




2011

Contenido


CAPITULO V 3
PROGRAMACIÓN DINÁMICA 3
INTRODUCCIÓN 4
EJEMPLO 1 5
PROBLEMA DE LA DILIGENCIA 5
CARACTERISTICAS DE LOS PROBLEMAS DE PROGRAMACIÓNDINÁMICA. 11
PROGRAMACIÓN DINAMICA DETERMINÍSTICA 12
EJEMPLO 2 12
Consejo Mundial de la Salud 12
EJEMPLO 3 16
Proyecto Espacial 16
EJEMPLO 4 20
Compañía Lechera 20
PROBLEMA 5 26
Problema de la Mochila 26




















CAPITULO V


PROGRAMACIÓN DINÁMICA









INTRODUCCIÓN

La programación dinámica es una técnica matemática que resulta útil para tomaruna sucesión de decisiones interrelacionada.
Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global.
Sí la comparamos con la programación lineal, no existe un planteamiento matemático estándar del problema de programación dinámica.
La programación dinámica es un tipo general de enfoque para resolver problemas y las ecuacionesparticulares usadas deben desarrollarse para que se ajusten a cada situación individual.
Se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuándo un problema se puede resolver mediante los procedimientos de esta programación y cómo se haría.








EJEMPLO 1

PROBLEMA DE LA DILIGENCIA


Esteproblema se refiere a un vendedor mítico que tuvo que viajar hacia el oeste por diligencia, a través de tierras indias hostiles, aproximadamente hace 125 años. Aun cuando su punto de partida y destino eran fijos, tenía un número considerable de opciones para elegir qué estados recorrer en su ruta.



























Aquí vemos las posibles rutas a seguir, cada estadoesta representado por un bloque numerado. Además se requieren cuatro etapas para viajar desde su punto de embarque en el estado 1 hasta su destino en el estado 10.
Continuando con el cuento......
Este vendedor era un hombre prudente, que se preocupaba bastante respecto a la seguridad de su viaje. Después de reflexionar un poco se le ocurrió una forma un tanto ingeniosa de determinar la ruta mássegura.
Se ofrecían seguros de vida a los pasajeros de las diligencias. Como el costo de cada póliza se basaba en una evaluación cuidadosa de la seguridad de ese recorrido, la ruta más segura debía ser aquella con la póliza de seguro de vida más barata.
Los costos de la póliza estándar para el viaje en diligencia del estado i al j , el cual se denotará Cij, es


¿Cuál sería la ruta queminimiza el costo total de la póliza?
Un primer impulso podría conducirnos a elegir. Al recorrido más barato ofrecido en cada etapa sucesiva.
Ejemplo

Ruta 1 2 6 9 10
Costo 2 + 4 + 3 + 4 = 13 costo total

Sin embargo, sacrificando un poco en una etapa es posible que se obtengan ahorros mayores de allí en adelante.
Ejemplo
Ruta 1 4 6
Costo 3 + 1= 4

Comparado con la elección anterior
Ruta 1 2 6
Costo 2 + 4 = 6
Globalmente es más barata la primera opción.
Una forma de resolver este problema es por tanteo. Pero el número de rutas posibles es muy alto (en este caso 18) y por lo tanto son muchos los cálculos a realizar.
La programación dinámica suministra una solución con mucho menos esfuerzo que lanumeración exhaustiva
La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este problema más pequeño. Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original.
Veamos los detalles involucrados en la implementación general.
Considérese que las...