Simplesso con le matrici: basi, forma canonica e costi ridotti

Nel metodo del simplesso il passo C consisteva nel riscrivere il sistema a ogni iterazione, esprimendo alcune variabili in funzione delle altre. In sostanza, si ripeteva sempre la stessa operazione. La formulazione matriciale permette di esprimere questo procedimento in modo compatto e generale.

Continuiamo con il problema di inverter e batterie in forma standard:

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

Vincoli, riscritti, in forma matriciale

I vincoli sono $r = 2$ equazioni in $c = 4$ incognite. In forma matriciale, $F\,w = b$:

$$F = \begin{bmatrix} 2 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{bmatrix} \qquad b = \begin{bmatrix} 14 \\ 6 \end{bmatrix}$$

con $w = (x_1, x_2, s_1, s_2)$. È un sistema sottodeterminato: ha infinite soluzioni, perché si possono scegliere liberamente $c - r = 2$ variabili, e le altre 2 sono allora determinate dal sistema.

Base e soluzione di base

Riscriviamo il modello, scelgiamo $r$ colonne di $F$ linearmente indipendenti: formano la matrice di base $B$. Le colonne rimaste formano $N$. Le variabili si dividono di conseguenza:

• le variabili di base $w_B$, associate alle colonne di $B$;
• le variabili non di base $w_N$, associate alle colonne di $N$.

Definizione: matrice di base

Sia $F \in \mathbb{R}^{r \times c}$ una matrice di rango $r$, cioè con $r$ righe linearmente indipendenti. Una matrice di base è una sottomatrice quadrata $B \in \mathbb{R}^{r \times r}$ formata da $r$ colonne di $F$ linearmente indipendenti.

Avendo colonne indipendenti, $B$ è invertibile:

$$\det(B) \ne 0$$

Il sistema non cambia, cambia solo il modo di scriverlo. Il prodotto $F\,w$ si spezza in due pezzi, uno con le colonne di base e uno con le altre:

$$F\,w = B\,w_B + N\,w_N = b$$

Ora si moltiplicano entrambi i lati per $B^{-1}$. Siccome $B^{-1} B = I$, davanti a $w_B$ resta l'identità:

$$w_B + B^{-1} N\, w_N = B^{-1} b$$

Questa è la forma canonica rispetto alla base $B$. Portando a destra il termine con $w_N$, ogni variabile di base è espressa solo con le non di base:

$$w_B = B^{-1} b - B^{-1} N\, w_N$$

Definizione: forma canonica

Un sistema è in forma canonica rispetto a un insieme di variabili di base se ogni variabile di base compare in una sola equazione, con coefficiente 1. Detto con le matrici: le colonne delle variabili di base formano l'identità.

Il vantaggio è che il sistema è già "risolto": ogni equazione dà il valore della sua variabile di base, una volta fissate le non di base.

Nel nostro esempio. Il sistema di partenza è già in forma canonica rispetto a $\{s_1, s_2\}$: $s_1$ compare solo nella prima equazione, $s_2$ solo nella seconda, entrambe con coefficiente 1.

Rispetto a $\{x_1, x_2\}$ invece no, perché $x_2$ compare in tutte e due. Con

$$B = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} \qquad B^{-1} = \begin{bmatrix} \tfrac{1}{2} & -\tfrac{1}{2} \\ 0 & 1 \end{bmatrix}$$

e $N = I$ (le colonne di $s_1$ e $s_2$), la moltiplicazione per $B^{-1}$ dà:

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

Ora $x_1$ e $x_2$ compaiono ciascuna in una sola equazione. Portando a destra gli scarti:

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

Con $s_1 = s_2 = 0$ si legge subito il vertice B (4, 6).

Mettendo le variabili non di base a zero si ottiene la soluzione di base, $w_B = B^{-1} b$. Se è anche non negativa si chiama soluzione di base ammissibile, ed è un vertice della regione ammissibile.

Nel nostro esempio le possibili coppie di colonne sono sei:

Le quattro soluzioni di base ammissibili sono esattamente i quattro vertici del disegno. Il punto (0, 14) è l'incrocio di due rette dei vincoli, ma sta fuori dalla regione. L'ultima coppia non è una base: le rette $x_2 = 0$ e $x_2 = 6$ sono parallele e non si incontrano.

I costi ridotti

Ora aggiungiamo anche l'obbiettivo: nel nostro caso $4x_1 + 3x_2 + \varphi = 0$. In generale si scrive

$$-c^\top w + \varphi = \gamma$$

dove:

• $c$ contiene i coefficienti dell'obiettivo da minimizzare (Qui $c = (-4, -3, 0, 0)$).
• $\gamma$ è una costante (poichè gli scarti non portano né profitto né costo, e $\gamma = 0$).

L'idea è la stessa della forma canonica: esprimere $\varphi$ solo con le variabili non di base. Così si vede subito cosa succede all'obiettivo se una di loro aumenta.

1. Si ricava φ, separando i coefficienti delle variabili di base ($c_B$) da quelli delle non di base ($c_N$):

$$\varphi = \gamma + c_B^\top w_B + c_N^\top w_N$$

2. Si sostituisce $w_B = B^{-1} b - B^{-1} N\, w_N$, la forma canonica:

$$\begin{aligned} \varphi = \gamma &+ c_B^\top B^{-1} b - c_B^\top B^{-1} N\, w_N + c_N^\top w_N \end{aligned}$$

3. Si raccolgono i due termini che contengono $w_N$:

$$\begin{aligned} \varphi &= \gamma + c_B^\top B^{-1} b - r_N^\top w_N \\[4pt] r_N^\top &= c_B^\top B^{-1} N - c_N^\top \end{aligned}$$

Nel vertice, dove $w_N = 0$, resta solo $\gamma + c_B^\top B^{-1} b$: è il valore dell'obiettivo nella soluzione di base.

Il vettore $r_N$ contiene i costi ridotti (o coefficienti di costo relativo), uno per ogni variabile non di base. Impostando tutto i valori delle variabili non di base a 0 cosa succede se incremento la variabile non di base, per esempio da 0 a 1, di quanto cambia l'obiettivo?

La risposta si legge nella formula del passo 3. Il prodotto $r_N^\top w_N$ è una somma, con un termine per ogni variabile non di base:

$$\begin{aligned} \varphi = \gamma &+ c_B^\top B^{-1} b \\ &- (r_1 w_1 + r_2 w_2 + \dots) \end{aligned}$$

Nel vertice tutte le $w$ della somma valgono 0. Se una sola di loro, $w_k$, passa a 1, nella parentesi resta solo $r_k \cdot 1$: l'obiettivo diventa $\gamma + c_B^\top B^{-1} b - r_k$. Rispetto al vertice è cambiato di $-r_k$.

Due esempi dal nostro problema:

• Nell'origine la base è $\{s_1, s_2\}$ e l'obiettivo è $\varphi = 0 - 4x_1 - 3x_2$, quindi i costi ridotti di $x_1$ e $x_2$ sono $4$ e $3$. Produrre un inverter in più ($x_1$ da 0 a 1) fa scendere $\varphi$ di 4, cioè fa guadagnare 4 k€. Conviene.
• Nel vertice B la base è $\{x_1, x_2\}$ e l'obiettivo è $\varphi = -34 + 2s_1 + s_2$, quindi i costi ridotti di $s_1$ e $s_2$ sono $-2$ e $-1$. Lasciare inutilizzata un'ora di collaudo ($s_1$ da 0 a 1) fa salire $\varphi$ di 2, cioè fa perdere 2 k€. Non conviene.

Da qui viene la condizione di ottimalità del simplesso, cioè il passo A. Poiché $\varphi = \text{costante} - r_N^\top w_N$:

• se c'è un $r_k > 0$, aumentare $w_k$ fa scendere $\varphi$: la base non è ottima;
• se tutti gli $r_k \le 0$, nessun aumento può far scendere $\varphi$: la base è ottima.

Nell'esempio, alla base ottima $w_B = (x_1, x_2)$:

$$B = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} \qquad B^{-1} = \begin{bmatrix} \tfrac{1}{2} & -\tfrac{1}{2} \\ 0 & 1 \end{bmatrix}$$

$B^{-1} b = (4, 6)$: è il vertice B. Con $c_B = (-4, -3)$ e le non di base $s_1, s_2$ (le cui colonne formano l'identità e i cui costi sono zero):

$$r_N^\top = c_B^\top B^{-1} = (-2,\ -1)$$

Entrambi $\le 0$: la base è ottima, e $\varphi = c_B^\top B^{-1} b = -34$. Sono esattamente i coefficienti trovati a mano nell'ultima iterazione, $\varphi = -34 + 2s_1 + s_2$.

Il tableau

In pratica i conti si organizzano in una tabella, il tableau, che contiene la forma canonica rispetto alla base corrente. Quello finale del nostro problema:

Si legge:

• le colonne delle variabili di base sono vettori unitari;
• la colonna dei termini noti è $B^{-1}b$, con i valori delle variabili di base, e in fondo il valore dell'obiettivo;
• la riga dell'obiettivo contiene i costi ridotti $r_N$;
• le colonne delle variabili di scarto contengono $B^{-1}$ (sopra) e $c_B^\top B^{-1}$ (sotto).

Riepilogo

• I vincoli in forma standard sono un sistema sottodeterminato $F\,w = b$, con infinite soluzioni.
• Una base $B$ è un insieme di colonne indipendenti. La forma canonica esprime le variabili di base con quelle non di base: $w_B = B^{-1}b - B^{-1}N\,w_N$.
• La soluzione di base si ottiene con $w_N = 0$. Se è non negativa è un vertice.
• I costi ridotti $r_N^\top = c_B^\top B^{-1}N - c_N^\top$ dicono se conviene far entrare una variabile: se sono tutti $\le 0$, la base è ottima.