Metodo del simplesso: Fase 1

Il metodo del simplesso parte da un vertice ammissibile e si sposta verso vertici migliori. Nel problema di produzione il punto di partenza era l'origine, ma questa spesso non è ammissibile.

La Fase 1 risolve proprio questo: costruisce un problema ausiliario, che ha sempre un punto di partenza, e lo usa per trovare un primo vertice del problema originale. Oppure per dimostrare che non esiste.

Esempio: la miscela di mangime

Riprendiamo l'esempio della miscela dall'articolo sul metodo grafico: 10 kg esatti di mangime da due ingredienti, con un massimo di fibra e un minimo di proteine, al costo più basso.

$$\begin{aligned} \min \ \varphi &= 2x_1 + 3x_2 \\ 3x_1 + x_2 &\le 22 \\ 4x_1 + 2x_2 &\ge 26 \\ x_1 + x_2 &= 10 \\ x_1,\ x_2 &\ge 0 \end{aligned}$$

In forma standard ogni tipo di vincolo si tratta in modo diverso:

• il vincolo $\le$ riceve uno scarto con il più: $3x_1 + x_2 + s_1 = 22$;
• il vincolo $\ge$ riceve uno scarto con il meno, che misura l'eccedenza: $4x_1 + 2x_2 - s_2 = 26$;
• il vincolo $=$ è già un'equazione.

Nell'origine, $x_1 = x_2 = 0$, servirebbe $s_2 = -26$, che non è ammesso, e l'equazione del terzo vincolo darebbe $0 = 10$. L'origine non è ammissibile, e non c'è una base pronta da cui partire.

Le variabili artificiali

Il trucco è aggiungere una variabile artificiale $t_i \ge 0$ a ogni vincolo che non ha già una base pronta:

$$\begin{aligned} 3x_1 + x_2 + s_1 &= 22 \\ 4x_1 + 2x_2 - s_2 + t_2 &= 26 \\ x_1 + x_2 + t_3 &= 10 \end{aligned}$$

Ora l'origine è un punto di partenza valido: con $x_1 = x_2 = s_2 = 0$ si legge subito $s_1 = 22$, $t_2 = 26$, $t_3 = 10$, tutti non negativi.

Le variabili artificiali però "non esistono": una $t_i > 0$ vuol dire che il vincolo originale non è rispettato. Il problema originale si ottiene solo con $t_2 = t_3 = 0$.

Il problema ausiliario

Si cerca quindi di portare a zero le variabili artificiali, minimizzando la loro somma:

$$\min \ \Psi = t_2 + t_3$$

$\Psi$ (letta "Psi") misura quanto il punto è lontano dall'essere ammissibile. Non può mai essere negativa, perché le $t_i$ sono al più positive, quindi il problema ausiliario ha sempre un minimo. Alla fine ci sono due possibilità:

• minimo $\Psi = 0$: tutte le variabili artificiali sono nulle e il vertice trovato è ammissibile per il problema originale. È il punto di partenza per la Fase 2, cioè il simplesso normale con l'obiettivo vero;
• minimo $\Psi > 0$: non c'è modo di soddisfare tutti i vincoli. Il problema originale non ha soluzioni ammissibili.

Prima di iniziare va fatto un ultimo passaggio. Nella base iniziale, $\{s_1, t_2, t_3\}$, l'obiettivo $\Psi$ deve essere espresso con le sole variabili non di base, ma $t_2$ e $t_3$ sono di base. Si sostituiscono con le loro equazioni:

$$\Psi = 36 - 5x_1 - 3x_2 + s_2$$

Come si ottiene l'espressione di Ψ

Dalle due equazioni con le variabili artificiali:

$$\begin{aligned} t_2 &= 26 - 4x_1 - 2x_2 + s_2 \\ t_3 &= 10 - x_1 - x_2 \end{aligned}$$

Sommandole:

$$\begin{aligned} \Psi = t_2 + t_3 &= 36 - 5x_1 - 3x_2 + s_2 \end{aligned}$$

Le iterazioni

Da qui si applica il simplesso, con $\Psi$ al posto dell'obiettivo. Nell'origine non c'è mangime: mancano 26 unità di proteine ($t_2 = 26$) e 10 kg di miscela ($t_3 = 10$), quindi $\Psi = 36$.

Iterazione 1: si aggiunge I1. In $\Psi = 36 - 5x_1 - 3x_2 + s_2$ il coefficiente più negativo è quello di $x_1$, quindi conviene aumentare $x_1$, che finora valeva zero.

Fin dove si può aumentare $x_1$? Ogni vincolo pone un limite, e vale il più stretto:

• proteine: il deficit si azzera con $26/4 = 6{,}5$ kg;
• fibra: il limite di 22 unità si raggiunge con $22/3 \approx 7{,}3$ kg;
• quantità: i 10 kg si raggiungono con 10 kg.

Il più stretto è quello delle proteine: con 6,5 kg di I1 il deficit di proteine $t_2$ arriva a zero, e ci si ferma lì.

Nel linguaggio del simplesso si dice che $x_1$ entra in base (smette di valere zero) e $t_2$ esce dalla base (si azzera). La base è l'elenco delle variabili che, nel vertice corrente, possono essere diverse da zero.

Si arriva in A (6,5; 0): le proteine bastano, ma mancano ancora 3,5 kg di miscela, e $\Psi = 3{,}5$.

Iterazione 2: si aggiunge I2. Riscritta rispetto alla nuova base, l'espressione diventa $\Psi = 3{,}5 - 0{,}5\,x_2 - 0{,}25\,s_2 + 1{,}25\,t_2$, e il coefficiente più negativo è quello di $x_2$.

Ora il simplesso aggiunge I2 restando sulla retta delle proteine.

Si arriva in D (3, 7), dove non manca più niente: $\Psi = 0$.

Nel disegno l'area colorata è la regione del problema ausiliario: i punti che rispettano il limite sulla fibra e non superano i 10 kg. Le variabili artificiali la rendono più grande di quella vera, perché coprono proteine e chilogrammi mancanti. La regione ammissibile vera è solo il segmento evidenziato tra D e C, sulla retta dei 10 kg.

La Fase 1 parte da O, scorre lungo l'asse fino ad A e poi lungo la retta delle proteine fino a D, il primo punto del segmento.

Perché la regione ammissibile vera è il segmento DC?

Il vincolo sulla quantità è un'uguaglianza: la miscela deve pesare esattamente 10 kg. Quindi i punti ammessi non formano un'area, ma stanno tutti sulla retta $x_1 + x_2 = 10$. Su questa retta vale $x_2 = 10 - x_1$, e lo si sostituisce negli altri due vincoli.

Fibra, al massimo 22:

$$\begin{aligned} 3x_1 + (10 - x_1) &\le 22 \\ x_1 &\le 6 \end{aligned}$$

Il caso limite è C (6, 4): con più I1 la fibra supera 22.

Proteine, almeno 26:

$$\begin{aligned} 4x_1 + 2(10 - x_1) &\ge 26 \\ x_1 &\ge 3 \end{aligned}$$

Il caso limite è D (3, 7): con meno I1 le proteine non bastano.

Restano i punti della retta con $3 \le x_1 \le 6$: il segmento da D a C.

La Fase 2

Da D (3, 7) si riparte con l'obiettivo originale, $\varphi = 2x_1 + 3x_2$. In D vale 27 €. Una sola iterazione porta all'altro estremo del segmento, C (6, 4), dove $\varphi = 24$ €: è l'ottimo. Conviene usare più ingrediente I1, che costa meno, fin dove lo permette il limite sulla fibra.

Le variabili artificiali, ormai a zero, si eliminano: il loro unico compito era trovare il punto di partenza.

Riepilogo

• Se l'origine non è ammissibile, il simplesso non ha un punto di partenza.
• I vincoli $\ge$ ricevono uno scarto con il meno; ai vincoli $\ge$ e $=$ si aggiunge una variabile artificiale $t_i \ge 0$, che fornisce una base iniziale.
• La Fase 1 minimizza $\Psi = \sum t_i$, che misura l'inammissibilità. Va prima espressa con le sole variabili non di base.
• Se il minimo è $\Psi = 0$, si ha un vertice ammissibile da cui parte la Fase 2. Se è $\Psi > 0$, il problema non ha soluzioni.