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: Problemi decisionali 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

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

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:

_PL min o max z = c^Tx

a₁^T x ≤ b₁ per i = 1,..., m₁

a_i^T x = b_i per i = m₁+1,..., m₂

x_j ≥ 0 per j = 1,..., m

x_j ≤ 0 per j = m,..., m

dove: min o max indica se

stiamo massimizzando o minimizzando la

z è la funzione obiettivo

x ∈ ℝⁿ è il vettore delle

variabili decisionali

c ∈ ℝⁿ è il vettore dei costi

A ∈ ℝ^m×n è la matrice dei

coefficienti tecnologici

b ∈ ℝ^m è il vettore delle

risorse

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:

nella forma standard, un problema di PL ha le

seguenti caratteristiche:

1) problema di minimo

2) tutti i vincoli sono di PL

3) tutte le variabili sono ≥ 0

_{ min_x z = c^Tx

A x = b

x ≥ 0

con A ∈ ℝ^m×n

x, c ∈ ℝⁿ, b ∈ ℝ^m

Partendo dai concetti della geometria convessa, è possibile, per problemi di due variabili decisionali, risolverli graficamente:

• Gli assi cartesiani rappresentano le due variabili decisionali
• I vincoli sono rappresentati da rette
• La regione ammissibile è il politopo convesso formato dalla parte di piano in cui tutti i vincoli sono rispettati
• si disegna poi il vettore corrispondente ai costi [c]
• Se si vuole massimizzare si segue il vettore c e si disegnano le curve di livello
• se si vuole minimizzare si va in direzione opposta a c e si disegnano le curve di livello
• La soluzione ottima, sta in corrispondenza dell’ultima curva di livello che ha punti nella regione ammissibile
• la soluzione ottima si ottiene se esiste almeno su uno dei vertici

Fase del simplesso

Dobbiamo calcolare una nuova soluzione ammissibile di base a partire da X che abbiamo.

In notazione vettoriale vuol dire che dobbiamo fare la seguente sommatoria: dove dove è il j-ésimo vettore standard. Quindi dobbiamo calcolare j, s e α.

1. Calcoliamo j: poiché sappiamo che deve essere una componente di minore di 0, scegliamo j l’indice di una componente negativa di quindi: poiché siamo sicuri che 0, e poiché vogliamo minimizzare scegliamo α il più grande possibile.
2. Calcoliamo s: la scegliamo tenendo conto dell’ammissibilità. ma noi sappiamo che per definizione è
3. Calcoliamo α:Abbiamo già detto che d deve essere positivo il più grande possibile. Inoltre:

Teoria della dualità

Possiamo associare ad ogni problema un altro problema.

Questi due problemi sono legati da particolari proprietà:

• Il problema "originale" si chiama primale
• Il problema "derivato" si chiama duale

L'obiettivo è dedurre proprietà del primale a partire del duale.

Possiamo dedurre la soluzione ottima del primale partendo dal duale.

Algoritmi:

• Simplex duale (contrapposto al simplesso primale, che abbiamo visto), metodo primale-duale

Definizione di Duale:

_min τ = c^T x Ax = b x ≥ 0 A ∈ R^m×m, x,c ∈ R^m, b ∈ R^m m vincoli, m variabili

⇒ D ^max w = π^T b A^T π = c π ≤ 0 A ∈ R^m×m, c ∈ R^m, π,b ∈ R^m m variabili, m vincoli

Le regole per ottenere il duale a partire dal primale sono:

1. Ad ogni vincolo nel primale corrisponde una variabile nel duale
2. Ad ogni variabile nel primale corrisponde un vincolo nel duale
3. Al vettore risorse nel primale corrisponde il vettore dei costi nel duale
4. Al vettore dei costi nel primale corrisponde il vettore risorse nel duale
5. Se il primale è di minimo, il duale è di massimo

• A vincoli di uguaglianza in P corrispondono variabili libere in segno in D
• A variabili > 0 in P corrispondono vincoli di disuguaglianza in D
1. x ≥ 0 se D di minimo
2. x ≤ 0 se D di massimo

• Algoritmi specifici per i problemi di PLI:
  • Cutting plane
  • Branch e cut (