Programmazione Lineare — Ottimizzazione di Obiettivi Lineari Sotto Vincoli Lineari
- Introdotto da
- George B. Dantzig
- Anno
- 1947
- Tipo
- Mathematical programming / continuous optimization
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La programmazione lineare (PL), il cui pioniere fu George B. Dantzig nel 1947, è un metodo matematico per trovare il valore migliore di una funzione obiettivo lineare — come il costo minimo o il profitto massimo — soggetta a un insieme di vincoli di disuguaglianza e uguaglianza lineari.
È la tecnica fondamentale nella ricerca operativa e sottende la pianificazione della produzione, l'allocazione delle risorse, la logistica, i problemi dietetici e innumerevoli altri scenari decisionali in ingegneria, economia e scienze naturali.
L’intuizione alla base del metodo
Immaginate di gestire una piccola fabbrica che produce due prodotti. Ogni prodotto vi frutta un certo profitto, ma la sua realizzazione consuma materie prime e tempo macchina limitati. La programmazione lineare trova la combinazione esatta di prodotti che estrae il massimo profitto dalle vostre risorse fisse — senza violare alcun limite fisico o contrattuale. La parte 'lineare' significa che il profitto e il consumo di risorse scalano in una relazione lineare con le quantità prodotte. Le scelte fattibili formano un poligono (in due dimensioni) o un poliedro (in dimensioni superiori), e la risposta ottimale si trova sempre in uno dei suoi vertici.
Storia
Lo sviluppo sistematico della programmazione lineare iniziò nel 1947 quando George B. Dantzig, lavorando per l'U.S. Air Force, inventò l'algoritmo del Simplesso per automatizzare la pianificazione della logistica militare. Dantzig pubblicò la teoria fondamentale nella sua monografia del 1963, che rimane il riferimento canonico. Lavoro indipendente e parallelo di Leonid Kantorovich nell'Unione Sovietica (1939) affrontò la pianificazione della produzione utilizzando idee matematiche simili, e Kantorovich fu insignito del Premio Nobel per l'Economia nel 1975 in parte per questo contributo. La questione teorica della risolvibilità in tempo polinomiale fu risolta dal metodo delle ellissoidi di Khachian (1979) e successivamente dal metodo del punto interno di Karmarkar (1984), che si dimostrò praticamente veloce per problemi su larga scala. Oggi, risolutori PL commerciali e open-source sono integrati nei sistemi di pianificazione delle risorse aziendali, nella programmazione delle compagnie aeree e nei sistemi energetici in tutto il mondo.
Quando usarlo
La programmazione lineare è appropriata ogni volta che si deve ottimizzare una quantità che dipende linearmente da un insieme di variabili decisionali, e tutti i vincoli sono anch'essi lineari. Non richiede assunzioni distributive né una dimensione minima del campione — è un modello matematico deterministico, non uno stimatore statistico. Il metodo si applica quando le variabili decisionali sono continue (valori frazionari sono significativi); se le variabili devono essere numeri interi o binari, è necessaria invece la programmazione intera. La PL è ampiamente utilizzata nella pianificazione della produzione, nella logistica della catena di approvvigionamento, nei problemi dietetici e di miscelazione, nell'ottimizzazione di portafogli finanziari, nei problemi di trasporto e assegnazione, e nella gestione dell'energia.
Limiti e considerazioni
- Requisito di linearità: se l'obiettivo o qualsiasi vincolo è non lineare, il modello PL è mal specificato e la soluzione potrebbe essere errata o infattibile.
- Solo variabili continue: quando le variabili decisionali devono assumere valori interi o binari, il rilassamento PL fornisce un limite inferiore ma non una soluzione valida; è necessario utilizzare la programmazione intera.
- Deterministica: la PL non modella l'incertezza nei parametri; è necessaria la programmazione stocastica o l'ottimizzazione robusta quando i dati sono incerti.
- Degenerazione e ciclaggio: in rari casi il metodo del Simplesso può ciclare tra basi degenerate senza convergere, sebbene regole anti-ciclaggio (es. regola di Bland) risolvano questo problema.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Ottimo globale garantito: poiché la regione fattibile è un poliedro convesso, qualsiasi ottimo locale è anche un ottimo globale, senza rischio di rimanere intrappolati in una soluzione sub-ottimale.
- Altamente scalabile: i moderni risolutori (HiGHS, Gurobi, CPLEX) gestiscono modelli con milioni di variabili e vincoli in pochi secondi.
- Ricche informazioni post-soluzione: prezzi ombra e intervalli di sensibilità forniscono informazioni azionabili sul valore delle risorse e sulla robustezza della soluzione senza esecuzioni aggiuntive.
- Nessuna assunzione distributiva: la PL è un modello puramente algebrico, quindi non richiede normalità o alcuna proprietà statistica dei dati.
Applicazioni
- Pianificazione della produzione: trovare il mix di prodotti ottimale che massimizza il profitto rispettando la capacità delle macchine e i limiti delle materie prime.
- Logistica della catena di approvvigionamento e dei trasporti: minimizzare i costi di spedizione attraverso una rete di magazzini e clienti.
- Problemi dietetici e di miscelazione: selezionare le quantità di ingredienti che soddisfano i requisiti nutrizionali al minimo costo.
- Ottimizzazione di portafogli finanziari: allocare il capitale tra gli asset per massimizzare il rendimento atteso soggetto a vincoli di rischio e normativi.
- Gestione dell'energia e programmazione della rete elettrica: minimizzare i costi del carburante soddisfacendo la domanda di elettricità e i limiti di capacità dei generatori.
- Pianificazione del personale e della forza lavoro: assegnare turni ai lavoratori per coprire la domanda al minimo costo del lavoro.
Come funziona
Come funziona
Il problema decisionale del mondo reale viene tradotto in simboli matematici. Si identificano le variabili decisionali (le quantità che si possono controllare), si scrive la funzione obiettivo (ciò che si vuole massimizzare o minimizzare) come una combinazione lineare di tali variabili, e si scrivono tutti i vincoli — limiti di risorse, capacità, requisiti di domanda — come una disuguaglianza o uguaglianza lineare. Una PL ben formulata ha un obiettivo chiaro, limiti espliciti delle variabili e ogni vincolo strutturale espresso linearmente.
Il modello viene portato in una forma canonica o standard che un risolutore può elaborare. Le disuguaglianze vengono convertite in uguaglianze introducendo variabili di scarto (slack) o di surplus non negative, e ogni variabile non ristretta viene sostituita dalla differenza di due variabili non negative. Questo passaggio meccanico produce il tableau o la rappresentazione matriciale su cui agisce l'algoritmo, e non modifica il problema — lo riorganizza solo per il calcolo.
Un risolutore cerca nel poliedro fattibile il vertice ottimale. Il classico metodo del Simplesso pivota da vertice a vertice lungo gli spigoli del poliedro, migliorando (o mantenendo) sempre l'obiettivo, finché non esiste un vicino migliorativo. I metodi del punto interno (barriera), invece, viaggiano attraverso l'interno della regione fattibile lungo un percorso centrale, che è particolarmente efficiente per modelli molto grandi. Entrambe le famiglie sono garantite per trovare un ottimo globale quando esiste, poiché la regione fattibile è convessa.
Il risolutore restituisce i valori ottimali delle variabili decisionali e il valore obiettivo ottimale, insieme alle variabili duali (prezzi ombra) e agli intervalli di sensibilità. I prezzi ombra quantificano quanto migliorerebbe l'obiettivo se un vincolo vincolante fosse rilassato di una unità — indicando direttamente a un decisore dove risorse aggiuntive sarebbero più preziose. L'analisi di sensibilità identifica quanto un coefficiente di costo o un valore del lato destro può cambiare prima che la base corrente cessi di essere ottimale.
Errori comuni
- Applicare la PL quando i vincoli o l'obiettivo sono non lineari — la soluzione sarà errata o il risolutore rifiuterà il modello.
- Ignorare i requisiti di interezza: arrotondare una soluzione PL continua a interi in generale non produce una soluzione intera fattibile o ottimale; utilizzare invece la programmazione intera.
- Modelli infattibili o illimitati: se la regione fattibile è vuota (vincoli conflittuali) o l'obiettivo è illimitato (mancanza di vincoli di limitazione), il risolutore segnalerà un errore — controllare sempre la struttura del modello prima dell'esecuzione.
- Trattare l'output della PL come una raccomandazione senza analisi di sensibilità: una soluzione tecnicamente ottimale potrebbe trovarsi su un bordo sottile dove una piccola variazione dei dati inverte la raccomandazione — gli intervalli di sensibilità dovrebbero sempre essere ispezionati.
Domande frequenti
Cosa rende un problema 'lineare' ai fini della PL?
Sia la funzione obiettivo che ogni vincolo devono essere lineari — il che significa che ogni termine è una costante moltiplicata per una singola variabile decisionale, senza prodotti di variabili, esponenti o funzioni non lineari. Se anche un solo vincolo o l'obiettivo coinvolge, ad esempio, x moltiplicato per y o x al quadrato, la PL standard non si applica più e è necessario un risolutore di programmazione non lineare o quadratica.
Perché la soluzione ottimale si trova sempre in un vertice della regione fattibile?
La regione fattibile definita da vincoli lineari è un poliedro (o politopo) convesso. Una funzione obiettivo lineare è essa stessa lineare, quindi non può essere 'tirata' verso l'interno di un insieme convesso — raggiunge sempre il suo valore estremo sul bordo, e specificamente in un vertice (punto d'angolo). Questa è l'intuizione geometrica alla base della strategia del metodo del Simplesso da vertice a vertice.
Quando dovrei usare la programmazione intera invece della PL?
Ogni volta che una o più variabili decisionali devono assumere valori interi o binari (0/1) — ad esempio, se aprire o meno una struttura (sì/no), quanti camion spedire (numeri interi), o quali articoli includere in una selezione. Semplicemente risolvere la PL e arrotondare la soluzione continua non è affidabile: le soluzioni arrotondate possono essere infattibili o lontane dall'ottimale. La programmazione intera gestisce correttamente l'interezza, a un costo computazionale maggiore.
Cosa mi dicono i prezzi ombra?
Un prezzo ombra (variabile duale) per un vincolo vincolante indica quanto migliorerebbe il valore obiettivo ottimale se il lato destro di quel vincolo fosse rilassato di una unità, mantenendo tutto il resto costante. Ad esempio, un prezzo ombra di 3 su un vincolo di ore di lavoro significa che aggiungere un'ora di lavoro in più migliorerebbe l'obiettivo di 3 unità. I vincoli che non sono vincolanti hanno un prezzo ombra pari a zero — non limitano l'ottimo corrente.
Metodi correlati
Fonti
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Copiato.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Apri il riferimento DOICopiato.