Miei appunti personali presi con latex di Ricerca operativa

Capitolo 1: Introduzione alla Ricerca Operativa e ai Mod-

elli Matematici

1.1 Cos’è la Ricerca Operativa?

La Ricerca Operativa è l’approccio scientifico alla presa di decisioni. Si occupa di

come prendere decisioni ottimali nell’allocazione e nell’utilizzo di risorse scarse

per raggiungere un determinato obiettivo. La caratteristica distintiva della RO

è l’uso di modelli matematici per rappresentare il sistema reale e di algoritmi

per trovare la soluzione migliore.

1.2 La Metodologia della Ricerca Operativa

Un tipico studio di Ricerca Operativa segue una metodologia strutturata: 1.

Definizione del Problema: Comprendere e definire chiaramente il prob-

lema, gli obiettivi e i vincoli del sistema reale. Questa è la fase più critica.

2. Costruzione del Modello: Tradurre il problema in un modello matem-

atico. Un modello è una rappresentazione semplificata della realtà che cattura

le sue caratteristiche essenziali. 3. Risoluzione del Modello: Utilizzare al-

goritmi e tecniche matematiche per trovare la soluzione ottima del modello. 4.

Validazione del Modello: Verificare che il modello sia una rappresentazione

accurata del sistema reale e che la soluzione ottenuta sia sensata nel contesto

pratico. 5. Implementazione della Soluzione: Tradurre la soluzione matem-

atica in procedure operative e politiche aziendali.

1.3 I Modelli Matematici in RO

Un modello matematico in RO è tipicamente un modello di ottimizzazione,

composto da tre elementi principali: 1. Variabili Decisionali: Sono le incog-

nite del problema, le quantità che devono essere determinate. Rappresentano

1

le decisioni da prendere (es. quanto produrre di un certo bene). 2. Fun-

zione Obiettivo: È un’espressione matematica che lega le variabili decisionali

all’obiettivo che si vuole raggiungere. L’obiettivo è quasi sempre quello di mas-

simizzare (es. il profitto) o minimizzare (es. i costi) questa funzione. 3.

Vincoli: Sono un insieme di equazioni o disequazioni che rappresentano le lim-

itazioni del sistema (es. disponibilità limitata di risorse, domanda di mercato

da soddisfare). I vincoli definiscono la regione ammissibile, ovvero l’insieme

di tutte le possibili soluzioni che rispettano le limitazioni.

Capitolo 2: La Programmazione Lineare: Formulazione dei

Problemi

La Programmazione Lineare (PL) è una delle tecniche più importanti e utilizzate

della Ricerca Operativa. Si applica a problemi di ottimizzazione in cui sia la

funzione obiettivo sia i vincoli sono funzioni lineari delle variabili decisionali.

2.1 Formulazione di un Problema di PL

Formulare un problema di PL significa tradurlo nel linguaggio matematico de-

scritto sopra. Esempio (Problema di Produzione): Un’azienda produce

due prodotti, P1 e P2. * Il profitto unitario è di 3€ per P1 e 5€ for P2. *

La produzione richiede due risorse, R1 e R2. * Per produrre una unità di P1

servono 1 ora di R1 e 2 ore di R2. * Per produrre una unità di P2 servono 1 ora

di R1 e 1 ora di R2. * La disponibilità giornaliera è di 4 ore per R1 e 6 ore per

R2. * Obiettivo: Massimizzare il profitto.

Formulazione Matematica: 1. Variabili Decisionali: * = quantità di

x1

P1 da produrre * = quantità di P2 da produrre 2. Funzione Obiettivo:

x2

* Massimizzare (Profitto totale) 3. Vincoli: *

Z = 3x1 + 5x2 x1 + x2 <=

(Vincolo sulla risorsa R1) * (Vincolo sulla risorsa R2) *

4 2x1 + x2 <= 6 x1

(Vincoli di non-negatività, non si può produrre una quantità

>= 0, x2 >= 0

negativa)

2.2 Forme Standard e Canonica

Un problema di PL può essere scritto in diverse forme equivalenti. * Forma

Canonica (per problemi di massimizzazione): * Funzione obiettivo da

massimizzare. * Tutti i vincoli sono di tipo * Tutte le variabili sono non-

�.

negative. * Forma Standard: * Funzione obiettivo da massimizzare o minimiz-

zare. * Tutti i vincoli sono equazioni (=). * Tutte le variabili sono non-negative.

È sempre possibile passare da una forma all’altra. Per trasformare un vincolo

in un’equazione, si introduce una variabile di slack (o di scarto), che

�

rappresenta la quantità di risorsa non utilizzata. Per trasformare un vincolo �,

si sottrae una variabile di surplus. 2

Capitolo 3: Risoluzione della PL: Metodo Grafico e Algo-

ritmo del Simplesso

3.1 Metodo Grafico

Per problemi di PL con solo due variabili decisionali, è possibile trovare la

soluzione graficamente. 1. Si disegnano gli assi cartesiani (x1, x2). 2. Si disegna

la retta associata a ogni vincolo e si tratteggia la regione ammissibile (l’area del

piano che soddisfa tutti i vincoli simultaneamente). La regione ammissibile

è sempre un poligono convesso. 3. Si disegna una retta di isoprofitto (o

isocosto), che rappresenta tutte le combinazioni di x1 e x2 che danno lo stesso

valore alla funzione obiettivo. 4. Si sposta la retta di isoprofitto parallelamente

a se stessa nella direzione di miglioramento (verso l’alto per massimizzazione)

finché non tocca l’ultimo punto della regione ammissibile. 5. Questo punto è la

soluzione ottima.

Teorema Fondamentale della PL: Se un problema di PL ammette una

soluzione ottima, allora essa si trova in almeno un vertice della regione am-

missibile. Questo teorema è cruciale, perché riduce la ricerca della soluzione da

infiniti punti a un numero finito di vertici.

3.2 L’Algoritmo del Simplesso

Per problemi con più di due variabili, il metodo grafico non è applicabile.

L’algoritmo del simplesso, sviluppato da George Dantzig, è un metodo

algebrico iterativo che esplora i vertici della regione ammissibile in modo

intelligente.

Logica di Base: 1. Inizializzazione: Si parte da un vertice ammissibile

iniziale (solitamente l’origine, se ammissibile). 2. Iterazione: * Test di Otti-

malità: Si verifica se il vertice corrente è ottimo. In un problema di massimiz-

zazione, questo avviene quando non è possibile migliorare la funzione obiettivo

spostandosi verso un vertice adiacente. * Scelta della Variabile Entrante:

Se il vertice non è ottimo, si sceglie la variabile (attualmente non in base, cioè

a valore zero) che, se aumentata, produce il maggior incremento della funzione

obiettivo. * Scelta della Variabile Uscente: Si determina quale variabile

attualmente in base deve diventare zero per mantenere la soluzione ammissi-

bile. Questo definisce lo spostamento al vertice adiacente. 3. Terminazione:

L’algoritmo termina quando viene trovato un vertice ottimo.

L’algoritmo del simplesso è estremamente efficiente in pratica, anche se nel caso

peggiore la sua complessità può essere esponenziale.

3

Capitolo 4: Dualità nella Programmazione Lineare

Ogni problema di Programmazione Lineare, detto problema primale, ha as-

sociato un altro problema di PL, detto problema duale.

4.1 Costruzione del Problema Duale

Esiste una corrispondenza diretta tra gli elementi del primale e del duale: * A

ogni vincolo del primale corrisponde una variabile duale. * A ogni variabile

primale corrisponde un vincolo duale. * Se il primale è di massimizzazione, il

duale è di minimizzazione, e viceversa. * I coefficienti della funzione obiettivo

del primale diventano i termini noti dei vincoli del duale. * I termini noti dei

vincoli del primale diventano i coefficienti della funzione obiettivo del duale.

4.2 Teoremi della Dualità

• Teorema della Dualità Debole: Il valore della funzione obiettivo di

una qualsiasi soluzione ammissibile del primale (di max) è sempre minore

o uguale al valore di una qualsiasi soluzione ammissibile del duale (di min).

• Teorema della Dualità Forte: Se il problema primale ha una soluzione

ottima, allora anche il duale ha una soluzione ottima, e i valori ottimi delle

loro funzioni obiettivo coincidono.

4.3 Interpretazione Economica: i Prezzi Ombra

Le variabili duali hanno un’importante interpretazione economica. Il valore di

una variabile duale associata a un vincolo di risorsa, nella soluzione ottima,

rappresenta il prezzo ombra (shadow price) di quella risorsa.

Il prezzo ombra indica di quanto aumenterebbe il valore della funzione obiettivo

(es. il profitto) se la disponibilità di quella risorsa aumentasse di una unità. È il

“valore marginale” della risorsa e indica il prezzo massimo che l’azienda sarebbe

disposta a pagare per un’unità aggiuntiva di quella risorsa.

Capitolo 5: Ottimizzazione su Grafi: Il Problema del Cam-

mino Minimo

Un grafo G = (V, E) è una struttura matematica composta da un insieme di

vertici (o nodi) V e un insieme di archi (o spigoli) E che collegano coppie di

vertici. I grafi sono modelli eccellenti per rappresentare reti di trasporto, reti di

comunicazione, ecc.

Il problema del cammino minimo (Shortest Path Problem) consiste nel trovare

il percorso di costo (o distanza, o tempo) minimo tra un nodo sorgente e tutti

gli altri nodi del grafo. 4

5.1 Algoritmo di Dijkstra (1959)

L’algoritmo di Dijkstra trova il cammino minimo da un nodo sorgente a tutti

s

gli altri nodi in un grafo con costi degli archi non-negativi.

Logica: * È un algoritmo “greedy”. Ad ogni passo, sceglie il nodo non ancora

visitato che ha la distanza minima dalla sorgente. * Mantiene una stima della

distanza di ogni nodo dalla sorgente, e la aggiorna iterativamente (processo di

“rilassamento”). * Utilizza un insieme di nodi già visitati e ottimizzati. Una

volta che un nodo entra in questo insieme, la sua distanza è considerata defini-

tiva.

5.2 Algoritmo di Bellman-Ford (1958)

L’algoritmo di Bellman-Ford risolve lo stesso problema, ma è più generale perché

funziona anche in presenza di costi degli archi negativi.

Logica: * È un algoritmo più lento di Dijkstra. Si basa su un numero di

iterazioni predefinito. * Esegue |V|-1 iterazioni (dove |V| è il numero di nodi).

In ogni iterazione, “rilassa” tutti gli archi del grafo. * Dopo iterazioni, ha

k

garantitamente trovato i cammini minimi che usano al più archi. * Può anche

k

rilevare la presenza di cicli di costo negativo, ovvero cicli nel grafo la cui

somma dei costi è negativa. Se esiste un tale ciclo raggiungibile dalla sorgente,

il problema del cammino minimo non è ben definito (si potrebbe percorrere il

ciclo all’infinito per ridurre il costo).

Capitolo 6: La Programmazione Dinamica

La Programmazione Dinamica (PD) è una potente tecnica per risolvere problemi

di ottimizzazione che possono essere scomposti in sottoproblemi più piccoli e

sovrapposti.

6.1 Principio di Ottimalità di Bellman