Soluzione algebrica dei problemi di PL

Consideriamo un problema di PL in Forma Standard:

$min \space z = \underline{c}^T \underline{x} \\ A\underline{x} = \underline{b} \\ \underline{z} \geq \underline{0}$

Poiché $m = rango(A)$ ed $m<n$, si può partizionare $A$ come $A= [A_B| A_N]$ dove:

• $A_B$ è una matrice non singolare $m\times m$ ($det(A_B) \neq 0$)
• $A_N$ è una matrice $m \times (n-m)$

La matrice $A_B$ è composta da $m$ colonne linearmente indipendenti di $A$; tali colonne (viste come vettori) sono quindi una base nello spazio vettoriale ad $m$ dimensioni delle colonne di $A$ → la matrice $A_B$ è detta Matrice di Base (Base)

In corrispondenza di una scelta di $A_B$ ed $A_N$ si può partizionare anche il vettore delle $\underline{x}$: $\underline{x} = \begin{bmatrix} \underline{x}_B \\ \underline{x}_N \end{bmatrix}$

• $\underline{x}_B$ è detto Vettore delle Variabili in Base (Vettore di Base)
• $\underline{x}_N$ è detto Vettore delle Variabili fuori Base

Il sistema di equazioni lineare $A\underline{x} = \underline{b}$ si può riscrivere come: $A_B \underline{x}_B + A_N \underline{x}_N = \underline{b} \Rightarrow A_B^{-1} A_B \underline{x}_b + A_B^{-1}A_N \underline{x}_N = A_B^{-1}\underline{b} \Rightarrow \underline{x}_B = A_B^{-1} \underline{b} - A_B^{-1} A_N \underline{x}_N$

Una soluzione del sistema di equazioni corrisponde a determinare il valore per $m$ variabili ($\underline{x}_B$) avendo fissato arbitrariamente il valore per le restanti $n-m$ variabili ($\underline{x}_N$)

Una scelta particolarmente importante è porre $\underline{x}_N = \underline{0}$ da cui si ottiene: $\underline{x} = \begin{bmatrix} \underline{x}_B \\ \underline{x}_N \end{bmatrix} = \begin{bmatrix} A_B^{-1} \underline{b} \\ \underline{0} \end{bmatrix}$ Soluzione di Base

Se $\underline{x}_b = A_B^{-1} \underline{b} \geq 0$ si ottiene una Soluzione di Base Ammissibile

Teorema (basi-vertici)

Sia $A$ una matrice $m \times n$ di rango $m$ e $\underline{b}$ un vettore $m$ dimensionale

Sia $X$ il poliedro convesso formato da tutti i vettori $\underline{x} \in \R^n$ che soddisfano $A \underline{x} = \underline{b}$ e $\underline{x} \geq \underline{0}$

Un vettore $\underline{x}$ è un vertice di $X$ se e solo se $\underline{x}$ è una soluzione ammissibile di base del sistema

Riassumendo

A ciascuna matrice di base $B$ (ammissibile) corrisponde una sola soluzione di base (ammissibile)