Investigacion De Operaciones

INSTITUTO TECNOLÓGICO DE CULIACÁN
ingeniería industrial

INVESTIGACIÓN DE OPERACIONES II
TRABAJO FINAL

13 DE DICIEMBRE DE 2012



INDICE
Introducción………………………………………………………………………………3
Justificación………………………………………………………………………………4
Marco teórico……………………………………………………………………………..5
Plantación del problema………………………………………………………………..6
Desarrollo del problema………………………………………………………………..6
Solucióndel problema………………………………………………………………….9
Conclusión……………………………………………………………………….……...13
Bibliografía……………………………………………………………………………....14

INTRODUCCIÓN
En el presente trabajo, realizaremos un análisis de las distintas rutas posibles a tomar entre dos puntos de nuestra ciudad, realizando un recorrido desde el punto inicial, siendo la casa de una de las integrantes localizada en el residencialInterlomas, y teniendo como punto final del trayecto el Instituto Tecnológico de Culiacán, ubicado en la colonia Guadalupe.
Por consiguiente el método que utilizaremos, basado en investigación de operaciones, será el de optimización de redes, buscando la ruta más corta dentro del recorrido especificado, con la ayuda de un GPS, realizando el recorrido de cada una de las rutas para verificar losdatos y estar seguros de cuál es la ruta más óptima en cuanto a tiempo y distancia.
Una vez determinada la ruta más corta, se tomara en consideración para el trayecto al Tecnológico.

JUSTIFICACIÓN
Los ingenieros industriales buscamos facilitar todas aquellas tareas que llevamos a cabo diariamente en cualquier ramo, en este caso desarrollamos la problemática de buscar las rutas óptimas para llegara nuestro destino, es decir al Instituto Tecnológico de Culiacán.
Por ende, pretendemos optimizar la distancia entre dos puntos, con el método de la ruta más corta, que se encuentra dentro del tema principal llamado optimización de redes, el cual está basado en los conocimientos obtenidos de Investigación de Operaciones.
Para ello será necesario realizar un recorrido entre los distintos puntostomando en cuenta todas las rutas posibles de trayecto, recabando los datos de distancias en kilómetros que comprenden cada una de ellas, así como las distancias comprendidas entre los distintos puntos de interconexión que se presenten.

MARCO TEÓRICO
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dadoun vértice origen al resto de vértices en un gráfico con pesos en cada arista.
La idea en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el gráfico, el algoritmo se detiene.
Sea Ui la distancia más corta del nodofuente 1 hasta el nodo i, y se define dij (≥0) como la longitud del arco (i,j). Entonces el algoritmo define la etiqueta de un nodo inmediato posterior j como:
[Uj, i] = [Ui + dij, i], dij≥0
La etiqueta del nodo de inicio es [0,-], que indica que el nodo no tiene predecesor.
Las etiquetas de nodos en el algoritmo de Dijkstra son de dos clases: temporales y permanentes. Una etiqueta temporal semodifica si se puede encontrar una ruta más corta a un nodo. Cuando se ve que no se pueden encontrar rutas mejores, cambia el estado de la etiqueta temporal a permanente.
El algoritmo se desarrolla de la siguiente manera:
Paso 0: Etiquetar el nodo fuente (nodo 1) con la etiqueta permanente [0,-], igualar i=1.
Paso 1: a) Calcular las etiquetas temporales [Ui + dij, i] para cada nodo j al que puedallegarse desde el nodo i, siempre y cuando j no tenga etiqueta permanente. Si el nodo j ya está etiquetado con [Ui,k] por otro nodo k, y si su Ui + dij<Uj, sustituir [Ui,k] por [Ui + dij, i]. b) Si todos los nodos tienen etiquetas permanentes, detenerse. En caso contrario, seleccionar la etiqueta [Ur, s] que tenga la distancia más corta (=Ur) entre todas las etiquetas temporales (los...