PROGRAMACION LINEAL EN TEORIA DE REDES
La modelación de redes permite la resolución de múltiples problemas de programación
matemática mediante la implementación de algoritmos especiales creados para tal fin,
conocidos como Algoritmos de optimización de redes.
Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se
encuentran los ya vistos modelos de transporte, transbordo además de los muy conocidos
modelos de determinación de cronograma de actividades para proyectos como lo son el PERT
y el CPM.
El PERT y el CPM son algoritmos basados en la teoría de redes para facilitar la planificación de
proyectos.
CONCEPTOS BASICOS EN TEORIA DE REDES
Gráfica: es una serie de puntos llamados nodos que van unidos por unas líneas
llamadas ramales o arcos.
Nodos: es un círculo en un diagrama de redes que representan un aspecto importante
de un problema. El nodo representa el origen y destino de bienes de un plan a realizar.
Arcos: también llamados ramales, es una línea o curva que conecta o enlaza dos nodos
en un diagrama esquemático que representa una relación entre estos dos nodos.
Red: es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo,
imaginemos una gráfica cuyo flujo en sus ramales sea la electricidad, por ende, esta
sería una red eléctrica.
Cadena: Una cadena corresponde a una serie de elementos ramales que van de un
nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el
nodo 7 y que se compone por los elementos [1-4, 4-7].
Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente
caso [1, 4, 7].
Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el
siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
Ramal Orientado: Un ramal o arco orientado es aquel que tiene un sentido
determinado, es decir que posee un nodo fuente y un nodo destino.
Grafica Orientada: Una gráfica orientada es aquella en la cual todos sus ramales se
encuentran orientados.
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.
Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos
de la red, de igual manera no permite la existencia de ciclos.
Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran
orientados hacia afuera.
Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se
encuentran orientados hacia él.
ALGORITMO DE ARBOL DE EXPASIÓN MINIMA
El algoritmo del árbol de expansión mínima 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.
PROBLEMA DE ARBOL DE EXPASIÓN MINIMA
En la ciudad de Huacho se está realizando un nuevo condominio a las afueras de la ciudad,
este condominio según la municipalidad no cuenta con la infraestructura necesaria para
satisfacer las necesidades de suministros públicos en materia flujo eléctrico, por el cual se ha
propuesto un nuevo plan integral urbanístico donde se realizará una red eléctrica por medio
de cableados a las primeras 8 casas del condominio.
Según el grafico cree usted una red de cableado en el cual se necesite la menor cantidad de
longitud de cable (en kilómetros) utilizando el algoritmo de árbol de expansión mínima
empezando por la casa (nodo) numero 6.