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)