Investigacion Proyecto 1

COSTOS Y OPTIMIZACION DE REDES

Los modelos de redes y los programas de números enteros son aplicables para una gran variedad de modelos decisión. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial. Estos problemas son ilustrados fácilmente utilizando los arcos de redes, y los nodos. Los programas lineal estándar asumen que las variables de decisión son continuas. Sin embargo, en muchas aplicaciones, los valores de fracciones podrían ser de poco uso así como es mostrado en algunas aplicaciones útiles.

Identificación e implementación de medidas de reducción y control de los costos en las configuraciones de la red, revisando los planes de servicios contratados y las capacidades de los equipos instalados. Se provee un mejor entendimiento de los costos en telecomunicaciones e informaciones sobre su utilización, para hacer más eficiente la administración de los recursos y de los proveedores. En este punto se desarrollan estrategias dirigidas a obtener los mayores beneficios de la plataforma existente a nivel de los servicios instalados, la tecnología, los proveedores, distribución de costos, análisis de costos, análisis de procesos, benchmark y análisis de requerimientos. |

MODELOS DE REDES

Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:

 Modelo de minimización de redes (Problema del árbol de mínima expansión).

 Modelo de la ruta más corta.

 Modelo del flujo máximo.

 Modelo del flujo del costo mínimo.

INTRODUCCIÓN A LOS MODELOS DE REDES

Los modelos de redes son aplicables a una extensa variedad de problemas de decisión, los cuales pueden ser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Sin embargo, muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial.

La familia de redes de los problemas de optimización incluye los siguientes prototipos de modelos: Problemas de asignación, camino crítico, flujo máximo, camino más corto, transporte y costo mínimo de flujos. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos.

¿Que es un Nodo? Es usualmente llamado vértice, o punto. Es usualmente representado por un círculo. En las redes de transporte, estos deberían ser las localidades o las ciudades en un mapa.

¿Que es un Arco? Es usualmente llamado borde o flecha. Este podría ser directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen como al final. En las redes de transporte, los arcos podrían ser los caminos, los canales de navegación en un río, o los patrones de vuelo de un avión. Los arcos proporciona la conectividad entre los nodos. Una calle de una sola dirección podría ser representada por un arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o por dos arcos que apuntan a direcciones opuestas.

Una red con n nodos podría tener tantos arcos como n! / [(n-2)! 2!] = n(n-1)/2. Si están dirigidos, este número pudiese ser doble. Este enorme número de arcos posibles es una de las razones del porque existen soluciones de algoritmos especiales para problemas de redes particulares.

Los modelos de transporten juegan un papel importante en la gerencia logística y en la cadena de insumos para reducir costos y mejorar servicios. Por lo tanto, el objetivo es encontrar la manera más efectiva en término de costos para transportar bienes.

MODELO DE MINIMIZACIÓN DE REDES

El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en la solución del problema. Para crear el árbol de expansión mínima tiene las siguientes características:

1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)

2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que hayan camino entre cada par de nodos.

3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.

MODELO DE FLUJO MÁXIMO

Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino. Características:

1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.

2. Los nodos restantes son nodos de trasbordo.

3. 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á dad por la capacidad del arco. En la fuente, todos losaros señalan hacia fuera. En el destino, todos señalan hacia el nodo.

4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de Lafuente o la cantidad que entra al destino.

MODELO DE LA RUTA MÁS 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 procedimientos 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-pésima iteración: encontrar el n-pésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2, « hasta que el n-pésimo nodo más cercano sea el nodo destino.)

2. Datos para la n-pé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-pé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-pésimo nodo más cercano: para cada nodo resuelto y sus candidatos, sesma 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-pésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es laque genera esta distancia.

DEL FLUJO DE COSTO MÍNIMO

El problema de flujo de costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su soluciones muy eficiente. Igual que el problema del flujo máximo, toma en cuenta un flujo en una red con capacidades limitadas en sus arcos. Igual que el problema de la ruta más corta, consideran costo (o distancia) para el flujo a través de un arco. Igual que el problema de transporte o el de asignación, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demandas) para el flujo, de nuevo con costos asociados. De hecho, estos cuatro problemas son casos especiales del problema de flujo de costo mínimo.

A continuación se describe el problema del flujo de costo mínimo:

1. La red es una red dirigida conexa.

2. Al menos uno de los nodos es nodo fuente.

3. Al menos uno de los nodos es nodo demanda.

4. El resto de los nodos son nodos de trasbordo.

5. 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. (Si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas.)

6. La red tiene suficientes arcos como suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos demanda.

7. El costo del flujo a través del arco es proporcional

...