Appunti completi corso Ricerca operativa

Prima lezione di ricerca operativa

Che cos’è però? È una branca della matematica che supporta la presa di decisioni attraverso modelli matematici che descrivono e modellano un problema e da quel modello si trovano algoritmi efficienti e ottimizzati per risolverlo. Abbiamo fatto un bell’esperimento con i telefoni. Alla fine i dati che ci interessano per definire un problema sono tre:

• Decisione: un insieme di variabili matematiche che rappresentano la soluzione al problema (quanti telefoni costruire dei due tipi)
• Regole: i vincoli che abbiamo per cercare la soluzione (il numero di pezzi a disposizione)
• Obiettivo: lo scopo, il valore che vogliamo massimizzare (i guadagni)

Tutto quanto ha una descrizione matematica! Noi nel nostro esperimento abbiamo fatto un bruteforce perché è l’unica cosa che sappiamo fare finora… Ma impareremo modi efficienti per modellare i problemi matematicamente e dimostrare perché una soluzione è corretta. Siccome abbiamo solo due variabili (il numero di pezzi per due telefoni) possiamo descrivere il numero di pezzi da utilizzare in funzione del numero di telefoni che vogliamo costruire.

Ogni pezzo diventa un vincolo e siccome le variabili sono due possiamo rappresentare i vincoli graficamente come rette! Le soluzioni possibili sono quelle che soddisfano tutti i vincoli, ovvero l’area sottesa da tutte le rette. L’area ottenuta è un insieme, ci sono infinite soluzioni possibili al suo interno, ma ovviamente solo alcune hanno senso (quelle che corrispondono a numeri interi). Per ognuna di queste soluzioni abbiamo un guadagno, e ci interessa il punto che massimizza quel guadagno.

Importanza della ricerca operativa

La ricerca operativa è importantissima… Il prof mostra l’esempio dell’ATM milanese. I servizi sono efficienti e fanno uso della RO per definire gli orari dei mezzi e degli autisti. Quando invece la RO non viene usata succede come quella volta che Trenord ha aggiornato il software che ha causato un macello. Domani faremo Pokemon Go.

La figata della RO è che si usa in ambiti completamente diversi tra loro, eppure mica devi essere un tuttologo. In ogni problema devi cogliere le variabili, i problemi matematici. Quello è uguale qualunque cosa fai: che sia lo scheduling di voli aerei o giocare a Pokémon Go senza essere un aerospaziale o un nerd.

Modellazione e variabili

Purtroppo mi sono perso il gioco di Pokémon Go, vabbè. L’importante è essere al passo con la teoria. Oggi non dobbiamo risolvere il problema, ma dobbiamo modellarlo. Capire quali sono le variabili, le funzioni e tutte le cosette matematiche per modellare il problema e poi risolverlo.

• Le decisioni: quali sono le variabili da trovare
• Le regole: i vincoli che abbiamo, come insiemi di equazioni e disequazioni
• L’obiettivo: la funzione che dobbiamo massimizzare o minimizzare

Noi avevamo fatto il problema dei telefoni, per esempio x_A e x_B sono i telefoni di tipo A e B che dobbiamo costruire. Sono la decisione, con il vincolo che devono essere valori positivi. Ovviamente vale in questo contesto, in altri possono essere libere in segno (per esempio una temperatura), oppure possono avere un significato non assoluto.

Un caso può essere quello in cui abbiamo già pronto un orario dei mezzi di trasporto e vogliamo modificarlo anticipando o ritardando le corse: la differenza tra l’orario vecchio e l’orario nuovo è una variabile e come tale può essere positiva o negativa (in base al fatto che sia un anticipo o un ritardo). È possibile trasformare una variabile libera in positiva in modo molto semplice: da una variabile libera x ne crei due x₊ e x_- entrambe positive e di esse fai la differenza.

Esempio di investimento

Esempio su un investimento di fondi (lo trovi sulle slide): hai una quantità di soldi, puoi comprare un certo numero di strumenti finanziari (espressi in migliaia di euro) e se prendi per intero uno strumento guadagni alla fine dell’anno il valore in coupon (sempre in migliaia di euro). Dobbiamo decidere quanto investire in ogni strumento per massimizzare il guadagno a fine anno.

• La decisione è quanti soldi investire in ognuno degli strumenti: x₁, x₂, x₃, x₄, x₅ con i vincoli che queste variabili sono non negative e la loro somma è minore o uguale a 137.
• I vincoli sono il massimo che puoi comprare di ogni strumento, quindi x₁ ≤ 40, x₂ ≤ 12, x₃ ≤ 130 e così via
• L’obiettivo è massimizzare il guadagno finale, che è proporzionale all’investimento. Quindi max(x₁*3,2/40 + x₂*1,5/12 + x₃*4,2/130 ...)

Il prof fa la furbata che le variabili non rappresentano i valori assoluti di quanto acquistare, ma sono dei valori compresi tra 0 a 1, che indicano la porzione di quanto compri di ogni strumento. In questo modo naturalmente devi cambiare le formule sopra.

• La decisione ha cinque valori compresi tra 0 e 1 da identificare.
• Il vincolo è che x₁*40 + x₂*12 + x₃*130 … sia minore di 137.
• La funzione obiettivo diventa max(x₁*3,2*40 + x₂*1,5*12 + x₃*4,2*130 …)

Comunque questo problema da risolvere è una cazzata perché è il problema dello zaino reale: basta guardare il “guadagno specifico” e prendi sempre quello migliore in modo greedy. Infatti viene fuori di prendere tutto il quarto, tutto il secondo, tutto il primo e 80 del quinto e come guadagno viene fuori 8,8.

Problemi dello zaino

Il problema si complica con lo zaino discreto: o prendi tutto o niente, e lì come si fa? La tecnica greedy non è ottimale. La modellazione comunque è uguale a quella del problema precedente, ma aggiungiamo che la decisione non è formata da variabili reali bensì intere (possono assumere solo i valori 0 e 1). In questo caso le variabili sono binarie, visto che non possono assumere qualsiasi valore intero ma solo un suo sottoinsieme. Questo tipo di variabili è anche detto logico. La grande differenza tra i due problemi è che nello zaino reale le soluzioni sono infinite, qui invece sono un insieme finito (al massimo sono 2⁶, poi di queste molte le butti via ma sono comunque finite). Eppure lo zaino discreto è un problema non banale, infatti è NP-completo… Come vedremo nel resto del corso, risolvere problemi con vincoli di interezza è più difficile rispetto ai problemi in cui le variabili sono continue.

Un altro tipo di variabile è quando rappresenta il valore appartenente ad un insieme (quindi non ad un insieme numerico infinito o un intervallo). Matematicamente non scriviamo che la variabile appartiene all’insieme: creiamo una variabile logica per ogni elemento dell’insieme e diciamo che la variabile è una combinazione lineare tra i valori dell’insieme e le variabili booleane, specificando che di queste ultime una sola è vera e le altre sono false. Questo è un ulteriore vincolo che va specificato (lo si fa indicando che la somma di queste variabili logiche è uguale a 1).

Le variabili possono essere “trasformate” e questo sarà molto utile. Un tipo di trasformazione l’abbiamo vista ed è quella per passare da una variabile libera in segno ad una coppia di variabili solo positive. Ma la trasformazione più banale è quella per cambiare segno: se hai una variabile x vincolata in un segno (positivo o negativo) ne crei una del tipo x’ = -x e la sostituisci in tutto il modello. Anche per quanto riguarda le variabili logiche, se serve avere il complementare di x basta introdurre una nuova variabile x’ = 1 - x.

Vincoli e risorse

I vincoli possono indicare le risorse a disposizione (quindi sono in minore o uguale) oppure indicare un fabbisogno minimo (quindi sono in maggiore o uguale). Naturalmente per passare da un tipo di disequazione all’altro basta solo moltiplicare tutto per -1. Ma per passare da una disequazione ad una equazione si introduce una variabile detta di slack, che indica la quantità in eccesso o in difetto rispetto al termine noto della disequazione. Questa variabile è positiva, quindi viene aggiunta nei vincoli di risorse (indica quante risorse avanzano) e sottratta nei vincoli di fabbisogno (indica quanto vale l’eccesso).

Un altro possibile vincolo è quello di blending, cioè quando bisogna decidere le quantità di materiale per creare un prodotto e ogni materiale deve comparire per almeno una certa percentuale. In questo caso il vincolo è espresso come la variabile fratto la somma delle variabili: questa formula non è lineare, ma siccome il denominatore è sicuramente positivo si può moltiplicare per esso a destra e a sinistra della disequazione ed ottenere un vincolo lineare.

I vincoli di esclusione con variabili logiche sono facili da creare: basta imporre che la loro somma sia uguale a 1. Se l’esclusione va imposta invece su variabili non logiche x, bisogna comunque aggiungere delle variabili logiche y tali per cui y = 1 implica che x va preso in considerazione. Poi si usa questa variabile logica nei vincoli del tipo x ≤ M * y. In questo modo se y vale 0, anche x varrà zero, mentre se y vale 1 allora x può assumere qualsiasi valore tra 0 e M.

Problemi lineari

Diciamo che un problema è lineare se sono lineari le equazioni della funzione obiettivo e dei vincoli. Nel caso precedente abbiamo una frazione tra espressioni lineari: moltiplicando a destra e sinistra col denominatore viene un’espressione lineare (che si risolve in modo efficiente). Usando variabili binarie, possiamo usare espressioni logiche del prim’ordine come vincoli, per esempio x₁ → x₂. Oppure in maniera decisamente matematica puoi dire che la somma di due variabili deve essere minore, uguale o maggiore a 1 per modellare l’and, l’or ecc...

• x₁ and x₂ → x₁ + x₂ = 2
• x₁ or x₂ → x₁ + x₂ ≥ 1
• x₁ xor x₂ → x₁ + x₂ = 1
• x₁ implica x₂ → x₁ ≤ x₂
• x₁ implica not x₂ → x₁ + x₂ ≤ 1

Useremo spesso la forma normale congiuntiva, cioè la seconda forma canonica, quella che usavi in logica e algebra, dove ci sono le clausole (unite in or) collegate tra loro in and. Per trasformare un SAT in matematica devi seguire le trasformazioni elencate prima. Ogni letterale positivo è una x, ogni letterale negativo è un (1 - x). All’interno delle clausole traduci l’or con un’addizione, e ogni clausola è un vincolo, cioè la somma dei letterali deve essere maggiore o uguale a 1. Rivelazione: QUALSIASI problema, anche quelli che non sono stati inventati, può essere trasformato in forma normale congiuntiva. Questo vuol dire che se sai risolvere il SAT in modo efficiente, puoi risolvere qualsiasi problema in modo efficiente!

Convertire le frasi logiche in matematiche non è sempre così semplice. Se vuoi dire che se c’è pasta allora non c’è riso, devi pensarci. La soluzione più semplice (e corretta) è che il prodotto pasta*riso sia uguale a zero. Però non è lineare… sono due variabili moltiplicate tra loro. Il trucco è creare due variabili logiche: una che dice pasta positiva e l’altra che dice riso positivo. Poi dici che la somma di queste variabili logiche deve essere uguale a uno.

Problemi di flusso

Un altro tipo di problema è quello del flusso: abbiamo dei pozzi di petrolio da trasportare nelle raffinerie. I pozzi forniscono una certa quantità che è richiesta dalle raffinerie. Dobbiamo decidere in quali tubi trasportare il petrolio e in quali quantità. Vediamo come modellare con un grafo di mezzo. Creiamo una variabile per ogni arco che chiameremo x_ij con i e j gli indici dei nodi. Naturalmente sono variabili non negative. Come vincoli dobbiamo specificare che dai pozzi possiamo estrarre una quantità massima. Direi che la somma degli archi uscenti dal pozzo è minore o uguale alla quantità disponibile. Nel caso del secondo pozzo togliamo però la quantità dell’arco entrante, perché quello contiene il petrolio proveniente dal primo pozzo. Il ragionamento è analogo per le raffinerie. Aggiungerei però un vincolo anche sulla pompa: quello che entra deve essere uguale a quello che esce!

Funzione obiettivo e problemi bottleneck

Vediamo anche dei casi particolari di funzione obiettivo. I casi più frequenti sono massimizzare o minimizzare un valore. Come passiamo da un min ad un max e viceversa? In un modo banalissimo… cercare max(x) è uguale a cercare min(-x). Basta cambiare segno.

Un caso particolare è quello dei problemi bottleneck, ovvero in cui vogliamo massimizzare un minimo o minimizzare un massimo. Traducendo un problema letteralmente avremmo che la funzione obiettivo è del tipo min(max(x)) che non è lineare. Si risolve creando una variabile d e la funzione obiettivo è min(d). Naturalmente bisogna legare d alle altre variabili del problema, e lo si fa con una serie di vincoli in cui d ≥ x (dove x rappresenta tutte le variabili delle quali minimizziamo il massimo). Siccome l’obiettivo è minimizzare d, avremo che d sarà identico al massimo delle x.

Spesso capita anche di avere più funzioni obiettivo che sono magari in contrasto fra loro: come si modellano in una unica funzione? Ci sono due approcci: uno è quello di inserire entrambe le funzioni in un unico obiettivo e una delle due è moltiplicata per una costante k. Le due funzioni saranno una positiva e una negativa (perché si contrastano) mentre il valore della costante deve essere scelto appositamente per trovare un buon trade-off. L’altro approccio è quello di scegliere una sola alternativa come funzione obiettivo, mentre l’altra diventa un vincolo sul valore minimo o sul valore massimo che deve assumere.

Grafi

Oggi si inizia a parlare di un argomento figo quanto importante: i grafi. L’esempio più semplice e chiaro è quando dobbiamo andare da un punto all’altro della città: i nodi sono le intersezioni o i punti che possiamo raggiungere e ogni arco ha un peso che rappresenta la durata di percorrenza da un punto all’altro. Dobbiamo decidere il percorso più breve per raggiungere la destinazione. Ma con i grafi si possono modellare una quantità enorme di problemi, anche se all’inizio non ci penseresti.

Comunque sai che i grafi hanno nodi e archi, che sono coppie di nodi. Questi archi possono essere orientati oppure non orientati.

Definizioni di percorsi e cicli

Definiamo i percorsi in questo modo:

• Percorso: una qualsiasi sequenza di archi e nodi adiacenti
• Percorso semplice: percorso in cui non si ripete nessun arco
• Percorso elementare: percorso in cui non si ripete nessun nodo

È importante il concetto di ciclo:

• Ciclo: percorso chiuso (il primo e l’ultimo nodo coincidono)
• Ciclo elementare: non ci sono nodi ripetuti (esclusi gli estremi)
• Ciclo hamiltoniano: tutti i nodi del grafo sono raggiunti, ha esattamente |N| archi
• Ciclo semplice: non si ripete nessun arco
• Tour euleriano: tutti gli archi del grafo sono attraversati, ha esattamente |A| archi

Il problema del tour Euleriano è quello che ha dato il via alla teoria dei grafi: conosci il noto problema dei ponti di Königsberg (Kaliningrad). Si chiede se quel grafo sostanzialmente è euleriano (la risposta è no).

Formalizzazione matematica dei grafi

Ora dobbiamo formalizzare matematicamente com’è fatto un grafo. È definito come G = {N, A} dove N è un insieme di nodi e A un insieme di archi (coppie di nodi). Naturalmente esistono grafi diretti e indiretti: in quest’ultimo caso per ogni arco (i, j) esiste anche (j, i).

Nei computer i grafi si possono rappresentare con la matrice di adiacenza che conosci bene perché la usi sempre anche se è un po’ inefficiente in quanto a spazio. L’altro metodo è la lista di adiacenza che è più efficiente e le librerie usano questo metodo (una libreria C++ per i grafi è boost). Non mi è ben chiaro però come è stata implementata questa lista sulle slide, mh… Comunque si può implementare in tanti modi, uno di questi è creare una mappa del tipo Node -> [(Node, Weight)] (per cui non esiste l’oggetto che rappresenta gli archi).

Esiste una terza rappresentazione che è strettamente matematica: è una matrice che ha una riga per ogni nodo e una colonna per ogni arco. Ogni cella della matrice contiene -1 se il nodo è quello di provenienza dell’arco e 1 se è quello di arrivo, altrimenti 0 (naturalmente nei grafi indiretti non esistono valori negativi). Di fatto quella è la matrice dei coefficienti che usi nella formulazione dei vincoli!

Algoritmo di Kruskal

Ora passiamo ad un problema concreto… [giocando con un grafo] ...e arriva l’algoritmo di Kruskal per calcolare il minimum spanning tree, ovvero un sottoinsieme di archi a peso minimo che connette tutti i nodi del grafo! Questa è la formalizzazione del problema.

Dati:

• Un grafo G = {N, A} con archi pesati w_ij ≥ 0, ∀(i, j) ∈ A

Trova un sottografo G’ = {N, A’} con A’ ⊆ A tale da avere min(∑w_ij(A’)).

L’albero di ricoprimento minimo ha queste proprietà:

• Non ci sono cicli (altrimenti non è un albero e non è minimo)
• È connesso (da un qualsiasi nodo puoi raggiungere tutti gli altri)
• Se i nodi sono n, gli archi sono n-1
• Se aggiungiamo un arco al MST otteniamo un ciclo

Scriviamo il problema in termini prettamente matematici. Siccome dobbiamo scegliere degli archi, la soluzione al problema è un assegnamento a delle variabili logiche x_ij che dicono se l’arco (i, j) appartiene al MST che vogliamo costruire. Esplicitiamo questo scrivendo x_ij ∈ {0, 1} ∀(i, j) ∈ A

La funzione obiettivo quindi diventa trovare il min(∑(w_ij x_ij)).

La parte difficile è dire che il grafo deve essere connesso e si usa una tecnica particolare. Dire che un grafo è connesso significa dire che per ogni sottoinsieme non...