Redes Cargo Fijo

Escuela de Ingeniería Industrial

Proyecto Computacional de Investigación Operacional I
Por
XXXXXXXXXXXXXXXXX

Diseño de Redes con Cargo Fijo

Mayo, 2012


Índice

Glosario 3
1 Introducción 4
2 Explicación del problema 5
3 Aplicación del problema 6
4 Formulación del Problema 7
5 Reseña Histórica 9
Bibliografía 11







Glosario

Árbol: Red conexa (paraalgú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.

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

Capacidad del arco: Cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido.

Ciclo: Trayectoria que comienza y termina en el mismo nodo.
Red: conjunto de puntos y líneas que unen ciertos pares de puntos.

Nodos: Puntos (ovértices).

Nodo de demanda: Nodo de destino, donde el flujo que llega excede al que sale de él. Nodo fuente:

Nodo origen, tiene la propiedad de que el flujo que sale del nodo excede el flujo que entra a él.

Nodo de trasbordo: Intermedio, satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.

Red conexa: Red en la que cada par de nodos está conectado.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.


1 Introducción

Dentro del curso de Investigación de Operaciones Nivel I de la carrera de Ingeniería Civil industrial de la Pontificia Universidad Católica de Valparaíso se contempla la realización de un proyectocomputacional, tema asignado por el profesor de la asignatura.

El desarrollo del proyecto permite a los alumnos profundizar en los temas acordes a la asignatura como también obtener un mayor manejo de los programas computacionales, los cuales son un aporte importante para la aplicación de los modelos. La Investigación de Operaciones (IO), o Investigación Operativa, es la investigación de lasoperaciones a realizar para el logro óptimo de los objetivos de un sistema o la mejora del mismo. Esta disciplina brinda y utiliza la metodología científica en la búsqueda de soluciones óptimas, como apoyo en los procesos de decisión, en cuanto a lo que se refiere a la toma de decisiones óptimas y en sistemas que se originan en la vida real.

El tema a abordar es sobre el diseño de redes con costofijo, el cual exponemos en el presente informe.
















2 Explicación del problema

El diseño de redes a costo fijo tiene una posición medular entre los modelos de optimización de redes; se debe enviar entre diferentes puntos de origen y destino a través de una red con capacidad limitada. Por otra parte se adjudica un costo proporcional al número deunidades de cada unidad transportada en un enlace de red (costo variable), además de un costo fijo que debe pagarse la primera vez que se utiliza el enlace, lo que supone su construcción de apertura. El objetivo es identificar el diseño óptimo, es decir, seleccionar los enlaces para incluir en la versión final de manera de minimizar los costos totales del sistema de red, calculado como la suma de loscostos fijos y variables, satisfaciendo al mismo tiempo la demanda requerida.

A continuación se describe el problema de redes con costo fijo:

1. La red es una red dirigida y conexa.
2. Al menos uno de los nodos es un nodo fuente.
3. Al menos uno de los nodos es un nodo de demanda.
4. El resto de los nodos son nodos de trasbordo.
5. Se permite el flujo a través de un arco...