La complessità dell'algoritmo del simplesso
Il numero di iterazioni necessarie all'algoritmo del simplesso per convergere a una soluzione è proporzionale al numero dei vincoli del modello e alla radice quadrata del numero delle variabili.
Diversi studi in materia affermano che l'algoritmo del simplesso abbia una complessità esponenziale.
Ecco il numero delle basi da analizzare in un problema con m vincoli e n variabili.
$$ \frac{n!}{m!(n-m)!} $$
Nota. Attualmente non esiste una versione polinomiale dell'algoritmo del simplesso. Esistono versioni polinomiali sperimentali del simplesso ma sono applicabili soltanto in casi limitati. Non sono generali.
La complessità computazionale dell'algoritmo del simplesso è influenzata dalla presenza o meno di basi degeneri ossia SBA con alcuni valori nulli.
- In assenza di basi degeneri l'algoritmo del simplesso non visita mai le stesse basi, perché la SBA è sempre inferiore alla precedente iterazione. Pertanto, il simplesso converge alla soluzione in un numero finito di iterazioni. La complessità dell'algoritmo è esponenziale. Secondo la regola di Klee-Minty sono necessarie in media per convergere alla soluzione
$$ 2^{n}-1 \: iterazioni $$
- In presenza di basi degeneri l'algoritmo del simplesso rischia di entrare in un ciclo infinito perché la SBA potrebbe restare immutata al cambiare delle basi. L'algoritmo è senza memoria e potrebbe visitare le stesse basi già analizzate. In questo caso l'algoritmo potrebbe non terminare mai.
Come evitare i cicli infiniti nel simplesso
Ci sono due possibili rimedi pratici
- Posso assegnare a ogni elemento pivot della matrice una variabile aleatoria che riduce la possibilità di richiamare lo stesso elemento più volte di seguito. Non si esclude del tutto il ciclo ripetuto ma comunque si riduce la probabilità.
- Posso modificare la regola per selezionare la variabile in entrata e in uscita dalla base. Ad esempio, la regola di Bland seleziona la variabile con indice più basso. Questo riduce il rischio dei cicli.
E così via.
