Swappa :: Ricerca Operativa - PLI - Arbitri

Torna alla pagina di Ricerca Operativa

 :: 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