Metodo del Simplesso: Guida Pratica ed Esercizio Risolto

Il Metodo del Simplesso è l’algoritmo algebrico per eccellenza della Ricerca Operativa, progettato per risolvere problemi di Programmazione Lineare esplorando i vertici del poliedro delle soluzioni ammissibili fino a individuare quello ottimo.

Per comprendere a fondo il meccanismo delle iterazioni, l’algebra di Gauss-Jordan e l’interpretazione economica dei calcoli, analizziamo la risoluzione completa di un classico problema di massimizzazione a due variabili e due vincoli di risorsa.

1. Il Modello Matematico di Partenza

Immaginiamo di dover pianificare la produzione di due beni, $x_1$ e $x_2$, per massimizzare il profitto totale $Z$. Il modello matematico si presenta in questa forma:

$$\max Z = x_1 + x_2$$

$$\text{s.t.} \quad x_1 + 2x_2 \le 16$$

$$\quad 2x_1 + x_2 \le 14$$

$$\quad x_1, x_2 \ge 0$$

I primi due vincoli strutturali rappresentano la disponibilità limitata di due risorse indipendenti (ad esempio, ore-macchina o materie prime), mentre l’ultima riga impone la condizione logica e fisica di non negatività delle variabili decisionali.

2. Il Passaggio alla “Forma Standard”

Le matrici e le tabelle di calcolo necessitano di equazioni esatte, non di disuguaglianze. Per trasformare il sistema geometrico in un formato algebrico risolvibile, effettuiamo due interventi di standardizzazione:

1. Gestione del Massimo: Per convenzione algoritmica, trasformiamo l’obiettivo di massimizzazione in minimizzazione sfruttando l’identità $\max (Z) = -\min (-Z)$. Portando le variabili a sinistra dell’uguaglianza, otteniamo l’equazione di base $-Z – x_1 – x_2 = 0$.
2. Introduzione delle Variabili di Scarto (Slack): Per convertire le disuguaglianze ($\le$) in uguaglianze ($=$), introduciamo una variabile di scarto per ciascun vincolo strutturale. Ognuna rappresenta la quota di risorsa non utilizzata in quella specifica equazione:
   • Nel primo vincolo inseriamo $x_3$: $x_1 + 2x_2 + x_3 = 16$
   • Nel secondo vincolo inseriamo $x_4$: $2x_1 + x_2 + x_4 = 14$

Il modello in Forma Standard risulta quindi:

$$\min -Z = -x_1 – x_2$$

$$\text{s.t.} \quad 1x_1 + 2x_2 + 1x_3 + 0x_4 = 16$$

$$\quad 2x_1 + 1x_2 + 0x_3 + 1x_4 = 14$$

$$\quad x_1, x_2, x_3, x_4 \ge 0$$

3. Il Tableau Iniziale (Iterazione 0)

Organizziamo i coefficienti del sistema all’interno della griglia di calcolo. All’avvio dell’algoritmo, ci troviamo geometricamente nell’origine degli assi: non produciamo nulla ($x_1 = 0, x_2 = 0$, variabili fuori base), mentre le risorse sono del tutto inutilizzate ($x_3 = 16, x_4 = 14$, variabili in base).

Base	x1​	x2​	x3​	x4​	Termine Noto (b)
$-Z$	-1	-1	0	0	0
$x_3$	1	2	1	0	16
$x_4$	2	1	0	1	14

Test di Ottimalità e Scelta del Pivot

La prima riga (quella della funzione obiettivo $-Z$) presenta coefficienti negativi: questo indica che aumentare la produzione di $x_1$ o $x_2$ farà crescere il profitto. Scegliamo di far entrare in base $x_1$ (colonna pivot).

Per determinare quale risorsa si esaurirà per prima, eseguiamo il test del quoziente minimo dividendo i termini noti per i coefficienti positivi della colonna di $x_1$:

• Riga $x_3$: $\frac{16}{1} = 16$
• Riga $x_4$: $\frac{14}{2} = \mathbf{7}$ (minimo)

Il valore minore ($7$) indica che la seconda risorsa costituisce il “collo di bottiglia” produttivo. La variabile $x_4$ esce di base per far posto a $x_1$. L’elemento pivot è il numero $2$, situato all’incrocio tra la riga di $x_4$ e la colonna di $x_1$.

4. Iterazione 1: L’Eliminazione di Gauss-Jordan

Il nostro obiettivo algebrico ora è trasformare la colonna di $x_1$ in un vettore della matrice identità, ossia far diventare l’elemento pivot pari a $1$ e azzerare tutti gli altri valori lungo quella colonna.

1. Creazione della nuova riga pivotale: Dividiamo ogni elemento della riga di uscente ($x_4$) per il pivot $2$. La nuova equazione di riferimento diventa:$$1x_1 + \frac{1}{2}x_2 + 0x_3 + \frac{1}{2}x_4 = 7$$
2. Aggiornamento della riga $x_3$: Sottraiamo dalla vecchia riga di $x_3$ la nuova riga pivotale:$$(1 – 1)x_1 + \left(2 – \frac{1}{2}\right)x_2 + (1 – 0)x_3 + \left(0 – \frac{1}{2}\right)x_4 = 16 – 7 \implies 0x_1 + \frac{3}{2}x_2 + 1x_3 – \frac{1}{2}x_4 = 9$$
3. Aggiornamento della riga $-Z$: Sommiamo la nuova riga pivotale alla vecchia riga di $-Z$:$$(-1 + 1)x_1 + \left(-1 + \frac{1}{2}\right)x_2 + 0x_3 + \left(0 + \frac{1}{2}\right)x_4 = 0 + 7 \implies 0x_1 – \frac{1}{2}x_2 + 0x_3 + \frac{1}{2}x_4 = 7$$

Ottiniamo così il Tableau 1:

Base	x1​	x2​	x3​	x4​	Termine Noto (b)
$-Z$	0	-1/2	0	1/2	7
$x_3$	0	3/2	1	-1/2	9
$x_1$	1	1/2	0	1/2	7

Geometricamente ci siamo spostati dal vertice $(0,0)$ al vertice $(7,0)$. Producendo 7 unità di $x_1$, il profitto è salito a $7$, mentre rimangono inutilizzate 9 unità della prima risorsa ($x_3$).

5. Iterazione 2: Raggiungimento dell’Ottimo

Osservando la riga di $-Z$, notiamo ancora la presenza di un costo ridotto negativo: $-\frac{1}{2}$ in corrispondenza di $x_2$. Il processo può essere ulteriormente ottimizzato.

1. Variabile entrante: $x_2$
2. Test del quoziente per la variabile uscente:
   • Riga $x_3$: $\frac{9}{3/2} = 9 \cdot \frac{2}{3} = \mathbf{6}$ (minimo)
   • Riga $x_1$: $\frac{7}{1/2} = 7 \cdot 2 = 14$

La variabile di scarto $x_3$ esce di base. Il nuovo elemento pivot è $\frac{3}{2}$.

Riapplichiamo le operazioni di Gauss-Jordan:

• Nuova riga $x_2$: Moltiplichiamo la riga uscente per il reciproco del pivot ($\frac{2}{3}$), ottenendo: $0x_1 + 1x_2 + \frac{2}{3}x_3 – \frac{1}{3}x_4 = 6$.
• Pulizia della riga $x_1$: Sottraiamo metà della nuova riga $x_2$, aggiornando il termine noto a $7 – \frac{1}{2}(6) = 4$.
• Pulizia della riga $-Z$: Sommiamo metà della nuova riga $x_2$, aggiornando il profitto a $7 + \frac{1}{2}(6) = 10$.

Il Tableau 2 finale presenta questa configurazione:

Base	x1​	x2​	x3​	x4​	Termine Noto (b)
$-Z$	0	0	1/3	1/3	10
$x_2$	0	1	2/3	-1/3	6
$x_1$	1	0	-1/3	2/3	4

6. Interpretazione dei Risultati

La riga della funzione obiettivo ($-Z$) non presenta più alcun coefficiente negativo ($0, 0, \frac{1}{3}, \frac{1}{3}$). Questo segnale algebrico garantisce che l’algoritmo ha terminato la sua corsa: abbiamo raggiunto il vertice ottimo.

Leggendo i valori nella colonna dei termini noti in corrispondenza delle variabili di base, la strategia produttiva perfetta risulta:

• Produzione del bene $x_1$: 4 unità
• Produzione del bene $x_2$: 6 unità
• Variabili di scarto $x_3$ e $x_4$: 0 (entrambe le risorse sono state interamente saturate senza sprechi)

Il valore massimo raggiunto dalla funzione obiettivo è pari a $10$. L’itinerario geometrico compiuto dall’algoritmo ha esplorato in successione tre vertici dell’area di ammissibilità: partendo dall’origine $(0,0 \rightarrow Z=0)$, ha prima saturato il vincolo inferiore $(7,0 \rightarrow Z=7)$, per poi trovare il punto di equilibrio perfetto all’intersezione dei due vincoli strutturali $(4,6 \rightarrow Z=10)$.

Padronizzare l’Algebra per la Ricerca Operativa

Come abbiamo visto nei vari passaggi dell’algoritmo, il vero motore del metodo del simplesso è l’eliminazione di Gauss-Jordan. Saper manipolare le righe di una matrice, individuare gli elementi pivot e azzerare i coefficienti con sicurezza è la competenza fondamentale per risolvere qualsiasi problema di ottimizzazione ed evitare banali errori di calcolo.

Se vuoi consolidare le tue basi algebriche e imparare a padroneggiare il metodo di Gauss e la riduzione delle matrici, esplora il Corso di Algebra Lineare: un percorso strutturato con teoria chiara, esempi applicati e tanti esercizi pratici svolti passo dopo passo per affrontare le matrici senza stress.

7. Risolvere il Problema con il Risolutore di Excel

Dopo aver compreso il meccanismo matematico dietro i passaggi algebrici di Gauss-Jordan, possiamo verificare la correttezza del nostro risultato e velocizzare i calcoli utilizzando uno strumento integrato nei fogli di calcolo: il Risolutore di Excel (impostato sull’algoritmo Simplex LP).

Vediamo come strutturare il foglio di lavoro utilizzando esattamente i dati del nostro primo esempio.

Step 1: Organizzazione del Foglio di Calcolo

Per impostare correttamente il modello, dobbiamo separare i coefficienti statici dalle celle dinamiche che Excel andrà a modificare:

1. La Matrice dei Vincoli ($A$): Nelle celle da E16 a F17 inseriamo i coefficienti tecnici delle risorse:
   • E16:F16 $\rightarrow$ 1 e 2 (primo vincolo)
   • E17:F17 $\rightarrow$ 2 e 1 (secondo vincolo)
2. Il Vettore dei Costi ($C$): Nelle celle E20 e F20 inseriamo i coefficienti della funzione obiettivo (in questo caso 1 e 1).
3. Le Variabili Decisionali ($X$): Evidenziamo in giallo le celle H16 e H17. Queste rappresentano le nostre incognite $x_1$ e $x_2$. Inizialmente possono essere lasciate vuote o contenere valori di prova (nell’esempio in figura mostrano temporaneamente 3 e 4).
4. I Termini Noti ($B$): Nelle celle G26 e G27 inseriamo i limiti massimi delle nostre risorse, ovvero 16 e 14.

Step 2: Le Formule da Inserire

Prima di avviare il Risolutore, dobbiamo collegare le celle tramite le formule matematiche del modello:

• Calcolo dei Vincoli ($AX$): Nelle celle E26 e E27 dobbiamo calcolare il consumo effettivo delle risorse in base alle quantità prodotte.
  • In E26 inseriamo la formula: =MATR.SOMMA.PRODOTTO(E16:F16; $H$16:$H$17)
  • In E27 inseriamo la formula: =MATR.SOMMA.PRODOTTO(E17:F17; $H$16:$H$17)
• Funzione Obiettivo ($\max Z$): Nella cella E22 calcoliamo il profitto totale moltiplicando le variabili decisionali per i rispettivi margini:
  • In E22 inseriamo la formula: =MATR.SOMMA.PRODOTTO(E20:F20; H16:H17)

Step 3: Configurazione dei Parametri del Risolutore

Apriamo il menu Dati e clicchiamo su Risolutore (se non è visibile, va attivato dalle Opzioni di Excel > Componenti aggiuntivi). Impostiamo i parametri esattamente come segue:

• Imposta obiettivo: Selezioniamo la cella del profitto, ovvero $E$22.
• A: Selezioniamo l’opzione Max (Massimizzazione).
• Modificando le celle variabili: Selezioniamo il blocco giallo delle nostre incognite, ovvero $H$16:$H$17.
• Soggette ai vincoli: Clicchiamo su Aggiungi e impostiamo la disuguaglianza tra il consumo effettivo e i termini noti: $E$26:$E$27 <= $G$26:$G$27.
• Vincoli di non negatività: Assicuriamoci che la casella “Rendi non negative le variabili senza vincoli” sia spuntata. Questo passaggio equivale matematicamente a imporre la condizione $x_1, x_2 \ge 0$.
• Metodo di risoluzione: Nel menu a tendina inferiore, selezioniamo tassativamente Simplex LP. Questa opzione indica a Excel di non usare algoritmi di approssimazione non lineare, ma di applicare l’esatto metodo geometrico e matriciale del Simplesso che abbiamo studiato teoricamente.

Risultato Finale

Cliccando sul pulsante Risolvi, Excel eseguirà le iterazioni in poche frazioni di secondo. Le celle gialle $H$16 e $H$17 si aggiorneranno automaticamente mostrando i valori ottimi 4 e 6, mentre la cella obiettivo $E$22 mostrerà il profitto massimo di 10, confermando al 100% l’esattezza dei nostri calcoli manuali!