Metodi di ottimizzazione della Ricerca operativa

APPUNTI OTTIMIZZAZIONE

Ottimizzare: Trovare la decisione migliore in processi decisionali complessi, o anche trovare il max/min di una funzione (profitto, costo...)

Per rappresentare il fenomeno in esame in maniera selettiva e semplificata, usiamo dei modelli, di cui esistono varie classificazioni (il livello di astrazione, la natura nei dati, la dimensione temporale...)

Sviluppo di un modello:

• Identificare il problema
• Formulare il modello (componenti importanti, orizzonti temporali...) scegliendo le variabili di decisione e l'indicatore di valutazione
• Risolvere il problema con un algoritmo risolutivo
• Collaudare il mio assestato, vedere che sia sempre ammissibile, e che succede se cambiano i dati (stabilità del risultato)

Componenti di analisi che ha invisto: Spazi vettoriali, vettori, matrici, sottospazi, funzioni, applicazioni lineari, Rouché-Capelli, matrice invertibile, regola di Cramer e gessi per matrici, topologie

IL PROBLEMA DI OTTIMIZZAZIONE

• Min o Max (scelta) di una funzione
• Funzione obiettivo f(x): quantifica la qualità della soluzione che voglio max-min
• Variabili di decisione: Le x, cosa caratterizza la soluzione, cosa voglio decidere
• Regione ammissibile K: i vincoli, i limiti delle nostre decisioni, la loro ammissibilità. È spesso descritta con relazioni matematiche che soddisfano un insieme di vincoli: g(k) ≤ b.

NB f(x) e vincoli sono funzioni in Rⁿ (sono vettori) e le variabili possono essere di tipo diverso fra loro (e anche i vincoli)

Appunti Ottimizzazione

Ottimizzare: Trovare la decisione migliore in processi decisionali complessi, o anche trovare il max/min di una funzione (profitto, costo...)

Per rappresentare il fenomeno in esame in maniera selettiva e semplificata, usiamo dei modelli, di cui si usano varie classi-risorse (il livello di astrazione, la natura incognita, la dimensione temporale...)

Sviluppo di un modello:

• Identificare il problema
• Formulare il modello (componenti importanti, orizzonti temporali...) scegliendo le variabili di decisione e l'indicatore di valutazione

Ne immaginiamo una decisione ottimizzante confrontando parametri confrontati che descrivono il problema.

• Risolvere il problema con un algoritmo risolutivo
• Colloquiare l’ipotesi risłt., vedere che sia restata ammissibile, e che succede se cambiano dati (stabilità del risultato)

Componenti di analisi che hai rivisto: spazi vettoriali, vettori, matrici, sottospazi, funzioni, applicazioni lineari, Roche-Capelli, matrice invertic., regola di Cramer e gessi per matrici, topologie

Il problema di ottimizzazione

Elementi principali:

• Min o max (scelta) di una funzione
• Funzione obiettivo f(x): quantifica la qualità della soluzione che voglio Max o Min
• Variabili di decisione: Le x, cosa caratterizza la soluzione, cosa voglio dedentare
• Regione ammissibile K: I vincoli, i limiti delle nostre decisioni, la loro ammissibilità. È spesso descritta con relazioni matematiche che soddisfano un insieme di vincoli: g(x) ≦ b

min (max) f(x)

x ∈ K

NB f(x) e vincoli sono funzioni in IRⁿ (i sono vettori) e le variabili possono essere di tipo diverso tra loro (e anche i vincoli)

Tipi di problemi:

• Lineare: Sì, i vincoli sì e l'obiettivo sono lineari: max (min) Cᵀx = C1x1 + C2x2 + ... Cnxn S.t. Ax ≤ b [A ∊ ℂ matrice (transposta)] [S.t. è per i vincoli, Such That]
• Quadratico: min xᵀQx = Q1nx₁² + ... Qnnxn² S.t. Ax ≤ b
• Non Lineare: DIFFICILE min f(x) s.t. g_j(x) ≤ 0
• Intero: min f(x) s.t. g_j(x) ≤ 0 con x ∊ {0,2}ⁿ o x ∊ ℤⁿ

BREVI PUNTI DI OTTIMIZZAZIONE Prendo ad esempio un problema di minimo: x* è sol. ottima globale se f(x*) ∡ f(x), ∀ x ∊ k e x≠x* mentre è ottima locale se ∃ ε>0, ∀ x, n x* - x n₁ ≤ ε, t.c. f(x*) ∡ f(x) Se x* è min. globale, lo è anche locale, ma il contrario vale solo se f connessa?

INSIEME CONNESSO IFF ∀ x, y ∊ A, ∀ a∊[0,2] → λx + (₋₁)x|y ∊ A segmento tra x e y [disegni di insieme convesso e non convesso] FUNZIONE CONVESSA se tutto ciò che è sopra il grafico di f (EPIGRAFE) è un ins. convesso ∀ x, y ∊ A, ∀ a∊[0,2] → f(λx + (₋λ)y) ≤ λf(x) + (₋λ)f(g) segmento che unisce 2 punti su f

SE f connessa, x* min. locale ⟷ x* min globale QUANDO PARLO DI VALORE DEL PROBLEMA, VAL(P), INTENDO QUANTO VALE L'() OBIETTIVO NEL PUNTO DI OTTIMO

Problemi di ottimi