:: Corsi di Laurea ::
Testo
Il Consiglio di Corso di Laurea deve decidere i piani di studio consigliati e per risolvere il problema si affida al ricercatore operativo. Ci sono N corsi attivati e P indirizzi tra cui gli studenti possono scegliere. Ogni corso ha un certo grado di attinenza, variabile da 1 a 10, con ciascuno degli indirizzi. Ogni corso non può comparire in più di K indirizzi (K <= P) e ogni indirizzo deve contenere esattamente M corsi (M<N). Ogni corso deve comparire in almeno un indirizzo.
Il Consiglio vuole massimizzare la misura totale di quanto i corsi sono attinenti agli indirizzi per cui sono consigliati.
Formulare il problema come problema di PLI e risolverlo nel seguente esempio (N=15, P=4, K=3, M=8).
Indirizzi A B C D
Corsi
1 10 8 9 10
2 9 10 9 9
3 10 9 7 7
4 9 10 8 8
5 8 9 7 6
6 8 7 7 6
7 5 7 4 4
8 3 2 2 2
9 4 3 1 1
10 5 6 4 3
11 5 5 5 2
12 6 3 4 3
13 5 5 3 3
14 6 6 3 3
15 5 4 3 4
Lingo
Questo esercizio è stato usato per introdurre l'utilizzo di Lingo, per il motivo che c'è un numero spropositato di variabili, e che quindi avrei avuto un sacco di vincoli, una funzione obiettivo satanica e così via. Lingo permette di semplificare le cose, definire matrici e simil-for, facilitandoci quindi la vita.
Il modello
Il modello inizia con la parola model e finisce con end.
I commenti
Attenzione ai commenti! I commenti partono da un ! e finiscono con un ; anche se si trovano su righe differenti!!! Questa è la causa principale di errore: uno non capisce quale sia l'errore, e poi si accorge di aver dimenticato un ; dopo un commento: tutte le righe comprese dal ! precedente fino a quel ; saranno considerate commento e non verranno cagate! Beware, innocent kid:)
sets
I sets, cioè gli insiemi di variabili. La notazione è un po' balorda:
biciclette /1..12/;
crea, in pratica, bicicletta1, bicicletta2 ... bicicletta12. Almeno è pratico.
Se voglio definire il prodotto cartesiano tra due insiemi, Lingo ci permette di farlo in una riga sola:
cartesiano (insiemeA, insiemeB);
Questo sistema è usato sotto, per generare automaticamente le N*M variabili necessarie a rappresentare il problema.
data
Nella sezione data ci vanno i dati. Posso scrivere allegramente variabili, ma anche matrici.
var = 100;
matrice = 1 2 3
4 5 6
7 8 9;
Per quanto riguarda le matrici, le scriviamo in tabella ma non perché Lingo abbia necessità di vederle in tabella, bensì per nostra comodità. Come dicevamo sopra, Lingo ha una particolare affezione per i ;. Pertanto, fino al ; lui tratta il tutto come membro della matrice. Inoltre, siccome Lingo per assegnare i dati alle matrici parte dall'indice che cresce meno velocemente, possiamo scriverle per righe.
C'è un'altra cosa da dire: se nei sets voglio creare un insieme, e assegnargli dei dati, posso usare il sistema che in effetti è stato usato nella soluzione qui sotto:
assegnamenti (corsi,indirizzi): a, x;
Questa riga crea un prodotto cartesiano chiamato assegnamenti, e dice a Lingo che la matrice a è di questa forma, così come la matrice delle variabili x. Inoltre, essendo a dichiarata sotto, Lingo la carica automaticamente in memoria. x invece non è dichiarata da nessuna parte, e quindi Lingo la tratta come variabile (che poi è effettivamente ciò che è).
Per indicizzare la matrice, si usa la sintassi x(i,j) che prende l'elemento con indici i e j nella matrice x.
Sommatorie
Le sommatorie hanno una sintassi particolare:
@sum(matrice(indice): assegnamento);
Questo rende possibile anche avere le sommatorie di sommatorie, come spesso è capitato nei problemi di RO:
@sum(corsi(i): @sum(indirizzi(j): a(i,j)*x(i,j)));
Per ogni
Il per ogni, che pure lui a volte salta fuori nei problemi, è esprimibile in Lingo con questa sintassi:
@for(matrice(indice): assegnamento);
Variabili binarie
Per dichiarare una variabile binaria, Lingo usa @bin. Nell'esempio qui sotto il @bin è stato usato in associazione con il @for per dichiare tante variabili binarie in un colpo solo:
@for(assegnamenti(i,j): @bin(x(i,j)));
Notate la "finezza": faccio scorrere a Lingo la matrice assegnamenti, per il solo motivo di trarne gli indici. Infatti, durante lo scorrimento della matrice, gli indici i e j vengono aggiornati, e io con la direttiva @bin dico a Lingo che gli elementi indicizzati da i e j sono binari, nella matrice x
Variabili intere
Le variabili intere, più ragionevolmente rispetto a Lindo, si dichiarano con la direttiva @int.
Soluzione
! Esercizio corso di laurea;
model:
! Nei sets ci vanno i corsi e gli indirizzi;
sets:
corsi /1..12/;
indirizzi /1..4/;
assegnamenti (corsi,indirizzi): a, x;
endsets
data:
a = 10 8 9 10
9 10 9 9
10 9 7 7
9 10 8 8
8 9 7 6
8 7 7 6
5 7 4 4
3 2 2 2
4 3 1 1
5 6 4 3
5 5 5 2
6 3 4 3;
K = 3;
M = 8;
enddata
! Funzione obiettivo: massimizzare affinità complessiva;
max = @sum(corsi(i): @sum(indirizzi(j): a(i,j)*x(i,j)));
! Vincolo sul numero massimo di indirizzi per ogni corso;
@for(corsi(i): @sum(indirizzi(j): x(i,j)) <= K );
! Vincolo sul numero di corsi per indirizzo;
@for(indirizzi(j): @sum(corsi(i): x(i,j)) = M);
! Vincolo sul numero minimo di indirizzi in cui deve comparire un corso
@for(corsi(i): @sum(indirizzi(j): x(i,j)) >= 1 );
!Dichiarare le variabili binarie;
@for(assegnamenti(i,j): @bin(x(i,j)));
end
