L'Algoritmo del Simplesso e la Dualità nella Programmazione Lineare

Un'analisi dettagliata con formule, esempi e applicazioni

Principali Concetti Chiave

Iteratività e Ricerca del Vertice Ottimale: Il metodo del simplesso attraversa iterativamente i vertici del politopo delle soluzioni ammissibili per massimizzare o minimizzare la funzione obiettivo.
Utilizzo delle Variabili di Slack: Le disequazioni vengono trasformate in uguaglianze tramite l’introduzione di variabili di slack, rendendo il problema idoneo per il tableau del simplesso.
Dualità e Relazione Primale-Duale: Per ogni problema primale esiste un problema duale, e le soluzioni ottimali di entrambi coincidono in valore, fornendo interpretazioni utili come i "prezzi ombra".

I Fondamenti del Metodo del Simplesso

1. Formulazione del Problema

La programmazione lineare consiste nel risolvere problemi del tipo:

$$\max \; z = c^T x$$
soggetto a:
$$Ax \leq b$$
$$x \geq 0$$

In questa formulazione:

c rappresenta il vettore dei coefficienti della funzione obiettivo;
x è il vettore delle variabili decisionali;
A è la matrice dei coefficienti che determina i vincoli;
b è il vettore dei termini noti.

Per poter applicare l’algoritmo del simplesso, il problema viene convertito in forma standard, ovvero tutte le disequazioni devono essere espresse come uguaglianze. Questo si ottiene tramite l'introduzione delle variabili di slack (o variabili di scarto). Ad esempio, un vincolo del tipo:

$$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1$$
diventa:
$$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n + s_1 = b_1, \quad s_1 \geq 0$$

Analogamente, il problema standard assume la forma:
$$\max \; z = c^T x$$
$$Ax + I\cdot s = b$$
$$x, s \geq 0$$

2. Passaggi dell'Algoritmo del Simplesso

L'algoritmo del simplesso procede attraverso i seguenti passaggi:

2.1. Scelta della Soluzione Base Iniziale

Si seleziona un insieme di variabili di base, tipicamente le variabili di slack, per ottenere una soluzione di base ammissibile (SBA). Queste variabili gabiranno il ruolo di “vertici” iniziali del politopo delle soluzioni.

2.2. Costruzione del Tableau del Simplesso

Il tableau del simplesso è una matrice ampliata che organizza i coefficienti delle variabili, i termini noti dei vincoli e i coefficienti della funzione obiettivo. La struttura tipica del tableau permette di visualizzare e identificare quali variabili possano migliorare la soluzione ottimale.

2.3. Identificazione della Variabile Entrante

Si calcola il vettore dei costi ridotti, che in un problema di massimizzazione sono dati dalla differenza tra i coefficienti della funzione obiettivo e quelli derivati dalla soluzione corrente. La variabile con il costo ridotto più negativo (ovvero quella in grado di aumentare il valore della funzione obiettivo) viene scelta come variabile entrante.

2.4. Identificazione della Variabile Uscente

Per mantenere l'ammissibilità della soluzione, si effettua il test del rapporto minimo: per ogni riga i per cui il coefficiente della colonna della variabile entrante è positivo, si calcola il rapporto tra il termine noto (RHS) e il coefficiente stesso. Il minimo di questi rapporti stabilisce quale variabile di base debba uscire.

2.5. Operazione di Pivot

Con l'individuazione del pivot (l'elemento in corrispondenza dell'incrocio fra la variabile entrante e la variabile uscente), si aggiornano le righe del tableau in modo da rendere la colonna della variabile entrante un vettore unitario (1 per la riga pivot e 0 per le altre), garantendo così la nuova base ammissibile.

2.6. Iterazione e Verifica dell'Ottimalità

Il processo viene ripetuto fino a quando nella riga della funzione obiettivo non rimangono più costi ridotti negativi (in caso di massimizzazione), garantendo così che la soluzione corrente sia ottimale.

L'Esempio Pratico: Risoluzione di un Problema con il Simplesso

1. Formulazione del Problema Primal

Consideriamo il seguente problema di programmazione lineare:

$$\max \; z = 3x_1 + x_2 + 3x_3$$
soggetto a:
$$2x_1 + x_2 + x_3 \leq 2$$
$$x_1 + 2x_2 + 3x_3 \leq 5$$
$$2x_1 + 2x_2 + x_3 \leq 6$$
$$x_1, x_2, x_3 \geq 0$$

Per trasformare il problema in forma standard, aggiungiamo le variabili di slack:

$$2x_1 + x_2 + x_3 + s_1 = 2$$
$$x_1 + 2x_2 + 3x_3 + s_2 = 5$$
$$2x_1 + 2x_2 + x_3 + s_3 = 6$$
con $ s_1, s_2, s_3 \geq 0 $.

La funzione obiettivo diventa:
$$z = 3x_1 + x_2 + 3x_3 + 0 s_1 + 0 s_2 + 0 s_3$$

2. Costruzione del Tableau del Simplesso

Organizzeremo il tableau iniziale dove le colonne rappresentano le variabili $x_1, x_2, x_3, s_1, s_2, s_3$ e la colonna RHS (Right Hand Side) indica i termini noti.

Esempio del tableau iniziale:

Base	x₁	x₂	x₃	s₁	s₂	s₃	RHS
s₁	2	1	1	1	0	0	2
s₂	1	2	3	0	1	0	5
s₃	2	2	1	0	0	1	6
z	-3	-1	-3	0	0	0	0

3. Procedimento di Iterazione: La Pivotazione

Passo 1: Individuare la variabile entrante. Secondo il criterio, si sceglie la variabile con coefficienti più negativi nella riga della funzione obiettivo, in questo caso $x_1$ con coefficiente -3.

Passo 2: Determinare la variabile uscente eseguendo il test del rapporto minimo, cioè:

$$\frac{RHS}{\text{coefficiente in colonna di } x_1} \quad \Rightarrow \quad \frac{2}{2} = 1,\quad \frac{5}{1} = 5,\quad \frac{6}{2} = 3.$$

Il minimo rapporto è 1, dunque la variabile associata a quella riga (in questo caso $s_1$) esce dalla base.

Passo 3: Eseguire l’operazione di pivot sulla cella in posizione (1, $x_1$), cioè l’elemento 2. Dividendo la riga pivot per il coefficiente, la riga diventa:

$$\text{Nuova riga } 1: \quad x_1 = 1,\quad x_2 = \frac{1}{2},\quad x_3 = \frac{1}{2},\quad s_1 = \frac{1}{2},\quad RHS = 1.$$

Successivamente, aggiornare le altre righe (riga 2, riga 3 e la riga obiettivo) per eliminare il contributo di $x_1$ utilizzando le operazioni elementari sulle righe del tableau. Il processo iterativo prosegue fino a che nella riga obiettivo non si presentano più coefficienti negativi.

4. Iterazione Ulteriore e Raggiungimento dell'Ottimalità

Dopo la prima pivotazione, si valuta la riga della funzione obiettivo. Se persistono coefficienti negativi, il procedimento continua scegliendo una nuova variabile entrante e ripetendo l’operazione di pivot. Nella nostra estesa dimostrazione, ipotizziamo che il procedimento porti ad una soluzione di ottimalità con:
$$x_1 = 1,\quad x_2 = 0,\quad x_3 = \frac{8}{5},\quad z = 4.$$

In ogni iterazione è fondamentale verificare che i nuovi valori siano ammissibili (ovvero, rispettino $x \geq 0$) e che il valore della funzione obiettivo migliori progressivamente.

Il Concetto di Dualità nella Programmazione Lineare

1. Fondamenti della Dualità

Ogni problema di programmazione lineare, detto problema primale, possiede un problema associato chiamato problema duale. La relazione tra primale e duale è centrale in quanto, in condizioni di ottimalità, il valore della funzione obiettivo del primale coincide con quello del duale.

Per un problema primale formulato come:

$$\max \; z = c^T x$$
soggetto a:
$$Ax \leq b, \quad x \geq 0,$$

il problema duale si esprime come:

$$\min \; w = b^T y$$
soggetto a:
$$A^T y \geq c, \quad y \geq 0.$$

Il teorema della dualità forte afferma che, se il problema primale ammette una soluzione ottimale, allora esiste una soluzione ottimale per il duale e:
$$z^* = w^*.$$

2. Interpretazione Economica e Applicazioni

Nella pratica, la dualità fornisce informazioni importanti, come i prezzi ombra che indicano il valore marginale delle risorse vincolate. Questo è particolarmente utile in economia nella determinazione del costo opportunità e nella pianificazione delle risorse.

3. Esempio Pratico di Dualità

Consideriamo il seguente problema primale:

$$\max \; z = 3x_1 + 2x_2$$
soggetto a:
$$x_1 + x_2 \leq 4,$$
$$2x_1 + x_2 \leq 5,$$
$$x_1, x_2 \geq 0.$$

Introducendo le variabili di slack $ s_1 $ e $ s_2 $, il problema viene riscritto come:

$$x_1 + x_2 + s_1 = 4,$$
$$2x_1 + x_2 + s_2 = 5.$$

Il problema duale associato, in cui le variabili duali $ y_1 $ e $ y_2 $ corrispondono ai vincoli del primale, diventa:

$$\min \; w = 4y_1 + 5y_2$$
soggetto a:
$$y_1 + 2y_2 \geq 3 \quad \text{(per } x_1\text{)},$$
$$y_1 + y_2 \geq 2 \quad \text{(per } x_2\text{)},$$
$$y_1, y_2 \geq 0.$$

Secondo il teorema della dualità forte, se il primale ammette una soluzione ottimale con $ z^* $, allora il duale ha una soluzione ottimale tale che $ w^* = z^* $. Nell'esempio, ipotizziamo che la soluzione ottimale sia:
$$x_1 = 1, \quad x_2 = 3, \quad z = 9.$$

I moltiplicatori (o prezzi ombra) ottenuti dal duale rappresentano l'impatto di una variazione marginale delle risorse disponibili.

Sintesi e Conclusioni

Riassunto dei Concetti Chiave

Abbiamo esaminato in maniera dettagliata il seguente percorso:

La formulazione standard del problema di programmazione lineare con l’introduzione delle variabili di slack per trasformare le disequazioni in uguaglianze, condizione necessaria per applicare il metodo del simplesso.
Il procedimento iterativo del simplesso: partenza da una soluzione base ammissibile, identificazione della variabile entrante tramite i costi ridotti, determinazione della variabile uscente mediante il test del rapporto minimo, e aggiornamento del tableau fino al raggiungimento dell’ottimalità.
La dualità, che stabilisce una relazione tra il problema primale e il duale, consentendo di interpretare i moltiplicatori e ottenere stime sui costi marginali delle risorse, oltre a garantire che i valori ottimali coincidano in condizioni ideali.

Implicazioni Pratiche e Considerazioni Finali

Il metodo del simplesso, pur non essendo polinomiale nel caso peggiore, si comporta in modo molto efficiente per la maggior parte dei problemi reali di programmazione lineare. Le applicazioni pratiche spaziano dalla pianificazione della produzione alla gestione delle risorse, dalla logistica al problema di trasporto. La capacità del metodo di muoversi da un vertice all'altro del politopo delle soluzioni ammissibili permette di ottenere la soluzione ottima in maniera intuitiva e trasparente.

Parallelamente, il concetto di dualità offre un ulteriore strumento di analisi, permettendo di formulare il problema duale che, in molti casi, può risultare più semplice da risolvere rispetto al primale oppure fornire informazioni supplementari sulla sensibilità della soluzione. Ad esempio, la conoscenza dei prezzi ombra aiuta a valutare come una modifica su uno dei vincoli influenzi il valore della funzione obiettivo.

Conclusioni Finali

In conclusione, l'algoritmo del simplesso e il concetto di dualità rappresentano due pilastri fondamentali della programmazione lineare. Attraverso l'applicazione iterativa del metodo del simplesso, un problema di programmazione lineare viene risolto passo dopo passo fino a raggiungere il vertice ottimo del politopo delle soluzioni ammissibili. Con la dualità, ogni problema primale trova una controparte nel problema duale, garantendo che il valore ottimale raggiunto sia lo stesso in entrambi i casi e fornendo al contempo informazioni extra utili per l’analisi economica e la pianificazione strategica.

Questo approccio combinato, che unisce tecniche numeriche robuste a teorie profonde di ottimizzazione, ha avuto un impatto significativo in numerosi campi applicativi ed è un esempio straordinario di come un algoritmo ben strutturato possa risolvere in maniera efficace problemi complessi e multidimensionali.

Riferimenti

https://www.andreaminini.com/ricerca-operativa/programmazione-lineare/algoritmo-del-simplesso

https://enricogiannini.com/4/algoritmo-del-simplesso/

https://lollox1k.github.io/Matematica/Ricerca-Operativa/Programmazione-lineare/Algoritmo-del-Simplesso

https://www.andreaminini.com/ricerca-operativa/programmazione-lineare/algoritmo-del-simplesso-in-due-fasi

https://www.diag.uniroma1.it/~roma/didattica/RO18-19/cap6A.pdf

https://www.math.unipd.it/~luigi/courses/ricop1718/m02.PLsim.02.esercizirisolti.pdf