Problema di Assegnazione: Come Risolverlo con Python e PuLP per Minimizzare i Costi

Problema di Assegnazione:

• Scenario: Un’azienda ha più compiti e più dipendenti. Deve assegnare ciascun compito a un dipendente per minimizzare il costo totale dell’assegnazione, tenendo conto delle competenze e dei costi di ciascun dipendente.
• Implementazione:
  • Definire le variabili decisionali come l’assegnazione di ciascun compito a ciascun dipendente.
  • Definire la funzione obiettivo come il costo totale dell’assegnazione.
  • Definire i vincoli come l’assegnazione di ciascun compito a un solo dipendente e l’assegnazione di ciascun dipendente a un solo compito.
• Utilizzo di PuLP: PuLP può essere utilizzato per trovare l’assegnazione ottimale.

Risolvere problemi di ottimizzazione lineare: Confronto pratico tra PuLP e scipy.optimize

Soluzione

Definizione del Problema

Immaginiamo di avere 3 dipendenti e 3 compiti da assegnare. Ogni dipendente ha un costo diverso per svolgere ogni compito e vogliamo assegnare i compiti in modo da minimizzare il costo totale.

L’obiettivo è trovare l’assegnazione ottimale in cui:
✔ Ogni compito è assegnato a un solo dipendente.
✔ Ogni dipendente riceve un solo compito.
✔ Il costo totale dell’assegnazione è il più basso possibile.

import pulp

# Dati del problema
dipendenti = ["D1", "D2", "D3"]
compiti = ["C1", "C2", "C3"]

# Matrice dei costi (righe = dipendenti, colonne = compiti)
costi = {
    ("D1", "C1"): 10, ("D1", "C2"): 8,  ("D1", "C3"): 9,
    ("D2", "C1"): 7,  ("D2", "C2"): 12, ("D2", "C3"): 5,
    ("D3", "C1"): 6,  ("D3", "C2"): 14, ("D3", "C3"): 7
}

# Definizione del problema di minimizzazione
problema = pulp.LpProblem("Problema_Assegnazione", pulp.LpMinimize)

# Variabili decisionali: x[i, j] = 1 se il dipendente i è assegnato al compito j, 0 altrimenti
x = {(d, c): pulp.LpVariable(f"x_{d}_{c}", cat="Binary") for d in dipendenti for c in compiti}

# Funzione obiettivo: minimizzare il costo totale dell'assegnazione
problema += pulp.lpSum(costi[d, c] * x[d, c] for d in dipendenti for c in compiti)

# Vincoli: ogni compito deve essere assegnato a un solo dipendente
for c in compiti:
    problema += pulp.lpSum(x[d, c] for d in dipendenti) == 1

# Vincoli: ogni dipendente deve ricevere esattamente un compito
for d in dipendenti:
    problema += pulp.lpSum(x[d, c] for c in compiti) == 1

# Risoluzione del problema
problema.solve()

# Output della soluzione
if problema.status == pulp.LpStatusOptimal:
    print("Soluzione Ottimale:")
    for d in dipendenti:
        for c in compiti:
            if pulp.value(x[d, c]) == 1:
                print(f"  {d} assegnato a {c} (costo: {costi[d, c]})")
    print(f"Costo totale minimo: {pulp.value(problema.objective)}")
else:
    print("Nessuna soluzione ottimale trovata.")

Output:

Soluzione Ottimale:
D1 assegnato a C2 (costo: 8)
D2 assegnato a C3 (costo: 5)
D3 assegnato a C1 (costo: 6)
Costo totale minimo: 19

Definizione dei dati

dipendenti = ["D1", "D2", "D3"]
compiti = ["C1", "C2", "C3"]

Qui definiamo 3 dipendenti (D1, D2, D3) e 3 compiti (C1, C2, C3).

# Matrice dei costi (righe = dipendenti, colonne = compiti)
costi = {
    ("D1", "C1"): 10, ("D1", "C2"): 8,  ("D1", "C3"): 9,
    ("D2", "C1"): 7,  ("D2", "C2"): 12, ("D2", "C3"): 5,
    ("D3", "C1"): 6,  ("D3", "C2"): 14, ("D3", "C3"): 7
}

Creiamo una matrice dei costi, che rappresenta il costo che ogni dipendente deve sostenere per svolgere ogni compito.
Ad esempio:

Il dipendente D1 svolge C1 con un costo di 10.
Il dipendente D2 svolge C1 con un costo di 7.
Il dipendente D3 svolge C1 con un costo di 6.

Creazione del modello di ottimizzazione

problema = pulp.LpProblem("Problema_Assegnazione", pulp.LpMinimize)

creiamo un modello matematico chiamato "Problema_Assegnazione" e specifichiamo che vogliamo minimizzare il costo (LpMinimize).

Definizione delle variabili decisionali

x = {(d, c): pulp.LpVariable(f"x_{d}_{c}", cat="Binary") for d in dipendenti for c in compiti}

Creiamo una variabile binaria x[d, c] per ogni combinazione di dipendente d e compito c.

• x[D1, C1] = 1 significa che D1 è assegnato al compito C1.
• x[D1, C1] = 0 significa che D1 non è assegnato a C1.
• Poiché ogni variabile è di tipo binario, può assumere solo i valori 0 o 1.

Definizione della funzione obiettivo

problema += pulp.lpSum(costi[d, c] * x[d, c] for d in dipendenti for c in compiti)

Qui definiamo la funzione che vogliamo minimizzare:

n altre parole, sommiamo i costi di assegnazione di tutti i dipendenti ai compiti, tenendo conto di quali assegnazioni sono attivate (x = 1) e quali no (x = 0).

Definizione dei vincoli

🔹 Vincolo 1: Ogni compito è assegnato a un solo dipendente

for c in compiti:
    problema += pulp.lpSum(x[d, c] for d in dipendenti) == 1

Per ogni compito C1, C2 o C3, ci assicuriamo che sia assegnato a un solo dipendente.
Matematicamente:

… e così via per gli altri compiti.

🔹 Vincolo 2: Ogni dipendente deve eseguire un solo compito

for d in dipendenti:
    problema += pulp.lpSum(x[d, c] for c in compiti) == 1

Per ogni dipendente D1, D2 o D3, ci assicuriamo che riceva un solo compito.
Matematicamente:

… e così via per gli altri dipendenti.

Risoluzione del problema

problema.solve()

Qui diciamo a PuLP di risolvere il problema usando un algoritmo di ottimizzazione.

Lettura dei risultati

if problema.status == pulp.LpStatusOptimal:
    print("Soluzione Ottimale:")
    for d in dipendenti:
        for c in compiti:
            if pulp.value(x[d, c]) == 1:
                print(f"  {d} assegnato a {c} (costo: {costi[d, c]})")
    print(f"Costo totale minimo: {pulp.value(problema.objective)}")
else:
    print("Nessuna soluzione ottimale trovata.")

Se il problema ha una soluzione ottimale, stampiamo quali dipendenti sono stati assegnati ai compiti e il costo totale minimo.

Conclusione

✔ Il nostro modello assegna i compiti ai dipendenti nel modo più economico possibile.
✔ Funziona con qualsiasi numero di dipendenti e compiti: basta aggiornare la matrice dei costi.
✔ È un esempio pratico di Programmazione Lineare usata per risolvere problemi reali.

Applicazioni pratiche nel mondo reale

Il problema di assegnazione trova applicazione in numerosi ambiti aziendali, contribuendo a migliorare l’efficienza operativa e ridurre i costi. In logistica, viene utilizzato per assegnare autisti ai percorsi di consegna minimizzando il tempo e il costo del trasporto. Nella gestione delle risorse umane, aiuta a distribuire i dipendenti sui turni di lavoro o ai progetti in base alle competenze e alla disponibilità. Nello scheduling della produzione, ottimizza l’assegnazione delle macchine ai vari processi produttivi, riducendo i tempi di attesa e massimizzando l’utilizzo delle risorse. Questi esempi dimostrano come la programmazione lineare sia uno strumento potente per risolvere problemi complessi e prendere decisioni data-driven.

Pubblicità