Ora la questione si fa complicata. Ci tengo però a precisare che per fare un orario scolastico non serve necessariamente sapere quello che vi sto per raccontare, d'altra parte penso che chiunque affronti un problema possa chiedersi la natura del problema e se è noto e studiato in letteratura.
Il problema della redazione dell'orario scolastico appartiene alla classe dei Problemi di Soddisfacimento di Vincoli (Constraint Satisfaction Problem o CSP).
Darò dei piccoli spunti per capire come può essere formulato matematicamente. Vi ricordo che il mio obiettivo è far capire ciò di cui stiamo parlando, non scrivere un manuale scientifico.
Il problema è un problema decisionale, nel quale le variabili possono assumere valere 0 o 1.
Innanzitutto quali sono le variabili. Definiamo con I l'insieme dei professori, J l'insieme delle classi, K l'insieme delle ore giornaliere, L l'insieme dei giorni della settimana, ed associamo ad ognuno di questi elementi un numero univoco nell'insieme.
I = {1,2, ... Ni}, con Ni il numero totale dei docenti
J = {1,2, ... Nj}, con Nj il numero totale delle classi
K = {1,2, ... Nk}, con Nk il numero totale delle ore giornaliere
L = {1,2, ... Nl}, con Nl il numero totale dei giorni
Quindi avremo il professore 1, il professore 2, il professore 3, fino al professore Ni
Avremo la classe 1, la classe 2, la classe 3, la classe 4, fino alla classe Nj
Possiamo quindi definire la variabile Xijkl che vale 1 se il professore i fa lezione nella classe j all'ora k del giorno l, 0 altrimenti.
Definite le variabili dobbiamo chiederci come trasformare in equazioni o disequazioni i vincoli che abbiamo espresso a parole. Lo farò solo per un vincolo, quello che mi interessa è mostrare il procedimento.
Prendiamo per esempio il numero massimo di ore giornaliere di un professore e supponiamo che questo sia uguale a Oi.
Si fissa i (il professore), si fissa l (il giorno della settimana) e il vincolo si ottiene sommando tutte le Xijkl con quei determinati valori di i e l e imponendo che questa somma sia minore o uguale a Oi. E si fa questo per tutte le possibili combinazioni di i e l.
Tradotto in un linquaggio più semplice... preso un professore e preso un giorno della settimana, imponiamo che per quel professore e quel giorno della settimana al più Oi variabili possano essere uguali a 1, cioè che faccia al più Oi ore di lezione.
Questo funziona se c'è anche un altro vincolo che ci dice che fissata un ora, fissato un professore e fissato un giorno, la somma di tutte le relative variabili di decisioni deve essere minore o uguale ad 1, cioè se un professore fa lezione lo fa in una sola classe alla volta (e sì, dobbiamo dirgli anche quello).
Questo giochino può essere fatto in modo più o meno complicato per tutti i vincoli tenendo conto che esistono regole per trasformare in equazioni e disequazioni vincoli condizionali (del tipo se... allora...) e vincoli logici (ad esempio un vincolo che viene soddisfatto se sono soddisfatti contemporaneamente due condizioni, cioè un vincolo AND, o similmente un vincolo OR)
La formulazione matematica coincide quindi con l'introdurre delle variabili decisionali e con il trasformare tutti i vincoli in un immenso insieme di equazioni e disequazioni.
Non credo che nessuno approcci in questo modo al problema, ma questo è la sua formulazione rigorosa.
In uno dei prossimi articoli vedremo come si risolvono problemi del genere, ma già vi preannuncio che sono considerati problemi difficili.
In uno dei prossimi articoli vedremo come si risolvono problemi del genere, ma già vi preannuncio che sono considerati problemi difficili.
Un riferimento sitografico:
Post
Nessun commento:
Posta un commento
Che ne pensi di questo articolo, ti è piaciuto? Lo trovi interessante? Oppure ti sembra completamente inutile? Hai trovato errori o imprecisioni?
La moderazione, non è attiva, mi riservo il diritto di farne uso in particolari momenti, situazioni o contesti.