Trabajo optimizacio n



UNIVERSIDAD AUTONOMA DE CHILE
CARRERA DE INGENIERIA CIVIL INDUSTRIAL




“APLICACIÓN DE LA PROGRAMACIÓN DINÁMICA PARA RESOLVER EL PROBLEMA SIMPLE DE BALANCEO DE LINEA DE ENSAMBLE”
Scientia et Technica Año XVII, No 46, Diciembre 2010. Universidad Tecnológica de Pereira.




Programación Dinámica Determinística


Alumnos : Cristóbal De Ugarte V.
Roberto Egger Z.

Profesor : Dr. Sra.Dafne Lagos Hurel
Carrera : Ingeniería Civil Industrial






Temuco, junio 2015

INDICE




























1. RESUMEN

Este trabajo presenta en forma reducida la aplicación de un algoritmo exacto para solucionar un problema simple de balanceo de línea de ensamble, el algoritmo utilizado es la programación dinámica, se muestran las ventajas y desventajas de usar este método para solucionarproblemas de tipo combinatorial. La información del documento fue extraída de la revista Scientia Et Technica, vol. XVII, núm. 46, diciembre, 2010, pp. 62-67 Universidad Tecnológica de PereiraPereira, Colombia. Link: http://www.redalyc.org/articulo.oa?id=84920977024























2. INTRODUCCIÓN

En el siguiente documento se estudiara el tipo de programación dinámica determinística, y sepresentará en el ramo de Optimización. Se verán conceptos, ecuaciones, algoritmos, etc. Todo esto enfocado a un caso real que está basado en la aplicación de la programación dinámica para resolver el problema simple de balanceo de línea de ensamble.




















3. DESARROLLO
3.1 MARCO TEORICO

El objetivo de la programación dinámica (PD) es descomponer el problema en subproblemas (másmanejables). Los cálculos se realizan entonces recursivamente donde la solución óptima de un subproblema se utiliza como dato de entrada al siguiente problema. La solución para todo el problema está disponible cuando se soluciona el último subproblema. La forma en que se realizan los cálculos recursivos depende de cómo se descomponga el problema original. En particular, normalmente los subproblemasestán vinculados por restricciones comunes. La factibilidad de estas restricciones comunes se mantiene en todas las iteraciones.

En cada etapa se valora no solo el costo actual de tomar una decisión sino los costos futuros que se originan a partir de ella.
Etapas: k
Decisiones en cada etapa: uk
Estados (situaciones en que puede encontrarse el sistema en cada etapa): xk
El número de estados puedeser finito o infinito.

Mediante una decisión uk se va de un estado al comienzo de una etapa xk a otro estado al comienzo de la siguiente xk+1

Variables estado de etapa k Decisiones Variables estado de etapa k + 1
xk uk xk+1
En cada etapa se evalúa la decisión óptima para cada uno de sus estados xk

Cada estado guarda toda la información necesaria paratomar las decisiones futuras sin necesidad de conocer cómo se ha alcanzo dicho estado.

Es un procedimiento recursivo que resuelve de manera iterativa, incorporando cada vez una etapa, partes cada vez mayores del problema original. El procedimiento puede hacerse hacia delante o hacia tras.

Ejemplo 1:
Se busca el camino más corto entre la ciudad 1 y la ciudad 2 y averiguamos que la solución óptima delproblema pasa por la ciudad 3


Cuadro 1: Camino más corto entre ciudades











Fuente: http://www.iit.upcomillas.es/aramos/simio/transpa/t_dp_ar.pdf (adaptado)

Si nos preguntamos por el camino más corto entre la ciudad 3 y la ciudad 2, es obvio que será el mismo que el utilizado en la solución del problema global (ciudad 1 – ciudad 2).
Si existiera un camino más corto entre laciudad 3 y ciudad 2 (problema parcial), lo habríamos tomado como parte de la solución del problema global.








3.2 DESARROLLO DEL TEMA










3.3 APLICACIÓN PRÁCTICA

I.- APLICACIÓN DE LA PROGRAMACIÓN DINÁMICA PARA RESOLVER EL PROBLEMA SIMPLE DE BALANCEO DE LINEA DE ENSAMBLE.
El problema de las líneas de ensamble ha sido estudiado por diferentes investigadores desde diferentes enfoques,...