PRÁCTICA 8A
Problema de cobertura de conjuntos, Winston página 478, ejemplo 5, formato1.

ENUNCIADO:

Hay seis ciudades (ciudades 1-6) en el condado de Kilroy. El condado debe determinar en qué lugar construir estaciones de bomberos. El condado quiere construir una mínima cantidad de estaciones de bomberos para asegurar que por lo menos una estación esté dentro de 15 minutos (tiempo de viaje) de cada ciudad. En la tabla 1 se muestran los tiempos requeridos (en minutos) para viajar entre las ciudades del condado de Kilroy. Formule un PE que dirá a Kilroy cuántas estaciones de bomberos habría que construirse y en dónde.

Tabla 1: tiempo requerido para viajar entre ciudades en el condado de Kilroy

DE | HACIA | | Ciudad 1 | Ciudad 2 | Ciudad 3 | Ciudad 4 | Ciudad 5 | Ciudad 6 | Ciudad 1 | 0 | 10 | 20 | 30 | 30 | 20 | Ciudad 2 | 10 | 0 | 25 | 35 | 20 | 10 | Ciudad 3 | 20 | 25 | 0 | 15 | 30 | 20 | Ciudad 4 | 30 | 35 | 15 | 0 | 15 | 25 | Ciudad 5 | 30 | 20 | 30 | 15 | 0 | 14 | Ciudad 6 | 20 | 10 | 20 | 25 | 14 | 0 |

Tabla 2: ciudades dentro de 15 minutos de una ciudad dada

Ciudad 1 | 1, 2 | Ciudad 2 | 1, 2, 6 | Ciudad 3 | 3, 4 | Ciudad 4 | 3, 4, 5 | Ciudad 5 | 4, 5, 6 | Ciudad 6 | 2, 5, 6 | La tabla 2 muestra la relación de localidades que pueden comunicarse con cada ciudad respectivamente en 15 minutos o menos.

Formulación matemática:
Para cada ciudad se debe determinar si se construye una estación de bomberos o no. Así, definimos las variables dicotómicas y1, y 2, y 3, y 4, y 5, y 6 {0,1} como: y j j=1,...,6

Entonces el número total de estaciones de bomberos que se construyen está dado por y 1+ y 2+ y 3 + y 4 + y 5 + y 6 y la función objetivo de Kilroy es:
Minimizar z = y 1+ y 2+ y 3 + y 4 + y 5 + y 6
Para asegurar que haya una estación de bomberos dentro de 15 minutos de cada ciudad, tenemos las siguientes restricciones: y 1 + y 2 >=1 (Restricción de la ciudad 1) y 1 + y 2 + y 6 >=1 (Restricción de la ciudad 2) y 3 + y 4 >=1 (Restricción de la ciudad 3) y 3 + y 4 + y 5 >=1 (Restricción de la ciudad 4) y 4 + y 5 + y 6 >=1 (Restricción de la ciudad 5) y 2 + y 5 + y 6 >=1 (Restricción de la ciudad 6)

Fichero práctica8a.mod
### Práctica 8a
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato 1
# Fichero practica8a.mod

# Declaración de variables

var y1 binary; var y2 binary; var y3 binary; var y4 binary; var y5 binary; var y6 binary;

# Función objetivo minimize objetivo: y1+y2+y3+y4+y5+y6 ;

# Restricciones asociadas a la distancia entre ciudades subject to res_ciudad_1: y1+y2 >= 1; subject to res_ciudad_2: y1+y2+y6 >= 1; subject to res_ciudad_3: y3+y4 >= 1; subject to res_ciudad_4: y3+y4+y5 >= 1; subject to res_ciudad_5: y4+y5+y6 >= 1; subject to res_ciudad_6: y2+y5+y6 >= 1;

Fichero practica8a.run

### Práctica 8a
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato 1
# Fichero practica8a.run reset; model A:\practica8a.mod; option solver cplex; solve; display objetivo; display y1,y2,y3,y4,y5,y6;

Solución obtenida con el programa AMPL:

CPLEX 8.0.0: optimal solution; objective 2
4 dual simplex iterations (0 in phase I) objetivo = 2 y1 = 0, y2 = 1, y3 = 0, y4 = 1, y5 = 0, y6 = 0;

PRÁCTICA 8B
Problema de cobertura de conjuntos, Winston página 478, ejemplo 5, formato2.

Fichero práctica8b.mod
### Práctica 8b
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato 2
# Fichero practica8b.mod

# Declaración de variables param m; param n;

set CLIENTES:=1..m; set SERVIDORES:=1..n;

var y{SERVIDORES} binary;

# Función objetivo minimize objetivo: sum {j in SERVIDORES} y[j] ;

# Restricciones asociadas a la distancia entre las ciudades subject to res_ciudad_1: y[1]+y[2] >= 1; subject to res_ciudad_2: y[1]+y[2]+y[6] >= 1; subject to res_ciudad_3: y[3]+y[4] >= 1; subject to res_ciudad_4: y[3]+y[4]+y[5] >= 1; subject to res_ciudad_5: y[4]+y[5]+y[6] >= 1; subject to res_ciudad_6: y[2]+y[5]+y[6] >= 1;

Fichero práctica8b.dat
### Práctica 8b
# Problema del libro del Winston página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato2
# Fichero practica8b.dat

param m:=6; param n:=6;

Fichero práctica8b.run
### Práctica 8b
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato 2
# Fichero practica8b.run

reset; model A:\redes\practica8b.mod; data A:\redes\practica8b.dat; option solver cplex; solve; display objetivo; display y;

Solución obtenida con el programa AMPL:

CPLEX 8.0.0: optimal integer solution; objective 2
0 MIP simplex iterations
0 branch-and-bound nodes objetivo = 2 y [*] : = 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 0 | 1 | 0 | 0 |

PRÁCTICA 8C
Problema de cobertura de conjuntos, Winston página 478, ejemplo 5, formato1.
Solucionar el problema añadiendo una matriz de distancias binaria

Formulación matemática:
A los datos del problema inicial se le añaden un vector kj de costes fijos que representa el coste de construir el servidor en la ciudad j. También se añade una matriz de costes variables ci,j que representa el coste cuando al cliente i le atiende el servidor j. Así tenemos:

dij = distancia funcional de la ciudad i a la ciudad j.

Vector de costes fijos: kj 1 | 2 | 3 | 4 | 5 | 6 | 1 | 5 | 3 | 7 | 3 | 2 |

Matriz de costes variables: cij | SERVIDORES | | 1 | 2 | 3 | 4 | 5 | 6 | CLIENTES | 1 | 7 | 5 | 9 | 12 | 8 | 5 | | 2 | 6 | 3 | 4 | 4 | 8 | 8 | | 3 | 5 | 8 | 4 | 5 | 9 | 6 | | 4 | 3 | 3 | 21 | 5 | 8 | 4 | | 5 | 9 | 1 | 1 | 7 | 4 | 5 | | 6 | 9 | 5 | 5 | 6 | 6 | 6 |

Matriz de distancias: dij | SERVIDORES | | 1 | 2 | 3 | 4 | 5 | 6 | CLIENTES | 1 | 0 | 10 | 20 | 30 | 30 | 20 | | 2 | 10 | 0 | 25 | 35 | 20 | 10 | | 3 | 20 | 25 | 0 | 15 | 30 | 20 | | 4 | 30 | 35 | 15 | 0 | 15 | 25 | | 5 | 30 | 20 | 30 | 15 | 0 | 14 | | 6 | 20 | 10 | 20 | 25 | 14 | 0 |

Tope=15 es la distancia máxima que se permite entre cualquier ciudad y las estaciones de bomberos.
Así tenemos que la función objetivo es la siguiente:

Minimizar i=1,...,m j=1,...,n

Sujeta a las siguientes restricciones:

1. yj 0,1 j =1,...,n

2. xij 0,1 i =1,...,m j =1,...,n

3. i =1,...,m (Cada cliente debe poder ser atendido al menos por un servidor)

4. xij <= yj j =1,...,n (si un cliente i es atendido por el servidor j, este debe estar activo)

5. dij xij <= tope i =1,...,m j =1,...,n

Fichero práctica8c.mod
### Práctica 8c
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos con costes
# Fichero practica8c.mod

# Declaración de variables param m; param n;

set CLIENTES:=1..m; set SERVIDORES:=1..n;

param costes_fijos {SERVIDORES}>=0; param costes_var {CLIENTES,SERVIDORES}>=0; param distancias {CLIENTES,SERVIDORES}>=0; param tope;

var y{SERVIDORES} binary; var x{CLIENTES, SERVIDORES} binary;

# Función objetivo minimize objetivo:
(sum {j in SERVIDORES} costes_fijos[j]*y[j]) + (sum{i in CLIENTES, j in SERVIDORES} costes_var[i,j]*x[i,j] ) ;

# Restricciones subject to res_tres{i in CLIENTES}: (sum {j in SERVIDORES} x[i,j]) >= 1; subject to res_cuatro {i in CLIENTES, j in SERVIDORES}: x[i,j] <= y[j]; subject to res_cinco {i in CLIENTES, j in SERVIDORES}: distancias[i,j]*x[i,j] <=tope ;

Fichero práctica8c.dat
### Práctica 8c
# Problema del libro del Winston página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato1
# Fichero practica8c.dat

param m:=6; param n:=6;

# Vector de costes fijos inventados param costes_fijos:=
1 1
2 5
3 3
4 7
5 3
6 2;

# Matriz de costes variables inventados param costes_var: 1 2 3 4 5 6:=
1 7 5 9 12 8 5
2 6 3 4 4 8 8
3 5 8 4 5 9 6
4 3 3 21 5 8 4
5 9 1 1 7 4 5
6 9 5 5 6 6 6;

# Matriz de distancias param distancias: 1 2 3 4 5 6:=
1 0 10 20 30 30 20
2 10 0 25 35 20 10
3 20 25 0 15 30 20
4 30 35 15 0 15 25
5 30 20 30 15 0 14
6 20 10 20 25 14 0;

# Tope param tope:=15;

Fichero práctica8c.run
### Práctica 8c
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos con costes
# Fichero practica8c.run

# include A:\redes\practica8c.run;

reset; model A:\redes\practica8c.mod; data A:\redes\practica8c.dat; option solver cplex; solve; display objetivo; display y; display x;

Solución obtenida con el programa AMPL:

CPLEX 8.0.0: optimal integer solution; objective 40
13 MIP simplex iterations
0 branch-and-bound nodes objetivo = 40 y [*] : = 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 1 | 0 | 1 | 0 |

x [*,*] : = | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 1 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 1 | 0 | 5 | 0 | 0 | 0 | 0 | 1 | 0 | 6 | 0 | 1 | 0 | 0 | 0 | 0 |

PRÁCTICA 8D
Problema de cobertura de conjuntos, Winston página 478, ejemplo 5, formato1.
Solucionar el problema añadiendo una matriz de distancias binaria para m clientes (igual que la práctica anterior, pero con la restricción cuatro distinta).

Formulación matemática:
Es la misma que en la práctica 8C, pero cambiando la cuarta restricción:
4. <= m*yj j =1,...,n (si un cliente i es atendido por el servidor j, este debe estar activo)

Fichero práctica8d.mod
### Práctica 8d
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos con costes
# Fichero practica8d.mod

# Declaración de variables param m; param n;

set CLIENTES:=1..m; set SERVIDORES:=1..n;

param costes_fijos {SERVIDORES}>=0; param costes_var {CLIENTES,SERVIDORES}>=0; param distancias {CLIENTES,SERVIDORES}>=0; param tope;

var y{SERVIDORES} binary; var x{CLIENTES, SERVIDORES} binary;

# Función objetivo minimize objetivo:
(sum {j in SERVIDORES} costes_fijos[j]*y[j]) + (sum{i in CLIENTES, j in SERVIDORES} costes_var[i,j]*x[i,j] ) ;

# Restricciones subject to res_tres{i in CLIENTES}: (sum {j in SERVIDORES} x[i,j]) >= 1; subject to res_cuatro {j in SERVIDORES}: (sum{i in CLIENTES}x[i,j] )<=m* y[j]; subject to res_cinco {i in CLIENTES, j in SERVIDORES}: distancias[i,j]*x[i,j] <=tope ;

Fichero práctica8c.dat
### Práctica 8d
# Problema del libro del Winston página 478, ejemplo 5
# Problema de cobertura de conjuntos en formato1
# Fichero practica8d.dat

param m:=6; param n:=6;

# Vector de costes fijos inventados param costes_fijos:=
1 1
2 5
3 3
4 7
5 3
6 2;

# Matriz de costes variables inventados param costes_var: 1 2 3 4 5 6:=
1 7 5 9 12 8 5
2 6 3 4 4 8 8
3 5 8 4 5 9 6
4 3 3 21 5 8 4
5 9 1 1 7 4 5
6 9 5 5 6 6 6;

# Matriz de distancias param distancias: 1 2 3 4 5 6:=
1 0 10 20 30 30 20
2 10 0 25 35 20 10
3 20 25 0 15 30 20
4 30 35 15 0 15 25
5 30 20 30 15 0 14
6 20 10 20 25 14 0;

# Tope param tope:=15;

Fichero práctica8d.run
### Práctica 8d
# Problema del libro de Winston, página 478, ejemplo 5
# Problema de cobertura de conjuntos con costes
# Fichero practica8d.run

# include D:\users\practica8d.run;

reset; model D:\users\practica8d.mod; data D:\users\practica8d.dat; option solver cplex; solve; display objetivo; display y; display x;

Solución obtenida con el programa AMPL:
CPLEX 8.0.0: optimal integer solution; objective 40
13 MIP simplex iterations
0 branch-and-bound nodes objetivo = 40 y [*] : = 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 1 | 0 | 1 | 0 |

x [*,*] : = | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 3 | 0 | 0 | 1 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 1 | 0 | 5 | 0 | 0 | 0 | 0 | 1 | 0 | 6 | 0 | 1 | 0 | 0 | 0 | 0 |