Uni.RO-PLI-27giu2006 History
Hide minor edits - Show changes to output
Added lines 1-158:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
----
(:title Ricerca Operativa - PLI - Arbitri - 27.06.06:)
%titolo%''':: Ricerca Operativa - PLI - Arbitri - 27.06.06 ::'''
!!Testo del problema
In seguito allo scandalo sulle designazioni arbitrali truccate, la Lega Calcio ha deciso di inaugurare un nuovo sistema, affidando ad un algoritmo di ottimizzazione le designazioni degli arbitri per i campionati di calcio. Noto il calendario delle partite e noto un insieme di arbitri disponibili, si vuole assegnare un arbitro ad ogni partita. Ovviamente lo stesso arbitro non può arbitrare più di una partita nella stessa giornata di campionato; inoltre ogni partita ha bisogno di un solo arbitro (non si considerano qui i guardalinee ed il “quarto uomo”).\\
Per garantire equità si vuole che il numero complessivo di volte che ogni arbitro viene assegnato ad ogni squadra sia il più uniforme possibile. In altri termini si vuole minimizzare la differenza tra il massimo ed il minimo numero di volte che uno degli arbitri viene assegnato ad una delle squadre nell’arco di tutto il campionato.\\
Formulare il problema, classificarlo e risolverlo con i dati del file ARBITRI.TXT, discutendo l’ottimalità e l’unicità della soluzione ottenuta.
!!!Dati
[@
Considerare un mini-campionato giocato da 6 squadre in un unico girone
all'italiana. Il calendario è il seguente:
Giornata 1
AAA - FFF
BBB - EEE
CCC - DDD
Giornata 2
AAA - DDD
BBB - FFF
CCC - EEE
Giornata 3
AAA - BBB
CCC - FFF
DDD - EEE
Giornata 4
AAA - EEE
BBB - CCC
DDD - FFF
Giornata 5
AAA - CCC
BBB - DDD
EEE - FFF
Si consideri il caso con 3 arbitri
@]
!!Formulazione del problema
!!!Dati
* '''nSquad = 6''' (numero di squadre nel campionato)
* '''nGiorn = 5''' (numero di giornate di campionato)
* '''nArbitri = 3''' (numero arbitri)
* '''giornata'_ijw_'''' (indica quali squadre w=1..6 giocano nella partita j=1..3 della giornata i=1..5) (nota: le partite sono 3 perché il numero di squadre è 6, quindi due per partita viene 3)
!!!Variabili
* '''x'_ijk_'''' (indica se l'arbitro k=1..3 è assegnato alla partita j=1..3 nella giornata i=1..5)
La variabile è binaria.
!!!Funzione obiettivo
Si vuole minimizzare la differenza tra il massimo e il minimo numero di volte in cui un arbitro viene assegnato ad una squadra nell'arco dell'intero campionato. Introduciamo le variabili ausiliarie maxn e minn che definiremo poi nei vincoli:\\
'''min maxn - minn'''
!!!Vincoli
* vincolo perché ci sia un arbitro per ogni partita j di ogni giornata i:\\
'''(somma)'_k_' x'_ijk_' = 1''' (per ogni i e per ogni j)
* vincolo perché lo stesso arbitro k non possa essere assegnato a più di una partita j in una stessa giornata i:\\
'''(somma)'_j_' x'_ijk_' <= 1''' (per ogni k e per ogni i)
* vincolo per definire maxn, ovvero il massimo numero di volte in cui un arbitro viene assegnato ad una squadra nell'arco dell'intero campionato:\\
'''maxn >= (somma)'_i_' (somma)'_j_' giornata'_ijw_' * x'_ijk_'''' (per ogni w e per ogni k)
* vincolo per definire minn, ovvero il minimo numero di volte in cui un arbitro viene assegnato ad una squadra nell'arco dell'intero campionato:\\
'''minn <= (somma)'_i_' (somma)'_j_' giornata'_ijw_' * x'_ijk_'''' (per ogni w e per ogni k)
!!Linghizzazione del problema
[@
! problema - Arbitri;
model:
sets:
squadra /1..6/;
giornata /1..5/;
arbitro /1..3/;
partita /1..3/;
assegnamento (giornata,partita,arbitro): x;
calendario (giornata,partita,squadra): cal;
endsets
data:
cal =
1 0 0 0 0 1
0 1 0 0 1 0
0 0 1 1 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 0
1 1 0 0 0 0
0 0 1 0 0 1
0 0 0 1 1 0
1 0 0 0 1 0
0 1 1 0 0 0
0 0 0 1 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 0 0 1 1;
enddata
! funzione obiettivo;
min = maxn - minn;
! deve esserci un arbitro per ogni partita;
@for(giornata(i):
@for(partita(j):
@sum(arbitro(k): x(i,j,k)) = 1
)
);
! un arbitro non può essere assegnato a più partite la stessa giornata;
@for(arbitro(k):
@for(giornata(i):
@sum(partita(j): x(i,j,k)) <= 1
)
);
! definiamo maxn: massimo numero di volte in cui un arbitro è assegnato
alla stessa squadra;
@for(squadra(w):
@for(arbitro(k):
maxn >= @sum(giornata(i):
@sum(partita(j):
cal(i,j,w) * x(i,j,k)
)
)
)
);
! definiamo minn: minimo numero di volte in cui un arbitro è assegnato
alla stessa squadra;
@for(squadra(w):
@for(arbitro(k):
minn <= @sum(giornata(i):
@sum(partita(j):
cal(i,j,w) * x(i,j,k)
)
)
)
);
! dichiarazione variabile binaria x;
@for(assegnamento(i,j,k): @bin(x(i,j,k)));
end
@]
----
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
|
