Il metodo del simplesso, passo per passo

Nell'articolo sul metodo grafico abbiamo trovato l'ottimo del problema di produzione disegnando la regione ammissibile. Con due variabili funziona; con centinaia conviene cambiare approccio. Serve un metodo algebrico, e il più famoso è il metodo del simplesso.

Lo seguiamo passo per passo sullo stesso problema, inverter ($x_1$) e batterie ($x_2$):

$$\begin{aligned} \max \ \omega &= 4x_1 + 3x_2 \\ 2x_1 + x_2 &\le 14 \\ x_2 &\le 6 \\ x_1,\ x_2 &\ge 0 \end{aligned}$$

Forma standard

Il simplesso lavora con equazioni, non con disuguaglianze. Ogni vincolo $\le$ diventa un'equazione aggiungendo una variabile di scarto, che misura quanto manca al limite:

$$\begin{aligned} 2x_1 + x_2 + s_1 &= 14 \\ x_2 + s_2 &= 6 \end{aligned}$$

$s_1$ sono le ore di collaudo non usate, $s_2$ i moduli di celle avanzati. Il segno di uno scarto dice dove si trova un punto rispetto al vincolo:

• $s_i > 0$: il punto rispetta il vincolo con margine;
• $s_i = 0$: il punto è sulla retta del vincolo;
• $s_i < 0$: il punto viola il vincolo.

Per questo si impone $s_1, s_2 \ge 0$: la regione ammissibile diventa "tutte le variabili non negative".

Infine il problema si scrive come minimo, con $\varphi = -\omega$, e anche l'obiettivo diventa un'equazione del sistema:

$$\begin{aligned} 2x_1 + x_2 + s_1 &= 14 \\ x_2 + s_2 &= 6 \\ 4x_1 + 3x_2 + \varphi &= 0 \end{aligned}$$

con $x_1, x_2, s_1, s_2 \ge 0$ e $\varphi$ da minimizzare.

Punto di partenza

Se l'origine è ammissibile, è comoda per partire: con $x_1 = x_2 = 0$ il sistema dà subito $s_1 = 14$, $s_2 = 6$ e $\varphi = 0$. Ogni iterazione del simplesso ha poi tre passi.

Iterazione 1

Passo A: la soluzione è ottima? Dall'equazione dell'obiettivo:

$$\varphi = 0 - 4x_1 - 3x_2$$

I coefficienti di $x_1$ e $x_2$ sono negativi: aumentando una delle due variabili, $\varphi$ scende, cioè il profitto sale. La soluzione non è ottima. Scegliamo di aumentare $x_1$, che ha il coefficiente più negativo, muovendoci lungo l'asse $x_2 = 0$.

Passo B: di quanto si può avanzare? Con $x_2 = 0$ le equazioni dei vincoli danno $s_1 = 14 - 2x_1$ e $s_2 = 6$. Il secondo non pone limiti, il primo deve restare $\ge 0$:

$$x_1 \le 7$$

È la regola del rapporto minimo: tra i limiti imposti dai vincoli si prende il più stretto, qui l'unico. Con $x_1 = 7$ si arriva al vertice A (7, 0), dove $s_1$ si azzera e $\varphi = -28$.

Passo C: riscrivere il sistema. Nel nuovo punto valgono zero $x_2$ e $s_1$, quindi conviene esprimere tutto in funzione di queste due. Dall'equazione che contiene $s_1$ si ricava $x_1 = 7 - \tfrac{1}{2}x_2 - \tfrac{1}{2}s_1$, e si sostituisce nelle altre:

$$\begin{aligned} x_1 + \tfrac{1}{2}x_2 + \tfrac{1}{2}s_1 &= 7 \\ x_2 + s_2 &= 6 \\ x_2 - 2s_1 + \varphi &= -28 \end{aligned}$$

Iterazione 2

Passo A. Ora $\varphi = -28 - x_2 + 2s_1$: il coefficiente di $x_2$ è negativo, quindi conviene aumentare $x_2$.

Passo B. Con $s_1 = 0$: $x_1 = 7 - \tfrac{1}{2}x_2 \ge 0$ dà $x_2 \le 14$, mentre $s_2 = 6 - x_2 \ge 0$ dà $x_2 \le 6$. Il più stretto è 6: si arriva a B (4, 6), dove si azzera $s_2$, e $\varphi = -28 - 6 = -34$.

Passo C. Dalla seconda equazione $x_2 = 6 - s_2$, che sostituita nell'obiettivo dà:

$$\varphi = -34 + 2\, s_1 + s_2$$

Iterazione 3: l'ottimo

Passo A. I coefficienti di $s_1$ e $s_2$ sono entrambi positivi: aumentare una qualsiasi delle due variabili farebbe salire $\varphi$, cioè peggiorare. Non c'è direzione che migliori, quindi la soluzione è ottima: $x_1 = 4$, $x_2 = 6$, $\varphi = -34$, cioè $\omega = 34$ k€. È lo stesso risultato del metodo grafico.

Al primo passo si poteva scegliere anche $x_2$, utile anche come esercizio.

Riepilogo

• Le variabili di scarto trasformano i vincoli $\le$ in equazioni.
• Ogni iterazione del simplesso ha tre passi: A verifica l'ottimalità, B trova di quanto avanzare con il rapporto minimo, C riscrive il sistema rispetto al nuovo vertice.
• Il simplesso si ferma quando nessun coefficiente dell'obiettivo è negativo.