Dato il seguente problema di PL in Forma Standard:
$min \space z = \underline{c}^T \underline{x} \\ A \underline{x} = \underline{b} \\ \underline{x} \geq \underline{0}$
dove $A$ è una matrice $m \times n$, con $m<n$, a rango pieno e $\underline{b} \geq \underline{0}$, supponiamo di voler utilizzare il metodo del simplesso per risolvere il problema
Occorre individuare una sottomatrice di $A$ che sia una base di $\R^m$
Se tra le colonne di $A$ non è presente la matrice identità, l’individuazione di una sottomatrice quadrata $m \times m$ di $A$, con determinante diverso da zero, può essere un’operazione costosa
Il problema viene risolto modificando artificialmente il sistema dei vincoli come segue:
Si aggiunge una variabile artificiale $y_i$ ad ogni vincolo del sistema affinché nel nuovo sistema sia presente una matrice identità (associata alle variabili $\underline{y}$)
Data una soluzione ammissibile $(\underline{x}' , \underline{y}')$ del poliedro $X' = \{A \underline{x} + I \underline{y} = \underline{b}, \underline{x} \geq \underline{0}, \underline{y} \geq \underline{0} \}$, il vettore $\underline{x}'$sarà soluzione ammissibile del poliedro $X = \{A\underline{x} = \underline{b},\underline{x} \geq \underline{0}\}$ se e solo se $\underline{y}' = \underline{0}$
Per ottenere la soluzione $(\underline{x}', \underline{0})$ (se esiste) risolviamo il seguente problema di PL a cui ci riferiremo come problema di PL della 1 fase
$min \space g = \sum_{i =1}^m y_i \\ A\underline{x} + I \underline{y} = \underline{b} \\ \underline{x} \geq \underline{0}, \underline{y} \geq \underline{0}$
Per risolvere il nuovo problema possiamo utilizzare il simplesso a partire dalla matrice identità generata dalle colonne associate alle variabili artificiali $\underline{y}$
Quindi all’inizio della procedura tutte le variabili artificiali $\underline{y}$ sono in base mentre tutte le variabili $\underline{x}$ del problema originale sono fuori base
Alla fine della prima fase possono verificarsi due casi: