Ottimizzazione (matematica): differenze tra le versioni

I problemi di ottimizzazione richiedono necessariamente la creazione di [[algoritmo|algoritmi]] efficienti in quanto, generalmente, un problema di ottimizzazione possiede uno spazio delle possibili soluzioni di cardinalità esponenziale, quindi anche possedendo il più potente dei [[computer]] non potremmo permetterci di enumerare tutte le possibili soluzioni e scegliere la migliore. A titolo di esempio supponiamo di avere n variabili x(i), i=1,...,n; che possono assumere d(i) valori diversi 0,1,2,...,d(i)-1; in questo caso avremo che il numero di soluzioni ammissibili per il problema sarebbe dato da: ns=d(1)*d(2)*...*d(n). Considerando n=20 e d(i)=4 per ogni i, si otterrebbe ns=4^20, cioè circa 10^12! Di conseguenza un algoritmo enumerativo richiederebbe un tempo di esecuzione proporzionale a 10^12 con soli 20 elementi.

 

 

Un lettore non addetto potrebbe domandarsi come sia possibile trovare la soluzione ottima senza verificare una per una tutte le soluzioni disponibili. Questo può avvenire grazie a meccanismi di classificazione; il dominio delle soluzioni viene organizzato secondo una struttura che le ordina in funzione di determinate caratteristiche, quindi è possibile scartare a priori alcuni sottoinsiemi del dominio delle soluzioni senza esaminarle essendo sicuri del fatto che queste non potranno fornire soluzioni migliori di un determinato obiettivo. È un po' come entrare in una biblioteca e cercare un libro; i libri sono organizzati per argomento e per titolo alfabeticamente, quindi non sarà necessario esplorare tutti i libri della biblioteca per trovare quello che cerchiamo, ma solo un sottoinsieme. Questo è il meccanismo di funzionamento degli algoritmi e delle metodologie di risoluzione dei problemi di ottimizzazione tra cui ricordiamo il [[metodo del simplesso]] e la tecnica del [[branch and bound]].