Un problema di programmazione lineare nasce quando un’azienda deve scegliere quantità di produzione rispettando vincoli tecnici e una funzione obiettivo (minimizzare o massimizzare). Dal 1947, il Metodo del Simplesso di George Dantzig fornisce la procedura per spostarsi tra vertici di un poliedro ammissibile fino al minimo globale. Nel seguito, teoria e algebra si incontrano in una procedura operativa applicata a un caso con costi e vincoli di domanda.
Dal modello al poliedro: come nasce l’istanza del simplesso
Costruire il modello è il primo passaggio. La parte cruciale è tradurre incognite, vincoli e funzione obiettivo in notazione matriciale, così da rendere il problema manipolabile con l’algoritmo.
Schema generale di assegnazione: significato di coefficienti e vettori
- aij: coefficiente tecnico, quantità della risorsa i necessaria per 1 unità del prodotto j. Ogni colonna descrive uno schema di produzione.
- vettore b: disponibilità delle risorse (termini noti) nel periodo considerato, in forma colonnare.
- vettore c: coefficienti di costo o guadagno nella funzione obiettivo.
Con variabili x (quantità da produrre), la funzione obiettivo assume la forma min (o max) come combinazione lineare dei prodotti. I vincoli tecnici si scrivono come disequazioni del tipo A·x ≤ b (o, in altri casi, A·x ≥ b) con x ≥ 0.
Teorema del vertice e perché non serve “forza bruta”
La regione ammissibile definita dai vincoli forma un poliedro convesso. La proprietà determinante è che l’ottimo (massimo o minimo) si trova in un vertice. Il simplesso sfrutta questa struttura: non verifica tutte le combinazioni di base, ma aggiorna in modo mirato la base corrente.
La dinamica del simplesso: ottimalità, quoziente e pivot
Il metodo procede per iterazioni spostandosi tra basi ammissibili. Ogni passo aggiorna la tabella (tableau) tramite una trasformazione algebrica controllata dall’elemento pivot.
Quattro decisioni operative nello stesso ciclo
- Partenza: si individua una prima base ammissibile (un vertice).
- Scelta di ingresso: si analizzano i coefficienti della riga dell’obiettivo per decidere quale variabile fuori base far entrare.
- Scelta di uscita: con il test del quoziente minimo, si determina fino a dove spingere la nuova produzione senza violare i vincoli; la riga che minimizza il rapporto definisce la variabile che esce di base.
- Pivot e Gauss-Jordan: si applicano operazioni di riduzione tipo Gauss-Jordan per trasformare il pivot in 1 e azzerare gli altri coefficienti della colonna, aggiornando il tableau al vertice adiacente.
Si arresta l’iterazione quando la lettura della riga obiettivo conferma che non esistono mosse adiacenti in grado di migliorare ulteriormente la funzione obiettivo.
Iterazione guidata: dal tableau iniziale al piano ottimo
Il caso analizzato riguarda una minimizzazione di costi giornalieri per produrre due beni A e B, con costi unitari 85€ e 106€ e vincoli su ore lavoro, ore macchina e una domanda contrattuale minima di almeno 14 unità.
Il modello di partenza è:
- min Z = 85x1 + 106x2
- vincoli: 3x1 + 6x2 ≤ 150, 5x1 + 2x2 ≤ 100, x1 + x2 ≥ 14, con x1, x2 ≥ 0.
Standardizzazione e base iniziale “di bordo”
Per applicare la procedura, la minimizzazione viene ricondotta a una massimizzazione con segno opposto. I primi due vincoli vengono trasformati in equazioni con variabili di scarto s1, s2; il vincolo contrattuale (≥) introduce una variabile di surplus e3.
Nei problemi con vincolo contrattuale, l’origine non è ammissibile: la base iniziale viene scelta sul bordo della domanda minima, imponendo una produzione temporanea tutta su B: x1 = 0, x2 = 14, con e3 = 0. In questa configurazione, le variabili di base e fuori base vengono letti dal tableau dell’iterazione 0.
Scelta del pivot: perché entra x1 e cosa esce
Nella riga dell’obiettivo, un coefficiente associato a x1 segnala un miglioramento economico. Si esegue quindi il test del quoziente minimo sulla colonna di x1 considerando i coefficienti strettamente positivi.
- Confronto dei rapporti: il valore minimo risulta collegato alla riga della variabile x2.
- Conclusione: x1 entra in base e x2 esce di base.
- Elemento pivot: il pivot è il numero 1 nell’incrocio tra la colonna di x1 e la riga di x2.
Gauss-Jordan sul tableau: risultato dell’iterazione
Si aggiornano le righe applicando le operazioni di riduzione: si rende la colonna pivot una colonna identità. L’esito è un tableau in cui, nella nuova base, i coefficienti nella riga obiettivo risultano non negativi (per il criterio adottato nel tableau).
All’istante in cui non compaiono termini “favorevoli” per ulteriori mosse, l’algoritmo conclude l’esplorazione: la soluzione trovata è ottima.
Risultato: piano minimo, costo e saturazione del contratto
La soluzione economica finale indica che la strategia di minimo costo concentra la produzione sul bene A. In particolare, x1 = 14 e x2 = 0.
- Costo minimo: passa da 1484€ (punto iniziale) a 1190€, pari a 85€ × 14.
- Domanda contrattuale: la variabile di surplus e3 risulta zero, quindi la domanda minima di 14 unità è soddisfatta senza sovrapproduzione.
- Efficienza vincoli: le variabili di scarto s1 e s2 indicano quante ore rimangono libere rispettivamente per lavoro e macchine.
Il messaggio tecnico è che, in questo caso, il vincolo davvero determinante per il minimo non è la capacità macchina, ma il tetto inferiore della domanda imposto dal contratto.
Tabella di Sintesi
| Elemento Chiave | Dettaglio / Impatto |
|---|---|
| Metodo del Simplesso | Algoritmo di Dantzig (1947) che cerca l’ottimo navigando tra vertici del poliedro ammissibile. |
| Schema di assegnazione | Matrice con coefficenti tecnici aij, disponibilità b e funzione obiettivo tramite c. |
| Teorema del vertice | L’ottimo si trova in un vertice: giustifica la ricerca tramite basi ammissibili. |
| Test di ottimalità | Scelta della variabile di ingresso in base ai segnali dalla riga obiettivo. |
| Quoziente minimo | Determina la variabile che esce di base, identificando il “collo di bottiglia”. |
| Pivot e Gauss-Jordan | Aggiorna il tableau: pivot a 1 e azzeramento della colonna per raggiungere il vertice adiacente. |
| Soluzione del caso di minimizzazione | x1=14, x2=0; costo minimo 1190€; surplus e3=0. |
Implicazioni Pratiche: cosa impara lo studente (e cosa cambia nella didattica)
Questo percorso trasforma l’astrazione del simplesso in una sequenza verificabile: base iniziale, scelta di ingresso/uscita e applicazione del pivot con Gauss-Jordan. Per lo studente, il vantaggio è vedere come l’algebra produce direttamente decisioni industriali (quale bene produrre e in che quantità).
La parte sul vincolo contrattuale con ≥ rende esplicito un punto spesso trascurato: non sempre l’origine è ammissibile, quindi la base iniziale va costruita sul bordo. Questo migliora la comprensione di “perché” si standardizza e non solo “come”.
Infine, la lettura dei valori finali delle variabili di scarto collega vincoli e risorse reali: studenti e docenti possono interpretare surplus e slack come indicatori di margini operativi, non come meri simboli.
FAQ
Perché il simplesso trova l’ottimo senza provare tutte le combinazioni?
Perché l’insieme delle soluzioni ammissibili è un poliedro convesso e l’ottimo si colloca in un vertice. Il simplesso esplora vertici adiacenti tramite pivot, limitando la ricerca alle basi pertinenti.
Nel caso di minimizzazione con vincolo “≥”, l’origine può essere ammissibile?
Non necessariamente. Se il vincolo impone una domanda minima, produrre zero può violare il vincolo. In quel caso si sceglie una base iniziale su un vertice compatibile con la condizione contrattuale.
Che ruolo hanno pivot ed eliminazione di Gauss-Jordan nel tableau?
Il pivot definisce quale variabile entra ed esce di base; con Gauss-Jordan si aggiornano le righe del tableau rendendo la colonna pivot una struttura identitaria, così da rappresentare matematicamente il passaggio al vertice adiacente.