Redes Practica 11 4 W430 W430 Lasana Ampl

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc

Curso 2005-06

PRACTICA 11-4-A1 Problema de CPM resuelto con programacin lineal, Winston pg. 430, ejercicio 2. Una compaa planea fabricar un producto que consiste en tres partes (A, B, C). La compaa prev que tomara 5 semanas disear las tres partes y determinar como ensamblarlas para obtener el producto final. Despus la compaa estima que tomara 4 semanas fabricar la parte A, 5 semanas la parte B, y 3 semanas la parte C. Despus de terminar la parte A, la compaa debe probar la parte A (lo cual toma 2 semanas). El proceso de ensamble seguir despus de la manera siguiente: ensamblar las partes A y B (2 semanas) y despus aadir la parte C (1 semana). Despus el producto final debe experimentar pruebas durante 1 semana. Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior mediante programacin lineal.Actividad a b c d e f g h

Actividad Diseo Fabricar la parte A Fabricar la parte B Fabricar la parte C Probar la parte A Suma de A y B Suma de A, B y C Prueba Final

Antecesor a a a b cye dyf g

Tiempo 5 4 5 3 2 2 1 1

Grfico asociado:

3C=5 b=4 e=2

1

a=5

2

c=5

4d=3

f=2

5

g=1

6

h=1

7

Formulacin matemtica: Variables de decisin: xij = instante en el que puede darse en suceso j. Modelo: Minimizar: x[m] Sujeto a: xj 0 j = 1..m x1 = 0 xj xi + t (i, j) (i, j) ar cos

Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 1 de 18


Curso 2005-06

Fichero Practica11-4-A1.mod### Practica 11-4-A1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A1.mod #declaracin de variables param m; # m es el nmero de nodos set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param tiempo {ARCOS} >= 0; var x{NODOS} >= 0; #objetivo de la funcin minimize objetivo: x[m]; #restricciones subject to res1 {(i,j) in ARCOS}: x[j] >= x[i] + tiempo[i,j]; subject to res2: x[1] = 0;

Fichero Practica11-4-A1.dat### Practica 11-4-A1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A1.dat param m := 7; param: ARCOS: tiempo:= 1 2 5 2 3 4 2 4 5 2 5 3 3 4 2 4 5 2 5 6 1 6 7 1;

Fichero Practica11-4-A1.run### Practica 11-4-A1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A1.run reset; model D:\users\Practica11-4-A1.mod; data D:\users\Practica11-4-A1.dat; option solver cplex; Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 2 de 18

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc solve; display objetivo; display x;

Curso 2005-06

Solucin obtenida con el programa AMPL: objetivo = 15 x [*] := 1 0 2 5 3 9 4 11 5 13 6 14 7 15 ;



Curso 2005-06

PRACTICA 11-4-A2 Problema de CPM resuelto con programacin lineal, Winston pg. 430, ejercicio 5.Considrese la lista (simplificada) de las actividades y de los encargados anteriores que intervienen en la construccin de una casa. La lista se proporciona en la tabla siguiente. ACTIVIDAD A B C D E F G DESCRIPCCION Construir los cimientos Construir los muros y techos Construir el tejado Colocar los cables elctricos Colocar las ventanas Colocar revestimiento Pintar la casa ANTECESORES A B B B E C, F TIEMPO 5 8 10 5 4 6 3

Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior mediante programacin lineal. Grfico asociado:

E=4 1 A=5 2 B=8 3

4 C=10 D=5

F=6 5 G=3 6

Formulacin matemtica: Variables de decisin: xij = instante en el que puede darse en suceso j. Modelo: Minimizar: x[m] Sujeto a: xj 0 j = 1..m x1 = 0 xj xi + t (i, j) (i, j) ar cos

Fichero Practica11-4-A2.mod### Practica 11-4-A2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A2.mod Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 4 de 18

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc #declaracin de variables param m; # m es el nmero de nodos set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param tiempo {ARCOS} >= 0; var x{NODOS} >= 0; #objetivo de la funcin minimize objetivo: x[m]; #restricciones subject to res1 {(i,j) in ARCOS}: x[j] >= x[i] + tiempo[i,j]; subject to res2: x[1] = 0;

Curso 2005-06

Fichero Practica11-4-A2.dat### Practica 11-4-A2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A2.dat param m := 6; param: ARCOS: tiempo:= 1 2 5 2 3 8 3 4 4 3 5 10 3 6 5 4 5 6 5 6 3;

Fichero Practica11-4-A2.run### Practica 11-4-A2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A2.run reset; model D:\users\Practica11-4-A2.mod; data D:\users\Practica11-4-A2.dat; option solver cplex; solve; display objetivo; display x;

Solucin obtenida con el programa AMPL objetivo = 26 x [*] := 1 0Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 5 de 18


Curso 2005-06

2 3 4 5 6 ;

5 13 17 23 26



Curso 2005-06

PRACTICA 11-4-A3 Problema de CPM resuelto con programacin lineal. Ejercicio de la lasaa.Usted y varios amigos van a preparar LASAA para la cena. Las tareas a realizar, sus tiempos en minutos y las restricciones de precedencia son: Descripcin Comprar queso mozzarella Rayar el mozzarella Batir dos huevos Mezclar huevos y queso ricotta Picar cebolla y champin Cocinar la salsa de tomate Hervir agua en una vasija Hervir la pasta de lasaa Enjuagar la pasta de lasaa Unir los ingredientes Precalentar el horno Hornear la lasaa Tarea A B C D E F G H I J K L Tiempo 30 5 2 3 7 25 15 10 2 10 15 30 Antecesores A C E G H B, D, F, I J, K

Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior mediante programacin lineal. Grfico asociado:

2 A=30 C=2 1 E=7 G=15 3 F=25 4 I=2

B=5 D=3 7 J=10 8 L=30 9

K=15 H=10 5 6

Formulacin matemtica: Variables de decisin: xij = instante en el que puede darse en suceso j. Modelo: Minimizar: x[m]



Curso 2005-06

Sujeto a: xj 0 j = 1..m x1 = 0 xj xi + t (i, j) (i, j) ar cos

Fichero Practica11-4-A3.mod### Practica 11-4-A3 # Problema de la lasaa # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A3.mod #declaracin de variables param m; # m es el nmero de nodos set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param tiempo {ARCOS} >= 0; var x{NODOS} >= 0; #objetivo de la funcin minimize objetivo: x[m]; #restricciones subject to res1 {(i,j) in ARCOS}: x[j] >= x[i] + tiempo[i,j]; subject to res2: x[1] = 0;

Fichero Practica11-4-A3.dat### Practica 11-4-A3 # Problema de la lasaa # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A3.dat param m := 9; param: ARCOS: tiempo:= 1 2 30 1 3 2 1 4 7 1 5 15 1 8 15 2 7 5 3 7 3 4 7 25 5 6 10 6 7 2 7 8 10 8 9 30; Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 8 de 18


Curso 2005-06

Fichero Practica11-4-A3.run### Practica 11-4-A3 # Problema de la lasaa # Problema de CPM resuelto con programacin lineal # Fichero Practica11-4-A3.run reset; model D:\users\Practica11-4-A3.mod; data D:\users\Practica11-4-A3.dat; option solver cplex; solve; display objetivo; display x;

Solucin obtenida con el programa AMPL objetivo = 75 x [*] := 1 0 2 30 3 2 4 7 5 15 6 33 7 35 8 45 9 75 ;



Curso 2005-06

PRACTICA 11-4-B1 Problema de CPM resuelto con la tcnica del camino ms largo, Winston pg. 430, ejercicio 2. Una compaa planea fabricar un producto que consiste en tres partes (A, B, C). La compaa prev que tomara 5 semanas disear las tres partes y determinar como ensamblarlas para obtener el producto final. Despus la compaa estima que tomara 4 semanas fabricar la parte A, 5 semanas la parte B, y 3 semanas la parte C. Despus de terminar la parte A, la compaa debe probar la parte A (lo cual toma 2 semanas). El proceso de ensamble seguir despus de la manera siguiente: ensamblar las partes A y B (2 semanas) y despus aadir la parte C (1 semana). Despus el producto final debe experimentar pruebas durante 1 semana. Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior con la tcnica del camino ms largo.Actividad a b c d e f g h

Actividad Diseo Fabricar la parte A Fabricar la parte B Fabricar la parte C Probar la parte A Suma de A y B Suma de A, B y C Prueba Final

Antecesor a a a b cye dyf g

Tiempo 5 4 5 3 2 2 1 1

Grfico asociado:

3C=5 b=4 e=2

1

a=5

2

c=5

4d=3

f=2

5

g=1

6

h=1

7

Formulacin matemtica: Variables de decisin: xij = flujo que pasa por el arco (i,j)



Curso 2005-06

Modelo: Mininizar : z =ij ( i , j )ARCOS

c

xij k =1 1 si = 1 si k=m 0 si 1 < k < m

Sujeta a :

kj { j:( k , j )ARCOS }

x

ik {i:( i , k )ARCOS

x

k = ndice de nodos xij 0 para (i, j) ARCOS

Fichero Practica11-4-B1.mod### Practica 11-4-B1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B1.mod param m; set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param oferta {NODOS}; param tiempo {ARCOS} >= 0; var x{(i,j) in ARCOS} binary; maximize objetivo: sum {(i,j) in ARCOS} tiempo[i,j] * x[i,j]; subject to res_1 {k in NODOS}: (sum {(k,j) in ARCOS} x[k,j] - sum {(i,k) in ARCOS} x[i,k]) = oferta[k];

Fichero Practica11-4-B1.dat### Practica 11-4-B1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B1.dat param m := 7; param: oferta:= 1 1 2 0 3 0 4 0 5 0 6 0 7 -1; param: ARCOS: tiempo:= 1 2 5 2 3 4 2 4 5 2 5 3 Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 11 de 18

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc 3 4 5 6 4 5 6 7 2 2 1 1;

Curso 2005-06

Fichero Practica11-4-B1.run### Practica 11-4-B1 # Problema de CPM, Winston, pgina 430, ejercicio 2 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B1.run reset; model D:\users\Practica11-4-B1.mod; data D:\users\Practica11-4-B1.dat; option solver cplex; solve; display objetivo; display x;

Solucin obtenida con el programa AMPL objetivo = 15 x := 12 23 24 25 34 45 56 67 ; 1 1 0 0 1 1 1 1



Curso 2005-06

PRACTICA 11-4-A2 Problema de CPM resuelto con la tcnica del camino ms largo, Winston pg. 430, ejercicio 5.Considrese la lista (simplificada) de las actividades y de los encargados anteriores que intervienen en la construccin de una casa. La lista se proporciona en la tabla siguiente. ACTIVIDAD A B C D E F G DESCRIPCCION Construir los cimientos Construir los muros y techos Construir el tejado Colocar los cables elctricos Colocar las ventanas Colocar revestimiento Pintar la casa ANTECESORES A B B B E C, F TIEMPO 5 8 10 5 4 6 3

Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior mediante la tcnica del camino ms largo. Grfico asociado:

E=4 1 A=5 2 B=8 3

4 C=10 D=5

F=6 5 G=3 6

Formulacin matemtica: Variables de decisin: xij = flujo que pasa por el arco (i,j) Modelo: Mininizar : z =ij ( i , j )ARCOS

c

xij k =1 1 si = 1 si k=m 0 si 1 < k < m

Sujeta a :


x


x




Curso 2005-06

Fichero Practica11-4-B2.mod### Practica 11-4-B2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B2.mod param m; set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param oferta {NODOS}; param tiempo {ARCOS} >= 0; var x{(i,j) in ARCOS} binary; maximize objetivo: sum {(i,j) in ARCOS} tiempo[i,j] * x[i,j]; subject to res_1 {k in NODOS}: (sum {(k,j) in ARCOS} x[k,j] - sum {(i,k) in ARCOS} x[i,k]) = oferta[k];

Fichero Practica11-4-B2.dat### Practica 11-4-B2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B2.dat param m := 6; param: oferta:= 1 1 2 0 3 0 4 0 5 0 6 -1; param: ARCOS: tiempo:= 1 2 5 2 3 8 3 4 4 3 5 10 3 6 5 4 5 6 5 6 3;

Fichero Practica11-4-B2.run### Practica 11-4-B2 # Problema del libro de Winston de la pagina 430, ejercicio numero 5 # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B2.run reset; model D:\users\Practica11-4-B2.mod; data D:\users\Practica11-4-B2.dat; option solver cplex; Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 14 de 18

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc solve; display objetivo; display x;

Curso 2005-06

Solucin obtenida con el programa AMPL objetivo = 26 x := 12 23 34 35 36 45 56 ; 1 1 1 0 0 1 1



Curso 2005-06

PRACTICA 11-4-B3 Problema de CPM resuelto con la tcnica del camino ms largo. Ejercicio de la lasaa.Usted y varios amigos van a preparar LASAA para la cena. Las tareas a realizar, sus tiempos en minutos y las restricciones de precedencia son: Descripcin Comprar queso mozzarella Rayar el mozzarella Batir dos huevos Mezclar huevos y queso ricotta Picar cebolla y champin Cocinar la salsa de tomate Hervir agua en una vasija Hervir la pasta de lasaa Enjuagar la pasta de lasaa Unir los ingredientes Precalentar el horno Hornear la lasaa Tarea A B C D E F G H I J K L Tiempo 30 5 2 3 7 25 15 10 2 10 15 30 Antecesores A C E G H B, D, F, I J, K

Siguiendo las especificaciones de la hoja de prcticas resuelva el problema anterior mediante la tcnica del camino ms largo. Grfico asociado: (30,30) A=30 (0,0) 1 C=2 E=7 (7,10) 2 (2,32) 3 F=25 4 K=15 B=5 (35,35) D=3 7 I=2 G=15 (15,23) H=10 (25,33) 5 6 J=10 8 (45,45) L=30 9 (75,75)

Formulacin matemtica: Variables de decisin: xij = flujo que pasa por el arco (i,j)



Curso 2005-06

Modelo: Mininizar : z =ij ( i , j )ARCOS

c

xij k =1 1 si = 1 si k=m 0 si 1 < k < m

Sujeta a :


x


x


Fichero Practica11-4-B3.mod### Practica 11-4-B3 # Problema de la lasaa # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B3.mod param m; set NODOS := 1..m; set ARCOS within {NODOS,NODOS}; param oferta {NODOS}; param tiempo {ARCOS} >= 0; var x{(i,j) in ARCOS} binary; maximize objetivo: sum {(i,j) in ARCOS} tiempo[i,j] * x[i,j]; subject to res_1 {k in NODOS}: (sum {(k,j) in ARCOS} x[k,j] - sum {(i,k) in ARCOS} x[i,k]) = oferta[k];

Fichero Practica11-4-B3.dat### Practica 11-4-B3 # Problema de la lasaa # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B3.dat param m := 9; param: oferta:= 1 1 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 -1; param: ARCOS: tiempo:= 1 2 30 1 3 2 Enrique Revuelta Navarro Daniel Ballesteros lvarez Pgina 17 de 18

OPTIMIZACION EN REDES Fichero: redes-practica-11-4-W430-W430-lasana-ampl.doc 1 1 1 2 3 4 5 6 7 8 4 5 8 7 7 7 6 7 8 9 7 15 15 5 3 25 10 2 10 30;

Curso 2005-06

Fichero Practica11-4-B3.run### Practica 11-4-B3 # Problema de la lasaa # Problema de CPM resuelto con la tcnica del camino ms largo # Fichero Practica11-4-B3.run reset; model D:\users\Practica11-4-B3.mod; data D:\users\Practica11-4-B3.dat; option solver cplex; solve; display objetivo; display x;

Solucin obtenida con el programa AMPL objetivo = 75 x := 12 13 14 15 18 27 37 47 56 67 78 89 ; 1 0 0 0 0 1 0 0 0 0 1 1


Documents

Redes Practica 11 4 W430 W430 Lasana Ampl