Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Comizi - 19.04.01 ::
Testo del problema
E' l'ultimo giorno della campagna elettorale e gli onorevoli Berlustelli e Rutusconi si stanno sfidando all'ultimo comizio. Ciascuno di loro deve percorrere l'autostrada e fermarsi in alcune città per arringare le folle. Ogni loro sosta lungo il viaggio implica un certo tempo fisso, uguale per entrambi ed indipendente dalla città, che deve essere impiegato stringendo mani e baciando bambini. Ogni comizio può essere di due tipi: comizio sintetico, in cui vengono enunciati rapidi slogan, e comizio analitico, in cui vengono esaminati in dettaglio vari punti del programma di governo. Ogni tipo di comizio ha la sua durata standard, indipendente dal numero di persone che vi assistono e uguale per entrambi gli onorevoli. In ogni città corrispondente ad un'uscita dell'autostrada è previsto che possa partecipare al comizio un certo numero di persone a seconda del tipo di comizio che vi si tiene e uguale per entrambi i candidati. Poiché la campagna elettorale volge al termine i comizi devono essere programmati in modo che l'ultimo termini entro la mezzanotte. Lo scopo del viaggio è ovviamente quello di arringare il maggior numero possibile di elettori.
Formulare il problema, classificarlo e risolverlo con i dati del file COMIZI.TXT.
Dati
La seguente tabella fornisce per ogni città in cui i candidati possono fermarsi
la distanza dall'estremità A dell'autostrada A-Y, e l'audience prevista a
seconda del tipo di comizio.
Città Distanza (km) Audience1 Audience2
a 0 120 140
b 12 80 200
c 25 60 100
d 31 400 450
e 46 200 250
f 60 10 30
g 72 500 550
h 89 90 110
i 110 50 80
j 127 300 330
k 142 10 50
l 160 60 90
m 166 230 280
n 170 190 240
o 180 100 150
p 193 100 110
q 211 100 180
r 218 200 300
s 230 80 180
t 244 10 20
u 263 80 150
v 280 90 100
w 285 120 130
x 292 500 650
y 298 400 490
Gli spostamenti tra una città e l'altra avvengono ad una velocità media di 100 Km/h.
Il tempo fisso per ogni sosta è pari a 1/2 ora.
La durata del comizio è di 1 ora (tipo 1) o 1.5 ore (tipo 2).
Il tempo a disposizione è di 16 ore.
Formulazione del problema
Dati
- citta = 25 (numero di città)
- com = 2 (numero di tipi di comizio)
- disti (distanza dalla città i=1..25) [km]
- audij (audience nella città i=1..25 per il comizio di tipo j=1..2)
- durj (durata comizio di tipo j=1..2) [h]
- sosta = 0.5 (tempo minimo per sosta) [h]
- tMax = 16 (tempo a disposizione) [h]
- vel = 100 (velocità di spostamento) [km/h]
Variabili
- xij (indica se il candidato si è fermato nella città i=1..25 e che tipo di comizio j=1..2 ha fatto)
La variabile è binaria.
Funzione obiettivo
max (somma)i (somma)j xij * audij
Vincoli
- il candidato può fare un solo tipo di comizio per città:
(somma)j xij <= 1 (per ogni i)
Il tempo a disposizione tMax è di 16 ore, ed ha tre componenti: tempo di trasferimento, tempi dei comizi, tempi fissi per le soste.
Consideriamoli separatamente e poi sommiamoli:
- calcolo dei tempi di trasferimento:
[(somma)j xij] * disti / vel <= tStrada (per ogni i)
- calcolo dei tempi dedicati ai comizi:
(somma)i (somma)j xij * durj <= tComizi
- calcolo dei tempi persi nelle soste:
(somma)i (somma)j xij * sosta <= tSoste
- ...sommiamo le componenti e otteniamo il vincolo sul tempo a disposizione:
tStrada + tComizi + tSoste <= tMax
Linghizzazione del problema
! esercizio - Comizi;
model:
sets:
citta /1..25/: distanze;
comizio /1..2/: durata;
svolgimento (citta,comizio): aud, x;
endsets
data:
distanze = 0 12 25 31 46 60 72 89 110 127 142 160 166 170
180 193 211 218 230 244 263 280 285 292 298;
aud = 120 140
80 200
60 100
400 450
200 250
10 30
500 550
90 110
50 80
300 330
10 50
60 90
230 280
190 240
100 150
100 110
100 180
200 300
80 180
10 20
80 150
90 100
120 130
500 650
400 490;
durata = 1 1.5;
sosta = 0.5;
tMax = 16;
vel = 100;
enddata
! funzione obiettivo;
max = @sum(svolgimento(i,j): x(i,j) * aud(i,j));
! vincolo tipo comizio per città;
@for(citta(i): @sum(comizio(j): x(i,j)) <= 1);
! calcolo/vincolo dei tempi di trasferimento;
@for(citta(i): @sum(comizio(j): x(i,j)) * distanze(i) / vel <= tStrada);
! calcolo/vincolo dei tempi dedicati ai comizi;
@sum(svolgimento(i,j): x(i,j) * durata(j)) <= tComizi;
! calolo/vincolo dei tempi persi nelle soste;
@sum(svolgimento(i,j): x(i,j) * sosta) <= tSoste;
! vincolo sul tempo massimo a disposizione;
tStrada + tComizi + tSoste <= tMax;
! dichiarazione variabile binaria x;
@for(svolgimento(i,j): @bin(x(i,j)));
end
Altre domande
Se i due onorevoli percorrono l'autostrada uno da A verso Y e l'altro da Y verso A, chi è avvantaggiato?
L'unico modo per scoprirlo è riformulare il problema e confrontare le due soluzioni. Per invertire il calcolo del tragitto bisognerà cambiare il vincolo:
! calcolo/vincolo dei tempi di trasferimento;
@for(citta(i): @sum(comizio(j): x(i,j)) * distanze(i) / vel <= tStrada);
in:
! calcolo/vincolo dei tempi di trasferimento;
@for(citta(i): @sum(comizio(j): x(i,j)) * (298 - distanze(i)) / vel <= tStrada);
Dove 298 era la distanza dall'ultima città. Risolvendo il problema in questa nuova forma si scopre che il valore ottimo non cambia.
E se piovesse e la velocità dovesse essere ridotta a 60 Km/h?
Bisogna risolvere il problema considerando il tragitto da "A->Y" e "Y->A", impostando stavolta la velocità (variabile vel) a 60. Si scopre così che il valore ottimo è migliore nel tragitto "Y->A", e vale 2780.
A che velocità dovrebbero viaggiare i due candidati per poter arringare più elettori?
Stiamo riformulando la funzione obiettivo del problema: vogliamo ora trovare la velocità minima a cui i candidati devono andare per arringare più elettori di quella che riescono ad arringare a 100 km/h (cioè 2980 persone). La funzione obiettivo va quindi riscritta come:
min = vel
e bisogna introdurre il vincolo che il numero di elettori arringati sia maggiore alla soluzione ottima trovata normalmente, cioè:
@sum(svolgimento(i,j): x(i,j) * aud(i,j)) > 2980;
Le soluzioni ottime trovate sono:
- per il tragitto "A->Y": 119.2 km/h
- per il tragitto "Y->A": 106.8 km/h
Quanto costa a ciascuno in termini di numero di elettori arringati la necessità di stringere mani e baciare bambini ad ogni tappa?
Per scoprirlo bisogna eliminare il vincolo:
! calolo/vincolo dei tempi persi nelle soste;
@sum(svolgimento(i,j): x(i,j) * sosta) <= tSoste;
e correggere il vincolo sui tempi totali in:
! vincolo sul tempo massimo a disposizione;
tStrada + tComizi <= tMax;
Risolvendo il problema scopriamo che la soluzione ottima aumenta da 2980 a 3580 elettori aringati.
Torna alla pagina di Ricerca Operativa
