Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 2.Ottimizzazione non lineare monodimensionale


Schema della lezione

I problemi di ottimizzazione monodimensionale sono quelli che presentano una sola variabile decisionale. Essi sono riconducibili ai semplici problemi di massimizzazione e minimizzazione di una funzione f (x) che svolge il ruolo di parametro di prestazione del sistema.

Questi problemi sono tradizionalmente oggetto di studio nei corsi di Analisi Matematica. Essi sono molto utili per introdurre il concetto di ottimizzazione ed illustrare la costruzione di un modello matematico e di un algoritmo risolutivo.

Nel seguito vengono illustrati semplici problemi decisionali formulabili in termini di modelli di ottimizzazione monodimensionale. Dopo la descrizione delle condizioni di ottimalità, vengono descritti alcuni metodi di ottimizzazione monodimensionale articolati in metodi con uso della derivata e metodi senza uso della derivata.

Risultati sperimentali e funzione interpolante


Funzione obiettivo z = I = f (v)


Esempio 1

Un’azienda produce un bene sostenendo un costo fisso di € 1000, un costo unitario di produzione di € 0.40/unità ed un costo di manutenzione degli impianti pari allo 0.5 del quadrato della quantità di bene prodotta. La capacità produttiva mensile è di 10000 unità. Si vuol calcolare il livello di produzione che determina il minimo costo unitario globale.

Si indichi con x la quantità da produrre e con z il costo unitario globale.

La funzione da minimizzare è espressa da: z = (1000 + 0.4x + 0.5x2)/x
Essa è sottoposta ai vincoli di produzione:

x ≥ 0, x ≤ 10000

La funzione z corrisponde ad un arco di iperbole non equilatera con asintoti

x = 0 e z = 0.5 x + 0.4 .

Il punto di minimo della funzione è x* = 2000 cui corrisponde il valore z* = 1.4.

Pertanto il minimo costo unitario globale è pari a 1.4€/unità e si ottiene con una produzione di 2000 unità al mese.

Esempio 1. Grafico della funzione obiettivo z = f (x)


Esempio 2

Un’azienda manifatturiera produce un bene con una capacità produttiva mensile di 1.5 tonnellate. Essa sostiene un costo fisso mensile pari a € 250 ed un costo variabile di € 0.5 per kg prodotto. La domanda D di bene sul mercato, espressa in kg è funzione del prezzo: D = 2400 – 800 p, dove p è il prezzo espresso in €/kg. L’azienda vuol calcolare la quantità di bene da produrre per ottenere il massimo utile.

Nell’ipotesi che tutta la quantità prodotta sia venduta, si può porre x = D e quindi dalla funzione di domanda si può ricavare il prezzo unitario p di vendita in funzione della quantità prodotta x:

p = (2400-x)/800 = 3 – 0.00125 x.

L’utile, differenza tra ricavi e costi, si può esprimere con

z = (3 – 0.0125 x) x – (250 + 0.5x) = – 0.00125 x2 + 2.5 x – 250.

Si può formulare dunque il seguente modello:

Max z =  – 0.00125x2 +2.5x – 250
sottoposto a x ≥ 0 e x ≤ 1500.

La funzione z corrisponde ad una parabola con la concavità verso il basso. Il punto di ottimo (massimo) è x* = 1000 kg. Il massimo utile è pari a € 1000.

Esempio 2. Grafico della funzione obiettivo z = f (x)


Esempio 3

Un’impresa commerciale acquista merce e la rivende ai dettaglianti. Il costo della merce è di €0.15/kg. Per acquisti di almeno 30 quintali il prezzo è ridotto a € 0.125/kg. La domanda di merce sul mercato è espressa dalla funzione x = 10000 – 20000 p (dove x indica la quantità di merce richiesta e p il prezzo unitario per kg di prodotto). L’impresa sostiene settimanalmente un costo fisso di € 100 e può acquistare al massimo 50 quintali di merce. Si vuol calcolare quanti kg di merce si devono acquistare per ottenere l’utile massimo, nell’ipotesi che tutta la quantità acquistata sia rivenduta. Si indichi con x la quantità (in kg) di merce acquistata e con z l’utile netto. Il costo totale si può esprimere in funzione di x attraverso le relazioni:
C(x) = 0.15x + 100, se x < 3000; C(x) = 0.125x + 100, se x ≥ 3000
Dalla funzione di domanda si può ricavare il prezzo p: p = 0.5 – 5·10-5x.
Il ricavo è dato dunque da: R = p x = (0.5 – 5·10-5x) x.
Si può formulare dunque il seguente modello:

Max z1 = (0.5 – 5·10-5x) x – (0.15x + 100) = – 5·10-5x2 + 0.35 x – 100 x < 3000
Max z2 = (0.5 – 5·10-5x) x – (0.125x + 100) = – 5·10-5x2 + 0.375x – 100 x ≥ 3000

con i vincoli x ≥ 0, x ≤ 5000
Il grafico della funzione è formato dai due archi di parabola riportati in figura. Per x = 3000 la funzione presenta un punto di discontinuità. Nell’intervallo 0 ≤ x < 3000 è crescente. Nell’intervallo 3000 ≤ x ≤ 5000 presenta un punto di massimo per x = 3750, con z = 603.12. Il massimo utile si ottiene quindi con l’acquisto di 3750 kg di merce, con un utile pari a € 603.12.

Esempio 3. Grafico della funzione obiettivo z = f (x)


Punto di ottimo di una funzione monodimensionale e condizioni di ottimalità. Se la funzione f (x) è differenziabile

Condizione necessaria affinché un punto x* sia un punto di minimo (massimo) locale non vincolato:

\frac{df}{dx}\Biggl|_{x=x^*}=0

Condizione sufficiente affinché un punto x* sia un punto di minimo (massimo) locale non vincolato:

\frac{d''f}{dx^2}\Biggl|_{x=x^*}>0\hspace{1cm}(<0)

Metodi di ottimizzazione monodimensionale

Ottimizzazione monodimensionale

  • Metodi con uso della derivata
  • Metodi senza uso della derivata
  • Metodi di riduzione dell’intervallo di incertezza
  • Metodi di generazione di punti

Metodi con uso della derivata


Metodi con uso della derivata a a riduzione dell’intervallo di incertezza

Sia f(x) una funzione pseudoconvessa sull’intervallo [c,b] e c un punto interno all’intervallo [a,b]. Si può dimostrare che:

  • se risulta f ‘ (c ) > 0 … si ha … f (x)f (c ) … … \forall x ∈[ c, b ]
  • se risulta f ‘ (c ) < 0 … si ha … f (x)f (c ) … … \forall x ∈[ a, c ]
  • se risulta f ‘ (c ) = 0 c è un punto di minimo globale

Sia [ak,bk] l’intervallo di incertezza sul punto di minimo all’iterazione k e sia ck un punto interno, nel quale viene effettuato il calcolo della derivata della funzione obiettivo:

  • se f ‘(ck) > 0 … x* ∈ [ak,ck]. ……………Si pone ak+1 = ak , bk+1 = ck
  • se f ‘(ck) < 0 … x* ∈ [ck,bk]. ……………Si pone ak+1 = ck , bk+1= bk
  • se f ‘(ck) = 0 … x* = ck

Algoritmo di bisezione


Metodi con uso della derivata a riduzione a generazione di una successione di punti

L’algoritmo di Newton, o della tangente, è un algoritmo a generazione di una successione di punti. Esso richiede la conoscenza e il calcolo delle derivate prima e seconda della funzione da ottimizzare. A partire da un punto iniziale x0 esso genera una successione di punti attraverso una relazione, facilmente ricavabile in modo geometrico, che lega derivate prima e seconda e due punti consecutivi della successione:

\frac {f'(x_k)}{(x_k - x_{k+1})} = f''(x_k)

dalla quale, conoscendo xk si può ricavare xk+1.

Algoritmo di Newton, o della tangente


Metodi senza uso della derivata


Metodi senza uso della derivata a riduzione dell’intervallo di incertezza

Sia f(x) una funzione pseudoconvessa sull’intervallo [c,b] e siano c, d due punti interni all’intervallo [a,b] tali che c < d. Si può dimostrare che:

  • se risulta f (c ) > f (d ) …si ha ...f (x) > f (d ) ……………. \forallx ] a, c [
  • se risulta f (c ) < f (d ) ...si ha ...f (x) > f (c ) ... ............. \forallx ] d, b [
  • se risulta f (c ) = f (d ) ...si ha ...f (x) f (c ) = f (d ) ... \forallx] a, c [ ] d, b [

Sia [ak,bk] l’intervallo di incertezza sul punto di minimo all’iterazione k e siano ck e dk due punti interni, con ck < dk , nei quali viene effettuato il calcolo della funzione obiettivo:

  • se f (ck) < f (dk) x* [ak,dk]. Si pone ak+1 = ak , bk+1 = dk 
  • se f (ck) > f (dk) x* [ck,bk]. Si pone ak+1 = ck , bk+1= bk 

Algoritmo della ricerca dicotomica


Algoritmo della sezione aurea


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion