Ottimizzazione (matematica)

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

L'ottimizzazione (o programmazione matematica, PM) è una branca della matematica applicata che studia teoria e metodi per la ricerca dei punti di massimo e minimo di una funzione matematica; si ottiene così un modello matematico che traduce in termini matematici un dato problema (non occupandosi quindi direttamente di come tale modello sia stato costruito).

I problemi di ottimizzazione richiedono necessariamente la creazione di 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.

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 contini 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; il 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.

Descrizione[modifica | modifica wikitesto]

È applicabile solo a problemi decisionali con un solo decisore, un solo criterio di scelta ed ambiente certo. L'ambito di ricerca privilegiato dell'ottimizzazione sono i modelli esprimibili in termini di funzioni di più variabili, nei quali i punti di ottimo vengono ricercati ponendo anche vincoli espressi secondo equazioni o disequazioni anche in termini di derivate successive.

Un qualsiasi problema di ottimizzazione può essere espresso nella seguente forma:

dove è il vettore delle variabili decisionali a componenti e è il sottoinsieme dello spazio euclideo definito dai vincoli.

Obiettivo della programmazione matematica è quindi quello di individuare il vettore (cioè i valori da assegnare alle n variabili decisionali) che, rispettando i vincoli, minimizza il valore della funzione obiettivo.

La programmazione matematica è suddivisa in più famiglie di problemi a seconda delle caratteristiche della funzione obiettivo, dei vincoli e quindi delle tecniche di approccio. In generale si distinguono tre categorie:

Classificazione JEL[modifica | modifica wikitesto]

La classificazione del Journal of Economic Literature pone la programmazione matematica, le tecniche di ottimizzazione e i relativi argomenti nelle sottocategorie JEL:C61-C63.

Bibliografia[modifica | modifica wikitesto]

  • (EN) Reiner Horst, Panos M. Pardalos, eds. (1995): Handbook of Global Optimization, Kluwer Academic Publishers, ISBN 0-7923-3120-6
  • (EN) Jonas Mockus, William Eddy, Audris Mockus, Linas Mockus, Gintaras Reklaitis (1997): Bayesian Heuristic Approache to Discrete and Global Optimizationn, Kluwer, ISBN 0-7923-4327-1
  • (EN) Hector O. Fattorini (1999): Infinite dimensional optimization and Control theory, Cambridge University Press, ISBN 0-521-45125-6
  • (EN) Stephen Boyd, Lieven Vandenberghe (2004): Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7, disponibile anche in PDF.
  • (EN) Aleksander Schrijver (1986): Theory of Linear and Integer Programming, J.Wiley, ISBN 0-471-90854-1
  • (EN) Evgenij S. Levitin (1994): Perturbation Theory in Mathematical Programming and its Applications, J.Wiley, ISBN 0-471-93935-8

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Controllo di autoritàGND (DE4043664-0
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica