|
|
| (8 versioni intermedie di 2 utenti non mostrate) |
| Riga 1: |
Riga 1: |
| − | [[Categoria:Corsi]][[Categoria:Corsi Primo Semestre]]
| + | {{introduzione}} |
| − | <!-- non cancellare le righe precedenti -->
| + | == Turni == |
| − | == Informazioni generali == | + | {{Turno|(Trubian)}} |
| | | | |
| − | '''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
| + | == A.A. passati == |
| | + | {{Annipassati|2006-2007|(Marco Trubian)}} |
| | + | {{Annipassati|2005-2006|(Marco Trubian)}} |
| | | | |
| − | === Docente === | + | == Informazioni == |
| | | | |
| − | Marco Trubian
| + | === Giudizio sul corso === |
| | + | {{Giudizio}} |
| | + | {{Giudizio/Interesse}} |
| | + | {{Giudizio/Difficoltà}} |
| | + | {{Giudizio/Nonfrequentanti}} |
| | + | {{Giudizio/Ore}} |
| | | | |
| − | === Orari delle lezioni ===
| + | [[Categoria:Corsi Primo Semestre]] |
| − | | |
| − | * Lunedì 14.30 - 16.30 in aula 208 (via Celoria 20)
| |
| − | * Mercoledì 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 [http://homes.dsi.unimi.it/~trubian/aa200506.htm] è 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 [http://homes.dsi.unimi.it/~trubian/studenti.htm].
| |
| − | | |
| − | Alcuni appunti online disponibili [http://www.dsy.it/forum/showthread.php?s=&threadid=22154 qui]
| |
| − | | |
| − | === 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 21 Novembre e la seconda il 23 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 giovedì, 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.
| |
| − | | |
| − | | |
| − | === Giovedì 13-10-05 ===
| |
| − | | |
| − | Lezione sospesa causa seminario
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | quoto direttamente il sito del corso:
| |
| − | | |
| − | POSSIBILE CAMBIAMENTO DI ORARIO DEL CORSO DI FRO:
| |
| − | | |
| − | A PARTIRE DALLA SETTIMANA CHE INIZIA LUNEDì 24 OTTOBRE, L’ORARIO POTRA’ DIVENTARE
| |
| − | | |
| − | Lunedì 14,30 – 16,30 in un’aula di Via Celoria 20 da definirsi
| |
| − | | |
| − | Mercoledì 15,30 – 17,30 aula 307 in Via Celoria 20
| |
| − | | |
| − | La conferma verrà comunicata mercoledì 19 ottobre. La lezione di giovedì 20 si terrà comunque.
| |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 19-10-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Creazione di modelli matematici lineari per i problemi di:
| |
| − | Miscelazione ottimale (=blending)
| |
| − | Turnazione del personale
| |
| − | Problema dei trasporti (un caso particolare deo modelli di flusso)
| |
| − | Assegnazione del personale (quello introdotto nella prima lezione)
| |
| − | Localizzazione servizi
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | E' stato confermato il cambiamento d'orario dal giovedì al lunedì, il nuovo orario (dalla prossima settimana) sarà:
| |
| − | * Lunedì 14:30-16:30 in aula 208
| |
| − | * Mercoledì 15:30-17:30 in aula 307
| |
| − | | |
| − | | |
| − | === Lezione di Giovedì 20-10-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Modelli matematici lineari per problemi di:
| |
| − | Fixed charge
| |
| − | Schedulazione dei processi (su macchina a singolo processore)
| |
| − | Bin packing
| |
| − | * Programmazione lineare continua:
| |
| − | | |
| − | -definizione di soluzione ammissibile e soluzione ottima
| |
| − | | |
| − | -Formalizzazioni di problemi: Generale e Standard
| |
| − | | |
| − | -Procedimento per il passaggio da Generale a Standard (l'inverso è banale)
| |
| − | | |
| − | * Risoluzione grafica dei vincoli del modello lineare:
| |
| − | | |
| − | -individuazione degli iperpiani di supporto dei vincoli
| |
| − | | |
| − | -individuazione del poliedro che determina la regione ammissibile (conditio sine qua non per passare l'esame)
| |
| − | | |
| − | -calcolo del gradiente dei vincoli e della funzione obbiettivo
| |
| − | | |
| − | -individuazione del vertice ottimo per via grafica (con la retta ortogonale al gradiente della funzione obbiettivo)
| |
| − | | |
| − | | |
| − | === Lezione di Lunedì 24-10-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Ricerca del vertice ottimo: 3 metodi per trovarlo
| |
| − | - Ortogonale al gradiente
| |
| − | - Inesistenza direzioni con miglioramento dal vertice
| |
| − | - Individuazione del cono dato dai gradienti dei vincoli
| |
| − | * '''Geometria della programmazione lineare'''
| |
| − | * Definizione di iperpiano, semispazio, poliedro, politopo, vertice
| |
| − | * Teorema di Minkowski-Weil: ogni punto di un politopo può essere ottenutocome combinazione convessa dei suoi vertici
| |
| − | * Teorema: se l'insieme delle soluzioni di un problema è limitato, allora esiste almeno un vertice ottimo (con dimostrazione)
| |
| − | * '''vertici e soluzioni di base'''
| |
| − | * Definizione di base di una matrice, variabili in base e fuori base, soluzione di base (ammissibile e degenere)
| |
| − | * Teorema: un punto x in P è un vertice del poliedro non vuoto P={x | Ax=b e x>=0} se e solo se x è una soluzione di base
| |
| − | * Esempi: esercizi per riconoscere variabili in e fuori base e per trovare soluzioni di base
| |
| − | * Introduzione all'algoritmo del simplesso
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | A causa del cambio di orario il primo compitino è stato spostato a lunedì 21 novembre
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 26-10-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | '''Algoritmo del simplesso'''
| |
| − | * riscrittura della funzione obbiettivo in funzione delle variabili fuori base e studio del vettore dei coefficienti di costo ridotto per determinare se la soluzione è ottima
| |
| − | * Teorema: una soluzione di base di un problema di PLC (programmazione lineare continua) in forma di minimo è ottima se il vettore dei coefficienti di costo ridotto delle variabili fuori base è non negativo (dimostrazione)
| |
| − | * Metodo di ricerca del vertice ottimo tramite l'azzeramento di una delle variabili in base
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | La lezione di lunedì 31 ottobre è sospesa
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 2-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Metodo dei tableau:
| |
| − | passo di pivot
| |
| − | regola di blandt
| |
| − | criteri per riconoscere una base degenere
| |
| − | | |
| − | * Metodo delle 2 fasi:
| |
| − | FASE 1: ricerca dell'ammissibilità
| |
| − | FASE 2: ottimalità o illimitatezza (=algoritmo del simplesso)
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 7-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * ancora prima fase del simplesso (vista più approfonditamente)
| |
| − | * esempio di risoluzione di un problema di PLC col metodo delle 2 fasi
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | L'iscrizione al sifa per l'esame di novembre si riferisce all'appello completo, per il compitino non ci si deve iscrivere. Oggi sono stati presi i nominativi di chi ha intenzione di sostenere la prova, ma solo per dare al prof un'idea approssimativa della quantità di gente
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 9-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Stima per eccesso della soluzione ottima di un problema di PLC
| |
| − | * definizione di diseguaglianza valida
| |
| − | * Lemma di Farkas (con dimostrazione)
| |
| − | * Duale di un problema di PLC
| |
| − | * Teorema di idempotenza della dualità
| |
| − | * Teorema di dualità debole e suo primo corollario
| |
| − | * Schema delle regole per il passaggio da primale a duale
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | Trubian si è reso disponibile per fare due ore di esercizi l'ultimo venerdi
| |
| − | prima del compitino. Doveva vedere se c'erano aule disponibili.
| |
| − | Comunque dovrebbe fare queste due ore dalle 12.30 alle 14.30
| |
| − | | |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 14-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Secondo corollario del teorema della dulità debole
| |
| − | * Teorema della dualità forte (con dimostrazione)
| |
| − | * Definizione di problema "ben posto"
| |
| − | * Esercizi di trasformazione da primale a duale
| |
| − | * Metodo di risoluzione del duale tramite gli scarti complementari
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | Gli argomenti del compitino saranno:
| |
| − | Risoluzione grafica di un problema di PL
| |
| − | Mettere un modello in forma canonica rispetto a una certa base
| |
| − | Algoritmo del simplesso
| |
| − | Trasformazione primale-duale
| |
| − | Risoluzione del duale col metodo degli scarti complementari
| |
| − | Analisi della sensitività (argomento che tratterà mercoledì)
| |
| − | | |
| − | Le 2 ore di esercitazione di venerdì 18 sono state confermate e si terranno in aula V5 (via venezian) dalle 12:30 alle 14:30
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 16-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Analisi della sensibilità (metodo algebrico + metodo grafico)
| |
| − | * Esercizi sull'analisi della sensibilità
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | Il prof ha chiesto a chi non si era segnato sul foglio per il compitino e ha intenzione di farlo (e a chi si era segnato e ha deciso di rinunciare) di mandargli un'email per informarlo, in modo da sapere quante copie del compito dovrà stampare
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 23-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Spiegazione delle motivazioni che portano alle regole per il passaggio da primale a duale (accenni di analisi parametrica)
| |
| − | * Nuova interpretazione dell'algoritmo del simplesso che considera il duale:
| |
| − | Individuazione nel tableau di 3 condizioni necessarie per l'ottimalità:
| |
| − | -ammissibilità per il primale
| |
| − | -ammissibilità per il duale
| |
| − | -ortogonalità (=scarti complementari)
| |
| − | * Algoritmo del simplesso duale
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 28-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Programmazione lineare intera
| |
| − | visualizzazione grafica
| |
| − | rilassamento del problema
| |
| − | relazioni tra la soluzione ottima di un problema di PLI e la soluzione ottima del suo rilassamento continuo
| |
| − | inviluppo convesso
| |
| − | criterio per stabilire per che tipo di problemi di PLC ho sempre soluzioni ottime intere
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 30-11-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Definizione di unimodularità (UM) e unimodularità totale (TUM)
| |
| − | * Criteri di unimodularità totale
| |
| − | * Definizione di taglio (valido)
| |
| − | * Algoritmo dei piani di taglio
| |
| − | * Disuguaglianze di Chvatal
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 5-12-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Tagli di Chvatal, rango di Chvatal, chiusure di Chvatal
| |
| − | * Tagli di Gomory (forma intera e forma frazionaria)
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 12-12-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Branch & Bound
| |
| − | * Tipi di rilassamento per un problema di ottimizzazione combinatoria:
| |
| − | continuo
| |
| − | per eliminazione
| |
| − | lagrangiano
| |
| − | surrogato
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 14-12-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Considerazioni sui rilassamenti: confronto tra i vettori soluzione ottenuti nei diversi rilassamenti
| |
| − | * Problema di knapsack (zaino): risoluzione tramite branch&bound con rilassamento continuo
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 19-12-05 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | INTRODUZIONE ALLA TEORIA DEI GRAFI:
| |
| − | * Definizione di grafo (non) orientato, grafo pesato su lati/archi/vertici, taglio (uscente/entrante) indotto, grado (uscente/entrante) di un nodo, cammino (semplice/elementare), circuito (euleriano/hamiltoniano), costo di un cammino, sottografo indotto, grafo (fortemente) connesso, grafo aciclico, albero, albero di copertura
| |
| − | * Algoritmo di Kruskal per trovare l'albero di copertura di costo minimo in un grafo pesato (e modello matematico del problema)
| |
| − | | |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | Mercoledì 21 dicembre non c'è lezione, ci si vede dopo le vacanze
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Lunedì 9-1-06 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Dimostrazione correttezza dell'algoritmo di Kruskal
| |
| − | * Algoritmo di Prim-Dijkstra per trovare tutti i cammini di costo minimo partendo da un nodo fissato in un grafo pesato non orientato
| |
| − | * Algoritmo di Dijkstra per trovare tutti i cammini di costo minimo partendo da un nodo fissato in un grafo pesato orientato e con pesi non negativi (e modello matematico del problema)
| |
| − | | |
| − | | |
| − | | |
| − | === Lezione di Mercoledì 11-1-06 ===
| |
| − | | |
| − | '''Argomenti trattati nella lezione di oggi''':
| |
| − | | |
| − | * Problema di flusso massimo (modello matematico che lo descrive)
| |
| − | * Definizioni di: taglio s-t, capacità di un taglio s-t, rete incrementale, arco saturo/scarico, cammino aumentante
| |
| − | * Teorema Max Flow Min Cut
| |
| − | * Algoritmo di Ford-Fulkerson per il problema di flusso massimo
| |
| − | | |
| − | '''AVVISO'''
| |
| − | | |
| − | Il compitino di mercoledì 18 è stato spostato a lunedì 23 (ora da definirsi)
| |
