Programmazione non-lineare

Da Wikipedia, l'enciclopedia libera.

In matematica, programmazione non lineare è il processo di soluzione di un sistema di equazioni e disequazioni su un insieme di variabili reali incognite, con una funzione obiettivo da massimizzare o minimizzare.

Indice 1 Formulazione matematica del problema 2 Procedure di soluzione del problema 3 Esempi 3.1 Esempio bidimensionale 3.2 Esempio tridimensionale 4 Voci correlate 5 Riferimenti 6 Collegamenti esterni (in Inglese)

[modifica] Formulazione matematica del problema

Il problema può essere impostato semplicemente come segue:

per massimizzare una variabile, ad esempio la produzione ottenuta

oppure

per minimizzare una funzione di costo,

dove

[modifica] Procedure di soluzione del problema

Se la funzione obiettivo f è lineare, e lo 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é una soluzione sia ottimale.

[modifica] Esempi

[modifica] Esempio bidimensionale

Un problema elementare può essere definito dai vincoli

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

e da una funzione obiettivo da massimizzare

f(x) = x₁ + x₂

con x = (x₁, x₂)

[modifica] Esempio tridimensionale

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₃)

[modifica] Voci correlate

• Metodo dei minimi quadrati

[modifica] Riferimenti

• 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.

[modifica] Collegamenti esterni (in Inglese)

• Nonlinear programming FAQ
• Mathematical Programming Glossary
• Nonlinear Programming Survey OR/MS Today

Software

• AIMMS Optimization Modeling AIMMS — contiene soluzioni di programmazione non lineare in ambito industriale (versione di prova disponibile);
• AMPL solver software - gratuito per gli studenti (interfaccia grafica disponibile)
• GAMS General Algebraic Modeling System – versione gratuita per studenti disponibile