Quaderno ricerca operativa

RICERCA OPERATIVA

È una disciplina matematica che ha come oggetto la definizione di modelli e la messa a punto di metodi per la soluzione di problemi decisionali che si manifestano in diversi ambienti della vita reale. Nel caso specifico del corso si tratterà essenzialmente di operazioni di ottimizzazione.

FASI DI UN PROCESSO DECISIONALE

Le principali fasi di un processo decisionale sono:

• Analisi del problema
• Costruzione di un modello
• Analisi del modello
• Soluzione numerica
• Validazione del modello

PROBLEMA DI OTTIMIZZAZIONE

DefinizioneConsideriamo una funzione reale f: Rⁿ → R e un insieme S ⊆ Rⁿ, un problema di Ottimizzazione (P) consiste nel determinare, se esiste, un punto di minimo della funzione f tra i punti dell'insieme S, ovvero:

{min   f(x){subject to  x ∈ S

• x ∈ Rⁿ viene chiamato vettore delle variabili di decisione
• f viene chiamata funzione obiettivo
• S viene chiamato insieme ammissibile
• x ∈ S rappresenta una soluzione ammissibile

Un modo analogo per formulare il problema si fonda sulla seguente uguaglianza

min (f(x)) = −max(−f(x))

che indica il fatto che i problemi di massimo e minimo sono equivalenti a meno del segno. Da questa osservazione si può riformulare il problema come segue

{max   −f(x){subject to  x ∈ S

Definizioni fondamentali del problema di ottimizzazioneIl problema di ottimizzazione (P) si dice inammissibile se

S = Ø

cioè se non esistono soluzioni ammissibili.Il problema di ottimizzazione (P) si dice illimitato se

∀M > 0  ∃x ∈ S tale che f(x) < −M

Il problema di ottimizzazione (P) si dice che ammette soluzione ottima se

∃x* ∈ S tale che f(x*) ≤ f(x) ∀x ∈ SIl punto x* è detto soluzione ottimale globale e il corrispondente valore f(x*) si dice valore ottimo.

Classificazione dei problemi di ottimizzazioneSi parla di problemi di ottimizzazione continua quando le variabili possono assumere tutti i valori reali (x ∈ Rⁿ), nel caso S = Rⁿ si parlerà di ottimizzazione non vincolata mentre nel caso S ⊆ Rⁿ si parlerà di ottimizzazione vincolata. Si parla invece di ottimizzazione discreta quando invece le variabili sono vincolate ad essere numeri interi (x ∈ Zⁿ), nello specifico si parla di ottimizzazione a numeri interi se

S ⊆ Zⁿ

RICERCA OPERATIVA

È una disciplina matematica che ha come oggetto la definizione di modelli e la messa a punto di metodi per la soluzione di problemi decisionali che si manifestano in diversi ambienti della vita reale. Nel caso specifico del corso si tratterà essenzialmente di operazioni di ottimizzazione.

FASI DI UN PROCESSO DECISIONALE

Le principali fasi di un processo decisionale sono:

• Analisi del problema
• Costruzione di un modello
• Analisi del modello
• Soluzione numerica
• Validazione del modello

PROBLEMA DI OTTIMIZZAZIONE

DefinizioneConsideriamo una funzione reale f: ℝⁿ → ℝ e un insieme S ⊆ ℝⁿ, un problema di Ottimizzazione (P) consiste nel determinare, se esiste, un punto di minimo della funzione f tra i punti dell’insieme S, ovvero:

{min f(x){subject to x ∈ S

• x ∈ ℝⁿ viene chiamato vettore delle variabili di decisione
• f viene chiamata funzione obiettivo
• S viene chiamato insieme ammissibile
• x ∈ S rappresenta una soluzione ammissibile

Un modo analogo per formulare il problema si fonda sulla seguente uguaglianza

min (f(x)) = −max(−f(x))

che indica il fatto che i problemi di massimo e minimo sono equivalenti a meno del segno.Da questa osservazione si può riformulare il problema come segue

{max −f(x){ subject to x ∈ S

Definizioni fondamentali del problema di ottimizzazione

Il problema di ottimizzazione (P) si dice inammissibile se

S = ∅

cioè se non esistono soluzioni ammissibili.Il problema di ottimizzazione (P) si dice illimitato se

∀M > 0 ∃x ∈ S tale che f(x) < −M

Il problema di ottimizzazione (P) si dice che ammette soluzione ottima se

∃x^* ∈ S tale che f(x^*) ≤ f(x) ∀x ∈ S

Il punto x^* è detto soluzione ottimale globale e il corrispondente valore f(x^*) si dice valore ottimo.