• Author / Uploaded
• Cecilia Aquino

Citation preview

TRABAJO PRACTICO DE REFORZAMIENTO INVESTIGACION OPERATIVA 2 TEORIA DE REDES 1. Dado la siguiente red determine el Camino más corto desde el nodo 1 al nodo 8. (12;2) (4;1) (29;5) (35;4)X (0;-)

(15;3)

(38;7) X (30;4)X (29;6)

(3;1) (7;3) (17,4)X 1-8=1-3-6-8

Distancia total 29km 2. Dada la siguiente Red, obtenga el árbol de expansión mínima: 200 224

2

3

1 300

200 283

7

4 400

6 5

Distancia 1607

4. Encuentre la Ruta más Corta desde el nodo inicial 1 al nodo 8. (12;2)

(29;5) (35;4)X

(4;1)

(0;-) (38;7)X (30;4)X (29;6)

(3;1) (7;3) (17;4)X

D1-8= 1-3-6-8

Distancia 29

6. Dado la siguiente Red, determine por medio del Algoritmo de Dijkstra:  un camino de peso mínimo del vértice D al vértice E  un camino de peso mínimo del vértice D al vértice H  un camino de peso mínimo del vértice d al vértice F

a) Un camino de de peso minimo de vértice D al vértice E dD-E= D-A-C-E peso minimo 8 b) Un camino de peso minimo del vértice D al vértice H Hay dos opciones Opción 1: dD-H= D-A-B-H peso minimo 12 Opción 2: : dD-H= D-A-B-H peso minimo 12 c) Un camino de de peso minimo de vértice d al vértice F No existe el vértice d

7. Dada la siguiente tabla de actividades determine: a) Red del proyecto. b) Tabla de los Tiempos más cercanos y más lejanos. c) Ruta Crítica y Duración del proyecto.

a) Red del proyecto

0

1

2

3

4

5

6

7

8 E

A

D

1

2

5 B

3

4

2

3

D 3

4

5

9

10 6

Holgura de las actividades Actividades

Li-(Ei+Tij)= Hij

1,2 1,3 2,4 2,6 3,2 3,5 4,6 5,4

5-(0+5)=0 5-(0+3)=2 9-(5+2)=2 9-(3+0)=2 5-(0+5)=0 9-(3+3)=3 9-(7+0)=2 9-(6+0)=3

C) ruta critica y duración del proyecto E 4

5 1

2 A

El proyecto durara 9 dias

6

8. Una empresa dedicada a la industria tiene que ejecutar la siguiente lista de actividades del problema.

Se pide determinar: a) Red del Proyecto b) Ruta Critica c) Tiempo de Terminación del Proyecto.

Red de proyecto

0

1

2 3 4 5 6

C

9 10 11 12 13 14 15 16

F

4

3

E

5

A

1

7 8

2

3

6

6

D

4

7

5

B

G

3 8

6

8

Holgura de las actividades Actividades

Li-(Ei+Tij)= Hij

1,2 1,3 1,4 2,5 2,6 3,8 4,7 5,3 6,8 7,6

5-(0+4)=1 8-(0+8)=0 9-(0+3)=6 8-(4+3)=1 14-(4+6)=4 14-(8+6)=0 14-(3+5)=6 8-(7+0)=1 14-(10+0)=4 14-(8+0)=6 D) TIEMPO DE DURACION

b) Ruta critica

14 DIAS 1 B

G 3

8

8 6

9. El departamento de investigación y desarrollo planea competir por un gran proyecto para un nuevo sistema de comunicación en aviones comerciales. La tabla siguiente muestra las actividades, tiempos y secuencias requeridas: Se pide determinar: a) Red del Proyecto b) Ruta Critica c) Tiempo de Terminación del Proyecto

Holgura de las actividades Actividades

Li-(Ei+Tij)= Hij

1,2 2,3 2,4 2,5 3,6 4,7 5,9 5,7

3-(0+3)=0 9-(3+2)=4 7-(3+4)=0 7-(3+4)=0 15-(5+6)=4 13-(7+6)=0 15-(7+3)=5 13-(7+0)=6

5,4 6,8 7,8 8,10 9,6

7-(7+0)=0 15-(11+0)=4 15-(13+2)=0 18-(15+3)=0 15-(10+0)=5

RUTA CRITICA 1

Duracion de proyecto F

C

4 1

7

6

4

A

G

I

2

18 dias

10

8 3

2 3

RUTA CRÍTICA 2 F

4

A

1

D

2 3

3 4

6

I

G

7

10

8 2

3

TEORIA DE GRAFOS 12. Dibujar el grafo G NO DIRIGIDO según los siguientes conjuntos. - V = {a, b, c, d, e} - A = {ab, bc, be, ed, de, ad} G=(V;A) a

b

c

1 d

e

13.Sea el conjunto de Vertices V= {a, b, c, d, e, f} y aristas A = {ab, ba, bc, ac, bd, ed, fe, cf} a) Construya el grafo DIRIGIDO. a

b

d

1 c

F

e

b) Obtenga el grado de cada vértice. G(a) 1 G(b) 1 G(c) 2 G(d) 2 G(e) 1 G(f) 1 8 c) Determine el grado del grafo. G(g)= 8

14. Dado el siguiente grafo G: a) Definir el grado de cada uno de los vértices. b) Determine las trayectorias que se pueden formar desde el nodo 1 al nodo 10. Determine por lo menos 3 caminos alternativos.

a) Definir el grado de cada uno de los vértices. G(7) = 7 G(1) = 1 G(8) = 3 G(2) = 2 G(9) = 4 G(3) = 5 G(10) = 1 G(4) = 6 G(5) = 3 G(6) = 4

  

b)Determine las trayectorias que se pueden formar desde el nodo 1 al nodo 10. Determine por lo menos 3 caminos alternativos 1-3-6-9-4-2-5-8-7-10 1-3-9-6-4-2-5-8-7-10 1-3-7-10

15. Dado el siguiente grafo G, Determine: a) El conjunto de vértices y aristas V= (1,2,3,4,5,6) A=( (1,2);(1,5);(2,1);(2,3);(2,5);(3,2);(3,4);(4,3);(4,5);(4,6);(5,1);(5,4);(5,2);(6,4) } b) El grado de cada vértice G(1) = 2 G(2) = 3 G(3) = 2 G(4) = 3 G(5) = 3 G(6) = 1

c) El grado del Grafo G(g)= 14 d) Recorridos desde 1 a 6.  1-5-2-3-4-6  1-5-4-6  1-2-3-4-6

e) Cuál es el nro. máximo de aristas que puede contener para que sea un grafo completo. Indique gráficamente. 1

6

2

5

3

Kn= n(n-1)/2 Kn=6(6-1)/2 Kn=15

4

16. A una fiesta de final de carrera acuden un grupo de amigos cuyos nombres son: Alicia (A), Berta (B), Celia (C), Dana (D), Elena (E), Felipe (F), Gerardo (G), Hilario (H), Ignacio (I) y Jacobo (J). Cada chica solo acepta bailar con un compañero segun el esquema siguiente:  A acepta como pareja a F,G,H.  B acepta como pareja a G,I.  C acepta como pareja a F,G.  D acepta como pareja a G,I,J.  E acepta como pareja a F,G,H

a) Dibujar el grafo que modele la situacion anterior, representando cada persona por un vértice. C

J

F D

A G

H

E

B

I

b) Determine si el grafo resultante es un grafo completo. Si no lo es, explique porque no es un grafo completo. No es un grafo completo porque no cumple con la formula tiene 13 aristas y Kn=45 deberia tener 45 aristas 17. Dado el siguiente grafo G, encontrar en él: a) Conjunto de Vertices y Aristas b) El numero máximo de aristas que puede tener el grafo e indique cuales son. c) El grado de cada vertice. d) El grado del grafo. e) Nueva trayectoria propuesta .

a) V=(A,B,C,D) E=( (A,B);(A,C);(B,A);(B,A);(B,D);(D,A);(D,B)}

Kn=4(4-1)/2

A

b)

Kn=6 C D

c) G(A) = G(B) = G(C) = G(D) =

3 3 2 2

d) G(g)= 10 e)  A-B-D  A-D  A-C-B-D

B

El numero mx de aristas es de 6

Parte Teorica 18. Cuales son los tipos de grafos?  Grafo simple  Grafo dirigido  Grafo no dirigido  Multígrafo o psudografo  Grafo completo  Grafo etiquetado 20. Que representan los nodos? Un nodo corresponde a un vértice de una red. El nodo es un evento que determina el inicio y el final de una tarea. 21. Cual es el objetivo de estudiar los modelos de Redes? Permite la optimización de un modelo por medio de una representación grafica 22. En que consiste el modelo de redes de planificación, control y evaluación de proyecto? En una buena administración de proyectos 23. Cual es el objetivo de realizar una buena planificación de proyecto? Minimizar el numero de dificultades que puede incurrir 24. A que se llama grafo completo? Un grafo completo es donde cada vértice esta siempre conectado con una arista 25. Que es una trayectoria o camino? Se llama asi a la secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente 26. Las aristas que representan? Corresponden a una relación entre dos vértices de un grafo. Son representadas por líneas o por flechas. 27. Que es una actividad ficticia? Son las actividades que no consumen recursos y están asociadas generalmente a eventos ficticios, tiene como propósito establecer las relaciones de procedencia pero no tiene ningún tiempo asignado. 28. El algoritmo de Dijkstra en que casos se utiliza? Es en casos de problemas de la ruta más corta 29. Como se determina la Ruta Critica de un proyecto? Es el camino o secuencia de actividades conectadas que conducen el proyecto desde un inicio hasta el final de mismo tomando en cuenta el mayor tiempo 30. La tabla de Holgura de las actividades para que me sirve? Es el tiempo libre existente es decir el tiempo que se demora sin afectar la fecha de presentación del proyecto.