Ricerca operativa

Introduzione Non tutti lo sanno, ma con i fogli di calcolo elettronico è possibile risolvere problemi di ottimizzazione. Come Excel e Open Office , anche Google Spreadsheets fornisce gli strumenti necessari per scrivere e risolvere semplici problemi di ottimizzazione, utili per: insegnare l’ottimizzazione realizzare semplici prototipi e dimostrativi risolvere problemi pratici Per capirne il funzionamento, ho provato a scrivere un semplice problema di ottimizzazione e a risolverlo in Google Spreadsheets. Descrizione del problema Come problema d’esempio, prendiamo in considerazione la schedulazione delle attività di lavorazione di un’azienda manifatturiera di abbigliamento. Il processo produttivo è organizzato per soddisfare degli ordini, che vengono realizzati in un laboratorio composto da postazioni di lavoro. L’uso del laboratorio è suddiviso in turni, dove lavoratori specializzati si alternano nelle postazioni di lavoro. Un ordine è caratterizzato da: CDC  —...

Per chi vuole provare a scrivere (semplici) modelli di ottimizzazione in un foglio di calcolo, può provare anche OpenSolver: componente aggiuntivo per Excel. Tutti i dettagli sono disponibili sul sito https://opensolver.org/

Credo che molti saranno interessati da queste lezioni che ho trovato su youtube . Si tratta delle lezioni tenute dal prof. Alberto Colorni , ordinario del Politecnico di Milano, per il Consorzio Nettuno . Le lezioni sono 40, ma qui di seguito riporto solo il link alla prima lezione. Per tutte le altre, basta seguire il link poi alla lezione 02, poi alla lezione 03 e così via. Buona visione e prendete bene i  vostri appunti ;-)

La diffusione o, come a molti piace dire, la disseminazione della ricerca operativa e delle sue applicazioni è sempre stato un argomento di mio interesse. Per questo motivo, trovo molto interessante la seguente tesi di laurea, che illustra come la ricerca operativa venga insegnata nelle scuole superiori in Italia a confronto con altri modelli didattici, quali quello degli Stati Uniti d'America e quello Inglese. Il titolo della tesi è " La Divulgazione della Ricerca Operativa nelle Scuole Superiori di Secondo Grado ", di Roberta Sagripanti, relatore Prof. Renato De Leone . Tesi Di Roberta Sagripanti

Trovo molto interessanti questi appunti, perché mostrano un punto di vista molto interessante. Infatti, si parla di  modellazione ! La presenza di 16 esercizi e relative soluzioni, in termini di programmazione lineare intera, fornisce una base di partenza molto utile di tecniche di modellazione. Purtroppo non conosco l'autore di questi appunti, per cui non sono in grado di citarlo giustamente. Ricerca Operativa I - Esercizi Di Modellazione 2006

Ho trovato un sito molto originale dove vengono proposti molti esercizi e, tra questi, ve ne sono decine di molto piccoli che riguardano la programmazione lineare. A giudicare dalla complessità e dai contenuti proposti in altre sezioni del sito, direi che questi esercizi sono diretti agli studenti delle scuole superiori. Questo è un esempio di esercizio proposto: Una segheria produce pezzi di legno per scaffalature, tagliando assi di legno lunghe un metro. In particolare, si devono produrre nel prossimo periodo 70 pezzi da 30cm, 62 pezzi da 50cm e 37 pezzi da 70 cm. Ogni asse da un metro costa 2 Euro. Inoltre, ogni pezzo prodotto in eccesso rispetto alla domanda, costa all'azienda 5 centesimi per il suo smaltimento. Formulare il problema di decidere come tagliare le assi in modo da minimizzare il costo complessivo, soddisfacendo la domanda. Probabilmente molti studenti, in prossimità degli esami di stato, troveranno utile fare alcuni, se non tutti, gli esercizi proposti. I m...

Da un lavoro di Gionata Massi del 2003, segnalo questa implementazione del simplesso in PHP. Credo che questo semplice programma possa essere molto utile per insegnare il funzionamento dell'algoritmo del simplesso. Infatti, dalla pagina sopra citata, è possibile inserire manualmente un problema di programmazione lineare ed avere in output tutti i passi risolutivi. Dalla documentazione del software: Il programma è stato implementato allo scopo di fornire in output la risoluzione passo passo di un problema di programmazione lineare, in molto del tutto simile all'analisi eseguita manualmente. Si è scelto, anche per facilitare le operazioni di debugging e di riscontro della correttezza dell'algoritmo, di rappresentare tutti i passaggi: visualizzazione del problema immesso, del problema portato prima in forma standard e successivamente in forma canonica, rappresentazione del tableau anche nel caso eventuale di utilizzo del metodo delle due fasi con indicazione ad ogni passo...

Per gli amanti di Java, tra i quali non ci sono io :-), vi voglio segnalare la disponibilità dell'edizione gratuita di OptimJ . OptimJ è una libreria di classi Java per la modellazione ad oggetti di problemi di programmazione lineare. OptimJ Free Edition comprende: integrazione in eclipse pre-elaborazione dei dati prototipazione rapida di interfacce grafiche la possibilità di utilizzare i solver GLPK e lp_solve supporto dei file in formato LP e MPS Non ho mai avuto la possibilità di utilizzare OptimJ, quindi sarò lieto di ospitare ogni contributo in tal senso.

Voglio segnalarvi questa iniziativa che trovo veramente molto interessante. Si chiama "Ottimizziamo!", si tiene a Crema ed è curata di Alberto Ceselli e Giovanni Righini . I dettagli li trovate su cremonaonline.it , ma in sintesi si tratta di incontri full-immersion di due giorni, tenuti presso i laboratori informatici dell'Università , dove i due docenti spiegano come modellare e risolvere problemi di ottimizzazione matematica. Trovo questa iniziativa molto lodevole e spero che si possa replicare anche in altre città.

Supply Chain Management

Su youtube ho trovato questa interessante intervista al prof. Paolo Toth . Si spiega in termini molto semplici il problema combinatorio del commesso viaggiatore e delle tecniche risolutive.

Vi giro i seguenti tre video che compongono un breve tutorial e una interessante raccolta di esercizi svolti. L'autore dei video è Fabiàn Breschi, studente del corso di laurea in Ingegneria Informatica del Politecnico di Milano.

In questi giorni, la ricerca più frequente sulle pagine di questo blog è proprio "tesina sulla ricerca operativa", con le sue varianti. Capita così ogni anno quando si avvicinano gli esami di maturità. Allora intanto esorto sempre gli studenti a studiare per tempo, perché i concetti devono avere il tempo di "sedimentare". Comunque, della serie meglio tardi che mai, vi posso suggerire gli appunti curati dal Prof. Amendola Alfonso, docente di Matematica Applicata dell' Istituto Tilgher . Per altri spunti interessanti di partenza, vi consiglio pure l'articolo " La ricerca operativa e le scuole superiori ".

Ho trovato questi due esercizi, anzi il loro svolgimento, su youtube. Si tratta di esercizi molto semplici che spiegano il così detto metodo grafico di risoluzione. Credo che si tratti di esercizi per le scuole superiori, ma forse possono essere utili anche per qualche corso base universitario. Il secondo video ha un audio molto basso.

All'interno del portale Federica è possibile trovare il corso di Ricerca Operativa curato da Paola Festa. Trovo questo esperimento dell'Università di Napoli molto interessante è anche molto promettente. Credo che almeno personalmente frequenterò i corsi ospitati da Federica come interessante opportunità di approfondimento.

L'AIRO ha organizzato per l'anno scolastico 2008-2009 una gara di ricerca operativi per gli studenti del triennio delle scuole superiori. Maggiori dettagli si trovano sul sito dedicato all'iniziativa. Ho dato un'occhiata ai referenti locali ed ho notato l'assenza di qualche regione. Qualcuno mi sa spiegare il motivo? Buon lavoro e buon divertimento a tutti gli studenti ed insegnanti.

IPCO 2008 Summer School University Residential Center, Bertinoro (Forlì-Cesena), Italy May 29-30, 2008 The IPCO Summer School will take place immediately after the IPCO conference. The lecturers will be Michele Conforti, Franz Rendl and Martin Skutella. Lectures' program Michele Conforti Extended Formulations in Integer Programming and Combinatorial Optimization An extended formulation of a polyhedron P is a system of inequalties S that defines a polyhedron Q in a higher dimensional space such that P is the projection of Q in the original space. If one can efficiently optimize a linear function over Q then one can optimize it over P, and if S is a "small" system, optimizing over Q can be efficiently done via Linear Programming. We first discuss a result of Yannakakis on the existence of such small systems and then survey some extended formulations in Combinatorial Optimization, related to matchings, cuts, stable sets, hamiltonian tours, etc. Extended formulati...

A cure del prof. PierLuigi Zezza , MetM@t è un interessante esperimento didattico, che si prefigge lo scopo di migliorare l'insegnamento della matematica in facoltà diverse da quelle di matematica. Due le versioni disponibili: quella interattiva e quella statica. La prima permette di "navigare" attraverso gli argomenti e le esercitazioni, mentre la seconda è adatta ad essere stampata. Gli argomenti trattati sono: PREREQUISITI METODI LINEARI Algebra Lineare Programmazione Lineare Complementi ANALISI MATEMATICA Funzioni di una variabile Funzioni di più variabili Ottimizzazione Integrali Multipli COMPLEMENTI Teoria dell’approssimazione Teoria della misura METODI DINAMICI Equazioni Differenziali Optimal Control Purtroppo l'ultimo aggiornamento sembra risalire al 2005 e MetM@t è ritenuta in beta. Speriamo che l'autore abbia la possibilità di portare in una versione definitiva il suo interessante lavoro.

Continuiamo la nostra presentazione di PuLP mostrando un esempio completo. A tal fine prendiamo in considerazione un problema reale: quello della schedulazione delle pompe idrauliche degli impianti di sollevamento dei serbatoi degli acquedotti. Ipotizziamo di voler programmare l'accensione e spegnimento orario di 5 pompe nell'arco di 24 ore. Siccome il comportamento risultante di più pompe che funzionano contemporaneamente non può essere considerato lineare, le 5 pompe vengono modellate come 32 pompe virtuali distinte e mutuamente esclusive. numPumps = 32 pumpSet = range(numPumps) numTimes = 24 timeSet = range(numTimes) Ognuna delle 32 pompe virtuali ha un consumo orario di energia e una portata oraria: energyForPump = [0, 595, 260, 855, 260, 855, 520, 1115, 445, 1040, 705, 1300, 705, 1300, 965, 1560, 595, 1190, 855, 1450, 855, 1450, 1115, 1710, 1040, 1635, 1300, 1895, 1300, 1895, 1560, 2155] dischargeForPump = [0, 1800, 828, 2600, 828, 2600, 1650, 3450, 1440, 3235, 2260, 4060,...

L'insegnamento dei concetti di base della ricerca operativa, ovvero la programmazione lineare, ha trovato nel corso degli ultimi anni diversi strumenti di supporto. Sono ormai parecchi i software gratuiti e open source che permettono agli studenti e agli insegnanti di toccare con mano le nozioni e i concetti spiegati e studiati sui banchi. Ricordiamo, ad esempio, glpk che con il suoi linguaggio di modellazione MathProg permettete di scrivere e risolvere anche complessi modelli di programmazione lineare intera. Oppure citiamo anche lp_solve che con il suo ambiente impropriamente chiamato lp_solve IDE permette di scrivere e risolvere modelli di programmazione lineare direttamente nella formulazione matematica. A mio avviso però le proposte appena citate sono limitate nella potenza espressiva e nelle capacità di integrarsi con altri software o moduli esterni. Queste limitazioni sono egregiamente risolte da PuLP : un modellatore di problemi di programmazione lineare intera basato ...