Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Modelos de redes

Seminario de Investigacion de Operaciones II - Universidad Galileo
by

Diego Tello

on 10 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Modelos de redes

Modelos de redes ¿Por qué nos interesan? Encuestas indican que el 70% de los problemas de programación matemática pueden modelarse como redes. Determinación de la ruta más corta entre dos ciudades, en una red de carreteras. Veamos algunos ejemplos Determinación del programa de flujo con costo mínimo desde los campos petroleros hasta las refinerías a través de una red de oleoductos. Determinación del cronograma de las actividades en la construcción de un proyecto. ¿Como los resolvemos? Con diferentes algoritmos de optimización de redes. Árbol de expansión mínima.
Algoritmo de la ruta más corta.
Algoritmo del flujo máximo.
Algoritmo de red capacitada con costo mínimo.
Algoritmo de la ruta crítica. ¿Redes? Se describe como (N,A) veamos un ejemplo N={1,2,3,4,5}
A={(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)} 1 2 3 4 5 Se le asocia un flujo.
Limitado por la capacidad de los arcos.
Finitos o infinitos.
Dirigido u orientado.
Red dirigida.
Ruta.
Ciclo.
Dirigido.
Red conectada.
Árbol.
De expansión. Ciclo 2 3 4 Árbol de expansión 1 2 3 4 5 Árbol 1 2 3 Algoritmo de árbol de expansión mínima Ejercicio 1 2 3 4 5 Paso 1:
Comenzar con cualquier nodo en el conjunto C_0' Sea
N= {1,2,....,n}
C_k
Conjunto de nodos conectados permanentemente en la iteración k.
C_k'
Conjunto de nodos que todavía se deben conectar en forma permanente Paso 0:
C_0 = {}
C_0'=N Paso k:
C_k = C_k-1 + j*
c_k'=c_k-1'-{j*} Paso 1:
i Є C_0'
C_1 = {i}
C_1' = N - {i}
k = 2 ¿Qué hace?
Una aplicación característica.
Procedimiento Paso general k:
j* Є C_k-1'
C_k = C_k-1 + {j*}
C_k' = C_k-1' - {j*} Midwest TV Cable Company 1 2 3 4 6 5 1 7 9 5 4 6 5 3 8 10 3 Problema de la ruta más corta Determina la ruta mas corta entre una fuente y un destino en una red de transporte. veamos un ejemplo Reemplazo de equipo 1 2 3 4 5 4000 4300 4800 4900 5400 9800 7100 6200 8700 Algoritmo de Dijkstra ¿Qué hace? Veamos el algoritmo u_i distancia mas corta del nodo fuente 1 hasta el nodo i
d_ij (>=0) longitud del arco (i,j)
Etiqueta del nodo posterior j
[u_j, i] = [u_i + d_ij, i], d_ij>=0
Paso 0:
Etiquetar el nodo fuente con [0,-]
i=1
Paso i:
Calcular las etiquetas temporales [u_j+d_ij, i] para cada nodo j al que pueda llegarse desde el nodo i, siempre y cuando j no tenga etiqueta permanente. Si el nodo j ya esta etiquetado con [u_j,k] por otro nodo k y si u_i+d_ij<u_j, sustituir [u_j,k] por [u_j+d_ij,i]
Si todos los nodos tienen etiquetas permanentes, detenerse. En caso contrario, seleccionar la etiqueta [u_r,s] que tenga la distancia más corta entre todas las etiquetas temporales. Hacer que i=r y repetir el paso i. 1 2 3 4 5 100 20 15 30 10 60 50 Algoritmo de Floyd Determina la ruta más corta entre dos cualesquiera nodos de la red. i j k d_ij d_jk d_ik d_ij + d_jk < d_ik Paso 0:
Definir las matrices iniciales de distancias D_0 y las secuencias de nodos S_0. Los elementos diagonales se marcan con "-" para indicar que están bloqueados.
k=1
Paso k:
Definir el renglón k y columna k como renglón pivote y columna pivote, aplicar la operación triple a cada elemento d_ij en D_k-1 para toda i y j.
Si se satisface la condición
d_ik + d_kj < d_ij, i!=k, j!=k e i!=j
Crear D_k reemplazando d_ij en D_k-1 por d_ik+d_kj
Crear S_k reemplazando S_ij en S_k-1 por k, luego k=k+1 y repetir el paso k
1 2 3 4 5 3 10 5 6 15 4
Full transcript