Teorema 13


3 Tipos de Métodos para cada problema.
Grafica Red orientada al menos un arco debe estar orientado.
Etiquetas
Matriciales Red no orientada todos sus arcos deben ser no orientados.

Camino Mínimo
Consiste en determinar la trayectoria de menor valor entre cualquier valor de nodos en una red orientada o una no orientada. Solo se necesita para resolverlo la identificación del nodo origen y elvalor de los arcos.

Árbol Mínimo
Es la unión o conexión de todos los nodos de una red no orientada, esto es una subred qque no contiene signos y el número de arco que la forman, N-1 e donde n0 numero de nodos de la red. No se requiere identificar al nodo al ser ni al nodo destino.

Flujo máximo
Consiste en determinar el total de unidades que pueden atravesar la red desde el nodo origen hasta elnodo destinado origen y el nodo destino, así como conocer la composiciones de flujo de cada acto.

Ejemplo de Método Grafico para camino mínimo.


0
2
3
4
7
11
7
9
S
A
B
C
D
R
F
T

1. Seleccionar los dos de menor valor
2. Seleccionar el arco de menos valor que no forme con ya seleccionados.
3. Se repite el paso anterior esto obtener los N-1 de los arcos.
4. Determinar el valor del árbol con losarcos seleccionados.
PROGRAMA SINTETIZADO
1. Redes de Optimización
2. Técnicas de Admón. de proyectos
3. Simulación
4. Análisis de Decisiones.
Redes de Optimizacion
Definición.
Es la representación grafica de los elementos de un sistema y sus interacciones, por el cual se hace pasar el jo de algún tipo (información, objetos, personas, etc.)
A los elementos del sistema se representan con pequeñoscírculos de de notados con letras mayúsculas y las interacciones como arcos o segmentos de rectis. Todo arco une o conecta a dos nodos.



Regresa al paso I hasta que no sea posible determinar una trayectoria, con la capacidad positiva en sus arcos el flujo máximo es igual FM=20
1) S → C → D → T
Ө1= Mim {10,6,10} = C
Ө1= 6
2) S → A → E → T
Ө2= Mim {12,8,9} =8
Ө2= 8
3) S → A → B → E → D→ TӨ3=Mim{4,5,4,5,4}=4
Ө3=4
4) S → C → B → D → F → T
Ө4= Mim {4,8,3,3,10}=3
Ө4=3
FM= { ӨI=6+8+4+3=2
METODO GRAFICO
Ejemplo
Red Presentada
Se identifica el nodo inicial y terminal de la red
Se conoce la capacidad de flujo de casa arco de la red.
FM≤Mim{}
Determinar el flujo
Modificacion del flujo
1. Determinar una trayectoria desde el nodo inicial al nodo terminal
De tal manera que la capacidad de los arcos quelo forman sean mayor que cero (Cj>0)
2. Se determina la cantidad de flujo que se hace pasar por la trayectoria seleccionada, en donde Ө Mim {} es mínimo de las capacidades de los arcos seleccionados.
3. Se suma Ө a la capacidad de los arcos de la trayectoria que van en sentido opuesto de (T a S) y se resta Ө a la capacidad de los mismos arcos pero en dirección opuesta. (S a T).}



Métodomatricial del árbol mínimo
Método Voraz.

1. Determinar la matriz o tabla (simétrica)del valor de los arcos, considerando a los nodos iniciales de los arcos como regiones y a los nodos finales como columnas de la red no orientada.
2. Seleccione arbitrariamente el nodo de un renglón donde elimine la columna correspondiente.
3. Sobre el renglón palomeado seleccione el valor del arco mínimo el nodo terminalde dicho nodo e ilumine la columna correspondiente.
4. Repita el paso anterior hasta obtener los N-1 arcos del árbol, esto es hasta que todos los renglones hayan quedado palomeados y las columnas eliminados. Calcule el valor del arco mínimo subrayando el valor de los arcos seleccionados.
Ejemplo.



MATRIZ DEL VALOR DE LOS ARCOS

S
A
B
C
D
E
F
T
SA=2
AB=1
BC=1
CB=1
DE=4
DR=4
FT=2
TF=2
DC=4
AD=5BA=1
CF=3
DA=5
DA=5
FC=3
TD=7
sb=5

BS=6

DB=6
ED=6
FI=5
TI=9


BI=8

DT=7
ET=9
FB=9



BE=9







Método de Dijkotea
(Ejemplo ara Red NO Orientada.)
Etiqueta temporal el nodo esta en el segundo estado
Etiqueta permanente el nodo esta en el tercer estado no cambia.
Etiqueta es una pareja de elementos ordenados.
Problema de Examen
Red NO Orientada

Los arcos (A,B),(C,D) y (B,A)
|Am|=20...