La programmazione lineare (PL) è una classe di problemi di ottimizzazione in cui una funzione obiettivo lineare viene massimizzata o minimizzata su una regione ammissibile definita da vincoli lineari. È uno dei modelli fondamentali della ricerca operativa, perché traduce decisioni su risorse limitate in un sistema matematico risolvibile e interpretabile.
Un modello lineare tipico descrive quantità da produrre, spedire, miscelare, assegnare, acquistare o allocare. La forza della PL non sta solo nel calcolo dell’ottimo, ma anche nella lettura post-ottimale: vincoli attivi, risorse residue, prezzi ombra e sensibilità dei coefficienti spiegano perché una soluzione è ottima e quali risorse limitano davvero il sistema.
Forma canonica
Una forma canonica di massimizzazione è:
Le componenti hanno una lettura operativa precisa:
| Oggetto | Significato |
|---|---|
| x | variabili decisionali continue |
| c | profitti, benefici, costi o pesi unitari nell’obiettivo |
| A | coefficienti tecnologici o consumi unitari |
| b | risorse disponibili, capacità, soglie o limiti |
| Ax\le b | vincoli di risorsa, domanda, capacità o compatibilità |
| x\ge0 | non negatività delle decisioni fisiche |
Il modello può essere scritto anche come minimizzazione, con vincoli di tipo \ge, uguaglianze o variabili libere. Le trasformazioni algebriche portano poi a una forma standard adatta agli algoritmi.
Ipotesi di linearità
La linearità implica due ipotesi operative:
- proporzionalità: raddoppiare una decisione raddoppia consumo e contributo;
- additività: l’effetto totale è la somma degli effetti delle singole decisioni.
Si assume inoltre che le variabili siano divisibili, quindi possano assumere valori reali continui. Questa ipotesi è ragionevole per tonnellate, ore, flussi, miscele, energia o budget aggregati; è meno adatta quando le decisioni sono intere, binarie o indivisibili.
Quando compaiono costi fissi, soglie, lotti minimi, sconti a scaglioni, saturazioni, prodotti tra variabili o decisioni sì/no, una PL pura non basta. Si passa allora a programmazione intera, ottimizzazione non lineare, modelli misti o linearizzazioni esplicite.
Regione ammissibile e vertici
Ogni vincolo lineare definisce un semispazio:
L’intersezione di un numero finito di semispazi è un poliedro:
La regione ammissibile di una PL è quindi convessa. Se due soluzioni sono ammissibili, anche ogni loro combinazione convessa è ammissibile:
Se l’ottimo finito esiste, almeno un vertice del poliedro è ottimo. In due variabili questo si vede graficamente valutando la funzione obiettivo sui vertici della regione ammissibile. In dimensione più alta lo stesso principio resta valido ed è la base geometrica del metodo del simplesso.
Forma standard e variabili di scarto
Per applicare molti algoritmi si usa la forma standard:
Un vincolo \le si trasforma in uguaglianza aggiungendo una variabile di scarto:
La variabile s_i misura la risorsa inutilizzata. Se s_i=0, il vincolo è attivo; se s_i\gt0, resta slack. Per vincoli \ge si sottrae una variabile di surplus e, se serve una base iniziale, si introducono variabili artificiali nelle procedure di fase I.
Soluzioni di base e simplesso
Il metodo del simplesso risolve una PL spostandosi tra soluzioni di base ammissibili, cioè vertici del poliedro. Scelta una base B di colonne indipendenti della matrice A, si scrive:
Ponendo le variabili non di base a zero:
Se x_B\ge0, la base è ammissibile. Il simplesso controlla i costi ridotti:
In una massimizzazione, se tutti i costi ridotti sono non positivi, la base corrente è ottima. Se esiste un costo ridotto positivo, la variabile corrispondente può entrare in base; il test del rapporto minimo decide quale variabile esce senza violare l’ammissibilità.
Dualità e prezzi ombra
A ogni PL si associa un problema duale. Per il primale canonico:
il duale è:
La dualità lineare fornisce limiti, certificati di ottimalità e interpretazioni economiche. Le variabili duali ottime sono prezzi ombra: misurano il valore marginale delle risorse. Gli scarti complementari legano vincoli attivi e variabili duali:
Un vincolo non saturo ha prezzo ombra nullo; un vincolo attivo può avere valore marginale positivo se quella risorsa è davvero scarsa nella soluzione ottima.
Casi possibili
Una PL può avere esiti diversi:
| Caso | Significato operativo |
|---|---|
| ottimo unico | un solo vertice massimizza o minimizza l’obiettivo |
| ottimi multipli | un intero lato o faccia del poliedro è ottimo |
| problema infeasibile | i vincoli sono incompatibili |
| problema illimitato | l’obiettivo migliora senza limite nella regione ammissibile |
| degenerazione | una base ammissibile ha variabili di base nulle |
L’infeasibilità spesso segnala vincoli contraddittori o requisiti troppo severi. L’illimitatezza indica quasi sempre un vincolo mancante, un verso sbagliato o un modello economico incompleto. La degenerazione non rende il modello sbagliato, ma può complicare il simplesso e l’interpretazione della sensitività.
Applicazioni
La programmazione lineare compare in:
- pianificazione della produzione e mix di prodotti;
- problemi di miscelazione e blend;
- allocazione di personale, macchine e budget;
- logistica, distribuzione e problemi di trasporto;
- flussi su rete e assegnamenti continui;
- gestione energetica e portafogli semplificati;
- analisi di capacità e colli di bottiglia.
La qualità del risultato dipende dalla qualità del modello. Una soluzione numericamente ottima può essere inutile se variabili, coefficienti o vincoli non rappresentano correttamente il sistema reale.
Errori comuni
Il primo errore è chiamare “lineare” un modello con prodotti tra variabili, costi fissi o condizioni logiche non linearizzate. Il secondo è dimenticare vincoli di non negatività o limiti fisici, ottenendo soluzioni matematicamente ammissibili ma impossibili nel sistema reale.
Un altro errore è interpretare le variabili continue come quantità intere quando il problema richiede decisioni indivisibili. Se il risultato dice di aprire 2{,}4 stabilimenti o acquistare 7{,}6 macchine, serve un modello intero, non un arrotondamento arbitrario.
Infine, non bisogna fermarsi al vettore ottimo x^\ast. In una PL ben usata si leggono anche vincoli attivi, scarti, costi ridotti, prezzi ombra e intervalli di sensitività: sono spesso la parte più utile per decidere cosa cambiare nel sistema.
Vedi anche: Dualità lineare, Prezzo ombra, Metodo del simplesso, Programmazione intera, Problema dei trasporti, Formulario di ricerca operativa ed esercizi di programmazione lineare.