Fondamenti di ricerca operativa/2005-2006

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

• 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 [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].

Alcuni appunti online disponibili 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)

Lezione di Lunedì 16-1-06

Argomenti trattati nella lezione di oggi:

• Problema di flusso massimo a costo minimo (modello matematico + metodo risolutivo)
• esercizi su Dijkstra, Prim, rilassamento lagrangiano

Lezione di Mercoledì 18-1-06

Argomenti trattati nella lezione di oggi:

• Esercizi su modellizzazione di problemi su grafi, knapsack, modello per determinare il ciclo hamiltoniano di costo minimo (non c'è nel compitino)

AVVISO

Il compito di lunedì 23 si terrà in aula G14 alle ore 14:30. Non è prevista iscrizione sul sifa.