Hai mai dovuto preparare una valigia per un volo low-cost? Hai un limite di peso (10kg) e uno di spazio (il trolley piccolo). Vuoi portare più vestiti possibili, ma anche le scarpe e il computer. Ti trovi a fare calcoli mentali: “Se tolgo un paio di scarpe, posso mettere due magliette in più”. Senza saperlo, stai risolvendo un problema di Programmazione Lineare.
In economia e ingegneria, questo è il pane quotidiano. Le risorse (soldi, tempo, materie prime) sono limitate, ma i nostri desideri (profitto, efficienza) sono infiniti. La Programmazione Lineare è il metodo matematico esatto per trovare la soluzione ottima in un mondo di vincoli. Non la soluzione “buona” o “accettabile”. La migliore in assoluto.
INDICE
I Tre Ingredienti dell’Ottimizzazione
Ogni problema di programmazione lineare si costruisce con tre blocchi matematici:
- Le Variabili Decisionali: Cosa posso controllare? (es. Quantità di prodotto A e B da fabbricare).
- La Funzione Obiettivo: Cosa voglio ottenere? Di solito è una formula da massimizzare (Profitto = $5A + 3B$) o minimizzare (Costo = $2A + 4B$). È una retta, per questo si chiama “lineare”.
- I Vincoli: I limiti della realtà. Sono disuguaglianze che non posso violare (es. Ore macchina disponibili $\leq 100$).
La Magia dei Vertici (Il Teorema Fondamentale)
Immagina di disegnare questi vincoli su un grafico cartesiano. Ogni vincolo è una linea che taglia via una parte del piano. Alla fine, ti resta un’area chiusa a forma di poligono: quella è la Regione Ammissibile. Tutte le soluzioni possibili sono lì dentro.
Ma qual è la migliore? Qui arriva la magia matematica. Non hai bisogno di controllare gli infiniti punti dentro l’area. Il Teorema Fondamentale della Programmazione Lineare dice che la soluzione ottima si trova sempre su uno dei vertici (gli angoli) del poligono.
Perché? Immagina la Funzione Obiettivo come un righello che fai scorrere sul grafico. Il righello toccherà l’ultimo punto del poligono prima di uscire: quel punto è sempre un angolo. Questo rende i calcoli incredibilmente veloci per i computer: invece di cercare ovunque, l’algoritmo (chiamato Metodo del Simplesso) salta semplicemente da un vertice all’altro finché non trova quello più alto.
🌍 Esempi nella Realtà: La Dieta dei Soldati e Amazon
La Programmazione Lineare non è nata per caso, ma per necessità belliche.
Uno dei primi esempi storici è il Problema della Dieta (The Diet Problem), studiato da George Stigler nel 1945. L’esercito doveva nutrire i soldati al costo minimo, garantendo però un minimo di calorie, vitamine e proteine (i vincoli). C’erano 77 alimenti possibili. Senza computer, ci vollero giorni di calcoli a mano per trovare che la dieta ottima (e disgustosa) consisteva in farina di grano, cavoli, spinaci e fegato di manzo essiccato.
Oggi, la programmazione lineare gestisce la logistica mondiale. Quando Amazon o FedEx devono consegnare 1 milione di pacchi con 10.000 camion, usano algoritmi derivati da questo metodo per minimizzare il carburante (Funzione Obiettivo) rispettando i tempi di consegna e la capacità dei camion (Vincoli). Se il tuo pacco arriva in tempo, ringrazia i vertici del poligono.
📜 Trafiletto di Storia
Il padre della Programmazione Lineare è George Dantzig. La sua storia sembra una leggenda metropolitana, ma è vera (ed è citata nel film Will Hunting). Nel 1939, Dantzig arrivò in ritardo a una lezione di statistica all’Università di Berkeley. Vide due problemi scritti alla lavagna, pensò fossero i compiti per casa e li copiò. Erano difficilissimi. Dopo qualche giorno li consegnò al professore, scusandosi per il ritardo. Anni dopo, scoprì che quelli non erano compiti, ma due famosi problemi statistici irrisolti che nessun matematico al mondo era mai riuscito a dimostrare. Lui li aveva risolti per sbaglio, pensando fossero esercizi standard! Fu proprio quella mente a sviluppare poi il Metodo del Simplesso nel 1947 per l’Air Force americana.