Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PLI - Comizi - 19.04.01 ::
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.
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.
La variabile è binaria.
max (somma)i (somma)j xij * audij
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:
! 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
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.
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.
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 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.