Teoremi

Prima di leggere

1. Quando un insieme $X \subseteq \mathbb{R}^n$ è convesso?
2. Quando una funzione $f$ è convessa? Una funzione lineare $c'x$ lo è?

Se una delle due risposte non torna, conviene rileggere le definizioni di insieme convesso e di funzione convessa prima di andare avanti.

Il problema

Un punto $\tilde x \in X$ è ottimo locale se esiste $\varepsilon > 0$ tale che $f(\tilde x) \le f(z)$ per ogni $z$ in $I_\varepsilon(\tilde x) = \{x \in X : \|x - \tilde x\| \le \varepsilon\}$. Il confronto riguarda solo i punti vicini, e in generale non dice niente su quelli lontani.

Su $X = [0, 1] \cup [2, 3]$ si minimizzi $f(x) = -x$. Con $\varepsilon = 1/2$ i punti di $X$ vicini a $x = 1$ sono quelli di $[1/2, 1]$, e lì $-x \ge -1$: $x = 1$ è ottimo locale. L'ottimo globale però è $x = 3$, con valore $-3$. La funzione è lineare, quindi il guaio sta nell'insieme, che ha un buco fra 1 e 2. Il teorema esclude questa situazione quando $X$ è convesso (niente buchi) e $f$ è convessa.

L'idea

Si prende un $y \in X$ qualsiasi e si vuole $f(\tilde x) \le f(y)$. Se $y = \tilde x$ non c'è niente da dimostrare, quindi sia $y \ne \tilde x$.

Sul segmento da $\tilde x$ a $y$ si sceglie il punto $z = \lambda \tilde x + (1 - \lambda)y$, con $\lambda < 1$ vicino a 1. Di $z$ servono tre fatti, e ciascuno usa un'ipotesi diversa:

• $z \in X$ perché $X$ è convesso;
• $z$ sta nell'intorno di $\tilde x$, perché $\|z - \tilde x\| = (1 - \lambda)\|y - \tilde x\|$ e basta prendere $1 - \lambda \le \varepsilon / \|y - \tilde x\|$; quindi $f(\tilde x) \le f(z)$ per l'ottimalità locale;
• $f(z) \le \lambda f(\tilde x) + (1 - \lambda)f(y)$ perché $f$ è convessa.

Messe in fila:

$f(\tilde x) \le f(z) \le \lambda f(\tilde x) + (1 - \lambda)f(y).$

Si porta $\lambda f(\tilde x)$ a sinistra e resta $(1 - \lambda)f(\tilde x) \le (1 - \lambda)f(y)$. Dato che $1 - \lambda > 0$, dividendo il verso non cambia: $f(\tilde x) \le f(y)$. Per questo serve $\lambda < 1$ in senso stretto, ed è il motivo per cui si è escluso $y = \tilde x$.

Perché vale nella PL

La funzione obiettivo $c'x$ è lineare, quindi convessa. La regione ammissibile è un poliedro. Ogni vincolo, qualunque sia il verso, definisce un insieme convesso, perché $a'(\lambda x + (1 - \lambda)y) = \lambda a'x + (1 - \lambda)a'y$: se $a'x$ e $a'y$ sono entrambi $\ge b$, oppure $\le b$, oppure $= b$, la combinazione lo è anche. Il poliedro è l'intersezione di questi insiemi, e un'intersezione di convessi è convessa: il teorema si applica a ogni problema di PL.

Dove si inciampa di solito

• Credere che il teorema dia un ottimo unico. Dice solo che ogni ottimo locale ha il valore migliore; in un PL gli ottimi possono essere un intero lato, tutti con lo stesso valore.
• Dimenticare la convessità di $X$ e controllare solo $f$: l'esempio con $[0, 1] \cup [2, 3]$ ha una funzione lineare e il teorema fallisce.
• Confondere "locale" con "nessun vertice adiacente migliora". Il teorema parla dell'intorno $I_\varepsilon$. Per passare da "nessun vertice adiacente migliora" a "ottimo locale" serve un argomento a parte (da un vertice ci si allontana muovendosi lungo combinazioni dei suoi lati); il teorema copre solo il passo da locale a globale.
• Applicarlo a un massimo senza pensarci. Per $\max$ serve $f$ concava; nella PL non cambia nulla, perché $\max c'x = -\min(-c'x)$ e $-c'x$ è ancora lineare.

Prima di leggere

1. Quando un vincolo $a_i'x \ge b_i$ (oppure $\le$, oppure $=$) si dice attivo in $x^*$? E un vincolo di segno $x_j \ge 0$?
2. Nel piano, quando due vincoli attivi individuano un solo punto?

Se la seconda non torna, conviene ripassare il legame fra indipendenza lineare e sistemi con soluzione unica.

Tre definizioni dello stesso punto

Gli "angoli" di un poliedro $P \subseteq \mathbb{R}^n$ si possono definire in tre modi.

• Punto estremo: $x^*$ non si scrive come $\lambda y + (1 - \lambda)z$ con $y, z \in P$ diversi da $x^*$, cioè non sta in mezzo a un segmento di $P$.
• Vertice: esiste un vettore $c$ per cui $x^*$ è l'unico punto di minimo di $c'x$ su $P$.
• Soluzione di base ammissibile (SBA): $x^* \in P$, tutti i vincoli di uguaglianza sono attivi e fra i vincoli attivi ce ne sono $n$ linearmente indipendenti.

Per controllare le prime due bisognerebbe passare in rassegna infiniti segmenti o infiniti vettori $c$; la terza si verifica con un sistema lineare. Il teorema dice che le tre definizioni individuano gli stessi punti, quindi un angolo visto sul disegno si conferma con un conto.

Un esempio

Si prenda il poliedro

$x_1 + 2x_2 \le 3 \ \ (a), \qquad 2x_1 + x_2 \le 3 \ \ (b), \qquad x_1, x_2 \ge 0,$

con vertici $O = (0, 0)$, $A = (3/2, 0)$, $B = (1, 1)$, $C = (0, 3/2)$. Si guardi $B$ con le tre definizioni.

SBA: in $B$ sono attivi (a) e (b). I vettori $(1, 2)$ e $(2, 1)$ sono indipendenti (determinante $1 - 4 = -3$), e $B$ rispetta tutti i vincoli.

Punto estremo: se $B = \lambda y + (1 - \lambda)z$ con $y, z \in P$ e $0 < \lambda < 1$, la quantità $x_1 + 2x_2$ vale al più 3 in $y$ e in $z$, e la loro media pesata vale 3; allora vale 3 in entrambi. Lo stesso per (b). Quindi $y$ e $z$ risolvono lo stesso sistema di (a) e (b), che ha la sola soluzione $B$: $y = z = B$.

Vertice: sommando (a) e (b) si ottiene $3x_1 + 3x_2 \le 6$, cioè $-x_1 - x_2 \ge -2$ su tutto $P$, con l'uguaglianza solo dove (a) e (b) sono entrambi attivi, cioè solo in $B$. Con $c = (-1, -1)$, $B$ è l'unico minimo.

Per confronto, il punto medio $M = (3/4, 0)$ del lato $OA$ attiva il solo vincolo $x_2 \ge 0$, sta in mezzo a un segmento di $P$, e nessuna $c$ lo rende unico minimo, perché $c'M$ è la media di $c'O$ e $c'A$.

Perché le tre cose coincidono

Basta un giro di tre implicazioni, ciascuna delle quali generalizza un pezzo dell'esempio.

• Vertice implica punto estremo. Se $x^*$ è l'unico minimo di $c'x$ e fosse $\lambda y + (1 - \lambda)z$, allora $c'x^*$ sarebbe la media pesata di $c'y$ e $c'z$, entrambi maggiori di $c'x^*$: impossibile.
• Punto estremo implica SBA. Se i vincoli attivi non contengono $n$ vettori indipendenti, esiste una direzione $d \ne 0$ ortogonale a tutti. Spostandosi di $\pm \varepsilon d$ i vincoli attivi restano uguaglianze e quelli non attivi, che hanno un margine, restano soddisfatti per $\varepsilon$ piccolo. Allora $x^*$ è il punto medio fra $x^* + \varepsilon d$ e $x^* - \varepsilon d$, e non è estremo.
• SBA implica vertice. Si sceglie come $c$ la somma dei vettori dei vincoli attivi, scritti nella forma $a_i'x \ge b_i$ (per questo nell'esempio compare il segno meno). Su $P$ vale $c'x \ge \sum b_i$, con l'uguaglianza solo se tutti quei vincoli sono attivi, e l'indipendenza lascia una sola soluzione.

Dal disegno al tableau

In forma standard ogni vincolo attivo è una variabile nulla: la slack del vincolo, oppure la $x_j$ di un vincolo di segno. Con le slack $x_3, x_4$, il vertice $B$ diventa $(1, 1, 0, 0)$: $x_3$ e $x_4$ stanno fuori base, $x_1$ e $x_2$ in base. Il vertice $A$ attiva (b) e $x_2 \ge 0$, quindi $x_4 = x_2 = 0$ e la base è $\{x_1, x_3\}$, con $x_3 = 3 - 3/2 = 3/2$.

Dove si inciampa di solito

• Prendere una soluzione di base per una SBA. $(3, 0)$ attiva (a) e $x_2 \ge 0$, due vincoli indipendenti, ma viola (b) perché $2 \cdot 3 = 6 > 3$. Il teorema richiede $x^* \in P$.
• Contare i vincoli attivi senza guardare l'indipendenza. Se il problema contiene $x_1 \le 1$ e $2x_1 \le 2$, ogni punto della retta $x_1 = 1$ ne attiva due, ma sono la stessa retta.
• Pensare che più di $n$ vincoli attivi escludano il vertice. Con anche $x_1 \le 1$, in $B$ i vincoli attivi sarebbero tre e $B$ resterebbe un vertice, degenere. Il teorema parla di punti: un vertice degenere corrisponde a più basi diverse.

Prima di leggere

1. Che cos'è un punto estremo di un poliedro $P$, e come si riconosce algebricamente?
2. Che cosa vuol dire che un problema $\min c'x$ ha valore ottimo $-\infty$?

Se la prima risposta non torna, conviene rileggere il Teorema 2.6.3 su vertici, punti estremi e SBA.

Quando un poliedro ha un vertice

Il Teorema 2.6.5 dice quando c'è almeno un vertice, il Teorema 2.6.7 che allora l'ottimo, se finito, sta in un vertice.

$P$ contiene una retta se esistono $x \in P$ e $d \ne 0$ con $x + \lambda d \in P$ per ogni $\lambda$ reale. Il semipiano $x_1 + x_2 \ge 1$ contiene la retta $x_1 + x_2 = 1$ (direzione $d = (1, -1)$) e non ha vertici. Aggiungendo $x_1, x_2 \ge 0$ la regione non contiene più rette e compaiono i vertici $(1, 0)$ e $(0, 1)$.

Una retta toglie tutti i vertici. Se $a_i'(x + \lambda d) \ge b_i$ per ogni $\lambda$, deve essere $a_i'd = 0$: altrimenti, mandando $\lambda$ verso $+\infty$ o $-\infty$, il termine $\lambda a_i'd$ diventa negativo quanto si vuole. Allora $d$ è ortogonale a tutti i vettori dei vincoli, e da ogni punto $y \in P$ ci si muove lungo $\pm d$ restando in $P$. Ogni $y$ è il punto medio fra $y + d$ e $y - d$, quindi nessuno è estremo.

Senza rette, invece, un vertice si costruisce partendo da un punto $x \in P$. Se i vincoli attivi in $x$ non contengono $n$ vettori indipendenti, esiste $d \ne 0$ ortogonale a tutti, e lungo la retta $x + \lambda d$ i vincoli attivi restano attivi. La retta non sta tutta in $P$, quindi in almeno un verso si incontra un vincolo nuovo $a_j$, con $a_j'd \ne 0$. Questo vincolo è indipendente da quelli di prima, che erano ortogonali a $d$. Fermandosi lì, i vincoli attivi indipendenti aumentano di uno. Dopo al più $n$ passi se ne hanno $n$, cioè una SBA.

Non contengono rette i poliedri limitati, che stanno in una scatola $|x_i| \le k$ da cui ogni retta esce, e quelli in forma standard: con $x \ge 0$, lungo $x + \lambda d$ una componente con $d_j \ne 0$ diventa negativa in uno dei due versi.

Ottimo in un vertice

Si ripete la costruzione di prima, scegliendo il verso di $d$ in base alla funzione obiettivo. Da un $x \in P$ che non è un vertice si prende $d$ con $c'd \le 0$, così spostandosi il valore non peggiora. Le possibilità sono due:

• si incontra un vincolo nuovo: si ottiene un punto con più vincoli attivi indipendenti e valore non peggiore, e si ripete;
• non si incontra mai un vincolo: se $c'd < 0$ il valore scende senza limite e l'ottimo è $-\infty$; se $c'd = 0$ si usa il verso opposto, che ha lo stesso valore e, dato che $P$ non contiene rette, prima o poi incontra un vincolo.

Così da ogni punto di $P$ si arriva a un vertice che vale almeno altrettanto, oppure si scopre che l'ottimo è $-\infty$. I vertici sono in numero finito, perché le soluzioni di base lo sono: il migliore di essi batte tutti i punti di $P$ ed è ottimo.

Ne segue anche che, quando $P$ ha un vertice, non esiste un terzo esito con l'estremo inferiore finito ma non raggiunto, come in $\min 1/x$ su $x \ge 1$.

Un esempio

Su $P = \{x_1 + x_2 \ge 1,\ x_1, x_2 \ge 0\}$, con vertici $(1, 0)$ e $(0, 1)$:

Togliendo $x_1, x_2 \ge 0$ resta il semipiano: $\min x_1 + x_2$ vale ancora 1, ma gli ottimi formano una retta e non c'è un vertice dove trovarli. Per questo il Teorema 2.6.7 chiede che $P$ abbia un punto estremo.

Dove si inciampa di solito

• Pensare che una regione illimitata dia sempre $-\infty$. Nella tabella la regione è illimitata e due obiettivi su tre hanno un ottimo finito: decide la direzione di $c$.
• Leggere "l'ottimo è in un vertice" come "ogni ottimo è un vertice". Con $\min x_1 + x_2$ sono ottimi anche i punti interni del segmento; il teorema garantisce che fra gli ottimi c'è almeno un vertice.
• Su una regione illimitata, confrontare solo i valori nei vertici. Con $\min -x_1$ il vertice migliore vale $-1$, ma il problema è illimitato. Prima va escluso che una direzione che resta in $P$ faccia scendere l'obiettivo.

Prima di leggere

1. In una SBA con base $B$, quanto vale il costo ridotto di una variabile di base?
2. Quando una SBA si dice degenere?

Se le risposte non tornano, rileggi come si costruisce una soluzione di base in forma standard: $x_B = B^{-1}b$ e $x_N = 0$.

Che cosa misura un costo ridotto

Da una SBA $x$ ci si sposta facendo crescere una sola variabile fuori base $x_j$ da 0 a $\theta$, con le altre fuori base ferme a 0. Perché $Ax = b$ resti vera, le variabili di base compensano: ne viene la $j$-esima direzione di base $d$, con $d_j = 1$ e $d_B = -B^{-1}A_j$. Lungo $d$ il costo vale $c'x + \theta\, c'd$, e

$$c'd = c_j - c_B'B^{-1}A_j = \bar c_j .$$

Quindi $\bar c_j$ è la variazione del costo per ogni unità di $x_j$ che entra. Il teorema usa il segno di questi $n - m$ numeri per decidere se $x$ è ottima, con un'eccezione nel verso inverso.

Perché $\bar c \ge 0$ basta

Prendi un punto ammissibile qualsiasi $y$ e guarda lo spostamento $y - x$. Vale $A(y - x) = 0$, e le sue componenti fuori base sono $y_j \ge 0$, perché in $x$ valevano 0. Un vettore $z$ con $Az = 0$ è fissato dalle sue componenti fuori base: quelle di base si ricavano risolvendo con $B$. Perciò $y - x$ è la somma delle direzioni di base $d^{(j)}$, ognuna con peso $y_j$, e il costo cambia di

$$c'y - c'x = \sum_{j \notin B} y_j\, \bar c_j .$$

Con pesi e costi ridotti tutti $\ge 0$ la somma è $\ge 0$, quindi nessun punto di $P$ costa meno di $x$.

Perché il verso inverso chiede la non degenerazione

Supponi $x$ ottima con $\bar c_j < 0$ per qualche $j$. Se $x$ è non degenere, $x_B > 0$, e per $\theta$ abbastanza piccolo anche $x_B - \theta B^{-1}A_j$ resta $\ge 0$. La direzione $j$ è allora ammissibile e abbassa il costo di $\theta\,|\bar c_j|$, contro l'ottimalità di $x$.

Se $x$ è degenere, una variabile di base può valere 0 e avere componente negativa in $d_B$: qualunque $\theta > 0$ la manda sotto zero. In quel caso la direzione esce subito da $P$ e il costo ridotto negativo non prova niente.

Due esempi

$\min x_1$ con $x_1 \le 2$, $x_1 - x_2 \ge 0$, $x_1 + x_2 \ge 1$, $x \ge 0$, in forma standard con la slack $s_1$ e le surplus $s_2$, $s_3$. Nel vertice $(1/2, 1/2)$ la base è $s_1, x_1, x_2$ e il tableau è

I costi ridotti fuori base valgono $1/2$: la SBA è ottima, con costo $1/2$. Dalla riga di $x_1$ si legge $x_1 = 1/2 + s_2/2 + s_3/2$, cioè ogni unità di $s_2$ o di $s_3$ alza il costo di $1/2$.

Nel secondo esempio la SBA è ottima ma ha un costo ridotto negativo. $\min -x_1$ con $x_1 + x_2 = 0$, $x \ge 0$: l'unico punto ammissibile è $(0, 0)$, quindi è ottimo. Con la base $\{x_2\}$ si ha $x_2 = 0$, una SBA degenere, e $\bar c_1 = -1 - 0 = -1$. La direzione di base $d = (1, -1)$ porta subito $x_2$ sotto zero. Un pivot con $\theta^* = 0$ passa alla base $\{x_1\}$, dove $\bar c_2 = 0 - (-1)\cdot 1 = 1$: il punto è lo stesso, e ora il test passa.

Dove si inciampa di solito

• Leggere il teorema come "ottima se e solo se $\bar c \ge 0$". In generale vale solo la prima implicazione; la seconda richiede che la SBA sia non degenere.
• Credere che $\bar c \ge 0$ escluda soltanto i vertici adiacenti migliori. Il conto su $y - x$ vale per ogni punto di $P$, vicino o lontano.
• Pensare che un costo ridotto nullo fuori base violi la condizione. $\bar c \ge 0$ ammette gli zeri: far entrare quella variabile lascia il costo invariato.

Prima di leggere

1. In un'iterazione entra $x_j$ con $\bar c_j < 0$ e $u = B^{-1}A_j$. Come si calcola il passo $\theta^*$, e di quanto cambia il costo?
2. Al massimo quante basi diverse può avere una matrice $A$ di dimensione $m \times n$?

Se non tornano, rileggi il Teorema 2.7.1 e come si costruisce la direzione di base $j$.

Il problema

Il simplesso passa da una base all'altra, e a priori niente gli impedisce di tornare su una base già visitata e ripetere da lì la stessa sequenza per sempre. Il teorema dice che senza SBA degeneri questo non succede, e che il metodo si ferma in uno di due modi.

Perché nessuna base si ripete

1. Se la SBA corrente è non degenere, $x_{B(i)} > 0$ per ogni $i$. Ogni rapporto $x_{B(i)}/u_i$ con $u_i > 0$ è allora positivo, e così il loro minimo: $\theta^* > 0$.
2. Il costo cambia di $\theta^*\,\bar c_j$, un positivo per un negativo, quindi scende strettamente.
3. Una base fissa la sua SBA ($x_B = B^{-1}b$, $x_N = 0$) e quindi il suo costo. Se una base ricomparisse, il costo tornerebbe a un valore già toccato, mentre i costi visitati scendono sempre. Ogni base compare al più una volta.
4. Le basi sono al più $\binom{n}{m}$, quindi le iterazioni sono finite. Con $n = 6$ e $m = 3$ il limite è 20.

La non degenerazione serve al passo 1. Se una variabile di base vale 0 e ha $u_l > 0$, il rapporto minimo è 0: la base cambia, il punto e il costo no. Allora il passo 3 cade, perché basi diverse possono avere lo stesso costo, e una serie di questi pivot può riportare a una base già vista.

Come finisce

Il metodo si ferma solo a uno dei due test.

• Tutti i $\bar c_j \ge 0$: per il Teorema 2.7.1 la SBA è ottima. Nel tableau la riga 0 è tutta $\ge 0$.
• Qualche $\bar c_j < 0$, ma $u \le 0$. La direzione $d$ con $d_j = 1$, $d_B = -u$ e le altre componenti nulle ha $d \ge 0$ (perché $-u \ge 0$), $Ad = 0$ per costruzione e $c'd = \bar c_j < 0$. Ogni punto $x + \theta d$ con $\theta \ge 0$ resta in $P$: le uguaglianze tengono perché $Ad = 0$, la non negatività perché $x$ e $d$ sono $\ge 0$. Il costo $c'x + \theta\,\bar c_j$ scende senza limite e il valore ottimo è $-\infty$. Nel tableau la colonna entrante non ha elementi positivi.

L'ipotesi $P \neq \emptyset$ serve a partire: un problema ammissibile in forma standard ha almeno una SBA da cui cominciare.

Un esempio

$\min -x_1$ con $x_1 - x_2 \le 1$, $x \ge 0$, slack $x_3$. Si parte dalla base $\{x_3\}$:

Entra $x_1$. L'unico rapporto è $1/1$, quindi esce $x_3$ con $\theta^* = 1 > 0$ e il costo passa da 0 a $-1$. Dopo il pivot (alla riga 0 si somma la riga di $x_1$):

Ora $\bar c_2 = -1$ e sotto c'è solo $-1$, così il metodo si ferma nel secondo modo. La direzione è $d = (1, 1, 0)$, con $Ad = 1 - 1 + 0 = 0$ e $c'd = -1$: i punti $(1 + \theta, \theta, 0)$ soddisfano tutti $x_1 - x_2 = 1$ e costano $-1 - \theta$. Il problema ha solo queste due SBA (con la base $\{x_2\}$ verrebbe $x_2 = -1$), entrambe con la variabile di base pari a 1, quindi l'ipotesi del teorema vale.

Dove si inciampa di solito

• Credere che il simplesso termini sempre. Con SBA degeneri può ciclare, e serve una regola di pivot come quella di Bland.
• Leggere "colonna senza elementi positivi" come "problema senza soluzioni". I punti ammissibili ci sono, e infiniti: è il costo a non avere un minimo.
• Mettere nel test del rapporto anche le righe con $u_i \le 0$. Lungo $d$ quelle variabili restano uguali o crescono, quindi non limitano $\theta$.

Prima di leggere

Con base $B$, che cosa contengono le righe del tableau, scritte come formule?

Se non torna, rileggi la definizione di costo ridotto.

Il problema

Nel pivot la riga 0 viene trattata come le altre: le si somma un multiplo della riga di pivot che azzera l'elemento nella colonna entrante $j$. Le righe da 1 a $m$ diventano $\bar B^{-1}[b \mid A]$ per costruzione. Per la riga 0 l'operazione impone un solo zero, eppure la proposizione dice che dopo il pivot la riga è proprio $[0 \mid c'] - c_{\bar B}'\bar B^{-1}[b \mid A]$.

La forma della riga 0 si conserva

Riscritta, la riga 0 è

$$[0 \mid c'] - g'[b \mid A], \qquad g' = c_B'B^{-1},$$

cioè $[0 \mid c']$ meno una combinazione lineare delle righe di $[b \mid A]$. Anche la riga di pivot è una combinazione di quelle righe, $h'[b \mid A]$, con $h'$ la riga $l$-esima di $B^{-1}$. Sommarne un multiplo alla riga 0 cambia solo i coefficienti, quindi dopo il pivot la riga 0 è $[0 \mid c'] - p'[b \mid A]$ per qualche vettore $p$.

Quale $p$

Sulla nuova riga 0 si sanno due cose.

• Nella colonna $j$ il pivot mette 0, quindi $c_j - p'A_j = 0$.
• Nella colonna $B(i)$ con $i \neq l$, una variabile che resta in base, la riga 0 aveva già 0. Nel vecchio tableau quella colonna è $e_i$, e la riga di pivot vi ha 0 perché $i \neq l$; sommarne un multiplo lascia lo 0, cioè $c_{B(i)} - p'A_{B(i)} = 0$.

Sono le $m$ colonne di $\bar B$, quindi $c_{\bar B}' - p'\bar B = 0$, e siccome $\bar B$ è invertibile $p' = c_{\bar B}'\bar B^{-1}$. Nella colonna 0, dove $[0 \mid c']$ ha 0, resta $-p'b = -c_{\bar B}'x_{\bar B}$.

Un controllo sui numeri

$\min x_1$ con $x_1 + s_1 = 2$, $x_1 - x_2 - s_2 = 0$, $x_1 + x_2 - s_3 = 1$, tutte le variabili $\ge 0$. Nel vertice $(1/2, 1/2)$ la base è $s_1, x_1, x_2$. Gli zeri sulle tre colonne di base danno $p_1 = 0$, $p_1 + p_2 + p_3 = 1$, $-p_2 + p_3 = 0$, cioè $p = (0, 1/2, 1/2)$. Allora $p'b = 1/2$ e $p'A = (1, 0, 0, -1/2, -1/2)$ sulle colonne $x_1, x_2, s_1, s_2, s_3$, e la riga 0 è $[-1/2 \mid 0, 0, 0, 1/2, 1/2]$: la stessa del tableau di quella base.

Dove si inciampa di solito

• Pensare che durante il pivot qualcuno scelga $p$. Nessuno lo calcola: lo fissano gli zeri sulle colonne di base.
• Aggiornare a parte il numero in alto a sinistra. È la colonna 0 della stessa operazione di riga.

Prima di leggere

1. Che cos'è un pivot degenere e perché non fa scendere il costo?
2. Se $x$ è la soluzione di base associata a $B$, che cosa misura il costo ridotto $\bar c_j = c_j - c_B' B^{-1} A_j$?

Se la seconda risposta non torna, conviene rivedere le condizioni di ottimalità.

Il problema

Il teorema di terminazione senza degenerazione funziona perché il costo scende a ogni pivot: nessuna base può ripresentarsi e le basi sono finite. Con i pivot degeneri il costo può restare fermo, e se una base già vista torna la regola, che è deterministica, ripete gli stessi pivot all'infinito: il simplesso cicla.

La regola di Bland sembra arbitraria: entra la variabile di indice minimo fra quelle con costo ridotto negativo, esce quella di indice minimo fra le righe che realizzano il rapporto minimo. Eppure un ciclo con questa regola porta a una contraddizione sul segno di un numero.

Il lemma che serve

Sia $x$ una soluzione di base con matrice $B$ e costi ridotti $\bar c' = c' - c_B' B^{-1} A$, e sia $y$ una qualunque soluzione di $Ay = b$, anche non ammissibile. Allora

$\bar c' y = c'y - c_B' B^{-1} A y = c'y - c_B' B^{-1} b = c'y - c_B' x_B = c'y - c'x.$

Il penultimo passaggio usa $x_B = B^{-1}b$, l'ultimo il fatto che le componenti fuori base di $x$ sono nulle. I costi ridotti di una base misurano quindi lo scarto di costo fra la sua soluzione e ogni altra soluzione del sistema.

L'idea della dimostrazione

Si suppone per assurdo che il simplesso con Bland cicli. Durante il ciclo il costo non può scendere, altrimenti la base di partenza non tornerebbe; quindi ogni pivot ha $\theta^* = 0$ e la soluzione non cambia mai. Ogni variabile che entra o esce nel ciclo è fuori base in qualche momento, perciò vale 0 per tutto il ciclo. Le righe su cui avviene un pivot ospitano solo variabili di questo tipo, quindi hanno 0 in colonna 0. Le altre righe tengono sempre la stessa variabile di base e Bland non le sceglie mai, come non sceglie mai le colonne delle variabili che non entrano. Togliendo queste righe e colonne nessuna scelta cambia, e resta un problema che cicla con la colonna 0 tutta nulla: da qui in poi si lavora su questo.

Sia $q$ l'indice più grande fra le variabili che entrano durante il ciclo. Poiché $x_q$ entra, prima o poi deve anche uscire. Si guardano due tableau:

• $T^1$, quando $x_q$ sta per entrare; i suoi costi ridotti sono $\bar c_j$, con soluzione di base $x$;
• $T^2$, quando $x_q$ sta per uscire ed entra $x_p$; il pivot è sulla riga $l$ di $x_q$. Anche $x_p$ entra nel ciclo, quindi $p < q$.

Che cosa dice Bland in ciascun tableau:

• in $T^1$ entra $x_q$, quindi $\bar c_q < 0$ e $\bar c_j \ge 0$ per ogni $j < q$;
• in $T^2$ entra $x_p$, quindi il suo costo ridotto è $T^2_{0p} < 0$;
• in $T^2$ esce $x_q$: tutte le righe hanno rapporto $0$, perché la colonna 0 è nulla, quindi pareggiano tutte quelle con $T^2_{ip} > 0$. Se una variabile di base $x_j$ con $j < q$ avesse $T^2_{ip} > 0$, Bland farebbe uscire lei. Quindi $T^2_{lp} > 0$ e $T^2_{ip} \le 0$ per le righe con variabile di base di indice minore di $q$.

Da $T^2$ si costruisce una soluzione $y$ facendo salire $x_p$ a 1:

$y_j = \begin{cases} 1 & j = p \\ -T^2_{ip} & x_j \text{ in base nella riga } i \text{ di } T^2 \\ 0 & \text{altrimenti.} \end{cases}$

La $y$ risolve $Ay = b$: le righe di $T^2$ dicono $x_{B(i)} + \sum_{j \notin B} T^2_{ij} x_j = 0$, e con $x_p = 1$ e le altre fuori base a 0 si ottiene proprio $x_{B(i)} = -T^2_{ip}$. Non è di base né ammissibile, ma il lemma non lo chiede. Il suo costo è quello della soluzione corrente più il costo ridotto di $x_p$ in $T^2$, cioè $c'y = c'x + T^2_{0p}$, perché la soluzione corrente di $T^2$ ha lo stesso costo di $x$.

Il conto del segno

Il lemma applicato a $x$ e $y$ dà

$\bar c' y = c'y - c'x = T^2_{0p} < 0.$

Ora si calcola la stessa somma $\sum_j \bar c_j y_j$ termine per termine:

• $j = q$: $\bar c_q < 0$ e $y_q = -T^2_{lp} < 0$, quindi il prodotto è positivo;
• $j < q$: $\bar c_j \ge 0$, e $y_j$ vale 0, 1 oppure $-T^2_{ip} \ge 0$, quindi il prodotto è $\ge 0$;
• $j > q$: $x_j$ non entra mai nel ciclo; se è in base in $T^1$ ha $\bar c_j = 0$, se è fuori base lo resta anche in $T^2$ e non è $x_p$, quindi $y_j = 0$.

La somma è strettamente positiva, contro il segno trovato col lemma. Il ciclo non esiste, e poiché le basi sono finite il simplesso termina.

Un esempio

Si risolve $\min\, -10x_1 - 12x_2 - 12x_3$ con $x_1 + 2x_2 + 2x_3 \le 20$, $2x_1 + x_2 + 2x_3 \le 20$, $2x_1 + 2x_2 + x_3 \le 20$, $x \ge 0$, partendo dalle slack $x_4, x_5, x_6$.

Al primo pivot entra $x_1$, con costo ridotto $-10$, anche se $x_2$ e $x_3$ hanno $-12$: conta l'indice, non il valore. Il pareggio fra $x_5$ e $x_6$ lascia $x_6$ in base a valore 0, e infatti il secondo pivot è degenere: la base cambia, il punto no. La riga 0 finale è $(0, 0, 0, 18/5, 8/5, 8/5)$, tutta non negativa: $(4, 4, 4)$ è ottimo.

Dove si inciampa di solito

• Prendere il minimo sul numero di riga invece che sull'indice della variabile di base. La regola guarda la numerazione delle variabili, fissata una volta per tutte.
• Credere che Bland eviti i pivot degeneri. Li permette, come nel secondo pivot dell'esempio; impedisce solo che una base torni.
• Mescolare i due tableau nel conto finale. I costi ridotti $\bar c_j$ vengono da $T^1$, mentre $y$ e il segno negativo $T^2_{0p}$ vengono da $T^2$: il lemma serve proprio a confrontare dati di due basi diverse.