Saper costruire un modello di Programmazione Lineare è solo il primo tempo della sfida: una volta formalizzati incognite, vincoli e funzione obiettivo, è necessario accendere il motore algebrico in grado di elaborare il sistema e guidare l’azienda verso la scelta ottimale. Questo motore è il Metodo del Simplesso, l’algoritmo sviluppato dal matematico George Dantzig nel 1947 che ha rivoluzionato il mondo della Ricerca Operativa e dell’analisi industriale.
Comprendere il funzionamento del Simplesso significa esplorare come l’algebra lineare si fonde con la geometria per navigare in modo intelligente all’interno di uno spazio di decisioni altrimenti impossibile da calcolare a forza bruta.
INDICE
1. La Teoria del Simplesso: Dallo Schema di Assegnazione all’Algoritmo
Per comprendere come lavora l’algoritmo, dobbiamo prima formalizzare il problema utilizzando il linguaggio universale dell’algebra matriciale. Ogni problema di programmazione lineare nasce infatti dall’esigenza di allocare risorse limitate per la realizzazione di diverse attività o prodotti.
Lo Schema Generale di Assegnazione e la Scrittura Simbolica
Immaginiamo un’azienda che produce $n$ differenti prodotti utilizzando varie combinazioni di $m$ risorse (ad esempio materie prime, ore lavorative o macchinari). Possiamo riassumere tutte le informazioni tecniche ed economiche all’interno di una matrice chiara e strutturata, nota come schema generale di assegnazione:
| Risorse / Prodotti | Prodotto 1 (x1) | Prodotto 2 (x2) | … | Prodotto n (xn) | Disponibilità Massima (bi) |
| Risorsa 1 | $a_{11}$ | $a_{12}$ | … | $a_{1n}$ | $b_1$ |
| Risorsa 2 | $a_{21}$ | $a_{22}$ | … | $a_{2n}$ | $b_2$ |
| … | … | … | … | … | … |
| Risorsa $m$ | $a_{m1}$ | $a_{m2}$ | … | $a_{mn}$ | $b_m$ |
| Guadagno / Costo Unitario | $c_1$ | $c_2$ | … | $c_n$ | — |
Dal punto di vista della notazione matematica, ogni elemento di questa tabella svolge un ruolo algebrico preciso:
- L’elemento $a_{ij}$ rappresenta il coefficiente tecnico, ossia la quantità della risorsa $i$ necessaria per produrre una singola unità del prodotto $j$. L’intera colonna $j$ costituisce lo schema di produzione del prodotto $j$.
- Il vettore colonna dei termini noti $\mathbf{b} = \bar{b}$ indica la disponibilità totale delle risorse nel periodo considerato:$$\mathbf{b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix}$$
- Il vettore riga $\mathbf{c} = \bar{c} = \begin{bmatrix} c_1 & c_2 & \dots & c_n \end{bmatrix}$ rappresenta i coefficienti della funzione obiettivo (ad esempio il guadagno o il costo unitario associato a ciascun prodotto).
Se poniamo come scopo l’ottimizzazione del risultato complessivo (indicando con $Z$ la variabile dipendente e con $x_j$ le quantità di produzione da determinare), la nostra Funzione Obiettivo (FO) si esprime come somma algebrica:
$$\max Z = \sum_{j=1}^{n} c_j \cdot x_j \quad \text{oppure per la minimizzazione:} \quad \min Z = \sum_{j=1}^{n} c_j \cdot x_j$$
In termini matriciali, indicando con $\bar{x}$ il vettore colonna delle quantità da produrre, la funzione obiettivo si compatta nella scrittura:
$$\max Z = \bar{c} \cdot \bar{x} \quad \text{oppure} \quad \min Z = \bar{c} \cdot \bar{x}$$
Questa funzione è soggetta al sistema dei vincoli tecnici e alle inderogabili condizioni di non negatività ($\bar{x} \ge 0$), che in forma matriciale si riassumono come:
$$A \cdot \bar{x} \le \bar{b} \quad (\text{oppure } \ge \bar{b} \text{ nel caso di vincoli di fabbisogno})$$
La Logica del Percorso Intelligente
La geometria e l’algebra ci insegnano che l’insieme di tutti i vettori $\bar{x}$ che soddisfano il sistema di vincoli forma un poliedro convesso (la regione delle soluzioni ammissibili) e che la soluzione ottima risiede tassativamente in uno dei suoi vertici (Teorema del Vertice).
Quando trasformiamo le disequazioni del sistema in equazioni introducendo le variabili di scarto (o di surplus), otteniamo un sistema con $m$ equazioni e $n+m$ incognite totali. Ogni vertice corrisponde a una soluzione di base ammissibile, ottenuta ponendo uguali a zero $n$ incognite (variabili fuori base) e risolvendo il sistema per le rimanenti $m$ variabili (variabili in base).
In un problema industriale reale, tuttavia, controllare il costo o il profitto su ciascun vertice calcolando tutte le combinazioni possibili ($C_{n+m, m}$) richiederebbe tempi irrealizzabili persino per i supercomputer. Il Metodo del Simplesso aggira questo scoglio combinatorio adottando una strategia elegante ed efficiente:
- Partenza: Individua una prima soluzione di base ammissibile di partenza (un primo vertice del poliedro).
- Esplorazione mirata: Controlla gli spigoli che partono dal vertice attuale per verificare se muoversi lungo una di quelle direzioni porta a un miglioramento della funzione obiettivo $Z$.
- Salto di vertice: Sposta la soluzione sul vertice adiacente che promette il miglioramento più rapido, scartando a priori tutte le direzioni peggiorative o neutre.
- Arresto: Ripete il ciclo fino a raggiungere un vertice dal quale nessuna direzione adiacente consente un ulteriore miglioramento. In quel momento, l’algoritmo ha la certezza matematica di aver raggiunto l’ottimo globale.
La Meccanica Algebrica del Simplesso
Il ciclo di calcolo si muove da una base all’altra attraverso tre passaggi meccanici che costituiscono una singola iterazione:
- Test di Ottimalità (Chi entra in base?): Si analizza la riga della funzione obiettivo. Se esiste una variabile fuori base con un coefficiente favorevole (atto a migliorare il valore di $Z$), quella variabile viene scelta per entrare in base, assorbendo risorse per aumentare la produzione.
- Test del Quoziente Minimo (Chi esce di base?): Per capire fin dove possiamo spingere la nuova produzione prima di violare un vincolo, si dividono i termini noti $\mathbf{b}$ per i coefficienti positivi della colonna della variabile entrante. La risorsa che registra il rapporto minore rappresenta il nostro “collo di bottiglia”: la variabile associata a quella riga si azzera ed esce di base.
- Eliminazione di Gauss-Jordan (Il Pivot): L’incrocio tra la colonna della variabile entrante e la riga della variabile uscente definisce l’elemento pivot. Utilizzando le operazioni di riduzione algebrica di Gauss-Jordan, si trasforma il pivot in $1$ e si azzerano tutti gli altri numeri di quella colonna, aggiornando la griglia (Tableau) al nuovo vertice adiacente.
2. Dalla Teoria alla Pratica: Il Caso della Minimizzazione Costi
Per vedere il Simplesso in azione, riprendiamo l’impostazione dell’esempio industriale sviluppato precedentemente e portiamolo fino al calcolo della soluzione finale.
Il Modello Matematico di Partenza
Un reparto aziendale deve produrre due beni, A ($x_1$) e B ($x_2$), combinando manodopera e macchinari.
- Il costo unitario di lavorazione è di $85\text{€}$ per il bene A e $106\text{€}$ per il bene B.
- I vincoli tecnici di reparto impongono un tetto massimo di 150 ore lavoro e 100 ore macchina disponibili ogni giorno.
- Per onorare i contratti con i clienti, l’azienda ha l’obbligo di fabbricare almeno 14 unità totali al giorno.
Il modello di ottimizzazione si presenta nella forma standard di minimizzazione:
$$\min Z = 85x_1 + 106x_2$$
$$\text{s.t.} \quad 3x_1 + 6x_2 \le 150 \quad \text{(ore lavoro disponibili)}$$
$$\quad 5x_1 + 2x_2 \le 100 \quad \text{(ore macchina disponibili)}\\ \quad x_1 + x_2 \ge 14 \quad \text{(domanda contrattuale minima)}\\ \quad x_1 \ge 0, \quad x_2 \ge 0$$
Passo 1: Standardizzazione e Individuazione della Base Iniziale
Per prima cosa, per applicare le matrici del Simplesso convertiamo la minimizzazione in massimizzazione del segno opposto ($\max(-Z) = -85x_1 – 106x_2$) e pareggiamo i vincoli inserendo due variabili di scarto ($s_1, s_2$) nei primi due vincoli e una variabile di surplus ($e_3$) nel terzo vincolo contrattuale:
- $3x_1 + 6x_2 + s_1 = 150$
- $5x_1 + 2x_2 + s_2 = 100$
- $x_1 + x_2 – e_3 = 14 \implies x_1 + x_2 = 14 + e_3$
A differenza dei problemi dove si parte da zero produzione, nei problemi di minimizzazione con vincoli contrattuali ($\ge$) l’origine degli assi $(0,0)$ non è un vertice ammissibile, perché produrre zero violerebbe l’obbligo delle 14 unità.
La logica operativa del Simplesso ci insegna a individuare a vista una prima soluzione di base ammissibile sul bordo del contratto: decidiamo di soddisfare la commessa concentrando temporaneamente la produzione solo sul bene B ($x_1 = 0, x_2 = 14$, con surplus zero $e_3 = 0$).
Sostituendo $x_2 = 14 – x_1 + e_3$ nelle altre equazioni, esprimiamo il sistema rispetto alla nostra base iniziale $B = \{s_1, s_2, x_2\}$:
- Equazione di $s_1$: $-3x_1 + 6e_3 + s_1 = 150 – 6(14) \implies -3x_1 + 6e_3 + s_1 = 66$
- Equazione di $s_2$: $3x_1 + 2e_3 + s_2 = 100 – 2(14) \implies 3x_1 + 2e_3 + s_2 = 72$
- Funzione Obiettivo: $-Z + 85x_1 + 106(14 – x_1 + e_3) = 0 \implies -Z – 21x_1 + 106e_3 = -1484$
Organizziamo ora questi coefficienti nella griglia iniziale di calcolo.
Passo 2: Il Tableau Iniziale (Iterazione 0)
Ci troviamo al vertice $(0, 14)$: produciamo solo 14 unità del bene B, spendendo temporaneamente $1484\text{€}$. Le variabili in base sono $s_1, s_2$ e $x_2$; le variabili fuori base (pari a zero) sono $x_1$ e $e_3$.
| Base | x1 | x2 | s1 | s2 | e3 | Termine Noto (b) |
| $-Z$ | -21 | 0 | 0 | 0 | 106 | -1484 |
| $s_1$ | -3 | 0 | 1 | 0 | 6 | 66 |
| $s_2$ | 3 | 0 | 0 | 1 | 2 | 72 |
| $x_2$ | 1 | 1 | 0 | 0 | -1 | 14 |
Analisi di Ottimalità e Scelta del Pivot
Guardiamo la prima riga (la riga di $-Z$): la presenza di un costo ridotto negativo, pari a $-21$ sotto la colonna di $x_1$, ci lancia un segnale economico preciso. Poiché l’obiettivo è massimizzare $-Z$ (ossia minimizzare $Z$), aumentare la produzione del bene A farà crollare i costi! Ogni unità di A che sostituisce un’unità di B comporta infatti un risparmio di $21\text{€}$ ($106\text{€} – 85\text{€}$).
La variabile $x_1$ entra in base.
Per decidere quale variabile deve farle posto, eseguiamo il test del quoziente minimo dividendo i termini noti per i coefficienti strettamente positivi della colonna di $x_1$:
- Riga $s_1$: coefficiente negativo ($-3$), si ignora. (Nota tecnica: inserire la produzione di A riduce le ore di lavoro rispetto a B, facendoci persino avanzare più ore!)
- Riga $s_2$: $\frac{72}{3} = 24$
- Riga $x_2$: $\frac{14}{1} = \mathbf{14}$ (minimo)
Il rapporto minore è $14$, corrispondente alla riga della variabile $x_2$. Questo significa che per conseguire il massimo risparmio dobbiamo azzerare completamente la produzione del bene B ($x_2$ esce di base) e sostituirla con il bene A. L’elemento pivot è il numero $1$ all’incrocio tra la colonna di $x_1$ e la riga di $x_2$.
Passo 3: L’Iterazione di Gauss-Jordan (Tableau 1)
Applichiamo le regole dell’algebra lineare per trasformare la colonna di $x_1$ in un vettore colonna identità (con il pivot pari a $1$ e zeri sopra e sotto):
- La riga pivotale ($x_2$): Essendo il pivot già pari a $1$, la riga rimane invariata: $1x_1 + 1x_2 – 1e_3 = 14$.
- Aggiornamento riga $s_2$: Sottraiamo $3$ volte la riga pivotale:$$(3 – 3)x_1 + (0 – 3)x_2 + 1s_2 + (2 – (-3))e_3 = 72 – 3(14) \implies 0x_1 – 3x_2 + 1s_2 + 5e_3 = 30$$
- Aggiornamento riga $s_1$: Sommiamo $3$ volte la riga pivotale:$$(-3 + 3)x_1 + (0 + 3)x_2 + 1s_1 + (6 – 3)e_3 = 66 + 3(14) \implies 0x_1 + 3x_2 + 1s_1 + 3e_3 = 108$$
- Aggiornamento riga obiettivo ($-Z$): Sommiamo $21$ volte la riga pivotale per calcolare il nuovo costo:$$(-21 + 21)x_1 + (0 + 21)x_2 + (106 – 21)e_3 = -1484 + 21(14) \implies 0x_1 + 21x_2 + 85e_3 = -1190$$
Otteniamo così la nuova configurazione della tabella di calcolo:
| Base | x1 | x2 | s1 | s2 | e3 | Termine Noto (b) |
| $-Z$ | 0 | 21 | 0 | 0 | 85 | -1190 |
| $s_1$ | 0 | 3 | 1 | 0 | 3 | 108 |
| $s_2$ | 0 | -3 | 0 | 1 | 5 | 30 |
| $x_1$ | 1 | 1 | 0 | 0 | -1 | 14 |
3. Interpretazione Economica e Risultato Finale
Osserviamo la prima riga della tabella finale: i coefficienti associati alle variabili attualmente fuori base ($x_2$ ed $e_3$) sono diventati strettamente positivi ($21$ e $85$). In termini algebrici, tutti i costi ridotti sono non negativi: l’algoritmo ha terminato la sua esplorazione perché qualsiasi ulteriore spostamento su vertici adiacenti provocherebbe solo un aumento dei costi operativi.
Leggendo i termini noti associati alla nuova base, l’ufficio programmazione della produzione ottiene un quadro di istruzioni operativo limpido ed esaustivo:
- Piano di Produzione Ottimo: La strategia di minimo costo richiede di concentrare l’intera forza produttiva sul bene A, fabbricando esattamente 14 unità ($x_1 = 14$) e azzerando la produzione del bene B ($x_2 = 0$).
- Costo Minimo Garantito: Il budget di spesa giornaliero crolla da $1484\text{€}$ al vertice iniziale a $1190\text{€}$ al vertice ottimo ($85\text{€} \times 14$), con un risparmio netto d’impresa del 20%.
- Saturazione del Contratta: La variabile di surplus $e_3$ vale zero. Abbiamo soddisfatto al millimetro la richiesta contrattuale di 14 pezzi totali, evitando sovrapproduzioni inutili che assorbirebbero capitali senza generare ricavi immediati.
- Efficienza delle Risorse: Le variabili di scarto ci indicano quante ore di impianto rimangono libere per altre commesse o per la manutenzione. Rimangono inutilizzate 108 ore lavoro ($s_1$) e 30 ore macchina ($s_2$), dimostrando che in questo processo industriale il vero fattore critico e vincolante non era la capacità tecnica dei macchinari, bensì il tetto minimo della domanda contrattuale.
ESPLORA L’ALGEBRA LINEARE
Come abbiamo visto nei passaggi dell’iterazione, il cuore computazionale del metodo del simplesso è l’eliminazione di Gauss-Jordan. Saper manipolare le righe di un tableau matriciale, individuare gli elementi pivot e azzerare i coefficienti con precisione è la competenza fondamentale per padroneggiare la ricerca operativa e risolvere qualsiasi sistema di ottimizzazione.
Se vuoi consolidare le tue basi matematiche e imparare a gestire con sicurezza matrici, vettori e riduzioni a gradini, esplora il Corso di Algebra Lineare: un percorso strutturato con spiegazioni chiare, esempi applicati e tanti esercizi pratici svolti passo dopo passo per affrontare l’algebra senza stress.