Forma canonica in funzione di una base $B$

Consideriamo il problema (PL) in Forma Standard:

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

Data una base $B$ ammissibile, riscriviamo il problema in funzione di $B$ come segue:

$min \space z = z_0 - \sum_{j \in N} (z_j-c_j) x_j \\ \underline{x}B = \underline{\overline{b}} - \sum{j \in N} \underline{y}_j \underline{x}_j \\ \underline{x} \geq 0$

Con $z_0 = \underline{c}_B^T A_B^{-1} \underline{b}$, $z_j = \underline{c}_B^T A_B^{-1}\underline{a}_j$, $\underline{\overline{b}} = A_B^{-1} \underline{b}$, $\underline{y}_j = A_B^{-1} \underline{a}_j$

Teorema (Condizione di ottimalità)

Una soluzione di base non degenere di un problema di PL è ottima se e solo se:

1. $\overline{b}_i \geq 0$ $i = 1,..,m$ (ammissibile)
2. $z_j - c_j \leq 0$ $\forall j \in N$ (non migliorabile)

Scelta della variabile entrante

Quando le condizioni di ottimalità non sono verificate è sempre possibile scegliere una variabile fuori base $x_k$ da portare in base per migliorare l’obiettivo

Quando esistono più alternative la scelta non preclude il raggiungimento della soluzione ottima, ma può al peggio aumentare il tempo necessario per la sua ricerca

Metodo del gradiente

Sceglie la variabile fuori base $x_k$ che localmente fa aumentare più rapidamente l’obiettivo: $z_k - c_k = max_{j \in N} \{z_j-c_j\}$

Scelta della variabile uscente

Determinata la variabile fuori base $x_k$ da portare in base, si deve scegliere la variabile uscente

Esistono due situazioni alternative:

1. $y_{ik} \leq 0$ $\forall i = 1,..,m$ La soluzione del problema è illimitata (non esiste un punto di ottimo) In questo caso facendo aumentare $x_k$ il valore di nessuna variabile di base diminuisce: $z = z_0 - (z_k-c_k)x_k \leq z_0$ per qualsiasi valore di $x_k$
2. $y_{rk} > 0$ per almeno un $r$ La soluzione di base non è ottima, bisogna quindi passare alla base successiva