Programmazione Lineare Stocastica — Ottimizzazione in Condizioni di Incertezza con Parametri Casuali
- Introdotto da
- George B. Dantzig
- Anno
- 1955
- Tipo
- Stochastic optimization model
- Famiglia
- Simulation / optimization
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La Programmazione Lineare Stocastica (SLP) estende la programmazione lineare classica a contesti in cui alcuni parametri del modello — costi, domande, disponibilità di risorse — sono incerti e modellati come variabili casuali.
Ottimizzando i costi attesi su una distribuzione di probabilità di scenari, la SLP produce decisioni che rimangono fattibili e quasi ottimali in una gamma di futuri possibili, piuttosto che per un singolo stato del mondo assunto.
L’intuizione alla base del metodo
La programmazione lineare classica assume che ogni coefficiente sia noto con precisione. In pratica, la domanda futura, i prezzi e i rendimenti sono incerti. La SLP incorpora questa incertezza direttamente nel modello: invece di ottimizzare per un unico scenario fisso, il pianificatore sceglie le azioni di primo stadio ora, osserva quale scenario si materializza, quindi intraprende azioni di ricorso per correggere qualsiasi carenza o surplus. L'obiettivo minimizza il costo totale atteso su tutti gli scenari, bilanciando i costi di impegno con i costi di ricorso attesi. Questo rispecchia la logica manageriale reale: si decide oggi cosa preordinare, e domani si può acquistare di più a un prezzo maggiorato o vendere il surplus con uno sconto.
Storia
La programmazione stocastica è stata introdotta da George Dantzig, che ha presentato il modello a due stadi nel 1955 poco dopo aver sviluppato il metodo del simplesso. Beale (1955) ha proposto indipendentemente idee simili. Il campo è stato sistematizzato dall'influente manuale di Birge e Louveaux del 1997 e dallo sviluppo dell'algoritmo di decomposizione a L (Benders) negli anni '60-'80. La SLP è ora alla base delle decisioni operative in energia, logistica e finanza in tutto il mondo.
Quando usarlo
Utilizzare la SLP quando: (1) i parametri di input chiave sono genuinamente incerti e possono essere caratterizzati da una distribuzione di probabilità o da un insieme di scenari empirici; (2) le decisioni devono essere prese prima che l'incertezza si risolva, ma azioni correttive sono possibili in seguito a un costo; (3) l'obiettivo e i vincoli sono lineari nelle variabili decisionali. Le applicazioni tipiche includono la pianificazione della produzione, la progettazione della catena di approvvigionamento, la gestione dell'energia e l'ottimizzazione del portafoglio. NON utilizzare la SLP quando: l'incertezza non può essere quantificata probabilisticamente (utilizzare invece l'ottimizzazione robusta); la relazione tra decisioni e risultati non è lineare o intera (utilizzare la programmazione stocastica MIP o la programmazione dinamica stocastica); l'insieme di scenari è troppo grande per essere enumerato e la decomposizione è computazionalmente infattibile; o quando una più semplice analisi di sensitività deterministica è sufficiente per comprendere l'impatto dell'incertezza.
Limiti e considerazioni
- Richiede la specificazione di una distribuzione di probabilità o di un insieme di scenari per i parametri incerti — questa assunzione distributiva è spesso difficile da validare.
- Il carico computazionale cresce rapidamente con il numero di scenari e variabili di primo stadio; problemi di grandi dimensioni richiedono decomposizione e significative risorse del risolutore.
- Limitata a obiettivi e vincoli lineari; strutture non lineari o intere richiedono estensioni che aggiungono ulteriore complessità.
- L'obiettivo del valore atteso può ignorare i rischi di coda; varianti avverse al rischio (CVaR, vincoli di probabilità) aggiungono overhead di modellazione e computazionale.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Incorpora direttamente l'incertezza probabilistica nell'ottimizzazione, producendo decisioni robuste tra gli scenari piuttosto che per un singolo futuro assunto.
- Il framework a due stadi rispecchia fedelmente i processi decisionali reali: impegnarsi ora, adattarsi in seguito con ricorso.
- Il Valore della Soluzione Stocastica (VSS) e l'EVPI forniscono metriche basate su principi per comunicare il beneficio della modellazione dell'incertezza.
- Ben supportata da algoritmi maturi (decomposizione a L / Benders) e risolutori commerciali (CPLEX, Gurobi).
- Scalabile a grandi problemi pratici tramite decomposizione; parallelizzabile tra scenari.
Applicazioni
- Pianificazione del sistema energetico e impegno delle unità in condizioni di incertezza della generazione rinnovabile e della domanda.
- Progettazione della rete della catena di approvvigionamento con domanda del cliente, tempi di consegna o costi di trasporto incerti.
- Pianificazione delle colture e dell'irrigazione in condizioni di incertezza delle precipitazioni e dei prezzi delle materie prime.
- Ottimizzazione del portafoglio finanziario con rendimenti degli asset incerti sotto vincoli di budget e regolamentari.
- Gestione dei ricavi delle compagnie aeree e pianificazione degli equipaggi in condizioni di incertezza della domanda dei passeggeri.
- Pre-posizionamento di forniture di soccorso nella logistica umanitaria prima di scenari di disastro incerti.
Come funziona
Come funziona
Formulare il modello a due stadi: le variabili di primo stadio x rappresentano decisioni "qui e ora" prese prima che l'incertezza sia risolta; l'obiettivo minimizza il costo di primo stadio c^T x più il costo di ricorso atteso E[Q(x,xi)] sul vettore casuale xi. I vincoli Ax = b devono valere per le decisioni di primo stadio indipendentemente dallo scenario.
Formula
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0Rappresentare il vettore casuale xi tramite un insieme discreto di scenari {xi_1, ..., xi_S} ciascuno con probabilità p_s che sommano a 1. Gli scenari possono essere derivati da dati storici, elicitazione di esperti o campionamento Monte Carlo. La qualità dell'insieme di scenari determina criticamente la qualità della soluzione; tecniche di riduzione degli scenari (ad esempio, clustering basato sulla distanza di Wasserstein) sono comunemente applicate per mantenere la dimensione del problema gestibile.
Per ogni scenario xi_s, risolvere il sottoproblema di ricorso: data la decisione di primo stadio x, trovare l'azione correttiva più economica y_s che soddisfi W y_s = h(xi_s) - T(xi_s) x, y_s >= 0. Se non esiste un ricorso fattibile, viene applicata una grande penalità (o infattibilità), segnalando che la decisione di primo stadio era troppo aggressiva.
Formula
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0Risolvere la forma estesa completa (tutti gli scenari impilati come un unico grande LP) per insiemi di scenari di piccole e medie dimensioni, oppure applicare la decomposizione di Benders (metodo a L) per insiemi grandi. Il metodo a L aggiunge iterativamente tagli di ottimalità e fattibilità a un problema master fino alla convergenza, sfruttando la struttura a blocchi diagonali dei sottoproblemi di scenario.
Valutare la qualità della soluzione tramite il Valore della Soluzione Stocastica (VSS) — il guadagno rispetto alla soluzione deterministica a valore medio — e il Valore Atteso dell'Informazione Perfetta (EVPI) — il limite superiore di quanto varrebbe una previsione perfetta. Riportare la decisione di primo stadio x*, il costo totale atteso e i costi di ricorso per scenario per comunicare il profilo di rischio ai decisori.
Errori comuni
- L'utilizzo di troppo pochi scenari produce una soluzione distorta che si comporta male fuori campione; validare sempre con test di scenari fuori campione.
- Confondere la soluzione deterministica a valore medio (sostituire i valori attesi) con la soluzione stocastica — il VSS può essere elevato anche quando i parametri sembrano stabili.
- Ignorare la fattibilità del ricorso: se il sottoproblema del secondo stadio può essere infattibile per alcuni scenari, il modello necessita di vincoli di ricorso completi o penalità esplicite.
- Sovra-adattamento alla distribuzione storica degli scenari senza test di stress contro scenari di coda o avversi, specialmente nelle applicazioni di catena di approvvigionamento o finanziarie.
- Trattare la programmazione lineare stocastica come un sostituto diretto dell'ottimizzazione robusta quando il decisore è in realtà avverso all'incertezza piuttosto che neutrale al valore atteso.
Domande frequenti
Qual è la differenza tra programmazione lineare stocastica e ottimizzazione robusta?
La SLP minimizza il costo atteso su una distribuzione di probabilità di scenari e consente azioni di ricorso dopo che l'incertezza si è risolta. L'ottimizzazione robusta invece ottimizza il caso peggiore su un insieme di incertezza senza assumere una distribuzione di probabilità e tipicamente produce un'unica soluzione fissa che è fattibile per tutti gli scenari. La SLP è preferibile quando le probabilità possono essere stimate; l'ottimizzazione robusta è preferibile quando è noto solo l'insieme di incertezza o quando la protezione dal rischio di coda è fondamentale.
Quanti scenari sono tipicamente necessari?
Ciò dipende dalla dimensione del problema e dalla complessità distributiva. Da decine a poche centinaia di scenari sono spesso sufficienti per i problemi di pianificazione se generati in modo intelligente (ad esempio, tramite moment-matching o riduzione degli scenari). L'approssimazione della media campionaria (SAA) basata su Monte Carlo può richiedere migliaia di scenari per soluzioni ad alta precisione, con intervalli di confidenza che guidano la convergenza.
La SLP può gestire decisioni intere o binarie?
Non direttamente — le variabili intere richiedono la Programmazione Intera Stocastica (SIP) o la Programmazione Lineare Intera Mista Stocastica (SMIP), che sono sostanzialmente più difficili dal punto di vista computazionale. La SLP si applica solo quando tutte le variabili decisionali sono continue.
Cosa misura il Valore della Soluzione Stocastica (VSS)?
VSS = EEV - RP, dove EEV è il costo atteso della soluzione deterministica a valore medio valutata su tutti gli scenari, e RP è l'ottimo stocastico vero (problema di ricorso). Un VSS elevato indica che ignorare l'incertezza e utilizzare parametri medi porta a risultati sostanzialmente peggiori.
Quali risolutori e software supportano la programmazione lineare stocastica?
Risolutori commerciali come CPLEX e Gurobi possono risolvere direttamente la forma estesa. I framework open source includono lettori di formato SMPS, PySP (parte di Pyomo) e il pacchetto Julia StochasticPrograms.jl. Per problemi su larga scala, le implementazioni personalizzate della decomposizione a L sono comuni nella ricerca e nell'industria.
Metodi correlati
Fonti
Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.
Apri il riferimento della pubblicazioneCopiato.Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 9780387982175Copiato.