OII 2010-12-02 – 13

Alcuni ragazzi decidono di costruire un ipertesto multimediale sugli avvenimenti storici significativi della loro regione.
Per organizzare il progetto, dividono il lavoro in 9 attività e assegnano ogni attività a un gruppo di loro.

La tabella che segue descrive le 9 attività (indicate rispettivamente con le sigle A1, A2, …, A9) riportando per ciascuna di esse il numero di ragazzi assegnato e il numero di giorni per completarla.

Le sequenzialità fra le attività sono descritte con coppie di sigle; ogni coppia esprime il fatto che l’attività associata alla sigla di sinistra è antecedente a quella associata alla sigla di destra, cioè l’attività di sinistra deve terminare prima che quella di destra possa iniziare.

Per esempio, la coppia (A1,A3) indica che l’attività A3 può cominciare solo quando è terminata l’attività A1.

L’attività che non ha nessuna antecedente è la prima, quella che non compare mai come antecedente è l’ultima.
Se un’attività ha più antecedenti, può essere iniziata solo quando tutte le antecedenti sono terminate.

Con le sequenzialità descritte dal seguente elenco:

(A1,A2) (A1,A3) (A1,A4) (A2,A7) (A2,A8) (A3,A6) (A3,A8) (A4,A5) (A5,A8) (A6,A9) (A7,A9) (A8,A9)

e assumendo che l’attività A1 inizi il giorno 1:

1. trovare il numero N di giorni necessari per completare il progetto, tenuto presente che alcune attività possono essere svolte in parallelo e che ogni attività deve iniziare il prima possibile (nel rispetto delle sequenzialità);
2. trovare il numero X1 che individua il giorno in cui lavora il maggior numero M1 di ragazzi e calcolare M1;
3. trovare il numero X2 del giorno in cui lavora il minor numero M2 di ragazzi e calcolare M2;
4. supponendo che la retribuzione media giornaliera per ragazzo sia di 90 euro, calcolare il costo complessivo S del progetto.

Soluzione: 8, 5, 12, 7, 1, 5400.

Il cronogramma seguente rispecchia i vincoli del problema

Per ogni giorno sono evidenziati

• le attività svolte contemporaneamente
• i ragazzi assegnati per ogni attività
• il totale di ragazzi assegnati

e le risposte al problema sono