Quando in un problema di Programmazione Lineare si vuole massimizzare un profitto con vincoli di risorse, il Metodo del Simplesso individua il valore ottimo esplorando i vertici del poliedro ammissibile. Qui viene ricostruita la procedura completa su un caso a due variabili, includendo standardizzazione, tableau, pivot e chiusura con interpretazione dei risultati. Il punto chiave è vedere come Gauss-Jordan trasforma le righe fino a fermarsi al vertice ottimo.
Cos’è il Metodo del Simplesso e perché funziona
Il Simplesso è l’algoritmo algebrico usato nella Ricerca Operativa per risolvere problemi di Programmazione Lineare. L’idea operativa è geometrica: partendo da una soluzione ammissibile, l’algoritmo muove la ricerca tra vertici del poliedro delle soluzioni fino a trovare quello che ottimizza l’obiettivo.
- Vertici ammissibili: i candidati migliori ricadono in punti “speciali” del dominio.
- Pivot selection: si decide la variabile che entra e quella che esce usando test mirati.
- Gauss-Jordan: si azzera la colonna del pivot per aggiornare il tableau.
Esempio risolto: massimizzazione con due vincoli
Modello iniziale e interpretazione dei vincoli
Si considerano due beni, x1 e x2, con profitto totale Z da massimizzare. I vincoli rappresentano la disponibilità limitata di due risorse e la condizione di non negatività delle variabili decisionali.
- Obiettivo: max Z = x1 + x2
- Vincoli: x1 + 2x2 ≤ 16; 2x1 + x2 ≤ 14
- Condizione: x1, x2 ≥ 0
Forma standard: trasformazione e variabili di scarto
Per applicare il calcolo tabellare, le disuguaglianze devono diventare uguaglianze. Per gestione del massimo si passa a minimizzazione cambiando segno, poi si introducono le variabili di scarto per ciascun vincolo.
- Massimo → minimizzazione con l’identità: max(Z) = -min(-Z).
- Slack: x3 per il primo vincolo e x4 per il secondo.
In forma standard si ottiene quindi un problema con incognite x1, x2, x3, x4 tutte vincolate a ≥ 0.
Tableau iniziale, test di ottimalità e scelta del pivot (Iterazione 0)
Nel tableau iniziale la base contiene le variabili di scarto, mentre x1 e x2 non sono ancora “attive” nella soluzione. Il test di ottimalità osserva la riga dell’obiettivo (quella di -Z): la presenza di coefficienti negativi indica che una variazione può migliorare l’obiettivo.
- Variabile entrante: x1 (colonna pivot).
- Test del quoziente minimo: 16/1 = 16 e 14/2 = 7 → esce x4.
- Elemento pivot: 2 (incrocio tra riga di x4 e colonna di x1).
Con la prima applicazione di Gauss-Jordan, la ricerca si sposta dal vertice di partenza e si aggiorna il valore di Z.
Iterazione 1 e costruzione del tableau con Gauss-Jordan
La colonna del pivot viene resa una colonna di matrice identità: l’operazione principale è dividere la riga uscente per il valore del pivot, poi azzerare gli altri coefficienti nella stessa colonna sottraendo o sommando righe opportunamente.
- Riga pivotale da x4 divisa per 2.
- Aggiornamento delle righe di x3 e di -Z tramite combinazioni lineari.
Il risultato geometrico descritto è lo spostamento fino a un nuovo vertice: con 7 unità di x1 il profitto cresce a 7, mentre la prima risorsa residua risulta pari a 9.
Iterazione 2: chiusura dell’algoritmo all’ottimo
Il tableau aggiornato viene verificato ancora sul test di ottimalità. Rimane un coefficiente negativo nella riga di -Z, associato alla possibilità di migliorare tramite x2.
- Variabile entrante: x2.
- Quoziente minimo: 9/(3/2) = 6 e 7/(1/2) = 14 → esce x3.
- Elemento pivot: 3/2.
Dopo l’ultima trasformazione di Gauss-Jordan, la riga di -Z non presenta più coefficienti negativi: il processo termina perché l’ottimo è stato raggiunto.
Interpretazione dei risultati finali
La lettura della soluzione passa dai valori nelle colonne dei termini noti associati alle variabili di base. Il tableau finale indica una strategia produttiva senza sprechi, con scarti nulli: x1 = 4, x2 = 6 e x3 = x4 = 0. Il valore massimo dell’obiettivo risulta Z = 10.
- Vertici esplorati: (0,0 → Z=0), (7,0 → Z=7), (4,6 → Z=10).
- Condizione di stop: assenza di coefficienti negativi nella riga di -Z.
Tabella di Sintesi
| Elemento Chiave | Dettaglio / Impatto |
|---|---|
| Obiettivo | Massimizzare Z = x1 + x2, poi gestito tramite trasformazione in minimizzazione |
| Vincoli | x1 + 2x2 ≤ 16 e 2x1 + x2 ≤ 14 con x1, x2 ≥ 0 |
| Slack (variabili di scarto) | x3 = 16 − (x1 + 2x2) e x4 = 14 − (2x1 + x2), per passare a uguaglianze |
| Iterazione 0 | Entra x1, esce x4; pivot = 2; profitto passa a 7 al nuovo vertice |
| Iterazione 1 | Aggiornamento tableau con Gauss-Jordan e lettura vertice (7,0) |
| Iterazione 2 | Entra x2, esce x3; pivot = 3/2; stop per assenza di coefficienti negativi in -Z |
| Soluzione ottima | x1 = 4, x2 = 6, x3 = 0, x4 = 0; Z = 10 |
Impatto sulla scuola: cosa cambia nella comprensione degli studenti
Questo percorso rende più operativo il Metodo del Simplesso: gli studenti non memorizzano solo formule, ma apprendono il collegamento tra geometria (vertici), algebra (pivot e Gauss-Jordan) e significato economico dei termini di scarto. Il tableau diventa uno strumento di lettura, non una sequenza meccanica.
La procedura in due passaggi di standardizzazione (massimo → minimo e introduzione di variabili di scarto) chiarisce la logica con cui la teoria delle disuguaglianze viene ricondotta a un calcolo tabellare. In continuità, l’uso del test di ottimalità spiega perché e quando l’algoritmo si ferma, evitando l’errore didattico più comune: applicare iterazioni “a caso”.
Infine, la parte sul Risolutore di Excel consente un controllo formativo: gli studenti possono verificare il risultato finale (x1 = 4, x2 = 6, Z = 10) e riflettere sulle corrispondenze tra celle e variabili, rafforzando l’abilità di tradurre un modello matematico in un modello eseguibile.
Verifica con il Risolutore di Excel (Simplex LP)
Una volta compresi i passaggi algebrici, il Risolutore permette di replicare i calcoli usando il metodo Simplex LP. L’impostazione richiede di distinguere coefficienti statici, variabili decidionali e termini noti dei vincoli.
- Inserimento coefficienti dei vincoli (matrice A) nelle celle dedicate.
- Definizione dei coefficienti dell’obiettivo (vettore dei costi C).
- Assegnazione delle celle alle incognite (variabili x1 e x2).
- Formule per calcolare consumo risorse (AX) e profitto (Z).
Nel menu di configurazione si imposta l’obiettivo come Max, si specificano i vincoli con le disuguaglianze e si seleziona Simplex LP. Il risultato atteso, secondo l’impostazione dell’esempio, mostra x1 = 4, x2 = 6 e Z = 10.