Il modello in forma canonica
Nella programmazione lineare un modello in forma canonica rispetto a una base è il seguente: $$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
La dimostrazione
Per trasformare un modello di ottimizzazione in forma canonica, devo partire dalla forma standard.
$$ \begin{cases} \min \: z(x) \: = \: c^T x \\ Ax = b \\ x \ge 0 \end{cases} $$
Nella ricerca delle soluzioni di base ammissibili (SBA) devo dividere le componenti in base (B) ed escluse (N).
$$ \begin{cases} \min \: z(x) \: = \: c_B^T x_B + \bar{c}_N^T x_N \\ A_B x_B + A_N x_N = b \\ x_B,x_N \ge 0 \end{cases} $$
Ora ricavo la componente Xb
$$ A_B x_B + A_N x_N = b $$
$$ A_B x_B = b - A_N x_N $$
$$ x_B = \frac{b}{A_B} - \frac{A_N x_N}{A_B} $$
$$ x_B = A_B^{-1}b - A_B^{-1} A_N x_N $$
Quindi riscrivo il modello in questa forma
$$ \begin{cases} \min \: z(x) \: = \: c_B^T x_B + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
Nella soluzione di base XN è nulla.
$$ x_B = A_B^{-1}b $$
Quindi sostituisco XB nella funzione obiettivo senza considerare XN
$$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
E' il modello di ottimizzazione in forma canonica.
Il primo termine della funzione obiettivo è un valore z numerico.
Il secondo termine della funzione obiettivo sono i costi ridotti delle variabili fuori base.
Si calcolano per differenza
$$ \bar{c}_N^T = c^T - c_B^T A_B^{-1} A $$
Quindi, posso riscrivere il modello nella forma canonica in questo modo
$$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + [ c^T - c_B^T A_B^{-1} A ] x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
Un esempio pratico
Ho un problema di ottimizzazione
$$ \begin{cases} \min z(x) = 4x_1 - x_2 \\ \\ x_1-x_2 \le 5 \\ 3x_1+x_2 \le 2 \\ \\ x_1 \ge 0 \\ x_2 \le 0 \end{cases} $$
Lo trasformo in forma standard
$$ \begin{cases} \min z(x) = 4x_1 - x_2\\ \\ x_1-x_2 +x_3 = 5 \\ 3x_1+x_2 + x_4 = 2 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
La matrice dei coefficienti del sistema è
$$ A = \begin{pmatrix} 1 & -1 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix} $$
Nota. Il rango del sistema è r(A)=r(A|B)=2. E' la condizione del teorema di Rouché Capelli perché abbia una o più soluzioni. Inoltre, il numero delle righe (m=2) non è superiore al numero delle variabili (n=4). Le condizioni per cercare le soluzioni di base sono soddisfatte.
Per trasformare il sistema in forma canonica devo cercare una soluzione di base ammissibile.
Seleziono due colonne della matrice dei coefficienti A linearmente indipendenti tra loro ossia con determinante diverso da zero.
Ad esempio, seleziono le colonne [1,2] e ottengo la matrice dei coefficienti A
$$ A_B = \begin{pmatrix} 1 & -1 \\ 3 & 1 \end{pmatrix} $$
Le variabili escluse (x3,x4) compongono un'altra matrice dei coefficienti.
$$ A_N = \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} $$
Le soluzioni XB della base sono
$$ x_B = A_B^{-1} b $$
$$ x_B = \begin{pmatrix} 1 & -1 \\ 3 & 1 \end{pmatrix} ^{-1} \begin{pmatrix} 5 \\ 2 \end{pmatrix} $$
Calcolo matrice inversa e svolgo i calcoli.
$$ x _B = \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} 5 \\ 2 \end{pmatrix} $$
$$ x_B = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} $$
E' una base ammissibile del problema perché nel problema le variabili selezionate devono essere x1≥0 e x2≤0.
Posso cominciare a scrivere il modello in forma canonica rispetto alla base [1,3].
$$ \begin{cases} \min c_B^T A_B^{-1}b + c_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
$$ \begin{cases} \min c_B^T A_B^{-1}b + c_N^T x_N \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Sapendo che i costi di base cB delle variabili x1 e x2 sono (4 , -1 )
$$ \begin{cases} \min (4 , -1 ) \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} + c_N^T x_N \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Ora calcolo il resto
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - A_B^{-1} A_N x_N \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} -0.25 & 0.25 \\ 0.75 & 0.25 \end{pmatrix} \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} -0.25x_3 & 0.25x_4 \\ 0.75x_3 & 0.25x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 = 1.75 + 0.25 x_3 - 0.25x_4 \\ x_2 = -3.25 -0.75x_3 -0.25x_4 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Ora devo solo calcolare i costi ridotti cN delle variabili escluse x4 e x5.
$$ c^T - c_B^T A_B^{-1} A $$
$$ (4, -1, 0, 0) - (4, -1) \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} 1 & -1 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix} $$
$$ (4, -1, 0, 0) - (4, -1) \begin{pmatrix} 1 & 0 & 0.25 & 0.25 \\ 0 & -1 & -0.75 & 0.25 \end{pmatrix} $$
$$ (4, -1, 0, 0) - (4, -1, 1.75, 0.75) $$
$$ (0, 0, -1.75, -0.75) $$
Quindi escludendo le variabili di base (x1,x2) ossia le prime due colonne, i coefficienti di costo delle variabili escluse sono
$$ c_N = (-1.75, -0.75) $$
Una volta trovati posso calcolare l'ultima componente del sistema
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + (-1.75 , -0.75) \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 -1.75x_3 , -0.75 x_4 \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Ho così calcolato il sistema in forma canonica rispetto alla base [1,2].
Nota. La soluzione è ammissibile perché x1≥0 e x2≤0 ma non è ottimale. Esiste almeno un coefficiente di costo della variabili fuori base negativo (-1.75 e -0.75).
E così via.
