Ottimizzazione (matematica): differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Ricerca degli zeri del gradiente: segue traduzione da Optimisation (mathématiques) |
m →Descrizione: wklink |
||
Riga 5:
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 <math>n</math> variabili <math>x(i), i=1,\ldots,n</math>; che possono assumere <math>d(i)</math> valori diversi <math>0,1,2,\ldots,d(i)-1</math>; in questo caso avremo che il numero di soluzioni ammissibili per il problema sarebbe dato da: <math>ns=\sum_1^n d(i)</math>. Considerando <math>n=20 \text{ e } d(i)=4</math>, si otterrebbe <math>ns=4^{20} \approx 10^{12}</math>. Di conseguenza un algoritmo enumerativo richiederebbe un tempo di esecuzione proporzionale a <math>10^{12}</math> con soli 20 elementi.
L'ottimizzazione può essere suddivisa in due grandi categorie: ''dinamica'' e ''statica''. Nell'ottimizzazione dinamica i vincoli e le variabili che esprimono il modello del problema possono variare nel tempo. Nella ottimizzazione statica vincoli e variabili sono costanti. A sua volta l'ottimizzazione statica si divide in ''continua'' e ''discreta'' in funzione del fatto che le variabili possano assumere valori continui o discreti. Nell'ambito della programmazione continua distinguiamo tra programmazione ''lineare'', se [[funzione obiettivo]] e vincoli sono lineari, e programmazione ''non lineare'' altrimenti.
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]].
| |||