Modelo De Transporte
Enviado por jaime_ame • 1 de Marzo de 2014 • 1.016 Palabras (5 Páginas) • 193 Visitas
LICENCIATURA EN ADMINISTRACION DE EMPRESAS
INVESTIGACION DE OPERACIONES II
MODELO DE TRANSPORte
PROGRAMACIÓN DINÁMICA
Elementos de un modelo de programación dinámica
La programación dinámica es una técnica matemática principalmente para mejorar la eficiencia de cómputo en ciertos problemas de optimización. La idea básica de la técnica es descomponer el problema en subproblemas (más pequeños) los cuales son computacionalmente más manejables.
La programación dinámica está diseñada para evitar estas dificultades de la manera siguiente:
1. El problema se descompone en subproblemas (llamados etapas) y cada subproblema se optimiza sobre sus alternativas de manera que nunca sea necesario enumerar todas las combinaciones anticipadamente.
2. Debido a que la optimización se aplica a cada subproblema, todas las combinaciones no óptimas se descartan sistemáticamente.
3. Los subproblemas están “ligados” en una forma especial de manera que nunca es posible optimizar sobre combinaciones infactibles.
Los puntos anteriores son traducidos en una formulación de programación en términos de tres elementos básicos: (1) etapas, (2) alternativas (variables de decisión) en cada etapa y su función de rendimiento asociado y (3) estados del sistema en cada etapa. Una etapa representa una porción del problema para la cual se debe tomar una decisión.
Un modelo de programación dinámica típico con N etapas (4 etapas) puede representarse gráficamente como en la figura, donde N son las etapas, ei son los estados y Xi las variables de decisión de cada etapa.
El proceso de optimización normalmente comienza en la etapa 1, y pasa sucesivamente por todas las etapas hasta que se optimiza la etapa N última.
La determinación de alternativas dentro de cada etapa es parte integral de la definición de la etapa, y por consiguiente, deberá ser fácilmente identificable. Asociada a cada etapa está la función de rendimiento de una variable de decisión, la cual evalúa el “valor” de cada alternativa.
En el problema de presupuestar el capital, Ri, mi es el ingreso de la alternativa mi en la etapa (fábrica) i. El estado del sistema es quizás el concepto más importante en un modelo de programación dinámica. Representa la “liga” entre etapas (subsecuentes) de tal manera que cuando cada etapa se optimiza por separado, la decisión resultante es automáticamente factible para el problema completo. Además permite que se hagan decisiones óptimas para las etapas restantes sin tener que comprobar el efecto de decisiones futuras sobre decisiones que se han tomado anteriormente.
La definición del estado es usualmente el concepto más sutil en formulaciones de programación dinámica. No existe forma fácil de definir el estado, pero usualmente pueden encontrarse pistas haciendo las dos preguntas siguientes:
1. ¿Qué relaciones enlazan las etapas?
2. ¿Qué información es necesaria para tomar decisiones factibles en la etapa actual sin verificar la factibilidad de decisiones hechas en etapas anteriores?
Representación por la ecuación recursiva
El uso de etapas y estados para descomponer un problema de
...