advertisement

Optimizacion de redes

50 %
50 %
advertisement
Information about Optimizacion de redes
Design

Published on March 10, 2014

Author: TPYXNHKN

Source: slideshare.net

advertisement

NOMBRE DEL ALUMNO: JAIME VALDIVIA CASTELLANOS MATERIA: INVESTIGACIÓN DE OPERACIONES II NUMERO DE CONTROL: 119T0101 NOMBRE DEL DOCENTE: ING. ROBERTO CRUZ ANDRADE NÚMERO Y NOMBRE DE LA UNIDAD: V OPTIMIZACIÓN DE REDES

INTRODUCCIÓN Muchos problemas comerciales pueden ser resueltos a través de modelos de redes, en la cual no se necesitan restricciones adicionales para obtener la solución el cual se resuelve por pequeños algoritmos, no importa el tamaño del problema.

5.1 TERMINOLOGÍA Una red consiste de puntos llamados nodos o vértices y las líneas que llaman arcos. Dos nodos pueden estar conectados por un conjunto de arcos. Una trayectoria es una secuencia de arcos distintos (con nodos no repetidos) conectando a los nodos. Los arcos pueden tener una dirección asociada, que se denominan arcos dirigidos, si un arco no tiene dirección se le denomina rama. Si todos los arcos en la red son dirigidos, la red se denomina una red dirigida. Si todos los arcos son no-dirigidos, la red es una red no-dirigida. Una trayectoria no dirigida puede incluir arcos dirigidos apuntando en cualquiera de dirección. Una trayectoria que comienza y que termina en el mismo nodo se denomina ciclo y puede ser ya sea dirigida o no-dirigida. 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.  Capacidad del arco: Cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido.  Nodo fuente: Nodo origen, tiene la propiedad de que el flujo que sale del nodo excede el flujo que entra a él.  Nodo de demanda: Nodo de destino, donde el flujo que llega excede al que sale de él.  Nodo de trasbordo: Intermedio, satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.

5.2 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.

5.3 PROBLEMA DEL ÁRBOL DE MÍNIMA EXPANSIÓN Este problema se refiere a utilizarlas ramas o arcos de la red para llegar a todos los nodos de la red, de manera tal que minimiza la longitud total. Se considera una red no dirigida y conexa. En ella se debe encontrar un árbol de expansión con la longitud mínima de sus arcos. Es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima. Algoritmo para el problema del árbol de expansión mínima.  Selecciona, de manera arbitraria, cualquier nodo y se al nodo distinto más cercano.  Identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos, este paso se repite hasta que todos los nodos están conectados.  Empates: Los empates para el nodo más cercano distinto (paso 1) o para el nodo conectado más cercano (paso 2)

5.4 PROBLEMA DE FLUJO MÁXIMO En una red con flujo de capacidades en los arcos, el problema es determinar el flujo máximo posible proveniente de los orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta red, deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m. En la formulación de la programación lineal, el objetivo es maximizar F. El monto que parte del origen por varias rutas. Para cada nodo intermedio, lo que entra debe ser igual a lo sale. En algunas rutas los flujos pueden tomar ambas direcciones. La capacidad no debe ser necesariamente la misma para cada dirección del arco.

.5.5 PROBLEMA DE FLUJO DE COSTO MÍNIMO 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 versión simplificada del método simplex llamada método simplex de redes. A continuación se describe el problema del flujo de costo mínimo.  La red es una red dirigida y conexa.  Al menos uno de los nodos es un nodo fuente.  Al menos uno de los nodos es un nodo de demanda.  El resto de los nodos son nodos de trasbordo.  Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco.  La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos de demanda.  El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.  El objetivo es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la demanda dada

CONCLUSIÓN Modelos de optimización de redes nos sirve como una herramienta para la solución óptima a los problemas de flujo de redes, por lo que proporcionan algoritmos fáciles de comprender y aplicar.

BIBLIOGRAFÍA Investigación de operaciones, 5ª edición, Editorial taha, pp. 856-863 Schrage, L. (2002). Optimization Modeling with LINGOâ. Fifth edition, Lindo System Inc. USA. Moskowitz, Herbert., Wright, Gordon. Investigación de Operaciones, Editorial Prentice Hall.

Add a comment

Related presentations

My Music Magazine Pitch

My Music Magazine Pitch

October 30, 2014

music mag pitch

Questionaire charts

Questionaire charts

November 4, 2014

bk

Final research

Final research

November 5, 2014

final research

Cersaie 2014

Cersaie 2014

October 30, 2014

allestimento in cartone per il Cersaie 2014 alberi in cartone scultura in cartone

Quarta turma do workshop de Infografia, ministrado por Beatriz Blanco e Marcos Sin...

Related pages

Optimización en redes. Flujos en redes (Network Flows NF)

TEORÍA DE GRAFOS. OPTIMIZACIÓN EN REDES 1 Optimización en redes. Flujos en redes (Network Flows NF) Andrés Ramos Universidad Pontificia Comillas
Read more

Optimización de redes - Monografias.com

Resúmen. Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida ...
Read more

Optimización de Enteros y Modelos de Redes - home.ubalt.edu

Estos problemas son ilustrados fácilmente utilizando los arcos de redes, y los nodos. Optimización de Enteros y Modelos de Redes.
Read more

Optimización de Redes Sociales - Joan Boluda

La Optimización de Redes Sociales es una disciplina del Marketing Online que tiene el objetivo de darse a conocer a través de comunidades sociales de ...
Read more

Definición de optimización - Qué es, Significado y Concepto

Definicion.de: Definición de optimización (http://definicion.de/optimizacion/) Últimas definiciones. Definición de consistente; Definición de ...
Read more

OPTIMIZACIÓN EN REDES - ftp.itam.mx

Title: OPTIMIZACIÓN EN REDES Author: Cristina Gigola Last modified by: I.T.A.M. Created Date: 11/16/1999 8:31:04 AM Document presentation format
Read more

Optimización (matemática) - Wikipedia, la enciclopedia libre

Variantes del algoritmo Simplex que son especialmente apropiadas para la optimización de redes. Algoritmos combinatorios. Métodos iterativos Los ...
Read more

Rendimiento y optimización de redes | Blue Coat

Ya sea para adoptar aplicaciones basadas en la nube, como Office 365 y SalesForce.com, o iniciativas BYOD y redes sociales, las empresas de hoy hacen ...
Read more

equip4.files.wordpress.com

Optimización De Redes. Alumnos: Yesenia Contreras Magaña. Román Hernández Estrada. Widman Antonio Hernández Ovando. Josué Efraín Aguilar Guzmán.
Read more