Skip to content
Torna ai risultati

Programmazione Lineare Deterministica — LP Classica con Parametri Certi

Introdotto da
George B. Dantzig
Anno
1947
Tipo
Deterministic mathematical optimization
Famiglia
Simulation / optimization

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La Programmazione Lineare Deterministica (DLP) è la forma classica di programmazione lineare in cui tutti i coefficienti della funzione obiettivo, i coefficienti dei vincoli e i valori del lato destro sono noti con certezza.

Trova l'allocazione ottimale delle risorse per massimizzare o minimizzare un obiettivo lineare soggetto a vincoli lineari, fornendo una soluzione esatta e riproducibile in presenza di dati fissi e certi.

L’intuizione alla base del metodo

Immaginate di allocare un budget fisso tra progetti, ciascuno con costi e rendimenti noti, soggetti a limiti di risorse che conoscete con precisione. La DLP codifica questo come un sistema di disuguaglianze lineari e trova la soluzione d'angolo che estrae il massimo valore da tali vincoli. Poiché ogni parametro è certo — nessuna distribuzione di probabilità, nessuna ambiguità — il risolutore restituisce un singolo piano ottimale esatto anziché una distribuzione di esiti. Questa chiarezza rende la DLP il modello di prima scelta naturale quando i dati sono ben misurati e l'incertezza non è una preoccupazione primaria.

Storia

La programmazione lineare fu formalizzata da George B. Dantzig nel 1947 con lo sviluppo dell'algoritmo del simplesso mentre lavorava per l'U.S. Air Force. La monografia di Dantzig del 1963 divenne il riferimento canonico. Il qualificatore 'deterministica' emerse con l'introduzione di varianti di programmazione lineare stocastica (Dantzig e Beale, anni '50-'60) per distinguere il modello originale a parametri certi dalle sue estensioni probabilistiche.

Quando usarlo

Utilizzare la DLP quando il problema decisionale può essere modellato con un obiettivo lineare e vincoli lineari, e quando tutti i parametri sono noti con sufficiente certezza da giustificarne il trattamento come costanti fisse. Impostazioni ideali includono pianificazione della produzione, trasporti e logistica, problemi di dieta e miscelazione, e flussi di rete in condizioni stabili. NON utilizzare la DLP quando i parametri sono genuinamente incerti e il rischio è rilevante — preferire invece la Programmazione Lineare Stocastica o Robusta. Evitare la DLP quando l'obiettivo o i vincoli sono non lineari, quando le variabili devono essere intere (utilizzare MIP), o quando più obiettivi conflittuali devono essere bilanciati simultaneamente senza aggregarli in un'unica somma pesata (utilizzare la programmazione lineare multi-obiettivo o la programmazione per obiettivi).

Limiti e considerazioni

  • Richiede che tutte le relazioni siano strettamente lineari — curve di costo non lineari o rendimenti decrescenti non possono essere catturati senza approssimazione.
  • Tutti i parametri devono essere noti e fissi; il modello non fornisce meccanismi nativi per gestire l'incertezza o errori di stima dei parametri.
  • La soluzione ottimale può essere non unica (degenere), rendendo ambigua la scelta della base da riportare senza criteri aggiuntivi.
  • Requisiti interi o combinatori (ad es., decisioni sì/no) richiedono estensione alla programmazione lineare intera mista, che è computazionalmente più complessa.
  • Problemi su larga scala con matrici di vincoli dense possono richiedere molta memoria anche per risolutori moderni.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Soluzione ottima globale garantita per qualsiasi istanza LP ammissibile e limitata grazie alla convessità.
  • Altamente scalabile — i risolutori moderni gestiscono milioni di variabili e vincoli in pochi secondi.
  • Le variabili duali e l'analisi di sensibilità forniscono una ricca interpretazione economica dei prezzi ombra e dei range.
  • Formulazione trasparente e verificabile: ogni assunzione è esplicita nella matrice dei vincoli.
  • Ecosistema software maturo (CPLEX, Gurobi, HiGHS, GLPK) con implementazioni affidabili e ben testate.
  • Segnale di ammissibilità chiaro sì/no: l'inammissibilità rivela immediatamente una errata specificazione del modello.

Applicazioni

  • Pianificazione della produzione e della manifattura con capacità di risorse fisse e domanda nota.
  • Trasporti e logistica: ricerca dei percorsi di spedizione a costo minimo attraverso una rete.
  • Problemi di dieta e miscelazione: formulazione di miscele nutrizionali o chimiche a costo minimo che soddisfino vincoli di composizione.
  • Ottimizzazione di portafoglio finanziario sotto vincoli lineari di rendimento e budget.
  • Pianificazione di sistemi energetici: dispacciamento ottimale di unità di generazione elettrica con costi e capacità noti.
  • Progettazione di reti di supply chain quando domanda e tempi di consegna sono trattati come costanti note.

Come funziona

Come funziona

1

Definire le variabili decisionali x (ad es., quantità di produzione, flussi), la funzione obiettivo c^T x da minimizzare o massimizzare, e il sistema di vincoli Ax <= b con x >= 0. Tutti i coefficienti in c, A e b sono trattati come costanti esatte e note — questo è ciò che rende il modello deterministico. Scrivere l'LP in forma standard: min c^T x soggetto a Ax = b, x >= 0.

Formula
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

Prima di ottimizzare, verificare che la regione ammissibile non sia vuota (il sistema di vincoli ha almeno una soluzione) e che l'obiettivo sia limitato. Se la regione ammissibile è vuota, il problema è inammissibile; se l'obiettivo è illimitato, il modello è mal specificato. Questi controlli vengono eseguiti automaticamente dai risolutori, ma dovrebbero essere interpretati dall'analista per individuare errori di formulazione.

3

Risolvere l'LP utilizzando l'algoritmo del simplesso (pivotando lungo i bordi del politopo convesso verso il vertice ottimale) o un metodo a punti interni (seguendo un percorso attraverso l'interno della regione ammissibile). Entrambi gli approcci sfruttano la convessità dell'insieme ammissibile e la linearità dell'obiettivo, garantendo che qualsiasi ottimo locale sia globale. I risolutori moderni (CPLEX, Gurobi, HiGHS) gestiscono milioni di variabili e vincoli in modo efficiente.

4

Il risolutore restituisce il vettore decisionale ottimale x* e il valore obiettivo ottimale c^T x*. Poiché la regione ammissibile è un politopo convesso e l'obiettivo è lineare, l'ottimo è sempre raggiunto in un vertice (soluzione ammissibile di base). Registrare x* e verificare che soddisfi tutti i vincoli, quindi tradurlo in termini gestionali (ad es., unità da produrre, percorsi da utilizzare).

Formula
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

Dopo aver ottenuto x*, condurre un'analisi di sensibilità (post-ottimalità) per determinare quanto ciascun coefficiente in c o b possa variare prima che la base corrente — e quindi la soluzione ottimale — cambi. I prezzi ombra (variabili duali) quantificano il valore marginale del rilassamento di ciascun vincolo. Sebbene il modello sia deterministico, l'analisi di sensibilità rivela la robustezza della soluzione rispetto agli errori di stima dei parametri senza abbandonare il quadro deterministico.

Errori comuni

  • Trattare parametri incerti come stime puntuali fisse senza successiva analisi di sensibilità può produrre soluzioni ottimali sulla carta ma fragili nella pratica.
  • Dimenticare di includere vincoli di non-negatività o limiti logici può produrre soluzioni matematicamente ottimali ma operativamente inammissibili (ad es., quantità di produzione negative).
  • Errata interpretazione dei prezzi ombra come valori marginali garantiti al di fuori dell'intervallo di validità identificato nell'analisi dei range.
  • Utilizzare la DLP quando il problema reale ha una struttura intera (ad es., numero di camion) e arrotondare le soluzioni LP — questo può violare i vincoli o mancare l'ottimo intero reale.
  • Eccessiva aggregazione di obiettivi in un'unica somma pesata senza validare che i pesi riflettano accuratamente le preferenze degli stakeholder, nascondendo importanti trade-off.

Domande frequenti

Cosa rende la LP 'deterministica' invece di 'stocastica'?

Nella LP deterministica, ogni coefficiente nella funzione obiettivo, nella matrice dei vincoli e nel vettore del lato destro è una costante nota. La LP stocastica, al contrario, tratta alcuni o tutti questi come variabili casuali con distribuzioni di probabilità, cercando soluzioni che si comportino bene in media o con alta probabilità attraverso diversi scenari.

L'algoritmo del simplesso è sempre efficiente?

In pratica, sì — il metodo del simplesso risolve quasi tutti gli LP del mondo reale molto velocemente. Teoricamente può richiedere tempo esponenziale nel caso peggiore (esempi di Klee-Minty), ma i metodi a punti interni (ad es., algoritmo di Karmarkar) funzionano in tempo polinomiale e sono competitivi per istanze molto grandi.

Posso usare la DLP se alcune delle mie variabili decisionali devono essere numeri interi?

No. Se le variabili devono essere intere (ad es., numero di macchine da acquistare), il modello diventa un programma lineare misto o intero puro. Risolvere il rilassamento LP e arrotondare può violare i vincoli o mancare l'ottimo intero reale; utilizzare invece un risolutore MIP dedicato.

Come aiutano i prezzi ombra dopo la risoluzione?

Il prezzo ombra (variabile duale) di un vincolo indica quanto migliorerebbe il valore obiettivo se il lato destro di quel vincolo venisse rilassato di un'unità, all'interno dell'intervallo di validità. Questo guida le decisioni su dove investire per espandere la capacità nel modo più conveniente.

Quando dovrei passare dalla DLP alla LP Robusta o Stocastica?

Passare quando l'incertezza dei parametri è non trascurabile e il costo di una soluzione inammissibile o scadente con i valori dei parametri realizzati è significativo. Se una deviazione del 10-20% in un coefficiente chiave cambiasse la soluzione preferita o causasse la violazione di un vincolo, l'assunzione di certezza della DLP è troppo forte.

Metodi correlati

Fonti

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

    ISBN: 9780691059136
    Copiato.
  2. Linear programming. Wikipedia.

    Apri il riferimento della pubblicazione
    Copiato.