Il Metodo del Simplesso¶
La Storia Dietro la Matematica¶
Nel 1947, George Dantzig (1914-2005), un giovane matematico che lavorava per la U.S. Air Force, si trovò di fronte a una sfida impegnativa: come allocare in modo ottimale risorse— aerei, personale, carburante— attraverso migliaia di missioni rispettando innumerevoli vincoli. Il problema era troppo vasto per essere risolto con tentativi ed errori.
Dantzig si rese conto che questi problemi di allocazione potevano essere espressi come programmi lineari: massimizzare (o minimizzare) una funzione obiettivo lineare soggetta a vincoli lineari. Ma risolverli in modo efficiente richiedeva un nuovo algoritmo. Una sera, mentre cercava di trovare una dieta ottimale per i militari (minimizzando i costi rispettando i requisiti nutrizionali), arrivò la svolta.
Dantzig notò qualcosa di straordinario: la soluzione ottimale si trova sempre in un "angolo" (vertice) della regione ammissibile. Invece di cercare ovunque, poteva saltare da vertice a vertice, migliorando sempre l'obiettivo, fino a raggiungere l'ottimo. Questa fu la nascita del Metodo del Simplesso.
La controversia: Gli informatici scoprirono in seguito che il Metodo del Simplesso poteva, in rari scenari peggiori, visitare un numero esponenziale di vertici. Eppure in pratica, risolve i problemi reali con una sorprendente efficienza. Questo "mistero algoritmico" ha perplesso i ricercatori per decenni. Non fu fino al 1979 che Leonid Khachiyan dimostrò che la programmazione lineare poteva essere risolta in tempo polinomiale con il suo metodo delle ellissi, e successivamente Narendra Karmarkar (1984) sviluppò metodi di punti interni che erano sia teoricamente efficienti che praticamente competitivi con il Simplesso.
Ma il Metodo del Simplesso rimane il cavallo di battaglia dell'ottimizzazione—elegante, intuitivo e incredibilmente veloce per la maggior parte dei problemi reali.
Perché Importa¶
Il Metodo del Simplesso alimenta: - Ottimizzazione della supply chain — FedEx, Amazon instradano miliardi di pacchi - Ottimizzazione del portafoglio — Wall Street bilancia rischio vs rendimento - Produzione manifatturiera — Toyota minimizza gli sprechi nelle linee di produzione - Reti energetiche — Distribuzione di elettricità in tempo reale - Agricoltura — Mix ottimale di colture per il profitto - Sanità — Pianificazione del personale ospedaliero - Teoria dei giochi — Calcolo dell'equilibrio di Nash
Ogni volta che ottieni un percorso da Google Maps, ogni volta che Netflix ti consiglia un film, algoritmi di ottimizzazione (spesso discendenti dal Simplesso) lavorano dietro le quinte.
Prerequisiti¶
- Programmazione Lineare — Formulazione del problema
- Sistemi di equazioni lineari
- Algebra lineare di base (notazione matriciale)
- Geometria dei poliedri convessi (vertici, spigoli, facce)
- Lemma di Farkas — Fondamento per capire perché funziona
L'Intuizione Fondamentale¶
La Visione Geometrica¶
Immagina la regione ammissibile come un poligono multidimensionale (un politopo) definito dai vincoli: - In 2D: un poligono - In 3D: un poliedro - In n-dimensioni: un politopo
Intuizione chiave #1: La soluzione ottimale si trova sempre in un vertice (angolo) di questo politopo.
Intuizione chiave #2: Due vertici sono collegati da uno spigolo se condividono tutti i vincoli tranne uno.
Intuizione chiave #3: Muoversi lungo uno spigolo cambia la funzione obiettivo linearmente. Se ci spostiamo verso un vertice migliore, continuiamo a andare. Se nessun vertice adiacente è migliore, siamo all'ottimo!
La Visione Algebrica¶
Un programma lineare in forma standard:
Dove: - \(x \in \mathbb{R}^n\) è la variabile decisionale - \(A\) è una matrice di vincoli \(m \times n\) (con \(m < n\)) - \(b \in \mathbb{R}^m\) è il termine noto - \(c \in \mathbb{R}^n\) è il coefficiente dell'obiettivo
Variabili di base: Scegli \(m\) colonne di \(A\) per formare una base \(B\). Imposta le rimanenti \(n-m\) variabili (non di base) a 0.
Soluzione di base ammissibile: Risolvi \(Bx_B = b\) per \(x_B\). Se \(x_B \geq 0\), questo è un vertice!
Il pivot: Scambia una variabile di base con una non di base → ti sposti verso un vertice adiacente.
Derivazione: Perché Funziona¶
Il Teorema Fondamentale della Programmazione Lineare¶
Teorema: Se esiste una soluzione ottimale, esiste una soluzione ottimale in un vertice della regione ammissibile.
Intuizione della dimostrazione: 1. La regione ammissibile è convessa (qualsiasi segmento tra punti ammissibili rimane ammissibile) 2. La funzione obiettivo è lineare (i suoi insiemi di livello sono iperpiani) 3. Muoversi in una direzione che migliora l'obiettivo finisce per colpire un confine 4. Una volta su un confine, puoi scivolare verso un vertice senza peggiorare l'obiettivo 5. Pertanto, almeno un vertice è ottimale
Ecco perché dobbiamo controllare solo i vertici!
La Condizione di Ottimalità¶
In un vertice definito dalla base \(B\), possiamo esprimere tutto in termini di variabili di base:
L'obiettivo diventa:
Il termine \((c_N^T - c_B^T B^{-1}N)\) è chiamato costo ridotto.
Ottimalità: Se tutti i costi ridotti sono \(\leq 0\) (per massimizzazione), nessuna variabile non di base può migliorare l'obiettivo quando viene portata in base. Siamo ottimali!
La Selezione del Pivot¶
Se qualche costo ridotto \(r_j > 0\), portare la variabile \(x_j\) in base migliora l'obiettivo. Ma quanto possiamo aumentarla?
Calcola il rapporto minimo: Per ogni variabile di base \(x_i\), trova quanto possiamo aumentare \(x_j\) prima che \(x_i\) diventi negativa.
La variabile di base che raggiunge zero per prima esce dalla base.
L'Algoritmo: Passo Dopo Passo¶
Passo 1: Inizializzazione¶
- Converti in forma standard (variabili di slack/surplus)
- Trova una soluzione di base ammissibile iniziale (spesso usando Fase I o metodo Big-M)
Passo 2: Verifica Ottimalità¶
- Calcola i costi ridotti: \(r_N = c_N^T - c_B^T B^{-1}N\)
- Se \(r_N \leq 0\) (mass), FERMATI — ottimale!
- Altrimenti, seleziona variabile entrante: costo ridotto più positivo
Passo 3: Verifica Illimitatezza¶
- Se la colonna entrante non ha elementi positivi in \(B^{-1}N\), il problema è illimitato
- Puoi aumentare la variabile all'infinito rimanendo ammissibile
Passo 4: Pivot¶
- Calcola i rapporti per trovare la variabile uscente
- Esegui operazioni di riga per pivotare: la colonna entrante diventa un vettore unitario
- Aggiorna la base
- Ritorna al Passo 2
Esempio Svolto¶
Problema: Massimizza \(z = 3x_1 + 2x_2\) soggetto a:
Passo 1: Aggiungi variabili di slack \(s_1, s_2\):
Tableau Iniziale:
Iterazione 1: - Coefficiente più negativo nella riga \(z\): \(x_1\) (coefficiente -3) - Rapporti: \(4/1 = 4\), \(2/1 = 2\) → minimo è 2 - Pivot sulla riga 2, colonna \(x_1\)
Dopo il Pivot:
Iterazione 2: - Il più negativo: \(x_2\) (coefficiente -5) - Rapporto: solo la riga 1 ha coefficiente positivo (2/2 = 1) - Pivot sulla riga 1, colonna \(x_2\)
Tableau Finale:
Soluzione: Tutti i costi ridotti nella riga \(z\) sono non negativi. Ottimale! - \(x_1 = 3\), \(x_2 = 1\), \(z = 11\)
Interpretazione geometrica: Ci siamo spostati dal vertice (0,0) → (2,0) → (3,1), migliorando l'obiettivo ad ogni passo.
Comprendere la Struttura¶
Perché i vertici? - La regione ammissibile è un politopo convesso - L'obiettivo lineare ha insiemi di livello (iperpiani) - Muoversi verso un obiettivo migliore colpisce un confine - I confini sono dove i vincoli sono serrati (vertici)
Perché gli spigoli? - I vertici adiacenti differiscono per esattamente un vincolo serrato - Muoversi lungo uno spigolo significa allentare un vincolo mentre se ne stringe un altro - Questo corrisponde a scambiare una variabile di base con una non di base
Perché il tableau? - Codifica il sistema \(Ax = b\) in una forma conveniente - Le operazioni di riga corrispondono all'eliminazione gaussiana - Ogni tableau rappresenta un vertice diverso - La riga \(z\) traccia i costi ridotti (condizioni di ottimalità)
Proprietà Chiave¶
- Terminazione finita: Visita al massimo \(\binom{n}{m}\) vertici (anche se di solito molti meno)
- Degenerazione: Può ciclicare in teoria, ma le regole anti-ciclo (regola di Bland) impediscono questo
- Caso peggiore esponenziale: Il cubo di Klee-Minty mostra che Simplesso può visitare \(2^n - 1\) vertici
- Efficienza pratica: Tipicamente \(O(m \log n)\) iterazioni per problemi reali
- Dualità: Simplesso risolve primale e duale simultaneamente (visibile nel tableau finale)
Problemi Comuni¶
| Problema | Causa | Soluzione |
|---|---|---|
| Degenerazione | Più vertici coincidono | Regola di Bland o perturbazione |
| Ciclaggio | Ciclo infinito in vertice degenere | Regola del più piccolo indice |
| Avvio inammissibile | Nessuna SBA iniziale ovvia | Fase I (problema ausiliario) |
| Illimitatezza | Nessun vincolo ferma il miglioramento | Controlla colonna entrante |
Il Collegamento con il Duale¶
Il Metodo del Simplesso risolve in realtà sia il problema primale che quello duale: - I coefficienti della riga \(z\) per le variabili di slack danno la soluzione duale - Quando il primale è ottimale, anche il duale lo è (dualità forte) - Questo è il fondamento dell'analisi di sensitività—quanto possono cambiare i parametri senza influenzare l'ottimalità?
Varianti Moderne¶
Simplesso Rivisto: Non memorizzare l'intero tableau; calcola \(B^{-1}\) esplicitamente. Più efficiente per problemi sparsi.
Simplesso Duale: Inizia con una soluzione ottimale ma inammissibile; ripristina l'ammissibilità. Ottimo per aggiungere nuovi vincoli.
Metodi Primale-Duale: Mantengono sia l'ammissibilità primale che duale; convergono all'ottimalità.
Metodi di Punti Interni: Camminano attraverso l'interno della regione ammissibile (algoritmo di Karmarkar). Tempo polinomiale, competitivo con Simplesso per problemi grandi.
Concetti Correlati¶
- Programmazione Lineare — Formulazione del problema
- Lemma di Farkas — Fondamento teorico
- Teoria della Dualità — Relazioni primale-duale
- Analisi di Sensitività — Analisi post-ottimalità
- Flussi su Rete — Simplesso specializzato per grafi
- Programmazione Intera — Quando le variabili devono essere intere (molto più difficile!)
Riferimenti¶
- Dantzig, G. B. (1947). "Maximization of a Linear Function of Variables Subject to Linear Inequalities." Activity Analysis of Production and Allocation.
- Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
- Klee, V., & Minty, G. J. (1972). "How Good is the Simplex Algorithm?" Inequalities III.
- Khachiyan, L. G. (1979). "A Polynomial Algorithm in Linear Programming." Soviet Mathematics Doklady.
- Karmarkar, N. (1984). "A New Polynomial-Time Algorithm for Linear Programming." Combinatorica.
Guida Visuale¶
Le seguenti figure illustrano l'interpretazione geometrica del Metodo del Simplesso:
1. Regione Ammissibile e Percorso di Ottimizzazione¶
La regione ammissibile (verde) con i vincoli come linee blu e rosse. Il percorso rosso mostra come il Simplesso si muove dal vertice (0,0) → (2,0) → (3,1), migliorando l'obiettivo a ogni passo. Le linee tratteggiate colorate rappresentano le curve di livello della funzione obiettivo z = 3x₁ + 2x₂.
2. Intuizione Geometrica 3D¶
In dimensioni superiori, la regione ammissibile diventa un poliedro. Il Metodo del Simplesso si muove lungo gli spigoli (linee blu) da vertice a vertice. Il percorso rosso mostra la traiettoria dall'origine al vertice ottimale, seguendo sempre gli spigoli del poliedro.
3. Evoluzione del Tableau¶
La rappresentazione algebrica: come cambia il tableau con ogni operazione di pivot. Le colonne verdi indicano le variabili entranti, le righe rosa mostrano la variabile uscente (riga di pivot). Ogni tableau corrisponde a un vertice nella vista geometrica.
4. Vista Geometrica vs Algebrica¶
Confronto affiancato che mostra come il movimento geometrico lungo gli spigoli corrisponda esattamente ai cambiamenti di base algebrici. Muoversi da un vertice a un vertice adiacente = scambiare una variabile base con una non-base.