Arboles De Expancion Min.

UNIVERSIDAD POLITECNICA DE BAJA CALIFORNIA

CARRERA
Ing. En tecnologías de la información

MATERIA:
Investigación de Operaciones

ALUMNO:
Ma. Graciela Escárcega Almeida
Alberto Aguilar Nrgrete

MAESTRO:
Fabiola Flores

TAREA
Método de mínima expansión
Métodos simplex

CUATRIMESTRE:
9 AV

Mexicali B.C a 28 de Junio del 2012

INDICE

Método de mínima expansión 1Métodos simplex 1
INDICE 2
ÁRBOL DE EXPANSIÓN MÍNIMA: 3
LA IMPORTANCIA DE LOS MODELOS DE REDES: 3
TERMINOLOGÍA DE REDES: 4
 Arcos dirigidos / no dirigidos: 4
 Nodos adyacentes: 4
RUTAS / CONEXIÓN ENTRE NODOS 4
 Ruta: 4
CICLOS / ARBOLES / ARBOLES EXPANDIDOS 4
 Ciclos: 4
 Árbol: 4
 Árbol expandido: 5
ARBOL DE EXPANCION MINIMA 5
ALGORITMO DE KRUSKAL 5
CNCLUSION 5 ÁRBOL DE EXPANSIÓN MÍNIMA

Un problema de recorrido mínimo involucra a un conjunto de nodos y a un conjunto de ramas propuestas, ninguna de las cuales es orientada. Cada rama propuesta tiene un costo no negativo asociado a ella. El objetivo es construir una red conexa que contenga a todos los nodos y que sea tal que la suma de los costos asociados con las ramas realmente empleadas semínima. Debe suponerse que hay suficientes ramas propuestas para asegurar la existencia de una solución.

No es difícil ver un problema de recorrido mínimo, se resuelve siempre mediante un árbol. (Si dos nodos en una red conexa están unidos mediante dos rutas, una de estas rutas debe contener una rama cuya eliminación no desconecte a la red. El eliminar la rama puede solamente abatir el costo total. Unárbol de recorrido mínimo puede encontrarse al seleccionar inicialmente cualquier nodo y determinar cual de las ramas que coinciden con el nodo seleccionado tiene el menor costo.  A esta rama se le acepta como parte de lared final. Después se completa la red iterativamente. En cada etapa delproceso iterativo, la atención se centra en aquellos nodos que ya se han eslabonado. Todas las ramas queconectan a estos nodos con nodo sin conexos se consideran y se identifica a la más barata de las ramas.
Los empates se resuelven arbitrariamente.  A esta rama se le acepta como parte de la red final.  El proceso iterativo termina cuando se han eslabonado todos los nodos. Si todos los costos son diferentes (esto siempre se puede obtener mediante cambios infinitesimales), se puede probar que el árbol derecorrido mínimo es único y que es un producto del algoritmo anterior para cualquier selección de nodo inicial.

Si todos los costos son diferentes (esto siempre se puede obtener mediante cambios infinitesimales), se puede probar que el árbol de recorrido mínimo es único y que es un producto del algoritmo anterior para cualquier selección de nodo inicial.

Un problema de redes es aquel quepuede representarse por:
* Nodos
* Arcos
* Funciones en los arcos.

LA IMPORTANCIA DE LOS MODELOS DE REDES:

* Muchos problemas comerciales pueden ser resueltos a través de modelos de redes.
* El resultado de un problema de redes garantiza una solución entera, dada su estructura matemática. No se necesitan restricciones adicionales para obtener este tipo de solución.
*Problemas de redes pueden ser resueltos por pequeños algoritmos, no importando el tamaño del problema, dada su estructura matemática.

TERMINOLOGÍA DE REDES:

Flujo:
Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a través de un arco que los conecta.

Notación usada

X ij | = | Cantidad de flujo |
U ij | = | Cota mínima de flujo que se debe transportar |
L ij| = | Cota máxima de flujo que se puede transportar. |

* Arcos dirigidos / no dirigidos:
Cuando el flujo puede transportarse en una sola dirección se tiene un arco dirigido (la fecha indica la dirección). Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha).

* Nodos adyacentes:
Un nodo j es adyacente con un nodo i si existe un arco que...