Programmazione non-lineare: differenze tra le versioni

Versione delle 08:20, 22 giu 2006

Versione attuale delle 10:50, 6 ott 2024

(56 versioni intermedie di 40 utenti non mostrate)

Riga 9:

:<math>\min_{x \in X}f(x)</math> per minimizzare una funzione di costo,

dove

:<math>f: \R^n \to \R</math>

o

:<math>f:X \subseteq \R^n. \to \R</math>.

== Procedure di soluzione del problema ==

Se la [[funzione obiettivo]] ''f'' è lineare, e lo [[spazio euclideo|spazio]] del vincolo è un [[politopo]], allora siamo di fronte a un problema di [[programmazione lineare]], che può essere risolto con metodi di programmazione lineare.

Anche quando la funzione obiettivo è convessa su tutte le funzioni di costo (guardando dal basso), si possono applicare soluzioni di programmazione lineare.

Per la soluzione di problemi non convessi ci sono molti metodi. Un approccio possibile è usare formulazioni particolari dei problemi di programmazione lineare. Un altro metodo coinvolge l'uso di tecniche [[branch and bound]], con cui la programmazione è divisa in sottoclassi da risolvere con approssimazioni lineari che vanno a formare un limite inferiore per il costo totale all'interno della suddivisione. Con suddivisioni successive, a un certo punto si otterrà una soluzione effettiva il cui costo è minore o uguale del valore più basso ottenuto per ogni soluzione approssimativa. Questa soluzione è ottimale, anche se non necessariamente unica. L'algoritmo può anche essere fermato prima, se si ha certezza che la miglior soluzione ottenibile non superi che di una data percentuale una soluzione già trovata. Questo vale soprattutto per problemi grandi, difficili, o dai costi non certi.

Le [[condizioni di Kuhn e -Tucker]] forniscono le condizioni necessarie perchèperché una soluzione sia ottimale.

==Esempi==

===Esempio bidimensionale===

[[Immagine:Nonlinear programming jaredwf.png|thumb|right|L'intersezione tra lo spazio dei vincoli e la funzione obiettivo rappresenta la soluzione]]

Un problema elementare può essere definito dai vincoli

:''x''₁ ≥ 0

:''x''₂ ≥ 0

:''x''₁² + ''x''₂² ≥ 1

:''x''₁² + ''x''₂² ≤ 4

e da una funzione obiettivo da massimizzare

:''f''('''x''') = ''x''₁ + ''x''₂

con '''x''' = (''x''₁, ''x''₂)

===Esempio tridimensionale===

[[Categoria:Matematica]]

[[Immagine:Nonlinear programming 3D jaredwf.png|thumb|right|Le intersezioni tra i piani e le superfici centrali rappresentante i vincoli sono le soluzioni]]

Un altro problema elementare può essere definito dai vincoli

:''x''₁² − ''x''₂² + ''x''₃² ≤ 2

:''x''₁² + ''x''₂² + ''x''₃² ≤ 10

e dalla funzione obiettivo da massimizzare

:''f''('''x''') = ''x''₁''x''₂ + ''x''₂''x''₃

con '''x''' = (''x''₁, ''x''₂, ''x''₃)

==Bibliografia==

[[en:Nonlinear programming]]

* Nocedal, Jorge and Wright, Stephen J. (1999). ''Numerical Optimization.'' Springer. ISBN 0387987932.

* Bazaraa, Mokhtar S. and Shetty, C. M. (1979). ''Nonlinear programming. Theory and algorithms.'' [[John Wiley & Sons]]. ISBN 0471786101.

==Voci correlate==

*Metodo dei [[minimi quadrati]]

==Altri progetti==

{{interprogetto|wikt=PNL}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

*{{cita web |1=http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html |2=Nonlinear programming FAQ |accesso=21 giugno 2006 |urlarchivio=https://web.archive.org/web/20090217084003/http://www-unix.mcs.anl.gov/otc/Guide/faq/nonlinear-programming-faq.html |dataarchivio=17 febbraio 2009 |urlmorto=sì }}

*{{cita web | 1 = http://carbon.cudenver.edu/~hgreenbe/glossary/index.php | 2 = Mathematical Programming Glossary | accesso = 21 giugno 2006 | urlarchivio = https://web.archive.org/web/20060525204744/http://carbon.cudenver.edu/~hgreenbe/glossary/index.php | dataarchivio = 25 maggio 2006 | urlmorto = sì }}

*{{cita web | 1 = http://www.lionhrtpub.com/orms/surveys/nlp/nlp.html | 2 = Nonlinear Programming Survey OR/MS Today | accesso = 21 giugno 2006 | urlarchivio = https://web.archive.org/web/20090724004340/http://lionhrtpub.com/orms/surveys/nlp/nlp.html | dataarchivio = 24 luglio 2009 | urlmorto = sì }}

;Software

*[https://web.archive.org/web/20090421074520/http://www.aimms.com/operations-research/mathematical-programming/nonlinear-programming AIMMS Optimization Modeling] [[AIMMS]] — contiene soluzioni di programmazione non lineare in ambito industriale (versione di prova disponibile);

*[http://www.ampl.com/ AMPL solver software] - gratuito per gli studenti (interfaccia grafica disponibile)

*[http://www.gams.com/ GAMS ][[General Algebraic Modeling System]] – versione gratuita per studenti disponibile

*[https://archive.is/20130101224332/http://www.ateji.com/optimj OptimJ Java based modeling language for optimization] [[OptimJ]] - Versione con glpk lp_solve e gratuito per qualsiasi utente. Premium anche gratuito con Mosek, CPLEX y Gurobi per studenti e insegnanti.

{{Controllo di autorità}}

[[Categoria:MatematicaRicerca operativa]]