Ricerca Operativa I

prova scritta del 26 giugno 2001

Il sindacato si riorganizza (de che?)

A coronamento di anni di crisi, il sindacato si trova oggi ad affrontare la questione delle questioni: il rinnovo del contratto dei professori universitari. Com’è noto, questi sono divisi in 3 fasce: ricercatori, associati e ordinari. Un’illuminata riforma approvata di recente dal parlamento prevede finalmente che la progressione di carriera non avvenga più attraverso concorsi nazionali (dove chiunque può farsi raccomandare al barone di turno) ma proceda per automatismi: per un primo periodo di x₁ anni lo stipendio viene fissato a una certa quantità s₁; dopodiché, per altri x₂ anni, lo stipendio verrà portato a s₂; infine, per altri x₃ anni, lo stipendio sarà fissato a s₃.

Novità principale dell’accordo è la disponibilità da parte del sindacato, in vista di un patto generale di stabilità, ad accettare eventuali riduzioni di stipendio da un periodo al successivo. Due delle 3 diverse ipotesi di contratto allo studio, indicate nelle righe della tabella seguente, corrispondono in effetti a questa eventualità.

	Periodo 1	Periodo 2	Periodo 3
Ipotesi 1	56	60	48
Ipotesi 2	48	56	60
Ipotesi 3	64	40	56

L’elemento i-esimo della generica riga rappresenta lo stipendio annuale s_i (espresso in milioni di £) relativo al periodo i in quell’ipotesi di contratto.

Il contratto copre un periodo di 7 anni, pari alla somma x₁ + x₂ + x₃ dei tre periodi considerati. In questi sette anni il sindacato vorrebbe ottenere per la categoria il massimo vantaggio economico. Il governo riconosce al sindacato, e solo a lui, il potere di definire le durate dei 3 periodi (alcune possono addirittura essere poste a zero). Ma in quanto controparte si riserva di scegliere a posteriori l’ipotesi di contratto per sé più conveniente.

Il sindacato vorrebbe evitare l’ennesima fregatura ma non sa bene che pesci prendere. Per fortuna un sindacalista, che ha studiato la ricerca operativa ed era presente all’ultima riunione con il governo, chiede la parola e dice: “Tranquilli, compagni, come minimo nei 7 anni si porta a casa 380.800.000 lire!”. Come fa a saperlo?

Per gli studenti di ingegneria

Il sindacalista sostiene che esiste una scelta dei periodi che rende lo stipendio complessivamente ottenuto indipendente dalle ipotesi di accordo scelte a posteriori dal governo. Ha ragione o ha torto? Perché?

Soluzione

Il sindacalista formula il problema come gioco a somma zero. L’obiettivo è massimizzare lo stipendio complessivo nei 10 anni, riferendosi al caso peggiore che corrisponderà all’ipotesi scelta alla fine dal governo. Si indichi con z tale quantità, e sia x_i la durata del periodo i (che è ciò che il sindacato può autonomamente decidere). Il problema si pone allora in questi termini:

max z

56x₁ + 60x₂ + 48x₃ > z

48x₁ + 56x₂ + 60x₃ > z

64x₁ + 40x₂ + 56x₃ > z

x₁ + x₂ + x₃ = 7

x₁, x₂, x₃ > 0

ovvero:

max z

– 56x₁ – 60x₂ – 48x₃ + z < 0

– 48x₁ – 56x₂ – 60x₃ + z < 0

– 64x₁ – 40x₂ – 56x₃ + z < 0

x₁ + x₂ + x₃ = 7

x₁, x₂, x₃ > 0

La tabella del simplesso è allora:

0	0	0	1	0	0	0	0
–56	–60	–48	1	1	0	0	0
–48	–56	–60	1	0	1	0	0
–64	–40	–56	1	0	0	1	0
1	1	1	0	0	0	0	7

Per ottenere la forma canonica basta ad esempio moltiplicare l’ultima riga per 48, 60, 56, e sottrarla rispettivamente alla prima, alla seconda, alla terza riga (considerando i costi ridotti in riga zero). Si ha:

0	0	0	1	0	0	0	0
–8	–12	0	1	1	0	0	336
12	4	0	1	0	1	0	420
–8	16	0	1	0	0	1	392
1	1	1	0	0	0	0	7

La soluzione di base corrispondente a questa tabella è w₁ = 336, w₂ = 420, w₃ = 392, x₃ = 7. Poiché z ha costo ridotto > 0, la soluzione può non essere ottima. Eseguendo un’operazione di pivot sull’elemento di riga 1 e colonna 4, si ricava:

8	12	0	0	–1	0	0	–336
–8	–12	0	1	1	0	0	336
20	16	0	0	–1	1	0	84
0	28	0	0	–1	0	1	56
1	1	1	0	0	0	0	7

Ora la soluzione corrente è w₂ = 84, w₃ = 56, x₃ = 7, e ha valore z = 336. Anche in questo caso compaiono costi ridotti positivi. Eseguendo un pivot sull’elemento di riga 3 e colonna 2 sia ha:

8	0	0	0	-4/7	0	-3/7	-360
-8	0	0	1	4/7	0	3/7	360
20	0	0	0	-3/7	1	-4/7	52
0	1	0	0	–1/28	0	1/28	2
1	0	1	0	1/28	0	-1/28	5

e la soluzione corrente diventa w₂ = 52, x₂ = 20/7, x₃ = 5, con valore z = 360.

Rimane ancora un costo ridotto positivo. Eseguendo un pivot sull’elemento di riga 2 e colonna 1 si perviene a:

0	0	0	0	-14/35	-2/5	-1/7	-1904/5
0	0	0	1	14/35	2/5	1/7	1904/5
1	0	0	0	–3/140	1/20	–1/35	13/5
0	1	0	0	-1/28	0	1/28	2
0	0	1	0	14/245	-1/20	-1/140	12/5

La soluzione finalmente ottenuta è x₁ = 13/5, x₂ = 2, x₃ = 12/5. Essa è ottima, e corrisponde a un valore di z = 1904/5 = 380,8 (milioni di £), proprio come aveva predetto il sindacalista.

Per gli studenti di ingegneria

Si noti che, essendo tutte le variabili in base, questa soluzione soddisfa tutti i vincoli con il segno “=”. Pertanto scegliendo le durate dei periodi in accordo ai valori trovati, le alternative per il governo sono tutte tra loro equivalenti.