Laboratorio 5 Fondamenti di Ricerca Operativa
Prof. E. AmaldiProblema del Set Packing (PLI)
Una giunta comunale deve decidere l’installazione di alcuni inceneritori scegliendo tra 10 aree A
1, . . . , A
10nelle vicinanze di 7 citt`a B
1, . . . , B
7. La seguente tabella mostra, nelle caselle segnate con “*”, se l’area `e vicina alla citt`a; la penultima riga mostra la capacit`a di ogni impianto (in tonnellate all’anno) e l’ultima il costo di installazione, in milioni di euro:
A
1A
2A
3A
4A
5A
6A
7A
8A
9A
10B
1* * * * *
B
2* * * *
B
3* * *
B
4* * * * * * *
B
5* * * *
B
6* * *
B
7* * * * *
Capacit`a 450 720 580 460 660 390 510 1000 830 680
Costo (MEuro) 4 7 8 4 6 9 10 10 8 6
Supponendo che l’amministrazione non voglia piazzare pi` u di un impianto vicino ad ogni citt`a, formulare un modello di Programmazione Lineare Intera che risolve il problema di massimizzare la capacit`a produttiva totale degli impianti aperti, mantenendo il costo totale di installazione inferiore al budget di 25 milioni di euro.
Documento preparato da Pietro Belotti e Leo Liberti
1
Laboratorio 5 Fondamenti di Ricerca Operativa
Prof. E. AmaldiSoluzione
Formulazione .
• Indici:
– sia i un indice sull’insieme delle aree (i ≤ m, dove m `e il numero delle aree, m = 10);
– sia j un indice sull’insieme delle citt`a (j ≤ n, dove n `e il numero delle citt`a, n = 7).
• Parametri:
– sia t
ij= 1 se l’area i `e vicina alla citt`a j e 0 altrimenti (come da tabella nel testo del problema);
– sia c
iil costo di installazione di un inceneritore sull’area i;
– sia C
ila capacit`a di smaltimento di un inceneritore costruito sull’area i;
– sia B il budget disponibile (B = 25).
• Variabili: sia x
i= 1 se un inceneritore viene costruito sull’area i e 0 altrimenti (x
i∈ {0, 1}).
• Funzione obiettivo:
max X
mi=1
C
ix
i• Vincoli:
– (ogni citt`a servita da non pi` u di un inceneritore) per ogni j ≤ n: P
mi=1
t
ijx
i≤ 1;
– (budget): P
mi=1
c
ix
i≤ B.
File modello in AMPL
# Inceneritori set M;
set N;
param costo{M}>=0;
param t{M,N} binary;
param capacita{M} >= 0;
param budget_max >= 0;
var x{M} binary;
Documento preparato da Pietro Belotti e Leo Liberti
2
Laboratorio 5 Fondamenti di Ricerca Operativa
Prof. E. Amaldimaximize cap_totale: sum{i in M} capacita[i] * x[i];
subject to packing{j in N}: sum{i in M} t[i,j] * x[i] <= 1;
subject to budget: sum{i in M} costo[i] * x[i] <= budget_max;
File dati in AMPL
# Inceneritori
set M:=1 2 3 4 5 6 7 8 9 10;
set N:=1 2 3 4 5 6 7;
param costo :=
1 4
2 7
3 8
4 4
5 6
6 9
7 10 8 10 9 8 10 6;
param t : 1 2 3 4 5 6 7 :=
1 0 1 0 1 0 0 0 2 1 1 0 0 0 1 0 3 0 0 0 1 1 0 1 4 0 1 0 0 1 0 0 5 1 0 1 1 0 0 0 6 1 0 0 0 0 0 1 7 1 0 0 1 1 0 1 8 0 1 1 1 0 1 1 9 1 0 1 1 0 1 0 10 0 0 0 1 1 0 1 ; param capacita:=
1 450
2 720
3 580 4 460
5 660
6 390
7 510 8 1000 9 830 10 680;
Documento preparato da Pietro Belotti e Leo Liberti
3
Laboratorio 5 Fondamenti di Ricerca Operativa
Prof. E. Amaldiparam budget_max := 25;
Soluzione
CPLEX 8.1.0: optimal integer solution; objective 1400 5 MIP simplex iterations
0 branch-and-bound nodes cap_totale = 1400.0000 x [*] :=
1 0.0000 2 1.0000 3 0.0000 4 0.0000 5 0.0000 6 0.0000 7 0.0000 8 0.0000 9 0.0000 10 1.0000
;
Documento preparato da Pietro Belotti e Leo Liberti
