Didattica della Ricerca Operativa nelle scuole superiori

La Ricerca Operativa è considerata una disciplina universitaria il cui insegnamento è previsto nei corsi di laurea di Ingegneria, Matematica e Informatica. Da qualche anno si è verificata una tendenza ad anticipare l'insegnamento della Ricerca Operativa ad un grado scolastico inferiore. In Gran Bretagna e negli Stati Uniti sono presenti organizzazioni molto attive nell'ambito della sua divulgazione e sono nati progetti importanti a livello didattico: corsi di formazione per i docenti, condivisione in rete di materiali e report delle esperienze effettuate. A partire dal 2012 anche nelle indagini internazionali OCSE-PISA si sono aggiunte due aree i cui obiettivi e contenuti si avvicinano alla Ricerca Operativa: financial literacy e problem solving. In Italia, dopo la riforma governativa Gelmini del 2008, sono presenti elementi di Ricerca Operativa solo nei programmi di matematica del quinto anno degli istituti tecnici commerciali e industriali. Tuttavia la Ricerca Operativa può svolgere un ruolo fondamentale nella formazione scientifica, innanzitutto per il suo ruolo di "ponte" tra la matematica e l'informatica, poi per l'importanza dello sviluppo della modellizzazione e per l'interdisciplinarietà della materia e lo stretto contatto con il mondo del lavoro. Inoltre, le esperienze documentate di didattica della Ricerca Operativa hanno potuto verificare l'importante ruolo motivazionale che possiede nei confronti degli studenti meno amanti della matematica. In questo lavoro di tesi si è interrogata la fattibilità di un percorso di Ricerca Operativa per una classe seconda liceo scientifico (anno in cui vengono svolte le indagini internazionali). Viene poi presentata la costruzione di una lezione di Programmazione Lineare che prevede una prima fase di modellizzazione del problema e una seconda fase di soluzione tramite il solutore di excel in laboratorio.

La programmazione lineare intera e i suoi sviluppi

La tesi si occupa della programmazione lineare in particolare nel caso in cui le variabili coinvolte o alcune di esse sono obbligate ad assumere valori interi.

Modelli di Ottimizzazione per la programmazione di sale operatorie

La tesi è l'esito di un lavoro di studio e ricerca nell'ambito della gestione delle sale operatorie, uno dei problemi principali su cui si sono focalizzati gli studi di Ricerca Operativa, applicati ai sistemi sanitari, sviluppati nell'ultimo decennio. Vengono presentati i due modelli di ottimizzazione creati al fine di migliorare l'efficienza organizzativa delle pianificazioni degli interventi chirurgici di un presidio ospedaliero. I due modelli, uno teorico e l'altro implementato con istanze reali, si distinguono dalle ricerche presenti in letteratura per l'innovativa proposta di pianificare attività preoperatorie che contribuiscano a raggiungere una miglior efficienza e la diminuzione dei costi delle pratiche chirurgiche.

Progettazione e sviluppo di software di supporto alla logistica dei trasporti.

Uno dei problemi più diffusi, nell'ambito della logistica, è rappresentato dai costi di trasporto. La gestione dei flussi merci, l'approvvigionamento dei clienti, e la relativa pianifcazione della movimentazione dei veicoli, hanno incidenze notevoli sui costi di gestione aziendali, i quali vengono stimati mediamente nel 45% dei costi logistici. A ragione di questo, sono sempre di più le aziende che ricorrono all'impiego di uffici dedicati alla pianifcazione delle consegne e la gestione dei trasporti in generale. Sebbene le voci di bilancio relative al trasporto raggiungano cifre rilevanti, fno al 4% del fatturato annuo, il tema della pianifcazione viene spesso sottovalutato. Infatti la soluzione a problemi di pianifcazione e monitoraggio dei costi, è spesso demandata a procedure manuali senza supporto informatico. Nasce da qui l'esigenza di proporre uno strumento informatico che supporti gli addetti preposti alla pianifcazione, sviluppando un sistema che copra esigenze di pianifcazione dei viaggi, controllo e consuntivazione dei costi di trasporto, e monitoraggio dei mezzi in tempo reale. La proposta di Gesp srl, Geographic Information Systems, azienda italiana che opera da anni nel campo delle applicazioni software geo-spaziali, prende il nome di Nuovo Sistema Trasporti, o più semplicemente, NST. In quest'ambito prende corpo questa tesi, la quale si pone l'obiettivo di illustrare le fasi di nascita, analisi, progettazione e sviluppo di un software generico per il supporto alla logistica. Saranno così analizzati: le problematiche affrontate nella fase di defnizione, e kick-off (avvio), del progetto, il problema del routing, o Vehicle Routing Problem e le tecniche di Ricerca Operativa che vengono applicate per la sua risoluzione; le moderne metodologie di gestione e sviluppo di un software; l'architettura e le tecnologie impiegate per la distribuzione dell'applicativo.

A study on set variable representations in constraint programming

Il lavoro presentato in questa tesi si colloca nel contesto della programmazione con vincoli, un paradigma per modellare e risolvere problemi di ricerca combinatoria che richiedono di trovare soluzioni in presenza di vincoli. Una vasta parte di questi problemi trova naturale formulazione attraverso il linguaggio delle variabili insiemistiche. Dal momento che il dominio di tali variabili può essere esponenziale nel numero di elementi, una rappresentazione esplicita è spesso non praticabile. Recenti studi si sono quindi focalizzati nel trovare modi efficienti per rappresentare tali variabili. Pertanto si è soliti rappresentare questi domini mediante l'uso di approssimazioni definite tramite intervalli (d'ora in poi rappresentazioni), specificati da un limite inferiore e un limite superiore secondo un'appropriata relazione d'ordine. La recente evoluzione della ricerca sulla programmazione con vincoli sugli insiemi ha chiaramente indicato che la combinazione di diverse rappresentazioni permette di raggiungere prestazioni di ordini di grandezza superiori rispetto alle tradizionali tecniche di codifica. Numerose proposte sono state fatte volgendosi in questa direzione. Questi lavori si differenziano su come è mantenuta la coerenza tra le diverse rappresentazioni e su come i vincoli vengono propagati al fine di ridurre lo spazio di ricerca. Sfortunatamente non esiste alcun strumento formale per paragonare queste combinazioni. Il principale obiettivo di questo lavoro è quello di fornire tale strumento, nel quale definiamo precisamente la nozione di combinazione di rappresentazioni facendo emergere gli aspetti comuni che hanno caratterizzato i lavori precedenti. In particolare identifichiamo due tipi possibili di combinazioni, una forte ed una debole, definendo le nozioni di coerenza agli estremi sui vincoli e sincronizzazione tra rappresentazioni. Il nostro studio propone alcune interessanti intuizioni sulle combinazioni esistenti, evidenziandone i limiti e svelando alcune sorprese. Inoltre forniamo un'analisi di complessità della sincronizzazione tra minlex, una rappresentazione in grado di propagare in maniera ottimale vincoli lessicografici, e le principali rappresentazioni esistenti.

Dall'insieme alla struttura matematica nella scuola di oggi

Percorso didattico alternativo dall'insieme alla struttura matematica con analisi di libri di testo di scuole superiori.

Solving the logically constrained multiple choice multiple knapsack problem: A real case

In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.

Algoritmi Euristici per la Schedulazione degli Interventi nel Blocco Operatorio

Questa tesi riguarda il problema della schedulazione degli interventi nel blocco operatorio di un presidio ospedaliero, noto anche come Operating Theatre Planning & Scheduling. Il blocco operatorio è la struttura che eroga servizi a più alto impatto sui costi di un presidio ospedaliero ed è legato ad attività ad alto rischio. E' quindi fondamentale gestire in modo ottimale questa risorsa. In questa tesi, si considera come caso studio l'applicazione reale di un presidio ospedaliero dell'Emilia Romagna con un orizzonte temporale di una settimana, ovvero la cosiddetta programmazione operativa. L'obiettivo è quello di ottenere un utilizzo efficiente del blocco operatorio, garantendo al contempo la priorità agli interventi più urgenti. Data la complessità del problema, vengono proposti algoritmi euristici che permettano di ottenere buone soluzioni in tempi di calcolo ridotti. Studi precedenti hanno infatti evidenziato la difficoltà di trovare soluzioni ottime al problema, mediante l'utilizzo di solver commerciali per modelli di Programmazione Lineare Intera, senza introdurre ipotesi semplificative. Sono stati elaborati tre algoritmi euristici costruttivi di tipo multi-start che permettono di generare soluzioni ammissibili con diverse caratteristiche. Gli algoritmi si differenziano principalmente per le modalità con cui collocano gli interventi nel tempo disponibile delle risorse (induction room, operating room, recovery room), cercando di migliorarne l’utilizzazione e dando priorità ai pazienti più urgenti. Gli algoritmi sono stati implementati utilizzando il linguaggio JAVA e sono stati testati su istanze realistiche fornite dal presidio ospedaliero. I risultati hanno evidenziato un alto grado di utilizzazione delle sale operatorie, un fattore molto rilevante per una ottimale gestione del blocco operatorio. E' stata, infine, svolta un'analisi di sensitività alla variabilità delle durate.

Le curve piane: dallo studio in geometria alla trattazione scolastica

L'argomento trattato in questa tesi riguarda lo studio geometrico delle curve piane. Una prima parte è dedicata alle varie definizioni di curva in matematica, la seconda tratta invece la presentazione delle curve da un punto di vista scolastico. Il mio lavoro è stato quello di analizzare alcuni testi delle scuole superiori allo scopo di evidenziare, laddove è stato possibile, il tipo di appproccio didattico utilizzato per presentare tali argomenti.

Metodi euristici per il Vehicle Routing Problem

Il problema della consegna di prodotti da un deposito/impianto ai clienti mediante una flotta di automezzi è un problema centrale nella gestione di una catena di produzione e distribuzione (supply chain). Questo problema, noto in letteratura come Vehicle Routing Problem (VRP), nella sua versione più semplice consiste nel disegnare per ogni veicolo disponibile presso un dato deposito aziendale un viaggio (route) di consegna dei prodotti ai clienti, che tali prodotti richiedono, in modo tale che (i) la somma delle quantità richieste dai clienti assegnati ad ogni veicolo non superi la capacità del veicolo, (ii) ogni cliente sia servito una ed una sola volta, (iii) sia minima la somma dei costi dei viaggi effettuati dai veicoli. Il VRP è un problema trasversale ad una molteplicità di settori merceologici dove la distribuzione dei prodotti e/o servizi avviene mediante veicoli su gomma, quali ad esempio: distribuzione di generi alimentari, distribuzione di prodotti petroliferi, raccolta e distribuzione della posta, organizzazione del servizio scuolabus, pianificazione della manutenzione di impianti, raccolta rifiuti, etc. In questa tesi viene considerato il Multi-Trip VRP, in cui ogni veicolo può eseguire un sottoinsieme di percorsi, chiamato vehicle schedule (schedula del veicolo), soggetto a vincoli di durata massima. Nonostante la sua importanza pratica, il MTVRP ha ricevuto poca attenzione in letteratura: sono stati proposti diversi metodi euristici e un solo algoritmo esatto di risoluzione, presentato da Mingozzi, Roberti e Toth. In questa tesi viene presentato un metodo euristico in grado di risolvere istanze di MTVRP in presenza di vincoli reali, quali flotta di veicoli non omogenea e time windows. L’euristico si basa sul modello di Prins. Sono presentati inoltre due approcci di local search per migliorare la soluzione finale. I risultati computazionali evidenziano l’efficienza di tali approcci.

Realizzazione di uno strumento per la ripartizione dei fondi europei nell'ambito del programma operativo regionale

La costituzione dell’Unione Europea nel 1993 pose la questione del dover aiutare le regioni svantaggiate in essa contenute, allo scopo di promuovere i principi di eguaglianza appena stipulati. Allo stesso tempo si dovette cercare uno strumento per facilitare la collaborazione fra le regioni appartenenti all’Unione stessa. Tale strumento sono i Fondi Strutturali Europei, un sistema di autofinanziamento utilizzato per promuovere progetti lavorativi, di cultura o di ricerca in tutta Europa. La distribuzione dei fondi avviene secondo delle regole specifiche e spesso i temi verso cui i fondi vengono rivolti sono scelti di comune accordo tra i Paesi membri. Le amministrazioni regionali hanno quindi la possibilità di usufruire di una notevole quantità di denaro, giustificando in modo appropriato la destinazione d’uso dei fondi e stilando dei piani che ne descrivano la loro suddivisione nei vari progetti. In seguito all’evoluzione tecnologica degli anni ’60 e ’70 nacquero nuovi strumenti a favore delle aziende: i DSS (Decision Support System), descritti come “sistemi informatici a supporto del processo decisionale”. L’uso di questa nuova tecnologia permise una facilitazione dei compiti decisionali, oltre ad un miglioramento delle prestazioni negli ambiti di applicazione. Da tali premesse nascono diversi progetti che puntano ad utilizzare strumenti di supporto alle decisioni nei campi più diversi: amministrativo, medico, politico, culturale. In particolare, l’area d’applicazione politica vive un grande fermento negli ultimi anni, grazie a strumenti in grado di aiutare la classe politica in decisioni su più livelli di scelta e su una grosse mole di dati. Un esempio fra gli altri è la redazione del Programma Operativo Regionale, il quale fa affidamento sui finanziamenti dei Fondi Strutturali Europei per potersi sostentare. Negli ultimi anni la Regione Emilia-Romagna ha puntato molto sull’uso di strumenti informatici e automatizzati come aiuto nella compilazione di progetti, piani operativi e preventivi di spesa, sviluppando delle collaborazioni con diversi Enti ed Università, tra le quali l’Università degli Studi di Bologna. L’ultimo progetto realizzato in collaborazione con la Regione, e qui esposto, riguarda la realizzazione di uno strumento di supporto alle decisioni politiche per la ripartizione dei Fondi Europei, in particolare quelli destinati al Programma Operativo Regionale (POR).

Simulazione del triage infermieristico in un centro di salute mentale

Il presente elaborato nasce con l'obiettivo di applicare metodi di ricerca operativa, ed in particolare tecniche di simulazione, ad una realtà sanitaria. L’attuale scenario dei dipartimenti sanitari suggerisce l’uso e l’applicazione di nuove tecnologie, fondamentali per analizzare i processi e valutare l’impatto economico, di questi ultimi, sul bilancio della struttura. Nella tesi si esamina il caso sanitario di un Centro di Salute Mentale della regione Emilia Romagna, attraverso il software Arena Simulation.

Algoritmi di ottimizzazione per il bus touring problem.

Nel campo della Ricerca Operativa e dei problemi di ottimizzazione viene presentato un problema, denominato Bus Touring Problem (BTP), che modella una problematica riguardante il carico e l’instradamento di veicoli nella presenza di di vincoli temporali e topologici sui percorsi. Nel BTP, ci si pone il problema di stabilire una serie di rotte per la visita di punti di interesse dislocati geograficamente da parte di un insieme di comitive turistiche, ciascuna delle quali stabilisce preferenze riguardo le visite. Per gli spostamenti sono disponibili un numero limitato di mezzi di trasporto, in generale eterogenei, e di capacitá limitata. Le visite devono essere effettuate rispettando finestre temporali che indicano i periodi di apertura dei punti di interesse; per questi, inoltre, é specificato un numero massimo di visite ammesse. L’obiettivo é di organizzare il carico dei mezzi di trasporto e le rotte intraprese in modo da massimizzare la soddisfazione complessiva dei gruppi di turisti nel rispetto dei vincoli imposti. Viene presentato un algoritmo euristico basato su Tabu Search appositamente ideato e progettato per la risoluzione del BTP. Vengono presentati gli esperimenti effettuati riguardo la messa appunto dei parametri dell'algoritmo su un insieme di problemi di benchmark. Vengono presentati risultati estesi riguardo le soluzioni dei problemi. Infine, vengono presentate considerazioni ed indicazioni di sviluppo futuro in materia.

Implementazione e test di modelli di ottimizzazione per la pianificazione tattica del blocco operatorio

In questa tesi è stato analizzato e tradotto nel linguaggio di alto livello AMPL un modello di ILP relativo alla pianificazione tattica del blocco operatorio. L'obiettivo è quello di permettere l'interfacciamento con numerosi solver -commerciali e non- al fine di analizzarne le prestazioni. In seguito a un'introduzione in merito al problema dell'Operating Room Management e a una descrizione del contesto sanitario regionale dell'Emilia-Romagna, si è proceduto alla descrizione formale del modello. Infine sono state eseguite numerose risoluzioni con i solver cplex e gurobi al variare di alcuni parametri in ingresso, tra cui il numero di sale operatorie, di infermieri e operatori sanitari, e di pazienti in lista d'attesa.