MODELOS DE REDES

Andrés Felipe Osorio MurielUniversidad Icesi 2011 - 1

MODELOS DE REDES

•Ruta mas corta•Árbol de expansión mínimo•Flujo Máximo•Flujo de costo mínimo•CPM – Modelo de Ruta Crítica

RUTA MAS CORTA

EJERCICIO

O

A

C F

B

G

E

D

H

I

T

4

3 4

7

4

56

3

6

2

2

5

2 22

8

213

5

4

5

ARBOL DE EXPANSIÓN MÍNIMA

PROBLEMA DE FLUJO MAXIMO

PROBLEMA DE FLUJO MAXIMO

Five male and five female entertainers are at a dance. The goal of the matchmaker is to match each woman with a man in a way that maximizes the number of people who are matched with compatible mates. Table 10 describes the compatibility of the entertainers.Draw a network that makes it possible to represent the problem of maximizing the number of compatible pairings as a maximum-flow problem.

PROBLEMA DE FLUJO MAXIMO

The Hatfields, Montagues, McCoys, and Capulets are going on their annual family picnic. Four cars are available to transport the families to the picnic. The cars can carry the following number of people: car 1, four; car 2, three; car 3, three; and car 4, four. There are four people in each family, and no car can carry more than two people from any one family. Formulate the problem of transporting the maximum possible number of people to the picnic as a maximum-flow problem.

PROBLEMA DE RUTA MAS CORTA

A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet. The demand and size of each box is given in Table 7. The variable cost (in dollars) of producing each box is equal to the box’s volume. A fixed cost of $1,000 is incurred to produce any of a particular box. If the company desires, demand for a box may be satisfied by a box of larger size. Formulate and solve a shortest-path problem whose solution will minimize the cost of meeting the demand for boxes.

FLUJO DE COSTO MÍNÍMO

CPM Y PERT

• PERT: Program Evaluation and Review Technique– Creado por la US Navy en un proyecto – Misil Polaris – que involucraba

3000 diferentes contratistas

• CPM: Critical Path Method– Desarrollado para la programación de mantenimientos totales en

plantas de procesamiento de químicos.

• PERT / CPM es el método que expone la ruta crítica de un proyecto; esto es, las actividades que limitan la duración de

un proyecto.

REGLAS - AOC

1. El nodo 1 representa el comienzo del proyecto2. Se debe incluir nodo de terminación del proyecto3. Se numeran todos los nodos de tal forma que el nodo donde termina

una actividad tenga un numero mas alto que el nodo donde empieza4. Una actividad no debe ser representada por mas de un arco en la red5. Dos nodos pueden estar conectados por mas de un arco

1 2 3A B

1

2

3

B

4C

A

REGLAS

1 2

1

2 3

B

3C

A

3

A

B

1 2

A

B Ficticio

EJEMPLO

• Widgetco está a punto de introducir un nuevo producto (Producto 3). Una unidad del producto 3 se produjo ensamblando 1 unidad del producto 1 y 1 unidad del producto 2. Antes que comience la producción de 1 y 2, se debe comprar las materias primas y capacitar a los trabajadores. Antes de poder ensamblar 1 y 2 en el producto 3, es necesario inspeccionar el producto terminado 2. La siguiente tabla presenta la lista de actividades, sus predecesores y sus tiempos de duración.

Actividad Descripción Predecesor DuraciónA Capacitar trabajadores - 6B Comprar MP - 9C Producir PT 1 A,B 8D Producir PT 2 A,B 7E Inspeccionar PT2 D 10F Ensamblar 1y2 C,E 12

DEFINICIONES

• Tiempo de evento inicial ET(i), es el primer momento en que ocurre el evento que corresponde al nodo i.

• ET (j) = max { ET(i)+Tij}

• Tiempo de evento tardío LT(i), es el ultimo momento en que puede ocurrir un evento que corresponde al nodo i sin retrasar la terminación del proyecto.

• LT (i) = min { LT(j)- Tij}

DEFINICIONES

• Tiempo libre total, cantidad en la que se podría retrasar la actividad representada por (i,j) mas allá de su tiempo de inicio mas proximo sin retrasar la terminación del proyecto

• TF (i,j) = LT(j)-ET(i) -Tij

• Ruta Critica• Ruta formada por las actividades criticas• Actividad critica, es aquella donde TF(i,j) =0

EJERCICIO

MODELO PL PARA HALLAR LA TUTA CRÍTICA

• Xj = Tiempo en el que ocurre el evento correspondiente al nodo j

• Se sabe que para cada ocurra el nodo j debe haber ocurrido antes el nodo i, y completar la actividad (i,j ).

• Entonces para cada arco se debe cumplir lo siguiente:• Xj >= Xi + Tij y la función objetivo será minimizar el tiempo

entre el inicio del evento 1 y el inicio del evento final….

• Z= Xf-X1

EJEMPLO

Actividad Descripción Predecesor DuraciónA Capacitar trabajadores - 6B Comprar MP - 9C Producir PT 1 A,B 8D Producir PT 2 A,B 7E Inspeccionar PT2 D 10F Ensamblar 1y2 C,E 12

1

2

3 65

4

A 6

B 9

Fic 0

C 8

D 7 E 10

F 12

MODELO PL PARA HALLAR LA TUTA CRÍTICA

• Para el ejemplo estudiado se tendría lo siguiente:• Min Z = X6-X1

• Sujeto a:• X3>=X1+6• X2>=X1+9• X5>=X3+8• X4>=X3+7• X5>=X4+10• X6>=X5+12• X3>=X2

ACELERACIÓN DEL PROYECTO

• Suponga que el producto de la competencia saldra en 26 dias, esto obliga a Widgetco a tener listo su producto antes de los 38 días inicialmente calculados, se espera entonces poder terminar el producto en 25 días.

• Suponga que al asignar recursos adicionales a una actividad, Widgetco reduce la duración de una actividad hasta por 5 dias el costo por día por reducir cada actividad se presenta a continuación:

A B C D E F10 20 3 30 40 50

MODELO PL PARA HALLAR LA TUTA CRÍTICA

• A = número de días que se reduce la duración de la actividad A• .• .• F = número de días que se reduce la duración de la actividad F• Xj = Tiempo en el que ocurre el inicio del evento correspondiente al nodo j

• Min Z = 10A + 20B + 3C + 30D + 40E + 50F• Sujeto a:

X3>=X1+6 – A A<=5X2>=X1+9 – B B<=5X5>=X3+8 – C C<=5X4>=X3+7 – D D<=5X5>=X4+10 – E E<=5X6>=X5+12 – F F<=5X3>=X2

• A,B,C,D,E,F >=0

PERT

CPM supone que la duración de las actividades es deterministica,sin embargo es muchos casos esto no es del todo cierto. PERT esun intento por involucrar la incertidumbre en la duración de lasactividades y para esto el gerente del proyecto debe estimar 3valores:

• a = estimación de la duración de la actividad en las condiciones mas favorables (mejor escenario)

• b = estimación de la duración de la actividad en las condiciones menos favorables (peor escenario)

• m = Valor mas probable para la duración de la actividad (escenario mas probable

PERT

36

)( )var(

6

4 )(

2abTij

bmaTijE

a b mB (1,2) 5 13 9A (1,3) 2 10 6C (3,5) 3 13 8D (3,4) 1 13 7E (4,5) 8 12 10F (5,6) 9 15 12

Actividad

Calcular E(Tij) y varTijCalcular E(CP) , var CP y desviación estándar de CP

PERT

Suponiendo que la ruta crítica se conserva …. Cual es la probabilidad de completarel proyecto en 35 días?

%1313.0)12.1(69.2

3835

2.69

38-CP)35(

ZPPCPP

EJERCICIO

Actividad Descripción Predecesores a b mA Encontrar el sitio - 2 4 3B Encontrar a los ingenieros A 1 3 2C Contratar el acto de apertura A 2 10 6D Poner anuncios de radio y TV C 1 3 2E Preparar agentes de boletos A 1 5 3F Preparar lo relacionado con la electronica B 2 4 3G Imprimir anuncios C 3 7 5H Organizar el transporte C 0,5 1,5 1I Ensayos F,H 1 2 1,5J Detalles de ultimo minuto I 1 3 2

El promotor de un concierto de Rock en Indianápolis debe llevar a cabo lastareas mostradas en la tabla de abajo antes de celebrar el concierto(duraciones en días).a) Trace la red del proyectob) Determine la trayectoria críticac) Si el promotor anticipado quiere tener una probabilidad del 99% de completar las preparaciones

el 30 de julio , Cuando debe comenzar el trabajo de hallar un sitio para el concierto?d) Prepare el PL que puede ser usado para encontrar la ruta critica