Formulazione di un Problema di Programmazione Lineare Intera

In contesti complessi come quello degli istituti di ricerca, la gestione strategica delle risorse è fondamentale, soprattutto quando si tratta di espandere l’organico. L’assunzione di nuovo personale qualificato, sebbene necessaria per la crescita e l’innovazione, si scontra spesso con limitazioni significative, prime fra tutte quelle di carattere economico. A queste si aggiungono spesso vincoli normativi, strutturali o interni che rendono la decisione su “chi” e “quanti” assumere per ciascuna posizione (nel nostro caso, i diversi livelli di ricercatori) una vera e propria sfida decisionale.

Come possiamo, dunque, massimizzare il numero complessivo di nuovi ricercatori da inserire, rispettando contemporaneamente un tetto massimo di spesa annuale, specifiche proporzioni imposte da normative tra i diversi livelli, e garantendo soglie minime di assunzione per ciascuna categoria? Affrontare queste problematiche in modo efficace richiede un approccio strutturato e quantitativo.

È qui che interviene l’ottimizzazione matematica. Formulando il problema come un modello matematico rigoroso, possiamo identificare la combinazione ottimale di assunzioni che soddisfi tutti i vincoli e raggiunga l’obiettivo desiderato.

In questo articolo, partendo da un caso pratico ben definito relativo all’assunzione di ricercatori di diverso livello in un istituto di ricerca, mostreremo passo passo come trasformare questa complessa problematica decisionale in un modello di Programmazione Lineare Intera (PLI). Analizzeremo la definizione delle variabili decisive, la formulazione della funzione obiettivo da massimizzare e la traduzione dettagliata di ogni vincolo descritto dal problema reale nella sua forma matematica. Seguiteci in questo processo per comprendere come la modellazione matematica possa fornire soluzioni chiare e basate sui dati a sfide di gestione risorse.

Tema d’esame:

Un istituto di ricerca deve decidere il numero di posti da mettere a concorso per l’assunzione di nuovi ricercatori di primo, secondo e terzo livello. L’istituto prevede di poter spendere annualmente, per la retribuzione dei nuovi ricercatori, una quota massima pari a tre milioni di euro.

Il costo annuo di retribuzione di un ricercatore di primo livello è pari a [math]40{,}000[/math] euro, di un ricercatore di secondo livello è pari a [math]30{.}000[/math] euro e di un ricercatore di terzo livello è pari a [math]25{.}000[/math] euro.

Per motivi legali, la spesa complessiva annuale da sostenere per assumere i nuovi ricercatori di secondo livello non può superare l’80% della spesa complessiva annuale sostenuta per assumere i nuovi ricercatori di primo livello; inoltre, il numero di ricercatori di secondo livello da assumere deve essere almeno il doppio del numero dei nuovi ricercatori di terzo livello.

Infine, il bando di concorso può essere emanato solo se, per ogni livello, vengono assunti almeno 6 ricercatori.

Obiettivo: formulare il problema come problema di ottimizzazione, con l’obiettivo di massimizzare il numero complessivo di nuovi ricercatori da assumere.

Soluzione e svolgimento:

Per definire le variabili decisionali, facciamo riferimento alla funzione obiettivo: massimizzare il numero complessivo di ricercatori da assumere. Tale numero è dato dalla somma dei ricercatori assunti per ciascun livello. Quindi le variabili decisionali sono:

[math]x_i = \text{numero di ricercatori di livello } i \text{ da assumere} \quad (i = 1,2,3)[/math]

Di conseguenza la funzione obiettivo [math]z[/math] è:

[math]z = x_1 + x_2 + x_3[/math]

L’obiettivo è “massimizzare il numero complessivo di nuovi ricercatori”. Il numero complessivo è semplicemente la somma dei ricercatori assunti a ciascun livello.

Passando ora ai vincoli, il primo vincolo richiede che, per la retribuzione dei nuovi ricercatori, si spenda annualmente non più di 3 milioni di euro. Quindi, tenendo conto che un ricercatore di primo livello costa all’istituto ogni anno 40.000 euro, un ricercatore di secondo livello costa 30.000 euro, mentre uno di terzo livello costa 25.000 euro, la somma complessiva annua spesa dall’istituto per la retribuzione dei nuovi ricercatori è pari a:

[math]40.000x_1 + 30.000x_2 + 25.000x_3[/math]

Quindi il primo vincolo è:

[math]40.000x_1 + 30.000x_2 + 25.000x_3 \leq 3.000.000[/math]

La spesa annuale totale per i nuovi ricercatori non può superare 3 milioni di euro.

La scrittura del vincolo che lega la spesa annuale da sostenere per assumere i ricercatori di primo e secondo livello è esprimibile nel seguente modo:

[math]30.000x_2 \leq 0{,}80 \cdot 40.000x_1[/math]

La spesa complessiva annuale per i ricercatori di secondo livello non può superare l’80% della spesa complessiva annuale per i ricercatori di primo livello.

I vincoli restanti sono semplici da scrivere e sono:

[math]x_2 \geq 2x_3[/math]

Il numero di ricercatori di secondo livello da assumere deve essere almeno il doppio del numero dei nuovi ricercatori di terzo livello.

e

[math]x_i \geq 6 \quad \text{per } i = 1,2,3[/math]

Per ogni livello, devono essere assunti almeno 6 ricercatori.

Precisiamo che in tal caso non ha senso aggiungere i vincoli di positività sulle variabili, visto che essi sono già implicati dai vincoli che impongono che, per ogni livello, devono essere assunti almeno 6 ricercatori.

È importante invece precisare che le variabili decisionali debbano assumere valori interi.

Quindi, semplificando alcuni vincoli (in cui si può dividere per 1.000), la formulazione finale è:

[math]
\begin{aligned}
&\text{max } z = x_1 + x_2 + x_3 \\
&\text{soggetto a:} \\
&40x_1 + 30x_2 + 25x_3 \leq 3000 \\
&30x_2 \leq 32x_1 \\
&x_2 \geq 2x_3 \\
&x_i \geq 6 \quad \text{per } i = 1,2,3 \\
&x_i \in \mathbb{Z} \quad \text{per } i = 1,2,3
\end{aligned}
[/math]

Risolvere manualmente un problema di programmazione lineare intera con tre variabili e diversi vincoli può essere complesso e richiede l’utilizzo di algoritmi specifici come il metodo Branch-and-Bound o Cutting Planes. Per problemi di queste dimensioni, la soluzione più efficiente e affidabile è utilizzare un solutore software dedicato alla programmazione matematica (cExcel Solver, Gurobi, CPLEX, PuLP in Python, ecc.).

Possiamo risolvere il problema formulato utilizzando Python e una libreria come PuLP, che è ottima per modellare e risolvere problemi di Programmazione Lineare e Intera.

Prima di eseguire il codice, assicurati di avere la libreria PuLP installata. Se non l’hai già, puoi installarla con pip:

Nota: l’articolo al seguente link è stato pubblicato su

La Scienza dei Dati- La Libreria PuLP
il nostro blog dedicato all’analisi quantitativa, agli algoritmi e all’intelligenza artificiale applicata.

pip install pulp

PuLP si basa su solutori esterni, ma viene fornito con un solutore predefinito (spesso CBC), che è sufficiente per questo problema.

Ecco il codice Python per modellare e risolvere il problema:

# Importa la libreria PuLP
from pulp import *

# 1. Crea l'oggetto problema di ottimizzazione
# LpMaximize indica che l'obiettivo è massimizzare la funzione
prob = LpProblem("Assunzione_Ricercatori", LpMaximize)

# 2. Definisci le variabili decisionali
# LpVariable(NomeVariabile, lowerBound=..., cat='Integer' o 'Continuous')
# Impostiamo lowerBound=6 direttamente qui per i vincoli minimi
x1 = LpVariable("x1", lowBound=6, cat='Integer') # Numero di ricercatori di Livello 1
x2 = LpVariable("x2", lowBound=6, cat='Integer') # Numero di ricercatori di Livello 2
x3 = LpVariable("x3", lowBound=6, cat='Integer') # Numero di ricercatori di Livello 3

# 3. Definisci la funzione obiettivo e aggiungila al problema
# L'obiettivo è massimizzare il numero totale di ricercatori assunti
prob += x1 + x2 + x3, "Numero totale di ricercatori"

# 4. Definisci i vincoli e aggiungili al problema
# I vincoli vengono aggiunti usando l'operatore +=
# Vincolo 1: Budget annuale (40000*x1 + 30000*x2 + 25000*x3 <= 3000000) semplificato per 1000
prob += 40*x1 + 30*x2 + 25*x3 <= 3000, "Vincolo_Budget"

# Vincolo 2: Spesa Livello 2 vs Livello 1 (30000*x2 <= 0.80 * 40000*x1) semplificato
# 30000*x2 <= 32000*x1 => 30*x2 <= 32*x1 => 30*x2 - 32*x1 <= 0
prob += 30*x2 - 32*x1 <= 0, "Vincolo_Spesa_L2_vs_L1" # Vincolo 3: Numero Livello 2 vs Livello 3 (x2 >= 2*x3)
prob += x2 >= 2*x3, "Vincolo_Numero_L2_vs_L3"

# I vincoli minimi x_i >= 6 e l'integralità (x_i in Z)
# sono già stati gestiti nella definizione delle variabili tramite lowBound e cat='Integer'

# 5. Scrivi il problema su un file (opzionale, utile per debug)
# prob.writeLP("problema_ricercatori.lp")

# 6. Risolvi il problema
# PuLP sceglierà un solutore disponibile (es. CBC)
prob.solve()

# 7. Stampa lo stato della soluzione e i risultati
print("Stato della soluzione:", LpStatus[prob.status])

# Verifica se è stata trovata una soluzione ottima
if prob.status == LpStatusOptimal:
    print("\nSoluzione Ottima Trovata:")
    print(f"Numero totale massimo di ricercatori: {value(prob.objective)}")
    print(f"Ricercatori Livello 1 (x1): {int(value(x1))}") # Usiamo int() per mostrare numeri interi puliti
    print(f"Ricercatori Livello 2 (x2): {int(value(x2))}")
    print(f"Ricercatori Livello 3 (x3): {int(value(x3))}")

    # --- Verifica dei Vincoli con la Soluzione Trovata (Opzionale) ---
    print("\nVerifica dei Vincoli:")

    budget_speso = 40*value(x1) + 30*value(x2) + 25*value(x3)
    print(f"Budget Speso (migliaia di €): {budget_speso:.2f} (<= 3000) - {'OK' if budget_speso <= 3000 else 'FALLITO'}")

    spesa_l2 = 30*value(x2)
    ottanta_percento_spesa_l1 = 32*value(x1)
    print(f"Spesa L2 ({spesa_l2:.2f}) <= 80% Spesa L1 ({ottanta_percento_spesa_l1:.2f}) - {'OK' if spesa_l2 <= ottanta_percento_spesa_l1 else 'FALLITO'}") numero_l2 = value(x2) doppio_l3 = 2*value(x3) print(f"Numero L2 ({numero_l2}) >= Doppio L3 ({doppio_l3}) - {'OK' if numero_l2 >= doppio_l3 else 'FALLITO'}")

    print(f"Minimo L1 ({value(x1)}) >= 6 - {'OK' if value(x1) >= 6 else 'FALLITO'}")
    print(f"Minimo L2 ({value(x2)}) >= 6 - {'OK' if value(x2) >= 6 else 'FALLITO'}")
    print(f"Minimo L3 ({value(x3)}) >= 6 - {'OK' if value(x3) >= 6 else 'FALLITO'}")


else:
    print("\nIl solutore non ha trovato una soluzione ottima.")
    print("Possibili stati: Not Solved, Infeasible, Unbounded, Undefined")

Output:

Stato della soluzione: Optimal

Soluzione Ottima Trovata:
Numero totale massimo di ricercatori: 91.0
Ricercatori Livello 1 (x1): 36
Ricercatori Livello 2 (x2): 37
Ricercatori Livello 3 (x3): 18

Verifica dei Vincoli:
Budget Speso (migliaia di €): 3000.00 (<= 3000) - OK
Spesa L2 (1110.00) <= 80% Spesa L1 (1152.00) - OK Numero L2 (37.0) >= Doppio L3 (36.0) - OK
Minimo L1 (36.0) >= 6 - OK
Minimo L2 (37.0) >= 6 - OK
Minimo L3 (18.0) >= 6 - OK

Verifichiamo nuovamente che questa soluzione soddisfi tutti i vincoli:

Vincolo di budget:

[math]40\times36+30\times37+25\times18\leq3000[/math]
[math]1440+1110+450\leq3000[/math]
[math]3000\leq3000[/math] (VERIFICATO – Il budget è utilizzato al massimo, il che è tipico nelle soluzioni di massimizzazione con vincoli di risorse scarse)

Vincolo spesa Livello 2 vs Livello 1:

[math]30\times37\leq32\times36[/math]
[math]1110\leq1152[/math] (VERIFICATO)

Vincolo numero Livello 2 vs Livello 3:

[math]37\geq2\times18[/math]
[math]37\geq36[/math] (VERIFICATO – Il numero di ricercatori di livello 2 è appena superiore al doppio di quelli di livello 3)

Vincoli minimi per livello:

[math]x_1 = 36 \geq 6[/math] (VERIFICATO)
[math]x_2 = 37 \geq 6[/math] (VERIFICATO)
[math]x_3 = 18 \geq 6[/math] (VERIFICATO)

Vincolo di integralità:

[math]x_1=36, x_2=37, x_3=18[/math] sono tutti numeri interi (VERIFICATO)

Conclusione:

La soluzione fornita dal solutore ([math]x_1=36,x_2=37,x_3=18[/math]) è fattibile (rispetta tutti i vincoli) e fornisce il valore massimo per la funzione obiettivo ([math]z=91[/math]). Poiché il solutore ha riportato lo stato “Optimal”, possiamo confermare che questa è effettivamente la soluzione ottima globale per il problema di Programmazione Lineare Intera formulato.

L’istituto di ricerca dovrebbe quindi assumere 36 ricercatori di primo livello, 37 di secondo livello e 18 di terzo livello per massimizzare il numero totale di nuovi ricercatori (arrivando a 91) nel rispetto del budget massimo di 3 milioni di euro e di tutte le altre normative imposte.

Conclusione:

Abbiamo formulato il problema come un problema di programmazione lineare intera con vincoli lineari e funzione obiettivo lineare. La risoluzione può avvenire tramite algoritmi come il metodo del simplesso con branch-and-bound per l’integralità, oppure utilizzando software come Excel Solver, LINDO, Gurobi o Python con la libreria PuLP.

(68)