Fondamenti di ricerca operativa

Informazioni generali

Fondamenti di Ricerca Operativa è un corso complementare per le lauree triennali in Informatica e per la laurea specialistica in Tecnologie dell'informazione e della comunicazione

Docente

Marco Trubian

Orari delle lezioni

• Mercoledì 15.30 - 17.30
• Giovedì 15.30 - 17.30

in aula 307 (via Celoria 20).

Orario di ricevimento studenti

Su appuntamento per email ( trubian@dsi.unimi.it ) nel suo studio (P103 in via comelico).

Sito del corso

Alla pagina [1] è disponibile il programma del corso.

Materiale didattico

• Libro di testo: M. Fischetti - "Lezioni di Ricerca Operativa" - Edizioni Libreria Progetto Padova, 1995.

• Lucidi utilizzati a lezione: R. Baldacci, M. Dell'Amico - "Fondamenti di Ricerca Operativa" - Pitagora Editrice Bologna, 2002.

• Eserciziario: - M. Dell’Amico: "120 esercizi di ricerca operativa" - Pitagora Editrice Bologna, 1996.

Come esercizi preparatori sono inoltre suggeriti i vecchi temi d'esame reperibili sul sito del prof. Trubian [2].

Modalità d'esame

L’esame consisterà in una prova scritta, che viene considerata valida se la valutazione è maggiore o uguale a 17, e di una parte orale obbligatoria per chi ha un voto allo scritto molto basso (17-18) o molto alto (>=28). La parte orale consiste nella discussione dello scritto e in un'eventuale integrazione, ed è facoltativa per chi ottiene un punteggio nello scritto tra il 19 e il 27. Sono inoltre previste 2 prove in itinere (che valgono come scritto): la prima il 18 Novembre e la seconda il 19 Gennaio.

Prerequisiti

Elementi di algebra delle matrici: inversa, trasposta, determinante.

Diario del corso

Lezione di Mercoledì 5-10-05

Argomenti trattati nella lezione di oggi:

• Introduzione al corso e informazioni generali
• Definizione di ricerca operativa
• Breve storia della ricerca operativa
• Esempi di modellizzazione di problemi: distribuzione ottimale sul territorio di centraline di rilevazione sismica o di trasmettitori (set covering), problema dei 7 ponti di Köenigsberg, problema dell'assegnazione del personale
• Definizione di programmazione matematica
• Come approcciare un problema di programmazione dinamica

Lezione di Giovedì 6-10-05

Argomenti trattati nella lezione di oggi:

• Notazioni:

insieme dei reali, spazio vettoriale a n dimensioni, insieme degli interi, 
intervallo chiuso/aperto, norma euclidea, definizione estensiva/intensiva 
di un insieme, cardinalità di un insieme, argmin, floor, roof, valore assoluto, 
vettore colonna, vettore trasposto (=vettore riga), matrice, prodotto scalare 
tra vettori, prodotto matrice-vettore, determinante, equazione con vettori 
(cioè del tipo Ax=b dove A è una matrice, b è un vettore e x uno scalare)

• Definizione di problema di programmazione matematica come coppia (X,f) dove X è l'insieme delle soluzioni ammissibili e f la funzione obbiettivo
• Definizione di problema impossibile e di problema illimitato
• Definizione di combinazione convessa, insieme convesso, funzione convessa e funzione concava
• Teorema: l'intersezione di insiemi convessi è un insieme convesso
• Teorema: X={x in R^n | f(x)<=0 , f convessa} è un insieme convesso (con dimostrazione)
• Teorema: X={x in R^n | Fi(x)<=0 con i=1,...,m e Fi convessa} è un insieme convesso
• Teorema: ogni funzione lineare è sia concava che convessa
• Definizione di minimo locale
• Teorema: ogni minimo locale di una funzione convessa è anche minimo globale (con dimostrazione)

Lezione di Mercoledì 12-10-05

Argomenti trattati nella lezione di oggi:

• Modello di programmazione lineare: forma generale e esempio
• Condizioni e vincoli logici per i modelli lineari (cioè trasformare formule logiche in espressioni lineari)
• Condizioni non rappresentabili direttamente con variabili booleane (introduzione "big M")
• Vincoli disgiuntivi (utilizzo di big M e introduzione della variabile logica delta)
• Esempio di risoluzione di problemi tramite modellizzazione:

Problema di mix ottimale di produzione
individuazione di: variabili, vincoli di capacità e di non negatività, funzione obbiettivo
risoluzione: grafica, tramite individuazione dell'iperpiano di supporto dei vincoli + vertice ottimo

AVVISO

Domani 13-10-05 non ci sarà lezione, ma siete tutti invitati a seguire un seminario in sala lauree (comelico) in inglese sulle tecniche di ottimizzazione di modelli matematici applicati al network design (mi pare :S). L'orario è 15.30-17.00

Oggi si è parlato del problema della sovrapposizione di orari del venerdì, dopo varie proposte che non sembravano risolvere il problema senza crearne di nuovi il prof ha chiesto (a chi ha intenzione di frequentare ovviamente) di mandargli per email l'elenco dei corsi fondamentali che ciascuno segue, così da analizzare le intersezioni di ore libere e scegliere una data opportuna.