Appunti di Ricerca operativa

Ricerca operativa

Definizione

La ricerca operativa si occupa di risolvere problemi decisionali.

Problemi decisionali: Problemi in cui uno o più decisori devono effettuare delle scelte tra uno o più obiettivi.

Problemi di ottimizzazione: Problema decisionale in cui si vuole massimizzare o minimizzare qualcosa.

Noi ci occupiamo di problemi di ottimizzazione con un solo decisore e un solo obiettivo.

Risoluzione di un problema di ottimizzazione

• Studio del problema reale
• Costruire un modello matematico che lo rappresenta
• Risoluzione del modello matematico con un algoritmo
• Testing (noi non lo consideriamo per l'esame)

Costruzione di un modello matematico

• Individuare le incognite del problema, che prendono il nome di variabili decisionali
• Costruzione della funzione obiettivo che rappresenta l'obiettivo del problema
• Definizione di eventuali vincoli, che rappresentano diverse alternative possibili

Ricerca operativa

Definizione

La ricerca operativa si occupa di risolvere problemi decisionali.

Problemi decisionali: Problemi in cui uno o più decisori devono effettuare delle scelte tra uno o più obiettivi.

Problemi di ottimizzazione: Problema decisionale in cui si vuole massimizzare o minimizzare qualcosa.

Noi ci occupiamo di problemi di ottimizzazione con un solo decisore e un solo obiettivo.

Risoluzione di un problema di ottimizzazione

• Studio del problema reale
• Costruire un modello matematico che lo rappresenta
• Risoluzione del modello matematico con un algoritmo
• Testing [noi non lo consideriamo per l'esame]

Costruzione di un modello matematico

• Individuare le incognite del problema, che prendono il nome di variabili decisionali
• Costruzione della funzione obiettivo che rappresenta l’obiettivo del problema
• Definizione di eventuali vincoli, che rappresentano diverse alternative possibili

Problema di programmazione lineare

Un problema, in cui compaiono solo funzioni lineari si chiama problema di ottimizzazione lineare o problema di programmazione lineare (PL).

Possiamo generalizzare un problema di PL nella seguente forma:

min (o max) Z = c^Tx ⎧ a₁^T x ≥ b_i per i = 1,..., m

PL ⎨ aㆍx ≤ b_i per i = m, m+1,...,m ⎩ x_j ≤ 0 per j = m+1,...m

Inoltre x_j ≥ 0 per j = 1,... m indica le variabili vincolate in segno mentre x_j ≤ 0 per j = m,...m indica le variabili libere in segno.

Ci sono anche casi in cui le variabili sono intere o sono booleane (ovvero x_i ∈ {0,1} i = 1...m).

Forma standard di un problema di PL

Forma standard di un problema di PL: nella forma standard, un problema di PL ha le seguenti caratteristiche:

• Problema di minimo
• Tutti i vincoli sono di uguaglianza
• Tutte le variabili sono ≥ 0

⎧ min Z = c^T x

PL ⎨ ⎩ A x = b x ≥ 0 ⎧ m×n

Con A ∈ ℝ ⎪ ⎪ c ∈ ℝⁿ ⎨ ⎪ b ∈ ℝ^m ⎩ x,c ∈ ℝⁿ, b ∈ ℝ^m

Nota: Tutti i problemi di PL si possono trasformare in problemi in forma standard.

Come? Operando 4 accorgimenti:

• Se è un problema di massimo, si scrive come min_x z=-c^Tx e poi, una volta risolto, il problema si può trovare la soluzione ottima è facendo -z^* scritta in forma standard
• Se sono presenti vincoli di ≥, si riscrivono come vincoli di uguaglianza dove al primo membro si sottrae una variabile di surplus, che è ≥ 0
• Se sono presenti vincoli di ≤, si riscrivono come vincoli di uguaglianza dove al primo membro si aggiunge una variabile di Slack, che è ≥ 0
• Se sono presenti variabili libere in segno si riscrivono come x_i = x_i⁺ - x_i^- con x_i⁺ e x_i^- ≥ 0 e ne, sostituiscono in tutto il modello.

Soluzione ammissibile

Def. soluzione [o punto] ammissibile:

Un punto — x ∈ ℝ^m è una soluzione ammissibile per PL se A— x = b e — x ≥ 0, ovvero se soddisfa vincoli.

Regione ammissibile

Def. regione ammissibile:

La regione ammissibile X per un problema PL è l'insieme di tutti i punti ammissibili — x:

X = {— x ∈ ℝ^m | A— x = b e — x ≥ 0}

Problema ammissibile

Def. problema ammissibile:

Un problema di PL è ammissibile se esiste almeno un punto ammissibile, ovvero se X ≠ ∅

Problema inammissibile

Def. problema inammissibile

Un problema di PL è inammissibile se non esiste nessun pu