La matrice Pivot
La matrice pivot è una matrice quadrata usata nell'algoritmo del simplesso per trasformare un modello in forma canonica da una base a un'altra.
Come costruire una matrice pivot
Ho un modello in forma canonica rispetto alla base B[2,3,4].
$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 = 1 + 0.5 x_1 \\ x_3 = 5 - 1.5 x_1 \\ x_4 = 2 - x_1 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$
Lo preparo per calcolare la matrice M.
Sposto i termini noti dei vincoli a destra e tutto il resto a sinistra.
$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$
Poi lo trasformo in una matrice ponendo la funzione obiettivo nella riga 0 (la prima riga) e i termini noti dei vincoli nella colonna 0 (la prima colonna).
La matrice ha m+1=4 righe e n+1=5 colonne.
$$ M = \begin{pmatrix} -d & c_1 & ... & c_n \\ b_1 & a_m1 & ... & ... \\ ... & ... & ... & ... \\ b_m & a_m1 & ... & a_mn \\ \end{pmatrix} $$
$$ M = \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 & 1 \\ \end{pmatrix} $$
Quindi, creo una matrice identità con m+1 righe e m+1 colonne.
In questo caso è una matrice quadrata 4x4
$$ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$
Infine sostituisco alla h-esima colonna con la k-esima colonna.
$$ Q=\begin{pmatrix} 1 & 0 & ... & -c_k/a_{hk} & ... & 0 \\
0 & 1 & ... & -a_{1k}/a_{hk} & ... & 0 \\
... & ... & ... & ... & ... & 0 \\
0 & 0 & ... & 1/a_{hk} & ... & 0 \\
... & ... & ... & ... & ... & 0 \\
0 & 0 & ... & -a_{mk}/a_{hk} & ... & 1 \end{pmatrix} $$
La variabile h è il numero della colonna uscente, ossia la variabile da sostituire nella base, mentre la variabile k è la variabile entrante.
Il prodotto tra la matrice pivot Q è la matrice M genera la matrice del modello in forma canonica rispetto alla nuova base.
$$ M_{B2} = Q M_{B1} $$
Il termine ah,k è il coefficiente positivo dei vincoli più grande ( vedi algoritmo del simplesso ).
Un esempio pratico
Questo modello è in forma canonica nella base B[2,3,4].
La variabile entrante in base è x1 e la variabile uscente dalla base è x3. Pertanto, devo considerare k=1 e h=3.
$$ \begin{cases} \min 9 - 6.5 x_1 \\ \\ x_2 - 0.5 x_1 = 1 \\ x_3 + 1.5 x_1 = 5 \\ x_4 + x_1 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$
Perché? In questo esempio k=1 perché nella funzione obiettivo la variabile x1 ha il coefficiente negativo minore (-6.5), mentre h=3 perché il valore minimo positivo b/a si trova nella riga con indice 3 ossia la terza equazione dei vincoli dove b/a=2/1. $$ h=min( -, \frac{5}{1.5} , \frac{2}{1} ) = 3 $$ La prima riga non viene considerata (-) perché il coefficiente non è positivo a1k=-0.5≤0.
Nella matrice M l'elemento pivot ahk è il numero a31=1 ( rosso ).
$$ M = \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ 2 & {\color{Red} 1 } & 0 & 0 & 1 \\ \end{pmatrix} $$
Nota. La prima riga e la prima colonna della matrice pivot hanno indice pari a zero (0).
Costruisco la matrice identità Q con lo stesso numero di righe della matrice M.
$$ Q= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$
Ora sostituisco la colonna h=3 della matrice Q con gli elementi della colonna k=1 della matrice M opportunamente modificati secondo la regola precedente,
$$ Q= \begin{pmatrix} 1 & 0 & 0 & {\color{Red} 0 } \\ 0 & 1 & 0 & {\color{Red} 0 } \\ 0 & 0 & 1 & {\color{Red} 0 } \\ 0 & 0 & 0 & {\color{Red} 1 } \end{pmatrix} $$
$$ Q = \begin{pmatrix} 1 & 0 & 0 & -c_1/a_{3,1} \\ 0 & 1 & 0 & -a_{1,1}/a_{3,1} \\ 0 & 0 & 1 & -a_{2,1}/a_{3,1} \\ 0 & 0 & 0 & < a_{3,1}/a_{3,1} > \end{pmatrix} $$
$$ Q = \begin{pmatrix} 1 & 0 & 0 & -(-6.5)/1 \\ 0 & 1 & 0 & -(-0.5)/1 \\ 0 & 0 & 1 & -1.5/1 \\ 0 & 0 & 0 & 1/1 \end{pmatrix} $$
$$ Q =\begin{pmatrix} 1 & 0 & 0 & 6.5 \\ 0 & 1 & 0 & 0.5 \\ 0 & 0 & 1 & -1.5 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$
A questo punto moltiplico le matrici Q e M.
$$ M_{new} = Q \cdot M $$
$$ M_{new} = \begin{pmatrix} 1 & 0 & 0 & 6.5 \\ 0 & 1 & 0 & 0.5 \\ 0 & 0 & 1 & -1.5 \\ 0 & 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} -9 & -6.5 & 0 & 0 & 0 \\ 1 & -0.5 & 1 & 0 & 0 \\ 5 & 1.5 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 & 1 \\ \end{pmatrix} $$
$$ M_{new} = \begin{pmatrix} 4 & 0 & 0 & 0 & 6.5 \\ 2 & 0 & 1 & 0 & 0.5 \\ 2 & 0 & 0 & 1 & -1.5 \\ 2 &1 & 0 & 0 & 1 \end{pmatrix} $$
Ho così ottenuto la matrice del modello in forma canonica rispetto alla base [1,2,3]
$$ \begin{cases} \min 4 + 6.5x_4 \\ \\ x_2+0.5x_4 = 2\\ x_3-1.5x_4 = 2 \\ x_1+x_4 = 2 \\ \\ x_1,x_2,x_3,x_4 \ge 0 \end{cases} $$
E' lo stesso risultato che ho ottenuto nell'esercizio dell'algoritmo del simplesso tramite l'operazione pivot.
E così via.
