La ruta mas corta - Lecture notes 123 PDF

Preview

Summary

texto...

Description

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

IO04001 – Investigación de Operaciones I

Tema # 19 El problema de la ruta más corta

Objetivos de aprendizaje

Al finalizar este tema serás capaz de: • Distinguir problemas de la ruta más corta y su proceso de solución. • Aplicar el algoritmo del problema de la ruta más corta para la solución d problemas. de bl

D.R. © Universidad TecMilenio

1

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Introducción al tema • Es importante aprender a encontrar la ruta más corta en un problema de redes, es decir, aplicar el algoritmo de la ruta más corta para encontrar la menor distancia de un punto origen a un destino, de entre una serie de nodos conectados entre sí para llegar al mismo destino. Este tipo de problema se utiliza en problemas de logística y planeación de rutas, para minimizar los costos, el tiempo de llegada y el tiempo tiempo de entrega, entrega yy especialmente especialmente para para planear las rutas de entregas de envíos o las rutas de viajes largos a seguir por los aviones en los aeropuertos.

3

La ruta más corta • A lo largo del curso hemos estudiado diferentes aplicaciones ap cac o es de la a pprogramación og a ac ó lineal, ea , espec específicamente ca e te los modelos de redes. • Como ya habíamos mencionado, los modelos de redes adoptan diversas formas, entre ellas el problema de la ruta más corta. • El modelo de la ruta más corta es una red en la que encontraremos un número cij asociado a cada arco (i, j). Este número Cij, puede ser interpretado como la distancia, el costo o el tiempo entre un nodo i y otro j. 4

D.R. © Universidad TecMilenio

2

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

La ruta más corta

• En el tema anterior aprendimos que una ruta entre dos nodos es cualquier secuencia de arcos que conecte a estos nodos. •El objetivo del problema de la ruta más corta es precisamente encontrar el camino má s corto, de menor costo o más rápido, desde un nodo específico hasta cada uno de los demás nodos de la red. 5

La ruta más corta •A continuación ejemplificaremos el modelo de la ruta más corta para su mejor comprensión. Una empresa distribuidora de jugos envía con frecuencia el producto a 7 hoteles diferentes. Las rutas para viajar entre los 7 hoteles se muestran en el siguiente diagrama de red:

6

D.R. © Universidad TecMilenio

3

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Ejemplo

• Como te podrás dar cuenta, los arcos no tienen orientación, es decir, que la red permite el flujo en cualquier dirección. 7

Ejemplo • Los números entre cada nodo representan la distancia entre ellos. El punto de partida es el nodo A. • El objetivo del problema es encontrar la ruta más corta para el envío de jugo a los 7 hoteles, de manera que se puedan minimizar los costos totales de la empresa.

8

D.R. © Universidad TecMilenio

4

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Formulación del modelo de PL Función objetivo: Se considera que la suma ∑ij Cij X ij incluye todos los arcos de la red, por lo que el objetivo es minimizar la distancia total del flujo. MIN ∑ ij Cij Xij Restricciones: ∑ k Xjk - ∑ k Xkj = Lj (j= 1, 2… n) 0 ≤ Xij ≤ Uij, para todo (i, j) de la red. 9

Ejemplo • Observamos que el flujo total que sale del nodo j, menos el flujo total que entra al nodo j, es igual a la oferta en el nodo j. • La oferta negativa (-) representa un requerimiento. Los nodos con oferta negativa son llamados destinos o puntos de demanda. Por el contrario, los nodos con oferta positiva se llaman orígenes o puntos de oferta. • Suponemos que ∑ jLj = 0, es decir que la oferta total es igual a la demanda total, por lo que toda Cij ≥ 0. • Los Uij son las capacidades de los flujos Xij.

D.R. © Universidad TecMilenio

10

5

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

• Utilizaremos el SOLVER de Excel para resolver el modelo, los datos que nos pide son los cij, las Lj y las Uij

Como podemos observar, en la tabla tenemos las distancias que se van acumulando de NODO a NODO, y con ello podemos determinar la ruta a seguir. 11

Cierre • El método es muy sencillo, teniendo como objetivo encontrar el nodo más cercano al origen, y así sucesivamente hasta donde el nodo más cercano sea el destino, se van conectando los nodos formando una distancia desde el origen y escogiendo los candidatos más pequeños como siguientes nodos hasta llegar al destino.

12

D.R. © Universidad TecMilenio

6

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Pregunta de reflexión

¿En qué consiste el Método de la Ruta Más Corta?

13

Para aprender más • Si todavía tienes problemas al generar los modelos en el Solver, So e , te recomiendo eco e do visites s tes eel ssiguiente gu e te ssitio t o de de Internet. • http://www.uv.es/asepuma/XIII/comunica/comunica_17.p df (consultada 6 de febrero el 2009)

14

D.R. © Universidad TecMilenio

7

Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones 1

Referencias bibliográficas Libro Hillier, F., Lieberman, G. (2006). Introducción a la Investigación de Operaciones. (8ª Ed.) México: McGraw Hill. ISBN 970-10-5621-3

Créditos Diseño de contenido: Ing. Ingrid Gabriela Benavides García Coordinador académico del área: Lic. José de Jesús Romero A. MC y MED Edición de contenido: Lic. Rosa Luz Fernández Retana Edición de texto: Lic. Dalila de León Bañuelos, MTE

D.R. © Universidad TecMilenio

8...