In questa lezione si presentano i problemi di ottimizzazione caratterizzati dalla presenza di almeno due variabili decisionali, in assenza di relazioni vincolari che definiscano un dominio di ammissibilità delle soluzioni.
Per introdurre l’argomento si presenta un problema di ottimizzazione multidimensionale non vincolata.
Si definiscono quindi le condizioni di ottimalità nei casi di funzioni differenziabili e convesse.
Si introducono i metodi di soluzione a “scalata diretta” della funzione (direct climbing) basati sulla generazione di una successione di punti cui corrispondono valori sempre migliori della funzione obiettivo.
Si presenta infine un esempio numerico dell’algoritmo di discesa ripida.
Un’azienda produce due beni, A e B, il cui profitto unitario è variabile con la produzione. Se con xA ed xB si indicano le quantità prodotte dei beni A e B, il profitto unitario è espresso dalle seguenti funzioni lineari:
pA = pA (xA) = 126 – 9xA
pB = pB (xB) = 182 – 13xB
Il profitto globale è espresso dunque dalla seguente funzione quadratica:
z = pA(xA) · xA + pB(xB) · xB = (126 – 9xA) xA + (182 – 13xB) xB
z = 126 xA – 9 xA2 + 182 xB – 13 xB2
Il massimo di questa funzione si determina nel punto: xA= 7, xB= 7, corrispondente alla produzione di A e B che rende massimo il profitto, con z = 1078. Nelle figure sono riportate le rappresentazioni tri e bidimensionali della funzione, attraverso le curve di livello della stessa sul piano v-g. La curva di livello più esterna corrisponde al valore z = 857.
Condizioni di ottimo per funzioni differenziabili
Condizione necessaria affinché il punto x* sia un punto di minimo (o di massimo) locale (globale) per la funzione differenziabile f (x) definita in un insieme aperto S è che x* sia un punto di stazionarietà della funzione obiettivo, cioè che sia:
∇f (x* ) = 0
Metodi di scalata diretta
Punto iniziale x0
xk+1=xk+θk dk
dk (vettore ad n componenti) direzione di spostamento
θk(scalare non negativo) lunghezza dello spostamento
{xk}≡{x0 , x1, x2 …} successione di punti
f (xk+1) < f (xk ) (Min) miglioramento
f (xk+1) > f (xk) (Max)
precisione per la convergenza dell’algoritmo.
Vettore gradiente e suo valore nel punto iniziale x0 sono espressi da:
Condizione di ottimalità non soddisfatta in x0:
Sostituendo nella formula di espressione f(x) le coordinate x1 e x2 del punto x1 sono in funzione di θ0 si ottiene:
Il punto x1 corrisponde al punto x1 in funzione di θ0, valore di θ0 che costituisce un punto di minimo per g(θ0).
Poiché non é un punto di minimo locale.
La funzione ha un punto di minimo in e dunque:
il punto x2 non è un punto di minimo locale.
Il punto x3 è un punto di minimo locale. Infatti ed inoltre
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...