Appunti di Ricerca operativa

Prima lezione: introduzione alla ricerca operativa

Ricerca Operativa sta ad indicare ricerca sulle operazioni che inizialmente erano operazioni militari, in quanto nasce negli anni subito dopo la 2^a guerra mondiale. Nasce in quel periodo per due motivi:

• I fondi della ricerca erano disponibili solo per ricerca militare;
• Negli anni '30 nasce sostanzialmente l'informatica.

La prima applicazione della R.O. si fa risalire alla fine degli anni '30 quando l'Inghilterra creò un sistema radar per controllare il mare del nord. Quello che si scoprì in questo periodo fu sostanzialmente che questi radar dal punto di vista tecnologico funzionavano bene, ma quello che era complicato era come utilizzare al meglio le informazioni che questi radar restituivano (come far arrivare l’aereo nel punto nel minor tempo possibile). Cioè mancava un approccio operativo che riuscisse ad utilizzare al meglio le informazioni. Venne creato perciò un OR team ovvero un gruppo di scienziati che definivano dei metodi quantitativi che permettessero di utilizzare al meglio le informazioni. Visto il successo poi, furono utilizzati circa 700 scienziati.

In generale, abbiamo sempre un numero di risorse limitate e dobbiamo decidere come utilizzarle per raggiungere al meglio determinati obiettivi.

• Esempi di ambiti dove può essere utilizzata la R.O.: pianificazione della produzione, progettazione di reti, allocazione di componenti elettronici, problemi economici e finanziari.

Definizione di ricerca operativa

Cominciamo con la definizione di R.O.: la ricerca operativa si occupa di problemi decisionali. Un problema decisionale si definisce "problema in cui uno o più decisori devono effettuare delle scelte tra diverse alternative possibili tenendo conto di determinati obiettivi". Dobbiamo tener conto ovviamente dei vincoli dei problemi che tipicamente sono le risorse utilizzabili in quantità limitata. Nella valutazione della scelta/decisione, quest’ultime devono essere valutate in base ad uno o più obiettivi.

Esempio di problema decisionale

Se questa è la definizione di un problema di decisione, facciamo un esempio: supponiamo di dover gestire un’organizzazione: 70 lavori e 70 lavoratori. L’ipotesi che facciamo è che ogni lavoratore può eseguire qualsiasi menzione e le esegue con un costo diverso (è più bravo per alcune menzioni allora costo più basso, meno bravo allora costo più elevato). Vogliamo assegnare una menzione a ciascun lavoratore. Il costo totale deve essere il più basso possibile.

Dal punto di vista matematico questo problema è banale perché un algoritmo in grado di risolvere questo problema lo posso descrivere utilizzando la forza bruta, cioè mi accorgo che l’insieme di tutte le decisioni possibili è un insieme finito perché non devo far altro che scegliere una permutazione delle 70 menzione sulle 70 persone e l’insieme di tutte le permutazioni è 70! (fattoriale). 70! è un numero grandissimo ma finito, quindi posso pensare ad un algoritmo che va ad elencare tutte le possibili soluzioni e per ciascuna soluzione valuta il costo (Cij) e alla fine sceglie la permutazione con costo più basso. Questo algoritmo prima o poi termina e risolve il mio problema di decisione.

Dal punto di vista formale questo algoritmo è corretto ma 70! è grandissimo, quindi se io ho una macchina che è in grado di ispezionare meno soluzioni al secondo, avrò bisogno di un’infinità di tempo. Tutto questo tempo non è dovuto al fatto che la macchina usata è scadente, non guadagno parecchio anche se utilizzo più calcolatori in parallelo alla stessa potenza.

Tutto questo per dire che questo problema di decisione è facile dal punto di vista matematico, ma per poterli risolvere in maniera pratica abbiamo bisogno di algoritmi che trovino la soluzione ottimale senza dover confrontare tutte le possibili soluzioni e farlo anche in tempi ragionevoli.

Classificazione dei problemi decisionali

Abbiamo già detto che un problema di decisione è dato da uno o più decisori che devono prendere decisioni sulla base di uno o più obiettivi posti: possiamo allora classificare i problemi in base al numero di decisori, il numero di obiettivi e il grado di incertezza dei dati di input.

Se guardo il numero dei decisori ho un unico decisore, oppure più decisori che devono prendere delle decisioni che però non sono indipendenti tra loro (la scelta di uno può influenzare la scelta di un altro).

Noi tratteremo solo i problemi di ottimizzazione. Per dare un’idea di cosa si intende per teoria dei giochi, facciamo un esempio: "il dilemma dei due prigionieri". Questi due decisori (le due persone accusate), devono prendere indipendentemente l’uno dall’altro una decisione in base a quello che gli conviene. Le regole le possiamo sintetizzare in una matrice [(-3,-3)(0,-6);(-6,0)(-1,-1)].

Se il problema fosse un problema di ottimizzazione, quindi se avessimo un unico decisore che consiglia ad entrambi di non confessare i due fanno la quantità minima di anni di carcere. Ma noi abbiamo due decisori, e la scelta dell’uno influenza la qualità della scelta dell’altro.

La soluzione migliore non è -1,-1 perché ognuno deve fare la sua decisione senza sapere cosa ha fatto l’altro: se il primo decide di non confessare se poi esce e si accorge che l’altro non ha confessato, è contento perché ha fatto la scelta migliore; ma se decide di non confessare e l’altro confessa si pentirà della sua scelta. La cosa migliore invece è fare una scelta in modo tale che quando viene a sapere cosa ha fatto l’altro non si pente in ogni caso. La scelta che non lo farà mai pentire è quella di confessare.

Il punto ottimo quindi è -3,-3 (punto di equilibrio) -> ognuno ha preso la decisione che non lo farà mai pentire nel momento in cui verrà a conoscenza della decisione dell’altro.

Nei problemi che tratteremo al corso siamo proiettati a trovare la soluzione migliore. Anche i problemi di ottimizzazione li possiamo caratterizzare in base al 2 grado di libertà (numero di obiettivi). Anche qui tratteremo solo problemi di ottimizzazione monobiettivo.

Diamo comunque un’idea di un problema di ottimizzazione multi-obiettivo: quello che di solito accade è che soluzioni di buona qualità per un obiettivo sono di scarsa qualità per un altro obiettivo.

Immaginiamo di dover organizzare a programmazione della produzione di una determinata azienda. Si può pensare di minimizzare il numero di clienti insoddisfatti, oppure quello di minimizzare i costi complessivi di produzione. Questi due obiettivi sono in contrasto tra loro. Tutte le possibili scelte sono rappresentate da uno dei punti sul diagramma. Alcuni di questi punti hanno un’etichetta: A, B, C. Ciascuna di queste soluzioni è caratterizzata da un certo valore di F1 e di F2.

Tra A e C, A è migliore di C. Il problema è che se ora confronto C e B, esse non sono confrontabili perché dal punto di F1 C è migliore di B, dal punto di vista di F2 B è migliore di C. Tuttavia la soluzione individuata da B non è dominata da nessun'altra soluzione.

Quello che si fa nella realtà per semplificarsi la vita e lo faremo anche noi, nel momento in cui si ha a che fare con un tale problema, si cerca di trasformarlo in maniera grezza in un problema di ottimizzazione monobiettivo o costruendo una funzione monobiettivo che è combinazione lineare di F1 e F2 (magari con un coefficiente di priorità tra F1 e F2), oppure scegliere una sola funzione tra le due e scelgo l’altra come vincolo di budget. Ovviamente non sempre è possibile fare ciò e quindi ci saranno altre tecniche che noi non faremo.

Problemi di programmazione matematica

Se consideriamo poi l’ultimo grado di libertà (incertezza sui dati), allora possiamo classificare: i problemi di programmazione matematica sono quelli che tratteremo, in cui ho un unico decisore, un unico obiettivo e tutte le grandezze in gioco sono rappresentabili tramite un numero ben preciso (dati deterministici). Scritto in questo modo il problema di programmazione matematica ha poco senso.

Come posso scrivere allora un problema di programmazione matematica? Quello che si fa è riscrivere il problema nel seguente modo: ho un sistema di disequazioni che chiamo "vincoli del problema". (se ho una funzione obiettivo a massimizzare, cambio i segni, oppure se ho un vincolo maggiore invece che minore cambio i segni). Come cambio un vincolo uguale in un vincolo di minore uguale?

Dato un problema di programmazione matematica, essi possono essere classificati in base alle caratteristiche della funzione obiettivo e dei vincoli. Il caso più semplice è quello in cui tutti sono lineari: problemi di programmazione lineare. Se la funzione obiettivo e i vincoli non sono lineari: problemi di programmazione non lineare. Nel corso tratteremo quasi esclusivamente i problemi di programmazione lineare. Tratteremo anche problemi di programmazione lineare intera (le variabili possono assumere solo valori interi).

Ricapitolando, noi cerchiamo di risolvere problemi di decisione con un approccio modellistico. Devo individuare quali sono le grandezze importanti ad ognuna delle quali viene associata una variabile di decisione. Una volta individuate le grandezze di interesse, vado a scrivere il mio modello di ottimizzazione che è un modello matematico, individuo un algoritmo che svolge il mio modello e i risultati andranno valutati.

Nel grafico c’è un feedback perché l’approccio modellistico è un approccio iterativo che va in qualche modo validato prima di poter essere utilizzato. Che intendiamo? Intendiamo che nel momento in cui costruisco il mio modello che è una rappresentazione semplificata della realtà, ho eliminato/non considerato alcune grandezze, e questo può andare a comportare una soluzione non ragionevole e quindi devo ripetere le precedenti operazioni finché non arrivo ad un modello stabile. Quando termino questo processo posso utilizzare tale approccio ogniqualvolta si verifica lo stesso problema (stessa istanza del problema con valori differenti).

In questo schema la fase meno automatizzabile è la fase di modellazione (o formulazione), perché io posso anche scrivere un modello perfetto ma se non esiste un algoritmo in grado di risolverlo non me ne faccio niente, quindi devo conoscere gli strumenti che ho a disposizione per risolvere il modello.

In rete esistono numerosi solutori. La validazione viene fatta tramite simulazione. Nel momento in cui devo scrivere un modello devo decidere le grandezze che mi interessano ed a ognuna associo una variabile. Devo poi determinare dei legami logici tra le variabili. Tali legami e limitazioni definiscono i vincoli. Devo poi individuare una funzione obiettivo da minimizzare.

Esempio di modello di ottimizzazione

Così può sembrare complesso, facciamo un esempio: per ogni oggetto ho a disposizione l’informazione che mi dice il costo per la realizzazione di un’unità, e il prezzo unitario di vendita. Osserviamo che sono state fatte una serie di ipotesi semplificative per far sì che il problema resti lineare: ipotizzo che qualunque quantità di giacca faccio, il prezzo è lo stesso => se rappresento il costo su una curva.

Se ipotizzo di stare sempre nella prima parte di curva, la approssimo con una retta. Cioè il mio prodotto riesco a venderlo a 45 euro al capo. Non è sempre così perché se io poi metto troppi capi sul mercato per evitare di avere oggetti non venduti, sono costretto ad abbassare il prezzo di vendita (dopo aver realizzato un numero importante di capi); altrimenti posso mantenerlo costante a 45 euro. Quindi noi ipotizziamo che la decisione finale sta nella prima parte della curva, cioè nella parte in cui i costi sono ancora costanti.

Noi abbiamo delle risorse limitate e le vogliamo usare al meglio: le risorse limitate sono il fatto che per produrre questi tre prodotti devo lavorare in tre reparti: taglio, stiratura e cucitura. Questi reparti non li ho a disposizione per un tempo infinito. Quindi la disponibilità di questi tre reparti sono le mie tre risorse disponibili in quantità limitata.

Quante unità di ogni prodotto mi conviene produrre ogni giorno senza sforare le risorse che ho a disposizione? La prima cosa da fare è stabilire quali sono le variabili del problema: quanti numeri mi servono per descrivere una decisione? In questo caso la decisione è rappresentata da tre numeri: quanti P, G e C produrre. Quindi avrò tre variabili (xp, xg, xc).

Quali sono i vincoli? Ho a disposizione tre risorse, quindi i vincoli sono delle disequazioni. Se xp consumo la risorsa taglio per 10 min.. (10*xp) min ecc. L’obiettivo più ragionevole è massimizzare il profitto. Per sapere se il modello è corretto devo convincermi che una qualsiasi possibile decisione soddisfa i vincoli del mio problema e viceversa. Se utilizzo solo questi tre vincoli la relazione è soddisfatta? Tra le possibili soluzioni di questo sistema ci sono soluzioni negative, ma non rappresenta niente produrre -10 pantaloni. Quindi devo completare questo modello con quelli che vengono detti “vincoli di non negatività”, ponendo le x maggiori/uguali di zero.

Minimizzare i costi non ha molto senso in quanto la soluzione del problema potrebbe essere quella di non produrre niente. In tal caso dovrei rendermi conto di aver definito un obiettivo poco ragionevole e quindi bisogna modificare qualcosa.

Seconda lezione (19.03.2020)

Facciamo un esempio di programmazione matematica non lineare: dobbiamo riscrivere tale problema in modo matematico. Come deve essere fatto questo cilindro? La prima cosa che dobbiamo fare è decidere quali sono le variabili del problema: per farlo, rispondiamo alla domanda “di quanti numeri ho bisogno per descrivere la mia soluzione”? In questo caso la soluzione è il cilindro, quindi le variabili rappresentano le sue dimensioni: allora ho bisogno di due variabili decisionali x (lunghezza raggio di base), y (altezza del cilindro).

Una volta scelte le variabili, dobbiamo definire la funzione obiettivo: l’obiettivo è costruire un cilindro che può contenere la max quantità di liquido, quindi vogliamo massimizzare la funzione.

Vincoli del problema

• Il cilindro deve essere appoggiato sulla base del magazzino, quindi il diametro del cilindro deve essere minore o uguale del lato più piccolo;
• Abbiamo detto che per costruire questo cilindro utilizzo un materiale plastico per una quantità massima disponibile pari a 200 m²;
• Anche l’altezza del magazzino è un vincolo (0.2 è la pendenza del tetto, che è del 20%. Se x=5, e quindi il diametro è =10, l’altezza non può superare l’altezza del magazzino).

Ovviamente, dobbiamo sempre garantire la corrispondenza tra l’insieme di tutte le decisioni ammissibili e le soluzioni ammissibili, e quindi abbiamo aggiunto il vincolo di fisica realizzabilità. Sono arrivata ad un problema di programmazione matematica. Per completare il processo decisionale, devo trovare la soluzione ottima: possiamo farlo attraverso il foglio di lavoro Excel che ha un tool in grado di risolvere problemi di programmazione matematica di dimensioni ridotte. La soluzione ottima è quella di costruire un cilindro. Nota: se faccio partire Excel dal punto (0,0) non riesce a risolverlo.

Programmazione lineare

Ritorniamo alla programmazione lineare. Un problema di programmazione lineare si può presentare in tre forme differenti: in genere, questi problemi di programmazione lineari sono più “facili”, nel senso che esistono algoritmi che risolvono problemi di PL con un numero di variabili molto elevato (cosa che non accade per i problemi di programmazione non lineari). Noi utilizzeremo un algoritmo, chiamato Simplex, che ha una complessità esponenziale, che nella maggior parte dei casi si comporta meglio degli algoritmi che hanno una complessità polinomiale.

I problemi PL possono essere classificati, ma è molto difficile trovare un problema reale che fa effettivamente parte di uno dei seguenti tre gruppi.

Il primo insieme è quello dell’allocazione ottima di risorse: in un problema di questo tipo io ho m risorse (R1,R2..Rm). Di queste risorse non ne ho una quantità illimitata. Queste risorse le utilizzo per produrre n prodotti (P1,P2..Pn) e ad ogni prodotto è associato un costo ci.

Matrice dei tassi di assorbimento

Facciamo un esempio. Questa tabella è la matrice dei tassi di assorbimento trasposta rispetto alla precedente definizione. Le mie risorse sono limitate. Devo scegliere le variabili: avrò ovviamente quattro variabili. (C’è un foglio Excel dove è svolta e risoluzione di tale problema). Esercizio su Xpress: Esempio_Allocazione_Ottima_1.mos. Nell’esercizio Esempio_Allocazione_Ottima_2.mos, il professore ha cercato di scrivere un programma che vada bene per qualsiasi tipologia di problema.

Terza lezione (20.03.2020)

Andiamo a vedere la classe dei problemi di miscelazione. Diamo una generica definizione: "un problema di miscelazione, nella sua forma generale, è definito da due insiemi. Si chiama così perché l’obiettivo del decisore è capire come produrre un prodotto ottenuto dalla miscelazione di alcune sostanze." Per questo motivo come dati input abbiamo un insieme di sostanze (S1,S2..Sn); ciascuna di queste sostanze ha un costo e il costo unitario di ognuna ci. Poi abbiamo un insieme di componenti utili per le sostanze (C1,C2..Cn).

Esempio di problema di miscelazione

Si definisce così la matrice Componenti-Sostanze. Un esempio di problema di miscelazione può essere quello della dieta. Le calorie sono la componente che voglio minimizzare. Avrò una variabili x1 che rappresenta la carne, x2 i legumi, x3 la pasta, x4 l’olio che l’atleta deve assumere in un giorno.

- Funzione obiettivo:

- Vincoli:

Nelle slide c’è il foglio Excel che risolve tale problema.