Cadenas De Markov

Tecnológico de colima

Nombre de la materia:

Investigación de Operaciones II

Nombre del maestro:

Jesús Francisco Tejeda Castrejón

Nombre del trabajo:

Optimización de redes

Nombre del alumno:

Ulises Daniel Gutiérrez Melchor

Grado: Grupo:

5to T12

Índice

Introducción

Desarrollo

Conclusión

Bibliografías

Introducción

Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. La representación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera, para nombrar sólo unos ejemplos. De hecho, una representación de redes proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre los componentes del sistema, que se usa casi en todas las áreas científicas, sociales y económicas. Uno de los mayores desarrollos recientes en investigación de operaciones (IO) ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización de redes. La aparición de algunos algoritmos ha tenido un impacto importante, al igual que las ideas de ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de los mismos. En consecuencia, ahora se dispone de algoritmos y paquetes de computadora y se usan en forma rutinaria para resolver problemas muy grandes que no se habrían podido manejar hace dos o tres décadas. Se darán a conocer en este trabajo cinco tipos importantes de problemas de redes y algunas ideas básicas sobre cómo resolverlos (sin profundizar en los aspectos de estructuras de bases de datos, tan vitales para la aplicación exitosa en los problemas de gran escala). Los tres primeros tipos de problemas –el problema de la ruta más corta, el problema del árbol de mínima expansión y el problema del flujo máximo- tienen una estructura específica que surge con frecuencia en la práctica. El cuarto tipo –el problema del flujo de costo mínimo- proporciona un enfoque unificador de muchas otras aplicaciones por su estructura mucho más general. Y por último el método del CPM. Terminología de Redes Red: conjunto de puntos y líneas que unen ciertos pares de puntos. Nodos: Puntos (o vértices). Arcos: Líneas, ligaduras, aristas o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales. Arco dirigido: Si el flujo a través de un arco se permite sólo en una dirección. La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. Arco no dirigido: Si el flujo a través de un arco se permite en ambas direcciones. Red dirigida: Red que tiene sólo arcos dirigidos. Red no dirigida: Todos sus arcos son no dirigidos. Trayectoria: Sucesión de arcos distintos que conectan nodos. Ciclo: Trayectoria que comienza y termina en el mismo nodo. Red conexa: Red en la que cada par de nodos está conectado. Árbol: Red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos. Árbol de expansión: Red conexa para los n nodos que contiene ciclos no dirigidos.

Desarrollo

PROBLEMA DE LA RUTA MAS CORTA Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino. Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino. Algoritmo de la ruta más corta: 1. Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.) 2. Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.) 3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.) 4. Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

FLUJO DE COSTO MÍNIMO ¿Qué es? El problema del flujo de costo mínimo tiene una posición medular entre los modelos de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su solución es muy eficiente. Toma en cuenta un flujo en una red con capacidades limitadas en sus arcos. Considera un costo (o distancia) para el flujo a través de un arco. Puede manejar varios orígenes (nodo fuente) y varios destinos (nodos demanda) para el flujo, de nuevo con costos asociados. La razón por la que el problema de flujo de costo mínimo se puede resolver de modo tan eficiente es que se puede formular como un problema de programación línea y es posible resolverlo con una

...