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.
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.
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.
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.
Condizione necessaria affinché un punto x* sia un punto di minimo (massimo) locale non vincolato:
Condizione sufficiente affinché un punto x* sia un punto di minimo (massimo) locale non vincolato:
Ottimizzazione monodimensionale
Sia f(x) una funzione pseudoconvessa sull’intervallo [c,b] e c un punto interno all’intervallo [a,b]. Si può dimostrare che:
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:
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:
dalla quale, conoscendo xk si può ricavare xk+1.
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:
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:
2. Ottimizzazione non lineare monodimensionale
3. Ottimizzazione non lineare multidimensionale non vincolata
4. Ottimizzazione non lineare multidimensionale vincolata
5. Ottimizzazione lineare: formulazione di modelli
6. Ottimizzazione lineare: Algoritmo del Simplesso
7. Ottimizzazione lineare: Algoritmo del Simplesso - II parte
8. Ottimizzazione lineare: Algoritmo del Simplesso - III parte
9. Ottimizzazione lineare: il metodo del Big M
10. Ottimizzazione lineare: il metodo delle due fasi
11. Ottimizzazione lineare: Algoritmo del Simplesso revisionato
12. Ottimizzazione lineare: Analisi post-ottimale
13. Ottimizzazione lineare: il modello duale
15. Ottimizzazione intera: il metodo del piano di taglio
16. Ottimizzazione intera: il metodo Branch and Bound
17. Ottimizzazione su rete: Introduzione alla Teoria dei Grafi
18. Ottimizzazione su rete: Problemi di percorso
19. Ottimizzazione su rete: Problemi di flusso
20. Ottimizzazione su rete: Problemi di progetto, circuito e locali...