Un piccolo laboratorio produce due tipi di tavoli. Il tavolo da cucina richiede 2 ore di falegnameria e 1 ora di verniciatura, e rende 60 euro di margine. Il tavolino da salotto richiede 1 ora di falegnameria e 1 ora di verniciatura, e rende 40 euro. Ogni settimana ci sono 100 ore di falegnameria e 80 di verniciatura. Quanti tavoli di ciascun tipo conviene produrre?
Questo è il tipico problema di programmazione lineare (PL): decidere quantità che rispettano risorse limitate, massimizzando un guadagno o minimizzando un costo. Il termine «programmazione» non c'entra con il software: viene dal linguaggio della pianificazione, nel senso di «programma di produzione».
I tre ingredienti di un modello
Ogni modello di PL ha la stessa struttura.
- Variabili decisionali: le quantità che possiamo scegliere. Qui x = tavoli da cucina, y = tavolini.
- Funzione obiettivo: ciò che vogliamo massimizzare o minimizzare, espresso come combinazione lineare delle variabili. Qui: massimizzare 60x + 40y.
- Vincoli: disuguaglianze o uguaglianze lineari che le variabili devono rispettare.
Il modello completo:
massimizza 60x + 40y
soggetto a 2x + y ≤ 100 (falegnameria)
x + y ≤ 80 (verniciatura)
x, y ≥ 0
«Lineare» significa che variabili e costanti compaiono solo moltiplicate per numeri e sommate: niente prodotti tra variabili, quadrati, radici o condizioni del tipo «se… allora». È una restrizione forte, ma permette di risolvere in modo affidabile modelli con migliaia o milioni di variabili.
Risolvere a occhio con il metodo grafico
Con due variabili si può disegnare il problema. Ogni vincolo divide il piano in due parti; l'intersezione delle parti ammesse è la regione ammissibile, un poligono convesso. In questo esempio i vertici del poligono sono (0, 0), (50, 0), (20, 60) e (0, 80).
Un risultato fondamentale dice che, se il problema ha un ottimo, almeno un ottimo si trova in un vertice della regione. Basta quindi valutare l'obiettivo nei vertici:
| Vertice | 60x + 40y |
|---|---|
| (0, 0) | 0 |
| (50, 0) | 3.000 |
| (20, 60) | 3.600 |
| (0, 80) | 3.200 |
La soluzione ottima è produrre 20 tavoli da cucina e 60 tavolini, per un margine di 3.600 euro. Entrambe le risorse sono usate al massimo: 2·20 + 60 = 100 ore di falegnameria e 20 + 60 = 80 di verniciatura.
Un secondo esempio: il problema della dieta
Il problema della dieta è un classico della PL: scegliere quanto acquistare di ciascun alimento per coprire il fabbisogno di alcuni nutrienti al costo minimo. Variabili: le quantità di ogni alimento. Obiettivo: minimizzare il costo totale. Vincoli: per ogni nutriente, la somma dei contenuti deve superare una soglia minima.
La stessa struttura descrive la miscelazione di mangimi, di carburanti o di leghe metalliche: si combinano ingredienti con proprietà diverse per ottenere un prodotto con caratteristiche richieste al minimo costo.
Errori di modellazione frequenti
Nel mio lavoro la parte difficile non è quasi mai il calcolo, ma la traduzione. Alcuni errori ricorrenti:
- dimenticare la non negatività: senza x ≥ 0 il risolutore può proporre di produrre −30 tavoli per «liberare» ore;
- unità incoerenti: ore in un vincolo e minuti in un altro, euro e migliaia di euro nello stesso obiettivo;
- vincoli troppo stretti: il modello risulta inammissibile, cioè senza soluzioni; spesso è un segno che una richiesta va trattata come preferenza e non come obbligo;
- vincoli mancanti: il modello risulta illimitato, cioè il guadagno può crescere all'infinito; nella realtà c'è sempre un limite, per esempio la domanda di mercato, che non è stato scritto;
- non linearità nascoste: sconti di quantità, costi fissi di avviamento o scelte «tutto o niente» non sono lineari e richiedono variabili intere o binarie.
Che cosa restituisce un risolutore
Oltre ai valori ottimi delle variabili, un risolutore di PL fornisce informazioni preziose:
- quali vincoli sono attivi, cioè rispettati con il segno di uguale: sono le vere risorse scarse;
- i prezzi ombra: quanto migliorerebbe l'obiettivo con un'unità in più di ogni risorsa;
- gli intervalli di sensitività: entro quali valori i coefficienti possono variare senza cambiare la soluzione ottima.
Nel caso dei tavoli, sapere che un'ora in più di falegnameria vale 20 euro di margine e un'ora in più di verniciatura ne vale 20 aiuta a decidere se convenga pagare straordinari.
Strumenti per scriverlo al computer
Non serve implementare un algoritmo: esistono risolutori maturi, sia commerciali sia liberi, e librerie che permettono di scrivere il modello quasi come sulla carta. In Python, per esempio, librerie come PuLP o le funzioni di ottimizzazione di SciPy accettano obiettivo e vincoli e restituiscono la soluzione. Per problemi piccoli basta anche il componente di risoluzione incluso nei fogli di calcolo.
In sintesi
- Un modello di PL ha variabili decisionali, una funzione obiettivo lineare e vincoli lineari.
- La regione ammissibile è un poligono convesso e l'ottimo, se esiste, si trova in un vertice.
- Produzione, dieta e miscelazione sono esempi tipici della stessa struttura.
- Gli errori più comuni sono di modellazione: segni, unità, vincoli mancanti o troppo rigidi.
- Vincoli attivi e prezzi ombra dicono quali risorse sono davvero scarse e quanto valgono.
