Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Concentratori - 18.11.02 ::
Testo del problema
Una rete telematica connette con cavi in fibra ottica diverse stazioni. Ciascuna di esse può ospitare un concentratore, ossia un punto di raccolta di messaggi provenienti da un certo sottinsieme di stazioni della rete. I concentratori devono essere localizzati in modo che ogni stazione sia assegnata ad un concentratore.
Ad ogni stazione della rete è associata una domanda, che rappresenta la quantità di traffico in ingresso o uscita da quella stazione. Ogni concentratore ha una capacità, che può dipendere da dove il concentratore è localizzato. E’ necessario che la somma delle domande delle stazioni assegnate allo stesso concentratore non ecceda la capacità del concentratore stesso.
Ogni assegnamento di una stazione i ad un concentratore j ha un costo che è dato dal prodotto tra la quantità di traffico della stazione i e il costo unitario di collegamento tra la stazione i e la stazione che ospita il concentratore j. Si vogliono minimizzare i costi complessivi.
I concentratori sono disponibili in numero limitato.
Formulare il problema, classificarlo e risolverlo con i dati del file CONCENTR.TXT.
Dati
Le stazioni sono 6.
============================================================
Tabella 1: Costi unitari di allocazione
Concentratore 1 2 3 4 5 6
Stazione
1 12 45 18 27 19 18
2 38 34 18 28 34 28
3 11 10 15 34 23 10
4 37 39 31 28 29 21
5 15 34 11 20 28 15
6 12 30 20 18 27 24
============================================================
Tabella 2: Domande associate alle stazioni
Stazione Domanda
1 100
2 150
3 100
4 200
5 200
6 300
============================================================
Tabella 3: Capacità dei concentratori
Stazione Capacità
1 650
2 500
3 550
4 450
5 550
6 600
============================================================
I concentratori disponibili sono 2.
Formulazione del problema
Dati
- s = 6 (numero stazioni)
- c = 2 (numero concentratori)
- cosij (costo unitario collegamento tra la stazione con concentratore i=1..2 e la stazione j=1..6)
- domj (domanda associata alla stazione j=1..6)
- capi (capacità del concentratore i=1..2)
Variabili
- xj (variabile binaria che indica se nella stazione j=1..6 c'è un concentratore)
- yij (variabile binaria che indica se la stazione j=1..6 è collegata alla stazione con concentratore i=1..2)
Funzione obiettivo
min (somma)j domj * cosij * yij (per ogni i)
Vincoli
- vincolo sul numero di concentratori disponibili:
(somma)j xj <= 2
- vincoli di allocazione per ogni stazione ad un unico concentratore:
(somma)j yij = 1 (per ogni i)
- vincoli di capacità del concentratore. Ciò che vogliamo dire è che:
(somma)i domj * yij <= capi * xj
ma dato che formuleremo il problema in Lindo, spostiamo le incognite a sinistra e i termini noti a destra, così da ottenere:
[(somma)i domj * yij] - capi * xj <= 0
Lindizzazione del problema
! esercizio - Concentratori
! variabili: y(j) = indica se nella stazione j c'è un concentratore (binaria)
! y(i,j) = indica se la stazione j è collegata alla stazione
! con concentratore i (binaria)
! le variabili sono binarie
! funzione obiettivo
min 1200 y11 + 4500 y12 + 1800 y13 + 2700 y14 + 1900 y15 + 1800 y16
+ 5700 y21 + 5100 y22 + 2700 y23 + 4200 y24 + 5100 y25 + 4200 y26
+ 1100 y31 + 1000 y32 + 1500 y33 + 3400 y34 + 2300 y35 + 1000 y36
+ 7400 y41 + 7800 y42 + 6200 y43 + 5600 y44 + 5800 y45 + 4200 y46
+ 3000 y51 + 6800 y52 + 2200 y53 + 4000 y54 + 5600 y55 + 3000 y56
+ 3600 y61 + 9000 y62 + 6000 y63 + 5400 y64 + 8100 y65 + 7200 y66
st
! vincolo numero di concentratori disponibili
conDisp) y1 + y2 + y3 + y4 + y5 + y6 <= 2
! vincoli di allocazione per ogni stazione ad un unico concentratore
alloSt1) y11 + y12 + y13 + y14 + y15 + y16 = 1
alloSt2) y21 + y22 + y23 + y24 + y25 + y26 = 1
alloSt3) y31 + y32 + y33 + y34 + y35 + y36 = 1
alloSt4) y41 + y42 + y43 + y44 + y45 + y46 = 1
alloSt5) y51 + y52 + y53 + y54 + y55 + y56 = 1
alloSt6) y61 + y62 + y63 + y64 + y65 + y66 = 1
! vincoli di capacità del concentratore
capCon1) 100 y11 + 150 y21 + 100 y31 + 200 y41 + 200 y51 + 300 y61 - 650 y1 <= 0
capCon2) 100 y12 + 150 y22 + 100 y32 + 200 y42 + 200 y52 + 300 y62 - 500 y2 <= 0
capCon3) 100 y13 + 150 y23 + 100 y33 + 200 y43 + 200 y53 + 300 y63 - 550 y3 <= 0
capCon4) 100 y14 + 150 y24 + 100 y34 + 200 y44 + 200 y54 + 300 y64 - 450 y4 <= 0
capCon5) 100 y15 + 150 y25 + 100 y35 + 200 y45 + 200 y55 + 300 y65 - 550 y5 <= 0
capCon6) 100 y16 + 150 y26 + 100 y36 + 200 y46 + 200 y56 + 300 y66 - 600 y6 <= 0
end
! definiamo le 36 + 6 variabili binarie
int 42
Torna alla pagina di Ricerca Operativa
