La programmazione lineare non è solo matematica astratta. È il motore dietro la logistica, le catene di fornitura e la gestione delle risorse. Al centro c’è il metodo del simplesso. Questa tecnica standard trova il miglior risultato possibile in un sistema definito da vincoli e da una funzione obiettivo.
Pensatela in questo modo. Hai un obiettivo. Forse sta massimizzando il profitto o minimizzando i costi. Anche tu hai dei limiti. Ore macchina. Materie prime. Lavoro. Il metodo del simplesso supera questi limiti per trovare il picco. Non indovina. Calcola.
Perché abbiamo bisogno di un approccio sistematico
Potresti pensare di poter semplicemente rappresentare graficamente due variabili e vedere dove si intersecano. Funziona per problemi semplici. Una fabbrica che produce due prodotti. Tu disegni delle linee. Trovi l’angolo in cui il profitto raggiunge il picco. È visivo. È intuitivo.
Ma la realtà è raramente bidimensionale. I problemi reali coinvolgono centinaia di equazioni e migliaia di variabili. Il numero di possibili soluzioni diventa astronomico. Disegnare un grafico per mille variabili è impossibile. Avresti bisogno di dimensioni che non puoi percepire.
George Dantzig risolse questo problema nel 1947. Lavorava come consulente matematico per l’aeronautica americana. I militari avevano enormi problemi logistici. Avevano bisogno di ottimizzare le rotte di approvvigionamento e l’allocazione delle risorse. Dantzig ha ideato il metodo simplex per eliminare il rumore.
Il metodo limita il numero di punti estremi che devono essere esaminati. Trasforma un compito impossibile in gestibile. Rimane l’algoritmo standard sui computer oggi. Uno degli strumenti più utili mai inventati.
Come funziona il metodo del simplesso passo dopo passo
Il processo è sistematico. Si passa da una possibilità all’altra. Ecco come si svolge nella pratica.
Innanzitutto, presuppone che tu abbia un punto di partenza. Un punto estremo. Se non ne hai uno, una variante chiamata Fase I trova un punto di partenza fattibile o determina che non esiste alcuna soluzione.
Successivamente, il metodo verifica quel punto. È ottimale? La specifica algebrica del problema esegue questo controllo. Se il test fallisce, l’algoritmo si sposta su un punto estremo adiacente. Si muove lungo un bordo. Sceglie la direzione in cui la funzione obiettivo aumenta al ritmo più rapido.
A volte la funzione aumenta senza limiti. La procedura si interrompe e identifica il bordo in cui il valore va all’infinito positivo. Hai trovato una soluzione illimitata.
Se ciò non accade, atterri su un nuovo punto estremo. Questo punto ha un valore almeno altrettanto alto del precedente. La sequenza si ripete. Continua finché non trova un punto ottimale o identifica l’illimitatezza.
In teoria i passi potrebbero crescere esponenzialmente con il numero dei punti estremi. In pratica, la convergenza è rapida. Di solito è necessario solo un piccolo multiplo del numero di punti estremi.
Un esempio concreto: massimizzare il profitto di fabbrica
Consideriamo un caso tangibile. Una fabbrica produce due prodotti. Li chiamiamo x1 e x2. Il profitto del secondo tipo è doppio rispetto al primo. Il profitto totale è rappresentato dall’equazione:
x1 + 2×2
Questa è la tua funzione obiettivo. Vuoi massimizzarlo.
Naturalmente, vorresti fare solo x2. Porta più soldi per unità. Ma esistono dei vincoli. Non puoi semplicemente produrre all’infinito.
Ecco i limiti del mondo reale:
- La materia prima per x2 limita la produzione a cinque unità per lotto (x2 ≤ 5).
- La materia prima per x1 limita la produzione a otto unità per lotto (x1 ≤ 8).
- Il tempo macchina consente un massimo di dieci unità totali (x1 + x2 ≤ 10).
- Non è possibile produrre importi negativi (x1 ≥ 0 e x2 ≥ 0).
Il metodo del simplesso trova i valori di x1 e x2 che massimizzano il profitto entro questi limiti. Qualsiasi soluzione è una coppia di numeri (x1, x2). Ad esempio, produrre tre di x1 e sei di x2 è un punto valido (3, 6).
Quando tracciati su un grafico, questi vincoli formano una regione poligonale. Questa è la serie di soluzioni fattibili. I punti esterni a questa regione violano uno o più vincoli.
Per vedere come il metodo del simplesso identifica il vertice ottimo, consideriamo la funzione obiettivo x1 + 2×2 = k. Se imposti k su 4, ottieni una linea sul grafico. Aumentando k si ottengono linee parallele. Il valore più alto di k che tocca ancora la regione ammissibile è il massimo profitto possibile.
In questo esempio, la linea per k = 15 tocca la regione nel punto (5, 5). Se k è maggiore, la retta cade al di fuori dell’insieme ammissibile. La soluzione ottimale è produrre quantità uguali di ciascuna merce.
Perché i vertici sono importanti nella programmazione lineare
Il risultato non è una coincidenza. Nei problemi lineari la soluzione ottima si trova sempre in un vertice. Un punto estremo.
Questa è una proprietà fondamentale della programmazione lineare. La funzione è lineare. I vincoli sono lineari. La forma è un poligono convesso (o poliedro nelle dimensioni superiori). Il picco di una funzione lineare su un insieme convesso è sempre in un angolo.
Non è necessario controllare ogni punto nella regione fattibile. Hai solo bisogno di controllare i vertici. Il metodo del simplesso fa esattamente questo. Salta da un vertice all’altro. Si arrampica sulla superficie della regione fattibile. Si ferma quando non può andare più in alto.
A volte l’ottimale non è unico. Un intero bordo potrebbe produrre lo stesso valore massimo. Ma il metodo del simplesso troverà comunque uno di quei punti ottimali. Ti dà una risposta concreta. Dati utilizzabili.
Sia per gli studenti che per i professionisti, comprendere questa meccanica è fondamentale. Non si tratta solo di risolvere equazioni. Si tratta di sapere come navigare in sistemi complessi con risorse limitate. Il metodo del simplesso fornisce il percorso.
Il metodo del simplesso non si limita a indovinare le risposte. Cammina lungo i bordi di una regione ammissibile, controllando i vertici finché non trova quello migliore. Si inizia ripulendo i conti. Prendi quelle disuguaglianze lineari disordinate e trasformale in uguaglianze pulite. Puoi farlo aggiungendo “variabili slack”.
Pensa al margine di flessibilità come alla capacità residua. Se hai un vincolo come $x_1 \le 8$, aggiungi una variabile $x_3$ tale che $x_1 + x_3 = 8$. E ricorda, $x_3$ deve essere maggiore o uguale a zero. Lo fai per ogni vincolo.
- $x_1 + x_3 = 8$ (con $x_3 \ge 0$)
- $x_2 + x_4 = 5$ (con $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10$ (con $x_5 \ge 0$)
È necessaria anche una variabile per la funzione obiettivo stessa. Chiamiamolo $x_0$. Se il tuo obiettivo è massimizzare $x_0 = x_1 + 2x_2$, riscrivilo come $x_1 + 2x_2 – x_0 = 0$.
Ora il problema è più semplice. Trova valori non negativi da $x_1$ a $x_5$. Rendi $x_0$ il più grande possibile.
Partendo dall’Origine
Da dove cominciare? Il punto più semplice è l’origine. Imposta tutte le variabili decisionali a zero. $x_1 = 0$. $x_2 = 0$.
Questa è una soluzione valida. È un punto estremo. In effetti, è l’angolo di partenza. Anche il valore obiettivo $x_0$ è zero. Non eccezionale, ma è una mossa legale.
Possiamo fare di meglio? SÌ. Se aumenti una delle variabili da zero mantenendo l’altra a zero, $x_0$ aumenta. La domanda è quale variabile ti dà il miglior rapporto qualità-prezzo.
Osserva l’equazione oggettiva: $x_1 + 2x_2 – x_0 = 0$. Riorganizzando per $x_0$, ottieni $x_0 = x_1 + 2x_2$.
Aumentando $x_1$ si aggiunge 1 al totale. Aumentando $x_2$ si aggiunge 2. $x_2$ è il chiaro vincitore. Produce il maggiore aumento di $x_0$ per variazione unitaria. Quindi, scegli $x_2$ e spingilo verso l’alto.
Raggiungere il primo vincolo
Non puoi aumentare $x_2$ per sempre. Le variabili devono rimanere non negative. Se spingi $x_2$ oltre il 5, qualcosa si rompe. Nello specifico, guarda il secondo vincolo: $x_2 + x_4 = 5$.
Se $x_2 = 6$, allora $x_4$ diventa -1. Non è consentito. Il requisito di non negatività agisce come un freno. Il limite è 5.
Quindi imposti $x_2 = 5$. Qual è la soluzione adesso?
$x_2 = 5$
* $x_1 = 0$ (ancora zero)
* $x_4 = 0$ (questa variabile ha raggiunto il limite, quindi ora è zero)
* $x_3 = 8$ (poiché $0 + 8 = 8$)
$
