Appunti Ricerca operativa

SISTEMI OPERATIVI

La RICERCA OPERATIVA studia i sistemi complessi: utilizza un approccio scientifico che comprende passi fondamentali:

• prima comprensione del sistema da trattare
• formulazione del problema, descrivendo il sistema in termini matematici

MODELLO MATEMATICO = astrazione matematica che descrive il sistema attraverso relazioni matematiche. Ci possono essere diversi modelli matematici per descrivere lo stesso sistema. Bisogna cercare un compromesso tra accuratezza del modello e la possibilità di risolverlo matematicamente.

• Soluzione del modello matematico e verifica di esso tramite analisi speri-mentale.
• eventuali modifiche al modello
• Per un modello di OTTIMIZZAZIONE bisogna identificare:

• VARIABILI → grandezze controllabili da noi (non confondere con i parametri: dati del problema)
• VINCOLI → legami esistenti tra le variabili nel sistema reale
• FUNZIONE OBIETTIVO → criterio di valutazione di una soluzione

PROBLEMI DI OTTIMIZZAZIONE

È una coppia ⟨X,f⟩ dove:

• X ⊂ R^m è un insieme (regione ammissibile)
• f: X → R è una funzione (funzione obiettivo)
• m = numero di variabili (= n° di decisioni da fare)

Non posso prendere tutte le coppie!! Risolvere il problema = determinare un punto (valore della funzione obiettivo) nel quale la funzione assume il valo- re minimale, ossia determinare X^* = arg min{f(x); x ∈ X} Una soluzione è un vettore x = {x₁, x₂, ..., x_m} ∈ R^m → è ammissibile se e solo se x ∈ X

• Nel caso di un problema in cui la funzione obiettivo deve essere

SISTEMI OPERATIVI

La RICERCA OPERATIVA studia i sistemi complessi: utilizza un approccio scientifico che comprende passi fondamentali:

• prima comprensione del sistema da trattare
• formulazione del problema, descrivendo il sistema in termini matematici

MODELLO MATEMATICO = astrazione matematica che descrive il sistema attraverso relazioni matematiche. Ci possono essere diversi modelli matematici per descrivere lo stesso sistema. Bisogna cercare un compromesso tra la accuratezza del modello e la possibilità di risolverlo matematicamente.

• Soluzione del modello matematico e verifica di esso tramite analisi sperimentale.
• Eventuali modifiche al modello
• Per un modello di OTTIMIZZAZIONE bisogna identificarne:
  • VARIABILI → grandezze controllabili da noi (non confondere con i parametri: dati del problema)
  • VINCOLI → legami esistenti tra le variabili nel sistema reale
  • FUNZIONE OBIETTIVO → criterio di valutazione di una soluzione

PROBLEMI DI OTTIMIZZAZIONE

È una coppia (X,f) dove:

• X ⊂ R^m è un insieme (regione ammissibile)
• f: X → R è una funzione (funzione obiettivo)
• m = numero di variabili (= n^o di decisioni da fare)

Non posso prendere tutte le coppie!! Risolvere il problema = determinare un punto (soluzione obiettivo) nel quale la funzione assume il valore minimo, ossia determinare X* = arg min{f(x), x ∈ X} X* ∈ XUna soluzione è un vettore x = (x₁, x₂, ..., x_m) ∈ R^m → è ammissibile se e solo se x ∈ X

• Nel caso di un problema in cui la funzione obiettivo deve essere

massimizzata, si usa questa trasformazione:

max {f(x): x ∈ X} => − min {− f(x); x ∈ X}

SOLUZIONE DI UN MODELLO

Risolvere un modello: determinare un vettore x* ∈ X tale che

f(x*) ≤ f(x) ∀x ∈ X => x* è un OTTIMO GLOBALE

 Un problema di ottimizzazione può avere più di una soluzione ottima

⊗ OTTIMO LOCALE: un vettore x* ∈ X tale che

 f(x*) ≤ f(x) ∀x ∈ X with ||x*-y|| ≤ ρ  (raggio della palla; per qualsiasi ρ>0 è arbitrario)

2 CASI PARTICOLARI:

• X = ∅  → nessuna soluzione ammissibile ⇒ il problema è impossibile e si pone min {f(x); x ∈ X} = ∞
• X è illimitato inferiormente sull'insieme X ⇒ il problema è illimitato (non esiste un valore che minimizza la funzione obiettivo: trova sempre un valore migliore) e si pone min {f(x); x ∈ X} = - ∞

CLASSIFICAZIONE DEI MODELLI

- PROGRAMMAZIONE NON LINEARE (NLP) → nessuna restrizione sulla forma di f e g

• classe