Le soluzioni di base

Nella programmazione lineare le soluzioni di base (SB) di un sistema vincolato sono le soluzioni ottenute usando n vincoli linearmente indipendenti. Se le soluzioni sono ammissibili si parla di soluzioni ammissibili di base (SBA).

Cosa sono le soluzioni di base

Ho un poliedro P in forma standard

$$ A \cdot x=b $$

• A è una matrice A_m,n con m righe e n colonne
• x è il vettore delle variabili di decisione
• b è il vettore dei termini noti

Esempio. Il seguente sistema vincolato ha m=3 righe e n=4 colonne. I vincoli non contano come riga. $$ \begin{cases} x_1 +x_2 + x_3 = 4 \\ 2x_2 +x_3 +x_4 = 6 \\ 3x_1 -x_2-2x_4 = 0 \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$ si può riscrivere in forma matriciale $$ Ax=b $$ $$ \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 3 & -1 & 0 & -2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 4 \\ 6 \\ 0 \end{pmatrix}$$

Il sistema soddisfa le seguenti condizioni

$$ rg(A) = m $$

$$ m \le n $$

Esempio. Il rango del sistema precedente è uguale a 3. $$ r_k \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 3 & -1 & 0 & -2 \end{pmatrix} = 3 = m $$ Il numero delle righe (m=3) è minore uguale al numero delle incognite/colonne (n=4). $$ m=3 \le n=4 $$

Questo vuol dire che il sistema ammette soluzioni secondo il teorema di Rouché-Capelli.

$$ rg(A) = rg(A|b) $$

A partire da questo sistema posso costruire una base B ottenuta selezionando m colonne della matrice A.

$$ [ B_{(1)}, ..., B_{( m)} ] $$

Nota. Le lettere B₍₁₎...B_(m) indicano il numero indice della colonna della matrice ( es 1=prima colonna, 2=seconda colonna, ecc. ).

Le colonne selezionate nella base B devono essere vettori linearmente indipendenti.

Usando questi indici, posso costruire una sottomatrice quadrata A_B con colonne linearmente indipendenti.

$$ A_B = [ A_{B_1} , ... , A_{B_m} ] $$

Esempio. Scegliendo [1,2,3] seleziono la prima e la seconda colonna della matrice delle incognite A. $$ A_{B_1} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 3 & -1 & 0 \end{pmatrix} $$

Con le restanti colonne della matrice A, quelle esclude da A_B, posso formare un'altra sottomatrice A_N.

Esempio. Se scelgo le colonne [1,2,3] , le colonne escluse della matrice A sono [4]. In questo caso è solo una ma potrebbero anche essere due o più. Quindi la matrice A_N è la seguente. $$ A_N = \begin{pmatrix} 0 \\ 1 \\ -2 \end{pmatrix} $$

Quindi, posso riscrivere la matrice A come composizione delle sottomatrici A_B e A_N

$$ A = [ A_B , A_N ] $$

Esempio. Nell'esempio precedente la matrice A è composta da $$ A = [ A_B , A_N ] = [ \begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 3 & -1 & 0 \end{pmatrix} , \begin{pmatrix} 0 \\ 1 \\ -2 \end{pmatrix} ] = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 3 & -1 & 0 & -2 \end{pmatrix} $$

Tenendo conto degli indici delle colonne di A_B e A_N posso formare due vettori con le rispettive incognite.

$$ x = \begin{pmatrix} x_B \\ x_N \end{pmatrix} \ge 0 $$

Esempio. La matrice A_B è composta dalla prima, seconda e terza colonna [1,2,3] della matrice A. Quindi, il vettore x_B è composto dalle incognite x₁ , x₂ e x₃. $$ x_B = \begin{pmatrix} x_1 & x_2 & x_3 \end{pmatrix} $$ La matrice A_N è composta dalla quarta colonna [4] della matrice A. Quindi, il vettore x_N è composto dall'incognita x₄. In questo caso è solo una ma potrebbero anche essere due o più. $$ x_N = \begin{pmatrix} x_4 \end{pmatrix} $$

Posso così riscrivere il sistema nel seguente modo:

$$ Ax = b $$

$$ [ A_B , A_N ] [ x_B,x_N ] = b $$

$$ A_B x_B + A_N x_N = b$$

Quindi, le incognite x_B della base sono determinate da:

$$ A_B x_B + A_N x_N = b$$

$$ A_B x_B = b - A_N x_N $$

$$ x_B = \frac{b - A_N x_N}{A_B} $$

$$ x_B = A_B^{-1} ( b - A_N x_N ) $$

$$ x_B = A_B^{-1} b - A_B^{-1} A_N x_N $$

Il vettore delle incognite diventa

$$ x = \begin{pmatrix} x_B \\ x_N \end{pmatrix} \ge 0 $$

$$ x = \begin{pmatrix} A_B^{-1} b - A_B^{-1} A_N x_N \\ x_N \end{pmatrix} \ge 0 $$

Quest'ultima forma è detta forma canonica.

E' la forma standard rappresentata rispetto agli indici della base B.

Come trovare la soluzione del sistema?

Per prima cosa metto a zero il vettore x_N=0.

$$ x_N = 0 $$

Così facendo il vettore x si riduce a

$$ x = \begin{pmatrix} A_B^{-1} b - A_B^{-1} A_N x_N \\ x_N \end{pmatrix} \ge 0 $$

$$ x = \begin{pmatrix} A_B^{-1} b - A_B^{-1} A_N \cdot 0 \\ 0 \end{pmatrix} \ge 0 $$

$$ x = \begin{pmatrix} A_B^{-1} b \\ 0 \end{pmatrix} \ge 0 $$

Le soluzioni di x_B sono dette soluzioni di base del poliedro associate agli indici di base B.

$$ \overline{x_B} = A_B^{-1} b $$

Esempio. Nell'esempio precedente ho selezionato le colonne B=[1,2,3] come base. $$ \overline{x_B} = A_B^{-1} b $$ $$ \overline{x_B} =\begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 3 & -1 & 0 \end{pmatrix} ^{-1} \begin{pmatrix} 4 \\ 6 \\ 0 \end{pmatrix} $$ Calcolo la matrice inversa A^-1. $$ \overline{x_B} =\begin{pmatrix} -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{-3}{2} & \frac{3}{2} & \frac{1}{2} \\ 3 & -2 & -1 \end{pmatrix} \begin{pmatrix} 4 \\ 6 \\ 0 \end{pmatrix} $$ $$ \overline{x_B} = \begin{pmatrix} -\frac{1}{2} \cdot 4 + \frac{1}{2} \cdot 6 + \frac{1}{2} \cdot 0 \\ \frac{-3}{2} \cdot 4 + \frac{3}{2} \cdot 6 + \frac{1}{2} \cdot 0 \\ 3 \cdot 4 -2 \cdot 6 -1 \cdot 0 \end{pmatrix} $$ $$ \overline{x_B} = \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} $$

Le soluzioni di x_B sono soluzioni di base ammissibile ( SBA ) se sono non negative.

$$ \overline{x_B} \ge 0 $$

Una SBA è detta degenere se una o più elementi di x_B sono uguali a zero.

Infine, se le soluzioni di x_B hanno almeno un elemento negativo la base oppure i vettori della base B prescelta sono linearmente dipendenti, la base è detta non ammissibile.

Esempio. Nell'esempio precedente uno dei tre elementi è zero. Si tratta di una base ammissibile degenere. $$ \overline{x_B} = \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} $$

Quante sono le soluzioni di base?

Le soluzioni di base sono date dalle possibili combinazioni di colonne scelte per formare B.

$$ \frac{n!}{m!(n-m)!} $$

Dove n sono le colonne e m le righe della matrice A.

Esempio. Nell'esempio precedente ci sono n=4 colonne e m=3 righe. $$ \frac{n!}{m!(n-m)!} $$ $$ \frac{4!}{3!(4-3)!} $$ $$ \frac{24}{6} = 4 $$ Ci sono 4 soluzioni di base possibili. $$ [ 1,2,3 ] \\ [ 1,2,4] \\ [1,3,4] \\ [2,3,4] $$

Ovviamente non tutte le soluzioni di base sono ammissibili.

Esempio. Vediamo tutte le combinazioni possibili delle colonne della matrice. Le incognite mancanti sono nulle perché fanno parte del vettore x_N. $$ B=[1,2,3] \rightarrow \overline{x_B} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} \text{SBA degenere} $$ $$ B=[1,2.4] \rightarrow \text{non ammissibile perché vettori linearmente dipendenti} $$ $$ B=[1,3,4] \rightarrow \overline{x_B} = \begin{pmatrix} x_1 \\ x_3 \\ x_4 \end{pmatrix}= \begin{pmatrix} 4 \\ 0 \\ 6 \end{pmatrix} \text{SBA degenere} $$ $$ B=[2,3,4] \rightarrow \overline{x_B} = \begin{pmatrix} x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 4 \\ 0 \\ -2 \end{pmatrix} \text{non ammissibile} $$ Le SBA [1,2,3] e [1,3,4] sono soluzioni ammissibili del sistema $$ \begin{cases} x_1 +x_2 + x_3 = 4 \\ 2x_2 +x_3 +x_4 = 6 \\ 3x_1 -x_2-2x_4 = 0 \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$

Alcune potrebbero essere non ammissibili, altre degeneri.

Le coordinate corrispondenti alle SBA sono particolarmente importanti perché

Ogni punto SBA corrisponde a un vertice del poliedro

Quindi, conoscere le SBA equivale a conoscere le coordinate dei vertici della regione ammissibile del problema di ottimizzazione.

Quale soluzione di base ammissibile è ottima?

Dipende dalla funzione obiettivo del modello.

La funzione obiettivo in un modello di ottimizzazione è espressa nella forma.

$$ \min c_1 x_1 + ... + c_n x_n $$

Espressa in forma vettoriale.

$$ \min c^T x $$

Nota. La lettera T indica la trasposizione del vettore da verticale a orizzontale per consentire il prodotto scalare dei due vettori.

Dove c e T sono vettori.

$$ c=\begin{pmatrix} c_1 \\ ... \\ c_n \end{pmatrix} $$

$$ x=\begin{pmatrix} x_1 \\ ... \\ x_n \end{pmatrix} $$

In questo caso, però, sia i costi che le incognite sono distinte in due vettori, uno di base (B) e l'altro con le colonne escluse (N).

$$ \min c^T_B x_B + c^T_N x_N $$

Quindi, per calcolare il costo di ciascuna soluzione devo moltiplicare il vettore dei costi c_B della soluzione di base e le incognite x_B della soluzione di base $$ c_B^T \cdot x_B $$

Esempio. Se la funzione obiettivo fosse $$ \min z(x) = x_1 + 2x_2 - x_4 $$ il vettore dei costi sarebbe $$ \begin{pmatrix} 1 \\ 2 \\ 0 \\ -1 \end{pmatrix} $$ Analizzando le soluzioni di base $$ SBA_{[1,2,3]} \rightarrow z(x) = c^T_B x_B = \begin{pmatrix} 1 , 2 , 0 , {\color{Red} {-1} } \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ {\color{Red} {x_4} } \end{pmatrix} = \begin{pmatrix} 1 , 2 , 0 , {\color{Red} {-1} } \end{pmatrix} \begin{pmatrix} 1 \\ 3 \\ 0 \\ {\color{Red} {0} } \end{pmatrix} = 1 \cdot 1 + 2 \cdot 3 = 7 $$ $$ \min z(x) = x_1 + 2x_2 - x_4 $$ $$ SBA_{[1,3,4]} \rightarrow z(x) = c^T_B x_B = \begin{pmatrix} 1 , {\color{Red} {2} } , 0 , -1 \end{pmatrix} \begin{pmatrix} x_1 \\ {\color{Red} {x_2} } \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 1 , {\color{Red} {2} } , 0 , -1 \end{pmatrix} \begin{pmatrix} 4 \\ {\color{Red} {0} } \\ 0 \\ 6 \end{pmatrix} = 1 \cdot 4 +( -1 ) \cdot 6 = -2 $$

Come trovare la soluzione di base ottima

Una soluzione ottima si ottiene quando x_N è uguale a zero, ossia quando le incognite escluse dalla base sono nulle.

$$ \min c^T_B x_B + c^T_N x_N $$

Per sapere se x_N=0 mi basta controllare il valore di c^T_N.

Secondo il criterio di ottimalità delle soluzioni di base, se c^T_N è maggiore o uguale a zero allora x_N è sicuramente uguale a zero.

Calcolo il vettore dei costi ridotti per differenza a partire dalla funzione obiettivo.

Sono i costi delle incognite escluse dalla base.

$$ \overline{c^T_N} = c^T - c^T_B A^{-1}_B A $$

Dove c^T è il vettore dei costi mentre c^T_B è il vettore dei costi della base.

Ottengo così i costi relativi alle incognite escluse dalla base.

Esempio. Nel caso della soluzione SDA[1,2,3] il costo minimo non è maggiore di zero. E' il costo dell'incognita x₄. $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,2, 0 ) \begin{pmatrix} -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{-3}{2} & \frac{3}{2} & \frac{1}{2} \\ 3 & -2 & -1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 3 & -1 & 0 & -2 \end{pmatrix} $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,2, 0 ) \begin{pmatrix} 1 & 0 & 0 & -0,5 \\ 0 & 1 & 0 & 0,5 \\ 0 & 0 & 1 & 0 \end{pmatrix} $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,2, 0, 0.5 ) $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 0, 0, 0, -1.5 ) $$ Nel caso della soluzione SDA[1,3,4] il costo minimo è maggiore di zero. E' il costo dell'incognita x₂. Pertanto, è una soluzione ottima. $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,0, -1 ) \begin{pmatrix} -2 & 2 & 1 \\ 3 & -2 & -1 \\ -3 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 2 & 1 & 1 \\ 3 & -1 & 0 & -2 \end{pmatrix} $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,0, -1 ) \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 2 & 0 & 1 \end{pmatrix} $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 1, 2, 0, -1 ) - ( 1,-1, 0, -1 ) $$ $$ \overline{c^T_N} = c^T - c^T_B x_B = ( 0, 3, 0, 0 ) $$

Va comunque detto che nel caso delle soluzioni di base degenere il criterio di ottimalità è una condizione necessaria ma non sufficiente.

Esempio

Ho un problema primale di minimizzazione

$$ \begin{cases}
\min z(x) = x_1-3x_2+2x_3-x_4 \\ \\
x_1-2x_2+4x_3+2x_4 \ge 6 \\
-x_1-2x_2-x_3+3x_4 \le 2 \\
3x_1 + 4x_2 -2x_3+x_4 = 0 \\ \\
x_1, x_4 \ge 0 \\
x_2 \le 0
\end{cases}
$$

Calcolo una soluzione di base ammissibile per il problema primale.

Scelgo le colonne [1,2,3] della matrice A dei coefficienti.

Ottengo così una matrice quadrata di base A_B con i coefficienti delle colonne selezionate.

Poi calcolo l'inversa della matrice di base A_B.

$$ \begin{pmatrix} 1 & -2 & 4 \\ -1 & -2 & -1 \\ 3 & 4 & -2 \end{pmatrix}^{-1} = \begin{pmatrix} 0.31 & 0.46 & 0.38 \\ -0.19 & -0.54 &-0.12 \\ 0.08 & -0.38 & -0.15 \end{pmatrix} $$

Le soluzioni di base sono le seguenti:

$$ x = A^{-1}b = \begin{pmatrix} 0.31 & 0.46 & 0.38 \\ -0.19 & -0.54 &-0.12 \\ 0.08 & -0.38 & -0.15 \end{pmatrix} \begin{pmatrix} 6 \\ 2 \\ 0 \end{pmatrix} = \begin{pmatrix} 2.78 \\ -2.22 \\ -0.28 \end{pmatrix} $$

E' una soluzione ammissibile del problema primale.

Verifica. Faccio una verifica usando le soluzioni X [ 2.78 , -2.22 , -0.28 , 0 ] $$ \begin{cases}
\min z(x) = x_1-3x_2+2x_3-x_4 \\ \\
x_1-2x_2+4x_3+2x_4 \ge 6 \\
-x_1-2x_2-x_3+3x_4 \le 2 \\
3x_1 + 4x_2 -2x_3+x_4 = 0 \\ \\
x_1, x_4 \ge 0 \\
x_2 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 2.78-3(-2.22)+2(-0.28)-0 \\ \\
2.78-2(-2.22)+4(-0.28)+2(0) \ge 6 \\
-2.78-2(-2.22)-(-0.28)+3(0) \le 2 \\
3·2.78 + 4(-2.22) -2(-0.28)+0 = 0 \\ \\
2.78, x_4 \ge 0 \\
-2.22 \le 0
\end{cases}
$$ $$ \begin{cases}
\min z(x) = 8,88 \\ \\
6.1 \ge 6 \\
1.94 \le 2 \\
0 = 0 \\ \\
2.78, x_4 \ge 0 \\
-2.22 \le 0
\end{cases}
$$ Le soluzioni sono ammissibili e risolvono il problema.

Verifico se è una soluzione ottimale

$$ c^T - c^T_B A^{-1}_B A $$

$$ (1,-3,2,-1) - (1, -3, 2 ) \begin{pmatrix} 0.31 & 0.46 & 0.38 \\ -0.19 & -0.54 &-0.12 \\ 0.08 & -0.38 & -0.15 \end{pmatrix} \begin{pmatrix} 1 & -2 & 4 & 2 \\ -1 & -2 & -1 & 3 \\ 3 & 4 & -2 & 1 \end{pmatrix} $$

$$ (1,-3,2,-1) - (1, -3, 2, 6.42 ) $$

$$ (0,0,0,6.42) $$

In questo caso è una soluzione ottimale.

E così via.